利用不经意传输完成隐私集合求交

隐私集合求交(PSI)和不经意传输(OT)的联系是深刻的。给定一个PSI, 可以(在多项式时间内)借助它构造OT；反过来，给定一个OT, 同样可以构造PSI。当前PSI实用化研究的一个标志性成果就是借助(扩展的)OT构造高性能PSI协议，在VOLE构造出来之前[1]，它保持了PSI计算速度的最快记录。OT-based PSI的设计思路是巧妙的，我在这里记录构造它的细节，结合自己的理解去讨论其中值得玩味的天才思想。

1

扩展的不经意传输

首先回顾经典的不经意传输OT，记作, 表示Sender不经意传输 个字符串(每个字符串长度为 bit)给Receiver。  更形式化的表示如下：

• 输入: Sender 握有 对字符串 , 。这里每个字符串的长度为 bit；Receiver 握有 个选择比特 。 

• 输出: Receiver 输出 for ; Sender 没有输出。

现在考虑扩展的不经意传输(Extended OT)问题: 令 , 如何使用 次OT完成 次OT?

更形式化的表述是：给定一个 的实现，实现 , 这里 。

这里引入[2]提出解决Extended OT的方法，算法如下图：

Extended OT 算法描述

这里写一些算法的注释。首先讨论算法的正确性：这里Sender 生成向量 ; Receiver 生成随机矩阵, 这里列向量 表示矩阵 的第 列。

算法的关键步骤(第2步)是反向使用 ：

让 做Receiver (选择比特向量为)， 让做sender (传输的字符串对为 for all )，OT运算结束后 得到矩阵, 显然有。另外，一个关于Q矩阵的，不容易察觉的，但是对算法有关键影响的关系式是:

这里用 分别标识矩阵 的第 行。下面证明上面的关系式的确存在：

证明 由和， 因此 可以改写为

即的第 行为, 得证。

由上述 关系式可得，若Receiver 的选择比特 , 则；若, 。这也解释了为什么Extened OT算法的第4步最终能正确返回 for all 。

接着讨论算法的有效性。为了实现 ，算法仅调用 一次，以及 次(Sender调用 次，Receiver调用 次)查询Random Oracle。容易看出，OT-extension算法极大地促进了OT技术的实用化。

最后讨论算法的安全性。事实上，该算法对于Sender而言是恶意安全的，对于Receiver的半诚实安全的。

从Sender的角度来看，严格的恶意安全证明需要构造一个模拟器使得在理想世界（ideal world）中和恶意Sender 交互得到的sender-receiver联合输出分布(joint output distribution)和现实世界(real world)中的 交互得到的联合输出分布不可区分。

这里避免展开证明，转而讨论当 偏离协议后（即 故意篡改自己接收到的输入和发送给Receiver的输出）会发生什么？可以在算法第3步收到的矩阵 篡改为 且篡改输出为，这里。最后在第4步Receiver计算。若，那么是一个随机数（，发生碰撞的概率是一个可忽略函数）；同理可分析的情况。因此， 偏离协议并不能让Receiver获得有用信息。

从Receiver的角度来看，算法第2步反向使用OT，因为是半诚实安全的，所以Receiver得不到关于Sender私有向量的任何信息；算法第3步Sender获取的 要么等于 (此时 ) ，要么等于 (此时 ), 也就是说，当 时，Sender私有的 恰好等于Receiver私有的 ，而Sender私有的 对于Receiver而言完全是随机的。

同理可分析当 ，Sender私有的 恰好等于Receiver私有的 ，对于Receiver而言完全是随机的。总而言之，算法第3步Sender发送的字符串对 中的一个字符串对于Receiver而言是已知的，另一个字符串则完全是随机的。已知的字符串最终使得Receiver恢复出 , 随机的字符串对Receiver恢复 没有任何帮助。至此，半诚实安全性得以保障。

