介绍了隐私求交的基本定义以及常见应用。介绍了常用的PSI协议以及它们的原理并进行了效率分析。基于哈希的PSI效率上达到了低通信量、低计算量，但在安全方面可能遭到攻击，故现在已经不采用这种方法进行隐私求交；基于公钥密码学的PSI实现了中计算量、低通信量，同时也保证了整个协议的安全。

简介

PSI(Private Set Intersection)是一种特殊的安全计算协议

参与方数量>= 2
功能：计算参与方数据的交集
安全：不泄露交集外的元素（需要Provable Security）

已有工作的两个主要思路：

通用安全计算（MPC, HE, ……）：天然支持后续安全计算
轻量级密码原语（OT, VOLE, ……）：效率高

两方半诚实PSI

挑战与要求：

隐私非交集元素（hiding)
- 密码学安全的"隐藏"
- 当两个元素不等时，必须对比较结果添加噪声（noise）以防止不匹配的元素被穷举计算
计算交集元素（comparing）
- 当两元素相等时，相等的结果应当**以某种方式（明文/支持后续安全计算）**的方式公布
高效率（efficiency）
- PSI协议应当在面对大规模应用时高效可用

常用的PSI协议及原理

Hash-based PSI（insecure）

密码学安全的哈希函数的安全性质包括：

单向性（抗原像攻击）：对任意给定的Hash码 $h$ ，找到满足 $H(x)=h$ 的 $x$ 在计算上是不可行的
抗第二原像攻击（抗弱碰撞性）：对任何给定的分快 $x$ ，找到满足 $y\ne x$ 且 $H(x)=H(y)$ 的 $y$ 在计算上是不可行的
抗碰撞攻击（抗强碰撞性）：找到任何满足 $H(x)=H(y)$ 的偶对 $(x,y)$ 在计算上是不可行的

效率：低计算量、低通信量

安全：可能遭到攻击

输入数据值小时遭到穷举攻击和字典攻击
不满足前向安全性

PKC-based PSI

PSI based on DH

基本思想：具有交换（commutative）性质的"双重加密"。（交换性质是进行比较的基础）

效率：中计算量、低通信量（仍为PSI的主流实现方式）

安全：PKC-based安全（基于离散对数问题（Discrete Logarithm Problem, DLP））

通过比较 $H(x_i)^d$ 和 $H(y_i)^d$ 求交。Receiver不能直接发送 $H(x_i)$ ，因此先引入掩码，在完成目标运算后消除掩码。

效率：中计算量、低通信量（接收方的计算量 $\ll$ 发送方计算量——解密操作耗时大于加密）

安全：PKC-based安全

OPRF-based PSI

伪随机函数（Pseudorandom Function, PRF)： $\forall k\in \mathcal{K},m\in \{0,1\}^l$ ，有 $F(k,m)\approx Uniform\ Random$

不经意伪随机函数（Oblivious PRF，OPRF）：给定一个来自Sender（Bob）的密钥 $k$ 和一个来自Receiver（Alice）的输入元素 $m$ :

Receiver知道 $m$ 和 $F(k,m)$ ，但是不知道 $k$
Sender只知道 $k$ ，但不知道计算结果和输入数据 $m$

流程示意如下图所示：

使用OPRF构造PSI：对于Receiver拥有的每一个数据 $x_i$ ，都会产生一个对应的 $k_i$ ，而Sender会利用 $k_i$ 对其每一个数据 $y_j$ 计算 $F(k_i,y_j)$ ，Receiver比对 $F(k_i,x_i)$ 和 $F(k_i,y_j)$ 。

Hiding：基于OPRF（通过秘密函数OPRF，使得Sender不知道Receiver的数据，而Receiver不知道秘密函数构造）
Comparing；比较数据经过秘密函数输出的结果
Efficiency：高计算量、高通信量（本地比较和通信都是 $O(n^2)$ ）

可通过Cuckoo Hashing + OPRF构造PSI（KKRT PSI Protocol），实现 $O(n)$ 规模的OPRF和本地比较

PSI需求与应用

除了常见的白/黑名单，撞库等，还有……

交集使用

动机：交集可能并不是PSI参与方间的常识（交集中的数据可能属于其他人）。比如：Alice使用相同ID在银行A和银行B都注册了信息，但是银行A和B不能通过PSI泄露Alice的联合明文信息。

挑战：交集“可用不可见”（PSI输出不能是直接的全部明文）

用法：

交集保密，基数（cardinality）只能向认证方泄露
交集保密，但PSI的秘密输出支持后续安全计算
交集保密，但是需要习惯（but still need to get used，啥意思，看不懂），比如来联合广告营销

多方PSI

常规多方PSI

动机：需要N参与方的交集

挑战：任意两方间的交集不能被泄露

方法：1、PHE+多项式表示（Polynomial representation） ; 2、OPPRF

特殊多方PSI

动机：需要计算一些两方间交集，交集结果会泄露给特殊的一些参与方

挑战：需求需要视情况而定，需要客制化的解决方案

方法：常规的PSI协议加上客制化

计算模型

单向模型（One-way Model）

动机：只有一方应当知道交集。比如，客户端向一个新的社交媒体服务提交联系人列表，客户端应该知交集，而服务器应当对客户端的数据一无所知（或只知道输入数据大小）。
共有模型（Mutual Model）

动机：两方都应当知道交集。比如，寻找两个银行的共有客户。
外包PSI（Outsourced/Delegated/Server-Aided PSI）

两个客户端在不可信第三方的帮助下在他们的外包数据上完成PSI计算。

动机：参与方无法完成PSI计算，比如参与方只拥有资源受限的设备

挑战：第三方只参与计算，但不应当获得最终结果（即使是cardinality这样的数据）

安全模型

诚实-好奇模型安全PSI（Semi-Honest Secure PSI）

动机：简单高效（目前大多数PSI协议都是在诚实-好奇的假设下实现的）

挑战：安全假设太强，只考虑了被动（passive）敌手

方法：基于DH、OPRF等的PSI
恶意模型安全PSI（Malicious Secure PSI)

动机：是更符合现实的，更进一步的安全假设，考虑恶意敌手

挑战：更多的计算和通信开销

方法：基于额外身份验证的 PSI 协议等

非对称PSI

动机：一方拥有元素的数量比另一方大得多（弱方拥有的大部分元素可能都在交集中出现）

方法：1、ECC-OPRF-PSI；2、FHE PSI

其他特殊需求

Size-hiding
Business scenario with customized requirements

PSI最新进展

优化离线阶段
- 使用最新的OT技术
- 使用VOLE替换OT
使用新的原语（primitives）替换Cuckoo Hashing
- 引入字符串的探测和异或（Probe-and-Xor-of-Strings(PaXos)）
- 引入不经意的键值对存储（Oblivious Key-Value Store (OKVS)）
支持在交集上进行后续的安全计算
亿级计算：高带宽 + 高算力，分钟级别完成

隐私求交技术的原理、发展及应用

简介