3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ Not complete, will continue later, open to additions. $\endgroup$ – kelalaka Mar 2 at 20:55
  • $\begingroup$ thanks for the references. Have these attacks been implemented or are they based on theoretical calculations? $\endgroup$ – evernal Mar 4 at 18:57
  • $\begingroup$ Only NTRU-107, AFAIK. I'll continue this when I have a proper mind. $\endgroup$ – kelalaka Mar 4 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.