今天给大家带来的是来自Eurocrypt 2023的一篇关于不经意传输的工作Endemic Oblivious Transfer via Random Oracles, Revisited，由浙大张秉晟研究组成员主导，美国弗吉尼亚联邦大学周红生研究组合作撰写，浙大网安投稿。
不经意传输（Oblivious Transfer，下面简称为OT）是一种重要的密码学原语，隐私计算技术的基石，许多著名的安全多方计算协议（如姚氏混淆电路[1]、GMW协议[2]）都依赖于OT。简单来说，OT是一个两方协议，发送方有两个文件m0,m1，接收方可以任意获取其中一个文件，但发送方无法知道接收方选择了哪个文件。除了作为基本组件构造其它安全协议之外，OT本身也是一种可保护隐私的密码协议，在电子商务、内容保护等系统中起到非常重要的作用。因此，对于OT的研究具有深远的意义，也一直受到国内外学者的密切关注。
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的同时，作者期望能够找到这两类模型之间的关系。
研究成果
在[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之间的关系：GrpRO不包含GroRO，而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协议构造，实现了理论和技术上的双重突破。
论文下载：https://eprint.iacr.org/2022/1525
[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.
原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-02-07 Endemic Oblivious Transfer
