细探不经意传输- 大数跨境

杭州量安科技有限公司

2023-10-25

导读：不经意传输(Oblivious Transfer)是安全多方计算的原语之一，如果说安全多方计算起源于百万富翁问题，那么我们也可以通过一些“游戏”，来了解不经意传输的具体含义。

不经意传输(Oblivious Transfer)是安全多方计算的原语之一，初次接触它难以一下子了解其背后蕴含的密码学含义，因而本文将从简到繁，通过描述不经意传输诞生过程中涉及到的三个计算任务，进而引出不经意传输的准确计算功能描述，并给出具体的密码学实现方式。在后续的介绍中，我们将Bob作为发送方，Alice作为接收方。

第一个计算任务：Bob需要告诉Alice一个秘密。这里我们要如何实现呢？显然，在现实中，Bob只需要在没有第三个人的情况下，小声的把秘密告诉Alice即可。在网络世界，利用公钥加密的思想，我们也可以实现这一计算任务，但这可能会遇到网络传输中的第三方攻击问题。不考虑第三方攻击的情况下，这一计算任务是可以实现的。值得一提的是，我们有相对应的安全手段防止第三方的攻击，但这里就不是安全多方计算所考虑的范围了，因此后续的任务我们不再考虑外部成员的攻击问题。

第二个计算任务，Bob持有多个秘密，但是只想让Alice知道其中的一个，因此他让Alice从多个秘密里选择一个秘密。这样的实现方式也很简单，Bob把秘密写在卡片里，并逐个编号，再让Alice来进行选择。Alice只需要将选择的编号告诉Bob，Bob把编号对应的秘密发送回Alice就行了。

但在这个过程中，编号和秘密的对应关系仅有Bob知道，从Alice的角度看，其无法准确地得到自己想要知道的那条秘密，能否获得想知道的秘密纯看“运气”（有没有选择到对应的编号），即使Alice运气爆棚选到了想要秘密的编号，Bob收到编号后，也有将其对应的秘密进行交换的可能性（作弊）。因此，第二个计算任务的成功实现存在着很多值得进一步讨论并优化的地方。

第三个计算任务，Bob持有多个秘密，但是只想让Alice知道其中的一个，因此他让Alice来选择一个编号，同时Alice也不想让Bob知道她选择的编号是什么。我们依旧首先从现实的角度来出发，Bob把秘密写在相同外形的卡片里，并且随机打乱，Alice从随机打乱后的秘密中选择一个进行查看，再放回。在此过程中，需要保证Bob不能查看其余卡片的内容，否则，Bob就可以从剩余的卡片内容来反推Alice查看的内容，可一旦Bob查看成功，此计算任务就等同于第二个计算任务，依旧没有达到实现Bob不知道Alice选择哪一个秘密的要求。

第三个计算任务实际上就是一个不经意传输，具体存在两个要求：（1）接收方能从发送方获取他选择的秘密，（2）发送方不能够知道接收方选择了哪个秘密。同时满足这两条要求并非易事，这也是不经意传输这一原语如此经典，几十年来一直被密码学者探讨的原因之一。

以上是关于不经意传输的通俗理解，但密码学是一个严谨的学科，接下来我们将从更专业的角度来阐述不经意传输。

1981年Rabin首次提出了不经意传输的思想，发送方会给出一个比特，而接收方有50%的概率能够拿到这个比特。将它与我们上面的内容进行联系，发送方将一个真比特和假比特写在“卡片“上，接收方从中选择一张，并且发送方不知道接收方拿到的是真比特的卡片，还是假比特的卡片。1985年Even等人就此正式给出了等价定义：发送方持有两个消息，接收方持有一个选择比特，接收方能够获取该选择比特对应的消息，而发送方不知道接收方的选择比特是什么，获取的是哪一条消息。

这样的功能描述意味着我们可以将不经意传输作为黑盒进行调用，来支撑一个更复杂的计算函数。但其自身功能函数的实现方式，需要基于一些数学难题，并借助公钥密码操作。比如，一个基于离散对数难题的实现方式如图1所示：

图1 基于离散对数构造的不经意传输协议

之所以Alice只能得到消息

而不能得到

，是因为Alice不知道

，而且由于不知道r，无法通过已知的C和

计算得到。

