An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice

Liang Zhichuang; Zheng Jieyu; Zhao Yunlei

doi:10.7544/issn1000-1239.202220980

Journal of Computer Research and Development > 2024 > 61(4): 1049-1069. > DOI: 10.7544/issn1000-1239.202220980

Liang Zhichuang, Zheng Jieyu, Zhao Yunlei. An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice[J]. Journal of Computer Research and Development, 2024, 61(4): 1049-1069. DOI: 10.7544/issn1000-1239.202220980

Citation:

PDF (1718 KB)

An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice

1.
School of Computer Science, Fudan University, Shanghai 200433
2.
State Key Laboratory of Cryptology, Beijing 100036

Funds: This work was supported by the National Natural Science Foundation of China (61877011), the National Key Research and Development Program of China (2022YFB2701600), the Shanghai Science and Technology Innovation Action Plan (21DZ2200500), and the Shandong Provincial Key Research and Development Program (2017CXG0701, 2018CXGC0701).

More Information

Author Bio:
Liang Zhichuang: born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

Zheng Jieyu: born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

Zhao Yunlei: born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing
Received Date: November 29, 2022
Revised Date: May 14, 2023
Available Online: November 16, 2023

Graphical Abstract

Abstract

Abstract

Constructing post-quantum key encapsulation mechanism based on NTRU lattice is one of the popular research fields in lattice-based cryptography. To reduce the ciphertext size, some current schemes compress the ciphertext with the aid of extra hardness assumptions and error correction codes, which leads to idealistic underlying assumption and complicated implementation. To address the issues, an efficient and compact key encapsulation mechanism, named LTRU, is proposed. LTRU is only based on NTRU one-wayness assumption and enables ciphertext compression without using any error correction codes. The performance-balanced parameter set of LTRU is provided, featuring 128 b quantum security level along with the matching and negligible error probability, and smaller public key size and ciphertext size. LTRU is based on the NTT-friendly polynomial ring. To compute the polynomial operations of LTRU, an efficient mixed-radix NTT is presented. At last, both C implementation and AVX2 implementation of LTRU are provided. When compared with NIST Round 3 finalist NTRU-HRSS, the classical and quantum security of LTRU are strengthened by 6 b and 5 b, respectively. LTRU reduces the public key size, ciphertext size and total bandwidth by 14.6%, 26.0% and 20.3%, respectively. LTRU is 10.9 times faster in key generation and 1.7 faster in decapsulation with respect to AVX2 implementation, respectively.
- post-quantum cryptography,
- NTRU,
- key encapsulation mechanism,
- ciphertext compression,
- number theoretic transform,
- AVX2 implementation

FullText(HTML)

References (60)

References

