“我知道这是二分之一的机会”——1/2不经意传输协议介绍

介绍一个密码学中的概念:“不经意传输”(Oblivious Transfer,OT)。“不经意”一词是英语“oblivious”的翻译,字典里给这个词的解释是“遗忘的、不知道”的,其实这个意思更接近这个概念的本质。

“不经意传输”要解决这类问题:你需要给对方多条信息,但是你又必须确保对方只获得其中一条,但是对方又希望能够确保你不知道他看到哪一条信息。

设计一个具体场景:你给你的哥们介绍相亲女朋友,你有两个可供介绍的单身女性,但是你不想同时将两人的情况和联系方式给对方。但你也无法抉择到底给哪个,所以你想让他随机抽签选择一个。但与此同时,你的哥们也不想让你知道,他最终抽到了谁。这个问题怎么解决?现实中,有个解决方法是这样的:

你把两位女性朋友的资料放进两个一样的信封里,封好口。确保外观上两个信封是一样的。然后你就和你的哥们当场让他选一个信封,剩下一个信封立即烧掉,选中的信封让他带回去慢慢拆开看。

现在我们需要把以上的流程移植到网络上,你和你的哥们不在一处,能否通过电话、微信等手段,安全可靠实现以上的信息传输效果?答案是可以的,这就是今天要介绍的“1/2不经意传输协议”。

而这个“1/2不经意传输协议”,顾名思义,发送方其实是发送了两条信息,但其中只有一条能被正确读取,被接收方收到,而具体是哪一条,但发送方并不知道,也无法决定。这个协议的具体标准一共三条:

第一:如果发送方正确执行协议,并且发送两条消息给接收方,那么接收方只能恰好从两条信息收到一条,获知其中一条的内容。并且按照原版规则,接收方并不能选择接收哪一条(虽然可以做一些改变,使得接收方可以决定收哪条消息)。

第二:对发送方来说,接收方获得两条消息中的任何一条的后验概率都是1/2。它的意思就是,重复不断玩这个游戏,接收方不能使自己看到某条消息的概率升高。不能出现这种情况:在玩了一百次游戏之后,接收方可以90%的概率来接收某一条消息了。可以看出,这条是与第一条有关联的,第一条规定了接收方是没有办法选择接收哪条消息的。

第三条,也是最后一条规则是:如果发送方试图欺诈,使得接收方接收某一条消息的概率高于50%,那么接收方可以发现、识破这种企图。这是三条规则中最严格和难以实现的一条。它不让发送方有操纵接收方接收某一条消息概率的可能。两条消息获得的几率必须是一半对一半。发送方如果试图欺诈,就会被接收方识破。

当然,如果发送方根本没有发送两条不同消息,而是发送两条一模一样的消息,那当然接收方只能收到那条消息。但这种情况不在技术讨论范围内了,我们只考虑正常发送不同消息的情况下,如何防止发送方的欺诈。

另外,规则里并没有说,接收方欺诈,比如同时尝试读取两条消息时,发送方是否能够识破。但看过具体实现后,你会发现,接收方没法欺诈。接收方欺诈的后果只可能是一条消息都看不见。

以上就是“1/2不经意传输协议”的游戏规则,听上去是有点难的。那我们来想想看如何来实现。

首先,为了简化问题,假设你已经把两位姑娘的资料放到某个网盘上,都设置了一个提取密码。现在问题就变为,你需要把两个密码发送给你的朋友,但是你必须确信他只能拿到其中一个的密码,而你的朋友需要确信你不能知道他最终看到哪个密码。

如果说用视频方式重复文章开始时的那个烧信封的流程,你把两个密码放进两个信封,让对方视频里挑一个,然后把信封里的密码给对方看。这样的话,你没法证明你没看到具体的密码。

如果让对方先你一个密码,然后你随机的给某个网盘的提取密码设置成对方给你的密码。但这样的话,这样你就会知道对方最终的选择。

所以,这里能看出,需要实现一种机制,接收方有最终选择权。但是,你需要在不知情的情况下,获得对方的这种选择结果。

这里,要实现这种机制,我们需要用一点密码学里的一个基本知识,就是“非对称”加密体系。关于非对称加密体系,我已经多次提到过,这里再简单介绍下。加密体系分为对称和非对称两种,“对称”就是加密、解密用同一把秘钥,就像你的word文件打开密码。非对称加密体系,就是加密用一个秘钥,解密用另一个秘钥。加密秘钥称为“公钥”,是可以公开的;解密秘钥,称为“私钥”,是需要严格保密的。

