前言

隐私集合求交（Private Set Intersection，即PSI）是一个特定的安全多方计算（Multi-Party Computation, 即MPC）问题，其问题可以简单理解为：Alice 输入集合 ，Bob 输入集合 ，双方执行 PSI 协议可以得到 Alice 和 Bob 两者的交集，同时不在交集范围内的部分是受保护的，即 Alice 和 Bob 无法学习出交集以外的任何信息。

隐私集合求交(PSI)协议有很多分类方法，按照底层依赖的密码技术分类主要包括：

• 基于公钥密码的PSI方案，包括：基于密钥交换（DH: Diffie-Hellman）的PSI方案和RSA盲签名的PSI方案；
  
• 基于不经意传输（OT: Oblivous Transfer）的PSI方案；
  
• 基于通用MPC的PSI方案，例如基于混淆电路（GC: Garbled Circuit）的PSI方案；
  
• 基于同态加密（Homomorphic Encryption）的PSI方案；
  

按照双方待求交集合大小是否相等进行分类，可分为：

• 平衡的PSI（Balanced PSI）：两方集合大小接近，即
  
• 非平衡的PSI （Unbalanced PSI）：两方集合大小相差加大，即
  

本文先介绍非平衡隐私集合求交(Unbalanced PSI)的需求和应用场景，然后介绍相关的背景知识，最后介绍两种专门的Unbalanced PSI协议。

01

非平衡隐私集合求交需求和应用场景

图1 Unbalanced PSI示意

大多数的 PSI 协议考虑的是两方数据集合大小基本相等的情况，在一些场景下求交双方的数据集大小差异较大，具体是指一方集合很小，一方集合很大的求交情况，即 ，这种场景的隐私集合求交称为：非平衡隐私集合求交(Unbalanced PSI)。

• 寻找联系人
  

当一个用户注册使用一种新的服务（如微信、Whatsapp 等）的时候，从用户的现有联系人中寻找有哪些已经注册了同类的服务是一种在大多数情况下十分必要的操作。通过将用户的联系人发送给服务提供商可以有效地完成这项功能，但是与此同时用户的联系人信息，一种在大多数情况下被认为是隐私的信息，也被暴露给服务提供商了。因此在这种场景下，将用户的联系人信息作为一方的输入，将服务提供商的所有用户信息作为另一方的输入来进行PSI 协议可以完成发现联系人的功能，而且可以防止交集以外的信息泄露给任何一方。

• 口令安全检查
  

通过与已经泄露的口令数据集对比，可以判定用户口令的安全性。用户如果直接将口令传输给服务器的话，用户口令的隐私不会得到满足。为保护用户口令隐私，系统使用隐私求交技术来保障既帮助检测口令是否安全，同时又不泄露用户口令隐私。例如：Google 开发的 Password Checkup，微软的Password Monitor。

• 联邦学习样本对齐
  

在联邦学习发起训练之前，必须基于双方的数据进行PSI，使用双方共有的用户信息（例如用户ID）找出交集，从而对应两方数据的特征和标签，在对齐的数据集上进行模型训练才有意义。

上面几种典型应用中，两方的数据量差异比较大，例如，10w vs 10亿的隐私集合求交。通用的balanced PSI协议在两方集合大小差异大的情况下，两方的计算量基本相同，跟大数据集的集合大小成线性关系，数据集小的一方也要按照大数据集的规模配置计算和通信资源，对于数据集小的一方计算资源需求和消耗太大。一些研究成果对于Unbalanced PSI这种比较常见而有实际应用价值的场景做优化，并且取得了较好的结果。

图2  DH PSI协议流程

以基于密钥交换(DH: Diffie-Hellman)的PSI方案为例，介绍在两方数据集差异很大时的计算。如图2中DH-PSI的流程，包括4个步骤：

1. alice对 计算 次幂指数 ，发送到bob
   
2. bob对 计算 次幂指数 ，发送到alice
   
3. bob对 计算 次幂指数 ，发送给alice
   
4. alice对 计算 次幂指数
   

可以看到alice数据集远小于bob数据集的情况下，alice和bob的计算量都是 ，alice要按照bob的数据集规模配置计算资源，对alice要求太高。

02

背景知识

2.1 不经意伪随机函数(OPRF)

伪随机函数(PseudoRandom Function PRF)是密码学中的基础函数，与伪随机生成器(PseudoRandom Generator PRG)、伪随机置换(PseudoRandom Permuation PRP)等基础组件之间也可以相互转换。伪随机函数的定义可以参见下图，根据密钥 和输入 得到结果 ，在不知道密钥 的假设下 和随机数差异可以忽略。

图3 PRF定义

最典型的PRF应用是在传输层安全协议(Transport Layer Security TLS)中，TLS 握手(handshake)阶段通过协商得到预主密钥(PreMaster Key)，预主密钥经过PRF计算得到主密钥(Master Key)，主密钥再使用PRF得到通信加密和认证密钥。

图4 OPRF协议框架

不经意伪随机函数(Oblivious PseudoRandom Function OPRF)是客户端和服务端之间计算伪随机函数(PRF)的两方协议。服务端提供伪随机函数(PRF)的密钥 ，客户端提供输入 ，协议结束后客户端得到 。不经意伪随机函数(OPRF)有很多构造方法，如：RSA、DH和不经意传输(Oblivious Transfer)。

2.1.1 基于OPRF的PSI框架

文献[HL08]提出了基于OPRF实现PSI协议，可以抽象为如下图所示的协议流程。

图5 基于OPRF构造PSI协议的通用框架