[1]	Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332 doi: 10.1137/S0036144598347011
[2]	NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates [EB/OL]. (2022-07-05) [2023-04-10].https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[3]	中国密码学会. 关于全国密码算法设计竞赛算法评选结果的公示[EB/OL]. (2020-01-02)[2023-04-10].https://www.cacrnet.org.cn/site/content/854.html Chinese Association for Cryptologic Research. Announcement of the selection results of the national cryptographic algorithm competitions [EB/OL](2020-01-02)[2023-04-10]. https://www.cacrnet.org.cn/site/content/854.html (in Chinese).
[4]	NIST. Post-quantum cryptography round 1 submissions [EB/OL]. (2017-01-03) [2023-04-10]. https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions
[5]	NIST. Post-quantum cryptography round 2 submissions [EB/OL]. (2019-01-30) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-2-submissions
[6]	NIST. Post-quantum cryptography round 3 submissions [EB/OL]. (2020-07-23) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions
[7]	Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1−40
[8]	Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices [C] // Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 719–737
[9]	Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C] // Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 1–23
[10]	Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565−599 doi: 10.1007/s10623-014-9938-4
[11]	Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C] //Proc of the 3rd Int Algorithmic Number Theory Symp. Berlin: Springer, 1998: 267–288
[12]	Howgrave-Graham N, Silverman J H, Whyte W. Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3[C] //Proc of the Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2005: 118–135
[13]	Howgrave-Graham N, Silverman J H, Singer A, et al. NAEP: Provable security in the presence of decryption failures [DB/OL]. IACR Cryptology ePrint Archive, 2003 [2023-04-10].https://eprint.iacr.org/2003/172
[14]	Hoffstein J, Pipher J, Silverman J H. NTRU: A new high speed public key cryptosystem[C] //Proc of the Rump Session of Crypto96. Berlin: Springer, 1996: 1–11
[15]	Coppersmith D, Shamir A. Lattice attacks on NTRU[C] //Proc of Int Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1997: 52–61
[16]	Garg S, Gentry C, Halevi S. Candidate multilinear maps from ideal lattices[C] //Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 1–17
[17]	Langlois A, Stehlé D, Steinfeld R. GGHLite: More efficient multilinear maps from ideal lattices[C] //Proc of the 33rd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2014: 239–256
[18]	Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices[C] // Proc of the 20th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 22–41
[19]	Fouque P A, Hoffstein J, Kirchner P, et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[20]	Chen Cong, Danba O, Hoffstein J. et al. NTRU submission[EB/OL]. NIST PQC round 3 submission, 2020 [2023-04-10]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[21]	Bernstein D J, Brumley B, Chen M S, et al. NTRU Prime: Round 3[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[22]	Avanzi R, Bos J, Ducas L, et al. CRYSTALS-Kyber: Algorithm specifications and supporting documentation (version 3.01)[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[23]	NIST. Status report on the third round of the NIST post-quantum cryptography standardization process [EB/OL]. (2022-07-30) [2023-04-10].https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf
[24]	Business Wire. Business wire security innovation’s NTRUEncrypt adopted as X9 standard for data protection [EB/OL]. (2011-04-11) [2023-04-10].https://www.businesswire.com/news/home/20110411005309/en/Security-Innovations-NTRUEncrypt-Adopted-X9-Standard-Data
[25]	OpenSSH. OpenSSH release notes [EB/OL]. (2022-10-04) [2023-04-10].https://www.openssh.com/releasenotes.html
[26]	Lyubashevsky V, Seiler G. NTTRU: Truly fast NTRU using NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019(3): 180−201
[27]	Duman J, Hövelmanns K, Kiltz E, et al. A thorough treatment of highly-efficient NTRU instantiations [C] //Proc of the 26th IACR Int Conf on Practice and Theory of Public-Key Cryptography. Berlin: Springer, 2023: 65–94
[28]	Liang Zhichuang, Fang Boyue, Zheng Jieyu, et al. Compact and efficient KEMs over NTRU lattices [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/579
[29]	Fouque P A, Kirchner P, Pornin T, et al. BAT: Small and fast KEM over NTRU lattices[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022, 2022(2): 240−265
[30]	D’Anvers J P, Tiepelt M, Vercauteren F, et al. Timing attacks on error correcting codes in post-quantum schemes[C] //Proc of ACM Workshop on Theory of Implementation Security Workshop. New York: ACM, 2019: 2–9
[31]	Kocher P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C] // Proc of the 16th Annual Int Cryptology Conf. Berlin: Springer, 1996: 104–113
[32]	Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[C] //Proc of the 30th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 27–47
[33]	Wang Yang, Wang Mingqiang. Provably secure NTRUEncrypt over any cyclotomic field[C] //Proc of the 25th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2018: 391–417
[34]	Jarvis K, Nevins M. ETRU: NTRU over the Eisenstein integers[J]. Designs, Codes and Cryptography, 2015, 74(1): 219−242 doi: 10.1007/s10623-013-9850-3
[35]	Hülsing A, Rijneveld J, Schanck J, et al. High-speed key encapsulation from NTRU[C] //Proc of the 17th Int Conf on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2017: 232–252
[36]	Bernstein D J, Chuengsatiansup C, Lange T, et al. NTRU prime: Reducing attack surface at low cost[C] //Proc of the 24th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2017: 235–260
[37]	Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C] //Proc of 2018 IEEE European Symp on Security and Privacy. Piscataway, NJ: IEEE, 2018: 353–367
[38]	Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of the 1st ACM Conf on Computer and Communications Security. New York: ACM, 1993: 62–73
[39]	Boneh D, Dagdelen Ö, Fischlin M, et al. Random oracles in a quantum world[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 41–69
[40]	Bernstein D J. Multidigit multiplication for mathematicians [EB/OL]. (2001-09-12) [2023-04-10]. http://cr.yp.to/papers.html#m3
[41]	Cooley J W, Tukey J W. An algorithm for the machine calculation of complex Fourier series[J]. Mathematics of Computation, 1965, 19(90): 297−301 doi: 10.1090/S0025-5718-1965-0178586-1
[42]	Gentleman W M, Sande G. Fast Fourier transforms: For fun and profit[C] // Proc of the AFIPS’66 Fall Joint Computer Conf. New York: ACM, 1966: 563–578
[43]	Weimerskirch A, Paar C. Generalizations of the Karatsuba algorithm for efficient implementations [DB/OL]. IACR Cryptology ePrint Archive, 2006 [2023-04-10].https://eprint.iacr.org/2006/224
[44]	Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[J]. Journal of Cryptology, 2013, 26(1): 80−101 doi: 10.1007/s00145-011-9114-1
[45]	Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation[C] //Proc of the 15th Theory of Cryptography Conf. Berlin: Springer, 2017: 341–371
[46]	Shoup V. Sequences of games: A tool for taming complexity in security proofs [DB/OL]. IACR Cryptology ePrint Archive, 2004 [2023-04-10].https://eprint.iacr.org/2004/332
[47]	Don J, Fehr S, Majenz C, et al. Online-extractability in the quantum random-oracle model [C] //Proc of the 41st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2022: 677–706
[48]	Kannan R. Minkowski’s convex body theorem and integer programming[J]. Mathematics of Operations Research, 1987, 12(3): 415−440 doi: 10.1287/moor.12.3.415
[49]	Bai Shi, Galbraith S D. Lattice decoding attacks on binary LWE[C] //Proc of the 19th Australasian Conf on Information Security and Privacy. Berlin: Springer, 2014: 322–337
[50]	Schnorr C P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1): 181−199
[51]	Chen Yuanmi, Nguyen P Q. BKZ 2.0: Better lattice security estimates[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 1–20
[52]	Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange—A new hope[C] //Proc of the 25th USENIX Security Symp. Berkeley: USENIX Association, 2016: 327–343
[53]	Albrecht M R, Curtis B R, Deo A, et al. Estimate all the {LWE, NTRU} schemes![C] //Proc of the 11th Int Conf on Security and Cryptography for Networks. Berlin: Springer, 2018: 351–367
[54]	Albrecht M, Bai Shi, Ducas L. A subfield lattice attack on overstretched NTRU assumptions[C] //Proc of the 36th Annual Int Cryptology Conf. Berlin: Springer, 2016: 153–178
[55]	Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU[C] // Proc of the 27th Annual Int Cryptology Conf. Berlin: Springer, 2007: 150–169
[56]	Hassan C A, Yayla O. Radix-3 NTT-based polynomial multiplication for lattice-based cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/726
[57]	Barrett P. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[C] //Proc of Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1986: 311–323
[58]	Montgomery P L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170): 519−521 doi: 10.1090/S0025-5718-1985-0777282-X
[59]	Seiler G. Faster AVX2 optimized NTT multiplication for ring-LWE lattice cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2018 [2023-04-10].https://eprint.iacr.org/2018/039
[60]	Bernstein D J, Lange T. eBACS: ECRYPT benchmarking of cryptographic systems [EB/OL]. (2022-06-19) [2023-04-10].https://bench.cr.yp.to

[1]	Liu Le, Guo Shengnan, Jin Xiyuan, Zhao Miaomiao, Chen Ran, Lin Youfang, Wan Huaiyu. Spatial-Temporal Traffic Data Imputation Method with Uncertainty Modeling[J]. Journal of Computer Research and Development, 2025, 62(2): 346-363. DOI: 10.7544/issn1000-1239.202330455
[2]	Xu Xiao, Ding Shifei, Sun Tongfeng, Liao Hongmei. Large-Scale Density Peaks Clustering Algorithm Based on Grid Screening[J]. Journal of Computer Research and Development, 2018, 55(11): 2419-2429. DOI: 10.7544/issn1000-1239.2018.20170227
[3]	Wang Haiyan, Xiao Yikang. Dynamic Group Discovery Based on Density Peaks Clustering[J]. Journal of Computer Research and Development, 2018, 55(2): 391-399. DOI: 10.7544/issn1000-1239.2018.20160928
[4]	Ren Lifang, Wang Wenjian, Xu Hang. Uncertainty-Aware Adaptive Service Composition in Cloud Computing[J]. Journal of Computer Research and Development, 2016, 53(12): 2867-2881. DOI: 10.7544/issn1000-1239.2016.20150078
[5]	Xu Zhengguo, Zheng Hui, He Liang, Yao Jiaqi. Self-Adaptive Clustering Based on Local Density by Descending Search[J]. Journal of Computer Research and Development, 2016, 53(8): 1719-1728. DOI: 10.7544/issn1000-1239.2016.20160136
[6]	Xu Min, Deng Zhaohong, Wang Shitong, Shi Yingzhong. MMCKDE: m-Mixed Clustering Kernel Density Estimation over Data Streams[J]. Journal of Computer Research and Development, 2014, 51(10): 2277-2294. DOI: 10.7544/issn1000-1239.2014.20130718
[7]	Qi Yafei, Wang Yijie, and Li Xiaoyong. A Skyline Query Method over Gaussian Model Uncertain Data Streams[J]. Journal of Computer Research and Development, 2012, 49(7): 1467-1473.
[8]	Pan Weimin and He Jun. Neuro-Fuzzy System Modeling with Density-Based Clustering[J]. Journal of Computer Research and Development, 2010, 47(11): 1986-1992.
[9]	Chen Jianmei, Lu Hu, Song Yuqing, Song Shunlin, Xu Jing, Xie Conghua, Ni Weiwei. A Possibility Fuzzy Clustering Algorithm Based on the Uncertainty Membership[J]. Journal of Computer Research and Development, 2008, 45(9): 1486-1492.
[10]	Ma Liang, Chen Qunxiu, and Cai Lianhong. An Improved Model for Adaptive Text Information Filtering[J]. Journal of Computer Research and Development, 2005, 42(1): 79-84.