NewHope

Appearance move to sidebar hide

In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.

NewHope is based on a mathematical problem ring learning with errors (RLWE) that is believed to be difficult to solve. NewHope has been selected as a round-two contestant in the NIST Post-Quantum Cryptography Standardization competition, and was used in Google's CECPQ1 experiment as a quantum-secure algorithm, alongside the classical X25519 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.
• 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 a {\displaystyle a} ) 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
• Lattice-based cryptography
• Quantum cryptography

References

1. ^ "NewHope Post-quantum key encapsulation".
2. ^ "Chrome: Stop future computers from cracking current encryption". CNET.
3. ^ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 2 Submissions - Post-Quantum Cryptography - CSRC". Csrc.nist.gov. Retrieved 14 November 2019.
4. ^ "Experimenting with Post-Quantum Cryptography". security.googleblog.com. 7 July 2016. Retrieved 14 November 2019.
5. ^ "CECPQ1 results (28 Nov 2016)". Adam Langley, security officer at Google.
6. ^ Original proposal paper
7. ^ "Post-quantum key exchange - a new hope". eprint.iacr.org. 10 November 2016. Retrieved 14 November 2019.

External links

• Reference implementation

v t e Public-key cryptography Algorithms Integer factorization Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Naccache–Stern Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa Discrete logarithm BLS Cramer–Shoup DH DSA ECDH X25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS Lattice/SVP/CVP/LWE/SIS BLISS Kyber NewHope NTRUEncrypt NTRUSign RLWE-KEX RLWE-SIG Others AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern knapsack cryptosystem Three-pass protocol XTR Theory Discrete logarithm cryptography Elliptic-curve cryptography Hash-based cryptography Non-commutative cryptography RSA problem Trapdoor function Standardization CRYPTREC IEEE P1363 NESSIE NSA Suite B Post-Quantum Cryptography Topics Digital signature OAEP Fingerprint PKI Web of trust Key size Identity-based cryptography Post-quantum cryptography OpenPGP card

v t e Cryptography General History of cryptography Outline of cryptography Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network Mathematics Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography Category