安全多方计算研究的是如何使一组互不信任的参与方实现保护隐私的协同计算问题, 即是这样一种分布式协议: n个参与方A₁, A₂, …, A_n分别拥有自己的秘密输入x₁, x₂, …, x_n, 在不借助任何第三方的情况下, 它们联合计算某个n变元功能函数

(y₁, y₂, …, y_n)=f (x₁, x₂, …, x_n)

且至少满足2个基本特性: 1) 正确性, 即每个参与方A_i都得到本方的正确输出y_i；2) 安全性, 即任何参与方的输入x_i都未泄露给其他人, 包括协议的其它参与方以及其他任何第三方.仅涉及2个参与方的安全多方计算称为安全两方计算.

安全多方计算的思想是Yao^[1]最先提出的.在Yao的开创性工作中, 提出了著名的百万富翁问题:两个富翁在街头相遇了, 在不向对方透露自己的财富的情况下, 他们想知道谁更富有. Yao将此问题抽象为隐私保护整数比较问题, 即分别拥有正整数a和b的2个人, 在不泄漏自己所拥有的整数的情况下, 如何比较a和b的大小，并给出了该问题的一个解决方案.此后，该思想受到了密码界的广泛关注. Goldreich等^[2]将Yao的安全计算思想推广为一般的安全多方计算模型, 并且证明了在点对点网络模型中, 若攻击者计算能力是有限的, 则1) 在半诚实攻击模型下, 安全多方计算可行的条件是t<n；2) 在恶意攻击模型下, 安全多方计算可行的条件是t<n/2. Ben-Or等^[3]和Chaum等^[4]证明了在点对点网络模型中, 若攻击者拥有无限的计算能力, 则1) 在半诚实攻击模型下, 安全多方计算可行的条件是t<n/2；2) 在恶意攻击模型下, 安全多方计算可行的条件是t<n/3. Rabin等^[5-6]证明了在广播网络模型中, 若攻击者拥有无限的计算能力, 则在半诚实攻击模型和恶意攻击模型下, 安全多方计算可行的条件都是t<n/2.

关于隐私保护整数比较问题, 由于Yao^[1]提出方案的复杂度较高, 很多密码学工作者致力于研究该问题安全高效的解决方案. Jakobsson等^[7]通过多轮迭代的方法给出了复杂度为多项式量级的一种解决方案；Ioannidis等^[8]基于1-out-of-2健忘传输协议给出了一种解决方案, 需要并行地运行n个1-out-of-2健忘传输协议, n为输入长度；Blake等^[9]基于同态加密体制给出了计算复杂度为16nlog N+28n、通信复杂度为4nlog N的一种解决方案.为避免复杂的公钥运算, Li等^[10-11]尝试利用对称密码的思想来解决隐私保护整数比较问题, 尽管提出的方案的效率较高, 但马敏耀^[12]指出它们的解决方案有时会输出错误的比较结果.

隐私保护整数比较问题比较的是2个整数的大小关系, 笔者提出一类新的安全两方比较问题, 即安全变换相等问题, 研究如何让两方在保护隐私的前提下, 比较有限集合上两个变换是否相等.非空集合X到自身的映射α:X→X称为集合X上的变换.对整数n (n>1), 令集合X_n={1, 2, …, n}, 将集合X_n上的所有变换构成的集合记为T_n, 即任意α∈T_n, α是这样的一个变换:α:X_n→X_n.对α∈T_n, 用α(i)表示i (i=1, 2, …, n)在α下的像.称X_n上的两个变换(即T_n中的两个元素)α和β是相等的如果α(i)=β(i)对所有的i=1, 2, …, n都成立.

笔者研究如何在保护隐私的情况下, 判断X_n上的2个变换，即T_n中的2个元素是否相等.此类问题有着丰富的应用背景, 例如在某些保护隐私的协作计算过程中, “双方拥有相同的变换”是整个计算过程有效进行的基本前提, 为此, 在计算真正开始之前, 双方需要在保护隐私的情况下执行某个协议, 来判断双方是否持有相同的变换.笔者在半诚实攻击模型下, 以具有加法同态性的加密体制为基本原语, 设计了求解安全变换相等问题的一个协议, 证明了其正确性和安全性, 并对其效率进行了说明.

