基于全同态加密的安全多方计算协议
摘 要：针对云计算环境下数据的隐私保护问题，在研究全同态加密技术的基础上设计了一个安全多方计算协议。该协议约定网络类型为同步网络，信道模式为可信的安全信道，敌手为半诚实的参与者，同时有一个服务器作为计算中心。参与者通过全同态加密算法预先对输入进行加密并将明文发送给服务器进行安全多方计算，服务器和其他参与者全程得不到该参与者的输入信息，保证了所有参与者的隐私。
内容目录：
1 算法概述
1.1 相关定义
1.2 全同态加密算法
1.3 基于整数全同态加密算法
1.4 安全多方计算模型
2 基于整数全同态加密技术的安全多方计算协议
3 结 语
随着云计算技术的飞速发展，越来越多的用户将个人数据上传至云服务器中交由云服务商管理，云服务商也将很多传统上本地化的服务提供给用户。智能信息化为当今社会提供便捷的环境的同时，如用户隐私泄露、网络攻击等安全问题却与日俱增。用户在很多云计算使用环境中并不希望其他用户和云服务商获得自己的个人信息，这正是安全多方计算（Secure Multi-party Computing，SMC）能解决的问题。
安全多方计算最早是由文献 [1] 通过百万富翁 问题提出的，该研究描述的是两个参与者在不泄露 自身信息的条件下进行比较，而在后续的研究中，参与者拓宽为多个。因此，安全多方计算就可以定义为，多个参与者在各自输入独立的情况下，共同进行一种运算。文献 [2] 将特定运算提高为任意代 数运算，并给出协议的完整流程。文献 [3] 在对前人研究进行概括的基础上形式化地定义了安全多方 计算的安全模型。文献 [4] 提出了参与者也有可能是攻击者的概念，将参与者根据行为定义为诚实参与者、半诚实参与者和恶意参与者。文献 [5] 在文 献 [4] 提出的参与者类型上，论述了即使参与者有恶意的行为，依然可以通过完善的设计保护系统和 其他参与者。
经过学界专家学者们多年的研究，安全多方计 算已经有了长足的发展。目前，由于全同态加密算法可以解决云计算、大数据环境下的用户数据隐私保护问题，因此将全同态加密（Fully Homomorphic Encryption，FHE ）算法与安全多方计算结合是一个新的研究热点。第一次真正意义上实现全同态加密 算法的研究是 Gentry 于 2009 年发表的博士论文 [6]， 该论文提出了基于 ideal latte 的全同态加密算法。 文献[7]利用门限加密与全同态加密相结合的构想， 实现了文献 [1] 提出的两方比较问题的同态思路，并且将计算复杂度降低至 O(m)（m 为信息长度）。文献 [8] 基于格上容错学习（Learning With Error， LWE ）的困难性假设，利用同态加密的思想，不直接比较输入是否相同，而是比较对输入的密文是否 有映射关系来判断安全两方协议的正确性。
针对云计算的发展速度和安全多方计算实际部 署问题，又有许多专家学者将服务器作为第三方来进行安全多方计算 。文献 [9] 充分利用云计算的 特点，构造出一种在服务器上利用求参与者之间输 入的最大近似公因子求解问题来进行判断安全多方 计算的正确性。虽然该方案降低了参与者的计算需 要；但是求解最大近似公因子本身需要的计算开销 很大，如果参与者数量很多的情况下，就要求服务 器拥有很大的计算能力。文献 [10] 利用多编码技术 和部分同态加密部署在云服务上达到安全多方计算的目的，但是该方案不能抵抗合谋攻击，且计算开 销较大。文献 [11] 将全同态加密算法转化为多比特 并行加密，构造出困难性基于 LWE 的多比特全同 态加密安全多方计算方案。文献 [12] 在文献 [11] 的基础上设计了一个困难性基于 Ferr-LWE 和 Some- are-errorless-LWE 的三轮协议的多方计算协议，该协议较好地控制了密文的膨胀，且其计算复杂度 密文膨胀率的控制是目前较好的。
充分考虑到实用性和安全性，本文首先决定采 用整数上的全同态加密算法来构造一个由服务器作 为第三方的安全多方计算协议。该协议需要参与者使用全同态加密算法预处理输入信息，服务器作为第三方只能对参与者的密文进行处理，保证了所有参与者的隐私不被泄露。
01算法概述
1.1 相关定义
本文的符号及其代表的含义如表 1 所示。
表 1 符号对应表
有如下两个定义：
（ 1）
有界分布
有
，并有 
满足：
式中： 是基于整数集的分布序列；
是一个可忽略函数。则称
是有界的。
根据 有界分布的定理，可以有推论：设 有界分布中有服从的
的独立随机变量，其变化出的
同样服从
有界分布。
（2 ）稀疏子集求和问题
一个整数集合
中的子集
， 找 到 一 个 S 中 的 元 素
， 使 得
是计算困难的。
1.2 全同态加密算法
全同态加密算法一般是由密钥生成算法、同态加密算法、同态解密算法和同态计算算法组 成，分别记为：KeyGen、Homo.Enc、Homo.Dec、 Evaluate。
（ 1 ）密钥生成算法（KeyGen）：随机选择一 个参数，输出公私钥对 (pk,sk)。（2 ）同态加密算法（ Homo.Enc ）：对于全同 态加密算法输入的明文 m 利用pk加密变成密文 c 的过程。3）同态解密算法（Homo.Dec）：对于Homo.Enc 中产生的 c 利用sk还原回 m 的过程。（4 ）同态计算算法（Evaluate）：对于多个密文
，利用公钥 pk 执行一个任意的代数运算f 的过程。
1.3 基于整数全同态加密算法
基于整数的全同态加密算法一般的安全性是基 于近似最大公因子问题，本文采用的参数选择与文 献 [13] 相同，同时给出整数上的全同态加密算法。一个全同态加密算法包含密钥生成算法、加密算法、解密算法和同态计算算法。
（ 1 ）密钥生成算法（KeyGen）：在密钥生成 中心产生一个长度为 η 的素数集
， μ 为选定的参数用于确定明文空间。选择参数 α 定 义为素数集中两个元素的乘积，随机选取一个元素 
，并令
，同时有 γ=α·β。利用
有界分布确定一个整数集合X，其界限为 β，其中的元素为
。再随机选取一个δ 比特的奇正整数y，即
。令公钥
， 私钥 sk=y。（2） 同态加密算法（Homo.Enc ）：首先以输 入的明文为 0 得到的密文组成集合
；其次取 
，计算
，S 为 1.1 小节中定义的稀疏子集求和中的子集 S。（ 3 ） 同 态 解 密 算 法（ Homo.Dec ）： 计 算
。（4 ）同态计算算法（Evaluate）：通过公式计 算
，其中 t 为电路 C 的输入。
1.4 安全多方计算模型
一个安全多方计算的模型为有 n 个参与 者
，参与者共同使用 f(·) 对输入
进行计算，得到一个计算结果y，并且参与者对于其他参与者的输入并不知情，如图 1 所示。
图 1 安全多方计算模型
一般在模型中执行协议的操作步骤，并且不去 获取其他参与者输入信息的参与者被称为诚实参与者。然而，在实际的应用场景中并不是所有的参与 者都是“安分守己”的，有一些参与者虽然会执行 协议的步骤，但是同时也会通过各种方法刺探其他参与者的输入信息，将这种参与者称为半诚实参与 者。还存在一种参与者，他们不仅不会正常执行协议的步骤，而且还可能向协议无关者泄露协议执行中获得的信息，甚至破坏协议的运行，将这种参与者称为恶意参与者。模型中的攻击者用
来表示，攻击者一般是一个或多个参与者，故有
。虽然半诚实的参与者不会主动对协议发起攻击，但是也存在着半诚实的参与者被收买等情况，所以在 很多研究中除了将恶意参与者看作是攻击者，也将半诚实参与者看为攻击者。
02 基于整数全同态加密技术的安全多方计算协议
研究安全多方计算协议，需要考虑到实际网络 类型、信道模式以及敌手攻击等问题。为了便于讨 论，本文中约定网络类型为同步网络，即参与者之 间不存在异步时钟，且信道模式为可信的安全信道， 敌手为半诚实的参与者，同时有一个服务器充当第 三方作为计算中心。本文设计的协议模型架构如图 2 所示。设基于整数全同态加密技术的安全多方计算协议中有 n 个参与者
，分别持有各自的输入
，经过服务器计算后再得到处理后的信息
。由于全同态加密的性质，可以将
还原为安全多方计算的结果y。具体流程如图 3 所示。
2 基于整数全同态加密技术的安全多方计算协议
图 3 基于同态加密的多方安全计算流程
具体的流程为分为 4 步，如下文所述。
（ 1 ） 初 始 化 流 程： 参 与 方
使 用密钥生成算法 KeyGen(·) 计算公私钥对 (pk,sk) 
。（2）加密处理流程：参与方
分别将各 自的输入
使用全同态加密算法Homo.Enc 进行加密，得到各自的密文
， 并将其发送给服务器。（ 3 ）安全多方计算流程：服务器接收到各个 参与者发送到的密文 ci 后，使用安全多方计算协议 进行处理，得到
。（4 ）同态计算流 程：服务器在对安全多方计算流程中计算的结果进行同态计算得到
，并将结果返还给各个参与者。
经过上述 4个步骤，参与者将各自输入的密文 上传至服务器进行安全多方计算处理，从服务器得 到返回的计算结果。整个过程中服务器并不知道参 与者的原始输入，只能对参与者上传的密文进行处 理。这样能保证其他参与者和服务器并不知道其原 始输入信息，从而保护了各个参与者的隐私。
03 结 语
本文基于整数上的全同态加密算法构造了一个安全多方计算协议，该协议约定网络类型为同步网络，信道模式为可信的安全信道，敌手为半诚实的参与者。该协议分为 4 个步骤，充分利用了全同态加密的性质，所有的参与者所得到的只有经过服务器处理后的对应输入的信息，同时该协议构造简洁，只需要两轮通信。
本文提出协议仍有需要改进的地方。由于全同态加密需要较大的计算能力，因此协议是将这部分交由参与者处理，这时如果有恶意的参与者混入其中，则最后可能无法还原回安全多方计算过程得到 的结果。后续研究工作中将针对这一问题进一步完善该协议。
