传输短秘密值的条件下提高OT扩展协议的效率

最近收到了一位知友的私信，询问能否把《Winter School on Cryptography 2012: Lattice-Based Cryptography》的一系列字幕也发布出来，供参考和学习。经过与

当时字幕负责人的讨论，由于相关字幕已经发布了很长时间，我已经可以将字幕发布出来供知友们学习了！因此，在接下来一段时间，我会集中整理《Winter School on Cryptography 2012: Lattice-Based Cryptography》的字幕，重新压制视频并放出。感谢 一直以来的支持！

虽然会集中整理之前的字幕，但是我也会不断听写新的视频，如果有任何顶级安全会议中数据安全相关讲座的听译需求，还请知友们私信我，或者直接在评论区留言。对于一些很大工作量的听译工作（如《Winter School on Cryptography 2015: Practical Secure Multi-Party Computation》这类），我也会持续坚持听译，到合适的时间再对外发布，敬请知友们耐心等待。

演讲视频简介

本次为知友们带来的视频是CRYPTO 2013论文《Improved OT Extension for Transferring Short Secrets》。OT Extension协议是安全多方计算中最重要、也是最核心的协议。熟悉OT的知友们可能知道，OT Extension中最核心的论文应该是CRYPTO 2003的《Extending Oblivious Transfer Efficiently》以及CCS 2013的《More Efficient Oblivious Transfer and Extensions for Faster Secure Computation》。不过我一直没有找到这两个讲座的视频，如果哪位知友知道视频链接，也可以在评论区告诉我。

《Improved OT Extension for Transferring Short Secrets》的重要程度相对这两篇论文来说没有那么高，但这篇论文是优化GMW协议的重要理论基础。如果想实现基于GMW协议的安全多方计算应用，这篇论文的阅读和实现也是必不可少的。CRYPTO 2013对应的演讲视频介绍了《Improved OT Extension for Transferring Short Secrets》的基本思想，观看视频后再去读论文会有更深入的理解。

演讲视频信息

中文字幕视频

演讲视频字幕

非常感谢主持人的介绍。此工作是我与来自贝尔实验室的Vladimir Kalashnikov所共同完成的。我们工作针对的目标是安全计算，这是密码学上一个非常典型、非常普遍的问题。

当前有很多重要的研究进展，尝试让安全计算从理论走向实际。这些工作的目标不仅是要提高协议的渐进效率，还要提高协议的真实执行效率。还有一些工作的方向是具体协议的实现，解决系统层面的问题。

在过去的5年，无论是理论角度还是实际角度，此领域都诞生了极多的突破性成果。从理论角度，我们得到了很多惊人的结论。我们现在只需要引入常数级额外开销，即可完成安全计算或安全函数求值。另一个突破是全同态加密。对于多种类型的函数，我们甚至可以在最优通信复杂度下构建安全计算协议。还可以使用基于ORAM的安全计算协议，利用RAM计算模型的优势完成安全计算，这样我们就能在次线性时间复杂度下完成安全计算。在实践角度，针对姚氏协议和GMW协议，学者们提出了很多算法或实现层面的优化，也尝试混合使用姚氏协议和GMW协议。特别地，姚氏协议的实现结果令人印象深刻。现在，我们可以在637毫秒内执行完AES的乱码电路。

虽然在实现层面和理论层面我们都得到了令人惊讶的成果，但在右侧，效率最高的协议仍然是20世纪80年代提出的姚氏协议和GMW协议。之所以这样，有一个很直观的原因：理论成果虽然引入常数复杂度，但这个常数可能非常大。

实际应用时，可能存在这样一个复杂度与效率的层级关系。FHE的复杂度目前、以后也总会比公钥密码学原语的复杂度高几个量级。公钥密码学原语的复杂度目前、以后也总会比对称密码学原语的复杂度高几个量级。对称密码学原语的复杂度目前、以后也总会比一次一密的复杂度高几个量级。本次演讲的主题是OT扩展，其出发点就是减小公钥操作和对称密码操作的效率鸿沟。

在第一部分演讲中，我会详细介绍OT扩展的研究出发点，并解释OT扩展面临的问题。

诸如密钥协商、不经意传输等公钥密码学原语一般都很难高效实现。公钥密码学原语天生要依赖于某类代数结构，因此也会遭受很多密码学攻击。因此，相应的参数需要设置得比较大。这导致公钥密码学的计算复杂度也相对较高。另一方面，我们更容易实现伪随机数生成器或哈希函数等对称密码学运算。学者们设计出了很多算法，相应的参数要比公钥密码学小得多，实际中也可以更容易、更轻量级地实现对称密码学运算。这个结论背后还有相应的理论支撑。理论上，无法通过黑盒方式应用对称密码学原语构造大多数公钥密码学原语。这意味着公钥密码学原语和对称密码学原语的性能差约为3至4个数量级。对于诸如AES等被广泛使用的特定对称密码学操作，Intel专门提供了对应的指令集，进一步提高了这类运算的执行效率。因此，我们无法通过对称密码学原语实现公钥密码学原语。

