云计算、移动互联网、人工智能、物联网等现代信息技术的不断升级和应用普及，为各个实体之间进行数据的共享及联合计算带来了极大的便利，使得各个实体不但可以合作共享各自的信息以实现交流互通，还可以方便地利用其他实体的数据进行计算以实现数据价值最大化。由于不同实体之间进行数据联合计算的应用场景愈发复杂化，如果各个实体在未对私有数据进行处理的情况下就进行联合计算，势必会存在不同程度的隐私数据泄露问题，导致严重的后果。因此保护各个实体联合计算过程中私有数据的机密性和安全性是联合计算面临的一个严峻挑战。

为了解决隐私数据的安全共享问题，在保证数据机密性的同时实现联合计算，国内外众多学者对安全多方计算（secure multiparty computation，SMC）技术进行了深入研究。安全多方计算最早由Yao^[1]以“百万富翁问题”提出，即在不泄露双方参与者具体财富值的情况下对财富大小进行比较，该问题是安全多方计算的一个应用实例；并且，该文指出如果陷门置换存在，任何两方函数都可以安全地被计算，这标志着安全多方计算的诞生。随着安全多方计算的发展，许多新的适用于不同应用场景的安全多方计算问题及解决方案被提出，已有的研究主要分为保密的科学计算^[2]、保密的区间计算^[3]、保密的几何计算^[4]、保密的集合运算^[5]、保密的数据挖掘^[6–7]以及其他应用问题^[8–10]，比如，电子投票相关问题^[11–15]。

在保密的科学计算方面，对多个数据最大（小）值的保密计算进行研究是十分重要的，因为它能够适用于多种应用场景，在信息安全实践中也有很大的实际意义。比如，多个公司进行招标，只有出价最低的公司才能胜出，而其余公司则倾向于不透露自己的招标信息，以避免发生对公司不利的事件。除此之外，关于多个数据最值的保密计算问题同样具有十分重要的数学意义，可以应用于平均值计算场景。比如，在计算平均值的过程中，出于合理性及真实性的考虑，必须忽略这些数据的离群值。

多个数据的最大（小）值保密计算方案还可广泛应用于保密集合运算、保密数据挖掘及查询、保密电子拍卖等实际场景，同时这些算法和协议还可以作为基础模块用于设计各种更加安全高效的保密招投标、保密选拔推荐、保密优化、多方参与的点和区间关系的保密判定等安全多方计算协议。一般要计算最大值和最小值需要对多个数据进行两两比较或者将该问题转化为排序问题，但这种做法会大大增加计算复杂度甚至会泄露除最大值和最小值之外的其他隐私信息。因此，进行最大（小）值的保密计算方案研究是很有必要的。

Shi等^[16]利用分片混合和二分查找技术构造了一个可保密计算最大值的保密查询协议，但是，该协议需要一个不可信的数据聚合服务器为每个参与者分配一个基于身份信息的密钥，并负责收集数据，不能抵抗数据聚合服务器和参与者参与的合谋攻击。Li等^[17]基于加法同态加密算法和HMAC密钥管理技术提出一个时间序列数据保密求和协议，能够保密计算时间序列数据的最大值，但是需要一个可信的权威服务器和一个不可信的数据聚合者。窦家维等^[18]利用ElGamal同态加密给出了一个最小值保密计算方案，但是由于数据编码方式的原因，该方案并不适用于多数据最大值的保密计算，需要将编码原理进行变换后重新编码，存在不能同时计算各参与者私有数据的最大值和最小值这一缺陷。Zhang等^[19]针对不同用户手机感知到的数据进行数据收集，在保证数据机密性的条件下计算该组数据的最小值，但是，该方案需要可信第三方生成用户加密密钥，不能抵抗用户和第三方参与的合谋攻击。杨晓艺等^[20]提出一种新思想，将最小值保密计算问题转换为保密替换问题，在半诚实模型下设计了一个能够保密计算最小值的协议，但是，该方案与文献[18]方案一样需要通过两种编码方法来分别计算最大值和最小值，存在复杂度高、安全性低等缺陷。李占利等^[21]利用0-1编码原理及NTRU加密算法构造了一个适用于云环境下的最小值保密计算协议，通过编码方式及全集排列顺序的改变可以保密地进行最大值的计算，但是同样不能一次性计算出最大值和最小值。

上述方案都是利用编码方法解决最大值和最小值问题，但此类方案并不能同时保密计算最大值和最小值。目前可同时求解最大（小）值的方案较少。杨颜璟等^[22]基于Paillier同态加密算法设计了一个可一次性计算一组保密数据最大值和最小值的协议，但由于解密过程不是联合解密，存在不能抵抗解密密钥持有者参与合谋攻击的问题。李顺东等^[23]给出一个恶意模型下可同时求解最大值和最小值的方案，该方案是在恶意模型下设计的，虽然安全性较高，但由于采用了零知识证明，协议的整体效率较低。

