An attack to NTRUencrypt was implemented using sagemath and Fpylll

The code is in attack.py

References:

[1] Marios Adamoudis, K. A. Draziotis, Message recovery attack to NTRU using a lattice independent from the public key, http://arxiv.org/abs/2203.09620

• K. A. draziotis ([email protected])
• Marios Adamoudis ([email protected] )

credits: Some functions are from https://latticehacks.cr.yp.to/ntru.html

This project is licensed under the GPLv2 License

The images are provided with CC BY 2.0

prerequisites : sagemath version >=8.1 and Fpylll.

In generate.md there is sagemath code that generates a pair (pk,sk) for NTRU and a random plaintext and also its encryption (ciphertext).

See attack.md for comments on the attack.py

For large values of N, say N>400, sagemath produces babai's infinite loop for LLL (we used sagemath 8.5).

In fpylll LLL succeeded. For instance, for N=509, it took 5 minutes for the LLL reduction.

For N=509,557 and 677 you can use the already reduced matrices from the directory reduced_matrices/. To compute the LLL- reduction of matrices in fpylll we use the code in ntru_large_matrices_reduction.ipynb

In the code (attack.py) there is an option in the function the_attack(.) to set flag=2, then the code will use the reduced matrix from the file in the directory reduced_matrices/ it and will not compute LLL reduction on it.

In appendix.ipynb there is Fpylll code that checks suitable values (N,q,y) that satisfy the hypotheses of Proposition.

Please report bugs (open an issue).