ALGEBRAIC CRYPTANALYSIS ON NTRU-HPS AND NTRU-HRSS
Abstract
NTRU is a lattice-based public-key cryptosystem designed by Hoffstein, Pipher, and Silverman in 1996. NTRU published on Algorithmic Number Theory Symposium (ANTS) in 1998. The ANTS’98 NTRU became the IEEE standard for public key cryptographic techniques based on hard problems over lattices in 2008. NTRU was later redeveloped by NTRU Inc. in 2018 and became one of the finalists in round 3 of the PQC (Post-Quantum Cryptography) standardization process organized by NIST in 2020. There are two types of NTRU algorithms proposed by NTRU Inc., which are classified based on parameter determination, NTRU-HPS (Hoffstein, Pipher, Silverman) and NTRU-HRSS (Hulsing, Rijnveld, Schanck, Schwabe). Algebraic cryptanalysis on ANTS’98 NTRU had previously been carried out in 2009 and 2012. In this paper, algebraic cryptanalysis is performed on NTRU-HPS with q=2048, n=509 (ntruhps2048509) and NTRU-HRSS with n=701 (ntruhrss701). This research aims to evaluate the resistance of NTRU-HPS and NTRU-HRSS algorithms against algebraic cryptanalysis by reconstructing the private key value. As a result, NTRU-HPS and NTRU-HRSS resistance to algebraic cryptanalysis.
Downloads
References
M. Haart and C. Hoffs, “Quantum Computing: What it is, how we got here, and who’s working on it.,” Mar. 2019.
K. Li, P. G. Yan and Q. Y. Cai, “Quantum computing and the security of public key cryptography,” Fundamental Research, vol. 1, no. 1, pp. 85–87, Jan. 2021.
K. S. Roy, “A survey on post-quantum cryptography for constrained devices,” International Journal of Applied Engineering Research, vol. 14, pp. 2608-2615, May. 2019.
D. Moody et al., “Status report on the second round of the NIST post-quantum cryptography standardization process,” National Institute of Standards and Technology, 2020, doi: 10.6028/NIST.IR.8309.
J. Hoffstein, J. Pipher and J. H. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem,” Lecture Notes in Computer Science, Berlin: Springer, 1998, 267-288.
IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices IEEE Computer Society, IEEE Std 1363.1-2008, 2009.
C. Chen et al., “NTRU algorithm specifications and supporting documentation,” NTRU Inc., 2019.
Y. M. Agus, M. A. Murti, F. Kurniawan, N. D. W. Cahyani, and G. B. Satrya, “An Efficient Implementation of NTRU Encryption in Post-Quantum Internet of Things,” in 2020 27th International Conference on Telecommunications (ICT), 2020, pp. 1–5. doi: 10.1109/ICT49546.2020.9239560.
G. Bourgeois and J. C. Faugère, “Algebraic attack on NTRU using Witt vectors and Gröbner bases,” Journal of Mathematical Cryptology, vol. 3, no. 3, pp. 205–214, Sep. 2009, doi: 10.1515/JMC.2009.011.
J. Ding and D. Schmidt, “Algebraic attack on lattice-based cryptosystems via solving equations over real numbers” Cryptology ePrint Archive, p. 94, 2012.
J. Bi and L. Han, “Lattice Attacks on NTRU Revisited,” IEEE Access, vol. 9, pp. 66218–66222, 2021, doi: 10.1109/ACCESS.2021.3076598.
H. Arabnezhad-Khanoki, B. Sadeghiyan, and J. Pieprzyk, “S-boxes representation and efficiency of algebraic attack,” IET Inf Secure, vol. 13, no. 5, pp. 448–458, Sep. 2019, doi: 10.1049/iet-ifs.2018.5201.
A. Askeland and S. Rønjom. “A Side-Channel Assisted Attack on NTRU,” IACR Cryptol. ePrint Arch., p. 790, 2021.
A. Abdel-Hafez, R. A. Elbarkouky and W. Hafez, “Comparative Study of Algebraic Attacks,” International Advanced Research Journal in Science, Engineering and Technology, vol. 3, pp. 85-90, 2016.
C. Mascia, E. Piccione and M. Sala, “An algebraic attack on stream ciphers with application to nonlinear filter generators and WG-PRNG,” arXiv, Cornell University, Dec. 2021, doi: 10.48550/arXiv.2112.12268.
Copyright (c) 2023 Fadila Paradise, Kiki Ariyanti Sugeng
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
