论文分享 | Endemic Oblivious Transfer via Random Oracles, Revisited

本文介绍的文章是由浙江大学网络空间安全学院博士生周哲磊和其导师张秉晟研究员以及任奎教授与美国弗吉尼亚联邦大学周红生副教授合作撰写的论文《Endemic Oblivious Transfer via Random Oracles, Revisited》，该论文被国际密码顶会之一欧密会（EUROCRYPT 2023）录用，研究内容为不经意传输。

论文链接：https://eprint.iacr.org/2022/1525

1

研究背景

不经意传输（Oblivious Transfer，下面简称为OT）是一种重要的密码学原语，隐私计算技术的基石，许多著名的安全多方计算协议（如姚氏混淆电路[1]、GMW协议[2]）都依赖于OT。简单来说，OT是一个两方协议，发送方有两个文件m0,m1，接收方可以任意获取其中一个文件，但发送方无法知道接收方选择了哪个文件。除了作为基本组件构造其它安全协议之外，OT本身也是一种可保护隐私的密码协议，在电子商务、内容保护等系统中起到非常重要的作用。因此，对于OT的研究具有深远的意义，也一直受到国内外学者的密切关注。

图1 不经意传输

EOT（Endemic Oblivious Transfer）是OT的一类变种，在2019年由Masny和Rindal提出[3]。在EOT中，发送方没有输入，但是在协议最后，发送方会得到两个随机数据，而接受方会得到两个随机数据中的一个；需要注意的是，恶意参与方可以影响随机数据的分布。所以，相较于传统的OT，EOT看起来拥有更“弱”的安全性，但是EOT胜在计算量更小、通讯量更低。当作为基本组件用于OTE（OT Extension，即OT的批量生成）的构造时，基于EOT的OTE会比基于OT的OTE更加高效。我们的主要研究对象便是EOT。

UC框架为密码学协议设计提供了一种模块化的设计方法，在密码学领域具有重要地位[4]。然而在UC框架下，协议的初始化设置均局限于协议自身，不同协议之间不能共享初始化设置。为了解决这个问题，GUC框架（和其补充EUC框架）被提出[5]。在GUC框架下，不同协议之间可以共享初始化设置，这更贴合实际应用场景。我们把在GUC（UC）框架下设计的协议，称为是GUC（UC）安全的。我们的研究涵盖了UC框架和GUC框架，做到了理论完备。

图2 UC，GUC和EUC框架之间的对比

在UC框架下，两方安全协议的实现都需要一个初始化设置，而我们所选取的初始化设置便是随机谕示机（Random Oracle，下面简称为RO）。RO是密码学中一类重要的初始化设置[6]，它具有透明、不依赖可信假设等特点。许多知名、高效的安全协议都建立在RO模型下：如Ligero[7]、ZKBoo[8]等。RO可以看作是一个初始为空的数据库，当有询问方来查询时，RO会检查询问方所查询的内容是否存在，如果存在，那么就会回复所存储的值；如果不存在，那么RO会生成、存储并回复一个随机值。在实际应用中，人们常常使用哈希函数（如SHA256）来实例化RO。

在GUC框架下，我们同样需要一个初始化设置。然而，传统的RO模型在GUC框架下并不适用。因此，我们采用了两类知名的全局RO模型，即GroRO[9]和GrpRO[10]。这两类模型可以视为是RO模型的拓展，但是各有侧重。GroRO模型允许模拟器（Simulator，UC/GUC框架中的一种术语）能够获取敌手对GroRO的查询，而GrpRO模型允许模拟器对GrpRO中未经查询的内容进行编辑。GroRO和GrpRO虽然被提出已久，但是它们之间的关系仍未被探索。在研究EOT的同时，我们期望能够找到这两类模型之间的关系。

2

研究成果

在[3]中，Masny和Rindal给出了RO模型下的UC安全的一轮EOT协议构造，但他们协议的安全性基于一个不标准的数学假设（即CODDH假设）。CODDH假设的安全性并没有被深刻理解，因此，[3]中的所提出的协议可能有安全隐患。

为了解决这个问题，我们提出了首个基于标准的数学假设（即DDH假设）的RO模型下的UC安全的一轮EOT协议构造。除了使用标准的数学假设以外，我们的协议还能够抵抗动态敌手（adaptive adversary，即敌手可以随时腐蚀协议参与方），而[3]中的协议只能抵抗静态敌手（static adversary，即敌手只能在协议执行之前就腐蚀协议参与方）。因此，我们所提出的协议更加安全可靠。

除了在UC框架下研究EOT之外，我们还在GUC框架下对EOT展开了深入的研究。在GroRO模型下，我们给出了首个基于CDH假设（CDH假设也为标准的数学假设）的GUC安全的一轮EOT协议构造。而在GrpRO模型下，我们证明了GUC安全的一轮EOT不存在，并给出了基于DDH假设的GUC安全的两轮EOT协议构造。基于此，我们发现了GroRO和GrpRO这两个模型并不等价，部分解决了一个悬而不决的公开问题。GroRO和GrpRO的关系如图3所示。

图3 GroRO和GrpRO之间的关系

最后，我们还研究了EOT本身的能力。在[3]中，作者部分揭示了EOT和另一类不经意传输（即Uniform Oblivious Transfer，下面简称UOT）之间的关系。UOT和EOT的功能是一样的，只是在UOT中，恶意参与方也不能影响随机数据的分布。在[3]中，作者发现了UOT蕴含了EOT，即在不借助任何其他密码学原语、不增加其他假设的前提下，仅需UOT就能构造出EOT；同时，作者发现使用EOT和Coin-flipping这两种密码学原语就能构造出UOT。我们进一步地研究了EOT的能力，并发现EOT蕴含了最基础的密码学原语：承诺协议（Commitment）。同时，又因为承诺协议蕴含了Coin-flipping，所以我们揭示了EOT也蕴含了UOT，即EOT和UOT在信息论层面是相互等价的。EOT和UOT的关系如图4所示。我们对EOT本身的研究揭示了一个反直觉的结论：虽然EOT所能实现的功能看起来很“弱”，但是在信息论层面上EOT非常“强”。我们的研究进一步地说明了EOT的重要性。

图4 EOT和UOT之间的关系

(a)为[3]中所揭示的关系

(b)为该论文所揭示的关系

总体来说，我们解决了有关EOT的若干公开问题，并给出了高效、安全、可靠的EOT协议构造，实现了理论和技术上的双重突破。

3

引用文献

[1] Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). FOCS 1982.

[2] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. STOC 1987.

[3] Daniel Masny and Peter Rindal. Endemic oblivious transfer. CCS 2019.

[4] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. FOCS 2001.

[5] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. TCC 2007.

[6] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. CCS 1993.

[7] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. CCS 2017.

[8] Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. ZKBoo: Faster zero-knowledge for Boolean circuits. USENIX Security 2016.

[9] Ran Canetti, Abhishek Jain, and Alessandra Scafuro. Practical UC security with a global random oracle. CCS 2014.

[10] Jan Camenisch, Manu Drijvers, Tommaso Gagliardoni, Anja Lehmann, and Gregory Neven. The wonderful world of global random oracles. EUROCRYPT 2018.

本文来源浙江大学网络空间安全学院官网

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

END

往期推荐

1.一文搞懂分组密码——DES、AES、IDEA
2.笔记分享 | 冯登国院士MPC讲座（3）——基于混淆电路方法的安全多方计算协议3.技术分享 | 隐私集合求交（PSI）技术体系整理4.联邦学习算法分类总结