• Fadila Paradise Department of Mathematics, Faculty of Mathematics and Natural Sciences, University of Indonesia, Indonesia
  • Kiki Ariyanti Sugeng Department of Mathematics, Faculty of Mathematics and Natural Sciences, University of Indonesia, Indonesia
Keywords: Algebraic Cryptanalysis, NTRU-HPS, NTRU-HRSS


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.


Download data is not yet available.


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.

How to Cite
F. Paradise and K. Sugeng, “ALGEBRAIC CRYPTANALYSIS ON NTRU-HPS AND NTRU-HRSS”, BAREKENG: J. Math. & App., vol. 17, no. 4, pp. 2187-2196, Dec. 2023.