What is the largest parameter broken for NTRU? 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?
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 Stehlé. 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
&gt;$2^{66}$


743
613
603
176
159
125
&gt; $2^{125}$


1024
1870
747
218
198
155
&gt; $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
&gt;128
&gt;189


743
&gt;267
&gt;443


1024
&gt;811
&gt; 590




BKZ with quantum sieving, hybrid attack vs. uSVP




N
hybrid attack Cost
uSVP




443
&gt;84
&gt;85


743
&gt;163
&gt;159


1024
&gt;289
&gt; 198