7
$\begingroup$

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules.

  • Is being a ring-based KEM contributed to their elimination?
  • In this case, is there any recent development in cryptanalysis on ideal lattices that can pose danger in the future?
  • Even if this is the case, isn't Falcon also a ring-based signature scheme? I am confused by this.
$\endgroup$
  • $\begingroup$ No, can you please give me the source? Is it available online? $\endgroup$ – Rick Oct 10 '20 at 10:02
  • $\begingroup$ @kelalaka Thanks I will look into the document. $\endgroup$ – Rick Oct 10 '20 at 10:03
  • $\begingroup$ Posted the comments as a bolded answer... $\endgroup$ – kelalaka Oct 10 '20 at 10:24
8
$\begingroup$

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process

3.12 NewHope

NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key sizes as well as fast computations via NTT. CCA security is achieved by a standard flavor of Fujisaki-Okamoto transform and is supported by proofs in the classical and quantum random oracle models. Among all LWE-based lattice submissions, NewHope (and other RLWE schemes) can be viewed as the most structured, with MLWE being an intermediately structured case and plain LWE being the least structured case. As a result of this structure, the scheme has very strong performance for nearly all applications.

In a technical sense, the security of NewHope is never better than that of KYBER. A recent paper gives a highly parameterizable, essentially linear-time reduction from RLWE to MLWE . If that reduction is specialized to the case of NewHope, one finds the following: the reduction takes RLWE instances and outputs an MLWE instance; it is modulus-preserving; it is “almost” sample-preserving; it is error distribution-preserving; and it translates the ring dimension for RLWE into the product of ring-dimension times module-rank for MLWE. As such, any attack against an underlying MLWE instance implies a bstantially similar-cost attack against NewHope’s underlying RLWE instance. There are a few minor caveats. However, NIST does not expect that these issues will substantially change the relative concrete security situation of NewHope and an MLWE scheme (like KYBER) that is indicated by the presence of such a tight and efficient reduction.

Further, NIST observed that the CoreSVP strength estimates of NewHope and KYBER are substantially comparable, and KYBER was slightly more efficient in most benchmarks [1] [2]. Specifically because of the relaxation in algebraic structure, KYBER naturally supports a category 3 security strength parameter set, whereas NewHope does not.

Despite the numerous strengths of the NewHope KEM proposal, NIST developed a slight but clear preference for KYBER and for low-rank MLWE schemes over RLWE schemes for the KEM application setting. Therefore, NIST did not select NewHope to continue into the third round (Bolds and links are mine, except the recent paper link that was original)

Like the AES selection, the performance is an important metric when the cipher suites are close to each other or passing the required bounds.

For the categories see this answer, or the NIST original page on Post-Quantum Cryptography: Security (Evaluation Criteria)

$\endgroup$
  • 1
    $\begingroup$ Thanks for your help and comments. It was very helpful. $\endgroup$ – Rick Oct 10 '20 at 10:22

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.