高效批处理不经意伪随机数生成器及其在隐私集合求交中的应用

随着涉及领域的不断增多，想听译的视频、想读的论文也变得越来越多。不过，这也意味着各个知识点之间变得更松散了。还是要抽出时间批量阅读一些论文，学习一些技术。

格密码学的视频还在整理当中。回看这些视频，不由得惊叹：当时自己哪里来的那么多时间把视频都听译完的。还是那句话：积少成多，我也在重新整理之前发布过的演讲视频相关专栏文章。部分有缺陷的文章和视频也重新进行了整理和发布。感兴趣的知友们可以翻看一下我之前发布的文章，会有一些新的变化。

演讲视频简介

本次为知友们带来的视频是信息安全顶级会议CCS 2016上的演讲视频《Efficient Batched Oblivious PRF with Applications to Private Set Intersection》。隐私集合求交（Private Set Intersection，PSI）愈发得到了学术界和企业界的关注。

近期，各个顶级会议上也推出了一系列高效PSI的构造与实现。自从Pinkas等人在2015年将不经意传输（Oblivious Transfer，OT）引入到PSI以来，PSI的效率已经从百万集合分钟级执行效率降低到百万集合秒级执行效率。这是一个相当巨大的飞跃。随着人们对隐私保护的愈发关注，相信以PSI为代表的安全多方计算（Secure Multi-Party Computation，SMPC）技术，以及以Intel SGX为代表的可信执行环境（Trusted Execution Environment，TEE）技术会逐步从理论走向落地、从落地走向大规模落地。期待未来能出现里程碑级别的应用杀手锏。

CCS 2016上的这篇文章可以说是非常有代表性的PSI方案构造。方案综合使用了不经意传输、不经意传输扩展（Oblivious Transfer Extension，OTE）、Cuckoo哈希、不经意伪随机数生成器（Oblivious Pseudo-Random Generator），同时还引入了编码理论相关的知识，可以说是多种密码学技术和安全多方计算技术的集合体。对此领域感兴趣的知友们可以认真阅读论文和开源代码，相信会有很大的收获。

演讲视频信息

中文字幕视频

演讲视频字幕

大家好，感谢Stefan的介绍。我的名字是Ni，我是俄勒冈州立大学的博士研究生，很高兴能来到这里介绍我们的工作。我们的论文题目是：高效批处理不经意伪随机函数及其在隐私集合求交中的应用。此工作是由我和Kalashnikov、Kumaresan、以及Rosulek共同完成的。在论文中，我们提出了一个高效的隐私集合求交协议。

隐私集合求交是密码学中一个非常有趣的问题。我们以一个简单的场景为例，来看看什么是隐私集合求交。例如，幻灯片上有两个参与方：Alice和Bob。每个参与方都有一个集合，这里分别是 和 。他们想计算两个集合的交集，但不想泄露其它额外的信息。例如，Alice不能知道Bob集合中非交集的元素。Bob也是类似的，他不能知道Alice集合中非交集的元素。这就是隐私集合求交问题的定义。

隐私集合求交的应用场景非常广泛，我这里给出的例子是通讯录匹配场景。例如，Alice有一个手机，里面存储着Alice的通讯录，Alice想要使用Skype。另一边，Bob是一个Skype服务器，里面存储着客户数据。

现在，Alice希望知道她的哪些朋友使用Skype，她希望使用Skype与朋友们聊天。很明显，两方希望计算集合的交集。

然而，Alice不想泄露自己的通讯录，因为这是她的个人信息。

Bob也面临类似的问题，他不能泄露自己的客户数据，因为这是客户的隐私。这个场景就需要使用隐私集合求交功能。

当考虑隐私集合求交这个问题时，我们可能会提出下述解决方案。Alice拥有集合 ，Bob拥有集合 。他们分别对 中的元素求哈希，对 中的元素求哈希。

Bob随后将哈希值发送给Alice。Alice对比两个集合的哈希值，并输出哈希值相等的元素，即交集元素。

这个协议效率非常高，因为协议只涉及到哈希值的计算。协议涉及的通信量也很小。但不幸的是，这个方案是不安全的，因为这个方案会泄露Bob输入集合的隐私。为什么呢？如果 属于比较小的域，例如 为电话号码，只包含大约10个数字，Alice直接计算上亿个电话号码的哈希值，并将结果与从Bob收到的结果对比。这样，Alice就可以知道Bob的输入了。这也是此协议被称为朴素哈希的根本原因。因此，这是一个不安全的PSI协议。

