What is the largest parameter broken for NTRU?

Question

The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission.

Security	N	q
Moderate	107	64
High	168	128
Highest	503	256

What are attacks done so far that have broke the moderate and high security level parameters? The papers I came across mainly talks about the theoretical aspects of the attacks but are there any papers that did an actual implementation and manage to break the parameters?

Or in other words, what are the attacks that have caused the secure parameters to change? What is the largest parameter broken for NTRU?

Answer 1

• 1996 - NTRU patent,

• 1998 - NTRU article

Lattice Attacks

• 1996 - Lattice attack on the Rump Session of Crypto'96

• 1997 - Don Coppersmith and Adi Shamir. Lattice attacks on NTRU. In EUROCRYPT, pages 52–61, 1997. No need to find the exact secret key to be able to decrypt

• 2008 - Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology, EUROCRYPT’08,

  It has been shown in that the ability to locate a unique shortest vector in a lattice depends on the root Hermite factor of the lattice,

• 2011 - Yuanmi Chen and Phong Q Nguyen. BKZ 2.0: Better lattice security estimates. In ASIACRYPT 2011, pages 1–20. Springer, 2011.

  Fastest NTRU-107. 214-dimensional lattices within $2^{42.62}$ clock cycles. Dimension of the lattice is the double of $N$

• 2016 - Shi Bai, Thijs Laarhoven, and Damien Stehlé. Tuple lattice sieving. IACR Cryptology ePrint Archive, 2016:713, 2016.

  Best lattice attack with $2^{0.292n}$ cost.

The below are the cost estimates from the NTRU PQC team.

N	m	b	Known Classical	Known Quantum	Best Plausible	Space Requirement
443	390	321	93	85	66	>$2^{66}$
743	613	603	176	159	125	> $2^{125}$
1024	1870	747	218	198	155	> $2^{155}$

Search attack

Searching the keyspace ${N \choose df,df}/N$ NTRU-743, we have $2^{1158}$ candidates. Impossible!

Hybrid attack

the hybrid attack is a hybrid of a lattice attack and a meet-in-the-middle search attack.

• 2007 - Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In CRYPTO, pages 150–169, 2007.

BKZ with classical enumeration, hybrid attack vs. uSVP

N	hybrid attack Cost	uSVP
443	>128	>189
743	>267	>443
1024	>811	> 590

BKZ with quantum sieving, hybrid attack vs. uSVP

N	hybrid attack Cost	uSVP
443	>84	>85
743	>163	>159
1024	>289	> 198