Question

不经意伪随机函数

Answer 1

        不经意伪随机函数是Freedman、Ishai、Pinkas和Reingold在2005年提出的概念

        首先不要被这个名字给迷惑了，先忽略限定词不经意(Oblivious), 直指 伪随机函数（Pseudo Random Function） 。

伪随机函数(PRF) ：是使用一个确定性的算法，计算出来的看似随机的数序，“伪”就是实际上并不真随机。如果输入到伪随机函数的初始值是相同的，那么输出的随机数的数值也是相同等。

不经意(Oblivious)： 参考不经意传输(Oblivious Transfer)协议，简单来说Bob 从 Alice 的一堆数据集中取一个，但 Alice 不知道 Bob 取的是哪一个，Bob 除了知道他取到的值之外，对Alice的其他数据也一无所知。

搜寻到有两个版本的实现，一个是基于伪随机函数的，一个是基于hash实现伪随机性的。

可以设定伪随机函数  （in group   of composite order  ）, 如 reference 2中的定义。

方案2：设定共用的Hash函数，将两组数据集映射在通过一个bloom filter 上，进而进行隐私求交，详见reference 3.

后续还有更多改进版本的，包括效率、安全性提升等。

1. https://crypto.stackexchange.com/questions/58246/can-someone-explain-how-oprf-oblivious-pseudo-random-function-is-based-on-ot

2. "A Verifiable Random Function With Short Proofs and Keys", 2005

3. “When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol”， DCW13

4. “Improved Private Set Intersection against Malicious Adversaries”，https://www.youtube.com/watch?v=Dz_mJmTZNQc