为了解决这个问题，学者们提出了很多PSI协议。当前最先进的PSI协议由Pinkas、Schneider、Segev和Zohner在2015年提出。隐私集合求交场景下的特殊情况为隐私相等性检测，即两个参与方希望知道两个字符串是否相等。他们的PSI协议通过不经意传输扩展实现隐私相等检测。他们还提出了一个高效的哈希技术，可以将隐私相等检测高效转换为隐私集合求交。我们的核心技术贡献是提高隐私相等检测的效率。

我们来看看Pinkas、Schneider、Segev、Zohner提出的隐私相等检测协议。Alice拥有 ，而Bob拥有 。我们想知道 是否成立。幻灯片上给出了一个例子： 、 。他们协议的核心思想是对 和 进行逐比特对比。如何做到这一点呢？他们使用了一个安全的黑盒工具，此工具叫不经意传输。

Bob分别为0和1随机采样两个 比特长的字符串。随后，Bob和Alice执行不经意传输协议，Alice的输入是她的第一个比特0。协议执行完毕后，Alice收到她第一个比特0所对应的字符串0。然而，Bob无法得知Alice在不经意传输中的输入是什么，此性质由不经意传输协议的定义所保证。他们继续对第二个比特、第三个比特执行此种操作。现在，Bob从OT协议中取得自己输入所对应的字符串。他的输入比特是011，因此他分别取得0、1、1所对应的三个字符串。他对几个字符串求异或，将结果发送给Alice。Alice也取得OT执行完毕后的结果，即0、0、1所对应的三个字符串。她对几个字符串求异或，并对比Bob发送过来的异或值。这样Alice就知道双方的输入是否相等了。这就是当前PSI协议的隐私相等检测过程。

协议执行过程中，双方逐比特对比 和 ，而协议的基本思想是将多个2选1-OT协议替换为一个N选1-OT协议。当前PSI协议使用了Kolesnikov和Kumaresan于2013年提出的OT扩展协议，这意味着每轮协议只能同时对比8比特长的 和 ，我后面会讲解为什么会这样。因此，他们的PSI协议中 。这意味着他们协议的OT执行次数依赖于 和 的比特长度。他们的协议还需要通过多个OT实现完整的隐私相等检测。

在我们的工作中，我们提出了一个OT扩展协议。此协议中的N可以任意大。在我们的协议中，N可以为无穷大。这样，我们只需要使用一次OT即可实现隐私相等检测过程。

这是当前PSI协议的另一个观察结论。我们将此协议看成一个黑盒。如果Alice的输入是 ，而Bob的输入是 ，这里 包含右侧的6个数据块，在PSI协议执行完毕后，Alice收到字符串0、0、1的异或值，我们可以将此异或值看成 。这意味着协议执行完毕后，Alice只能知道 所对应的 。而Bob已知全部的6个数据块，因此Bob可以对任意 计算得到 。

这里一个非常重要的性质是，如果 ，则对Alice来说 看起来是个随机数。这么看来，此协议本质上就是一个不经意伪随机函数。不经意伪随机函数是Freedman、Ishai、Pinkas和Reingold在2005年提出的概念。进一步，如果Bob将异或值，也就是 发送给Alice，则Alice可以简单地比较 和 ，得知这两个值是否相等。这就是隐私相等检测协议的原理。

在接下来的讲座中，我会聚焦于OT扩展协议本身。我们将首先介绍原始的2选1-OT扩展协议，再介绍N选1-OT扩展协议，最后介绍我们构造出的∞选1-OT扩展协议。随后，我们会介绍∞选1-OT扩展协议和我们提出的OPRF实例之间的关系。这里的OPRF对原始OPRF的定义进行了弱化。我后面会详细讲解定义具体的弱化点。我们将我们的OPRF应用在PSI上，从而构造了一个半诚实安全的PSI协议，比当前PSI协议的执行效率高3倍。正如我前面所说，当前PSI协议中，OT的执行次数依赖于集合元素的比特长度。我们的协议移除了OT执行次数与集合元素比特长度的依赖关系。