上述构造不仅可以适用于二选一的不经意传输(写作

），还可以扩展到n选一的情况下（写作

）。其主要的区别在于：发送方持有n条消息，而接收方持有比特串

，可以包含n种选择。同样地，其可以使用基于离散对数的方法实现，具体如图2所示。

图2 基于离散对数构造的

除了二选一不经意传输和选一不经意传输之外，还有n选k不经意传输，广义不经意传输等等，此文章就不具体介绍了。

不经意传输的构造方法有很多种，上述介绍的是一个较早提出的构造方法。由于依赖了公钥操作，如果需要发送m组消息，那么就需要m次公钥操作，这样的开销就比较大了。因此，提升不经意传输的效率一直是学者研究的重要方向，用对称加密和公钥加密的结合方式，就是一个不错的思路。比如Ishai等人提出的不经意传输扩展方案，如图3所示。

图3 不经意传输扩展方案

该方案基于了转置的思想，原始的多组不经意传输，是对每一行的数据进行处理，但是随着组数的增加，需要的公钥操作就随之增加。然而，保证安全性所需的操作不一定需要随着组数的变化而变化，只需要满足一定的安全参数即可。消息的长度如果是固定的话，就可以对每列的数据进行不经意传输，这样就可以使公钥操作保持在一个常数范围。该不经意传输扩展方案中，包含一个原始不经意传输操作，对于内层的不经意传输来讲，发送方和接收方在内层的身份是互换的，并且内层的不经意传输是有关联的不经意传输。其内部实现如图4所示。

图4 不经意传输扩展方案内部实现示意图

除了有关联的不经意传输之外，还有随机不经意传输等变种。随机不经意传输示意图如图5所示。

图5 随机不经意传输示意图

我们在有关联的不经意传输可以察觉到，实现不经意传输的关键是在于变量的关联性，而不是在于输入输出的因果性。因此随机不经意传输也很容易能够理解，原本是发送方的Bob主动输入消息，而是随机生成两个消息，Alice也不再是主动选择比特，而是随机生成比特。基于随机不经意传输的实现框架如图6所示。在此设定下，输入与输出之间仍然保持了一个关联性，如果需要在随机不经意传输的主干上实现主动输入消息，可以采用随机消息和主动消息相复合的方法。

图6基于随机不经意传输的实现框架

采取随机消息和主动消息相复合的方案看似把问题弄复杂了，显得多此一举，但事实上，随机不经意传输产生随机消息的步骤是可以离线生成的，虽然这部分效率相比于前面的原始不经意传输没有实质性优化，但是由于在很多场景下，离线部分的时间是可以忽略不计的，因而结合具体实现场景，随机不经意传输是一个提升方案性能很好的选择。此外，由于有些组件只能够保证关联性，而无法保证因果性，因此具有极大可能性只能构造出随机不经意传输的功能函数与实现方案。

除了Ishai等人提出的不经意传输方法外，后续很多学者都对之进行了改进。当然，最令人兴奋的是来自于Boyle在2019年基于另外一种思想构造的silent OT，这个类型的不经意传输极大降低了通信量，使得不经意传输更具有实用性。该类型的不经意传输不是基于转置思想，而是基于LPN难题假设，该方向的研究也是目前的一个热点。

关于我们

杭州量安科技有限公司（以下简称量安科技）成立于 2022年，由之江实验室孵化，专注于后量子密码、高性能国密和数据安全领域，为政务、金融、大型企业、军工、医疗等领域提供新一代密码产品和服务。量安科技成立之初即获得数十家知名投资机构青睐，目前已完成三轮融资，共计数千万元，并获杭州市余杭区顶尖人才政策支持。同时，公司牵头主持密码相关国家重点研发计划，并多次获得行业内重要奖项，包括2022 年全球数字贸易博览会先锋奖银奖（年度最高奖）、2022 第三届中国数字经济科技大会年度最具竞争力产品创新奖、2022 第三届中国数字经济科技大会年度数据安全金盾奖等。

往期回顾

◆你的数据，我的密码：强大的同态加密

◆“道高一尺魔高一丈”的后量子密码

◆一文简单了解密码共享

【声明】内容源于网络

杭州量安科技有限公司

杭州量安科技有限公司由之江实验室孵化、院士领衔，是国内首家专注于后量子密码研究与产业应用的公司，为电力、政务、金融、军工、医疗等领域提供新一代密码产品和服务。

内容 53

粉丝 0

杭州量安科技有限公司杭州量安科技有限公司由之江实验室孵化、院士领衔，是国内首家专注于后量子密码研究与产业应用的公司，为电力、政务、金融、军工、医疗等领域提供新一代密码产品和服务。

总阅读2

粉丝0

内容53