不经意传输扩展(OTE)-不经意伪随机函数(OPRF)-隐私集合求交(PSI)

即上篇《Efficient Batched Oblivious PRF with Applications to Private Set Intersection》(CCS2016)的后续产物论文进行论文分享！

《SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension》(CRYPTO2019)

《Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF》(CRYPTO2020)

第一篇KKRT16是从运行效率上针对IKNP03-OTE的一个改变，通过将纠错码改为伪随机编码实现1-无穷OTE,避免了OT数量与元素的大小相关！

第二篇PRTY19从通信负载上针对KKRT16-OTE的一个改变，通过将巨大的矩阵传输改为n阶多项式传输实现k-NOTE, 将通信复杂度从Nk下降到nk.

第三篇CM20从通信负载和运行效率均衡针对KKRT16-OTE的一个改变。通过将纠错码C即伪随机函数的输出从字符串变成矩阵，将通信复杂度从Nk下降到nk

对于最重要的三个基于OTE的PSI协议，我将从PSI协议最关注的两个方面对其文章的主要贡献进行了梳理。KKRT16主要从运行时间上对OTE组件进行了优化。PRTY19则在KKRT16-OTE的基础上增加多项式插值对通信进行优化但损失了计算。CM20则对KKRT16-OTE进行了优化，在未损失运行效率的情况下减少了通信负载。

KKRT6是一篇CCS2016顶会上的文章，该会专注于信息安全领域实用性的论文。本文介绍的这篇文章综合使用了不经意传输扩展、Cuckoo哈希、不经意伪随机数生成器（Oblivious Pseudo-Random Generator），同时还引入了编码理论相关的知识，将多种密码学技术和安全多方计算的PSI都涵括在内，是非常经典的文章！之前师兄也讲过。但我觉得仍然有必要复习一下这篇论文！这篇论文仍然是目前PSI协议中大集合场景下，局域网下(也就是带宽在20GB/S左右)的场景下运行效率最高！

我将以这样一个方式对KKRT16这篇文章进行介绍。首先介绍具体贡献，然后将贡献当成一个具体的问题带入到下面如何改进实现的。

接下来就是按PSI由OPRF构建，OPRF由OTE构建，从底层开始讲起每一个构建它改进了什么，带来了什么效果！

KKRT16最主要的贡献是将KK13的1-nOTE提升为1-无穷OTE。附带的贡献是 将OTE解释为OPRF协议成为一个独立的密码学子协议，然后构建PSI协议使得OT执行次数不再与元素大小相关。另外引入了Cukoohash 降低了通信复杂度，且运行时间是目前局域网带宽下最快的。

我们将从如下方式介绍KKRT16的具体构建过程。base-OT的功能与实现--同等安全条件下，采用少量开销实现大量OT实例--将1-2选择OT扩展为1-nOTE--扩展为1-无穷OTE-解释为OPRF-构造PSI协议。

base-OT基于公钥加密实现为OTE提供PPT内的安全性。1-2baseOT具有如上功能：。

baseOT有很多种实现方式。例如基于RSA,基于DH,基于ECC等。本文采用的是基于三次离散对数困难问题的公钥加密实现的Naor-Pinkas-OT协议。发送方选择一个随机数C发送给R.接收方计算PK_0和PK_1，其中PK_r=g^k。R将PK_0发送给S.S计算计算x_0和x_1的加密E_0和E_1并发送给R。可以简单的证明，如果r=0,则PK_0=g^k,发送方PK_0^a=g^ka,PK_1=C^a/g^ka。而接收方只能获得g^ak,无法获得C^a/g^ka,因此只能得到x0.

不经意传输扩展主要为解决实际应用场景每一次都使用baseOT而带来的低效性！因此研究人员提出采用固定数量的baseOT实现任意数量的不经意传输实例被称为不经意传输扩展。这里举个简单的例子，S拥有n对数据集，R拥有n个选择比特，若仅采用baseOT需要执行n次这是非常缓慢的！而采用OTE,baseOT的数量K远小于n大大提升了效率！

