NewHope: Quantum-robust Crypto for Key Generation using Ring Learning With Errors

A demo of this method is defined here.
Photo by Shahadat Rahman on Unsplash

NewHope: Quantum-robust Crypto for Key Generation using Ring Learning With Errors

A demo of this method is defined here.

There are several methods defined for quantum robust cryptography including:

  • Lattice-based cryptography [Lattice] — This classification shows great potential and is leading to new cryptography methods, such as for fully homomorphic encryption, and code obfuscation.
  • Code-based cryptography [McEliece] — This classification was created in 1978 with the McEliece cryptosystem but has barely been using in real applications. The McEliece method uses linear codes that are used in error correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code.
  • Multivariate polynomial cryptography [UOV] — This classification involves the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
  • Hash-based signatures [GMSS] — This classification involves creating digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed, and that there is a limit to the number of signatures that can be produced. New methods, though, integrate into Merkle Trees, which allows for the signer to use the same keys to sign multiple entities.

The two main applications of public key encryption is in signing and in key exchange. The existing methods of key exchange include the Diffie-Hellman Method, Elliptic Curve Diffie-Hellman (ECDH) and RSA encryption (and where the shared key is generated by the client and then encrypted with the public key of server). Unfortunately each of these methods will be cracked with quantum computers. NewHope is a quantum robust key-exchange method, and is based on the Ring-Learning-with-Errors (Ring-LWE) problem. For this, Alice generates a message, and passes it to Bob, and Bob also generates a message and passes to Alice. After they process the message, they will end up with the same shared key.

With quantum computers, many of the current public key encryption methods, such as RSA, are at threat, as quantum computers can factorize the prime numbers used, within a reasonable time limit. So the risk is that anything which is encrypted now, will be able to be decrypted within the next 20 years.

NewHope was defined by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe in this [paper]. Google selected NewHope for an experiment to reduce the impact of quantum computers. With this they integrated into a special browser version (Canary) and is integrated into HTTPs communications. The method is named “Ring Learning With Errors” (Ring-LWE) and is a key exchange method which would be robust in the age of quantum computing. Ring-LWE has no known weaknesses within a quantum computing era.

Ring-LWE uses a mixture of current key exchange methods and quantum robust methods, and thus an intruder would have to defeat both methods in order to crack the encrypted communication. It is currently only being used in a few Google domains, and only when users are using Chrome Canary, where users can see a string of “CECPQ1” within the browser’s security panel (under Key-exchange heading):

The method is defined as [paper]:

Alice initially generates a 256-bit seed value (seed), and then uses the Shake_128 hashing method to create the polynomial coefficients (a).

Next Alice generates secret values (sA) and error values (eA).

Alice then creates b_A parameters using a, s_A and e_A:

b_A=a×s_A+e_A

This value is passed to Bob, along with the seed.

From the seed value, Bob can recreate a.

Bob goes through a similar process to Alice, and sends Alice back two values (u,r). After this they can create the same shared key. The key is generated from a SHA-256 hash of a value (v).

For NewHope we define q = 12,289 and with NewHope512 we set n = 512. For NewHope1024 we select n = 1024. NewHope512 has a brute force security level equivalent to 128-bit AES, and NewHope1024 has the strength of 256-bit AES.

Sample run

A sample run is:

Alice's message is (showing first 100 characters) [7104L, 11469L, 12754L, 9818L, 6103L, 2336L, 4494L, 4581L, 8702L, 1033L, 1638L, 2617L, 1507L, 10512L, 1147L, 8945L, 5384L, 2211L, 11003L, 10251L, 5612L, 3475L, 10105L, 2162L, 5933L, 2558L, 2550L, 5477
 Alice Seed: 678ce7042916695f2ff0cbfe38a06f58
Bob's message is  (showing first 100 characters) [3L, 3L, 3L, 2L, 3L, 2L, 3L, 2L, 3L, 2L, 2L, 3L, 2L, 1L, 0L, 2L, 2L, 3L, 3L, 1L, 2L, 3L, 3L, 2L, 1L, 1L, 0L, 3L, 1L, 3L, 2L, 2L, 2L, 3L, 1L, 0L, 1L, 3L, 2L, 0L, 2L, 3L, 1L, 2L, 2L, 1L, 0L, 3L, 0L, 1L,
Alice's key is 
[200L, 167L, 209L, 244L, 161L, 207L, 196L, 242L, 27L, 239L, 148L, 211L, 8L, 94L, 80L, 197L, 75L, 16L, 191L, 241L, 157L, 179L, 122L, 60L, 185L, 242L, 88L, 120L, 108L, 68L, 85L, 200L]
Bob's key is 
[200L, 167L, 209L, 244L, 161L, 207L, 196L, 242L, 27L, 239L, 148L, 211L, 8L, 94L, 80L, 197L, 75L, 16L, 191L, 241L, 157L, 179L, 122L, 60L, 185L, 242L, 88L, 120L, 108L, 68L, 85L, 200L]
Successful handshake! Keys match.

We have generated 32 byte integers (32x8 bits = 256 bits). An outline of Ring LWE is:

And a demonstration of Ring LWE is given here, and the code here:

Conclusions

NewHope has been submitted to the NIST Round 1 Submission for quantum robust cryptography. Ring LWE looks to be one of the preferred methods for quantum robust cryptography, as it produces good levels of security for relatively small keys, along with good levels of performance.