综上，现有的大部分安全多方计算协议存在以下问题：效率低下、需要可信或者不可信的第三方、不能一次性保密计算出最大值和最小值、保密计算结果由唯一的指定解密密钥持有者获取等。为解决上述问题，本文首先提出一种新的隐私数据编码方法，可以对保密数据一次编码后同时计算最大值和最小值，其基本思想是给定一个势为l的有序数全集，各参与者据其所持数据在全集中的位置编码得到长度为l的数组，各数组按位相乘后的最左和最右非1数值所在位置即为最大值和最小值在全集中的位置。

在此基础上，结合ElGamal同态加密算法及门限解密构造了一个由各参与者参与且无需可信第三方的可同时求解最大值和最小值的安全高效保密计算协议。该协议可以保证所有参与者数据的安全性，并且解决了保密计算结果由唯一的指定解密密钥持有者获取的安全瓶颈问题，实现去中心化的目的。最后，基于理想–现实模拟范例证明了所提方案在半诚实模型下能够抵抗解密密钥持有者不参与的合谋攻击。该保密计算协议还可作为基础模块用于设计更加安全高效的保密数据挖掘、保密优化、多方参与的点与区间关系保密判定等安全多方计算协议。

1.   预备知识

给出用于构造可同时求解最大（小）值方案的安全多方计算协议安全性的定义，主要包括安全多方计算的理想模型、半诚实模型以及证明安全多方计算协议安全性需要用到的理想–现实模拟范例。

1.1   安全多方计算的理想模型

假定存在一个不可攻破的可信第三方TTP，TTP会忠实地执行协议并且不会透露任何隐私信息。各个参与者 ${P_i}$ 分别通过安全信道将自己的隐私数据 ${x_i}$ 告诉TTP，由TTP在本地帮助参与方执行计算函数，得出计算结果 ${f_i}\left( {{x_1},{x_2}, \cdots ,{x_n}} \right)$ ，再通过安全信道将结果分发给对应的参与者。协议执行过程中，TTP不会透露除结果外的任何信息，参与者 ${P_i}$ 也无法获取额外信息。具体模型如图1所示。

图  1  理想模型

Fig.  1  Ideal model

下载: 全尺寸图片

1.2   安全多方计算的半诚实模型

半诚实模型又称被动攻击模型，是一种重要的安全多方计算模型，该模型下，参与者 ${P_1},{P_2}, \cdots , {P_n}$ 诚实地按照协议规则和步骤执行，但 ${P_i}$ 有可能会记录计算过程中 ${P_j}\left( {i \ne j} \right)$ 传送的中间结果和协议的最终输出结果，并在协议执行后试图根据记录的这些秘密信息推导出 ${P_j}$ 的秘密输入，也可能将自己的秘密数据泄露给攻击者，这种攻击称为被动攻击，它只发生在协议执行之后。

1.3   理想–现实模拟范例

安全多方计算的安全性证明主要是通过计算复杂性进行一种抽象的仿真，即构造式证明。理想安全多方计算协议被认为是安全性最高的，然而现实生活中很难找到一个可以被所有参与者信任的TTP，因此实际中设计的安全多方计算协议是无可信第三方的。现实的安全多方计算协议通过参与方之间的交互协同计算功能函数 $f\left( {{x_1},{x_2}, \cdots ,{x_n}} \right)$ 。在证明现实模型下安全多方计算协议安全性过程中，假设协议A和协议B完成同样的功能，如果攻击者攻击协议A不能比攻击协议B获得更多的信息，那么协议A至少和协议B一样安全^[24]。同理，如果攻击者攻击现实模型下的一个协议 ${\pi}$ ，不比攻击理想模型下的一个协议 $\mathcal{F}$ 获得更多的信息，那么 ${\pi} $ 至少和 $\mathcal{F}$ 一样安全。该说法可以形式化地表述为：如果任何现实模型攻击者都存在一个理想模型攻击者 $S$ （模拟器），对于任何输入，在现实模型下运行包含攻击者的协议 ${\pi} $ 的全局输出，它和在理想模型下运行包含攻击者的协议 $\mathcal{F}$ 的全局输出是计算不可区分的，那么 ${\pi}$ 至少和 $\mathcal{F}$ 一样安全。