最后思考Receiver 偏离协议会发生什么。算法第2步 篡改输入为 , 导致算法第3步Sender获取的 满足 , 最终导致Sender输出。因此，Receiver可以毫不费力地从恢复出 。总而言之，算法无法抵御恶意的Receiver获取额外有效信息。

2

隐私集合求交

讨论完Extended OT, 现在转而讨论如何利用Extended OT实现PSI [3][4]。首先需要构造Private Equality Test，在此基础之上构造Private Membership Test。最终通过Private Membership Test构造PSI。

隐私相等测试 (Private Equality Test, PET）

PET的计算目标是判定计算双方Alice和Bob的私有输入和 是否相等，而不泄露和 相关的其他任何信息。利用Extended OT (具体地指代 primitive) 构造PET如图所示：

这里假定私有输入是 bit的字符串。

• 首先Bob准备好对随机字符串，其中Bob的私有输入 的任意比特 对应一个 bit的字符串 。 

• 接着Alice Bob进行 运算，运算结束后Alice得到 for 。

• Bob发送 给Alice。

• Alice本地计算并通过比较 判定 是否等于 。 

PET的正确性是显然的。下面简单分析PET的(半诚实)安全性：假定 是安全的, 那么Alice得到的 服从均匀分布。又因为 是随机的，因此Bob发送给Alice的字符串 服从均匀分布，整个通讯过程收发的都是随机字符串，因此半诚实安全性得以保障。

隐私成员测试 (Private Membership Test, PMT）

现在考虑如何构造PMT: 即Alice拥有私有输入 ，Bob拥有私有集合 , 安全地判定 是否成立。

基于PET, 容易构造PMT如下：

也就是说运行 次PET即可完成PMT。

完整的PSI协议

现在考虑基于PMT构造完整的PSI。类似基于PET构造PMT的思路，容易有：

容易看出这样的PSI需要做 次PMT（ 次PET）。

3

一些重要优化

上面描述的PSI需要做 次PET, 当集合大小 较大时，它的计算复杂度是相当可观的。为了让PSI实用化，需要一些特别的优化技术，使得PSI仅需做PET 即可。这些优化技术依赖经典的hash-to-bins思想，我之前在介绍使用FHE构造PSI的文章[5]中已经提及过它。这里，我想稍微展开些讨论hash-to-bins。具体地，讨论两种hashing策略。

1. Simple Hashing 是最简单的哈希策略。Sender和Receiver约定好使用一个哈希函数 将各自集合里面的 个元素哈希到 个桶内（标记为 ）。当桶的个数和集合元素个数相等时()，每个桶内至多存有约 个元素。因此在做PSI时，Sender拿私有的 桶内元素构成的集合和Receiver私有的 桶内元素构成的集合做一次子PSI, 那么，对所有 个桶都重复这样的子PSI操作后就相当于完整地做了一次PSI。容易推出经过simple hashing后，一次PSI仅需 次PET操作。

2. Balanced Hashing 和Simple Hashing是类似的。不同之处在于Balanced Hashing使用两个独立的哈希函数, 给定一个集合元素 ，查看桶 和桶 哪个桶内的元素少，并将元素 放入那个元素少的桶内。当桶个数和集合个数相等时( ), 每个桶内最多存有约 个元素。因此经过balanced hashing后，一次PSI仅需 次PET操作。

4

参考

[1] https://zhuanlan.zhihu.com/p/598254428

[2] Ishai, Yuval, et al. "Extending Oblivious Transfers Efficiently." Crypto. Vol. 2729. 2003.

[3] Pinkas, Benny, Thomas Schneider, and Michael Zohner. "Faster private set intersection based on {OT} extension." 23rd {USENIX} Security Symposium ({USENIX} Security 14). 2014.

[4] https://www.youtube.com/watch?v=6Wo-MFd4Uuw

[5] https://www.zhihu.com/column/c_1569287736594415616

本文作者：hujwei

知乎链接：https://zhuanlan.zhihu.com/p/587098381

END

往期推荐

1.一文了解零知识证明基础知识
2.密码学的100个基本概念（上）3.密码学的100个基本概念（下）4.笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议