隐私求交PSI的原理和Java实现

PSI（Private Set Intersection）隐私求交是指两个或多个参与方在不泄露各自输入数据的情况下，安全计算出它们集合的交集。

一、隐私计算的合规依据

实际上还是在个保法和数据安全法两者之间，在“取得用户授权同意即可使用”与“原始数据不能出域、断直连”之间进行折中和博弈。隐私计算特别是多方安全，没有raw data给到对端，但最终计算结果实际上是把infomation或knowledge给到了对端，使得最终对数据主体的了解变多了。这其实是个模糊地带，目前是按照上述做法满足了“用户知情授权”（在用户隐私协议里写与合作伙伴做用户画像之类），以及“没有传输出原始数据”这两个规则来作为合规依据的。
某种草平台用户隐私政策第三方信息共享清单 ** 里边有提到通过多方联合隐私计算手段做的间接用户画像**

二、常用的 PSI 协议：ECDH、KKRT、RR22 的含义及原理。

1. ECDH（基于椭圆曲线的 Diffie-Hellman 协议）

基于椭圆曲线 Diffie-Hellman (Elliptic Curve Diffie-Hellman) 密钥交换的 PSI 协议，利用公私钥对和椭圆曲线离散对数难题确保计算安全。

原理：

每方持有一个集合（如 A 和 B），然后对集合中的元素做hash_to_point()，这样每个元素都成为了EC曲线上的点。比如两个点集合是P、Q
每方对集合元素用私钥（假设为m, n）做点乘，然后彼此交换这俩点乘集合。（点乘的结果仍然是EC point）这时两方手里的分别是nQ和mP
双方对交换来的点乘集合，用私钥再做点乘,这时双方手里的是mnQ, nmP。然后一方按照约定把结果发送给另一方。（这里以第一方为例，知道P和m但因为不知道n所以构造不出nmP，所以这里需要一方按照计算结果归属的约定把mnQ或nmP发给另一方）
收到两个做了两次点乘集合的一方，对两个集合mnQ和nmP做交集比对，得到结果。（Q和P里边相同的元素做出来的mn点乘结果一定一样，所以这里可以求出交集）

优点：

简单直接，基于椭圆曲线的计算效率较高。
不需要额外的复杂计算和存储。

缺点：

计算复杂度随集合大小线性增长。
没有充分利用现代 PSI 协议的优化特性，在大规模数据时效率较低。

2. KKRT（Kolesnikov-Kumar-Rosulek-Tan PSI 协议）

KKRT 是一种基于 OT（Oblivious Transfer，盲传输）优化的 PSI 协议，特别适合于大规模集合交集计算。

原理：

OT 扩展：KKRT 协议利用扩展的盲传输来实现批量化数据处理，通过少量的基本操作扩展为大规模传输。
数据编码：每方将其集合元素编码为固定长度的比特字符串，并通过 OT 发送给对方。
匹配计算：通过协议，接收方可以高效地对比元素是否匹配，而不暴露非交集的元素。

优点：

在网络 IO 和计算性能之间取得了良好平衡，适合大规模集合。
提供了较高的效率，是现代 PSI 协议的代表之一。

缺点：

对盲传输的实现依赖较重，协议实现稍微复杂。
在非常小的数据集上效率不如简单协议（如 ECDH）。

3. RR22（Rosulek-Rosulek PSI 协议，2022 年改进版）

RR22 是一种新型 PSI 协议，针对计算效率进行了优化。它在通信和计算复杂度上优于 KKRT，特别是在更大的集合中表现出色。

原理：

批处理加速：RR22 采用了基于批量处理的优化方式，能够对大规模数据进行快速计算。
高效通信协议：通过减少协议交互步骤和传输数据量，RR22 减少了网络通信成本。
适应多方 PSI：RR22 还可以适配多方参与的 PSI 场景。

优点：

提供了更高效的计算和通信性能。
能够扩展到多方 PSI 场景。

缺点：

较新的协议实现可能还在逐步优化和完善中。
实现复杂度高于 ECDH 和 KKRT。

对比上述3种PSI协议：

协议	特点	优点	缺点
ECDH	基于椭圆曲线 Diffie-Hellman	简单直接，适合小规模集合	大规模数据效率低，计算复杂度高
KKRT	基于 OT 优化	高效，适合大规模集合	实现复杂度较高，依赖 OT 机制
RR22	新型 PSI 优化协议	性能优秀，适合大规模和多方场景	实现复杂，适应性仍在优化中

可以根据数据规模、场景需求和硬件性能选择合适的 PSI 协议来实现隐私求交的功能。

三、基于ECDH协议的PSI的Java实现

image.png

to be continue ...

参考

隐私计算跨平台互联互通开放协议第1部分：ECDH-PSI
蚂蚁集团异构平台开放算法协议与开源实践 - AIQ
隐私计算实训营第5讲-------隐私求交和隐语PSI介绍以及开发实践-阿里云开发者社区
 https://bbs.huaweicloud.com/blogs/266527
https://c.biancheng.net/view/zqzhic.html
https://zhuanlan.zhihu.com/p/478706071
https://zhuanlan.zhihu.com/p/367477035