理想–现实模拟范例是利用仿真建立现实模型和理想模型之间的联系，将现实模型的安全规约到理想模型的安全上。其一般框架是，在模拟器 $S $ 中分别构造理想模型和现实模型。现实模型中，模拟器内部调用敌手，以诚实参与方的身份与敌手共同执行一个真实的两方协议；理想模型中，模拟器以敌手的身份与可信第三方TTP一起计算功能函数 $f( {x_1}, {x_2}, \cdots ,{x_n} )$ 。现实模型中，敌手在协议执行过程中所实施的攻击，在理想模型中都存在一个敌手实施相同效果的攻击。模拟器成功完成模拟后，将现实模型中的联合输出与理想模型中的联合输出进行对比，如果二者是计算不可区分的，则说明在理想模型中可以模拟敌手的可能的实际执行，敌手无法区分现实协议与理想协议，现实协议是安全的。

2.   基于ElGamal同态加密和门限解密的最大（小）值保密计算协议

首先，给出最大（小）值保密计算协议的计算原理，主要包含各个参与者隐私数据的编码原理和实现隐私数据最大值和最小值保密计算的依据。然后，基于该计算原理结合ElGamal同态加密算法及门限解密设计一个可一次性保密计算最大（小）值的安全多方计算协议。

2.1   基本编码原理

给出一种新的编码方法，该方法无需两次编码便能同时求解 $n$ 个参与者的最大值和最小值。在该方法基础上结合同态加密即可实现最大（小）值的保密计算。下面详细给出该编码方法的具体步骤。

假设有 $n$ 个保密数据都在全集中，即 ${x_i} \in \{ {{\textit{z}}_1}, {{\textit{z}}_2}, \cdots ,{{\textit{z}}_l} \} = U$ ，它们分别由 $n$ 个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 持有，其中 ${{\textit{z}}_1} < {{\textit{z}}_2} < \cdots < {{\textit{z}}_l}$ 且全集U的势 $\left| U \right| = l$ 。

1）每个参与者 ${P_i}$ 首先将数据 ${x_i}$ 按照以下方法表示为对应的数组 ${X_i} = \left\{ {{x_{i1}},{x_{i2}}, \cdots ,{x_{il}}} \right\}$ ，其中：

式中， $ {r_{ij}} $ 为不等于1的随机数， ${r_{ij}} \in {Z_N}$ ，且 $2 \leqslant {r_{ij}} < p^{ {1 /n}}$ ，其中 $p$ 为算法的模数。

所有参与者按照式（1）得到与自己持有的秘密数据 ${x_i}$ 一一对应的数组 ${X_i}$ ，

2）所有参与者对得到的 $n$ 个数组 ${X_1},{X_2}, \cdots ,{X_n}$ 求积，即将这些数组对应元素相乘，得到一个新数组：

3）对于新数组 $Y = \left\{ {{y_1},{y_2}, \cdots ,{y_l}} \right\}$ ，按照从左到右的方向，当首次出现 ${y_i} = {r_{ij}}$ 时，它所在的位置就是最小值在全集U中所在的位置，且该位置的元素值与最小值相等，即 $\min \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_i}$ ；按照从右到左的方向，当首次出现 ${y_j} = {r_{ij}}$ 时，所在的位置就是最大值在全集U中所在的位置，且该位置的元素值与最大值相等，即 $\max \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_j}$ 。

假设有4个参与者，其各自拥有的数据分别为 ${x_1} = 16,{x_2} = 13,{x_3} = 18,{x_4} = 12$ ，令 $U = \{ 11,12, \cdots , 19, 20 \}$ ，则：

显然可得： $\min \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_2} = 12$ ， $\max \{ {x_1},{x_2}, \cdots , {x_n} \} = {{\textit{z}}_8} = 18$ 。

以上是实现秘密数据的最大值最小值保密计算的依据，正确性说明详见第3.1节。直接在明文状态下进行运算不能保证数据的安全性，为了实现最大值和最小值的保密计算，本文在上述编码方法的基础上引入ElGamal同态加密，详见第2.2节。

2.2   最大（小）值保密计算协议设计

在第2.1节的编码方法的基础上结合ElGamal同态加密和最大门限解密，设计出可同时求解最大（小）值的保密计算协议，具体步骤如下：

输入： $n$ 个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 各自拥有的保密数据 ${x_1},{x_2}, \cdots ,{x_n}$ 。

输出： $a = \min \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}$ ， $b = \max \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}$ 。

