qTesla is a signature scheme and a submission to the NIST post-quantum standardization process, which made it to the second round. It is based on the hardness of RLWE. The NIST round 2 status report says that it didn't make it to round 3 because:

the performance of the remaining parameter sets of qTESLA is not strong enough to remain competitive. In particular, the public key sizes of q-TESLA-p-I and q-TESLA-p-III are about 15 to 20 times as large as those of FALCON and CRYSTALS-DILITHIUM, and the signature sizes are larger as well.

However, there were also attacks on the scheme, notably one by Lyubashevsky and Schwabe; the document states that

We (Peter Schwabe and I) give a complete break of (3) ‐ in particular, a signing algorithm for arbitrary messages that doesn't require the use of the secret key and is faster than the qTesla signing algorithm (which uses the secret keys).

So my question is: is qTesla considered secure? Was this attack just an attack on a variant of qTesla, or did it render qTesla insecure? Was this attack a factor in NIST not progressing it to round 3?

  • 2
    $\begingroup$ That will depend on what you define qTestla to be, and to a lesser degree what you take as "secure". A proposed variant/mode is not secure at all, and 10 out of 12 of the proposed parameters were questionable enough to be retracted. $\endgroup$
    – fgrieu
    Nov 25, 2021 at 11:33
  • $\begingroup$ Is there a form which is unbroken and has a reliable parameter set? $\endgroup$
    – a196884
    Nov 25, 2021 at 11:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.