Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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 substantially 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)
