随着物联网以及移动互联网的快速发展, 全球数据量呈指数级增长, 大数据时代已经到来.在大数据产业蓬勃发展的同时, 个人隐私数据泄露事件层出不穷, 引起了人们的广泛关注.确保数据安全性、设计安全实用的多方协议成为亟待解决的问题.不经意传输(oblivious transfer)作为许多典型安全协议的核心基本工具, 无论是在理论研究还是在应用研究中都担任了重要角色.

不经意传输是一个两方传输任务.其中一个参与方称为发送方, 提供多个字符串; 另一个参与方称为接收方, 提供一个索引以选取其中1个或多个.任务执行完成后, 接收方获得其索引所对应的字符串, 对其他字符串一无所知; 发送方没有输出, 且不知道接收方获得了哪些字符串.自Rabin在1981年提出不经意传输以来^[1], 针对该领域的研究就受到了密码学研究者的广泛关注.在后续的研究中, 有很多工作重点关注设计更高效或更安全的不经意传输协议^[2-6].另外, 也有很多工作提出了功能性更强的不经意传输变种, 用来增强调用不经意传输的外层协议的安全性或提高协议效率, 如承诺不经意传输^{[7, 8]}、不经意传输扩展^[9-11]等.值得注意的是, Lindell等人在TCC 2011会议上提出了cut-and-choose不经意传输^[12], 将其应用在基于混乱电路和cut-and-choose技术的安全两方计算协议中, 高效地解决了Kiraz等人指出的选择性失败攻击问题^[13].然而, 该变种仅能用来传输单个参与方的混乱密钥.为了传输另一个参与方的混乱密钥以完成混乱电路检测和计算, 协议还需要参与方进行多轮交互.显然, 基于该原语的协议交互复杂度过高.

受cut-and-choose不经意传输的启发, 本文提出cut-and-choose双向不经意传输这一新原语.与cut-and-choose不经意传输相比, 新原语具有更强大的功能, 可以在安全两方计算中一次性传输两个参与方的所有相关密钥.除了能够解决选择性失败攻击问题以外, 该原语还具有以下3个优势:

(1)降低外层协议的交互轮数, 这在协议双方交互受限的场景中是非常关键的;

(2)更具模块化、更清晰地描述协议过程, 使协议更易于理解和分析;

(3)可用于其他cut-and-choose场景中, 其本身具有独立的研究意义.

基于同态加密, 本文构造出仅需1轮交互的cut-and-choose双向不经意传输协议, 并基于标准的安全性定义, 在半诚实模型下形式化证明该协议的安全性.

本文第1节回顾一些预备知识.第2节给出新原语cut-and-choose双向不经意传输的功能函数定义, 并基于同态加密构造具体协议, 在半诚实模型下给出严格的安全性证明.第3节阐述该原语在基于cut-and-choose技术的安全两方计算中的应用.第4节总结全文, 并展望后续的研究工作.

1 预备知识

本节介绍相关预备知识, 包括不经意传输、cut-and-choose不经意传输、同态加密方案以及半诚实模型下的安全性定义.

1.1 不经意传输

一个标准的2取1不经意传输是一个两方功能函数, 其中一个参与方称为发送方S, 输入为两个n比特字符串y₀, y₁, 另一个参与方称为接收方R, 输入为一个选择比特τ∈{0, 1}.该任务执行完成后, R获得y_τ, 而对y_1-τ一无所知; S没有输出, 且不知道R获得了y₀, y₁中的哪一个.这些性质可以由下面的功能函数ℱ_ot给出.

功能函数ℱ_ot.

输入:

    --S输入y₀, y₁∈{0, 1}ⁿ.

    --R输入τ∈{0, 1}.

输出:

    --S输出⊥(表示为空).

    --R输出y_τ.

1.2 Cut-and-Choose不经意传输

Lindell等人提出的cut-and-choose不经意传输是在2取1不经意传输的基础上, 为R引入一个cut-and-choose指示比特j, 以便让R选择是要获得S的所有两个输入值, 还是只需要获得其中一个.我们将Lindell等人提出的该原语做了适当简化, 将其写成下面的功能函数ℱ_ccot以便表述.

功能函数ℱ_ccot.

输入:

    --S输入y₀, y₁∈{0, 1}ⁿ.

    --R输入(j, τ), 其中j∈{0, 1}为cut-and-choose指示比特, τ∈{0, 1}为R的选择比特.

