星河杯“黑名单共享查询”赛题基于隐语实现baseline #441

halosecret00 · 2023-04-14T04:02:44Z

halosecret00
Apr 14, 2023

🌟星河杯大赛专辑

隐语纵向联邦 SecureBoost Benchmark白皮书

隐语 PSI benchmark 白皮书

隐语 Unbalanced PSI Benchmark 白皮书

基于同态的隐私信息检索协议-SealPIR介绍

星河杯“诈骗电话识别”赛题基于隐语实现baseline（即将更新，敬请期待！）

赛题情况介绍

星河杯隐私计算大赛“黑名单共享查询-多方安全计算”赛题，要求参赛者基于多方安全计算技术实现多家企业黑名单数据的安全共享查询功能，完成以下两项任务：

计算两方黑名单ID交集

参与方A：作为任务发起方、数据提供方、计算方、结果方；
参与方B：作为数据提供方、计算方；
各参与方的网络带宽为100Mbps；
在半诚实敌手模型下，保证计算过程中各方原始数据、各数据方的本地中间数据、计算结果不被泄露，计算结果仅结果方可获取。

根据ID匿踪查询黑名单样本信息

参与方A：作为查询方，提供待查询ID；
参与方B：处理查询请求，返回查询结果；
各参与方的网络带宽为100Mbps；
在半诚实敌手模型下，保证查询方的查询目标不被泄露（不可区分度与样本量相同），查询方不能获得查询结果之外的其他信息

任务一：计算两方黑名单ID交集

1、方案整体说明

两方黑名单ID交集赛题要求是100M网络环境半诚实模型下两方PSI协议。隐语目前实现了多种类型的PSI协议，包括：半诚实模型/恶意模型、两方/三方等。适合两方黑名单ID交集赛题的PSI协议包括：

ecdh based psi
kkrt16 psi
bc22 psi

详细的协议介绍和参考文献可参考官网的PSI介绍[1]。

2、方案原理介绍

隐语框架通过ray来调度具体的隐私计算任务，包括mpc、he、psi等，分别在不同的功能组件中实现。其中：

SPU：实现了MPC(semi-2k、ABY3)和PSI、PIR协议
HEU：实现了同态算法（主要以半同态为主）和相关运算

在执行一个具体的两方PSI任务时，可分为如下步骤：

编写psi任务 python代码，并在ray主节点/集群A执行
ray主节点/集群A分解psi任务到两方任务节点
两方任务节点按角色（sender/receiver）定义执行PSI协议交互，得到PSI结果并输出到csv文件。

3、方案安全性说明

算法安全性：

ecdh-psi协议安全性参考[2]
KKRT16 协议安全性参考[3]
BC22 协议安全性参考[4]

通信安全：

隐语所依赖的rayfed中使用的是标准的mTLS，其实际实现是使用了grpc自带的mTLS能力
隐语 spu通信安全brpc的TLS能力

安全参数：

ecdh psi支持的曲线包括：curve25519、fourq、sm2、secp256k1，安全参数均达到128比特安全

kkrt/bc22 psi中，base OT使用的是curve25519，OT扩展使用的128bit AES，均达到128bit安全

高于比赛要求的112bit安全

统计安全参数：40bit，高于比赛要求的30bit

结果安全：

仅结果方能获得模型结果，除预期结果外，不能输出额外的敏感信息

密码安全：

PSI中使用的密钥大多是临时密钥，由安全的PRG模块生成，不涉及存储、备份、归档；

通信安全的私钥，比赛选手可自行设计安全机制。

安全随机数：隐语支持NIST SP 800-90A ctr-drbg和《GM/T 0105-2021软件随机数设计指南》中的基于SM4_CTR RNG。