图3协议中bob产生密钥 ，并对数据集 计算 ，alice和bob执行上节提到的不经意伪随机函数，得到数据集 的OPRF结果 。通过比较两方集合的PRF值，得到交集结果。

2.1.2 OPRF相关标准

IETF草案《使用素数阶群的OPRF》给出了基于素数阶群构造OPRF的方法，定义了函数名称、参数、数据格式和标准向量。

图6 基于素数阶群DH构造OPRF 

IETF草案《使用素数阶群的OPRF》协议过程如下：

1. 客户端随机选择 , 将输入 映射到群 中的元素 ，计算 ，发送给服务端。
   
2. 服务端接收到 后，计算 ，发送给客户端。
   
3. 客户端接收到 后，计算 得到 ，计算 。
   

IETF草案《使用素数阶群的OPRF》将上面三个步骤中的计算部分定义为三个函数（Blind，Evaluate和Finalize），并给出了具体的函数名称、参数和标准向量。

IETF草案《使用素数阶群的OPRF》给出了候选的素数阶群，包括：

• ristretto255, SHA-512
  
• decaf448, SHAKE-256
  
• P-256, SHA-256
  
• P-384, SHA-384
  

ristretto是将非素数阶的ecc群转换为素数阶群的一种方法，ristretto255是将curve25519(阶是8乘以一个素数)的点群转换为素数阶群的实现。除了ristretto255外，其他阶为大素数或具有大素数阶子群的椭圆曲线也可以作为候选，例如比特币使用的secp256k1曲线或商密SM2定义的曲线也可作为候选。文献[CMGD+21]及其开源实现APSI建已使用FourQ曲线。

2.2 全同态加密(Full Homomorphic Encryption FHE)

全同态加密(Full Homomorphic Encryption FHE)是一种强大的密码原语，可以对加密的数据执行任意(算术或二进制)电路运算，电路运算后的结果还是加密的，可以使用解密密钥进行解密。但是全同态加密一般计算开销比较大，常用的全同态加密方案是分级全同态加密方案(leveled Full Homomorphic Encryption FHE)，即加密方案的参数选择只允许执行有限的乘法深度。

全同态加密(Full Homomorphic Encryption FHE)可用于设计隐私集合求交协议和隐匿查询协议，在通信量和计算上都有加到的优势。

03

快速非平衡隐私求交协议

文献[RA18]中给出了半诚实模型下的快速非平衡隐私集合求交协议，并给出了实现参考和性能。[RA18]的PSI协议可以看做图5 OPRF构造PSI协议的一种具体实现方法，其中OPRF协议采用2.3节中描述的OPRF协议。

协议过程中bob产生密钥 ，并对数据集 计算 ，alice和bob执行上节提到的不经意伪随机函数，得到数据集 的OPRF结果 。

图7 [RA18] Unbalanced PSI协议流程

该协议分为离线和在线阶段：

• 离线阶段
  

bob端对数据集 , 计算 ，发送给alice，alice对接收到的数据进行缓存。bob端的计算量主要是 次幂运算。

• 在线阶段
  

alice和bob对数据集 执行不经意伪随机函数，alice端得到 。比较两个集合得到交接结果。alice端的计算量主要是 次幂运算，bob端的计算量主要是 次幂运算。

总体计算量方面，[RA18] Unbalanced PSI比dh-psi减少一半。[RA18] Unbalanced PSI 在线阶段只和小数据集的大小 相关。考虑到 , 在线阶段执行很快。可以看到上面的协议更适合Unbalanced PSI 的情形。

04

基于FHE的Unbalanced PSI 协议

文献[CLR17]给出了使用全同态(Level Full Homorphic Encryption)构造PSI的方法，并给出了优化方法。[CHLR18]中提出在预处理阶段使用不经意随机函数(OPRF)对原始数据进行安全加强。[CMGD+21]给出了具体的参数优化方法，减少了在线阶段计算和通信量，并给出了和[RA18]的性能对比。

图8 FHE PSI协议流程

FHE PSI协议流程：

• 数据预处理阶段
  

alice和bob在线执行OPRF协议，alice得到数据集 的OPRF结果 。

• 在线求交阶段
  

1. alice计算 部分幂指数的FHE密文，发送给bob;
   
2. bob计算得到 所有需要幂指数，计算插值多项式的密文结果 ，发送给alice；
   
3. alice对插值多项式的密文结果 解密, 如果解密为0，则 。
   

FHE 的Unbalanced PSI 和[RA18] 中的Unbalanced PSI 相比，优势在于不需要传输大数据集的相关数据，在执行完不经意伪随机函数(OPRF)后，通过增加一轮查询交互，即FHE的查询密文和返回，得到交集。

相关链接

[Password Checkup]https://security.googleblog.com/2019/02/protect-your-accounts-from-data.html

[Password Monitor] https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/

[传输层安全协议] https://datatracker.ietf.org/doc/html/rfc5246/#section-5

[使用素数阶群的OPRF] https://www.ietf.org/archive/id/draft-irtf-cfrg-voprf-09.html

[ristretto] https://ristretto.group/ristretto.html

[secp256k1] http://www.secg.org/sec2-v2.pdf

[APSI] http://github.com/microsoft/APSI

[FourQ] http://github.com/microsoft/FourQlib

参考文献

[HL08] Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries

[CT10] Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity

[CKT10] Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model

[KLSAP17] Private Set Intersection for Unequal Set Sizes with Mobile Applications

[RA18]  Faster Unbalanced Private Set Intersection

[CLR17] Fast Private Set Intersection from Homomorphic Encryption

[CHLR18] Labeled PSI from Fully Homomorphic Encryption with Malicious Security

[CMGD+21] Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication

[draft-irtf-cfrg-voprf-09] Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups