JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (11): 78-84.doi: 10.6040/j.issn.1671-9352.0.2017.370

Previous Articles     Next Articles

Properties of the expansion factor over quotient ring

WANG Ai-lan, SONG Wei-tao, ZHAO Xiu-feng   

  1. Information Engineering University, Zhengzhou 450004, Henan, China
  • Published:2018-11-14
  • About author:国家自然科学基金资助项目(61601515,61672031);河南省自然科学基金资助项目(162300410332)
  • Supported by:

Abstract: Because of the simplicity, security and efficiency R-LWE-based FHE schemes become the mainstream design of FHE. The value of polynomial expansion factor of R-LWE-based FHE for quotient ring R=Z[x]/(f(x))has an important influence on the noise expansion speed for homomorphic operation of ciphertexts. Based on the expansion factor of ∞ norm for different polynomials, the values of expansion factors of ∞ norm over ring R for some special polynomials f(x)are obtained. It proves that the larger numbers of monomials with coefficient being zero for polynomials f(x), the smaller the corresponding expansion factors is. The higher the power of a monomial with a coefficient of 0, the smaller the corresponding expansion factor. The results can provide theoretical guidance for the design of efficient R-LWE-based FHE schemes.

Key words: homomorphic encryption, R-LWE problem, infinite norm, expanding factor

CLC Number: 

  • TN918
[1] RIVEST R L, ADLEMAN L, DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978:169-179.
[2] MITTAL D, KAUR D, AGGARWAL A. Secure data mining in cloud using homomorphic encryption[C] //IEEE International Conference on Cloud Computing in Emerging Markets. [S.l] IEEE, 2014:1-7.
[3] PASUPULETI S K, RAMALINGAM S, BUYYA R. An efficient and secure privacy-preserving approach for outsourced data of resource constrained mobile devices in cloud computing[J]. Journal of Network & Computer Applications, 2016, 64(C):12-22.
[4] JAIN R, MADAN S, GARG B. Homomorphic framework to ensure data security in cloud environment[C] //International Conference on Innovation and Challenges in Cyber Security. [S.l] IEEE, 2016:177-181.
[5] GENTRY C. Fully homomorphic encryption using ideal lattices [J]. Stoc, 2009, 9(4):169-178.
[6] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C] //Acm Symposium on Theory of Computing. ACM, 2005:84-93.
[7] BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from(standard)LWE[C] //Foundations of Computer Science. IEEE, 2011:97-106.
[8] BRAKERSKI Z, VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C] //Cryptology Conference. Berlin: Springer, 2011: 505-524.
[9] BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled)Fully homomorphic encryption without bootstrapping[J]. Acm Transactions on Computation Theory, 2014, 6(3):1-36.
[10] BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C] //Cryptology Conference on Advances in Cryptology-CRYPTO. New York: Springer-Verlag, 2012: 868-886.
[11] GENTRY C, HALEVI S, PEIKERT C, et al. Ring switching in BGV-style homomorphic encryption[C] //International Conference on Security and Cryptography for Networks. Berlin: Springer, 2012:19-37.
[12] ALPERIN-SHERIFF J, PEIKERT C. Practical bootstrapping in quasilinear time[M] //Advances in Cryptology — CRYPTO 2013. Berlin: Springer, 2013: 1-20.
[13] GENTRy C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[M] //Advances in Cryptology—CRYPTO 2013. Berlin: Springer, 2013: 75-92.
[14] ALPERIN-SHERIFF J, PEIKERT C. Faster bootstrapping with polynomial error[M] //Advances in Cryptology—CRYPTO 2014. Berlin: Springer, 2014: 297-314.
[15] DUCAS L, MICCIANCIO D. FHEW: Bootstrapping homomorphic encryption in less than a second[M] //Advances in Cryptology-EUROCRYPT 2015. Berlin: Springer, 2015: 617-640.
[16] COSTACHE A, SMART N P. Which Ring based somewhat homomorphic encryption scheme is best?[C] //Cryptographers Track at the RSA Conference. Cham: Springer, 2016: 325-340.
[1] DING Yi-tao, YANG Hai-bin, YANG Xiao-yuan, ZHOU Tan-ping. A reversible image data hiding scheme in Homomorphic encrypted domain [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 104-110.
[2] WANG Wei-li, HU Bin, ZHAO Xiu-feng. An efficient multi-identity-based fully homomorphic encryption scheme [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(5): 85-94.
Full text



[1] SHAO Yong. Semilattice-ordered completely regular periodic semigroups[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 1 -5 .
[2] GONG Zeng-tai, GAO Han. Preinvexity of n-dimensional fuzzy number-valued functions[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 72 -81 .
[3] CHEN Wen-qian, ZHANG Xiao-jin, ZAN Li-bo. The number of tilting modules over Gorenstein algebras[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 14 -16 .
[4] GUO Shou-tao, WANG Zhan-ping. Gorenstein homological dimensions of modules under exact zero-divisors[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 17 -21 .
[5] WU Xiao-ying, WANG Fang-gui. Graded version of Enochs theorem[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 22 -26 .
[6] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27 -34 .
[7] WANG Dan, WANG Zheng-pan. Characterizing a band variety in terms of forbidden subsemigroups[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 6 -8 .
[8] LIANG Xing-liang, WU Su-peng, REN Jun. Characterization of monoids by C(P')acts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 9 -13 .
[9] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35 -41 .
[10] ZHEN Wei-wei, ZENG Jian, REN Jian-long. Time dependent parabolic inverse source problem based on variational theory[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 61 -71 .