安全多方计算(1):不经意传输协议
在安全多方计算系列的首篇文章(安全多方计算之前世今生)中,我们提到了百万富翁问题,并提供了百万富翁问题的通俗解法,该通俗解法可按图1简单回顾。
图1 百万富翁问题通俗解法
百万富翁问题通俗解法场景中,我们可以将Alice和Bob的诉求总结如下:
Alice:有9个装有物品的箱子,Bob只能打开其中一个箱子看到物品,看不到其他箱子内的物品。
Bob:不希望Alice知道自己打开的是哪个箱子。
百万富翁问题通俗解法可以通过密码学中的n选1的不经意传输协(Oblivious Transfer,OT)议完美解决。
通过百万富翁问题通俗解法场景描述,对OT协议解决的问题可抽象为:Alice拥有n条消息{m1,…,mn},Bob想知道其中一条消息mi;通过执行OT协议,Bob可以正确获得想要知道的消息mi,无法获得其它n-1条消息,而Alice无法知道Bob获得的是哪条消息。
OT协议按研究类别区分,可以分为以下3种OT协议:
2选1的OT协议(2条消息中正确解密1条)
n选1的OT协议(n条消息中正确解密1条)
OT扩展协议(n条消息中正确解密m条,m<n)
受篇幅所限,本文仅介绍2选1与n选1的OT协议,OT扩展协议则在后续系列文章中进行介绍。
2.1RSA加解密过程简介
RSA密钥参数:N=p*q,L=(p-1)*(q-1)其中p和q为大素数。
RSA公私钥对:生成d和e,满足d与L互质,e与L互质,且d*e mod L=1,则令(d,N)为公钥,e为私钥。
则RSA算法对明文m(m为大整数)的加解密过程如图2所示。
图2 RSA算法加解密计算过程
2.2RSA实现n选1的OT协议过程描述
基于RSA公钥算法实现的n选1的OT协议执行过程如图3所示。
图3 基于RSA公钥算法实现n选1的OT协议执行过程
协议执行过程分为4个步骤:
Alice有n条消息,则产生n个RSA公私钥对,并将n个私钥保留,n个公钥发送给Bob。
Bob随机产生一个大整数key,假定Bob想要获得第t条消息,则Bob用收到的第t个RSA公钥加密大整数key,加密计算结果为s,Bob将s发送给Alice。
Alice用保留的n个RSA私钥,依次解密s,获得n个解密结果,依次为{key1,key2,…,keyt,…,keyn};利用对称加密算法,利用key1~keyn,加密对应的消息m1~mn,得到密文消息M1~Mn,将M1~Mn发送给Bob。
Bob利用自己掌握的大整数key作为密钥,对第t条密文Mt进行对称解密,则得到想要的第t条原始明文消息mt。
2.3n选1的OT协议解决百万富翁问题
将图1中的百万富翁问题和图3中的n选1的OT协议结合,我们可以对图1中的操作步骤做如图4的改造:
Step1:Alice构造9条明文消息,序号<x,消息为“0”;否则消息为“1”。
Step2:Alice与Bob执行9选1的OT协议,解密第7条消息,看到0,y<x;看到1,y≥x。
图4 基于n选1的OT协议实现百万富翁问题
2.4协议分析
该协议执行过程可以满足OT协议中Alice和Bob的核心诉求,关键在于第2步和第3步。
第3步中,Alice利用n个私钥逐个尝试解密s,得到key1~keyn,由于s是由Bob利用第t个公钥加密整数key计算得到的,因此只有keyt=key,但对于Alice来说,key1~keyn都是大整数,根本无法区分哪个才是Bob掌握的key,实现了Bob的诉求,即Alice无法知道Bob选择的是哪条消息。
对于Bob来说,拿到了n个密文消息M1~Mn,但是自己只有一个key,此key只能解密消息Mt,对于其他n-1条消息则无法解密,实现了Alice的诉求,即Bob只能正确得要Bob想要得到1条消息,无法正确得到其他n-1条消息。
如果n=2,则该n选1的OT协议就退化成了2选1的OT协议。
虽然基于RSA实现的n选1的OT协议简单易懂,但是却存在如下缺陷:
key为0或1时,Alice的诉求无法保证。Bob如果将key指定为0或1,则根据图2中RSA的加解密计算方法,无论私钥e是否正确,解密后的m0=m均成立,意味着第3步中,Alice强行解密s得到的key1~keyn均等于key,则Bob可以解密所有的消息,获得所有的明文m1~mn。
协议计算效率有待优化。第1步Alice需要产生n个RSA公私钥对,而RSA公私钥对的产生比较耗时。
为了提高安全性和计算效率,还有基于其他密码学方法的OT协议,如基于离散对数的OT协议,将在本文第四节和第五节中进行介绍。(如果您仅希望简单了解OT协议的原理和能解决的问题,则读到此处足矣,本文后面的内容适合有一定密码学基础读者。)
为了优化OT协议计算效率和安全性,学者一般对2选1的OT协议和n选1的OT协议分开进行研究。对于2选1的OT协议,Tung Chou[2]于2015年基于离散对数问题,在DH密钥协商协议的基础上设计的2选1的OT协议,被认为是一个简单清晰的2选1的OT协议。
3.1离散对数简介
3.2离散对数实现2选1的OT协议过程描述
基于离散对数实现2选1的OT协议执行过程如图5所示。
图5 离散对数实现2选1的OT协议执行过程
Alice有消息m0、m1∈Fp*,则Alice挑选g、a∈Fp*,并计算A=gamod p,将A、g、p发送给Bob。
Bob想要第σ条消息(σ=0或1),Bob挑选b∈Fp*,并计算B=Aσ*gb mod p,将B发送给Alice。
Alice利用a、A、B,按照图4中的步骤3计算C0和C1的值,然后用C0为密钥,对称加密m0;用C1为密钥,对称加密m1。将加密后的密文M0和M1传递给Bob。
Bob利用A和b计算解密密钥gab mod p,对称解密对应的密文后拿到想要的正确消息。
3.3协议分析
该协议的核心步骤是步骤2和步骤3,对这两步中的参数B、C0、C1进行展开,展开后如图6所示。
图6 2选1的OT协议部分参数展开
章节将以Wen-Guey Tzeng[3]提出的高效n选1的OT协议为例,讲解如何基于离散对数实现基本的n选1的OT协议。
4.1离散对数实现n选1的OT协议过程描述
基于离散对数实现n选1的OT协议执行过程如图7所示。
图7 离散对数实现n选1的OT协议执行过程
Alice有n条消息{m1,…,mn},mi∈G(G代表素数域Fp*),挑选G的两个生成元g和h,将g、h、p发送给Bob。
假定Bob想获得第t条消息,则Bob随机选择大整数r∈G,并计算y=gr*htmod p,将y发送给Alice。
Alice利用y、g、h,分别对n条消息,重复执行图6中左下角的计算步骤,每一次执行都会随机选择大整数ki∈G,并结合消息mi计算ai和bi。然后将n组(ai,bi)发送给Bob。
Bob拿到n组(ai,bi)后,利用掌握的大整数r,计算想要的第t条消息mt=bt∕(at)r。
4.2协议分析
图8 消息mx的计算公式展开
参考文献
[1] https://en.wikipedia.org/wiki/Oblivious_transfer
[2] Chou T , Orlandi C . The Simplest Protocol forOblivious Transfer[C]// International Conference on Cryptology and InformationSecurity in Latin America. Springer International Publishing, 2015.
[3] Tzeng W G . Efficient 1-out-of-noblivious transfer schemes with universally usable parameters[J]. IEEETransactions on Computers, 2004, 53(2):p.232-240.
往期回顾
本公众号原创文章仅代表作者观点,不代表绿盟科技立场。所有原创内容版权均属绿盟科技研究通讯。未经授权,严禁任何媒体以及微信公众号复制、转载、摘编或以其他方式使用,转载须注明来自绿盟科技研究通讯并附上本文链接。
关于我们
绿盟科技研究通讯由绿盟科技创新中心负责运营,绿盟科技创新中心是绿盟科技的前沿技术研究部门。包括云安全实验室、安全大数据分析实验室和物联网安全实验室。团队成员由来自清华、北大、哈工大、中科院、北邮等多所重点院校的博士和硕士组成。
绿盟科技创新中心作为“中关村科技园区海淀园博士后工作站分站”的重要培养单位之一,与清华大学进行博士后联合培养,科研成果已涵盖各类国家课题项目、国家专利、国家标准、高水平学术论文、出版专业书籍等。
我们持续探索信息安全领域的前沿学术方向,从实践出发,结合公司资源和先进技术,实现概念级的原型系统,进而交付产品线孵化产品并创造巨大的经济价值。