1） $n$ 个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 基于ElGamal同态加密算法选取一个大素数 $ p $ 、一个乘法群 $ Z_P^* $ 上的生成元 $ g $ 、明文集 $ M = Z_P^* $ 、密文集 $ C = Z_P^* \times Z_P^* $ 。所有参与者随机选取整数 ${\alpha _i}(i = 1,2, \cdots ,n)$ ， $ {\alpha _i} \in {\mathbb{Z}_{p - 1}} $ ，计算公钥 $\; {\beta _i} = {g^{{\alpha _i}}}(\bmod p)$ ；公布公钥 $\;{\beta _i}$ ，计算获得联合公钥K，即： $K = \displaystyle\prod \limits_{i = 1}^n {\beta _i} = {g^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\left( {\bmod p} \right)$ 。

2） $n$ 个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 按照式（1）将各自拥有的保密数据 ${x_i}$ 编码为对应数组 ${X_i}$ ，其中 ${X_i} = \left\{ {{x_{i1}},{x_{i2}}, \cdots ,{x_{il}}} \right\}$ 。

3）每个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 随机选取 $ {k_i} $ ， $ \text{ }{k}_{i}\in {\mathbb{Z}}_{p-1} $ ，且 $ gcd\left( {{k_i},p - 1} \right) = 1 $ ，使用联合公钥K对编码后的数组 ${X_i} = \left\{ {{x_{i1}},{x_{i2}}, \cdots ,{x_{il}}} \right\}$ 进行加密，所有参与者可得到密文 ${C_i} = E\left( {{X_i}} \right) = \left\{ {{C_{i1}},{C_{i2}}, \cdots ,{C_{il}}} \right\}$ ，其中 ${x_{ij}}$ 的密文 ${C}_{ij}=E({x}_{ij})=\left({c}_{1},{c}_{2}\right)=\left({g}^{{k}_{i}}\mathrm{mod}\;p,{x}_{ij}\cdot {K}^{{k}_{i}}\mathrm{mod}\;p\right)$ ，并公布密文 ${C_i}$ 。

4）所有参与者由公布的密文可获取矩阵 ${\boldsymbol{C}}$ ：

5）对密文矩阵 ${\boldsymbol{C}}$ 的每一列元素进行相乘，得到密文：

6）联合解密密文 $ {\boldsymbol{H}} $ ，解密某个密文 ${H_k} = \left( {{H_{k1}},{H_{k2}}} \right)$ 时每个参与者需要提供部分解密结果 ${V_i} = H_{k1}^{{\alpha _i}}\left( {\bmod p} \right) = $ $ {\left( {\displaystyle\prod\limits_{i = 1}^{n + 1} {{g^{{k_i}}}} } \right)^{{\alpha _i}}}$ 。首先，按照从左到右的方向进行联合解密，当首次得到第1个等于随机数 ${r_{ij}}$ 的元素 ${y_i}$ 时终止解密，全集中对应位置的元素即为最小值，并令 $a = \min \{ {x_1}, {x_2}, \cdots ,{x_n} \} = {{\textit{z}}_i}$ ；随后，按从右到左的方向解密，得到第1个等于随机数 ${r_{ij}}$ 的元素 ${y_j}$ 时终止解密，全集中对应位置的元素即为最大值，并令 $b = \max \{ {x_1},{x_2}, \cdots ,{x_n} \} = {{\textit{z}}_j}$ 。

具体协议执行过程如图2所示。

图  2  最大（小）值保密计算协议执行过程示意图

Fig.  2  Schematic diagram of the implementation process of the confidential maximum (minimum) value calculation protocol

下载: 全尺寸图片

3.   安全性分析

对第2节所提基于ElGamal同态加密和门限解密的最大（小）值保密计算协议进行正确性及安全性分析，并与现有同类方案进行性能对比。

3.1   正确性证明

定理1 　对于 $n$ 个参与者拥有的数据 ${x_1},{x_2}, \cdots ,{x_n}$ ，均按照式（1）构造数组 ${X_i}$ ，将数组对应位置的元素相乘，得到一个新数组 $Y = \left\{ {{y_1},{y_2}, \cdots ,{y_l}} \right\}$ 。按照从左到右的方向，当首次出现 ${y_i} = {r_{ij}}$ 时，全集 $U$ 中对应位置的元素即为最小值，即 $\min \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_i}$ ；按照从右到左的方向，当首次出现 ${y_j} = {r_{ij}}$ 时，全集 $U$ 中对应位置的元素即为最大值，即 $\max \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_j}$ 。

证明：因为对于每个参与者按照式（1）编码后获得的数组 ${X_i}\left( {i = 1,2{\text{,}} \cdots ,n} \right)$ 来说， ${x_i}$ 在全集 $U$ 中所在的位置对应的元素为随机数 ${r_{ij}}$ ，其余位置对应元素为1；将每个参与者编码后得到的数组 ${X_i}\left( {i = 1,2, \cdots ,n} \right)$ 对应位置的元素进行相乘得到数组 $Y$ ，相当于在全集 $U$ 中对这 $n$ 个参与者私有数据的最大值和最小值位置进行标记，数组 $Y$ 从左到右的方向第一个等于随机数的元素 ${y_i}$ 和从右到左的方向第1个等于随机数的元素 ${y_j}$ 的位置则分别为所有参与者私有数据最小值和最大值在全集 $U$ 中所处的位置。证毕。

定理2 　在半诚实模型下，基于ElGamal同态加密和门限解密的最大（小）值保密计算协议是正确的。