输出:

    --S输出⊥.

    --R输出z:

      当j=1时, z为(y₀, y₁);

      当j=0时, z为y_τ.

1.3 同态加密方案

记某公钥加密方案为M=(Gen, Enc, Dec), 其中, Gen表示密钥生成算法, Enc表示加密算法, Dec表示解密算法.将使用公钥pk对明文m的加密记为Enc_pk(m).直观上, 给定两个密文c₁=Enc_pk(m₁)和c₂=Enc_pk(m₂), 若在不知道对应私钥和明文的前提下可以高效计算c₁·c₂满足c₁·c₂=Enc_pk(m₁+m₂), 则称该公钥加密方案具有加法同态性.这里要求计算c₁·c₂的结果是对m₁+m₂的一次随机加密.正式地, 有如下定义:

定义1(加法同态加密).对于一个公钥加密方案M=(Gen, Enc, Dec), 如果对于任意的n, 任意Gen(1ⁿ)的输出(pk, sk), 满足:

{pk, c₁=Enc_pk(m₁), c₁·Enc_pk(m₂)}≅{pk, Enc_pk(m₁), Enc_pk(m₁+m₂)},

其中, 等号≅表示计算不可区分, 则M是一个加法同态加密方案.

1.4 安全性定义

不经意传输作为一类具体的安全两方计算问题, 其安全性可由安全两方计算的标准安全模型来定义.本文使用半诚实模型下的安全性定义^[14]来刻画所构造的cut-and-choose双向不经意传输协议的安全性.

定义2(半诚实模型下的安全性).令f(·, ·)=(f₁, f₂)为任意{0, 1}×{0, 1}→{0, 1}×{0, 1}多项式时间功能函数, π为一个计算f(·, ·)的两方协议.给定输入(x, y)(参与方P₁的输入为x, P₂的输入为y)和安全参数n, P_i(i∈{1, 2})在协议π中的视图记为view_i^π(x, y, n)=(w, rⁱ, m₁ⁱ, …, m_tⁱ), 其中, w∈{x, y}, rⁱ为P_i的内部随机带, m_jⁱ为P_i接收到的第j条消息; P_i的输出记为output_i^π(x, y, n).另外, 记双方的联合输出为output^π(x, y, n)=(output₁^π(x, y, n), output₂^π(x, y, n)).

如果下列条件满足, 则协议π在半诚实模型下安全计算功能函数f(·, ·).

首先, 要求满足正确性, 即满足:

{output^π(x, y, n)}_{x, y, n}≅{f(x, y)}_{x, y}.

其次, 要求存在概率多项式时间算法$\mathcal{S}$₁和$\mathcal{S}$₂, 满足:

{$\mathcal{S}$₁(1ⁿ, x, f₁(x, y))}_{x, y, n}≅{view₁^π(x, y, n)}_{x, y, n},

{$\mathcal{S}$₂(1ⁿ, y, f₂(x, y))}_{x, y, n}≅{view₂^π(x, y, n)}_{x, y, n},

其中, x, y∈{0, 1}, 满足|x|=|y|, n∈ℕ.

2 Cut-and-Choose双向不经意传输

这一节首先介绍并形式化定义cut-and-choose双向不经意传输功能函数, 然后基于同态加密给出其协议构造, 并形式化证明该协议满足半诚实模型下的标准安全性定义(定义2).

2.1 功能函数

我们说标准的不经意传输和cut-and-choose不经意传输实现的功能都是单向的.也就是说, S输入两个值等待R进行选择, 而其本身并没有主动选择权.如果在cut-and-choose不经意传输的基础上, 为S增加两个字符串x₀和x₁, 使其能够通过一个新的选择比特σ对R接收到这两个字符串中的哪一个拥有决定权, 就构成了cut-and-choose双向不经意传输.当然, 增加的这两个字符串被R接收到1个还是2个, 依然由R的cut-and-choose指示比特j来决定.需要注意的是, 引入选择比特σ会带来以下问题:当j为0时, R必须知道x₀和x₁这两个值应该获得哪一个.如果按照正常顺序x₀, x₁发送这两个值, 则R可以获得σ的值, 这与σ需要保密相矛盾.因此, 需要引入一个置换比特b来对x₀和x₁的位置进行随机置换, 从而达到隐藏σ的目的.这样, R就可以在不知道σ的情况下获得x_σ.置换比特的引入会对接收方的输出造成影响:当cut-and-choose指示比特j为1时, 接收方除了获得被置换位置后的两个字符串x_b, x_1-b之外, 还需要拿到b的值, 以获得正常顺序的x₀, x₁; 当cut-and-choose指示比特j为0时, 接收方除了获得由发送方指定应该获得的x_σ之外, 实际上也获得了x_σ的位置信息σ⊕b, 即当获得x_b, x_1-b中的第1个时, 说明σ⊕b为0, 反之则说明σ⊕b为1.该功能可以由下面的功能函数ℱ_ccbot给出.