接下来介绍Ishai、Kilian、Nissim和Petrank于2003年提出的如何基于矩阵变化思想实现少量baseOT和对称密钥构造大量OT实例的不经意传输扩展协议。

1.接收方首先随机生成一个m*k矩阵T和m*1字符串r,通过计算矩阵T的第i列和字符串r异或得到第二个矩阵U.

2.发送方和接收方执行k次baseOT：发送方输入选择比特s_i，接收方输入秘密t_i,u_i.发送方输出q_i,如果选择比特s_i=0，则q_i=t_i否则等于u_i。执行完k次baseOT后，发送方获得一个m*k矩阵Q。可能这里会疑惑发送方和接收方是不是搞反了。其实这里的发送方和接收方的定义是按PSI协议来定义的，一般谁获得最后的输出就定义为接收方。

3. 接下来基于矩阵变化的思想将已经完成k-baseOT结果转化为m个OT实例，其中m远大于k。

4. 也就是我们从行的角度来观察这三个矩阵，当字符串r的第i行等于0时，T的第i行就等于U的第i行，因此矩阵Q的第i行就等于T的第i行

5.当字符串r的第i行等于1时，矩阵U的第i行等于T的第i行异或{1}^k，则矩阵Q的第i行第j列的值取决于字符串s第i列的取值，若s_i=0，则为矩阵T第i行第j列的值。若s_i=1,则为矩阵T第i行第j列的值异或1，因此矩阵Q的第i行等于矩阵T第i行异或字符串s.

我们将其进行进一步的解释为我们等一下会用到的OPRF

1.我们将行可解释为”变”这个形式。第i个OT实例：发送方输入两个秘密矩阵Q的第i行和矩阵Q的第i行异或字符串s。接收方输入第i个选择比特，输出指定秘密。

2.我们可以发现当r^i=0时，接收方只能知道q^i，但无法知道q^i异或s。当r^i=1时，接收方只能知道q^i异或s，但无法知道q^i。

1.这意味着我们可以将q^i异或s和q^i作为OT实例的数据加密密钥。注意到我们这里采用了随机预言机H对其加密，这里想了很久，为什么要对其进行加密，我觉得原因是必须要破坏矩阵中q^i异或s和q^i之间的相互关系。最后接收方根据t^i选择是x_0还是x_1。

我们再次回顾接收方生成矩阵T和U的过程。矩阵T等于矩阵U异或矩阵R. 我们可以发现矩阵R 的第i行为 k个 r^i ，这意味着 矩阵R的每一行都是r^i的一种编码. 纠错编码是一种简单的编码，于是是否可以采用一个更复杂的编码呢？

1.这里我们选择一个复杂的纠错码C,它的输入域具有一个很大的范围，不只有{1,0},输出为一个kbit.22

2.然后我们将C带入IKNP03重新研究一下。

通过K个1-2baseOT后仍然可以得到这样一个关系：矩阵Q的第i行等于矩阵T的第i行异或C编码(r的第i行)与字符串s.

因此我们得到了2^l个密钥。

对于2^l输入域的每一个r’，发送方都可以计算出所有的C(r)而接收方只能计算出其中一个C(r)。因此得到了2^l选1.

为证明接收方只能得到一个秘密，假设接收方选择字符串为r^j但是想学习r’的秘密。由黄色公式可知，除了s所有的其他接收方都是知道的。我们假设纠错码C的最小距离为计算安全参数。为此敌手需要猜测k位才能违犯安全性。因此我们认为是安全的。

KKRT16等人通过对KK13-OTE的观察发现通过OTE构建隐私相等性测试时：

1.我们并不需要对纠错码C进行解码，我们只需要比较两个纠错码映射的值是否相等即可

2.对于任何两个r和r’我们需要保证C(r)⊕C(r’)的汉明距离不小于计算安全参数，虽然汉明距离是概率性的，但这个概率忽略不计！因此我们可以将汉明距离不小于我们的计算安全参数。

