In
post-quantum cryptography, NewHope is a
key-agreement protocol In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third parties from forcing a key choice on the agreeing ...
by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
attacks.
NewHope is based on a mathematical problem
ring learning with errors
In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to ...
(RLWE) that is believed to be difficult to solve. NewHope has been selected as a round-two contestant in the
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
Post-Quantum Cryptography Standardization competition, and was used in
Google
Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. ...
's
CECPQ1 experiment as a quantum-secure algorithm, alongside the classical
X25519
X, or x, is the twenty-fourth and third-to-last letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''"ex"'' (pronounced ), ...
algorithm.
Design choices
The designers of NewHope made several choices in developing the algorithm:
* ''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) to prevent signature from leaking information about the private key, it's otherwise not so essential to key exchange schemes. The author chose to sample error vectors from
binomial distribution
In probability theory and statistics, the binomial distribution with parameters ''n'' and ''p'' is the discrete probability distribution of the number of successes in a sequence of ''n'' independent experiments, each asking a yes–no quest ...
.
* ''Error Reconciliation'': What distinguishes NewHope from its predecessors is its method for error reconciliation. Previous
ring learning with error key exchange schemes correct errors one coefficient at a time, whereas NewHope corrects errors 2 or 4 coefficients at a time based on high-dimension geometry. This allows for lower decryption failure rate and higher security.
* ''Base Vector Generation'': The authors of NewHope proposed deriving the base "generator" vector (commonly denoted as A or
) from the output of the XOF function
SHAKE-128 in order to prevent "back-doored" values from being used, as may happen with traditional
Diffie–Hellman through
Logjam attack.
* ''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 challenge.
In the version submitted to NIST, the 512-degree version is codified to provide 128-bit "classical" security level.
See also
*
CECPQ2
*
Cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
*
Lattice-based cryptography
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for pos ...
*
Quantum cryptography
References
{{Reflist
External links
Reference implementation
Cryptographic protocols
Application layer protocols
Transport Layer Security
Post-quantum cryptography