多方免密钥协商加密计算探究
2016-09-20杨宾四川大学计算机学院成都610065
杨宾（四川大学计算机学院，成都 610065）
多方免密钥协商加密计算探究
杨宾
（四川大学计算机学院，成都610065）
0 引言
云计算是一种全新的在线计算模式，它是基于互联网服务相关的使用和交付模式。根据美国国家标准与技术研究院（NIST）定义：云计算是一种按使用量付费的模式，这种模式提供可用的、便捷的、按需的网络访问，进入可配置的计算资源共享池（资源包括网络、服务器、存储、应用软件、服务），这些资源能够被快速提供，只需投入很少的管理工作，或与服务供应商进行很少的交互。云计算为企业和个人带来了福音，用户不再需要自己搭建服务平台，只需要向云服务提供商按需购买相应的服务（存储、计算资源），只用很少的费用就能得到巨大的计算能力。云服务减少了用户的系统管理、维护成本，并且避免了安全风险，收益大。云计算模式引起了商业领域、企业经营的大变革。
虽然云计算服务发展迅速，但云端的用户隐私数据一直令人担忧。云服务提供商的面前，用户一直出于弱势地位。虽然服务商一在承诺会保护数据隐私，但是并不能排除黑客攻击或者内部管理人员为了一己私利贩卖数据库的用户数据。大量企业不敢将自己的数据存储到云端，担心服务商有意无意的使用自己的企业数据，泄漏商业秘密。数据泄漏已经严重阻碍到云计算服务的使用。一般的数据保护方式是采用数据加密，将数据库的数据加密存储。如果数据库被拷贝，没有密钥，数据也不会被解密泄漏，但是会增加数据操作复杂性：
①每一次操作之前，需要解密数据：m=D（c）；
②操作数据：m'=F（m）；
③操作完成之后，必须再一次加密数据：c'=E （m'）。
安全永远和效率是负相关，追求数据安全性，必将导致数据处理效率降低。每一次操作都将进行一次数据加密，处理时间将会严重浪费在加解密算法里面，真正用于数据处理的CPU时间将会变少。另一个问题是密钥存储问题，密钥必须交给服务提供商，他们可以自行决定是否对加密数据解密，“监守自盗”的可能性并没有被排除。直接在密文上面进行数据处理的同态加密应运而生。
1 同态加密
同态加密的定义可以描述为对于明文数据m1，m2加密，可以在它们对应的密文之上进行如下操作⊙。操作的结果解密之后，同直接对明文的操作值一样。
1.1同态加密的发展
同态加密的概念的首次提出是1978年，Rivest，Adleman，Dertouzos在文献[1]中为了解决明文的泄露问题，采用的一种同时具有加法同态和乘法同态的算法。但是该方案和随后的改进方案都不能有效克制密文膨胀，导致复杂度升高，效率和安全性较低，不能抗已知明文攻击。之后全同态加密成为了密码学一个研究热点，一个开放的难题。直到2009年，由Gentry在文献[2]构造了第一个在格上的完备理论的全同态加密方案。通过“稀疏子集和”问题的假设，从而在进行各种密文操作的之后依靠自己的解密函数进行同态解密，降低了密文噪声的增长，最终在这种假设下获得全同态加密的理论基础。Gentry为全同态加密开启了一扇大门，根据他的理论产生了多种改进方案[3-4]。但是由于同态解密无论怎么改进，效率依然十分低下，产生了基于LWE和RLWE的问题的同态加密方案[5-8]，不再需要进行同态解密技术，使用密钥交换技术和模交换技术就能很好地控制密文的维数增长和密文的噪声增长。
1.2NTRU 同态加密
NTRU最先由Jeffrey，Jill等人提出的一种公钥加密[9]。它的困难问题是在格中寻找最短向量（SVP）的数学难题。格是一组在Rm中n个线性无关向量的整系数集合。表示为：
其中b1，b2，b3…bn是在Rn空间中一组线性无关向量，它们共同构成了格L的一组基。格可以有不同的基表示，一个格的基并不唯一。
最短向量问题[10]：B∈Zn×m是格L的一组基，在格L （B）中的寻找一个非零向量Bx，使得||Bx||≤||By||，对任意的向量y∈Zm均成立。
NTRU是构建在环上，通过多项式在环上进行各类操作。它只涉及了简单的模乘法运算和模求逆运算，没有大数因式分解和离散对数等大量运算，所以NTRU的效率更高，加、解密运算速度显著。它的困难问题又是格上最短向量问题，在维数较大的格里，具有抗量子计算能力。另外在全同态技术还不具有实用意义的时候，NTRU作为部分同态加密方案（somewhat
homomorphic encryption or partially homomorphic en-cryption），针对加法乘法的同态操作有天然优势。
1.3安全多方计算
安全多方计算（SMC）是一种协同计算模式，希望在各个互不信任的参与方共同参加一种计算，但是不会把自己的输入泄露给其他参与者。每个参与者将输入数据提交给可信的第三方进行计算，计算完成之后，将结果返回给所有参与者，但是参与共同计算的时候不止要对其他参与者保密，同时也要对第三方计算平台保密。因为现实里，并没有完全可信的第三方。多方计算的SMC模型由以下四个方面组成：参与方、安全性定义、通信网模型、信息论安全与密码学安全。
为了保护在云端的数据安全，不希望透露给任何人，包括参与者和第三方云服务商。所有存放在云端的数据采用同态加密，云服务商只能对密文进行计算。参与方产生自己的密钥，将自己的数据进行加密之后，交给第三方进行计算。计算完毕之后，得到结果。在公钥加密体制内，参与方在加密之前需要进行密钥协商，密钥协商会导致一系列问题。（1）密钥协商需要花费额外的时间。（2）在互联网上海量的参与者进行密钥协商会增加许多不确定的因素。针对以上问题，本文提出了多方免协商加密计算，来破除密钥协商增加的时间复杂度。
2 多方免协商加密计算
通过NTRU的同态特性将云端数据加密之后进行有效的计算，利用经典的SHA-1哈希算法对参与方生成自己的数据计算哈希值，使得密文具有自己的独立特性。对明文数据进行双重加密，一层是NTRU，保护数据的安全性和同态性。另外一层是哈希算法，增加数据的身份特性，这样对参与计算的用户，拥有独立的解密权，没有参与的用户无法解密结果。
2.1数据解密过程
典型的NTRU方案参考文献[11]，NTRU是构建在商环Ζ[χ]/（χN-1）。公钥是Η=αFa*Β（mod β），私钥Α∈Lf，Β∈Lg，Lf，Lg是整系数多项式。N，α，β取整数，β为2的幂次方且β>>α。
①密钥生成：随机任意选择3个多项式A，B和D，A和 B分别关于 mod α，mod β的可逆多项式 Fα，Fβ，D∈Lg。
2.2多方计算过程
每一个参与方必须使用一样的加密和解密策略来处理数据。加密之后将
①暂时抹去身份痕迹：c1=c1-s1；c2=c2-s2
②计算数据：c3=c1⊙c2（⊙在NTRU加密方案中可以为加法同态或者乘法同态），s3=s1*s2，c3=c3+s3
③返回结果：
上例中只有参与者有查看的权利，其他任何人都不能正确地解密结果，包括云计算提供商。
2.3正确性证明我们分别以加法同态和乘法同态进行验证。（1）加法同态性证明
3 结语
多方免密钥协商加密计算能够将完全将输入和输出加密。输入只有一个参与方能够正确解密，所有参与方可以解密输出。通过哈希函数为每一个参与方设置身份标识，身份标识不需要和其他参与方进行协商，加密过程的时候，为每一个加密数据保留自己身份痕迹。只要输出存在自己的身份痕迹，参与方就能正确解密数据。本文的加密安全性来自于格的SVP问题，能够对抗量子计算。云计算方只能按部就班进行同态运算，完全不了解参与运算的数据和运算结果，保护了存放在云端的隐私数据。同时参与方之间根本不知道对方的输入值，达到了安全多方计算的根本要求。但是本方案存在一些不足之处，1）SHA-1最大的抗冲突性为280，如果在大量的参与方存在的情况下，由于生日悖论存在，攻击者的哈希值猜测的哈希冲突会得到很大的提升，使得没有查看计算结果的攻击者，有机会查看计算结果。2）哈希函数的增加会导致一定的数据膨胀。
[1]Rivest R，Adleman L，Dertouzos M.On Data Banks and Privacy Homomorphisms[M].[S.l.]:Academic Press，1978:169-177.
[2]GENTRY C.Fully Homomorphic Encryption Using Ideal Lattices［C］.ACM，2009:169-178．
[3]van Dijk M，Gentry C，Halevi S，et al.Fully Homomorphic Encryption over the Integers[C].Proc.of Cryptology-CRYPTO'11.[S.l.]: Springer-Verlag，2011:24-43.
[4]Gentry C，Halevi S.Fully Homomorphic Encryption Without Squashing Using Depth-3 Arithmetic Circuits[C].Proc.of FOCSIEEE'11. [S.l.]:Springer-Verlag，2011.
[5]ZvikaBrakerski and Viod Vaikuntanathan.Efficient Fully Homoorphic Encryption from（Standard）lwe.In 2011 52nd Annual IEEE Symposium on Foundations of Computer Science，2011:97-106
[6]Vadim Lyubashevsky，Chris Peikert，Oded Regev.On Ideal Lattices and Learning with Errors Over Rigns.In EUROCRYPT-2010，volume 6110 of LNCS，2010:1-20
[7]Zvika Brakerski,Craig Gentry,Vinod Vaikuntanathan.Fully Homomorphic Encryption without Bootstrapping[C].ACM Transactions on Computation Theory，2014.7:[13:1]-[13:36]
[8]Ruan de Clercq，Sujoy Sinha Roy，Frederik Vercauteren.Efficient Software Implementation of Ring-LWE Encryption[C].EDA Consortium，2015.3:339-344
[9]J.Hoffstein，J.Pipher，J.H.Silverman.NTRU:A Ring-Based Public Key Cryptosystem[C].In:Algorithmic Number Theory（ANTS-III），LNCS 1423，Berlin:Springer-Verlag，June 1998:267-288.
[10]Goldreich o，Goldwasser S，Halevi S.Collision-Free Hashing from Lattice Problems[C].Electronic Colloquium on ComputationalComplexity（ECCC），1996，3（42）:236-241
[11]胡予濮.一个新型的NTRU类数字签名方案[J].计算机学报，2008，31（9）:1661-1666.
Cloud Security;Secure Multi Party Computation;Homomorphic Encryption;NTRU
Research on Encryption Computation of Multi-Party Free-Key Negotiation
YANG Bin
（College of Computer Science，Sichuan University，Chengdu 610065）
1007-1423（2016）07-0012-04
10.3969/j.issn.1007-1423.2016.07.003
杨宾（1989-），男，四川浦江人，硕士研究生，研究方向为信息安全
2016-01-21
2016-02-21
为了保护在云端的隐私数据，改变用户的弱势地位，安全多方计算得到广泛关注。而安全多方计算是需要各方提前进行密钥协商，增加整个多方计算的复杂度和不安全因素。为了解决上述问题，设计一种基于NTRU同态加密的多方免协商计算模型，缩短整个计算的步骤，降低风险。保护隐私数据和计算结果不被云服务商泄露，同时也不会被没有参与过计算的用户知晓计算结果。
云安全；安全多方计算；同态加密；NTRU
In order to protect the privacy of data in the cloud,to change the user's weak position,secure multi-party computation has been widely concerned.Secure multi-party computation is required for all parties for key agreement in advance,which increases the complexity and the unsafe factors of the whole multi-party computation.In order to solve the above problems,designs a method based on NTRU,which is based on the computation model of multi-party free-key negotiation,which shortens the calculation steps and reduces the risk.Privacy preserving data and computing results are not revealed by the cloud service provider,at the same time the user who not be involved in calculating not known results.
