In
post-quantum cryptography
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms (usually public-key algorithms) that are currently thought to be secure against a crypt ...
, NewHope is a
key-agreement protocol
In cryptography, a key-agreement protocol is a protocol whereby two (or more) parties generate a cryptographic Key (cryptography), key as a function of information provided by each honest party so that no party can predetermine the resulting value ...
by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist
quantum computer
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing takes advantage of this behavior using specialized hardware. ...
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 t ...
(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 s ...
Post-Quantum Cryptography Standardization competition, and was used in
Google
Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...
's
CECPQ1 experiment as a quantum-secure algorithm, alongside the classical
X25519
X, or x, is the twenty-fourth letter of the Latin alphabet, used in the English alphabet, modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is Wikt:ex#English, ''ex'' (pro ...
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
BLISS is a system programming language developed at Carnegie Mellon University (CMU) by W. A. Wulf, D. B. Russell, and A. N. Habermann around 1970. It was perhaps the best known system language until C debuted a few years later. Since then, C ...
(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 and is the discrete probability distribution of the number of successes in a sequence of statistical independence, independent experiment (probability theory) ...
.
* ''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 "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
*
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 support important standards of post-quant ...
*
Quantum cryptography
Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure soluti ...
References
External links
Reference implementation
{{crypto-stub
Cryptographic protocols
Application layer protocols
Transport Layer Security
Post-quantum cryptography