1 知识准备

下面给出所涉及的基本知识.延用上文的符号, 记T_n为集合X_n={1, 2, …, n}上的所有变换构成的集合.

定义1  Alice和Bob分别拥有变换α∈T_n和β∈T_n, 在未泄露各自所拥有的变换且不借助任何第三方的前提下, 判定α和β是否相等的问题称为安全变换相等问题.求解安全变换相等问题的协议称为安全变换相等判定协议.

1.1 有限域上的Lagrange插值多项式

定义2^[13]  n是正整数, p是大于n的素数, 变换α∈T_n在GF_p上的Lagrange插值多项式，定义为

${f_\alpha }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\alpha \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} {{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right\}$

(1)

其中α(i)表示i (i=1, 2, …, n)在α下的像.可以验证, f_α(x)∈GF_p[x]是次数不超过n-1的多项式, 并且对任意i=1, 2, …, n, 都有f_α(i)=α(i).

下面的结论是显然的(证明略)：

定理1  n是正整数, p是大于n的素数, 变换α, β∈T_n在域GF_p上的Lagrange插值多项式分别为

$\begin{array}{l} {f_\alpha }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\alpha \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\}\\ {f_\beta }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\beta \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\} \end{array}$

记f_α(x)的系数向量为v_α=(α₀, α₁, α₂, …, α_n-1), f_β(x)的系数向量为v_β=(β₀, β₁, β₂, …, β_n-1), 则有

${v_\alpha } = {v_\beta } \Leftrightarrow \alpha = \beta $

(2)

1.2 加法同态加密体制

定义3 公钥加密体制E称为加法同态的, 如果在未知解密密钥的情况下, 能够从m₁和m₂的密文E (m₁)和E (m₂)有效地计算出m₁+m₂的密文E (m₁+m₂).

加法同态的加密体制具有如下特性: 1) 对任意正整数a, 能够从明文m的密文E (m)计算出数乘am的密文E (am). 2) 对有限域GF_p上的n维加密向量E (v)和n阶矩阵M, 可以同态地计算加密向量E (v·M).若用∑_{M (i)}表示矩阵M的第i列的所有元素的整数和, 则此计算过程中需要调用$\sum\limits_{i = 1}^n {} \left( {{\sum _{M(i)}} - 1} \right)$次同态加法运算.

1.3 半诚实攻击模型下的隐私函数计算

在半诚实攻击模型下, 每个参与者都严格地执行协议的步骤, 但他们可能保留协议执行的中间结果, 试图推导出其他参与方的隐私输入.下面给出半诚实攻击模型下两方隐私函数计算的定义.

定义4^[14] 记f:{0, 1}^*×{0, 1}^*→{0, 1}^*×{0, 1}^*是一个二元概率多项式时间函数, 其中f (x, y)=(f₁(x, y), f₂(x, y)). Π是计算f的一个双方协议.协议开始, 参与方P₁和P₂分别以x和y为输入, 执行协议后, P₁和P₂的view分别记为

$\begin{array}{l} {\rm{view}}_1^\mathit{\Pi }\left( {x,y} \right) = (x,{r^1},m_1^1,m_2^1, \ldots ,{m_t}^1)\\ {\rm{view}}_2^\mathit{\Pi }\left( {x,y} \right) = (y,{r^2},m_1^2,m_2^2, \ldots ,m_k^2) \end{array}$

其中：rⁱ表示第i方的内部随机带输出, m_jⁱ表示第i方收到的第j条信息. P₁和P₂的output分别记为output₁^Π(x, y)和output₂^Π(x, y).称Π在半诚实攻击模型下隐私计算f, 如果存在概率多项式时间算法S₁和S₂, 使下面的2个关系式成立:

$\begin{array}{l} \left\{ {{S_1}(x,{f_1}\left( {x,y} \right)),{f_2}\left( {x,y} \right)} \right\} \equiv c\\ \left\{ {{\rm{vie}}{{\rm{w}}_1}^\mathit{\Pi }\left( {x,y} \right),{\rm{outpu}}{{\rm{t}}_2}^\mathit{\Pi }\left( {x,y} \right)} \right\} \end{array}$