但这里要注意的是,无论是是对称还是非对称秘钥,当你用“不正确”的秘钥去解密的时,所发生的情况并不是像你平时输错密码时,被拒绝操作。实际情况是,程序仍然去默默的“解密”。只是解密结果像是乱码,除此以外与你用正确秘钥解密发生的情况是一样的。所以,“秘钥”正确与否,全看解密后的输出。


使用对称秘钥加解密的例子:

用des-ecb加密算法,’C0FEE’为秘钥(对openssl,秘钥需要以16进制数字输入),将字符串“大老李聊数学”加密为base64编码的字符串:“7qEvJ9wvjTNffHd4Brcm4m2u0AtLS7O+”

openssl enc -des-ecb -base64 -in <(echo "大老李聊数学") -K C0FEE
7qEvJ9wvjTNffHd4Brcm4m2u0AtLS7O+

用’C0FEE’可以正常解密:

openssl enc -d -des-ecb -base64 -in <(echo "7qEvJ9wvjTNffHd4Brcm4m2u0AtLS7O+") -K C0FEE
大老李聊数学

用’BEEF’也可以“解密”,只是结果无意义:

openssl enc -d -des-ecb -base64 -in <(echo "7qEvJ9wvjTNffHd4Brcm4m2u0AtLS7O+") -K BEEF -nopad
��^V"�SMS��.�5��x�����I

那么这里有意思的一个情况出现了,如果原始信息本身就是一个随机数呢?那用任何秘钥解密出来看,也是一个随机数。这时,如果事先不知道这个数字的话,是无法判断解密结果是否“正确”的。这是一个很重要的特性,是后面需要用的。

那现在我们可以这样来操作:

  1. 发送方随机产生两套非对称加密秘钥,然后把这两套秘钥的公钥,通过任何方式发送给接收方。

  2. 接收方收到两个公钥后,首先产生一个随机数,然后可以作出选择。其选择就是从收到的两个公钥之中,选择一个,对自己的随机数加密,把结果返回给发送方。

  3. 发送方收到这个加密结果后,情况有意思了。发送方当然可以用两个私钥对这个结果进行解密,得到两个数字。发送方只知道其中必然有一个是对方生成的随机数,但是并不确定具体是哪一个。那么能做的就是,把得到的两个数字作为提取密码,分别设置到两个网盘上。再通知对方可以去提取文件了。

  4. 接收方用自己的产生的随机数,作为密码去网盘提取文件。接收方应该发现,其中只有一个位置可以提取。那么整个协议完成!

简单分析一下以上步骤,是否符合“1/2不经意传输协议”的三条规则。

第一是:两条信息,接收方只能收到一条,且发送方不知道。那是肯定的,因为接收方没有全部2个私钥,所以他不能知道另一个私钥解密后产生的数字。

第二条是:对发送方来说,获得两条消息中的任何一条的后验概率都是1/2。这也是对的,因为发送方用两个秘钥解密,得到的都是两个像随机数的数字,对发送方来说是无法区分。但这里要注意的是,这里对接收方产生的随机数有所要求的,不能使用明显有规律的数字,比如说“12346”等等。

因为此后当发送方解密时,他发现其中一个数字太有规律了,就能觉察到这是接收方设置的数字,所以这个数字必须是与用任何私钥解密后的格式很像的才行。另外,我之前介绍的步骤其实是稍微简化后的“1/2不经意传输协议”,原版的协议略微复杂些,但没有这个缺陷了。


原版“1/2不经意传输协议”的实现:


第三条规则是:如果发送方试图欺诈,那么接收方可以发现、识破这种企图。那么以上过程中,发送方没有任何欺诈机会。同样接收方也没有任何机会,使得自己能看到两条信息。

那么以上就是1985年,由三位计算机科学家共同提出的“1/2不经意传输协议”,那这个协议思路很巧妙,那么它有没有用呢?真有的,其实这三位科学家在这个协议的基础上,开发了一种“远程合同签署”协议。它可以让不在同一个地方的两个人,安全可靠的签署合同。不会出现一方签署,另一方不签的情况。这个协议下一期介绍,敬请期待。

参考链接:

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.7448&rep=rep1&type=pdf