那接下来该怎么办？或许可以用少量公钥原语实例和大量对称密码学操作，生成大量公钥实例。这一技术称为“扩展原语”。我们已经知道，很容易扩展公钥加密体制，具体过程是用对称加密算法加密具体的明文，用公钥加密算法加密对称加密的密钥。这样一来，我们只需要执行一次公钥操作。这一技术在我们每天使用的加密过程中起到了非常重要的作用。我们可以很自然地把这个问题展开：是否可以扩展其它公钥密码学原语。如OT？

回忆一下不经意传输要解决的问题。发送方有两个输入： 和 。接收方有一个输入 。协议执行完毕后，发送方无法得到任何信息，接收方可以得到与其选择比特关联的发送方输入。OT是SFE的基础构建模块。姚氏电路中应用不经意传输实现了乱码密钥的2选1过程。在GMW协议中，OT的用途更加广泛，每个AND门的求值过程都要使用一次OT协议。

我们知道OT的执行开销非常大，我们无法通过对称密码学操作实现OT。但假设我们有一个可以传输短字符串的OT，通过使用标准的伪随机数生成器，我们能得到可以传输长字符串的OT。这一技术称为“OT长度扩展”。

还有一个更难解决的问题，称为“OT实例扩展”，简称“OT扩展”。幸运的是，我们知道OT扩展是可行的。我们只需要 个公钥密码学操作，即 个种子OT，再加上 次对称密码学操作。应用这 次公钥密码学操作，我们就可以执行任意多项式大小次的OT操作。这一技术大幅降低了公钥密码学运算次数，对SFE的实际应用起到了重要的作用。近期大多数SFE的实现都应用了OT扩展协议，从而提高协议的执行效率。

Beaver在1996年提出了第一个OT扩展协议。第一个高效的OT扩展协议由Ishai、Kilian、Nissim和Petrank给出。此协议也称为IKNP协议，对应的论文发表在CRYPTO 2003上。后续，学者们期望在恶意攻击场景下提高OT扩展协议的执行效率。学者们同时也在加深对OT扩展协议的理解，从而知道OT扩展协议的上限是什么。在本工作中，我们将在半可信场景下提高IKNP协议的效率。我们给出了协议的渐进优化方法和实际优化方法。

在接下来的讲座中，我们会描述Ishai等人的OT扩展协议构造。实际上，我们将直接使用Ishai等人CRYPTO 2003的演讲幻灯片。

IKNP第一个、也是最重要的步骤是将 个OT归约为传输 比特字符串的 个OT。这一步骤将引入额外的、线性数量级的对称密码学操作。下一步是长度扩展步骤，我们之前已经讲解过这一步骤了。这可以让我们把长字符串OT协议归约为短字符串OT协议。这一步骤进一步引入了线性数量级的对称密码学操作。

在核心归约步骤中，我们让接收方选择一个随机的 矩阵 。随后，发送方选择一个随机的行向量 。接下来，接收方和发送方执行 个OT协议，但此OT协议中两个参与方的角色互换。在每个OT协议中，接收方要选择长度为 的两列比特值。每对比特值中。第一列为矩阵 中的某一列，第二列为第一列比特值与选择向量 的异或结果。发送方实际上应用它随机选择的行向量在接收方的两列比特值中选择一列。

这样，发送方通过OT协议得到了一个矩阵 。我们来看看矩阵 Q 满足何种性质。如果 ，则 。如果 ，收到的每对比特值就不太一样了。如果 ，在IKNP协议中 。

注意到，在第一种情况下，接收方知道 ，但无法知道 。因此，在第一种情况下，接收方能得到 ，但无法得到 。在第二种情况下， 接收方能得到 ，也就是 ，但无法得到 。这意味着我们或许可以使用 和 作为OT协议中的数据加密密钥。但需要注意的是，我们必须要破坏矩阵中 和 的相互关系。我们应用随机预言机 来破坏 和 的相互关系。最后，接收方根据 选择得到它的输出，也就是应用 进行解密。

IKNP协议非常简单、非常优雅、效率极高。

我们考虑 个OT协议所需要的通信开销。其中发送方输入的长度为 。大家已经了解到，核心归约步骤就是对 和 加密，这需要发送 比特的数据。在长度扩展步骤中，我们要应用一个PRG，这需要发送 比特的数据。

