笔记分享 | 组队学习密码学（3）——隐私求交之不经意的伪随机函数构造

本文是 笔记分享 | 组队学习密码学（3）——隐私求交的关键路径及其应用 的续集，本章主要介绍不经意的伪随机函数构造。

下图是基于不经意的伪随机函数的技术框架，OPRF允许一个参与方获得密钥，另一个参与方获得密钥下的特定值的伪随机函数，接下来我们重点来讲一下OPRF的构造。

接下来我们将从以下几个方面来引入不经意的伪随机函数。

我们接下来来介绍一种简单的构造方式，Alice生成一把公私钥对，并随机选择一个随机数，并按照如下的顺序进行放置，Bob使用Alice生成的公钥进行加密，同时Alice仅对一个消息具有解密能力，正确性显而易见。在该方案中，我们可以使用任意的公钥加密算法来实例化该算法。

但是基础OT协议都是公钥操作，如果需要传输大量消息，那么会导致巨大的计算开销。我们希望使用少量的公钥操作来实例化大量的对称操作，这也是OT扩展协议设计的初衷，接下来我们来介绍IKNP03的协议。

IKNP03中有两个参与方，Bob具有选择向量r，并对其进行扩展，得到两个秘密分享的矩阵，具体的构造如下所示：

Alice在这个使用得到了0，1对应的密钥，Bob获得了其中的一个密钥，即具有其中一个消息的解密能力。

以下是基于的DH密钥协商协议构造不经意的伪随机函数的一个示例，但是我们会发现基于DH的算法需要很多次公钥加密操作，实际场景中非常难使用。

接下来我们来看一下如何使用IKNP03的思路来构造OPRF，下图是主要构造的方式，在KKRT16中发表，需要说明的一点是，q,s是Alice的伪随机函数密钥，r是Bob对该轮的查询。

之前所讲的所有方案都是需要对元素一个个比较，这需要平方次数的比较，接下来我们介绍一种优化方法，使得复杂度从平方次降到线性次。

Bob使用布谷鸟哈希，Alice使用普通哈希，对集合元素进行分组，这样两个参与方只需要对特定的桶进行比较操作即可。

我们发现Bob每个桶里只有一个元素，Alice每个桶里有若干个元素，Bob只需要对Alice同理的元素进行固定次比较即可，大大降低了比较次数，具体的优化请参见Benny Pinkas在2015年发表的论文。

下一节将整理PSI的变体协议及其在联邦学习和可搜索加密场景中的应用。

对隐私求交有兴趣的小伙伴们，还可以阅读技术分享 | 隐私集合求交（PSI）技术体系整理 进行进一步学习哟～

作者：杨赟博

分享仅供学习参考，若有不当，请联系我们处理。