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实现
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
