Research Current Status and Challenges of Fully Homomorphic Cryptography Based on Learning with Errors

doi:10.3969/j.issn.1671-1122.2024.09.003

Abstract

Abstract:

Fully homomorphic encryption scheme is an encryption scheme with data confidentiality and security, and it is also able to perform computational operations on the ciphertext. In the era of cloud computing, full homomorphic encryption scheme can meet the needs of private information retrieval, multi-party secure computing and other applications. The combination of the Learning With Errors (LWE) problem and fully homomorphic encryption has rapidly promoted the development of fully homomorphic encryption schemes, and has led to a variety of technological tools, such as key exchange and mode exchange, as well as many technology with theoretical and practical applications. Since the LWE-based fully homomorphic encryption scheme was proposed in 2011, the LWE-type based scheme has become the mainstream method of fully homomorphic encryption scheme, and has gradually moved from theory to practical application. This paper first introduced the basics and applications of full homomorphic encryption, and provided a detailed analysis of the mathematical theory used to construct the scheme; then systematically combed through the development of each generation of homomorphic encryption schemes, and gave the typical construction methods of each generation of schemes; finally, it discussed the problems of the current LWE-based full homomorphic encryption schemes as well as the development trends in the future. This paper analysed and researched the development of LWE-based fully homomorphic encryption in recent years, and provided some references for subsequent researchers.

Key words: fully homomorphic encryption, learning with errors, privacy protection

CLC Number:

TP309

WEN Jinming, LIU Qing, CHEN Jie, WU Yongdong. Research Current Status and Challenges of Fully Homomorphic Cryptography Based on Learning with Errors[J]. Netinfo Security, 2024, 24(9): 1328-1351.

Figures/Tables 8

References 91