因此KKRT16提出我们并不需要纠错码C，只需要一个汉明距离不小于计算安全参数的伪随机函数即可。这是非常小的一个改变但也是本文最重要的一个改变！这使得基于KKRT16-OTE的psi协议比基于KK13-OTE的PSI协议提升了3倍！

显然将纠错码C替换为随机函数，只要伪随机函数的抗碰撞性大于计算安全参数，协议仍然是安全的！且和KK13-OTE保持一样的效果，因为协议的整个核心过程并没有改变！

而且我们还得到了另外一个效果：即接收方可以选择任何字符串作为它的选择字符串了！消除了选择字符串的先验约束！

也就是发送方可以计算任意字符串相对应的密钥值，而接收方只能计算出一个，这也就是KKRT16为什么说得到了1-无穷OTS

为保证安全性，需要PRF(r^’)⨁PRF(r^j)的汉明距离要不小于计算安全参数k,为此将PRF的输出长度设置为3.5k。具体设置长度会在讲到伪随机函数的安全性时介绍到为什么设置3.5k!

接下来介绍如何将KKRT16-OTE解释为一个OPRF协议，并封装成一个独立的密码学子协议！

首先介绍一下OPRF协议的功能：发送方和接收者执行两方OPRF协议，发送方无输入，接收方输入元素x_i,发送方输出密钥k,接收方输出OPRF值F(k,x_i)。

将KKRT16-OTE解释为OPRF,伪随机函数为H(q异或C(r)与s)。可以发现接收方只能获得指定输入的OPRF值，而发送方可以获得任意输入的OPRF值。

我们的OPRF与现有的OPRF存在一下微妙的不同：

1.接收方的输出信息略多余“PRF”值，事实上接收方获得的不是H(t)而是 t=q⨁C(r)⊙s。泄露了一定的信息但并不影响安全性，因此KKRT16作者称之为relaxed-OPRF(松弛OPRF)

2.我们可以注意到OT矩阵每一行都定义了一个OPRF实例，因此KKRT16作者称之为batched-OPRF(批处理)

3.我们关注到每个OPRF实例的q是不同的，s都是一样的，且q和s相关！因此KKRT16作者称之为related-Key(批处理)

第三点的性质非常重要，在2019年PRTY19和2020年CM20都基于该属性对OPRF协议进行了进一步的改进，得到多点OPRF！实现了正常带宽下最快的PSI协议！有兴趣的可以沿着这条路看！

将OTE解释为一个OPRF协议后可以很容易的通过OPRF构造出PSI协议！

简单介绍一下PSI协议的功能：S和R分别拥有隐私集合X和Y,它们共同计算集合交集，并获得交集结果！除交集外无任何元素额外信息的泄露！

为什么说OPRF可以简单构造PSI呢？这里先举一个大致思路，有助于理解等下的优化点！

S与R执行OPRF,R输入隐私集合，输出OPRF值。S输出密钥k,可计算任意的OPRF值，S本地计算OPRF值并将其发送给接收方，R通过字符串比较得到交集！

可以说基于OPRF构造PSI协议非常简单，但发送方需要加密O(n^2)个和发送O(n^2)的通信量，接收方需要比较O(n^2)次。(因为每个OPRF实例的密钥都是不同的！)

为此：

KKRT-PSI协议遵循了PSZZ15基于KK13-OTE构造PSI的过程，采用Cuckoo hashing算法减少通信负载和比较次数。我们首先从使用到的哈希函数说起！

1.Cuckoo hashing分为两个存储表，一个为Cuchoo哈希表，一个称为堆存储容器。(这篇文章采用的这样的容器，之后的文章有采用无堆存储容器的Cuckoo hashing,大家可以看看！)

2.Cuckoo插入元素x的算法如下：计算元素x的三个哈希值，寻找对应索引的位置，若至少有一个位置为空则随机插入空位置。若一个位置也没空，则随机选择一个位置替换该元素。对该元素执行上述步骤。

若执行k次后，仍然需要替换，则将该元素存储到堆存储器中！

这里我们以PSSZ15的构造方式构造PSI协议，仅将OPRF协议替换为KKRT16-OTE