我们先来简单介绍Beaver的OT扩展协议。OT扩展协议的基本思想是，可以用少量OT和对称密码学操作构造大量的OT实例。Beaver在数十年前首次提出了这个想法。

现在，我要向大家介绍一个非常著名、非常高效的OT扩展协议。此协议由Ishai、Kilian、Nissim和Petrank于2003年提出。此协议的基本思想是，在基础OT协议中，Alice选择一个随机的 比特长字符串 。她计算得到另一个字符串 。在另一端还有个参与方Bob，他有一个单比特字符串 。

如果 ，则Bob接收到第一列字符串 。

如果 ，则Bob接收到第二列字符串 。

也就是说，Bob可以根据自己的选择比特 接收到字符串 。OT协议定义的功能就是这样的。

现在，他们重复上述过程 次，每次都使用相同的 。最后，Bob收到包含 列的矩阵 ，每列 的值都由比特 所决定。

现在，他们使用轻量级的密码学技术伪随机数生成器将 个OT扩展为 个OT。这里 要远远大于 。 大约等于 。

在整个协议执行过程中，Alice得到了矩阵 和矩阵 。我们将这组矩阵称为OT矩阵。

如果我们从行的角度观察这个矩阵，并且令 表示第一个矩阵的第 行。如果令 表示 的第 个比特值，则第二个矩阵的第i行就等于 ，则此时 。左右两行下标相同，取值也相同。

如果 ，则第二个矩阵的第i行等于 。此时 。

也就是说， 或者等于0，或者等于1，长度为1比特。而 。

现在，我们把目标聚焦于OT矩阵本身。如果Alice的输入是 ，Bob的输入是 ，则Alice已知 ，她可以计算 的哈希值。Bob收到 后，可以计算 的哈希值，以及 的哈希值。这里一个非常重要的性质是， ，或者 ，具体等于什么取决于 。也就是说， 和 有且仅有一个值等于 ，而另一个值对Alice来说看起来像随机数。换句话说，Bob有两个值，Alice只知道其中的一个值。

在2013年，Kolesnikov和Kumaresan指出，IKNP协议中包含重复编码。如果称 是一个 个比特值重复编码 次的编码过程，我们再来研究一下IKNP协议。第二个矩阵的第 行等于 ，而 。Bob计算的是幻灯片上这两个值的哈希值。

现在，如果把随机编码移除，将 替换为纠错编码，则此协议可以支持长度最大为8比特的选择比特值 。这也是为什么当前PSI协议只能对比8比特长的 和8比特长的 。举例来说，我们令 的输入为3比特长，此时Bob需要根据幻灯片上的公式计算8个哈希值。我们得到了一个非常重要的性质： 。

现在，我们观察等式中的绿色部分。如果 ，则绿色部分等于0。绿色部分与 逐比特与，计算结果还是0，这意味着我们得到的是 。换句话说，Bob可以计算 个哈希值，而Alice只能得到其中一个哈希值，这也是为什么此协议被称为N选1-OT的原因。从安全角度看，他们的协议要求 的汉明重量要大于 。我们翻到下一页幻灯片，讲解其中的原因。

Bob能得到什么？他计算得到 ，这个值等于 。如果 ，则此表达式计算得到的值对Alice来说是个随机数。然而，如果Alice可以通过某种方式猜测 的值，如果Alice知道了 ，她就知道了 ，她也就知道了 ，这实际上意味着Alice知道此表达式所有红色部分的取值，但不知道蓝色部分 的值。如果 的最小汉明距离为 ，则 的汉明重量大于 。这意味着，Alice必须正确猜测 中的 个比特。这样一来，此协议就满足安全性要求了。

下面是我们的观察结论，我们发现，我们不需要使用编码算法。我们将 替换为输出 比特长随机字符串的随机函数。这是一个非常小的技巧，但这个技巧让我们的协议变得非常厉害。

如果我们将 替换为随机函数，则我们的协议可以支持任意长度的 。也就是说，这里的 可以为任意比特长。从Bob的角度看，他可以计算得到 。这意味着从正确性角度看，我们所得到的协议与之前的协议功能完全相同。在我们的协议中，Bob可以计算任意哈希值，而Alice只能知道其中一个哈希值。这就是为什么我们称我们的协议是∞选1-OT扩展的原因。从安全性看，我们要计算 的最优输出比特长度，让此长度等于 ，从而得到安全性。