(3)

$\begin{array}{l} {f_1}\left( {x,y} \right),{S_2}(y,{f_2}\left( {x,y} \right))\mathop \equiv \limits^c \\ {\rm{outpu}}{{\rm{t}}_1}^\mathit{\Pi }\left( {x,y} \right),{\rm{vie}}{{\rm{w}}_2}^\mathit{\Pi }\left( {x,y} \right) \end{array}$

(4)

其中$\mathop \equiv \limits^c $表示随机变量簇的计算不可区分.

2 安全变换相等判定协议

下面基于有限域上的Lagrange插值多项式, 以加法同态加密体制为基本原语, 构造一个安全变换相等判定协议.在协议开始之前, 假定Alice和Bob商定了一个具有加法同态性的公钥加密体制, 例如Paillier加密体制^[15]. Alice生成自己的公私钥对, 保密私钥, 将公钥k告知Bob.

协议1 安全变换相等判定协议

输入: Alice拥有变换α∈T_n, Bob拥有变换β∈T_n.

输出: Alice和Bob均输出α=β或α≠β.

协议步骤如下:

1) Alice首先计算α∈T_n的Lagrange插值多项式

$\begin{array}{l} {f_\alpha }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\alpha \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\} = \\ \quad \quad \quad {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_{n - 1}}{x^{n - 1}} \end{array}$

令v_α=(a₀, a₁, a₂, …, a_n-1), 然后利用公钥k计算加密向量E_k(v_α)=(E_k(a₀), E_k(a₁), …, E_k(a_n-1)), 即对向量的各个分量进行加密.最后将E_k(v_α)发送给Bob.

2) Bob收到E_k(v_α)后, 执行如下步骤.

① 计算β∈T_n的Lagrange插值多项式

$\begin{array}{l} {f_\beta }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\beta \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\} = \\ \quad \quad \quad {b_0} + {b_1}x + {b_2}{x^2} + \ldots + {b_{n - 1}}{x^{n - 1}} \end{array}$

令v_β=(b₀, b₁, b₂, …, b_n-1), 用Alice的公钥k计算加密向量E_k(-v_β)=(E_k(-b₀), E_k(-b₁), …, E_k(-b_n-1)), 其中-b_i表示b_i在有限域GF_p中的加法逆元.

② 根据E_k(v_α)=(E_k(a₀), E_k(a₁), …, E_k(a_n-1))和E_k(-v_β)=(E_k(-b₀), E_k(-b₁), …, E_k(-b_n-1)), 利用加密体制的加法同态性计算:

$({E_k}({a_0} - {b_0}), \ldots ,{E_k}({a_{n - 1}} - {b_{n - 1}})) = {E_k}({v_\alpha } - {v_\beta })$

③ 随机地生成GF_p上的一个n阶可逆矩阵M, 利用加密体制的加法同态性计算E_k[(v_α-v_β) M], 并将E_k[(v_α-v_β) M]发送给Alice, 其中M是Bob的秘密矩阵.

3) Alice收到E_k[(v_α-v_β) M]后, 用自己的私钥对其进行解密(分别解密每个分量), 得到向量δ=(v_α-v_β) M.根据$\delta = 0 \Leftrightarrow \alpha = \beta $来判断α=β是否成立.

4) Alice将比较结果发送给Bob, 协议结束.

3 协议分析 3.1 正确性分析

定理2 在半诚实攻击模型下, 协议1执行结束后, 双方都输出正确的结果.

证明 在半诚实攻击模型下, Alice和Bob都严格地遵守协议规则, 由于δ=(v_α-v_β) M, 其中M是有限域GF_p上的n阶可逆矩阵, 所以, δ=(v_α-v_β) M=0，当且仅当v_α-v_β=0, 即v_α=v_β.由定理1可知, v_α=v_β当且仅当α=β.从而α=β当且仅当δ=(v_α-v_β) M=0, 即$\delta = 0 \Leftrightarrow \alpha = \beta $结论成立.

3.2 安全性分析