1. 接收方R随机选择三个hash函数，将集合元素通过布谷鸟hash算法映射到布谷鸟表或堆容器中。最后空余的地方采用虚拟元素填充！

2.发送方和接收方执行(b+s)次OPRF实例。b和分别代表布谷鸟表或堆容器的长度。并将OPRF值和元素x的对应存储位置联系起来。

3.发送方拥有密钥K,本地计算H和S并将每一行打乱再发送给接收方。由于我们选择的是3个hash函数，因此H的长b宽3，s是一个常数，因此需要传输3b+sn

4.接收方哈希表每一行的比较次数为3次，堆容器中的每个元素需要比较n次但只有s个元素且s为常量，因此只需要比较(3+s)n次，将比较次数和通信负载从O(n^2)下降到O(nlogn)。

刚刚我们分析了H和S的大小，分别为3b和sn。KKRT16对其又做了一个小的改变，可将比较次数提升10%。将H分为了三类，因此每一行只需要比较1次了。减少了2n次比较次数！

接下来我们重新分析一下基于KK13OTE构造的隐私相等性和BaRK-OPRF的隐私相等性测试的区别！

对于两个元素的相等性测试如上：

1.若是1-2OT则r比特长度的元素需要r个OT实例

2.若是1-2^lot则r比特长度的元素需要r/l个OT实例。KK13中的l一般设置为8bit,所以是1-256OT

2.若是1- ∞ OT则任意比特长度的元素仅需要一个OT实例。这样得到一个性质：OT执行次数不再与元素大小相关！

最近投稿的那篇文章里写到了OTE的baseOT数量不与集合大小有关仅与计算安全参数有关，因此OTE适用于大集合场景！刚好借这篇文章的定理证明一下！

这是我们生成的m*k矩阵，为得到m个OT实例，我们需要进行k个公钥加密,也就是k个baseOT,k即是矩阵的宽度也是伪随机编码的长度，也就是k的参数应该设置为多少？

k的大小主要有两个限制条件1.BaRK-OPRF中需要一个伪随机代码来实现不小于计算安全参数的汉明距离。

2.PSI协议中发送方需要计算(3+s)n个OPRF值，我们需要其是伪随机的，因此需要底层PRF具有m-RK-PRF安全性(m=(3+s)n)

前面我们提到了松弛(relaxed)OPRF, 这里我们做一个更广泛的定义，有两个函数F,F’。只要给定F’(k,r)就能高效的计算出F(k,r)，F被称为relaxed-PRF.

我们首先需要使底层PRF具有m-RK-PRF安全性，那什么时候才能满足呢？

通过该文的证明可知：当伪随机编码的参数为d=计算安全参数和错误率E=统计安全参数+logm时我们就可以说伪随机函数具有m-RK-PRF安全性.

证明如上。对于m个元素的汉明距离为d 的概率为1-2^-e，这是一个极小的概率因此我们认为是不可区分的，因此是安全的。

我们将具有m-RK-PRF安全性的伪随机编码的参数为d=计算安全参数和错误率E=统计安全参数+logm带入计算得到伪随机编码的长度n仅与安全参数有关从这个标红的式子可知！

KKRT16-OTE是接下来两篇的基础，为其提供了高效的运行时间和实用性

第二篇PRTY19从通信负载上针对IKNP03OTE的一个改变，通过将巨大的矩阵传输改为n阶多项式传输实现k-NOTE, 将通信复杂度从Nk下降到nk.

PRTY19发表在密码学顶会美密会上的文章，和KKRT16是同一波密码学大牛写的文章

接下来，我们直接介绍其在KKRT16-OTE上的改进,因为前面的步骤和KKRT16一样并且后面的改进和KKRT16-OTE没有关系，以及改进后得到的效果。从通信负载上针对IKNP03OTE的一个改变，通过将巨大的矩阵传输改为n阶多项式传输实现k-NOTE被称为SparseOTE(稀疏OTE)。