证明：第2.2节第5）步中，对密文矩阵 ${\boldsymbol C}$ 的每一列元素进行相乘，由ElGamal加密算法的乘同态性质，可得： $\displaystyle\prod \limits_{i = 1}^n {C_{ij}} = \displaystyle\prod \limits_{i = 1}^n E({x_{ij}}) =$ $\left({\displaystyle \prod _{i=1}^{n}{g}^{{k}_{i}} \left(\mathrm{mod}\;p\right)},\displaystyle \prod \limits _{i=1}^{n}{x}_{ij}\cdot {K}^{{k}_{i}} \left(\mathrm{mod}\;p\right)\right)$ ，其中 $K = \displaystyle\prod \limits_{i = 1}^n {\beta _i} = {g^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\left( {\bmod p} \right)$ 。

第2.2节第6）步中，每个参与者解密某个密文 ${H_k} = \left( {{H_{k1}},{H_{k2}}} \right)$ 时需要提供部分解密结果 ${V_i} = H_{k1}^{{\alpha _i}} \left( {\bmod p} \right) = {\left( {\displaystyle\prod\limits_{i = 1}^{n + 1} {{g^{{k_i}}}} } \right)^{{\alpha _i}}}$ ，所有参与者进行联合解密：

根据定理1，按照从左到右的方向解密，当首次出现 ${y_i} = {r_{ij}}$ 时，全集 $U$ 中对应位置的元素为最小值，即 $\min \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_i}$ ；按照从右到左的方向解密，当首次出现 ${y_j} = {r_{ij}}$ 时，全集 $U$ 中对应位置的元素为最大值，即 $\max \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_j}$ 。证毕。

3.2   安全性证明

在安全多方计算中，半诚实协议的安全性定义如下^[25]：

设 $f = f{\left( {{{\left\{ {0,1} \right\}}^*}} \right)^n} \to {\left( {{{\left\{ {0,1} \right\}}^*}} \right)^n}$ 是概率多项式函数，如果存在概率多项式时间算法 $S $ 满足：

则称 ${\pi}$ 为保密计算 $f$ 的协议。

式中： $\mathop \equiv \limits^c $ 代表计算上不可区分； $I = \left\{ {{P_{i1}},{P_{i2}}, \cdots ,{P_{is}}} \right\}$ 为任意参与者的子集，即 $I \subseteq \left\{ {{P_1},{P_2}, \cdots ,{P_n}} \right\}$ ； $x_{ij}(j=1,2, \cdots , s)$ 为参与者 $ P_{ij} $ 的私密数据； ${X=\left\{x_1,x_2, \cdots ,x_n\right\} }$ 为全体参与者的私有数据集合； ${f_I}\left(X \right)$ 为任意参与者序列； $\{view_I^{\pi} \left( X \right)\}$ 为各个参与者 $ P_i $ 的视图 $view_i^{\pi} \left( X \right) $ 的集合， $view_i^{\pi} \left( X \right)$ 为协议 ${\pi}$ 执行过程中的消息序列，即 $view_i^{\pi} \left( X \right) = $ $\left( {{x_i},{r_i},m_i^1,m_i^2, \cdots ,m_i^t} \right)$ ，其中， $m_i^j$ 为第 $i$ 个参与者收到的第 $j$ 个消息， ${r_i}$ 为第 $i$ 个参与者产生的随机数。

定理3 　基于ElGamal同态加密和门限解密的最大（小）值保密计算协议在半诚实模型下是安全的，且能抵抗合谋攻击。

证明：在半诚实模型下，考虑任意 $n - 1$ 个参与者合谋的情况，证明协议的安全性，该结构为最大攻击者结构，如果可以证明基于ElGamal同态加密和门限解密的最大（小）值保密计算协议对于该最大攻击者结构是安全的，那么该协议对于其他任意非最大攻击者结构都是安全的。

各参与者都是在密文的形式下进行计算，所以，攻击者只能获取其他参与者保密信息的密文形式。由于协议采用的是基于难解的离散对数困难性问题的ElGamal同态加密算法，因此攻击者不能解密获取其他参与者的保密信息。

由协议的执行过程可知，每个参与者都是通过自己持有的私钥进行公钥计算，最后联合生成ElGamal同态加密系统的公钥，解密过程需要所有参与者共同协作才能得到正确的输出结果。如果有某个参与者不进行联合解密，那么就不能正确地将密文解密，所以能抵抗合谋攻击。

不妨假设后 $n$ 个参与者合谋，由于在该协议中各个半诚实参与者 ${P_i}$ 的地位是均等的，所以只需证明 ${P_1}$ 的保密数据是安全的即可。不失一般性，假设 ${P_1}$ 是诚实的，最大攻击者集合为 $I = \left\{ {{P_2},{P_3}, \cdots ,{P_n}} \right\}$ ， $X = \{ {x_1}, {x_2}, \cdots , {x_n} \}$ ， ${P_1}$ 的私有数据 ${x_1}$ 有两种情况：

