افزایش کارآمدی الگوریتم تولید کلید مشبکه‌های NTRU به کمک نرم میدان

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشگاه قم، قم، ایران

چکیده

در طراحی بسیاری از طرح‌های نامتقارن مانند کلید عمومی و امضای دیجیتال از مشبکه‌های NTRU استفاده می‌کنند. به‌صورت مفهومی یک طرح امضا از سه مرحله تشکیل می‌‌شود: تولید کلید خصوصی، امضا و تصدیق. برای تولید کلید خصوصی در طرح‌های امضای مبتنی بر NTRU در یک لپ‌‌‌‌تاپ معمولی (Intel Core i7-6567U 3.30 GHz) زمان زیادی صرف می‌شود (بیش از یک ثانیه) درحالی‌که امضا و تصدیق به‌مراتب زمان کمتری نیاز دارند (برای مثال یک‌هزارم ثانیه). مقالۀ فعلی به ارائۀ راهکارهایی برای کاهش زمان مرحلۀ تولید کلید خصوصی می‌پردازد. در این مقاله، روش‌های قبلی مورد مطالعه قرار می‌گیرند و سپس یک روش جدید مبتنی بر نرم میدان معرفی می‌گردد و نشان داده می‌شود که با استفاده از آن، زمان اجرا به‌طور قابل ملاحظه‌ای کاهش پیدا می‌کند. 
 
 
 

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

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

نویسندگان [English]

  • Reza Alimoradi
  • Mohammad Hossein Noorallahzadeh
  • Ahmad Gholami
University of Qom, Qom, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Post-quantum cryptographic schemes
  • Lattice-based cryptographic schemes
  • NTRU-based cryptographic schemes
  • Algorithms based on soft field
[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.