在姚氏电路中，我们需要传输长度为 的密钥，因此核心归约步骤和长度扩展步骤中的通信开销相同。在GMW中，我们只需要传输 的信息。令人惊讶的是，这一场景下长度扩展步骤的通信开销远高于核心归约步骤的通信开销。这就是一个问题了，我们可能可以在这一场景下对通信开销进行优化。

在讲座的后半部分，我们会提出IKNP的通用框架。我们也会向大家展示如何提高IKNP的效率。

我们先来详细分析一下IKNP协议。可以看到，接收方要选择这个 的随机矩阵。随后，接收方要生成另一个矩阵，这个矩阵的第 列为第一个矩阵的第 列异或选择向量 。换句话说， ，其中 是所有列均相等的矩阵，每个列都为接收方的选择向量。

如果我们从行的视角看，就会发现 的第 行为 个 ，这意味着 的每一行都是 的一种编码。在IKNP协议中， 被映射为 ，而 被映射为 。因此，我们可以看到IKNP这一高效协议在底层执行了一次逐行重复编码。这自然引出了一个问题：我们是否可以使用更复杂的编码？毕竟，重复编码是一种最简单的编码。

假设我们使用编码 ，并且我们假定 属于一个很大的域，域为从 到 。我们用编码 将 映射成 ，这是一个 比特长字符串。现在，接收方需要用选择比特 构建矩阵 。我们来看看，在这个理论框架下IKNP协议的执行过程。

第一步，接收方获得了矩阵 。随后，接收方用加法秘密分享方案将 分享为 和 ，即 。接下来，接收方和发送方角色互换，执行 个OT协议。在第 个OT中，接收方的输入是 和 ，即 和 的第 列。执行完OT协议后，发送方得到矩阵 。在IKNP协议中，我们知道 或者等于 ，或者等于 。在这一理论框架中，我们可以知道 ，结果不算太复杂。

我们可以验证一下，当C是重复编码时 此框架对应的协议就是IKNP协议。特别地，当 时， 是一个全 向量，因此我们得到 。当 时， 是一个全 向量，此时我们可以得到 。这样一来，我们得到了 个密钥。后面的执行过程就完全一样了，密钥生成算法为 。

我们仍然可以证明接收方只能知道 。因此接收方只能解密对应的密文，从而得到对应的输入。核心归约步骤在恶意发送方的攻击下是完美安全的。特别地，恶意发送方只能得到矩阵 ，这是编码的随机独立分享结果。核心归约步骤在半诚实接收方的攻击下是统计安全的。这是因为除了在加密过程中使用了随机预言机之外，核心归约步骤没有安全性损失。因此，整个协议的安全性损失为 ，即 的取值范围，以及 ，其中 是线性编码 的最小距离。

注意到在此理论框架下，我们可以从 到 选取消息，因此从效果上看，我们可以实现 选1-OT，而不是2选1-OT。但在这种情况下，核心归约步骤的通信开销会从 提高到 。随后，我们将标准的2选1-OT转换为 个字符串长度稍长的 选1-OT实例，这也允许我们将通信开销表示为与 相关的函数。

现在，我们有了一个自由变量 ，用它来平衡核心归约步骤和长度扩展步骤的开销。具体来说，如果我们使用的是最小距离为 的Hadamard编码，在这种情况下，2选1-OT的通信开销可以降低2倍。在多方GMW协议中，如果 ，则通信开销也可以降低2倍。

也可以进一步优化长度扩展步骤的通信开销，此开销的优化程度是算法层面的，而不是渐进层面的。结合Hadamard编码后，与未优化的IKNP协议相比，新协议的通信开销要降低3.5倍。Asharov等人也独立发现了这一优化点，他们的论文将发表在CCS 2013上。

与IKNP相比，我们从渐进层面降低了每一个OT的通信开销。当 时，IKNP需要通信 比特，而我们需要通信 比特。

总结一下，为了平衡公钥密码学原语和对称密码学原语的性能鸿沟，学者们提出了OT扩展协议，这一协议在安全函数求值的实例落地中产生了巨大的影响。在本次讲座中，我们提出了IKNP的编码理论框架。可以在随机预言模型下证明此框架的安全性。随机预言模型也可以换为特定类型哈希函数假设，即相关性健壮哈希函数，这沿用了IKNP中安全性所依赖的相关性健壮哈希函数假设。当使用复杂编码时，此框架提高了多方GMW中2选1-OT和 选1-OT的性能。

我想用GMW和姚氏电路的性能对比问题作为讲座的结尾。近期的安全多方计算研究主要关注恶意模型下姚氏电路的性能优化问题。在半可信安全模型下，学者们也提出了很多姚氏电路的优化方法。但近期的一些工作也表明，GMW协议也有很多算法层面的优化点。我们的工作适用于GMW协议。谢谢大家。