Increasing the efficiency of the key generation algorithm for NTRU with the help of the norm field

Document Type : Original Article

Authors

University of Qom, Qom, Iran

Abstract

Conceptually, a signature scheme consists of three steps: private key generation, signature, and authentication. Private key generation in NTRU-based signature schemes on a typical laptop (Intel Core i7-6567U 3.30 GHz) takes a long time (more than one second), while signature and verification take much less time (for example, a thousandths of a second). The current paper deals with providing solutions to reduce the time of private key generation. In this paper, the previous methods are studied and then a new method based on the norm field is introduced and it is shown that the execution time is significantly reduced by using it.

Keywords

Main Subjects

References

[1] Albrecht, M., Bai, S., & Ducas, L. (2016). A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes. In Annual International Cryptology Conference, Berlin, Heidelberg: Springer Berlin Heidelberg, 9814, 153–178. DOI: https://doi.org/10.1007/978-3-662-53018-4_6.
[2] Babai, L. (1986). On Lovász’lattice reduction and the nearest lattice point problem. Combinatorica, 6, 1–13. DOI: https://doi.org/10.1007/BF02579403.
[3] Bernstein, D.J., Chuengsatiansup, C., Lange, T., & van Vredendaal, C. (2016). NTRU Prime. Tech.rep., National Institute of Standards and Technology.
[4] Campbell, P., & Groves, M. (2017). Practical post-quantum hierarchical identity-based encryption. 16th IMA International Conference on Cryptography and Coding.
[5] Cash, D., Hofheinz, D., Kiltz, E., & Peikert, C. (2010). Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. EUROCRYPT 2010. Lecture Notes in Computer Science, vol 6110. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-13190-5_27.
[6] Cheon, J.H., Jeong, J., & Lee, C. (2016). An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low level encoding of zero. LMS Journal of Computation and Mathematics, 19, 255–266. DOI: https://doi.org/10.1112/S1461157016000371.
[7] Chuengsatiansup, C., Prest, T., Stehlé, D., Wallet, A., & Xagawa, K. (2020). ModFalcon: Compact signatures based on module-NTRU lattices. In: Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, 853–866. DOI: https://doi.org/10.1145/3320269.3384758. 
[8] Cooley, J.W., & Tukey, J.W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19, 297–301.
[9] Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22, 644–654. DOI: https://doi.org/https://doi.org/10.1109/TIT.1976.1055638.
[10] Ducas, L., Lyubashevsky, V., & Prest, T. (2014). Efficient identity-based encryption over NTRU lattices. In Advances in Cryptology–ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7-11, 2014, Proceedings, Part II, 20, 22–41. DOI: https://doi.org/10.1007/978-3-662-45608-8_2.
[11] Espitau, T., Fouque, P.A., Gérard, F., Rossi, M., Takahashi, A., Tibouchi, M., Wallet, A., & Yu, Y. (2022). Mitaka: A simpler, parallelizable, maskable variant of Falcon. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cham: Springer International Publishing, 222–253. DOI: https://doi.org/10.1007/978-3-031-07082-2_9.
[12] FIPS. (2001). NIST: Security Requirements for Cryptographic Modules.
[13] Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., & Zhang, Z. (2017). Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (tech. rep.).
[14] Fouque, P.A., Kirchner, P., Pornin, T., & Yu, Y. (2022). Bat: Small and Fast KEM over NTRU Lattices. IACR Transactions on Cryptographic Hardware and Embedded Systems, 240–265. DOI: https://doi.org/10.46586/tches.v2022.i2.240-265.
[15] Gentleman, W.M., & Sande, G. (1966). Fast Fourier transforms: for fun and profit. In Proceedings of the November 7-10, fall joint computer conference, 563–578.
[16] Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, 197–206. DOI: https://doi.org/10.1145/1374376.1374407.
[17] Harvey, D., & Van Der Hoeven, J. (2021). Integer multiplication in time O(nlog n). Annals of Mathematics, 193, 563–617. DOI: https://doi.org/10.4007/annals.2021.193.2.4.
[18] Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., & Whyte, W. (2003). NTRUSIGN: Digital signatures using the NTRU lattice. In Cryptographers’ track at the RSA conference, Berlin, Heidelberg: Springer Berlin Heidelberg, 122–140. DOI: https://doi.org/https://doi.org/10.1007/3-540-36563-X_9.
[19] Hoffstein, J., Pipher, J., & Silverman, J.H. (1998). NTRU: A ring-based public key cryptosystem. In International algorithmic number theory symposium, Berlin, Heidelberg: Springer Berlin Heidelberg, 267–288. DOI: https://doi.org/https://doi.org/10.1007/BFb0054868.
[20] Kirchner, P., & Fouque, P.A. (2017). Revisiting lattice attacks on overstretched NTRU parameters. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cham: Springer International Publishing, 3–26. DOI: https://doi.org/10.1007/978-3-319-56620-7_1. 
[21] Lenstra, A.K., Lenstra, H.W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(ARTICLE), 515–534. DOI: https://doi.org/10.1007/BF01457454.
[22] Micciancio, D., & Warinschi, B. (2001). A Linear Space Algorithm for Computing the Hermite Normal Form. In Proceedings of the 2001 international symposium on Symbolic and algebraic computation, 231–236. DOI: https://doi.org/10.1145/384101.384133.
[23] NIST. (2016). Submission requirements and evaluation criteria for the post-quantum cryptography standardization process.
[24] Schönhage, A., & Strassen, V. (1971). Fast multiplication of large numbers. Computing, 7, 281–292. DOI: https://doi.org/10.1007/BF02242355.
[25] Smart, N.P., Albrecht, M.R., Lindell, Y., Orsini, E., Osheter, V., Paterson, K., & Peer, G. (2017). Lima: A PQC encryption scheme. National Institute of Standards and Technology.
[26] Stehle, D. & Steinfeld, R. (2013). Making NTRUEnrypt and NTRUSign as secure as standard worst-case problems over ideal lattices. Cryptology ePrint Archive, Report 2013/004.
[27] Von Zur Gathen, J., & Gerhard, J. (2013). Modern Computer Algebra (3. Ed.). Cambridge University Press.
[28] Working Group of the C/MM Committee. (2009). IEEE P1363. 1 Standard Specifications for Public-Key Cryptographic Techniques Based on Hard Problems over Lattices.
[29] Zhao, R.K., McCarthy, S., Steinfeld, R., Sakzad, A., & O’Neill, M. (2023). Quantum-safe HIBE: does it cost a Latte?. IEEE Transactions on Information Forensics and Security. DOI: https://eprint.iacr.org/2021/222. 

Files

History

  • Receive Date: 09 February 2024
  • Revise Date: 16 April 2024
  • Accept Date: 19 June 2024

Share

How to cite

Statistics