第十一章：不经意传输

不经意传输

一.不经意传输发展现状

1981 年：Rabin 首次提出不经意传输的概念，该协议中发送方发送秘密消息 m, 接收方以 1/2 概率成功获取该消息。

1985 年：Even 等提出了 2 取 1 不经意传输，协议中发送方有两条秘密消息m1 和 m2, 其中 m1,m2 属于 {0, 1}, 接收方选择并且恢复其中一条消息，发送方无法知道接收方选择了那一条消息。

1986 年：G.Brassard 等人提出了 n 取 1 不经意传输协议，该协议实际上在 2 取 1 上经过加工设计的，该协议通过调用 n 轮 2 取 1 不经意传输协议来实现 n 取 1 不经意传输协议；随后 G.Brassard 等人发现该协议有一些小 Bug, 随后他们又进一步设计了通过调用 log2 的 n 次方 2 取 1 不经意传输协议来实现 n 取 1 的不经意传输协议，从此之后， n 取 1 的不经意传输协议成为了一个重要的研究课题。这个研究课题吸引了越来越多的研究人员加入，有基于这个协议设计增强协议，又基于判定的 Diffie-Hellman 困难问题假设，实现 n 取 1 的不经意传输协议，甚至还有基于同态的，就是没有人考虑 n 取 k 的不经意传输协议的。

1989 年：一群以 Bellare 带头的聪明人提出了一个 n 取 n-1 不经意传输协议，接着 Naor 设计了通过调用 2 取 1 不经意传输协议，实现了一个非平凡的 n 取 k 的不经意传输协议。Naor 又进一步提出具有适应性的不经意传输协议。

自此，不经意传输进入繁荣时代，zhang 提出了高校的 n 取 k 不经意传输协议，chengkangchu 提出了带有自适应和非适应性询问协议，赵春明设计了基于隐藏证书的 n 取 k 不经意传输协议。王风和基于格的不经意传输协议。还有很多优秀的朋友设计了很多优秀的算法 ......

二.不经意传输概念

不经意传输（OT）是通信双方用来传递秘密消息的协议，一般有两个参与方，一方是消息发送方或者说消息持有方，他拥有 n 条秘密消息，另一方是消息接收方，希望获得发送方手中的 k (k < n) 条消息。协议要求接收方应该正确的获取到自己的消息，而发送方并不知道接收方接收了那些消息。

不经意传输协议应满足以下几个条件

正确性：协议执行完毕后，接收方能够收到发送方发过来的加密消息，同时也能正确的解密他所选择的消息。
接收方的隐私性：协议执行完毕后，发送方无法获知接收方选择了那些消息，从而保证了接收方选择的隐秘性。
发送方的隐私性：协议执行完毕后，接收方只能获取到其选择的消息，不会知道他所选择之外的消息。
抗冒名攻击：只有被发送方认可的接收方才能拿到发送方发送的秘密消息
抗重放攻击性：发送方与接收方之前传递的数据被攻击者利用网络手段监听到，攻击者利用通信双方的公共参数以及截取到的数据，无法获知发送方拥有的秘密数据和接收方的具体选择。
抗中间人攻击：攻击者截取通信双方的通信数据，同时冒充接收方与发送方通信获取发送方的秘密消息，同时冒充发送方与接收方防止接收方发现截取而采用其他方式终止协议执行。安全的不经意传输协议需要抵抗这样的攻击。

不经意传输一般可以分为以下几个类别

1. 1 选 1 不经意传输

发送方将秘密消息 M 加密后发送给接收方，发送方无法确认接收方是否成功恢复出秘密消息 M。

2. 2 选 1 不经意传输

发送方将秘密消息 M1 和 M2 加密后发送给接收方，接收方只能成功恢复其中的一个秘密消息 Mi i 属于 {1, 2}, 发送方无法确定接收方恢复的消息是 M1 还是 M2。

3. n 选 1 不经意传输

发送方将 n 个秘密消息 M1，M2，M3 ... Mn 加密后发送给接收方，接收方只能成功恢复其中的一个秘密消息 Mi i 属于 Zn, 发送方无法确定接收方恢复的消息是 M1, M2, M3 ... Mn 中的那一个。

4. n 选 k 不经意传输

发送方将 n 个秘密消息 M1，M2，M3 ... Mn 加密后发送给接收方，接收方只能成功恢复其中的 K 个秘密消息

Ma1, Ma2 ... Mak, a1, ak 属于 {1, n}

发送方无法确定接收 Ma1, Ma2 ... Mak 是 M1，M2，M3 ... Mn 中的哪 K 个。

n 选 k 不经意传输协议具有一般特性，所有我们的整个分享论述都是基于 n 选 k 这种协议算法模式。

三.几种常见的不经意传输算法设计

目前市面上比较流行的 n 选 k 不经意传输协议的设计主有要基于 AES 的不经意传输协议，基于 RSA 的不经意传输协议，基于椭圆曲线的不经意传输协议，基于 IBE 公钥系统的不经意传输，基于 NTRU 的不经意传输和基于匿名验证隐藏证书的不经意传输等。

1.基于 AES 的不经意传输协议

2.基于 RSA 的不经意传输

RSA 加密算法设计的 n 选 K 不经意传输是有 Hung 等设计的，整个协议的执行流程如下：