我们再回顾一下IKNP03: S和R执行计算安全参数k个baseOT:R输入t_i,u_i,S输入s_i,S输出q_i。然后将得到的矩阵Q，s,T,r之间的关系转化为m个OT实例。

R发送矩阵R：M*k给接收方S。S发送消息Q和Q异或s，实现m个实例！但Sparse-OTE注意到了M*k矩阵是非常大的通信开销。因此接收方将矩阵R和对应的元素对应起来插值一个多项式，只传输多项式系数给发送方S即可。S计算H(Q(x)⊕s·P(x)|x∈X并发送给R.我们可以看到Q(x)⊕s·P(x)=T(x)⊕s·(P(x)⊕R(x)))仍然满足要求。因此Sparse-OTE:将R的通信复杂度从O(mk)下降到O(nk)(n为集合大小n<

当然这篇文章还改进了hash映射算法和多项式插值技术！有兴趣的可以看看。

第三篇是从通信负载和运行效率均衡针对KKRT16-OTE的一个改变。从而得到中等带宽中运行效率最快且通信和计算之间相对均衡。本篇文章也是发表在美密会20年的文章。这篇论文的重点在于如何使用不经意传输协议OT、对称密码技术和伪随机数函数PRF实现N选k的多点OPRF!

本文的难点是如何仅使用KKRT16-OTE的技术实现多点OPRF,即需要计算低也需要通信低！所谓多点OPRF:也就是一个OPRF实例可以对多个元素进行OPRF值的评估。

我们首先回顾一下KKRT16的单点OPRF:一个OPRF实例仅能对一个元素进行OPRF值的评估。

我们以S和R分别拥有元素x和y进行隐私相等性测试为例。

采用KKRT16-OTE的第i行作为我们的单点OPRF实例。

1.在baseOT阶段，R的种子r是通过伪随机函数对元素y映射得到，因此等到一个性质就是能实现1-无穷OT实例。

2.在OPRF实例阶段，发送方计算OPRF值q^i异或PRF(x)与s。然后发送给接收方，可以发现如果x和y相等则F(x)与F(y)。

多点OPRF:一个OPRF实例可以对多个元素进行OPRF值的评估。

 KKRT16中的纠错码为一个伪随机函数，其将一个任意的字符串映射为一个长为k的字符串。而且通过观察在baseOT中发送方的选择位s无论为什么都会影响F(y)=H(t^i)的性质。也就是说是否相等的这个性质和s是无关的。那我们是否可以考虑将纠错码c换成另一种伪随机函数：其为一个m*k的矩阵呢？这样就能实现一个OPRF实例可以对多个元素进行评估了。

接收方这里采用替换的PRF进行元素x的映射，得到矩阵T和u. 这样就得到了多点OPRF.

可能还是不理解，这里我们举一个具体的例子说明。

KKRT16-OTE中纠错码的映射范围是矩阵的一行，因此一个OPRF实例只能比较一对

CM20中纠错码的映射范围是整个矩阵，因此一个OPRF实例可以比较x是否属于集合Y.

这就决定了KKRT16-OTE中通过Cuckoo hash函数映射后m的长度为(3+s)n,而CM20通过多点OPRF即可带来Cuckoo hash函数的作用且消除通信开销，m的长度为集合大小即可。出现这个原因是它们最终比较n个元素所要使用的OPRF实例决定。而宽k是由PRF应具有计算安全参数的汉明距离决定所以列的长度是一样的。

这里再解释一下为什么要用Cuckoohash可以减少通信开销。因为如果直接进行比较的话我们需要用每一个OPRF实例对元素x进行加密再传输给R.这样需要消耗O(n^2)的通信开销。而采用Cuckoohash后，虽然增加了OPRF实例，也就是增加了矩阵的长度，但是减少了通信量O((3+s)n)，因为Cuckoohash保证元素出现在同一行。

多点OPRF就不关心用的那个OPRF实例进行加密了，因为都是用的同一个OPRF进行加密所以m的长度为n。

因此相较于PRTY19和KKRT16，CM20仅通过对称密钥实现了通信复杂度为O(nk)。