在半诚实模型下, A和B都严格遵循协议步骤, 允许他们借助自己在执行协议过程中的全部中间信息, 去推测对方的秘密输入.下面将证明协议1在该模型下是安全的.

定理3 协议1在半诚实攻击模型下是安全的.

证明 由于当″α=β″时, 双方都知道对方的输入.故证明过程中, 仅讨论″α≠β″的情形.令

f₁(α, β)=f₂(α, β)=″α≠β″

根据定义4, 需证明存在两个模拟器S₁和S₂, 分别满足半诚实攻击模型下隐私函数计算的两个条件.

首先构造模拟器S₁, 使其满足定义4中的式(3) :

$\begin{array}{l} \left\{ {{S_1}(\alpha ,{f_1}\left( {\alpha ,\beta } \right)),{f_2}\left( {\alpha ,\beta } \right)} \right\}\mathop \equiv \limits^c \\ \left\{ {{\rm{vie}}{{\rm{w}}_1}^\mathit{\Pi }\left( {\alpha ,\beta } \right),{\rm{outpu}}{{\rm{t}}_2}^\mathit{\Pi }\left( {\alpha ,\beta } \right)} \right\} \end{array}$

协议1执行完之后, Alice的view为

${\rm{vie}}{{\rm{w}}_1}^\mathit{\Pi }\left( {\alpha ,\beta } \right) = \left( {\alpha ,{R^1},{E_k}\left[ {({v_\alpha } - {v_\beta })\mathit{\boldsymbol{M}}} \right]} \right)$

其中：α为Alice的输入, R¹为Alice的内部随机带输出, E_k[(v_α-v_β) M]为Alice从Bob处收到的信息.模拟器S₁以(α, f₁(α, β))=(α, ″α≠β″)为输入, 执行如下步骤:

1) S₁计算α∈T_n的Lagrange插值多项式

$\begin{array}{l} {f_\alpha }\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {\alpha \left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\} = \\ \quad \quad \quad {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_{n - 1}}{x^{n - 1}} \end{array}$

令v_α=(a₀, a₁, a₂, …, a_n-1), 然后用Alice的公钥k计算加密向量E_k(v_α)=(E_k(α₀), E_k(α₁), …, E_k(α_n-1)).

2) S₁随机选取β^*∈T_n满足α≠β^*, 计算其Lagrange插值多项式

$\begin{array}{l} {f_{{\beta ^*}}}\left( x \right) = \sum\limits_{i = 1}^n {} \left\{ {{\beta ^*}\left( i \right)\prod\limits_{j = 1,j \ne i}^n {} \left[ {{{\left( {i - j} \right)}^{ - 1}}\left( {x - j} \right)} \right]} \right\}{b_0}^* + \\ \quad \quad \quad {b_1}^*x + {b_2}^*{x^2} + \ldots + b_{n - 1}^*{x^{n - 1}} \end{array}$

令v_β^*=(b₀^*, b₁^*, b₂^*, …, b_n-1^*), 用Alice的公钥k计算加密向量

E_k(-v_β^*)=(E_k(-b₀^*), E_k(-b₁^*), …, E_k(-b_n-1^*))

其中-b_i^*表示b_i^*在有限域GF_p中的加法逆元.

3) S₁根据E_k(v_α)=(E_k(α₀), E_k(α₁), …, E_k(α_n-1))和E_k(-v_β^*)=(E_k(-b₀^*), E_k(-b₁^*), …, E_k(-b_n-1^*)), 利用加密体制的加法同态性计算

(E_k(a₀-b₀^*), …, E_k(a_n-1-b_n-1^*))=E_k(v_α-v_β^*).

4) S₁随机地生成GF_p上的一个n阶可逆矩阵M^*, 并利用加密体制的加法同态性计算E_k[(v_α-v_β^*) M^*].

5) S₁输出

S₁(α, f₁(α, β))=α, R^*, E_k[(v_α-v_β^*) M^*]

其中R^*是S₁的内部随机带输出.

下面证明

$\alpha ,{R^1},{E_k}\left[ {({v_\alpha } - {v_\beta })M} \right]\mathop \equiv \limits^c \left( {\alpha ,{R^*},{E_k}\left[ {({v_\alpha } - {v_{{\beta ^*}}}){M^*}} \right]} \right)$

