基于全同态加密的安全多方计算探讨

李习习 胡业周

摘要：随着云计算的发展与应用，数据的隐私保护越来越受到人们的关注。而全同态加密这一密码学原语的提出，为数据的隐私计算提供了一个强有力的工具。另一方面，安全多方计算允许人们共同计算一个函数得到想要的结果而不泄露自己的私有数据，在现实生活中有着众多的应用。研究发现全同态加密可以作为安全多方计算协议的构建模块，且在LWE的假设下，协议在面对一个半恶意的敌手是安全的，进一步，在CRS模型下可由非交互的零知识证明将协议转换成面对恶意敌手也是安全的。

关键词：全同态加密;安全多方计算;LWE;（半）恶意敌手;CRS模型

中图分类号：TP309.7 文献标识码：A

文章编号：1009-3044（2020）21-0019-04

开放科学（资源服务）标识码（OSID）：

1 引言

云计算作为一种新的计算方式，在生产生活中扮演着重要的角色，当用户将自己的私有数据上传到一个不可信的云服务器上进行计算，如何能够保证数据不会泄露，这给云计算的应用带来巨大的挑战。随着量子计算机的不断发展，一些传统的加密体制在量子计算机面前将会变得不再安全，如RSA，EIGa-mal等。后量子时代的到来迫切需要能够抵抗量子计算攻击的密码体制，如基于纠错码的公钥密码体制，基于格的公钥密码体制等。

全同态加密（FHE）的出现上述问题提供了一个很好的解决方案，FHE的一个显著特征就是允许对密文直接进行计算操作，解密结果相当于对明文做同样的计算操作，即：如，（f （Enc（m1），Enc（m2），…，Enc（mn）=f（m1，m2，...'mn）。安全多方计算的提出允许人们在不揭露自身的数据而安全的计算出一个函数，参与方除了最终的计算结果得不到任何其他的信息。自1986年姚期智构造一个基于混淆电路的安全多方计算协议以来[1]，安全多方计算得到了快速地发展。2012年，LOPEZ-AltA等人提出多密钥（MFHE）全同态加密的概念并基于NUTR构造了第一个MFHE方案[2]，很自然的，以MFHE为基础，可以创建一个安全多方计算协议。之后，大量基于多密钥全同态加密的安全多方计算被提出。在本文中，我们主要探讨以GSW全同态加密方案为基础的安全多方计算，因为该类方案的密文不会随着同态操作发生扩张也不需要运行密钥。我们从MW（16）中的安全多方计算协议展开[3]，对不同模型下的安全多方计算协议的构造、协议的安全性、协议的功能性进行探讨。

2 基于GSW全同态加密的安全多方计算协议的构造

在本节中，我们描述在三种不同模型中以GSW全同态加密方案为基础的安全多方计算协议，三种模型分别为CRS模

通常，一个全同态加密方案包含以下几个步骤：SetUp（参数设置）、KeyGen（密钥对生成）、Enc（加密）、Eval（评估密文）、Dec（解密）。然后若想能够应用在安全多方计算中，需要将一个单密钥的全同态加密方案扩展成多密钥，即在原有方案的基础上增加一个步骤为Expand（扩展）。最后一个安全多方计算协议以下几个过程：输入（一个想要计算的函数以及不同参与方的私有数据）、交互（所有的参与方在协议内进行交互，参与方当中可能有被敌手腐败的人员，他们不一定忠实地履行协议。判断一个协议的优良与否在于交互的轮数，一般轮数越低，协议的性能越好）、输出（交互完成后，每个参与方输出自己的结果，最后联合所有参与方的输出，即可得到最终想要计算的结果）。

2.1 CRS模型中的安全多方计算协议议的安全性可由LWE假设来保证，具体我们将在下节讨论。

3 协议的安全类型

我们首先给出安全多方计算中常见的敌手类型。

（1）半诚实敌手：忠实地履行协议但是想根据自己的信息窥探出其他参与方的私有信息。

