基于NTRU的全同态加密方案
|
摘要
本文提出一种基于公钥密码体制(Number Theory Research Unit,NTRU)选择明文攻击(Chosen Plaintext Attack,CPA)可证明安全的全同态加密方案.首先,对NTRU的密钥生成算法进行改进,通过格上的高斯抽象算法生成密钥对,避免了有效的格攻击,同时,没有改变密钥的分布.然后,基于改进的NTRU加密算法,利用Flattening技术,构造了一个全同态加密体制,并在标准模型下证明方案是选择明文攻击不可区分性IND-CPA安全的.
A fully homomorphic encrgption scheme was presented based on number theory research unit( NTRU),which is provable security about indistinguishable chosen plaintext attack( IND-CPA). Firstly, to avoid the effective lattice attacks,we modified the key generation algorithm of NTRU by Gaussian abstraction algorithm of lattices, and the distribution of the key is not changed. Then,we proposed a new homomorphic encryption scheme based on the improved NTRU encryption algorithm by using the Flattening technique. Its IND-CPA security was proved strictly under the standard model.
A fully homomorphic encrgption scheme was presented based on number theory research unit( NTRU),which is provable security about indistinguishable chosen plaintext attack( IND-CPA). Firstly, to avoid the effective lattice attacks,we modified the key generation algorithm of NTRU by Gaussian abstraction algorithm of lattices, and the distribution of the key is not changed. Then,we proposed a new homomorphic encryption scheme based on the improved NTRU encryption algorithm by using the Flattening technique. Its IND-CPA security was proved strictly under the standard model.
引文
[1]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[A].Foundations of Secure Computation[C].USA:Academia Press,1978.169-179.
[2]GAMAL T E.A public key cryptosystem and a signature scheme based on discrete logarithms[A].Proceedings of CRYPTO 84 on Advances in Cryptology[C].New York:Springer-Verlag,1985.10-18.
[3]GOLDWASSER S,MICALI S.Probabilistic encryption&how to play mental poker keeping secret all partial information[A].Proceedings of Fourteenth ACM Symposium on Theory of Computing[C].New York:ACM,1982.365-377.
[4]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[J].Lecture Notes in Computer Science,1999,547(1):223-238.
[5]RIVEST R,SHAMIR A,ADLEMAN L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,26(2):96-99.
[6]GENTRY C.A Fully Homomorphic Encryption Scheme[D].USA:Stanford University,2009.
[7]DIJK M V,GENTRY C,HALEVI S,et al.Fully homomorphic encryption over the integers[J].Lecture Notes in Computer Science,2009,(4):24-43.
[8]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from(standard)LWE[A].Proceedings of Foundations of Computer Science[C].USA:IEEE,2010.97-106.
[9]MANDAL A,TIBOUCHI M.Fully homomorphic encryption over the integers w ith shorter public keys[A].Proceedings of Conference on Advances in Cryptology[C].New York:Springer-Verlag,2011.487-504.
[10]CORON J,NACCACHE D,TIBOUCHI M.Public key compression and modulus sw itching for fully homomorphic encryption over the integers[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques[C].New York:Springer-Verlag,2012.446-464.
[11]YAGISAWA M.Fully homomorphic encryption without bootstrapping[J].ACM Transactions on Computation Theory,2015,6(3):1-36.
[12]HALEVI S,SHOUP V.HElib,Homomorphic Encryption Library[OL].http://shaih.github.io/HElib/,2012.
[13]李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803.LI Shun-dong,WANG Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese)
[14]辛丹,顾纯祥,郑永辉,光焱,康元基.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):442887-2893.XIN Dan,GU Chun-xiang,ZHENG Yong-hui,GUANG Yan,KANG Yuan-ji.Identity-based fully homomorphic encryption from ring learning w ith errors problem[J].Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)
[15]CHEN H,YUPU H,LIAN Z.Double batch for RLWEbased leveled fully homomorphic encryption[J].Chinese Journal of Electronics,2015,24(3):661-666.
[16]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring-based public key cryptosystem[A].Proceedings of the 3rd International Symposium on Algorithmic Number Theory[C].Berlin:Springer,1998.267-288.
[17]杨铭,曹云飞.NTRU的应用前景分析及展望[J].信息安全与通信保密,2007,(8):36-38.YANG M ing,CAO Yun-fei.Application prospect and analysis of NTRU[J].Information Security and Communications Privacy,2007,(8):36-38.(in Chinese)
[18]TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[A].Proceedings of Forty-Fourth ACM Symposium on Theory of Computing[C].New York,ACM,2012.1219-1234.
[19]GENTRY C,SAHAI A,WATERS B.Homomorphic Encryption from Learning w ith Errors:Conceptually-Simpler,Asymptotically-Faster,Attribute-Based[M].Berlin:Springer,2013.75-92.
[20]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[A].Proceedings of DBLP[C].Germany:DBLP,2008.197-206.
[21]LYUBASHEVSHY V,PEIKERT C,REGEV O.On ideal lattice and learning w ith errors over rings[A].Proceedings of Eurocrypt 2010[C].New York:Springer-Verlag,2010.1-23.
[22]张建航,贺健,胡予濮.基于R-LWE问题的新型NTRU加密方案[J].电子科技,2012,25(5):76-78.ZHANG Jian-hang,HE Jian,HU Yu-pu.A novel NTRU encryption scheme based on R-LWE problem[J].Electronic Science and Technology,2012,25(5):76-78.(in Chinese)
[23]STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology[C].New York:Springer-Verlag,2011.27-47.
[2]GAMAL T E.A public key cryptosystem and a signature scheme based on discrete logarithms[A].Proceedings of CRYPTO 84 on Advances in Cryptology[C].New York:Springer-Verlag,1985.10-18.
[3]GOLDWASSER S,MICALI S.Probabilistic encryption&how to play mental poker keeping secret all partial information[A].Proceedings of Fourteenth ACM Symposium on Theory of Computing[C].New York:ACM,1982.365-377.
[4]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[J].Lecture Notes in Computer Science,1999,547(1):223-238.
[5]RIVEST R,SHAMIR A,ADLEMAN L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,26(2):96-99.
[6]GENTRY C.A Fully Homomorphic Encryption Scheme[D].USA:Stanford University,2009.
[7]DIJK M V,GENTRY C,HALEVI S,et al.Fully homomorphic encryption over the integers[J].Lecture Notes in Computer Science,2009,(4):24-43.
[8]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from(standard)LWE[A].Proceedings of Foundations of Computer Science[C].USA:IEEE,2010.97-106.
[9]MANDAL A,TIBOUCHI M.Fully homomorphic encryption over the integers w ith shorter public keys[A].Proceedings of Conference on Advances in Cryptology[C].New York:Springer-Verlag,2011.487-504.
[10]CORON J,NACCACHE D,TIBOUCHI M.Public key compression and modulus sw itching for fully homomorphic encryption over the integers[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques[C].New York:Springer-Verlag,2012.446-464.
[11]YAGISAWA M.Fully homomorphic encryption without bootstrapping[J].ACM Transactions on Computation Theory,2015,6(3):1-36.
[12]HALEVI S,SHOUP V.HElib,Homomorphic Encryption Library[OL].http://shaih.github.io/HElib/,2012.
[13]李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803.LI Shun-dong,WANG Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese)
[14]辛丹,顾纯祥,郑永辉,光焱,康元基.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):442887-2893.XIN Dan,GU Chun-xiang,ZHENG Yong-hui,GUANG Yan,KANG Yuan-ji.Identity-based fully homomorphic encryption from ring learning w ith errors problem[J].Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)
[15]CHEN H,YUPU H,LIAN Z.Double batch for RLWEbased leveled fully homomorphic encryption[J].Chinese Journal of Electronics,2015,24(3):661-666.
[16]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring-based public key cryptosystem[A].Proceedings of the 3rd International Symposium on Algorithmic Number Theory[C].Berlin:Springer,1998.267-288.
[17]杨铭,曹云飞.NTRU的应用前景分析及展望[J].信息安全与通信保密,2007,(8):36-38.YANG M ing,CAO Yun-fei.Application prospect and analysis of NTRU[J].Information Security and Communications Privacy,2007,(8):36-38.(in Chinese)
[18]TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[A].Proceedings of Forty-Fourth ACM Symposium on Theory of Computing[C].New York,ACM,2012.1219-1234.
[19]GENTRY C,SAHAI A,WATERS B.Homomorphic Encryption from Learning w ith Errors:Conceptually-Simpler,Asymptotically-Faster,Attribute-Based[M].Berlin:Springer,2013.75-92.
[20]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[A].Proceedings of DBLP[C].Germany:DBLP,2008.197-206.
[21]LYUBASHEVSHY V,PEIKERT C,REGEV O.On ideal lattice and learning w ith errors over rings[A].Proceedings of Eurocrypt 2010[C].New York:Springer-Verlag,2010.1-23.
[22]张建航,贺健,胡予濮.基于R-LWE问题的新型NTRU加密方案[J].电子科技,2012,25(5):76-78.ZHANG Jian-hang,HE Jian,HU Yu-pu.A novel NTRU encryption scheme based on R-LWE problem[J].Electronic Science and Technology,2012,25(5):76-78.(in Chinese)
[23]STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology[C].New York:Springer-Verlag,2011.27-47.