Two new Quantum Attack Algorithms against NTRU_pke # KA_NTRU # & # PA_NTRU #

Authors

  • LAAJI EL Hassane ACSA Laboratory, Mohammed First University Oujda, Morocco
  • AZIZI Abdelmalek Mohammed First University Oujda, Morocco
  • AZZOUAK Siham ACSA Laboratory Sidi Mahammed Ben Abdellah University Fes, Morocco

DOI:

https://doi.org/10.37231/myjcam.2020.3.1.37

Keywords:

NTRU, NewHope, Lattice- Based-Cryptography, Post Quantum cryptography, Grover´’ Algorithm

Abstract

The NTRUencrypt authors submitted four versions to National Institute of Standardization (NIST) competition since 2016 and it is still in process for the second round. The NTRU_pke release is one of them, it is defined in the ring Rq = Zq[X] / (Xn−1); and the private keys and the plaintext are codified in trinary polynomial, that means all their coefficients are in {-1,0,1}. Our two quantum attacks algorithms KA_NTRU and PA_NTRU on NTRU_pke implementation, inspired from Grover’s Algorithm, targeted respectively to find Private Keys and Plaintext. For testing the implementation attacks, we create a NTRU_pke test version named NTRU Attacks. In the general case, the quantum algorithms can break a system of dimension n in 2n/2 time.

Published

2020-06-30