微信服务号

微信订阅号

2025-6-3- 22
Home > Archive>Volume 26, Issue 10, 2015 >2696-2719. DOI:10.13328/j.cnki.jos.004808
PDF HTML XML Export Cite reminder
Fully Homomorphic Encryption from Approximate Ideal Lattices
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [71]
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Constructing efficient and secured fully homomorphic encryption is still an open problem. By generalizing approximate GCD to approximate ideal lattice, a somewhat homomorphic encryption scheme is first presented based on partial approximate ideal lattice problem (PAILP) over the integers. The scheme is then converted it into a fully homomorphic encryption scheme (FHE) by applying Gentry's bootstrappable techniques. Next, the security of the somewhat homomorphic encryption scheme is reduced to solving a partial approximate ideal lattice problem. Furthermore, a PAILP-based batch FHE and an AILP-based FHE are constructed. Finally, the PAILP/AILP-based FHE is implemented, and the performance of the proposed scheme is demonstrated to be better than that of previous schemes by computational experimental.

    Reference
    [1] Gentry C. Fully homomorphic encryption using ideal lattices. In: Mitzenmacher M, ed. Proc. of the 41st Annual ACM Symp. on Theory of Computing (STOC 2009). New York: Association for Computing Machinery, 2009. 169-178. [doi: 10.1145/1536414. 1536440]
    [2] van Dijk M, Gentry C, Halevi S, Vaikuntanathan V. Fully homomorphic encryption over the integers. In: Gilbert H, ed. Proc. of the EUROCRYPT 2010. LNCS 6110, Heidelberg: Springer-Verlag, 2010. 24-43. [doi: 10.1007/978-3-642-13190-5_2]
    [3] Smart NP, Vercauteren F. Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen PQ, Pointcheval D, eds. Proc. of the Public Key Cryptography (PKC 2010). LNCS 6056, Heidelberg: Springer-Verlag, 2010. 420-443. [doi: 10.1007/978-3-642-13013-7_25]
    [4] Coron JS, Mandal A, Naccache D, Tibouchi M. Fully homomorphic encryption over the integers with shorter public keys. In: Rogaway P, ed. Proc. of the CRYPTO 2011. LNCS 6841, Heidelberg: Springer-Verlag, 2011. 487-504. [doi: 10.1007/978-3-642- 22792-9_28]
    [5] Coron JS, Naccache D, Tibouchi M. Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval D, Johansson T, eds. Proc. of the EUROCRYPT 2012. LNCS 7237, Heidelberg: Springer-Verlag, 2012. 446-464. [doi: 10.1007/978-3-642-29011-4_27]
    [6] Cheon JH, Coron JS, Kim J, Lee MS, Lepoint T, Tibouchi M, Yun A. Batch fully homomorphic encryption over the integers. In: Johansson T, Nguyen P, eds. Proc. of the EUROCRYPT 2013. LNCS 7881, Heidelberg: Springer-Verlag, 2013. 315-335. [doi: 10. 1007/978-3-642-38348-9_20]
    [7] Gentry C, Halevi S. Implementing Gentry's fully-homomorphic encryption scheme. In: Paterson KG, ed. Proc. of the EUROCRYPT 2011. LNCS 6632, Heidelberg: Springer-Verlag, 2011. 129-148. [doi: 10.1007/978-3-642-20465-4_9]
    [8] Gentry C, Halevi S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In: Proc. of the 2011 IEEE 52nd Annual Symp. on Foundations of Computer Science (FOCS 2011). Washington: IEEE Computer Society, 2011. 107-116. [doi: 10.1109/FOCS.2011.94]
    [9] Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway P, ed. Proc. of the CRYPTO 2011. LNCS 6841, Heidelberg: Springer-Verlag, 2011. 505-524. [doi: 10.1007/978-3-642- 22792-9_29]
    [10] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (Standard) LWE. In: Proc. of the 2011 IEEE 52nd Annual Symp. on Foundations of Computer Science (FOCS 2011). Washington: IEEE Computer Society, 2011. 97-106. [doi: 10. 1109/FOCS.2011.12]
    [11] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) Fully homomorphic encryption without bootstrapping. In: Proc. of the 3rd Innovations in Theoretical Computer Science Conf. (ITCS 2012). New York: Association for Computing Machinery, 2012. 309-325. [doi: 10.1145/2090236.2090262]
    [12] Gentry C, Halevi S, Smart NP. Better bootstrapping in fully homomorphic encryption. In: Fischlin M, Buchmann J, Manulis M, eds. Proc. of the Public Key Cryptography (PKC 2012). LNCS 7293, Heidelberg: Springer-Verlag, 2012. 1-16. [doi: 10.1007/978-3- 642-30057-8_1]
    [13] Gentry C, Halevi S, Smart NP. Fully homomorphic encryption with polylog overhead. In: Pointcheval D, Johansson T, eds. Proc. of the EUROCRYPT 2012. LNCS 7237, Heidelberg: Springer-Verlag, 2012. 465-482. [doi: 10.1007/978-3-642-29011-4_28]
    [14] Gentry C, Halevi S, Smart NP. Homomorphic evaluation of the AES circuit. In: Safavi-Naini R, Canetti R, eds. Proc. of the CRYPTO 2012. LNCS 7417, Heidelberg: Springer-Verlag, 2012. 850-867. [doi: 10.1007/978-3-642-32009-5_49]
    [15] Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini R, Canetti R, eds. Proc. of the CRYPTO 2012. LNCS 7417, Heidelberg: Springer-Verlag, 2012. 868-886. [doi: 10.1007/978-3-642-32009-5_50]
    [16] Lopez-Alt A, Tromer E, Vaikuntanathan V. On-the-Fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proc. of the 44th Annual ACM Symp. on Theory of Computing (STOC 2012). New York: Association for Computing Machinery, 2012. 1219-1234. [doi: 10.1145/2213977.2214086]
    [17] Stehle D, Steinfeld R. Faster fully homomorphic encryption. In: Abe M, ed. Proc. of the ASIACRYPT 2010. LNCS 6477, Heidelberg: Springer-Verlag, 2010. 377-394. [doi: 10.1007/978-3-642-17373-8_22]
    [18] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-Simpler, asymptotically-faster, attribute-based. In: Canetti R, Garay JA, eds. Proc. of the CRYPTO 2013. LNCS 8042, Heidelberg: Springer-Verlag, 2013. 75-92. [doi: 10.1007/978-3-642-40041-4_5]
    [19] Brakerski Z, Vaikuntanathan V. Lattice-Based FHE as secure as PKE. In: Proc. of the 5th Conf. on Innovations in Theoretical Computer Science (ITCS 2014). New York: Association for Computing Machinery, 2014. 1-12. [doi: 10.1145/2554797.2554799]
    [20] Gu CS, Gu JX. Cryptanalysis of the smart-vercauteren and Gentry-Halevi's fully homomorphic encryption. Int'l Journal of Security and Its Applications, 2012,6(2):103-108.
    [21] Nguyen P, Stehle D. LLL on the average. In: Hess F, Pauli S, Pohst M, eds. Proc. of the ANTS 2006. LNCS 4076, Heidelberg: Springer-Verlag, 2006. 238-256. [doi: 10.1007/11792086_18]
    [22] Lenstra HW, Lenstra AK, Lovasz L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982,261(4): 515-534. [doi: 10.1007/BF01457454]
    [23] Hu YP, Wang FH. An attack on a fully homomorphic encryption scheme, ePrint archive. Technical Report, 2012/561, 2012. http://eprint.iacr.org/2012/561
    [24] Chen Y, Nguyen PQ. Faster algorithms for approximate common divisors: Breaking fully homomorphic encryption challenges over the integers. In: Pointcheval D, Johansson T, eds. Proc. of the EUROCRYPT 2012. LNCS 7237, Heidelberg: Springer-Verlag, 2012. 502-519. [doi: 10.1007/978-3-642-29011-4_30]
    [25] Lauter K, Naehrig M, Vaikuntanathan V. Can homomorphic encryption be practical. In: Proc. of the 3rd ACM Workshop on Cloud Computing Security Workshop (CCSW 2011). New York: Association for Computing Machinery, 2011. 113-124. [doi: 10.1145/ 2046660.2046682]
    [26] Shoup V. NTL: A library for doing number theory. Version 7.0.2, 2009. http://shoup.net/ntl/
    [27] Gu CS, Wu FS. On fully homomorphic encryption, approximate lattice problem and LWE. Int'l Journal of Cloud Computing and Services Science, 2013,2(1):1-15. [doi: 10.11591/closer.v2i1.1339]
    [28] Zhang Y, Wen T, Guo Q, LI FK. Pair-Wise key establishment for wireless sensor networks based on fully homomorphic encryption. Journal on Communications, 2012,33(10):101-109 (in Chinese with English abstract).
    [29] Chen JY, Wang C, Zhang WM, Zhu YF. A secure image steganographic method in encrypted domain. Journal of Electronics & Information Technology, 2012,34(7):1721-1726 (in Chinese with English abstract). [doi: 10.3724/SP.J.1146.2011.01240]
    [30] Sun ZW, Feng DG, Wu CK. An anonymous fingerprinting scheme based on additively homomorphic public key cryptosystem. Ruan Jian Xue Bao/Journal of Software, 2005,16(10):1816-1821 (in Chinese with English abstract). http://www.jos.org.cn/1000- 9825/16/1816.htm
    [31] Guang Y, Gu CX, Zhu YF, Zheng YH, Fei JL. Certificateless fully homomorphic encryption based on LWE problem. Journal of Electronics & Information Technology, 2013,35(4):988-993 (in Chinese with English abstract). [doi: 10.3724/SP.J.1146.2012. 01102]
    [32] Feng DG, Zhang M, Zhang Y, Xu Z. Study on cloud computing security. Ruan Jian Xue Bao/Journal of Software, 2011,22(1): 71-83 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3958.htm [doi: 10.3724/SP.J.1001.2011.03958]
    [33] Yu NH, Hao Z, Xu JJ, Zhang WM, Zhang C. Review of cloud computing security. Acta Electronica Sinica, 2013,41(2):371-381 (in Chinese with English abstract). [doi: 10.3969/j.issn.0372-2112.2013.02.026]
    [34] Cheng FQ, Peng ZY, Song W, Wang SL, Cui YH. An efficient privacy-preserving rank query over encrypted data in cloud computing. Chinese Journal of Computers, 2012,35(11):2215-2227 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016. 2012.02215]
    [35] Cai K, Zhang M, Feng DG. Secure range query with single assertion on encrypted data. Chinese Journal of Computers, 2011,34(11): 2093-2103 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2011.02093]
    [36] Zhu Q, Zhao T, Wang S. Privacy preservation algorithm for service-oriented information search. Chinese Journal of Computers, 2010,33(8):1315-1323 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2010.01315]
    [37] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 2009,56(6):1-40. [doi: 10.1145/1060590.1060603]
    [38] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Gilbert H, ed. Proc. of the EUROCRYPT 2010. LNCS 6110, Heidelberg: Springer-Verlag, 2010. 1-23. [doi: 10.1007/978-3-642-13190-5_1]
    [39] Alperin-Sheriff J, Peikert C. Practical bootstrapping in quasilinear time. In: Canetti R, Garay JA, eds. Proc. of the CRYPTO 2013. LNCS 8042, Heidelberg: Springer-Verlag, 2013. 1-20. [doi: 10.1007/978-3-642-40041-4_1]
    [40] Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error. In: Garay JA, Gennaro R, eds. Proc. of the CRYPTO 2014. LNCS 8616, Heidelberg: Springer-Verlag, 2014. 297-314. [doi: 10.1007/978-3-662-44371-2_17]
    [41] Halevi S, Shoup V. Algorithms in HElib. In: Garay JA, Gennaro R, eds. Proc. of the CRYPTO 2014. LNCS 8616, Heidelberg: Springer-Verlag, 2014. 554-571. [doi: 10.1007/978-3-662-44371-2_31]
    [42] Kannan R. Improved algorithms for integer programming and related lattice problems. In: Proc. of the 15th Annual ACM Symp. on Theory of Computing (STOC'83). New York: Association for Computing Machinery, 1983. 193-206. [doi: 10.1145/800061. 808749]
    [43] Schnorr CP. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 1987,53(2-3): 201-224. [doi: 10.1016/0304-3975(87)90064-8]
    [44] Ajtai M, Kumar R, Sivakumar D. A sieve algorithm for the shortest lattice vector problem. In: Proc. of the 33rd Annual ACM Symp. on Theory of Computing (STOC 2001). New York: Association for Computing Machinery, 2001. 601-610. [doi: 10.1145/ 380752.380857]
    [45] Gama N, Howgrave-Graham N, Koy H, Nguyen PQ. Rankin's constant and blockwise lattice reduction. In: Dwork C, ed. Proc. of the CRYPTO 2006. LNCS 4117, Heidelberg: Springer-Verlag, 2006. 112-130. [doi: 10.1007/11818175_7]
    [46] Gama N, Nguyen P. Finding short lattice vectors within Mordell's inequality. In: Proc. of the 40th Annual ACM Symp. on Theory of Computing (STOC 2008). New York: Association for Computing Machinery, 2008. 208-216. [doi: 10.1145/1374376.1374408]
    [47] Gama N, Nguyen P. Predicting lattice reduction. In: Smart N, ed. Proc. of the EUROCRYPT 2008. LNCS 4965, Heidelberg: Springer-Verlag, 2008. 31-51. [doi: 10.1007/978-3-540-78967-3_3]
    [48] Nguyen P, Vidick T. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2008,2(2): 181-207.
    [49] Becker A, Gama N, Joux A. A sieve algorithm based on overlattices. LMS Journal of Computation and Mathematics, 2014, 17(Special Issue A):49-70. [doi: 10.1112/S1461157014000229]
    [50] Micciancio D, Voulgaris P. Faster exponential time algorithms for the shortest vector problem. In: Proc. of the 21st Annual ACM- SIAM Symp. on Discrete Algorithms (SODA 2010). Society for Industrial and Applied Mathematics, 2010. 1468-1480. http://dl. acm.org/citation.cfm?id=1873601.1873720&coll=DL&dl=ACM&CFID=715343813&CFTOKEN=29694473
    [51] Wang XY, Liu MJ, Tian CL, Bi JG. Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. In: Proc. of the 6th ACM Symp. on Information, Computer and Communications Security (ASIACCS 2011). New York: Association for Computing Machinery, 2011. 1-9. [doi: 10.1145/1966913.1966915]
    [52] Ajtai M, Dwork C. A public-key cryptosystem with worst-case/average-case equivalence. In: Proc. of the 29th Annual ACM Symp. on Theory of Computing (STOC'97). New York: Association for Computing Machinery, 1997. 284-293. [doi: 10.1145/258533. 258604]
    [53] Regev O. New lattice-based cryptographic constructions. Journal of the ACM, 2004,51(6):899-942. [doi: 10.1145/1039488. 1039490]
    [54] von zur Gathen J, Gerhard J. Modern Computer Algebra. 3rd ed., Cambridge: Cambridge University Press, 2013.
    [55] Boyar J, Peralta R, Pochuev D. On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1). Theoretical Computer Science, 2000,235(1):43-57. [doi: 10.1016/S0304-3975(99)00182-6]
    [56] Hastad J, Impagliazzo R, Levin LA, Luby M. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 1999,28(4):1364-1396. [doi: 10.1137/S0097539793244708]
    [57] Vaikuntanathan V. Computing blindfolded: New developments in fully homomorphic encryption. In: Proc. of the 2011 IEEE 52nd Annual Symp. on Foundations of Computer Science (FOCS 2011). Washington: IEEE Computer Society, 2011. 5-16. [doi: 10. 1109/FOCS.2011.98]
    [58] Howgrave-Graham N. Approximate integer common divisors. In: Silverman JH, ed. Proc. of the CaLC 2001. LNCS 2146, Heidelberg: Springer-Verlag, 2001. 51-66. [doi: 10.1007/3-540-44670-2_6]
    [59] Nguyen PQ, Vallée B. The LLL Algorithm: Survey and Applications. Heidelberg: Springer-Verlag, 2009. 33-35. [doi: 10.1007/ 978-3-642-02295-1]
    [60] Barak B, Haitner I, Hofheinz D, Ishai Y. Bounded key-dependent message security. In: Gilbert H, ed. Proc. of the EUROCRYPT 2010. LNCS 6110, Heidelberg: Springer-Verlag, 2010. 423-444. [doi: 10.1007/978-3-642-13190-5_22]
    [61] Goldwasser S, Bellare M. Lecture notes on cryptography. 2008. 249-250. http://cseweb.ucsd.edu/~mihir/papers/gb.html
    [62] Shor PW. Polynomial-Time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal Computing, 1997,26(5):1484-1509. [doi: 10.1137/S0097539795293172]
    附中文参考文献:
    [28] 张永,温涛,郭权,李凤坤.WSN中基于全同态加密的对偶密钥建立方案.通信学报,2012,33(10):100-109.
    [29] 陈嘉勇,王超,张卫明,祝跃飞.安全的密文域图像隐写术.电子与信息学报,2012,34(7):1721-1726. [doi: 10.3724/SP.J.1146.2011. 01240]
    [30] 孙中伟,冯登国,武传坤.基于加同态公钥密码体制的匿名数字指纹方案.软件学报,2005,16(10):1816-1821. http://www.jos.org. cn/1000-9825/16/1816.htm
    [31] 光炎,顾纯祥,祝跃飞,郑永辉,费金龙.一种基于LWE问题的无证书全同态加密体制.电子与信息学报,2013,35(4):988-993. [doi: 10.3724/SP.J.1146.2012.01102]
    [32] 冯登国,张敏,张妍,徐震.云计算安全研究.软件学报,2011,22(1):71-83. http://www.jos.org.cn/1000-9825/3958.htm [doi: 10.3724/ SP.J.1001.2011.03958]
    [33] 俞能海,郝卓,徐甲甲,张卫明,张驰.云安全研究进展综述.电子学报,2013,41(2):371-381. [doi: 10.3969/j.issn.0372-2112.2013.02. 026]
    [34] 程芳权,彭智勇,宋伟,王书林,崔一辉.云环境下一种隐私保护的高效密文排序查询方法.计算机学报,2012,35(11):2215-2227. [doi: 10.3724/SP.J.1016.2012.02215]
    [35] 蔡克,张敏,冯登国.基于单断言的安全的密文区间检索.计算机学报,2011,34(11):2093-2103. [doi: 10.3724/SP.J.1016.2011. 02093][36] 朱青,赵桐,王珊.面向查询服务的数据隐私保护算法.计算机学报,2010,33(8):1315-1323. [doi: 10.3724/SP.J.1016.2010.01315]
    Related
    Cited by
Get Citation

古春生.近似理想格上的全同态加密方案.软件学报,2015,26(10):2696-2719

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 01,2013
  • Revised:December 09,2014
  • Online: October 10,2015
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2050453Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063