（2）半恶意敌手：可以腐败任意多个诚实方，除了标准磁带外，还拥有一个证据磁带，该敌手必须将自己代表的诚实方的输入记录到证据磁带上。敌手可以根据输入和一定的随机性来决定是否忠实地履行协议。

（3）恶意敌手：可以任意篡改、泄露协议和私有数据，甚至可以中断协议。

通常利用理想现实模型证明一个安全多方计算协议的安全性，即通过一系列的混合游戏来证明理想=现实，其中。o表示计算不可区分。下面我们分别描述在不同模型下的安全多方计算协议的安全性。

3.1 CRS模型中安全多方计算协议的安全性

在CRS模型中，安全多方计算协议在面对一个恶意的敌手是安全的。首先利用理想现实模型证明协议在面对一个半恶意的敌手是安全的，即存在一个模拟算法S thr，假设共有Ⅳ个参与方，当一个半恶意的敌手恰好腐败Ⅳ-l个参与方时，模拟器S thr在第一轮用0代替唯一诚实方Ph的真实输入进行加密并发布出去，在第二轮中得到模拟解密p h并在第二轮结束前用模姒部分解密代替真实解密发布出去。通过定義混合游戏REAL πAZ，HYB πAZ，IDEALFSZ利用LWE假设得到IDEAL FSZ≈ REAL πAz，安全性得证。在证明协议在面对一个半恶意的敌手之后，通过一个非交互的零知识证明可以将协议转化成在面对恶意敌手也是安全的。

3.2 分布式设置模型中安全多方计算协议的安全性

在分布式设置中，安全多方计算协议在面对一个恶意的敌手是安全的。和上述证明方法类似，首先证明在面对一个半恶意的敌手协议是安全的，过程与上述方案相同。之后，在转化成为面对恶意敌手也是安全的，需要一个两轮的自适应安全承诺方案，一个单向函数，一个三轮的随机硬币带有延迟输入的不可区分混淆器，一个四轮的零知识证明系统，利用这些可以将上述3轮半恶意安全的协议转化成一个4轮恶意安全的协议。

3.3 无CRS模型中安全多方计算协议的安全性

在无CRS模型中，安全多方计算协议在面对一个半恶意的敌手是安全的，证明方法与上述方案相同。但如何从一个半恶意安全转化为恶意安全仍然是一个公开的问题。

4 协议的更多功能

4.1基于多跳全同态加密方案的安全多方计算

上面的方案都只支持单跳，在2016年，[BP16]、[PS16]构造了多跳的全同态加密方案（动态多密钥全同态加密方案），即在一组密钥下的密文（扩展密文）在增加若干个私钥后仍然可以进行同态运算。其中[BP16]利用了自举技术，优点是密文尺寸伴随着密钥个数呈线性增长，密文尺寸小，缺点是在自举过程中操作量过大[7];[PS16]利用加密承诺矩阵来构造多跳全同态加密方案，优点是操作量小，更有效率，缺点是密文尺寸过大且随着密钥个数呈四次增长[8]。基于多跳全同态加密方案的安全多方计算允许在密文同态运算这一阶段加入新的用户。

4.2 基于多比特全同态加密的安全多方计算

在2017年，李增鹏等人基于GSW全同态加密方案构造了两个多比特全同态加密方案，并利用编码技术提出了一个新的密文扩张方案，可以以此为基础构造了一个两轮的安全多方计算协议。该协议在面对一个恶意敌手是安全的[9]。

4.3 抵抗混合型敌手的安全多方计算协议

混合型敌手指的是集合（A Sh，A Sm，A Fc），代表的是在一组被敌手腐败的参与方中，有一部分是被半诚实敌手腐败，有一部分是被半恶意敌手腐败，有一部分是腐败失败（懒惰的参与方）;集合（ASm，A mal，AFc）表示的是在一组被敌手腐败的参与方中，有一部分是被半恶意敌手腐败，有一部分是被恶意敌手腐败，有一部分是腐败失败。其中懒惰的参与方是指协议中途离开的参与方。在[BJMS19]利用{0，1}- LSSSD访问结构和一个非交互的零知识证明系统，证明了在CRS模型中以及分布式设置中的安全多方计算协议，当（Ash，Asm）不属于访问结构时，协议在面对一个混合型敌手（Ash，，Asm，AFc）是安全的。同第三节方案类似，利用非交互的零知识证明，当（AMa;，As）不属于访问结构时，可以将协议转化成在面对一个混合型敌手（ASm，AMal，AFc）是安全的。