功能函数ℱ_ccbot.

输入:

    --S输入(x₀, x₁, y₀, y₁, b, σ), 其中x₀, x₁, y₀, y₁∈{0, 1}ⁿ, b∈{0, 1}为置换比特, σ∈{0, 1}为S的选择比特.

    --R输入(j, τ), 其中j∈{0, 1}为cut-and-choose指示比特, τ∈{0, 1}为R的选择比特.

输出:

    --S输出⊥.

    --R输出z:

      当j=1时, z为(x_b, x_1-b, 1-b, y₀, y₁);

      当j=0时, z为(x_σ, y_τ, σ⊕b), 其中σ⊕b指示x_σ的位置信息.

2.2 协议构造

Cut-and-choose双向不经意传输可以基于同态加密构造.主要思想是利用加密方案的同态性, 将接收方cut-and-choose指示比特的密文与发送方的输入进行特定运算.具体构造请见协议1.

协议1. Cut-and-Choose双向不经意传输协议.

输入:发送方S输入(x₀, x₁, y₀, y₁, b, σ); 接收方R输入(j, τ)).

辅助输入:安全参数1ⁿ; 满足定义1的选择明文攻击(CPA)安全的加法同态加密方案M=(Gen, Enc, Dec).

协议过程:

步骤1. R将τ编码为两个比特τ₀τ₁, 其中τ_τ=1, τ_1-τ=0.具体来说, 如果τ=1, 则编码为τ₀τ₁=01;如果τ=0, 则编码为τ₀τ₁=10.另外, R将j编码为两个比特j₀j₁=j0.然后, R生成一组密钥(pk, sk)←Gen(1ⁿ), 公开公钥pk, 并用pk对(j₀, j_τ0+τ₀, j_τ1+τ₁)进行加密, 将加密后得到的密文三元组(Enc_pk(j₀), Enc_pk(j_τ0+τ₀), Enc_pk(j_τ1+τ₁))发送给S.

步骤2. S将σ编码为两个比特σ₀σ₁, 其中σ_σ=1, σ_1-σ=0.具体来说, 如果σ=1, 则编码为σ₀σ₁=01;如果σ=0, 则编码为σ₀σ₁=10.然后, S利用R的公钥pk计算(Enc_pk(j₁), Enc_pk(σ₀), Enc_pk(σ₁), Enc_pk(b)), 并计算密文五元组:

$\begin{array}{c} {w_b} = {(En{c_{pk}}({j_{{\sigma _b}}}) \cdot En{c_{pk}}({\sigma _b}))^{{x_b}}},\\ {w_{1 - b}} = {(En{c_{pk}}({j_{{\sigma _{1 - b}}}}) \cdot En{c_{pk}}({\sigma _{1 - b}}))^{{x_{1 - b}}}},\\ {w_2} = {(En{c_{pk}}({j_b}) \cdot En{c_{pk}}(b))^{1 - b}},\\ {w_3} = {(En{c_{pk}}({j_{{\tau _0}}} + {\tau _0}))^{{y_0}}},\\ {w_4} = {(En{c_{pk}}({j_{{\tau _1}}} + {\tau _1}))^{{y_1}}}. \end{array}$

计算完成后, 将密文五元组(w_b, w_1-b, w₂, w₃, w₄)发送给R.

步骤3. R用私钥sk对接收到的密文五元组进行解密, 得到明文五元组(u_b, u_1-b, u₂, u₃, u₄):

·当j=1时, 令(u_b, u_1-b, u₂, u₃, u₄)=(x_b, x_1-b, 1-b, y₀, y₁);

·当j=0时, 忽略u₂的值, 令u_b, u_1-b中不为0的值为x_σ, 即u_b, u_1-b中的第σ⊕b+1个; 令u₃, u₄中的第τ+1个为y_τ, 得到输出(x_σ, y_τ, σ⊕b).

2.3 安全性证明

定理1.假定M=(Gen, Enc, Dec)是一个满足定义1的CPA安全的加法同态加密方案, 则协议1在定义2下安全计算功能函数ℱ_ccbot.