采用Intel DRNG (Digital Random Number Generator）作为硬件熵源，为随机数模块提供安全的种子。

4、具体实现与性能

两台阿里云ECS，8269CY 16c 2.5GHz，128G内存

不同PSI的性能数据如下：单位（s）

	LAN	100Mbps
ecdh(25519)	56.15	55.47
ecdh(fourq)	10.79	11.86
kkrt	7.44	15.87
bc22	7.49	11.12

100Mbps带宽时性能数据，可以看到ecdh-psi选择fourq曲线，以及bc22两种PSI性能较好。

具体代码参见隐语psi benchmark白皮书[5]

SPU TLS配置可参考隐语官网API说明[6]

5、提升建议

选手可以自行设计部署调用方式
选择合适的PSI协议，自己设计优化方案。
选择合适的TLS密码算法套件：公私钥（RSA或ECC）、证书类型(证书签发层级），对称算法和完整性算法

任务二：根据ID匿踪查询黑名单样本信息

1、方案整体说明

ID匿踪查询黑名单赛题要求是100M网络环境半诚实模型下匿踪协议。隐语目前实现了SealPIR和labeled psi两种PIR协议，可分明用于index PIR和keyword PIR，赛题中数据量为百万，ID为18位十进制整数，可以使用隐语中基于微软APSI封装的keyowrd PIR方案。

2、方案原理介绍

ray框架调度原理

隐语框架通过ray来调度具体的隐私计算任务，包括mpc、he、psi等，分别在不同的功能组件中实现。其中：

SPU：实现了MPC(semi-2k、ABY3)和PSI、PIR协议
HEU：实现了同态算法（主要以半同态为主）和相关运算

在执行一个具体的两方PIR任务时，可分为如下步骤：

编写pir任务 python代码，并在ray主节点/集群A执行
ray主节点/集群A分解pir任务到两方任务节点
两方任务节点按角色（client/server）定义执行PIR协议交互，得到PIR结果并输出到csv文件。

keyword PIR基本原理

假设服务的key/value键值对是：(-3,242),(-2,198),(-1,1.4),(0,-31) (1,88),(2,66),(3,-228)

服务端
根据key，即(-3,0),(-2,0),(-1,0),(0,0) (1,0),(2,0),(3,0)，插值得到查询多项式P(x)。
根据key/value键值对，即(-3,242),(-2,198),(-1,1.4),(0,-31) (1,88),(2,66),(3,-228)得到value的插值多想式Q(x)
客户端
发送查询值x的同态加密结果给服务端，
服务端
服务端根据同态运算分别计算P(x)和Q(x)的密文结果，并发送给客户端
客户端
客户端解密P(x)的密文，若结果为0，表示x在服务端数据key列表中，解密Q(x)的密文，得到x对应的value。

3、方案安全性说明

算法安全性：

Labeled PSI的原理可参考下面的论文：

CLR17**[7]** Fast Private Set Intersection from Homomorphic Encryption

CLHR18**[8]** Labeled PSI from Fully Homomorphic Encryption with Malicious Security

CMCD+21**[9]**Labeled PSI from Homomorphic Encryption with ReducedComputation and Communication

通信安全：

隐语所依赖的rayfed中使用的是标准的mTLS，其实际实现是使用了grpc自带的mTLS能力
隐语 spu通信安全brpc的TLS能力

安全参数：

ec-oprf支持的曲线为：fourq，安全参数均达到128比特安全。

同态算法使用的是BFV算法，相关参数按照128比特安全选取。

统计安全参数：40bit，高于比赛要求的30bit。

结果安全：

保证查询方查询目标不被泄漏，查询方不可获取查询结果外的其他信息。详细论证可参考上方给出的论文。

密码安全：

PIR中客户端使用的ec-oprf盲化密钥和BFV密钥是临时密钥，由安全的PRG模块生成，不涉及存储、备份、归档；

PIR中服务端使用ec-oprf密钥，由安全的PRG模块生成，选手可自行设计安全机制，部署时生成或安全导入。

通信安全的私钥，比赛选手可自行设计安全机制。

安全随机数：隐语支持NIST SP 800-90A ctr-drbg和《GM/T 0105-2021软件随机数设计指南》中的基于SM4_CTR RNG。

采用Intel DRNG (Digital Random Number Generator）作为硬件熵源，为随机数模块提供安全的种子。

4、具体实现与性能

两台阿里云ECS，8269CY 16c 2.5GHz，128G内存

keyword PIR的性能数据如下：单位（s）

16c	setup	query	total	query(100M)	totoal(100M)
1-100w	32	27	59	32	64
10-100w	99	13	112	14	113

赛题规定了，客户端的查询量为10条数据，上面给出了两种参数设置时的性能情况：

1-100w，每次查询1个，查询10次完成所有查询
10-100万，每次查询10个，查询1次完成所有查询

可以看到，1-100w对应的性能数据优于10-100w的性能数据。

服务端部分数据示例：

id	register_date	age
167019600627484111	2008-10-29	36
623049248851670423	2011-12-14	32
453108121117357944	2008-11-22	43

register_date+age一起为查询特征，总长度为12字节，加上分隔符‘,’，和填充长度(4 bytes)信息，max_label_length可以设为18。

1.使用spu中python接口进行PIR任务

服务端offline/setup

python examples/python/pir/pir_setup.py --in_path B_PIR_DATA.csv \
--key_columns id --label_columns register_date,age \
--count_per_query 1 -max_label_length 18 \
--oprf_key_path oprf_key.bin --setup_path setup_path

服务端查询响应脚本调用

python examples/python/pir/pir_server.py --party_ips ip0:port0,ip1:port1 \
--rank 1 --oprf_key_path oprf_key.bin --setup_path setup_path --enable_tls True \
--link_server_certificate server.crt --link_server_private_key server.key \
--link_server_ca ca.crt --link_client_certificate client.crt \
--link_client_private_key client.key \ --link_client_ca ca.crt

客户端查询脚本调用

python examples/python/pir/pir_client.py --party_ips ip0:port0,ip1:port1 \
--rank 0 --in_path A_PIR_ID.csv --key_columns id \
--out_path pir_out.csv --enable_tls True \
--link_server_certificate server.crt --link_server_private_key server.key \
--link_server_ca ca.crt --link_client_certificate client.crt \
--link_client_private_key client.key \ --link_client_ca ca.crt

secretflow python脚本

import os
import sys
import time
import logging
import multiprocess
from absl import app
import spu
import secretflow as sf
#import random
# init log
logging.basicConfig(stream=sys.stdout, level=logging.DEBUG)

# SPU settings
# alice as pir client
# bob as pir server
cluster_def = {
    'nodes': [
        {
            'party': 'alice', 
            'id': 'local:0', 
            'address': f'127.0.0.1:17268', 
            'tls_opts': {
                'server_ssl_opts': {
                    'certificate_path': 'alice servercert.pem',
                    'private_key_path': 'alice serverkey.pem',
                    # The options used for verify peer's client certificate
                    'ca_file_path': 'cacert.pem',
                    # Maximum depth of the certificate chain for verification
                    'verify_depth': 1
                },
                'client_ssl_opts': {
                    'certificate_path': 'alice clientcert.pem',
                    'private_key_path': 'alice clientkey.pem',
                    # The options used for verify peer's server certificate
                    'ca_file_path': 'cacert.pem',
                    # Maximum depth of the certificate chain for verification
                    'verify_depth': 1
                }
            }
        },
        {
            'party': 'bob', 
            'id': 'local:1', 
            'address': f'127.0.0.1:17269', 
            'tls_opts': {
                'server_ssl_opts': {
                    'certificate_path': 'bob servercert.pem',
                    'private_key_path': 'bob serverkey.pem',
                    # The options used for verify peer's client certificate
                    'ca_file_path': 'cacert.pem',
                    # Maximum depth of the certificate chain for verification
                    'verify_depth': 1
                },
                'client_ssl_opts': {
                    'certificate_path': 'bob clientcert.pem',
                    'private_key_path': 'bob clientkey.pem',
                    # The options used for verify peer's server certificate
                    'ca_file_path': 'cacert.pem',
                    # Maximum depth of the certificate chain for verification
                    'verify_depth': 1
                }
            }
        },
    ],
    'runtime_config': {
        'protocol': spu.spu_pb2.SEMI2K,
        'field': spu.spu_pb2.FM128,
    },
}

link_desc = {
    'recv_timeout_ms': 3600000,
}

def main(_):
    # sf init
    # 这里是以单机仿真配置为例，选手可根据需要选用集群模式仿真或者生产模式部署
    sf.init(['alice','bob'],address='local',log_to_driver=True,omp_num_threads=multiprocess.cpu_count())

    # init log
    logging.basicConfig(stream=sys.stdout, level=logging.DEBUG)

    alice = sf.PYU('alice')
    bob = sf.PYU('bob')

    key_columns = ['id']
    label_columns = ['register_date','age']
    spu = sf.SPU(cluster_def, link_desc)

    pir_input_path = '/path/B_PIR_DATA.csv'
    pir_oprf_key_path = '/path/oprf_key.bin'
    pir_setup_path = '/path/sf_setup_path'

    start = time.time()

    # server setup
    reports = spu.pir_setup(
        server='bob',
        input_path=pir_input_path,
        key_columns=key_columns,
        label_columns=label_columns,
        oprf_key_path=pir_oprf_key_path,
        setup_path=pir_setup_path,
        num_per_query=1,
        label_max_len=18,
    )

    #print(f"psi reports: {reports}")
    logging.info(f"offline psi reports: {reports}")
    logging.info(f"cost time: {time.time() - start}")

    alice_input_path = 'A_PIR_ID.csv'

    # client config
    alice_config = {
        'input_path': alice_input_path,
        'key_columns': key_columns,
        'output_path': '/path/sf_pir_out.csv',
    }

    # server config
    bob_config = {
        'oprf_key_path': pir_oprf_key_path,
        'setup_path': pir_setup_path,
    }

    query_config = {
        alice: alice_config,
        bob: bob_config,
    }

    start = time.time()

    reports = spu.pir_query(
        server='bob',
        config=query_config,
    )

    logging.info(f"online pir reports: {reports}")
    logging.info(f"cost time: {time.time() - start}")

    sf.shutdown()

if __name__ == '__main__':
    app.run(main)

5、提升建议

选手可以自行设计部署调用方式
选择合适的keyword PIR参数，自己设计优化方案。
选择合适的TLS密码算法套件：公私钥（RSA或ECC）、证书类型(证书签发层级），对称算法和完整性算法

Reference

【1】https://www.secretflow.org.cn/docs/secretflow/

zh_CN/components/psi.html

【2】[HFH99] Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In ACM CONFERENCE ON ELECTRONIC COMMERCE. ACM, 1999.

参见：附录A CryptographicDetails--Private Preference Matching

[Mea86] C. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In 1986 IEEE Symposium on Security and Privacy, pages 134-134, April 1986.

参见：2 The Protocol

【3】[KKRT16] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched oblivious PRF with applications to private set intersection. In ACM CCS 2016, pages 818-829. ACM Press, October 2016.

参见：5.2 PSI from OPRF

【4】[BC22] Private Set Intersection from Pseudorandom Correlation Generators/Improved Private Set Intersection for Sets with Small Entries, eprint 2022/334, PKC2023

参见：4.1 A new membership batched OPRF.

参见：4.2 A new semi-honest PSI from mOPR

【5】https://www.secretflow.org.cn/docs/secretflow/zh\_CN/developer/benchmark/psi\_benchmark.html

【6】https://www.secretflow.org.cn/docs/secretflow/en/source/secretflow.html#secretflow.SPU.\_\_init\_\_

【7】Fast Private Set Intersection from Homomorphic Encryption

https://eprint.iacr.org/2017/299.pdf

【8】Labeled PSI from Fully Homomorphic Encryption with Malicious Security

https://eprint.iacr.org/2018/787.pdf

参见：7 Malicious Security

【9】Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication

https://eprint.iacr.org/2021/1116.pdf

隐语官网：