3
$\begingroup$

As far as I know NTRUSign is considered to be a Post-Quantum scheme but it's vulnerable to the Nguyen-Regev attack that allow to recover private key when there is an access to signature oracle (as it stated in the original paper, 400 message-signature pairs are enough).

After that paper some improvements were proposed and cracked and now NTRUSign seems to be broken.

Do other lattice-based Post-Quantum schemes suffer from the attack by Nguyen-Regev or similar attacks? Signature and key agreement schemes should also be considered.

Improve this question
$\endgroup$
2
  • $\begingroup$ If you vote down please describe in comments the reason for that. $\endgroup$ – CaptainRR Jan 17 '17 at 11:20
  • 1
    $\begingroup$ Just to add: I'm not sure that all NTRU signature proposals are necessarily broken, see for instance eprint.iacr.org/2016/471. Yes, the initial attempts were flawed, but I suppose the standard way to defend against these breaks (rejection sampling) can also be applied to NTRU signatures. Maybe @zhenfei zhang can shed more light on this. $\endgroup$ – TMM Feb 4 '17 at 14:02
4
$\begingroup$

NTRUSign does not have a security reduction of the type "if one can break the scheme then one can find short vectors in some lattice." There are several other lattice schemes that do have such a reduction, and are therefore unaffected (as far as we know) by the Nguyen-Regev attack. If they were affected, then we would have a better algorithm fro finding short vectors in lattices.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! I'm not familiar with lattice-based crypto and I used to think NTRUSign has reduction to SVP, now it's clear. $\endgroup$ – CaptainRR Jan 18 '17 at 11:35

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.