即随机变量簇view₁^Π(α, β)和S₁(α, f₁(α, β))是计算不可区分的.首先, 由于R¹和R^*分别是Alice和S₁的内部随机带输出, 故R¹$\mathop \equiv \limits^c $R^*，其次证明E_k[(v_α-v_β^*) M^*]和E_k[(v_α-v_β^*) M^*]的不可区分性:

1) 对除Alice之外的攻击者而言, 其不知道解密密钥(私钥), 由加密体制的安全性, 可保证E_k[(v_α-v_β^*) M^*]和E_k[(v_α-v_β^*) M^*]的不可区分性.

2) 对半诚实攻击者Alice而言, 其知道解密密钥, 能够从E_k[(v_α-v_β^*) M^*]和E_k[(v_α-v_β^*) M^*]分别得到(v_α-v_β) M和(v_α-v_β^*) M^*.由于α≠β且α≠β^*, 根据定理1, 可得v_α≠v_β且v_α≠v_β^*, 即满足v_α-v_β和v_α-v_β^*都是非零向量.由于M^*和M都是GF_p上n阶随机可逆矩阵, 故在未知M^*和M的情况下, (v_α-v_β) M和(v_α-v_β^*) M^*是不可区分的, 从而有

E_k[(v_α-v_β^*) M^*]$\mathop \equiv \limits^c $E_k[(v_α-v_β^*) M^*]

综上, 下面的关系式成立:

$\begin{array}{l} \left( {\alpha ,{R^1},{E_k}\left[ {({v_\alpha } - {v_\beta })M} \right]} \right)\mathop \equiv \limits^c \\ \left( {\alpha ,{R^*},{E_k}\left[ {({v_\alpha } - {v_{{\beta ^*}}}){M^*}} \right]} \right) \end{array}$

即S₁(α, f₁(α, β))$\mathop \equiv \limits^c $view₁^Π(α, β).由于变换相等函数是确定型的, 从而下关系式成立:

$\begin{array}{l} \left\{ {{S_1}(\alpha ,{f_1}\left( {\alpha ,\beta } \right)),{f_2}\left( {\alpha ,\beta } \right)} \right\}\mathop \equiv \limits^c \\ \left\{ {{\rm{vie}}{{\rm{w}}_1}^\mathit{\Pi }\left( {\alpha ,\beta } \right),{\rm{outpu}}{{\rm{t}}_2}^\mathit{\Pi }\left( {\alpha ,\beta } \right)} \right\} \end{array}$

类似地, 可以构造模拟器S₂, 使定义4中的式(4) :

$\begin{array}{l} \left\{ {{f_1}\left( {\alpha ,\beta } \right),{S_2}(\beta ,{f_2}\left( {\alpha ,\beta } \right))} \right\} \equiv c\\ \left\{ {{\rm{outpu}}{{\rm{t}}_1}^\mathit{\Pi }\left( {\alpha ,\beta } \right),{\rm{vie}}{{\rm{w}}_2}^\mathit{\Pi }\left( {\alpha ,\beta } \right)} \right\} \end{array}$

成立, 定理证毕.

3.3 效率说明

协议1的信复杂度为nK (其中K为密文长度).令∑_{M (i)}表示矩阵M的第i列的所有元素的整数和, 在协议1的一次执行中, Alice和Bob的计算复杂度如表 1所示.

4 结束语

笔者提出一类新的安全两方计算问题, 即安全变换相等问题.为了构造该问题的解决方案, 首先通过有限域上的Lagrange插值多项式, 将此问题转化为判断有限域上的两个向量是否相等问题, 然后以具有加法同态性的加密体制为基本原语, 设计了解决安全变换相等问题的一个协议.协议被证明是正确的, 且被证明在半诚实攻击模型下是安全的.从效率方面来看, 协议的复杂度较低.对所选用的加密体制而言, 本文只要求其安全且具有加法同态性, Paillier^[15]加密体制是一个可选的方案.笔者仅研究半诚实攻击者模型下的协议设计, 因此在下一步研究工作中, 可将如何在恶意模型下构建安全变换相等判定协议作为研究方向.