1） $ \mathrm{max}\left(X\right)= {x}_{1} $ 或者 $ \mathrm{min}\left(X\right)= {x}_{1} $ 并且 ${x_1} \notin \{ {x_2},{x_3}, \cdots , {x_n} \}$ ，此时如果后 $n$ 个参与者合谋， ${x_1}$ 将完全泄露，这和理想模型下的协议完全一样，实际协议没有比理想协议泄露更多信息，所以协议是安全的。

2） $\min \left( X \right) < {x_1} < \max \left( X \right)$ ，此时如果后 $n$ 个参与者合谋， ${x_1}$ 不会泄露，和理想模型下的协议也完全一样，实际协议没有比理想协议泄露更多信息，所以协议是安全的，证明如下：

利用模拟–范例的方式，通过构造满足式（4）的模拟器 $S $ ，模拟后 $n$ 个合谋者在现实模型下的视图信息，分为以下两种情况：

①基于以上假设，最大攻击者集合为 $I = \left\{ {{P_2},{P_3}, \cdots , {P_n}} \right\}$ ，这 $n - 1$ 个攻击者合谋想获取有关 ${P_1}$ 私有数据 ${x_1}$ 的信息。 $ S $ 的模拟过程如下：

a.后 $n$ 个参与者合谋，给定输入 $\left( {I,{X_I},{f_I}\left( X \right)} \right) = \left( {I,\left\{ {{x_2},{x_3}, \cdots ,{x_n}} \right\},{f_I}\left( X \right)} \right)$ ，模拟器 $S $ 从全集 $U = \{ {{\textit{z}}_1},{{\textit{z}}_2}, \cdots , {{\textit{z}}_l} \}$ 中随机选取 ${x'_1}$ ，并且 ${x'_1}$ 必须满足条件： ${f_I}\left( X \right) = {f_I}\left( {X'} \right)$ ，其中 $X = \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}$ ， $X' = \left\{ {{{x}'_1},{x_2}, \cdots ,{x_n}} \right\}$ 。

b. $S $ 模拟所有参与者执行协议，根据 $X'$ 按照式（1）构造数组 $X_1^*,{X_2}, \cdots ,{X_n}$ ，利用ElGamal同态加密算法加密所得数组得到 $E\left( {X_1^*} \right),E\left( {{X_2}} \right), \cdots ,E({X_n})$ 。

c. $S $ 根据协议对密文矩阵的每一列元素进行相乘，得到数组 ${H^*}$ ，最后解密得到 ${f_I}\left( {X'} \right)$ 。

$S $ 模拟过程中所得的视图信息如下：

令 $S \left( {I,{X_I},{f_I}\left( X \right)} \right) \;=\;$ $\{ I, \left( {{x_2},{x_3}, \cdots ,{x_n}} \right),\left( {E\left( {{X_2}} \right),E\left( {{X_3}} \right), \cdots , E\left( {{X_n}} \right)} \right),{C^*},{f_I}\left( {X'} \right) \}$ ，由于ElGamal加密方案具有语义安全^[26]，并且所有参与者共同参与联合计算才能得到正确的解密结果，因此 $C$ 和 ${C^*}$ 是计算不可区分的，即 $C\mathop \equiv \limits^c {C^*}$ ，同时 ${f_I}\left( X \right) = {f_I}\left( {X'} \right)$ ，因此 ${\left\{S \left(I,{X}_{I},{f}_{I}\left(X\right)\right)\right\}}_{X\in {\left({\left\{0,1\right\}}^{*}\right)}^{n}} \stackrel{c}{\equiv } {\left\{vie{w}_{I}^{{\pi} }\left(X\right)\right\}}_{X\in {\left({\left\{0,1\right\}}^{*}\right)}^{n}}$ 。

由此可知，协议在半诚实模型下是安全的。

②基于以上假设， $I \subset \left\{ {{P_2},{P_3}, \cdots ,{P_n}} \right\}$ 想获取有关 ${P_1}$ 私有数据的信息。

由情况①可知：当 $I \subset \left\{ {{P_2},{P_3}, \cdots ,{P_n}} \right\}$ 时，在执行协议时， $I$ 作为一个攻击者集合，收到的消息只有第2.2节第3）步 ${P_1}$ 发出的 ${C_1} = E\left( {{X_1}} \right) = \left\{ {{C_{11}},{C_{12}}, \cdots ,{C_{1l}}} \right\}$ 和第2.2节第6）步解密某个密文 ${H_m} = \left( {{H_{m1}},{H_{m2}}} \right)$ 时收到的部分信息，后 $n$ 个参与者参与合谋无法获取关于保密数据 ${x_1}$ 的有关信息，因为解密过程需要所有参与者共同协作才能得到正确的输出结果。同理，当攻击者结构为其他任意非最大攻击者结构时，这些参与者参与合谋同样无法获取关于保密数据 ${x_1}$ 的有关信息，即当 $I \subset \left\{ {{P_2},{P_3}, \cdots ,{P_n}} \right\}$ 时，合谋者无法获取有关 ${P_1}$ 私有数据的信息。

综上所述，基于ElGamal同态加密和门限解密的最大（小）值保密计算协议在半诚实模型下是安全的，且能抵抗合谋攻击。证毕。

3.3   安全性对比

选取同类最大（小）值保密计算方案与本文所提方案进行性能对比，分别从同态特性、是否需要可信第三方、比较最值是多次比较还是一次性比较、是否是联合解密等方面进行对比，其对比结果如表1所示。

由表1可以看出：文献[17]方案基于加法同态加密算法保密计算时间序列数据的最大值，需要一个可信的权威服务器和一个不可信的数据聚合者，不能一次性计算一组保密数据最大值及最小值，并且解密过程不是联合解密。文献[18]方案用的是乘法同态，整个协议执行过程中都无需可信第三方，但是存在不能同时计算各参与者私有数据的最大值和最小值这一缺陷，同时由于解密过程不是联合解密，所以不能抵抗任意合谋攻击。文献[22]方案采用的是加法同态，即无需可信第三方还能一次性计算一组保密数据最大值及最小值，但由于解密过程不是联合解密，所以存在不能抵抗解密密钥持有者参与的合谋攻击这一问题。本文所提方案既无需可信第三方还可一次性保密计算最大值和最小值，同时利用联合解密解决了保密计算结果由唯一指定解密密钥持有者获取导致的安全问题。

4.   效率分析

对上述基于ElGamal同态加密和门限解密的最大（小）值保密计算协议的效率进行分析，分别从计算复杂度、通信复杂度、方案性能对比等方面进行研究。

4.1   计算复杂度

在基于ElGamal同态加密和门限解密的最大（小）值保密计算协议中，首先， $n$ 个参与者都需要生成各自的公钥最后合作计算获得联合公钥，所有参与者需要进行 $2n$ 次模指数运算。接着，每个参与者 ${P_i}( i = 1,2, \cdots ,n )$ 按照式（1）将各自拥有的保密数据 ${x_i}$ 编码为对应的l维数组。而后，对编码后的数组中的每一个元素进行加密，所有参与者需要进行 $2nl$ 次模指数运算。然后，所有参与者联合解密密文 ${\boldsymbol H}$ ，先按照从左到右的方向进行联合解密，当得到第1个等于 $0$ 的元素 ${y_i}$ 时终止解密，并令 $a = {\text{min}}\left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_i}$ ，需要进行 $ni$ 次模指数运算；再按照从右到左的方向解密，得到第1个等于 $0$ 的元素 ${y_j}$ 时终止解密，并令 $b = {\text{max}}\left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\} = {{\textit{z}}_j}$ ，需要进行 $n\left( {l - j} \right)$ 次模指数运算。因此，协议总共需要 $2n\left( {l + 1} \right) + n\left( {i + l - j} \right)$ 次模指数运算。

4.2   通信复杂度

通信复杂度指的是一个问题能以多快的速度解决。比如EQ的任何确定型通信协议无法比发送所有输入做得更好，那么这就意味着EQ的复杂度为 $O\left( n \right)$ 。一般情况下，通常采用一个协议的通信轮数、传送比特数等来衡量该协议的通信复杂度，而针对安全多方计算协议则往往倾向于选择通信轮数这一指标来进行衡量。

在基于ElGamal同态加密和门限解密的最大（小）值保密计算协议中，每个参与者 ${P_i}\left( {i = 1,2, \cdots ,n} \right)$ 共同计算获得联合公钥 $K$ 需要进行1轮通信。接着，对数组 ${X_i} = \left\{ {{x_{i1}},{x_{i2}}, \cdots ,{x_{il}}} \right\}$ 进行加密，而后公布密文 ${C_i}$ ，需要进行1轮通信。最后，所有参与者联合解密密文 ${\boldsymbol H}$ ，先按从左到右的方向进行联合解密，当得到第1个等于随机数的元素 ${y_i}$ 时终止解密，需要进行 $i$ 轮通信；再按从右到左的方向解密，得到第1个等于随机数的元素 ${y_j}$ 时终止解密，需要进行 $j$ 轮通信。因此，协议总共需要 $i + j + 2$ 轮通信。

4.3   性能对比

文献[18]方案利用ElGamal同态加密给出一个最小值的保密计算方案，运行整个协议求出一组数据的最小值需要进行 $2\left( {nl + y} \right)$ 次模指数运算，如果需要一次性计算出最大值和最小值则需要进行两次协议的执行，即需要进行 $ {\text{4}}\left( {nl + y} \right) $ 次模指数运算。另外，该协议执行完需要的通信轮数为 $n + y - 1$ 轮。文献[20]方案利用GM同态加密算法给出一个最小值的保密计算方案，但是该方案需要通过两种编码方法来分别计算出最大值和最小值，存在复杂度高、安全性低等缺陷。此外，该协议总共需要 $2nl + {\text{lb }}p$ 次模指数运算、n轮通信。文献[21]方案利用0-1编码原理及NTRU加密算法构造一个适用于云环境下的最小值保密计算协议，通过编码方式及全集排列顺序的改变可以保密地进行最大值的计算，其基本原理是最大值和最小值问题具有对称性，整个协议总共需要进行 $n\left( {l + 1} \right)$ 次模指数运算、 $3n - 1$ 轮通信。

本文所提方案既无需可信第三方还可一次性保密计算最大值和最小值，同时利用联合解密解决保密计算结果由唯一指定解密密钥持有者获取导致的安全问题。整个协议总共需要 $2n\left( {l + 1} \right) + n\left( {i + l - j} \right)$ 次模指数运算、 $i + j + 2$ 轮通信。

将文献[18,20,21]方案与本文方案进行效率对比，分别从是否能够抵抗合谋攻击、计算复杂度、通信复杂度等方面进行研究，结果如表2所示。

表2中，n为参与者人数，l为全集中的元素个数，y为最小值，i、j分别为最小值、最大值在全集中所处的位置，p为算法模数。表2中数据表明：虽然文献[21]方案效率较高，但并不能抵抗合谋攻击。因此，主要与文献[18,20]方案进行对比。文献[18,20]方案的计算复杂度与n、l、y、p有关，而本文方案与n、l、i、j有关。一般情况下，i和j都较小，而n、l、y、p较大，所以总体来看，本文方案具有更低的计算复杂度。

为了更直观地看出文献[18,20]方案与本文方案的差异，分别假设协议中 $n=\text{1}00，l=\text{5}0，y=\text{1}0， i=\text{5}，j=\text{7}$ ，通过计算不同同态加密算法在同一个模指数下的运行时间进行实验仿真，其中，硬件环境为Intel Core i5 @CPU at 8300 Hz with 8.00 GB of RAM，软件环境为Win 10 64-bit，Python 2.7。文献[18,20]方案和本文所提协议计算耗时对比如图3所示，通信轮数对比如图4所示。

图  3  其他方案与本文方案计算开销对比

Fig.  3  Comparison of the computational overhead of other solutions and the proposed solution in this paper

下载: 全尺寸图片

图  4  相关协议在不同参与人数情况下的通信轮数对比

Fig.  4  Comparison of the number of communication rounds for the relevant protocols with different numbers of participants

下载: 全尺寸图片

由图3结果可以看出：文献[18,20]方案和本文方案在算法模数为128～256 bit之间时，三者计算开销相差不大；但当模数大于256 bit时，显然本文方案的协议耗时最少。文献[18]方案的协议耗时虽然与本文方案耗时相差不大，但是它不能抵抗解密密钥持有者参与的合谋攻击，而本文方案可以抵抗任意参与者参与的合谋攻击。

由图4结果可以看出：文献[18,20]方案中协议的通信轮数随着参与者人数的增加而线性增加，而本文方案的通信轮数不变。原因是因为本文方案的通信轮数只与最大值和最小值在全集中所处位置有关，而其他方案的通信轮数与参与人数相关。当参与者人数小于或者等于10时，文献[20]方案中协议的通信轮数是所有方案中最少的，但当参与者人数超过14时，本文方案比其他方案具备更高的效率。

5.   结　论

本文研究一组数据的最大值和最小值同时求解问题，该问题的解决方案可以作为基础模块用于设计其他安全多方计算协议，在信息安全实践中也有着广泛的应用前景。本文以ElGamal同态加密算法为基石，提出一种安全高效的可同时求解最大（小）值的方案。方案中设计了一种隐私数据编码方法，能有效克服传统方案中的无法一次性保密计算最大（小）值问题；另外，采用门限解密技术可有效保证所有参与者的计算公平性，实现去中心化的目的。同时，对所提方案在半诚实模型下能够抵抗任意合谋攻击进行证明。最后，与同类方案进行性能和效率分析对比，表明本文所提方案在一次性保密计算最大值和最小值的同时还能保证各参与方之间的公平性，并且通过仿真测试可以看出所提方案在运算效率方面具有一定优越性。如何将最大最小值保密计算协议应用于保密集合运算、保密数据挖掘、保密电子拍卖等实际场景有待于进一步研究。