证明:令ℱ_ccbot为cut-and-choose双向不经意传输功能函数, π为计算ℱ_ccbot的协议1, 根据定义2, 如果下列条件满足, 我们就说协议π在半诚实模型下安全计算ℱ_ccbot.

首先满足正确性, 即

{output^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}_{x0, x1, y0, y1, b, σ, j, τ, n}≅{ℱ_ccbot((x₀, x₁, y₀, y₁, b, σ), (j, τ))}_{x0, x1, y0, y1, b, σ, j, τ}.

其次, 存在概率多项式时间算法$\mathcal{S}$₁和$\mathcal{S}$₂满足:

${\{ {{\cal S}_1}({1^n},({x_0},{x_1},{y_0},{y_1},b,\sigma ))\} _{{x_0},{x_1},{y_0},{y_1},b,\sigma ,n}} \cong {\{ vie{w_1}^\pi (({x_0},{x_1},{y_0},{y_1},b,\sigma ),\left( {j,\tau } \right),n)\} _{{x_0},{x_1},{y_0},{y_1},b,\sigma ,j,\tau ,n}}$

(1)

${\{ {{\cal S}_2}({1^n},(j,\tau ,z))\} _j}_{,\tau ,z,n} \cong {\{ vie{w_2}^\pi (({x_0},{x_1},{y_0},{y_1},b,\sigma ),\left( {j,\tau } \right),n)\} _{{x_0},{x_1},{y_0},{y_1},b,\sigma ,j,\tau ,n}}$

(2)

其中, x₀, x₁, y₀, y₁∈{0, 1}ⁿ, z∈{0, 1}, b, σ, j, τ∈{0, 1}, n∈ℕ.

下面我们对协议1的安全性给出形式化证明.

首先, 根据cut-and-choose指示比特j的取值分两种情况对协议1的正确性进行证明.

情况1)当j=1时, ℱ_ccbot((x₀, x₁, y₀, y₁, b, σ), (j, τ))的输出为(x_b, x_1-b, 1-b, y₀, y₁), 我们证明在此情况下, 协议1的输出也是如此.

在协议1中, 当j=1时, j₀=1, j₁=0, 有j_b+b=1, b∈{0, 1}, 所以,

$\begin{array}{c} {w_b} = {(En{c_{pk}}({j_{{\sigma _b}}}) \cdot En{c_{pk}}({\sigma _b}))^{{x_b}}} = En{c_{pk}}({x_b} \cdot ({j_{{\sigma _b}}} + {\sigma _b})) = En{c_{pk}}({x_b}),\\ {w_{1 - b}} = {(En{c_{pk}}({j_{{\sigma _{1 - b}}}}) \cdot En{c_{pk}}({\sigma _{1 - b}}))^{{x_{1 - b}}}} = En{c_{pk}}({x_{1 - b}} \cdot ({j_{{\sigma _{1 - b}}}} + {\sigma _{1 - b}})) = En{c_{pk}}({x_{1 - b}}),\\ {w_2} = {(En{c_{pk}}({j_b}) \cdot En{c_{pk}}(b))^{1 - b}} = En{c_{pk}}((1 - b) \cdot ({j_b} + b)) = En{c_{pk}}(1 - b),\\ {w_3} = {(En{c_{pk}}({j_{{\tau _0}}} + {\tau _0}))^{{y_0}}} = En{c_{pk}}({y_0} \cdot ({j_{{\tau _0}}} + {\tau _0})) = En{c_{pk}}({y_0}),\\ {w_4} = {(En{c_{pk}}({j_{{\tau _1}}} + {\tau _1}))^{{y_1}}} = En{c_{pk}}({y_1} \cdot ({j_{{\tau _1}}} + {\tau _1})) = En{c_{pk}}({y_1}). \end{array}$

这样, 对(w_b, w_1-b, w₂, w₃, w₄)解密得到的明文为(x_b, x_1-b, 1-b, y₀, y₁).

因此, 当j=1时, 协议1的输出为(x_b, x_1-b, 1-b, y₀, y₁), 满足正确性要求.

情况2)当j=0时, ℱ_ccbot((x₀, x₁, y₀, y₁, b, σ), (j, t))的输出为(x_σ, y_τ, σ⊕b), 我们证明在此情况下, 协议1的输出也是如此.

在协议1中, 当j=0时, j₀=0, j₁=0, 有j_b+b=b, b∈{0, 1}, 所以,

