一种NTRU格上基于身份全同态加密体制设计
|
摘要
全同态加密可以用来解决云计算环境中的隐私保护问题,然而现有体制具有系统参数大、效率低的缺点.针对现有攻击技术,首先设计了一种高效的NTRU格上的基于身份公钥加密体制,无需借助额外的安全性假设,具有更高的安全性和更小的系统参数.之后,基于近似特征向量技术,构造了一种高效的全同态加密转化方式.通过将以上两种方法结合,给出了一种高效的基于身份全同态加密体制.和现有体制相比,除了不需要计算密钥、实现了真正意义上的基于身份特性以外,还减小了密钥、密文尺寸,提高了计算和传输效率.
Fully homomorphic encryption can be used to solve privacy concerns for data over cloud,while large parameters and lowefficiency are the universal issues for present schemes. To oppose mainstream attacks,an identity-based public key scheme over NTRU lattice with smaller parameters,higher security level,and without additional security assumptions is put forward. Take advantage of the approximate eigenvector technique,an efficient fully homomorphic encryption transformation method is raised. And by combining the two skills above,an efficient identity-based fully homomorphic encryption scheme is proposed. Compared with existing schemes,the schemes is fully identity-based without evaluation key,and has smaller keys and ciphertext sizes,leading to higher transmission and computational efficiency.
Fully homomorphic encryption can be used to solve privacy concerns for data over cloud,while large parameters and lowefficiency are the universal issues for present schemes. To oppose mainstream attacks,an identity-based public key scheme over NTRU lattice with smaller parameters,higher security level,and without additional security assumptions is put forward. Take advantage of the approximate eigenvector technique,an efficient fully homomorphic encryption transformation method is raised. And by combining the two skills above,an efficient identity-based fully homomorphic encryption scheme is proposed. Compared with existing schemes,the schemes is fully identity-based without evaluation key,and has smaller keys and ciphertext sizes,leading to higher transmission and computational efficiency.
引文
[1] Gentry C. Fully homomorphic encryption using ideal lattices[A]. Proceedings of the 41st Annual ACM Symposium on Theory of Computing[C]. New york:ACM,2009.169-178.
[2] Brakerski Z,Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[A]. Proceedings of the 31st Annual International Cryptology Conference[C]. Berlin:Springer,2011. 505-524.
[3] Brakerski Z,Vaikuntanathan V. Efficient fully homomorphic encryption from(standard)LWE[J]. SIAM Journal on Computing,2014,43(2):831-871.
[4]Brakerski Z,Gentry C,Vaikuntanathan V.(Leveled)Fully homomorphic encryption w ithout bootstrapping[J]. ACM Transactions on Computation Theory,2011,18(3):169
[5]汤殿华,祝世雄,王林,等.基于RLWE的全同态加密方案[J].通信学报,2014,35(1):173-182.TANG DH,ZHU SX,WANG L,et al. Fully homomorphic encryption scheme from RLWE[J]. Journal of Communications,2014,35(1):173-182.(in Chinese)
[6]Zhang P,Yu JP,Wang T. A homomorphic aggregate signature scheme based on lattice[J]. Chinese Journal of Electronics,2012,21(4):701-704.
[7]Gentry C,Groth J,Ishai Y,et al. Using fully homomorphic hybrid encryption to minimize non-interative zero-know ledge proof[J]. Journal of Cryptology,2015,28(4):820-843.
[8] Ducas L,Micciancio D. FHEW:Bootstrapping homomorphic encryption in less than a second[A]. Proceeding of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2015. 617-640.
[9]Gorbunov S,Vaikuntanathan V,Wichs D. Leveled fully homomorphic signatures from standard lattices[A]. Proceedings of the 47th Annual ACM on Symposium on Theory of Computing[C]. New york:ACM,2015. 469-477.
[10] Peikert C,Shiehian S. Multi-key FHE from LWE,revisited[A]. Proceedings of the 13th IACR Theory of Cryptography Conference[C]. Berlin:Springer,2016. 217-238.
[11]Benhamouda F,Lepoint T,Mathieu C,et al. Optimization of bootstrapping in circuits[A]. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms[C]. New york:ACM,2017. 2423-2433.
[12]陈振华,李顺东,王道顺,等.集合成员关系的安全多方计算及其应用[J].电子学报,2017,45(5):1109-1116.CHEN ZH,LI SD,WANG DS,et al. Secure multiparty computation of set membership and its applications[J].Acta Electronica Sinica,2017,45(5):1109-1116.(in Chinese)
[13]Chen H,Hu YP,Lian ZZ. Properties of SV-style homomorphic encryption and their application[J]. Chinese Journal of Electronics,2017,26(5):926-932.
[14]Regev O. On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM,2009,56(6):34.
[15]光焱,祝跃飞,费金龙,等.利用容错学习问题构造基于身份的全同态加密体制[J].通信学报,2014,35(2):111-117.Guang Y,Zhu YF,Fei JL,et al. Identity-based fully homomorphic encryption from learning w ith error problem[J]. Journal of Communications,2014,35(2):111-117.(in Chinese)
[16] Gentry C,Sahai A,Waters B. Homomorphic encryption from learning w ith errors:Conceptually-simpler,asymptotically-faster,attribute-based[A]. Proceedings of the33rd Annual International Cryptology Conference[C].Berlin:Springer,2013. 75-92.
[17]Hoffstein J,Pipher J,Silverman JH. NTRU:A ring-based public key cryptosystem[A]. Proceeding of the 3rd International Algorithmic Number Theory Symposium[C].Berlin:Springer,1998. 267-288.
[18] Lyubashevsky V,Peikert C,Regev O. On ideal lattices and learning w ith errors over rings[J]. Journal of the ACM,2013,60(6):43.
[19]StehléD,Steinfeld R. Making NTRU as secure as worstcase problems over ideal lattices[A]. Proceedings of the30th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2011. 27-47.
[20] Ducas L,Lyubashevsky V,Prest T. Efficient identitybased encryption over NTRU lattices[A]. Proceedings of the 20th Annual International Conference on the Theory and Application of Cryptology and Information Security[C]. Berlin:Springer,2014. 22-41.
[21]Peikert C. A decade of lattice cryptography[J]. Foundations and Trends in Theoretical Computer Science,2016,10(4):283-424.
[22]Lyubashevsky V,Prest T. Quadratic time,linear space algorithms for gram-schmidt orthogonalization and gaussian sampling in structured lattices[A]. Proceedings of the34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2015. 789-815.
[23]Lyubashevsky V,Peikert C,Regev O. A toolkit for ringLWE cryptography[A]. Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2013.35-54.
[24]Ducas L,Nguyen PQ. Faster gaussian lattice sampling using lazy floating-point arithmetic[A]. Proceedings of the18th Annual International Conference on the Theory and Application of Cryptology and Information Security[C].Berlin:Springer,2012. 415-432.
[25]Kirchner P,Fouque PA. An improved BKW algorithm for LWE w ith applications to cryptography and lattices[A].Proceedings of the 35th Annual International Cryptology Conference[C]. Berlin:Springer,2015. 43-62.
[26]Lepoint T,Naehrig M. A comparison of the homomorphic encryption schemes FV,and YASHE[A]. Proceedings of the 7th International Conference on Cryptology in Africa[C]. Berlin:Springer,2014. 318-335.
[27] Gama N,Nguyen PQ. Predicting lattice reduction[A].Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2008. 31-51.
[28] Micciancio D,Regev O. Lattice-Based Cryptography[M]. Berlin:Springer,2011. 713-715.
[29]Lindner R,Peikert C. Better key sizes(and attacks)for LWE-based encryption[A]. Proceedings of the 11th International Conference on Topics in Cryptology[C]. Berlin:Springer,2011. 319-339.
[30]Gama N,Nguyen PQ,Regev O. Lattice enumeration using extreme pruning[A]. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2010. 257-278.
[31]Becker A,Ducas L,Gama N,et al. New directions in nearest neighbor searching w ith applications to lattice sieving[A]. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms[C]. New york:ACM,2016. 10-24.
[32]Chen Y,Nguyen PQ. BKZ 2. 0:Better lattice security estimates[A]. Proceeding of the 17th International Conference on the Theory and Application of Cryptology and Information Security[C]. Berlin:Springer,2011. 1-20.
[33] Aono Y,Wang YT,Hayashi T,et al. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[A]. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2016.789-819.
[34]Albrecht MR,Player R,Scott S. On the concrete hardness of learning w ith errors[J]. Journal of M athematical Cryptology,2015,9(3):169-203.
[35]辛丹,顾纯祥,郑永辉,等.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):2887-2893.XIN D,GU CX,ZHENG YH,et al. Identity-based fully homomorphic encryption from ring learning w ith errors problem[J]. Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)
[36] Micciancio D,Peikert C. Trapdoors for lattices:Simpler,tighter,faster,smaller[A]. Proceedings of the 31th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2012. 700-718.
[37]康元基,顾纯祥,郑永辉,等.利用特征向量构造基于身份的全同态加密体制[J].软件学报,2016,27(6):1487-1497.KANG YJ,GU CX,ZHENG YH,et al. Identity-based fully homomorphic encryption from eigenvector[J]. Journal of Softw are,2016,27(6):1487-1497.(in Chinese)
[2] Brakerski Z,Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[A]. Proceedings of the 31st Annual International Cryptology Conference[C]. Berlin:Springer,2011. 505-524.
[3] Brakerski Z,Vaikuntanathan V. Efficient fully homomorphic encryption from(standard)LWE[J]. SIAM Journal on Computing,2014,43(2):831-871.
[4]Brakerski Z,Gentry C,Vaikuntanathan V.(Leveled)Fully homomorphic encryption w ithout bootstrapping[J]. ACM Transactions on Computation Theory,2011,18(3):169
[5]汤殿华,祝世雄,王林,等.基于RLWE的全同态加密方案[J].通信学报,2014,35(1):173-182.TANG DH,ZHU SX,WANG L,et al. Fully homomorphic encryption scheme from RLWE[J]. Journal of Communications,2014,35(1):173-182.(in Chinese)
[6]Zhang P,Yu JP,Wang T. A homomorphic aggregate signature scheme based on lattice[J]. Chinese Journal of Electronics,2012,21(4):701-704.
[7]Gentry C,Groth J,Ishai Y,et al. Using fully homomorphic hybrid encryption to minimize non-interative zero-know ledge proof[J]. Journal of Cryptology,2015,28(4):820-843.
[8] Ducas L,Micciancio D. FHEW:Bootstrapping homomorphic encryption in less than a second[A]. Proceeding of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2015. 617-640.
[9]Gorbunov S,Vaikuntanathan V,Wichs D. Leveled fully homomorphic signatures from standard lattices[A]. Proceedings of the 47th Annual ACM on Symposium on Theory of Computing[C]. New york:ACM,2015. 469-477.
[10] Peikert C,Shiehian S. Multi-key FHE from LWE,revisited[A]. Proceedings of the 13th IACR Theory of Cryptography Conference[C]. Berlin:Springer,2016. 217-238.
[11]Benhamouda F,Lepoint T,Mathieu C,et al. Optimization of bootstrapping in circuits[A]. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms[C]. New york:ACM,2017. 2423-2433.
[12]陈振华,李顺东,王道顺,等.集合成员关系的安全多方计算及其应用[J].电子学报,2017,45(5):1109-1116.CHEN ZH,LI SD,WANG DS,et al. Secure multiparty computation of set membership and its applications[J].Acta Electronica Sinica,2017,45(5):1109-1116.(in Chinese)
[13]Chen H,Hu YP,Lian ZZ. Properties of SV-style homomorphic encryption and their application[J]. Chinese Journal of Electronics,2017,26(5):926-932.
[14]Regev O. On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM,2009,56(6):34.
[15]光焱,祝跃飞,费金龙,等.利用容错学习问题构造基于身份的全同态加密体制[J].通信学报,2014,35(2):111-117.Guang Y,Zhu YF,Fei JL,et al. Identity-based fully homomorphic encryption from learning w ith error problem[J]. Journal of Communications,2014,35(2):111-117.(in Chinese)
[16] Gentry C,Sahai A,Waters B. Homomorphic encryption from learning w ith errors:Conceptually-simpler,asymptotically-faster,attribute-based[A]. Proceedings of the33rd Annual International Cryptology Conference[C].Berlin:Springer,2013. 75-92.
[17]Hoffstein J,Pipher J,Silverman JH. NTRU:A ring-based public key cryptosystem[A]. Proceeding of the 3rd International Algorithmic Number Theory Symposium[C].Berlin:Springer,1998. 267-288.
[18] Lyubashevsky V,Peikert C,Regev O. On ideal lattices and learning w ith errors over rings[J]. Journal of the ACM,2013,60(6):43.
[19]StehléD,Steinfeld R. Making NTRU as secure as worstcase problems over ideal lattices[A]. Proceedings of the30th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2011. 27-47.
[20] Ducas L,Lyubashevsky V,Prest T. Efficient identitybased encryption over NTRU lattices[A]. Proceedings of the 20th Annual International Conference on the Theory and Application of Cryptology and Information Security[C]. Berlin:Springer,2014. 22-41.
[21]Peikert C. A decade of lattice cryptography[J]. Foundations and Trends in Theoretical Computer Science,2016,10(4):283-424.
[22]Lyubashevsky V,Prest T. Quadratic time,linear space algorithms for gram-schmidt orthogonalization and gaussian sampling in structured lattices[A]. Proceedings of the34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2015. 789-815.
[23]Lyubashevsky V,Peikert C,Regev O. A toolkit for ringLWE cryptography[A]. Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2013.35-54.
[24]Ducas L,Nguyen PQ. Faster gaussian lattice sampling using lazy floating-point arithmetic[A]. Proceedings of the18th Annual International Conference on the Theory and Application of Cryptology and Information Security[C].Berlin:Springer,2012. 415-432.
[25]Kirchner P,Fouque PA. An improved BKW algorithm for LWE w ith applications to cryptography and lattices[A].Proceedings of the 35th Annual International Cryptology Conference[C]. Berlin:Springer,2015. 43-62.
[26]Lepoint T,Naehrig M. A comparison of the homomorphic encryption schemes FV,and YASHE[A]. Proceedings of the 7th International Conference on Cryptology in Africa[C]. Berlin:Springer,2014. 318-335.
[27] Gama N,Nguyen PQ. Predicting lattice reduction[A].Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2008. 31-51.
[28] Micciancio D,Regev O. Lattice-Based Cryptography[M]. Berlin:Springer,2011. 713-715.
[29]Lindner R,Peikert C. Better key sizes(and attacks)for LWE-based encryption[A]. Proceedings of the 11th International Conference on Topics in Cryptology[C]. Berlin:Springer,2011. 319-339.
[30]Gama N,Nguyen PQ,Regev O. Lattice enumeration using extreme pruning[A]. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2010. 257-278.
[31]Becker A,Ducas L,Gama N,et al. New directions in nearest neighbor searching w ith applications to lattice sieving[A]. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms[C]. New york:ACM,2016. 10-24.
[32]Chen Y,Nguyen PQ. BKZ 2. 0:Better lattice security estimates[A]. Proceeding of the 17th International Conference on the Theory and Application of Cryptology and Information Security[C]. Berlin:Springer,2011. 1-20.
[33] Aono Y,Wang YT,Hayashi T,et al. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[A]. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2016.789-819.
[34]Albrecht MR,Player R,Scott S. On the concrete hardness of learning w ith errors[J]. Journal of M athematical Cryptology,2015,9(3):169-203.
[35]辛丹,顾纯祥,郑永辉,等.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):2887-2893.XIN D,GU CX,ZHENG YH,et al. Identity-based fully homomorphic encryption from ring learning w ith errors problem[J]. Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)
[36] Micciancio D,Peikert C. Trapdoors for lattices:Simpler,tighter,faster,smaller[A]. Proceedings of the 31th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C]. Berlin:Springer,2012. 700-718.
[37]康元基,顾纯祥,郑永辉,等.利用特征向量构造基于身份的全同态加密体制[J].软件学报,2016,27(6):1487-1497.KANG YJ,GU CX,ZHENG YH,et al. Identity-based fully homomorphic encryption from eigenvector[J]. Journal of Softw are,2016,27(6):1487-1497.(in Chinese)