NewHope

In cryptography, NewHope is a key-agreement protocol by Erdem Alkim et al. designed to resist quantum computer attacks.

NewHope is based on the Ring learning with errors (RLWE) problem. It is a round-two contestant in the NIST PQC competition, and is used in Google's CECPQ1 experiment as a quantum-secure algorithm (alongside the classical X25519).

Features

• Binomial Sampling: Although sampling to high-quality discrete Gaussian distribution is important in post-quantum lattice-based compact signature scheme such as Falcon (GPV-style Hash-and-Sign paradigm) and BLISS (GLP-style Fiat-Shamir paradigm), it's otherwise not so essential to key exchange schemes. The author choosed to sample error vectors from binomial distribution.
• Error Reconciliation: What NewHope differs from its predecessors, is its method for error reconciliation. Previous ring learning with error key exchange schemes corrects errors one coefficient at a time; where as NewHope corrects error 2 or 4 coefficients at a time based on high-dimension geometry. This allows for lower decryption failure rate and higher security.
• Security Levels: In the early versions of the papers describing NewHope, authors proposed using 1024-degree polynomial for 128-bit "post-quantum" security level, and a 512-degree polynomial as "toy" instance for cryptanalysis challange. In the version submitted to NIST, the 512-degree version is codified to provide 128-bit "classical" security level.

See also

• Reference implementation
• Original proposal paper
• Ring learning with errors
• Quantum cryptography
• Post-Quantum Cryptography Standardization
• CECPQ1