隐私计算实训营学习五：隐语PSI介绍及开发指南

一、SPU 实现的PSI介绍

1.1 PSI定义和种类

1.1.1 PSI定义和种类

PSI(Private Set Intersection)安全求交集： 是一种特殊的安全多方计算(MPC)协议。 Alice持有集合X，Bob持有集合Y，Alice和Bob通过执行PSI协议，得到交集结果X∩Y，除交集外不会泄漏交集外的其它信息。

PSI分类：

1. 2-Party/Multi-Party PSI

2. Balanced/Unbalanced) PSI

3. Semi-honest/Malicious PSI

4. PSI with computation：

   PSI-CA(Cardinality)

   PSI-Payload Analytics

   Circuit PSI

1.1.2 隐语PSI功能分层

基础组件层： 包含基础密码算法与协议。
PSI协议实现层： 协议实现主要在中间SPU层，包含不同类型PSI协议实现；SPU往上封装了bucket_psi统一PSI入口，通过入口可以屏蔽不同协议的差异，调用时只需要指定输入与协议类型即可调用PSI。
PSI功能封装层： python调用框架secretflow，包含psi_csv与psi_df；再往上包含MVP(最小功能实现)与kuscia，有白屏、openapi与调用功能；还有SCQL通过SQL语句执行PSI与安全多方计算内容。

1.2 SPU 实现的PSI介绍

1.2.1 半诚实模型

1、两方

1. ecdh、kkrt16、bc22(pcg-psi)
2. ec-oprf PSI (Unbalanced PSI)
3. dp-psi

2、多方

1. ecdh-3-party(可扩展到多方)

---

1、ecdh-PSI介绍： 协议简单、易于理解与实现、通信成本小、计算量大、易于扩展到求交集数量与计算PSI类型。

实现过程：
1、Alice将自己的数据哈希到ECC点，通过私钥对这些点进行加密点乘，然后发送给bob。
2、bob对自己的value数据也做点乘，同时对接收到Alice数据，用其私钥β也做一次点乘计算。
3、Alice方计算y的α次方得到x的αβ次方与y的αβ次方，计算交集。

隐语实现的ecdh-PSI优点： 性能提升：测评及合规需求、互联互通。

---

2、KKRT16介绍：扩展了IKNP和KK OT，并且基于它们构造了新的Batch，Related-key OPRF。优点为运行时间较快，16年之后的多PSI协议大多数和KKRT作为比较基准。缺点为内存占用量比较大，通信量大。

主要流程： 主要构建为cuckoo hash、OT Extension、OPRF。

cuckoo hash：基于多个哈希，此处以3个哈希为例。左侧对X做3个哈希，判断哈希里面有没有H1X1位置有没有数据，若为空则放入H1位置，否则放入H2，H2若被占用放入H3…，若全部被占用则随机找一个位置将其替换。

KKRT优化： CuckooHash、AES->(Pipeline AES、Vector AES)、计算量大的矩阵转置(算法、intel比特转换指令加速)。

---

3、BC22 PCG介绍：基于sVOLE构建的BaRK-OPRF，以及Generalized Cuckoo Hash和Permutation-Based Hashing。Generalized Cuckoo Hash：普通的Cuckoo Hash每一行只有一个元素，有冲突放入下一个位置；Generalized每一行元素扩展到2个或3个。

BC22协议流程： 借助于VOLE方案，需要根据Cuckoo Hash的数量和每一行元素构建若干数量的VOLE，同时插入Cuckoo Hash和Simple Hash，再构建Bark-OPRF，双方交互OPRF值，在左侧计算出交集。

实现时选用的参数：

---

4、Unbalanced PSI介绍：实际应用出现两方数量级差值较大，渐少计算量。

ec-oprf based大致流程： Alice计算H(x)的α次方，Bob计算H(x)的αβ次方，Alice收到后再计算的H(x)α/1次方得到H(x)的β次方，与发送过来的H(y)的β次方做比较得到交集。

SHE-based大致流程： 同态PSI方案，有点为不需要吧大数据方的数据传输到小数据方，服务端会对数据做差值多项式，客户端将查询的数据同态发送到服务端，服务端计算多项式的结果返还给客户端，客户端解密若为0表示x在y集合中，否则x不在服务端数据中。缺点为计算量比较大，运行时间长。

---

5、基于ecdh的三方PSI协议介绍：

基于ecdh的三方PSI： 优点基于ecdh-psi，协议简单易于实现；缺点为泄露Alice和Bob两方交集数量。

协议流程：

1. Alice和Bob先进行交互，得到shuffle后的两方交集

2. Alice将shuffle后两方交集，发给Charlie

3. Charlie加密后的数据依次给Bob和Alice加密

4. Charlie比较密态数据，得到交集
   

1.2.2 PSI实现位置

二、SPU PSI调度架构

SPU调用架构： SecretFlow层有psi_csv，然后通过Bucket PSI分桶调度解决大数据问题，利用千万数据分为多个百万数据合并求交。

接口封装层： 分为bucket_psi、mem_psi、operator，通过operator将不同的协议注册到mem_psi统一由bucket_psi做调度。

bucket_psi： 包括调用时配置(psi类型、接收方标识、是否广播结果、输入输出参数、协议类型、分桶大小)。

memory_psi： 包括调用时配置(psi类型、接收方标识、是否广播、协议类型)。

operator协议注册给psi：

batch_provder读取csv文件接口： 指定每次读取数量分批读取数据。

三、Secretflow PSI开发指南

部署模式： 仿真模式与生产模式。

1、启动Ray集群。

2、初始化secretflow。

3、启动SPU设备。

4、执行PSI：配置psi_csv参数，输入、输出路径、协议类型、输出检查、输出排序等。

四、隐语PSI后续计划