Alice 拥有 n 个秘密消息 m1, m2, m3 ... mn, 并且同意不经意传输其中的 K 个消息 {mσ1, mσ2, mσ3 ... mσk} 给接收方 Bob, {σ1, σ2 ... σk} ∈ {1, 2 ... n } 为 Bob 的一个选择，同时 Alice 的 RSA 公钥系统公钥为（e, N），解密私钥为 d, Alice 和 Bob 通过以下步骤完成不经意传输协议：

.：

2.1.协议的安全性分析

协议中密文的安全基于 RSA 加密算法的安全，根据前面章节中对 RSA 加密算法的介绍，对于第三方在没有 Alice 解密密钥的前提下，无法通过 Alice 与 Bob 的交互数据中获取到消息 M1 到 Mn。

接收方的隐私保护

根据协议的执行过程以及 RSA 加密算法的安全性，显然只有 Alice 能够计算 .：

但是，Si 是由 Bob 随机选取的，对 Alice 是保密的， Alice 无法根据 Zi 知道 Zi 是由哪个消息计算得来, 因此 Alice 无法获知 Bob 的选择。保证了 Bob 选择的隐私性。

发送方的隐私保护

在这个协议中由于 Bob 没有 Alice 的解密私钥 d, 这里 e = 1 mod Φn，根据 RSA 算法的安全性， Bob 不能通过任一加密密文 .：

获取消息Mi，i=1，2，3，... n；因此 Bob 无法获得其他 n - k 个消息，这是因为 Alice仅仅解密了 k 个秘密消息。

3.基于椭圆曲线的不经意传输

祝孔儒利用椭圆曲线离散对数问题到现在仍然没有找到亚指数的时间级破解优势，结合椭圆曲线离散对数问题构造一种新的不经意传输，整个协议执行流程如下：

初始化阶段

在不经意传输协议的预处理阶段，首先构造一个有限域 Fq, 在有限域 Fq 上面定义椭圆曲线 E，取椭圆曲线上的点 P，M，发送方 Alice 在区间 1, n-1上随机选取整数 p 做为算法的私钥，计算点 K = pM, 其中 K 做为算法的公钥，并且 K 也是椭圆曲线上的点，其坐标在有限域 Fq 上，然后 Alice 把公钥 K 和生成元点 M 发送给接收方 Bob。此时 Bob 随机选择 i ∈ {0,1} 做为自己的选项。

传输阶段

协议按照一下步骤执行

(1）发送方 Alice 将生成元 M 公钥 K 发送给接收方 Bob

(2) 接收方 Bob 在收到 M 和 K 后，执行以下步骤：

随机选择整数 ai ∈ Fq
在区间 [1 , n-1]上随机选择整数 bi
计算点（x1, y1）= biM, (x2, y2) = biK(如果 x2=0, 则重新选择 bi, 直到 x2 不等于 0)
计算 si = ai * x1, 再随机选取密文 s1-i ∈ Fq, 最后将密文对（s0, s1）和 (x1, y1) 发送给 Alice

(3).由于 Alice 知道私钥 p, 因此可以从密文（s0, s1）中计算出明文对（a0, a1),具体的计算过程如下

利用私钥 p 和点（x1, y1）计算 (X2, y2) = p(x1, y1);
令 j = 0,1, 再计算 aj = sj * x2 的 -1 次方，从而得到明文 aj 的信息
令 j = 0,1, 设 cj ^ i = cj xor Lj, 其中 cj 是 Alice 不经意传输的位，Lj 是明文 aj 的最低有效位。
发送 c0 和 c1 给 Bob

(4) Bob 由于知道 aj, 因此可以通过计算 cj 的 i 次方异或 Li 恢复出 ci 的内容，具体执行过程如下： .：

由上图的执行过程可以知道，如果接受方是诚实的参与者，则无法猜到明文 a1-i, 原因是离散对数学的难解性。他保证接收者即使在知道密文的前提下，点(x1, y1)、M 和 K 也不能在多项式时间内计算出 b1-i 和 b1-i * K 的值，这说明了接收方只能得到位而无法计算出有关 c1-i 的值。此外，对于发送方来说，密文对（s0, s1）是完全等价的，并且根本无法知道接收方选择了 c0 还是 c1。

综合以上分析可以得知，如果协议的参与方都严格按照协议的步骤执行，那么上述协议就可以将位 c0 和 c1 从发送方不经意地传输给接收方。

4.基于 IBE 公钥系统的不经意传输

本小节将要介绍的是以 Boneh 设计的基于身份加密系统为基础构造了一个n 取 k 不经意传输协议，同时给出了协议的正确性、安全性分析，以及协议执行效率分析。

5.基于匿名验证隐藏证书的不经意传输

6.基于 NTRU 的不经意传输

四.不经意传输的应用

MPC 中的一种协议，主要用于数据的隐私保护。

五.总结

不经意传输协议，一种具有隐私保护功能的通信协议，能使通信双方以一种选择模糊化的方式在彼此之间传送消息。OT是密码学的一个基本协议，他使得服务的接收方以不经意的方式得到服务发送方输入的某些消息，这样就可以保护接收者的隐私不被发送者所知道，同时接收者也不知道发送者具体发送了什么消息。