从前面两页幻灯片中，我们可以得到幻灯片上的这一行结论。现在，我们将 设置成了伪随机函数。从安全性角度看，我们只需让 的最小汉明重量是可忽略函数即可。为此，我们让伪随机函数 的输出比特长度为 。这就是为满足协议的安全性，我们需要设置的算法参数。

这也意味着我们需要把基础OT矩阵宽度扩展到 比特。不过，我们没必要使用更多的基础OT来扩展OT矩阵宽度。我们使用了一个小技巧。应用伪随机数生成器将OT矩阵的高度扩展到 比特。随后，我们对矩阵转置，得到宽度为 比特的基础OT矩阵。这样，我们的协议就满足了安全性要求。

这是协议的完整执行流程。再次强调，如果 ，则 看起来像是随机数。而 ，这就是不经意伪随机函数 的定义。OT矩阵的每一行都定义了一个OPRF实例，这也是为什么我们将我们的协议命名为批处理OPRF的原因。每一行对应的第二个密钥 均不相同，但第一个密钥 是相同的。因此，我们得到的是批处理密钥相关OPRF。

这也是为什么我们将我们的协议最终命名为批处理密钥相关OPRF的原因。

很容易在PSI上应用此OPRF。Bob将 发送给Alice，Alice简单比较 和 ，并告知这两个值是否相等。如果 ，则对Alice来说 像是个随机数。这意味着Alice无法猜测得到有关r'的任何信息。这就是隐私相等检测协议的执行过程。

最终，我们协议的OT执行次数不依赖于输入比特长度 、也不依赖于 。我们的协议比当前PSI协议执行效率快3倍。

幻灯片上给出了半诚实PSI协议的执行效率对比。基于电路的PSI协议的意思是使用通用安全计算协议实现PSI，此类协议的执行效率较低。如果我们使用公钥密码学构造PSI协议，协议的通信效率很高，但计算效率较低。基于OT构造PSI的协议效率较高，计算复杂度和通信复杂度都比较低。我们也对比了最近提出的两个协议，我们的协议比当前PSI协议执行效率快3倍。X轴用10为底的对数进行了放缩。我们协议的执行效率进一步向朴素哈希算法的执行效率迈进。

感谢大家的聆听。

主持人：感谢主讲人的演讲，我们还有一些提问的时间。

提问者：你好，有个地方我没有想明白。如果我们用盲签名等公钥密码学方案构建OPRF，则此类方案只需要一轮交互，但你提到公钥密码学方案的执行效率很低。

主讲人：你能再描述一遍问题吗？

提问者：应用OPRF实现PSI的最直接方法是，Alice要求Bob对双方的字符串签名。Bob对字符串签名，并将结果返回给Alice。Alice检查签名结果是否相等，只要签名结果是唯一的，这个协议就是正确的。当然这里还有很多限制条件，比如不能直接使用RSA。但是，这个方案效率很高，可以实现PSI。你前面提到，参与方A要对参与方B所有的字符串签名。

主讲人：是的。

提问者：参与方A同时要对它自己的字符串签名，随后取两组签名的交集。但你前面提到这个过程效率很低，因为…

主讲人：我明白了，感谢你提出的问题。我们的OPRF只需要使用少量的公钥密码学方案 但需要使用大量的对称密码学方案，这就是我们的协议要比公钥密码学方案的协议高效的原因。

提问者：因为你只需要执行128次公钥密码学操作吗？

主讲人：是的，我们只需要执行128次，你可以看这页幻灯片。这里的技巧在于，我们在OPRF协议中使用了OT扩展协议，这意味着我们只需要执行128次公钥密码学操作，或者说κ次公钥密码学操作。

提问者：明白了。

主讲人：是的，我们还使用了对称密码学。很显然，对称密码学的执行效率比公钥密码学高得多，所以…

提问者：明白了。

主讲人：好的。

提问者：谢谢，所以这个方案才能这样高效地完成计算，明白了。

主讲人：是的。

提问者：谢谢。

主持人：听众还有什么其它问题吗？没有其它问题了，我们再次感谢主讲人。