$\begin{array}{c} {w_b} = {(En{c_{pk}}({j_{{\sigma _b}}}) \cdot En{c_{pk}}({\sigma _b}))^{{x_b}}} = En{c_{pk}}({x_b} \cdot ({j_{{\sigma _b}}} + {\sigma _b})) = En{c_{pk}}({x_b} \cdot {\sigma _b}),\\ {w_{1 - b}} = {(En{c_{pk}}({j_{{\sigma _{1 - b}}}}) \cdot En{c_{pk}}({\sigma _{1 - b}}))^{{x_{1 - b}}}} = En{c_{pk}}({x_{1 - b}} \cdot ({j_{{\sigma _{1 - b}}}} + {\sigma _{1 - b}})) = En{c_{pk}}({x_{1 - b}} \cdot {\sigma _{1 - b}}),\\ {w_2} = {(En{c_{pk}}({j_b}) \cdot En{c_{pk}}(b))^{1 - b}} = En{c_{pk}}((1 - b) \cdot ({j_b} + b)) = En{c_{pk}}((1 - b) \cdot b) = En{c_{pk}}(0),\\ {w_3} = {(En{c_{pk}}({j_{{\tau _0}}} + {\tau _0}))^{{y_0}}} = En{c_{pk}}({y_0} \cdot ({j_{{\tau _0}}} + {\tau _0})) = En{c_{pk}}({y_0} \cdot {\tau _0}),\\ {w_4} = {(En{c_{pk}}({j_{{\tau _1}}} + {\tau _1}))^{{y_1}}} = En{c_{pk}}({y_1} \cdot ({j_{{\tau _1}}} + {\tau _1})) = En{c_{pk}}({y_1} \cdot {\tau _1}). \end{array}$

可以看到, 当j=0时, 无论b取何值, w₂都是对0的加密.根据协议, 我们忽略这一项, 分别对w_b, w_1-b和w₃, w₄进行处理.对w_b, w_1-b, 由于σ_σ=1, σ_1-σ=0, 所以在对w_b, w_1-b解密得到的明文中, 一个为0, 一个为x_σ, 其中x_σ的位置信息为σ⊕b.具体来说, 若σ=1, 则σ₁=1, σ₀=0, 对w_b, w_1-b解密可得到0和x₁(顺序不定, x₁的位置信息为σ⊕b=1⊕b); 若σ=0, 则σ₀=1, σ₁=0, 对w_b, w_1-b解密可得到0和x₀(顺序不定, x₀的位置信息为σ⊕b=0⊕b).对w₃, w₄, 由于τ_τ=1, τ_1-τ=0, 所以在对w₃, w₄解密得到的明文中, 一个为y_τ, 一个为0, 其中y_τ的位置由τ直接确定.

因此, 当j=0时, 协议1的输出为(x_σ, y_τ, σ⊕b), 满足正确性要求.

综上所述, 有{output^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}_{x0, x1, y0, y1, b, σ, j, τ, n}≅{ℱ_ccbot((x₀, x₁, y₀, y₁, b, σ), (j, τ))}_{x0, x1, y0, y1, b, σ, j, τ}.

下面我们分别证明等式(1)和等式(2)成立.

情况1) S被腐化, 证明等式(1)成立.

为了证明S被腐化时等式(1)成立, 我们需要构造一个模拟器$\mathcal{S}$₁, 给定输入(x₀, x₁, y₀, y₁, b, σ)和安全参数1ⁿ, 输出S在协议1中的视图, 并证明该视图和真实协议执行中S的视图view₁^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)计算不可区分.

根据协议1, S所能看到的视图消息仅为密文(Enc_pk(j₀), Enc_pk(j_τ0+τ₀), Enc_pk(j_τ1+τ₁)).为了模拟该消息, 我们令模拟器$\mathcal{S}$₁在明文空间随机选取明文m₁, m₂, m₃, 使用R的公钥pk进行加密, 得到密文(Enc_pk(m₁), Enc_pk(m₂), Enc_pk(m₃)).这样, 给定输入(1ⁿ, (x₀, x₁, y₀, y₁, b, σ)), 模拟器$\mathcal{S}$₁的输出为

(x₀, x₁, y₀, y₁, b, σ, r, Enc_pk(m₁), Enc_pk(m₂), Enc_pk(m₃)),

其中, r为协议过程中使用的随机数.

以上即是模拟器$\mathcal{S}$₁的构造.我们接下来证明等式(1)成立, 即

