朴素哈企求交法是一种非安全的求交办法。假如发送者 Alice 持有的数据集 X 的样本空间 较小（比如手机号码或特定的电子邮件等），那么 Bob 在接收数据后，可以进行对样本空间内的一切数据进行哈希核算来破解。即便要比对的数据具有足够大的样本空间，朴素哈企求交法也并非绝对安全，接收者 Bob 仍可以依据获取到的核算后的数据，判断 Alice 是否具有哪些特定的信息。
发送者 Alice 持有数据 X={x0, x1, …, xn-1}, 接收者 Bob 持有数据 Y={y0, y1, …, ym-1}
Bob 生成同态加密密钥，并对调集中的一切数据进行全同态加密生成新的调集 C = {c0, c1, …, cm-1}
Alice 生成随机一组随机数 R，并运用如下公式来核算多项式的值。
Alice 将核算成果的数据集 {d0, d1, …, dn-1} 发送给 Bob
Bob 对数据集进行解密，搜集一切解密成果为 0 的数据，便是数据集 X 与数据集 Y 的交集。
在交互进程中，Alice 收到的是同态加密后的数据，所以 Alice 不知道 Bob 的数据集 Y 的信息。Bob 收到的是经过多项式核算后的同态加密数据，假如解密后的成果为 0，Bob 知道对应的数据存在于 Alice 的数据集 X 中，不然解密后的数据关于 Bob 来说是一个随机数。
在上述进程中，Bob 对数据集 Y 内的一切数据进行同态加密，Alice 核算高阶多项式，和 Bob 对多项式核算成果进行解密是计划中对功能负面影响较大的行为。在 Chen 等人的办法中，针对这些问题进行了一些列的优化处理，其间包括运用布谷鸟哈希办法和批处理同态加密，下降协议的核算开支和通讯开支。运用分窗的办法来加快高阶多项式核算。
发送者 Alice (Server) 持有数据 S={s1, s2, …, sw}, 接收者 Bob 持有数据 C={c1, c2, …, cv}
Alice 和 Bob 运用相同的哈希函数 H 和 H`，Bob 有持有 RSA 的私钥 (n, e)，并将公钥 (n, d) 发送给 Alice
离线阶段：
3.1. Alice 运用公钥对每个 S 核算 hsj= H(sj), Ks:j= RSA(hsj), tj= H`(Ks:j)
3.2. Bob 生成随机数 Rc:i(Rc:i< n 且 gcd (Rc:i, n) = 1)，并运用私钥对数据 C 核算 hci= H(ci), yi= hci* RSA(Rc:i)
在线阶段：
4.1. Bob 发送一切 yi给 Alice
4.2. Alice 运用私钥核算 yi’= RSA(yi)
4.3. Alice 发送一切 yi’ 和 tj 给 Bob
4.4. Bob 核算 Kc:i= (yi’/ Rc:i) mod n, ti’= H'(Kc:i)。之后核算 { t1′, t2′, …, tn’}∩{t1, t2, …, tw}, 输出的成果为 Bob 和 Alice 数据的交集
OT（Oblivious Transfer）是根底的密码学原语，中文译为不经意传输，茫然传输。OT 协议最早于 1981 年由 Michael O. Rabin 提出，协议由发送方和接收方两方参加，接收方恳求获取信息，发送方发送信息给接收方。在这个进程中，发送方对接收方的恳求信息一无所知，一起接收方也无法获取恳求的信息之外的额定信息。OT 协议首要运用有限的非对称加密技能，到达安全传输很多数据的功能
2014 年，Pinkas 等人提出了依据 OT 扩展协议的高效隐私调集求交计划 [8]，该计划运用 OT 扩展，传输数据使得通讯双发取得一个伪随机函数，并运用此伪随机函数对两边持有的数据进行加密比对。计划首要分为三个阶段来履行，哈希阶段，隐秘传输阶段和求交阶段。在哈希阶段，通讯 Alice 和 Bob 把各自持有的数据经过哈希运算均匀分布在一个给定大小的地址空间内，并运用随机数填充空余的哈希方位。在隐秘传输阶段，Bob 依据自己持有数据的比特信息作为选择位，运用 OT 扩展安全地获取 Alice 持有相同比特方位上的伪随机生成数据。最后在求交阶段，Bob 解密伪随机数据，并和自己持有的而数据进行比较。
2016 年，Kolesnikov 运用批量 OT 扩展传输和布谷鸟哈希完结了更高效的隐私调集求交计划 [9]，依据 OT 的隐私调集求交成为功能上最只是朴素哈企求交技能的隐私调集求交计划。2019 年，Pinkas 等人提出了依据稀少扩展的隐私调集求交计划 [10]，计划首先把隐秘信息分红三份，这样在未获取到要求交的数据之前，可以提前随机生成两份隐秘信息，以便在离线阶段进行 OT 扩展传输，提前获取伪随机生成函数。在在线阶段，为了防止传输很多的隐秘信息，计划运用了多项式技能，把要传输的数据融入多项式，仅传递多项式的参数来替代传输很多数据。依据该计划的测验成果，在要比照的数据量巨大，或者带宽受限制场景下，此计划相较于现在最优的依据 OT 的隐私调集求交计划，供给了更好的功能优势。
[1] M. Raab and A. Steger. “Balls into bins” – a simple and tight analysis. In Randomization and Approximation Techniques in Computer Science (RANDOM’98), volume 1518 of LNCS, pages 159–170. Springer, 1998.
[2] A. C. Yao. How to generate and exchange secrets. In Foundations of Computer Science (FOCS’86), pages 162–167. IEEE, 1986.
[3] M. Bellare, V. Hoang, and P. Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS’12, pages 784–796, 2012.
[5] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption[C] //Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1243-1255.
[6] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.
[7] E. De Cristofaro, G. Tsudik, Practical private set intersection protocols with linear complexity, in: International Conference on Financial Cryptography and Data Security, Springer, 2010: pp. 143–159.
[8] B. Pinkas, T. Schneider, and M. Zohner. Faster private set intersection based on OT extension. In USENIX Security Sympo sium, pages 797–812. USENIX, 2014.
[9] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched oblivious
PRF with applications to private set intersection. In ACM CCS 2016, pages 818–829,
Vienna, Austria, October 24–28, 2016. ACM Press. 7
[10] B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai. SpOT-light: Lightweight private set
intersection from sparse OT extension. In CRYPTO 2019, Part III, LNCS 11694,
pages 401–431, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Heidelberg,
Germany. 7