5 其他的基于全同态加密的安全多方计算

在2017年，王会勇等人在GSW全同态加密的基础上，利用密钥同态的性质在CRS模型中构造了一个三轮的安全多方计算协议，该方案与上述在CRS模型中的方案相比，优点是不用进行密文扩展操作，缺点是要增加一轮交互用来得到所有参与方的公钥[10]。

在文献[BJMS19]中构造了一个三轮的诚实方占大多数的安全多方计算协议，该协议能够保证每一个诚实的参与方在协议结束之后都可以得到最终的结果，并证明了该协议在面对混合敌手是安全的。

6 结论

在云计算的快速发展下，全同态加密和安全多方计算计算的研究越来越受到入们的重视，在本文中我们对基于GSW全同态加密的安全多方计算做了全面研究，在第二节给出了在CRS模型、分布式设置、无CRS模型中基于GSW全同态加密的安全多方计算协议。在第三节分别给出了不同模型下协议的安全性，在第四节我们给出了安全多方计算协议的更多功能，在第五节给出了其他基于GSW全同态加密的安全多方计算。

参考文献：

[1] YAO A. Protocols for secure computations[C]//Proceedings ofthe 23rd Annual Symposium on Foundations of Computer Sci-ence， New York， USA， 1982： 160-164.

[2] Stehle D， Steinfe R. Making NTRU as secure as worst-caseproblems over ideal lattic[Cy/Advances in Cryptology-EURO-CRYPT 2011， Tallinn， Estonia， 2011： 27-47.

[3]P. Mukherjee，D.Wichs. Two Round Multiparty Computationvia Multi-key FHE[[C]. M. Fischlin，J.-S. Coron. EURO-CRYPT 2016， Part ll. Springer， Heidelberg， 2016， 9666： 735- 763.

[4] M. Clear， C. McGoldrick. Multi-identity and Multi-key Lev- eled FHE from Leaming with Errors[C].R. Gennaro， M. J. B. Robsha，v. CRYPT0 2015， Part lI. Springer，Heidelberg， 2015，9216：630 ～ 65.

[5] Zvika Brakerski. Shai Halevi， and Antigoni Polychroniadou.Four round secure computat-ion without setup// TCC2017：lnTheory of Cryptography， Baltimore， MD， USA， 2017：678-710.

[6] Kim E ， Lee H S ， Park J . Towards Round-Optimal SecureMultiparty Computations： Multikey FHE Without a CRS[M].Information Security and Privacy. Springer， Cham， 2018：101-113 .

[7] Z. Brakerski and R. Perlman. Lattice based fully dynamicmulti key FHE with short ciphertexts. key FHE with short ci-phertexts. In CRYPTO， 2016： 190 ～ 213.

[8] Sina Shiehian. Multi-Key FHE from LWE， Revisited. 2016.

[9] Li Z ， Ma C ， Morais E . et al. Multi-bit Leveled Homomor-phic Encryption via DuaI.LWE -Based[Cy]/lntemational Con-ference on Information Security and Cryptology， Seoul， Korea2017：221-242.

[10] WANG Hui-yong FENG Yong ZHAO Ling-zhong TANG Shi-jie. A Secure Multi-Party Computation Protocol on the Ba-sis of Multi-Key Homomorphism[J]. JSCUT（Natural ScienceEdition）， 2017， 45（7）： 69-76.

基金項目：广州市教育局协同创新重大项目（1201610005）

作者简介：李习习（1996-），女，安徽萧县人，学生，硕士，主要研究方向为全同态加密与安全多方计算;胡业周（1996-），男，安徽明光人，学生，硕士，主要研究方向为全同态加密与安全多方计算。