{$\mathcal{S}$₁(1ⁿ, (x₀, x₁, y₀, y₁, b, σ))}_{x0, x1, y0, y1, b, σ, τ, n}≅{view₁^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}_{x0, x1, y0, y1, b, σ, j, τ, n}.

由模拟器$\mathcal{S}$₁的构造可知, {$\mathcal{S}$₁(1ⁿ, (x₀, x₁, y₀, y₁, b, σ))}={(x₀, x₁, y₀, y₁, b, σ, r, Enc_pk(m₁), Enc_pk(m₂), Enc_pk(m₃))}.

由协议1可知, {view₁^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}={(x₀, x₁, y₀, y₁, b, σ, r, Enc_pk(j₀), Enc_pk(j_τ0+τ₀), Enc_pk(j_τ1+τ₁))}.

我们利用规约来证明上述两个分布不可区分.假如存在一个非均匀概率多项式时间区分器D和一个多项式p(·), 满足对于无限多n, 有:

|Pr[D($\mathcal{S}$₁(1ⁿ, (x₀, x₁, y₀, y₁, b, σ)))=1]-Pr[D(view₁^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n))=1| > 1∕p(n),

则存在一个敌手$\mathcal{A}$_M, 满足:

|Pr[$\mathcal{A}$_M(Enc_pk(m₁), Enc_pk(m₂), Enc_pk(m₃))=1]-Pr[$\mathcal{A}$_M(Enc_pk(j₀), Enc_pk(j_τ0+τ₀), Enc_pk(j_τ1+τ₁))=1| > 1∕p(n).

我们知道, 如果公钥加密方案M满足CPA下的不可区分性, 则M在CPA下是不可区分多重加密.因此, 若存在敌手$\mathcal{A}$_M能够区分上述两个多重加密消息序列, 则其能够攻破加密方案M, 即M不具有CPA安全性, 这和我们的假设相矛盾.因此, 等式(1)成立, 协议1在参与方S被腐化时是安全的.

情况2) R被腐化, 证明等式(2)成立.

为了证明R被腐化时等式(2)成立, 我们需要构造一个模拟器$\mathcal{S}$₂, 给定输入(j, τ, z)和安全参数1ⁿ, 输出R在协议1中的视图, 并证明该视图和真实协议执行中R的视图view₂^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)计算不可区分.

根据协议1, R所能看到的消息为S发送的密文五元组(w_b, w_1-b, w₂, w₃, w₄).由于cut-and-choose指示比特j取值不同时, 由该密文五元组解密得到的输出结果不同, 因此需要分情况进行讨论.

