一、前言
在安全多方计算系列的首篇文章（安全多方计算之前世今生）中，我们提到了百万富翁问题，并提供了百万富翁问题的通俗解法，该通俗解法可按图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扩展协议则在后续系列文章中进行介绍。
二、利用RSA加密实现n选1的OT协议
自1981年提出以来，OT协议有多种多样的实现形式，其中最容易理解的是基于RSA公钥算法实现的n选1的OT协议[1]。
2.1RSA加解密过程简介
此处不讲解RSA原理，只介绍RSA加解密过程和用到的参数，便于密码学知识储备不足的读者理解后面的OT协议。
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协议的原理和能解决的问题，则读到此处足矣，本文后面的内容适合有一定密码学基础读者。）
三、基于离散对数实现2选1的OT协议
为了优化OT协议计算效率和安全性，学者一般对2选1的OT协议和n选1的OT协议分开进行研究。对于2选1的OT协议，Tung Chou[2]于2015年基于离散对数问题，在DH密钥协商协议的基础上设计的2选1的OT协议，被认为是一个简单清晰的2选1的OT协议。
3.1离散对数简介
离散对数问题通俗理解：有限域Fp*（p为大素数，Fp*中元素共p-1个整数，取值1~p-1）上大整数的幂乘取模容易计算（ab mod p=>c，a、b∈Fp*），而对数计算困难( log a c=>b)。
3.2离散对数实现2选1的OT协议过程描述
基于离散对数实现2选1的OT协议执行过程如图5所示。
图5 离散对数实现2选1的OT协议执行过程
协议执行过程分为4个步骤：
- 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协议部分参数展开
从图6的展开式可知，无论σ=0还是σ=1，C0和C1始终只有一个为gab，而另一个对于Bob而言则不可计算（Bob不知道a的值），gab的计算实质上就是DH密钥协商协议。
对于Alice来说，仅知道B、A、g，不知道b的情况下，由于离散对数问题难解，因此是无法推断出σ=0还是σ=1。
与2.2的协议相比，该协议不存在Bob选择特殊的b会导致密文消息M0和M1同时正确解密这一缺陷。
四、基于离散对数实现n选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协议执行过程
协议执行过程分为4个步骤：
- 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协议分析
对于第4步Bob的操作，我们把消息mt泛指为mx，则对mx的计算公式展开后如图8所示。
图8 消息mx的计算公式展开
从图8可以看出，要想获得消息mx，要么令x=t，此时消息为Bob想要获得的消息；要么计算出h(t-x)*kx，由于kx是Alice的秘密数字，因此保证了Bob不可能正确解密除消息mt之外的其余n-1条消息。
对于Alice来说，虽然知道y、g、h，但是不知道r的情况下，由于离散对数问题难解，因此是无法推断出t的正确值。
与2.2的协议相比，该协议不存在Bob选择特殊的r会导致n条消息同时正确解密这一缺陷，同时也不存在需要产生n对公私钥这一耗时操作。
五、总结
本文介绍了OT协议和3个基于密码学实现的OT协议实例，并结合百万富翁问题的通俗解法看到了OT协议的应用实例，这样的实例很难看出OT协议的重要性。
其实OT协议是安全多方计算中很重要的一个协议，在安全多方计算系列的首篇文章（安全多方计算之前世今生）中，我们提到，安全多方计算的通用技术路线可以用混淆电路解决，而混淆电路的构建离不开OT协议。因此，下期文章将会讲解如何通过OT协议实现混淆电路，以及如何实现基于混淆电路的通用安全多方计算路线。
参考文献
[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.