[1]	RIVEST R L, ADLEMAN L, DERTOUZOS M L. On Data Banks and Privacy Homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.
[2]	RIVEST R L, SHAMIR A, ADLEMAN L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.
[3]	ELGAMAL T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469-472.
[4]	NACCACHE D, STERN J. A New Public Key Cryptosystem Based on Higher Residues[C]// ACM. Proceedings of the 5th ACM Conference on Computer and Communications Security. New York: ACM, 1998: 59-66.
[5]	PAILLIER P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 1999: 223-238.
[6]	DAMGARD I, JURIK M. A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System[C]// Springer. Public Key Cryptography:4th International Workshop on Practice and Theory in Public Key Cryptosystems. Heidelberg: Springer, 2001: 119-136.
[7]	SANDER T, YOUNG A, YUNG M. Non-Interactive Cryptocomputing for NC^1[C]// IEEE. 40th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1999: 554-566.
[8]	DAMIEN S, STEINFELD R. Faster Fully Homomorphic Encryption[C]// Springer. Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2010: 24-43.
[9]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]// ACM. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.
[10]	GENTRY C, HALEVI S. Implementing Gentry’s Fully-Homomorphic Encryption Scheme[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2011: 129-148.
[11]	CRAMER R, DUCAS L, PEIKERT C, et al. Recovering Short Generators of Principal Ideals in Cyclotomic Rings[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2016: 559-585.
[12]	SMART N P, VERCAUTEREN F. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes[C]// Springer. International Workshop on Public Key Cryptography. Heidelberg: Springer, 2010: 420-443.
[13]	VAN D M, GENTRY C, HALEVI S, et al. Fully Homomorphic Encryption over the Integers[C]// Springer. Advances in Cryptology-EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2010: 24-43.
[14]	HOWGRAVE-GRAHAM N. Approximate Integer Common Divisors[C]// Springer. International Cryptography and Lattices Conference. Heidelberg: Springer, 2001: 51-66.
[15]	GALBRAITH S D, GEBREGIYORGIS S W, MURPHY S. Algorithms for the Approximate Common Divisor Problem[J]. LMS Journal of Computation and Mathematics, 2016, 19: 58-72.
[16]	YANG Haomiao, XIA Qi, WANG Xiaofen, et al. A New Somewhat Homomorphic Encryption Scheme over Integers[C]// IEEE. 2012 International Conference on Computer Distributed Control and Intelligent Environmental Monitoring. New York: IEEE, 2012: 61-64.
[17]	RAMAIAH Y G, KUMARI G V. Towards Practical Homomorphic Encryption with Efficient Public Key Generation[J]. International Journal on Network Security, 2012, 3(4): 10-21.
[18]	CHEN Liquan, BEN Hongmei, HUANG Jie. An Encryption Depth Optimization Scheme for Fully Homomorphic Encryption[C]// IEEE. 2014 International Conference on Identification, Information and Knowledge in the Internet of Things. New York: IEEE, 2014: 137-141.
[19]	NUIDA K, KUROSAWA K. (Batch) Fully Homomorphic Encryption over Integers for Non-Binary Message Spaces[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2015: 537-555.
[20]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.
[21]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors over Rings[C]// Springer. Advances in Cryptology-EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2010: 1-23.
[22]	LÓPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption[C]// ACM. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. New York: ACM, 2012: 1219-1234.
[23]	BOS J W, LAUTER K, LOFTUS J, et al. Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[C]// Springer. Cryptography and Coding:14th IMA International Conference. Heidelberg: Springer, 2013: 45-64.
[24]	DORÖZ Y, SUNAR B. Flattening NTRU for Evaluation Key Free Homomorphic Encryption[J]. Journal of Mathematical Cryptology, 2020, 14(1): 66-83.
[25]	SMART N P, VERCAUTEREN F. Fully Homomorphic SIMD Operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57-81.
[26]	BRAKERSKI Z, VAIKUNTANATHAN V. Efficient Fully Homomorphic Encryption from (Standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2): 831-871.
[27]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.
[28]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymp-Totically-Faster, Attribute-Based[C]// Springer. Advances in Cryptology-CRYPTO 2013: 33rd Annual Cryptology Conference. Heidelberg: Springer, 2013: 75-92.
[29]	BRAKERSKI Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[C]// Springer. Annual Cryptology Conference. Heidelberg: Springer, 2012: 868-886.
[30]	DUCAS L, MICCIANCIO D. FHEW: Bootstrapping Homomorphic Encryption in Less than a Second[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2015: 617-640.
[31]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds[C]// Springer. Advances in Cryptology-ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2016: 3-33.
[32]	MARTINS P, SOUSA L, MARIANO A. A Survey on Fully Homomorphic Encryption: An Engineering Perspective[J]. ACM Computing Surveys, 2017, 50(6): 1-33.
[33]	ACAR A, AKSU H, ULUAGAC A S, et al. A Survey on Homomorphic Encryption Schemes: Theory and Implementation[J]. ACM Computing Surveys, 2018, 51(4): 1-35.
[34]	ALLOGHANI M, ALANI M M, AL-JUMEILY D, et al. A systematic Review on the Status and Progress of Homomorphic Encryption Technologies[J]. Journal of Information Security and Applications, 2019, 48: 102-112.
[35]	ALAYA B, LAOUAMER L, MSILINI N. Homomorphic Encryption Systems Statement: Trends and Challenges[J]. Computer Science Review, 2020, 36: 100-112.
[36]	MARCOLLA C, SUCASAS V, MANZANO M, et al. Survey on Fully Homomorphic Encryption, Theory, and Applications[J]. Proceedings of the IEEE, 2022, 110(10): 1572-1609.
[37]	BONEH D, GOH E J, NISSIM K. Evaluating 2-DNF Formulas on Ciphertexts[C]// Springer. Theory of Cryptography:Second Theory of Cryptography Conference. Heidelberg: Springer, 2005: 325-341.
[38]	KUSHILEVITZ E, OSTROVSKY R. Replication is Not Needed: Single Database, Computationally-Private Information Retrieval[C]// IEEE. Proceedings 38th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1997: 364-373.
[39]	BENALOH J. Dense Probabilistic Encryption[C]// IEEE. Proceedings of the Workshop on Selected Areas of Cryptography. New York: IEEE, 1994: 120-128.
[40]	YAO A C. Protocols for Secure Computations[C]// IEEE. 23rd Annual Symposium on Foundations of Computer Science. New York: IEEE, 1982: 160-164.
[41]	ISHAI Y, PASKIN A. Evaluating Branching Programs on Encrypted Data[C]// Springer. Theory of Cryptography Conference. Heidelberg: Springer, 2007: 575-594.
[42]	BARAK B, BRAKERSKI Z. Building the Swiss Army Knife[EB/OL]. Windows on Theory Blog. (2012-05-02)[2024-03-30]. http://windowsontheory.org/2012/05/02/building-the-swiss-army-knife.
[43]	WANG Huiyong, FENG Yong, ZHAO Lingzhong, et al. A Secure Multi-Party Computation Protocol on the Basis of Multi-Key Homomorphism[J]. Journal of South China University of Technology (Natural Science Edition), 2017, 45(7): 69-76.
	王会勇, 冯勇, 赵岭忠, 等. 基于多密钥同态技术的安全多方计算协议[J]. 华南理工大学学报(自然科学版), 2017, 45(7):69-76. doi: 10.3969/j.issn.1000-565X.2017.07.010
[44]	KIM E, LEE H S, PARK J. Towards Round-Optimal Secure Multiparty Computations: Multikey FHE without a CRS[J]. International Journal of Foundations of Computer Science, 2020, 31(2): 157-174.
[45]	TANG Chunming, HU Yezhou. Secure Multi-Party Computation Based on Multi-Bit Fully Homomorphic Encryption[J]. Chinese Journal of Computers, 2021, 44(4): 836-845.
	唐春明, 胡业周. 基于多比特全同态加密的安全多方计算[J]. 计算机学报, 2021, 44(4):836-845.
[46]	CHEN Hao, LAINE K, RINDAL P. Fast Private Set Intersection from Homomorphic Encryption[C]// ACM. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1243-1255.
[47]	CHEN Hao, HUANG Zhicong, LAINE K, et al. Labeled PSI from Fully Homomorphic Encryption with Malicious Security[C]// ACM. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1223-1237.
[48]	OPPERMANN A, GRASSO-TORO F, YURCHENKO A, et al. Secure Cloud Computing: Communication Protocol for Multithreaded Fully Homomorphic Encryption for Remote Data Processing[C]// IEEE. 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC). New York: IEEE, 2017: 503-510.
[49]	GAI Keke, QIU Meikang, LI Yujun, et al. Advanced Fully Homomorphic Encryption Scheme over Real Numbers[C]// IEEE. 2017 IEEE 4th International Conference on Cyber Security and Cloud Computing (CSCloud). New York: IEEE, 2017: 64-69.
[50]	ALTAEE M M S, ALANEZI M. Enhancing Cloud Computing Security by Paillier Homomorphic Encryption[J]. International Journal of Electrical and Computer Engineering (IJECE), 2021, 11(2): 1771-1779.
[51]	CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private Information Retrieval[J]. Journal of the ACM (JACM), 1998, 45(6): 965-981.
[52]	ANGEL S, CHEN Hao, LAINE K, et al. PIR with Compressed Queries and Amortized Query Processing[C]// IEEE. 2018 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2018: 962-979.
[53]	PATEL S, PERSIANO G, YEO K. Private Stateful Information Retrieval[C]// ACM. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1002-1019.
[54]	BARNI M, ORLANDI C, PIVA A. A Privacy-Preserving Protocol for Neural-Network-Based Computation[C]// ACM. Proceedings of the 8th Workshop on Multimedia and Security. New York: ACM, 2006: 146-151.
[55]	ORLANDI C, PIVA A, BARNI M. Oblivious Neural Network Computing via Homomorphic Encryption[J]. EURASIP Journal on Information Security, 2007: 1-11.
[56]	RAHULAMATHAVAN Y, PHAN R C W, VELURU S, et al. Privacy-Preserving Multi-Class Support Vector Machine for OutSourcing the Data Classification in Cloud[J]. IEEE Transactions on Dependable and Secure Computing, 2013, 11(5): 467-479.
[57]	XIE Pengtao, BILENKO M, FINLEY T, et al. Crypto-Nets: Neural Networks over Encrypted Data[EB/OL]. (2014-12-24)[2023-12-13]. https://doi.org/10.48550/arXiv.1412.6181.
[58]	ZHANG Qingchen, YANG L T, CHEN Zhikui. Privacy Preserving Deep Computation Model on Cloud for Big Data Feature Learning[J]. IEEE Transactions on Computers, 2015, 65(5): 1351-1362.
[59]	CHABANNE H, DE WARGNY A, MILGRAM J, et al. Privacy-Preserving Classification on Deep Neural Network[EB/OL]. (2017-03-24)[2024-03-25]. https://eprint.iacr.org/2017/035.
[60]	CRAMER R, GENNARO R, SCHOENMAKERS B. A Secure and Optimally Efficient Multi-Authority Election Scheme[J]. European Transactions on Telecommunications, 1997, 8(5): 481-490.
[61]	BAUDRON O, FOUQUE P A, POINTCHEVAL D, et al. Practical Multi-Candidate Election System[C]// ACM. Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing. New York: ACM, 2001: 274-283.
[62]	PARKES D C, RABIN M O, SHIEBER S M, et al. Practical Secrecy-Preserving, Verifiably Correct and Trustworthy Auctions[C]// ACM. Proceedings of the 8th International Conference on Electronic Commerce: The New E-Commerce:Innovations for Conquering Current Barriers, Obstacles and Limitations to Conducting Successful Business on the Internet. New York: ACM, 2006: 70-81.
[63]	Zhu Zhengyang. An Electronic Scheme Based on Total Homomorphic Encryption[D]. Guangzhou: Guangzhou University, 2013.
	朱正阳. 一种基于全同态加密的电子投票方案[D]. 广州: 广州大学, 2013.
[64]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. A Homomorphic LWE Based E-Voting Scheme[C]// Springer. Post-Quantum Cryptography:7th International Workshop. Heidelberg: Springer, 2016: 245-265.
[65]	LOU Yu. A Private Multi-Candidate Electronic Voting Protocol[D]. Xiangtan: Hunan University of Science and Technology, 2017.
	娄宇. 一种私密多候选人电子投票协议[D]. 湘潭: 湖南科技大学, 2017.
[66]	LOU Yu, ZHU Gengming. A Multi-Candidate Electronic Voting Protocol with RLWE Homomorphic Encryption[J]. Com-puter Engineering & Science, 2018, 40(3): 472-480.
	娄宇, 朱更明. RLWE同态加密算法的多候选人电子投票协议[J]. 计算机工程与科学, 2018, 40(3):472-480.
[67]	HE Qian, SHEN Wei. Multi-Candidate Electronic Voting Scheme Based on Homomorphic Encryption[J]. Computer Systems and Applications, 2019, 28(2): 146-151
	何倩, 沈炜. 基于同态加密的多候选人电子投票方案[J]. 计算机系统应用, 2019, 28(2):146-151.
[68]	CORON J S, MANDAL A, NACCACHE D, et al. Fully Homomorphic Encryption over the Integers with Shorter Public Keys[C]// Springer. Annual Cryptology Conference. Heidelberg: Springer, 2011: 487-504.
[69]	FAN Junfeng, VERCAUTEREN F. Somewhat Practical Fully Homomorphic Encryption[EB/OL]. (2012-03-22)[2024-03-25]. https://eprint.iacr.org/2012/144.
[70]	GENTRY C, HALEVI S, SMART N P. Fully Homomorphic Encryption with Polylog Overhead[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2012: 465-482.
[71]	HALEVI S, SHOUP V. Bootstrapping for Helib[J]. Journal of Cryptology, 2021, 34(1): 7-15.
[72]	ALPERIN-SHERIFF J, PEIKERT C. Practical Bootstrapping in Quasilinear Time[C]// Springer. Annual Cryptology Conference. Heidelberg: Springer, 2013: 1-20.
[73]	HALEVI S, SHOUP V. Faster Homomorphic Linear Transformations in Helib[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 2018: 93-120.
[74]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]// Springer. Advances in Cryptology-ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security. Heidelberg: Springer, 2017: 409-437.
[75]	BRAKERSKI Z, VAIKUNTANATHAN V. Lattice-Based FHE as Secure as PKE[C]// ACM. Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. New York: ACM, 2014: 1-12.
[76]	BARRINGTON D A. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC[C]// ACM. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. New York: ACM, 1986: 1-5.
[77]	ALPERIN-SHERIFF J, PEIKERT C. Faster Bootstrapping with Polynomial Error[C]// Springer. Advances in Cryptology-CRYPTO 2014: 34th Annual Cryptology Conference. Heidelberg: Springer, 2014: 297-314.
[78]	GAMA N, IZABACHENE M, NGUYEN P Q, et al. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems[C]// Springer. Advances in Cryptology-EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2016: 528-558.
[79]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. TFHE: Fast Fully Homomorphic Encryption Over the Torus[J]. Journal of Cryptology, 2020, 33(1): 34-91.
[80]	MICCIANCIO D, SORRELL J. Ring Packing and Amortized FHEW Bootstrapping[J]. (2019-10-06)[2024-03-30]. https://eprint.iacr.org/2018/532.
[81]	ALBRECHT M, CHASE M, CHEN Hao, et al. Homomorphic Encryption Standard[J]. Protecting Privacy through Homo-Morphic Encryption, 2021: 31-62.
[82]	ESPITAU T, JOUX A, KHARCHENKO N. On a Hybrid Approach to Solve Small Secret LWE[J]. (2020-06-01)[2024-04-01]. https://eprint.iacr.org/2020/515.
[83]	MICCIANCIO D, POLYAKOV Y. Bootstrapping in FHEW-Like Cryptosystems[C]// ACM. Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. New York: ACM, 2021: 17-28.
[84]	LEE Y, MICCIANCIO D, KIM A, et al. Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption[J]. ( 2023-06-10)[2024-04-01]. https://eprint.iacr.org/2022/198.
[85]	CHILLOTTI I, JOYE M, PAILLIER P. Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks[C]// Springer. Cyber Security Cryptography and Machine Learning:5th International Symposium. Heidelberg: Springer, 2021: 1-19.
[86]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2017: 377-408.
[87]	CHILLOTTI I, LIGIER D, ORFILA J B, et al. Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE[C]// Springer. Advances in Cryptology-ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2021: 670-699.
[88]	YANG Zhaomin, XIE Xiang, SHEN Huajie, et al. TOTA: Fully Homomorphic Encryption with Smaller Parameters and Stronger Security[J]. (2021-10-07)[2024-04-01]. https://eprint.iacr.org/2021/1347.
[89]	LI Baiyu, MICCIANCIO D. On the Security of Homomorphic Encryption on Approximate Numbers[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2021: 648-677.
[90]	FAUZI P, HOVD M N, RADDUM H. On the IND-CCA1 Security of FHE Schemes[J]. Cryptography, 2022, 6(1): 13-20.
[91]	LAI Junzuo, DENG R H, MA Changshe, et al. CCA-Secure Keyed-Fully Homomorphic Encryption[C]// Springer. Public-Key Cryptography-PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography. Heidelberg: Springer, 2016: 70-98.

方案	公钥	私钥	评估密钥	密文
BV11	$n(n+1){{\log }^{2}}q$	$(L+1)n\log q$	$L{{(n+1)}^{2}}{{\left\lceil \log q \right\rceil }^{2}}$	$(n+1)\log q$
BGV12	$2n(n+1){{\log }^{2}}q$	$(L+1)(n+1)\log B$	$L{{(n+1)}^{3}}{{\left\lceil \log q \right\rceil }^{2}}$	$(n+1)\left\lceil \log q \right\rceil $
Bra12	$2n(n+1){{\log }^{2}}q$	$(L+1)(n+1)\log q$	$L{{(n+1)}^{3}}{{\left\lceil \log q \right\rceil }^{4}}$	$(n+1)\left\lceil \log q \right\rceil $
GSW13	$2n(n+1){{\log }^{2}}q$	$(n+1)\left\lceil \log q \right\rceil $	—	${{(n+1)}^{2}}{{\left\lceil \log q \right\rceil }^{2}}$