情况(1)当j=1时, R解密密文得到的结果为z=(x_b, x_1-b, 1-b, y₀, y₁).给定z的值, 模拟器$\mathcal{S}$₂可以直接用R的公钥pk对(x_b, x_1-b, 1-b, y₀, y₁)进行加密, 得到密文五元组(w_b', w_1-b', w₂', w₃', w₄'), 作为对真实协议执行中(w_b, w_1-b, w₂, w₃, w₄)的模拟.

以上即是模拟器$\mathcal{S}$₂在j=1时的构造.我们接下来证明在该情况下, 等式(2)成立, 即

{$\mathcal{S}$₂(1ⁿ, (j, τ, z))}_{j, τ, z, n}≅{view₂^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}_{x0, x1, y0, y1, b, σ, j, τ, n}.

由模拟器$\mathcal{S}$₂的构造可知, {$\mathcal{S}$₂(1ⁿ, (j, τ, z))}={(j, τ, r, w_b', w_1-b', w₂', w₃', w₄')}.

由协议1可知, {view₂^π((x₀, x₁, y₀, y₁, b, σ), (j, τ), n)}={(j, τ, r, w_b, w_1-b, w₂, w₃, w₄)}.

由于R掌握私钥sk, 因此(w_b', w_1-b', w₂', w₃', w₄')和(w_b, w_1-b, w₂, w₃, w₄)在R看来都是对(x_b, x_1-b, 1-b, y₀, y₁)的加密.也就是说, 上述两个分布对R来说是等同的.因此, 等式(2)在j=1时成立.

情况(2)当j=0时, R解密密文得到的结果为z=(x_σ, y_τ, σ⊕b).给定(j, τ, z)的值, 模拟器$\mathcal{S}$₂可以如下构造R的视图:

对(w_b, w_1-b, w₂, w₃, w₄)中前两个元素w_b和w_1-b, $\mathcal{S}$₂用pk加密x_σ作为对其中第σ⊕b+1个元素的模拟, 用pk加密0作为对另一个元素的模拟; 对第3个元素w₂, $\mathcal{S}$₂用pk加密0作为对w₂的模拟; 对最后两个元素w₃和w₄, $\mathcal{S}$₂用pk加密y_τ作为对其中第τ+1个元素的模拟, 用pk加密0作为对另一个元素的模拟.

以上即是模拟器$\mathcal{S}$₂在j=0时的构造.在掌握私钥sk的R看来, 上述构造的密文和真实协议执行中接收到的密文(w_b, w_1-b, w₂, w₃, w₄)具有等同的分布.因此, 等式(2)在j=0时成立.

这样就完成了R被腐化时的证明.协议1在参与方R被腐化时是安全的.

综上, 协议1在定义2下安全计算功能函数ℱ_ccbot.

3 应用

Cut-and-choose双向不经意传输在基于cut-and-choose技术的密码协议中具有重要意义.本文以安全两方计算为例, 对其应用及所带来的优势进行阐述.在详细介绍如何将cut-and-choose双向不经意传输应用到安全两方计算之前, 首先简单介绍基于Yao混乱电路的安全两方计算协议以及cut-and-choose范例.

安全两方计算是参与方P₁和P₂之间的交互式计算任务.双方各自持有自己的秘密输入x和y, 互不信任, 交互式地协同计算一个目标函数f(·, ·).任务完成后, 双方各自获得相应的秘密输出, 整个计算过程不泄露其他任何额外信息.20世纪80年代, 姚期智先生提出采用“混乱电路”的方法来实现安全两方计算^[15].混乱电路实际上是对布尔电路的一种加密形式, 其拥有如下性质:

(1)每条电路线对应两个混乱密钥, 一个密钥对应比特0, 另一个密钥对应比特1;

(2)当每条电路输入线给定一个密钥时, 可以逐层计算该混乱电路, 并最终获得电路输出值, 除此之外得不到其他任何额外信息.

基于混乱电路和不经意传输, 文献[15]给出了安全两方计算的第1个通用解决方案--Yao协议.在该协议中, P₁和P₂分别为混乱电路构造方和混乱电路计算方.双方首先将要计算的函数表示为布尔电路, 参与方输入的每一比特在布尔电路中都有对应的电路输入线.然后, P₁独立构造该布尔电路对应的混乱电路, 并将该混乱电路以及对应自己输入的密钥发送给P₂.对P₂输入所对应的每条输入线, 双方执行一次不经意传输协议, 使P₂获取自己输入对应的密钥.具体来说, P₁作为发送方, 输入为该条输入线上的两个密钥; P₂作为接收方, 输入为该条输入线对应的输入比特.协议执行完成后, P₂获得其输入比特对应的密钥.最后, P₂使用已获得的所有电路输入线上的密钥, 在不知道P₁秘密输入和其他额外信息的情况下, 茫然地对混乱电路逐层计算, 获得电路的输出值.

Yao协议非常高效, 但其仅在半诚实模型下安全.在恶意模型下, 潜在的恶意参与方可以任意偏离协议执行, 协议构造更加困难, 也更低效.一个显然的问题是, 恶意的P₁可能会构造错误的混乱电路, 使P₂计算出的函数结果出错.与利用零知识证明强迫潜在的恶意敌手诚实地执行协议相比, 使用cut-and-choose技术可以获得恶意模型下非常高效的安全两方计算协议^{[12, 16, 17]}.该技术的基本想法是使参与方P₂能够以很高的概率发现恶意P₁的作弊行为.首先, P₁被要求构造s份混乱电路而不是1份(s为统计学安全参数).P₂随机选择其中一部分(称为检测电路), 要求P₁打开, 以检测混乱电路是否正确构造; 若全部检测通过, 则以很高的概率说明剩余混乱电路中的大多数都是正确构造的.随后, 双方像Yao协议一样计算剩余的每个混乱电路(称为计算电路), 并取计算结果中占大多数的值作为协议输出.通过这种方法, 恶意构造方作弊成功的概率被限制得非常小.

在所有基于cut-and-choose范例的两方计算协议中, 文献[12]提供的解决方案较为典型、高效.该协议主要基于cut-and-choose不经意传输进行构造.注意到该功能函数仅能用来传输单个混乱电路中单条P₂输入线上的密钥.为了使其能够适用于外层的两方计算协议, 需要将其扩展为一个可以进行批处理的版本, 称为批处理单选择cut-and-choose不经意传输, 记为ℱ$_{ccbot}^{B,S}{\rm{,}}$以用来传输s个混乱电路中所有P₂输入线上的密钥.关于ℱ$_{ccbot}^{B,S}$的详细描述可参见文献[12].基于cut-and-choose不经意传输, 我们可以获得如下的安全两方计算协议框架.

基于Cut-and-Choose不经意传输的安全两方计算协议框架.

步骤1. P₁构造s份混乱电路.

步骤2.双方调用批处理单选择cut-and-choose不经意传输功能函数ℱ$_{ccbot}^{B,S}.$对于所有混乱电路中每条P₂输

入线:在检测电路中, P₂获得全部两个密钥; 在计算电路中, P₂获得与其输入比特相对应的密钥.

步骤3. P₁将所有混乱电路发送给P₂.

步骤4. P₂公开ℱ$_{ccbot}^{B,S}$中用到的cut-and-choose指示比特串J, 并向P₁证明J的正确性.

步骤5.对每个检测电路, P₁发送自己每条输入线上的两个密钥.

步骤6. P₂对所有检测电路进行检测.若检测出现问题, 则P₂中止协议; 否则继续执行.

步骤7.对每个计算电路, P₁将自己输入对应的密钥发送给P₂, 并证明在所有计算电路中, P₁输入一致.

步骤8. P₂对所有计算电路进行计算, 并取计算结果中占大多数的值作为协议输出.

可以看出, 上述协议框架中的密钥传输被分割成为几个部分, 导致参与方之间的交互变得非常复杂, 从轮复杂度的角度考虑协议较为低效; 同时, 复杂的交互使协议框架非常混乱, 不利于协议的理解和应用.

为了降低参与方的交互复杂度并简化协议框架, 我们将上述协议中的cut-and-choose不经意传输替换为新原语cut-and-choose双向不经意传输.利用该原语的双向性, 可以将所有涉及到的密钥在一个阶段全部传输完成.同样, 由于功能函数ℱ_ccbot仅能用来传输单个混乱电路中单条输入线上的密钥, 我们将其扩展为可用于传输s个混乱电路中所有输入线密钥的功能函数, 称为批处理单选择cut-and-choose双向不经意传输, 记为ℱ$_{ccbot}^{B,S}.$基于cut-and-choose双向不经意传输, 安全两方计算协议框架可以简化为如下过程.

基于Cut-and-Choose双向不经意传输的安全两方计算协议框架.

步骤1.P₁构造s份混乱电路.

步骤2.双方调用批处理单选择cut-and-choose双向不经意传输功能函数ℱ$_{ccbot}^{B,S}.$对于所有混乱电路中的每条输入线:在检测电路中, P₂获得全部两个密钥; 在计算电路中, P₂获得与参与方输入比特相对应的密钥.

步骤3. P₁将所有混乱电路发送给P₂.

步骤4. P₂对所有检测电路进行检测, 检测通过后计算所有计算电路, 并取计算结果中占大多数的值作为协议输出.

通过对比该协议框架与基于cut-and-choose不经意传输的协议框架, 可以看出, 将cut-and-choose不经意传输替换为cut-and-choose双向不经意传输后, 协议框架明显得到简化, 新框架更清晰、更易于理解; 参与方之间的交互轮数明显得到降低.具体来说, 原有协议框架中的公开cut-and-choose指示比特串(步骤4)、发送检测电路中P₁输入线密钥(步骤5)以及发送计算电路中P₁输入对应密钥(步骤7)等诸多步骤都被省去.参与方P₁仅需在构造完混乱电路后和P₂运行一次批处理单选择cut-and-choose双向不经意传输协议, 然后将所有混乱电路发送给P₂即可.剩余阶段不再需要P₁参与, P₂可以本地完成所有检测和计算操作, 从而极大地降低了协议的交互复杂度.

4 结束语

本文提出了一种称为cut-and-choose双向不经意传输的密码学原语, 并基于同态加密给出了仅需1轮交互的协议构造.该构造被形式化证明在半诚实模型下满足标准的安全性定义.此外, 本文详细阐述了该原语在基于cut-and-choose范例的安全两方计算中的应用和优势.在下一步的研究中, 我们将重点关注如何构造可抵抗恶意敌手攻击的cut-and-choose双向不经意传输协议, 使其能够真正应用到基于cut-and-choose范例的安全协议中.