KKRT库：https://github.com/osu-crypto/BaRK-OPRF
文章：Efficient Batched Oblivious PRF with Applications to Private Set Intersection-2016
解读论文，参考：Efficient Batched Oblivious PRF -Private Set Intersection
关键词：两方PSI、ORFT、OTE
KKRT-PSI方案使用了OTE（OT扩展）、OPRF、Cuckoo哈希等技术，在大集合场景、局域网（带宽20GB/s）下运行效果最好。
方案构造思路：先设计一个OTE，进而设计一个OPRF，最后设计一个PSI
协议功能：Sender不知道Receiver的选择\(r\)；Receiver只知道\(X_r\)
协议实现：有基于RSA的、基于DH的、基于ECC的等。
下面介绍的是Naor-Pinkas-OT，Naor和Pinkas通过三次公钥密码学操作实现了半诚实模型下的1-2 OT：
论文：Efficient oblivious transfer protocols-2001
其中\(E_{r,2}\)表示\(E_r\)的第二部分，若\(r=0\)，则：
安全性：Sender根据\(PK_0\)不能反推出\(k\)；Receiver根据\(g^a\)不能反推出\(a\)。
1-2 OT在实际应用中，每次都需使用一次，效率较低，所以下一步采用“固定数量的OT来实现任意数量的OT”，例如下图只需要使用\(k\)次1-2OT即可实现，其中\(k\)是根据安全参数决定的。
Ishai、Kilian、Nissim和Petrank于2003年提出基于矩阵变化实现少量1-2OT和对称密钥构造大量OT实例的不经意传输扩展协议。
论文：Extending Oblivious Transfers Efficiently-2003
本文提出了一种OT扩展协议，即\(k\)次1-2OT实现了\(m\)次1-OT，其中\(k<m\)，，即每次有两种选择。文中给出了两种情况的协议：Receiver半诚实和Receiver恶意，下面介绍Receiver半诚实的协议：
分析：
注意：\(m_i\)表示列，\(m^i\)表示行
IKN03方案是用\(k\)次OT实现了\(m\)次1-2OT，其中\(k<<m\)。KK13方案将IKN03中的\(r\)看作一个矩阵\(R_{m*k}\)（每列都一样），计算\(T=U \oplus R\)，无需使用1-2OT实现1-nOT，仅改变了\(R\)，利用编码技术，实现了\(1-n\)OTE。
论文：Improved OT Extension for Transferring Short Secrets-2013
参考：KK13 OTE——Improved OT Extension for Transferring Short Secrets
用\(k\)次1-n OT传递了\(m\)个信息，每个消息是\(lbit\)，且是n个中选1个，其中\(k>=n\)。
关于WH编码：
从KK13方案中，知道\(C_{WH}^k(a)\)是一种编码形式，即输入一个\(log^k\)bit的字符串\(a\)，输出一个\(k\)个字符串\((c_0,...,c_{k-1})\)，每个字符串为\(k\)bit，在进行隐私相等性测试时，即已知\(C_{WH}^k(a),C_{WH}^k(b)\)，如何安全判断\(a\)和\(b\)是否相等，无需解码，只需比较\(C_{WH}^k(a),C_{WH}^k(b)\)是否相等即可，这里需要保证\(C_{WH}^k(a)\oplus C_{WH}^k(b)\)的汉明距离不小于计算安全参数。所以在KKRT16方案中的OTE，无需使用\(WH\)编码技术，只需要一个汉明距离不小于计算安全参数的伪随机函数即可。
发送方和接收者执行两方OPRF协议，发送方无输入，接收方输入元素\(x_i\)，发送方输出密钥\(k\)，接收方输出OPRF值\(F(k,x_i)\)：
上面提到需使用伪随机函数，这里伪随机函数的功能相当于KK13中的哈希，即\(F=H(j,\mathbf{q}_{j}\oplus(\mathbf{c}_{r}\odot\mathbf{s}))\)。一共有\(m\)个\(r_i\)，可以执行\(m\)次OPRF。另外在2019年PRTY19和2020年CM20都基于第3个属性对OPRF协议进行了进一步的改进，得到多点OPRF，实现了正常带宽下最快的PSI协议。
KKRT167中使用的OPRF由于是Batch、relaxed的，所以叫做BaRK-OPRF。
得到一个OPRF协议后，就可以很容易的构造一个PSI协议。例如下图：
但接收方需要进行\(O(n^2)\)次比较。
更多参考：https://www.cnblogs.com/pam-sh/p/16155650.html#cuckoo-hash
Cuckoo hashing分为两个存储表，一个为Cuchoo哈希表，一个称为堆存储容器。（本文协议采用的这样的容器，之后的文章有采用无堆存储容器的Cuckoo hashing）。
Cuckoo插入元素\(x\)的算法如下：
上述基于一个理想的OPRF构造了一个简单的PSI协议，但效率（计算和通信）较低。
KKRT16-PSI协议遵循了PSZZ15基于KK13-OTE构造PSI的思路，采用Cuckoo hashing算法减少了比较次数。对于128bit的字符串和足够大的集合，求交速度比PSZZ15快3.1～3.6倍，具体说只需3.8s就能求出集合大小为\(2^{20}\)的交集。
「PSZZ15」Phasing: Private set intersection using permutation-based hashing-2015
「PSZ14」Faster private set intersection based on OT extension-2014
总结了PSI协议构造的方法：基于哈希的、基于公钥加密的、基于GC的、基于OT的等。改进了「PSZ14」方案：使用置换哈希减少
bin的位长、使用哈希和安全电路计算，降低电路深度和通信消耗、使用改进的OT协议改进计算和内存消耗。
对于在bin中的数据，\(z\)表示所用的哈希函数，OPRF的输入为\(x||z\)，输出为\(F(k_{h_z(x)},x||z)\)；对于在stash中的数据，OPRF的输入不变，即\(x\)，输出为\(F(k_{1.2n+x},x)\)，所以H和S的生成为：\(\begin{gathered} H_{i} =\{F(k_{h_t(x)},x\|i)\mid x\in X\},\text{for}i\in\{1,2,3\} \\ S_{j} =\{F(k_{1.2n+j},x)|x\in X\},\text{for}j\in\{1,\ldots,s\} \end{gathered}\)。
这样PRF的值变为了\(n+ns\)，且降低了OPRF的碰撞概率。
关于\(K=(k_1,....,k_{1.2n+s})\)的生成没有具体说，待补充。
环境：Centos7.6
## 下载
git clone https://github.com/osu-crypto/BaRK-OPRF.git
## 下载依赖库
cd BaRK-OPRF/thirdparty
bash all_linux.get
## 会发现有些问题，需要将makelist中的'yum -Y'改为'yum -y'
## 编译
cd ..
make
## 会发现mpir安装的有问题，原来是给的下载链接失效了，重新找了一个替换上
## mpir.get文件
wget http://sources.buildroot.net/mpir/mpir-3.0.0.tar.bz2
tar -xjf mpir-3.0.0.tar.bz2
mv mpir-3.0.0 mpir
rm mpir-3.0.0.tar.bz2
cp ./mpir_patch/mpirxx.h ./mpir/
cp ./mpir_patch/mpir.h ./mpir/
cd mpir
./configure
make
## 重新编辑，即可
make
## 测试
./Release/bOPRFmain.exe -t
# 输入数据集规模为2^{12}，进行测试
./Release/bOPRFmain.exe -t
计算6种情况下的PSI，输入数据规模为（\(2^8\)，\(2^{12}\)，\(2^{16}\)，\(2^{20}\)，\(2^{24}\)）。对于每种情况，运行代码10次来计算PSI。输出包括平均在线/离线/总运行时间（显示在屏幕上）和output.txt文件。
# Sener
./Release/bOPRFmain.exe -r 0
# Receiver
./Release/bOPRFmain.exe -r 1
# Sener
./Release/bOPRFmain.exe -r 0 -ip <ipAdrress:portNumber>
# Receiver
./Release/bOPRFmain.exe -r 1 -ip <ipAdrress:portNumber>
//提示函数，其中argv0指向exe
void usage(const char *argv0)
{
std::cout << "Error! Please use:" << std::endl;
std::cout << "\t 1. For unit test: " << argv0 << " -t" << std::endl;
std::cout << "\t 2. For simulation (2 terminal): " << std::endl;
;
std::cout << "\t\t Sender terminal (localhost): " << argv0 << " -r 0" << std::endl;
std::cout << "\t\t Receiver terminal (localhost): " << argv0 << " -r 1" << std::endl;
std::cout << "\t\t Sender terminal (with ip input): " << argv0 << " -r 0 -ip <ip:port>" << std::endl;
std::cout << "\t\t Receiver terminal (with ip input): " << argv0 << " -r 1 -ip <ip:port>" << std::endl;
}
int main(int argc, char **argv)
{
//有两个参数，第一个为exe，第二个为“-t”，其中第二个参数argv[1][0] == '-'，argv[1][1] == 't'
if (argc == 2 && argv[1][0] == '-' && argv[1][1] == 't')
{
BopTest();
}
//有三个参数，第一个为exe，第二个为“-r”，第三个为“0”，另外atoi()能把字符串转换成整型数
else if (argc == 3 && argv[1][0] == '-' && argv[1][1] == 'r' && atoi(argv[2]) == 0)
{
BopSender("localhost:1213");
}
//有三个参数，第一个为exe，第二个为“-r”，第三个为“1”
else if (argc == 3 && argv[1][0] == '-' && argv[1][1] == 'r' && atoi(argv[2]) == 1)
{
BopRecv("localhost:1213");
}
else if (argc == 5 && argv[1][0] == '-' && argv[1][1] == 'r' && atoi(argv[2]) == 0 && argv[3][0] == '-' && argv[3][1] == 'i' && argv[3][2] == 'p')
{
//获取ip
string ipAddr = argv[4];
BopSender(ipAddr);
}
else if (argc == 5 && argv[1][0] == '-' && argv[1][1] == 'r' && atoi(argv[2]) == 1 && argv[3][0] == '-' && argv[3][1] == 'i' && argv[3][2] == 'p')
{
string ipAddr = argv[4];
BopRecv(ipAddr);
}
else
{
//跳转提示
usage(argv[0]);
}
return 0;
}
int main(int argc, char** argv)主函数中的argc代表的是参数的数量，至少为1（argv[0]即.exe文件的路径)。argv为指针表示的参数，argv[0]表示第一个参数，argv[1]表示第二个参数，以此类推。
待补充
参考：隐私集合求交
[KKRT16] 是半诚实 OT-based PSI协议,基于 OT Extension, BaRK-OPRF 和 CuckooHash。 [KKRT16] 是第一个在千万( 224224)规模,长度(128 bits)数据集上，求交时间在1分钟之内的PSI协议.
隐语 SPU PSI 中使用了 [PSZ18] 提到的 3-way stash-less CuckooHash：
