[Back] NewHope is a quantum robust key-exchange method. It is based on the Ring-Learning-with-Errors (Ring-LWE) problem. 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.

## NewHope: Quantum-robust Crypto for Key Generation |

## Outline

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 will integrate a new encryption method for their 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.

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.

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 (\(\textbf{a}\)).

Next Alice generates secret values (\(s_A\)) and error values (\(e_A\)).

Alice then creates \(\textbf{b_A}\) parameters using \(\textbf{a}\), \(\textbf{s_A}\) and \(\textbf{e_A}\):

\(\textbf{b_A} = \textbf{a} \times \textbf{s_A} + \textbf{e_A}\)

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

From the \(seed\) value, Bob can recreate \(\textbf{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\)).

## 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)

## Coding

The following is an outline (based on code [here]):

import sys import poly1 import os import hashlib import sha3 N = 1024 K = 16 Q = 12289 POLY_BYTES = 192 NEWHOPE_SEEDBYTES = 16 NEWHOPE_RECBYTES = 256 NEWHOPE_SENDABYTES = POLY_BYTES + NEWHOPE_SEEDBYTES NEWHOPE_SENDBBYTES = POLY_BYTES + NEWHOPE_RECBYTES #global variables: a_key = [] b_key = [] s_hat = [] #get_noise returns a random sampling from a normal distribution in the NTT domain. def get_noise(): coefficients = poly1.get_noise() coefficeints = poly1.poly_ntt(coefficients) return coefficients # shareda is a server-side function that takes the (decoded) message received # from the client as an argument. It generates the shared key a_key. def shareda(received): global a_key, s_hat (c_coeffs, b_coeffs) = received v_coeffs = poly1.pointwise(s_hat, b_coeffs) v_coeffs = poly1.invntt(v_coeffs) a_key = poly1.rec(v_coeffs, c_coeffs) return # sharedb is a client-side function that takes the (decoded) message received # from the server as an argument. It generates the shared key b_key and returns # a message in the form of a tuple. This message should be encoded using JSON or # another portable format and transmitted (over an open channel) to the server. def sharedb(received): global b_key (pka, seed) = received a_coeffs = gen_a(seed) s_coeffs = get_noise() e_coeffs = get_noise() b_coeffs = poly1.pointwise(a_coeffs, s_coeffs) b_coeffs = poly1.add(b_coeffs, e_coeffs) v_coeffs = poly1.pointwise(pka, s_coeffs) v_coeffs = poly1.invntt(v_coeffs) e_prime = poly1.get_noise() v_coeffs = poly1.add(v_coeffs, e_prime) c_coeffs = poly1.helprec(v_coeffs) b_key = poly1.rec(v_coeffs, c_coeffs) return (c_coeffs, b_coeffs) # keygen is a server-side function that generates the private key s_hat and # returns a message in the form of a tuple. This message should be encoded using # JSON or another portable format and transmitted (over an open channel) to the # client. def keygen(verbose = False): global s_hat seed = os.urandom(params.NEWHOPE_SEEDBYTES) a_coeffs = gen_a(seed) s_coeffs = get_noise() s_hat = s_coeffs e_coeffs = get_noise() r_coeffs = poly1.pointwise(s_coeffs, a_coeffs) p_coeffs = poly1.add(e_coeffs, r_coeffs) return (p_coeffs, seed) def int_from_bytes(b): return int(b.encode('hex'), 16) # gen_a returns a list of random coefficients. def gen_a(seed): hashing_algorithm = sha3.shake_128() hashing_algorithm.update(seed) # 2200 bytes from SHAKE-128 function is enough data to get 1024 coefficients # smaller than 5q, from Alkim, Ducas, Poppelmann, Schwabe section 7: shake_output = hashing_algorithm.digest(2400) output = [] j = 0 for i in range(0,params.N): coefficient = 5 * params.Q # Reject coefficients that are greater than or equal to 5q: while coefficient >= 5 * params.Q: # coefficient = int.from_bytes( # shake_output[j * 2 : j * 2 + 2], byteorder = 'little') coefficient = int_from_bytes(shake_output[j * 2 : j * 2 + 2] ) j += 1 if j * 2 >= len(shake_output): print('Error: Not enough data from SHAKE-128') exit(1) output.append(coefficient) return output alice_message = keygen(True) print "Alice's message is (showing first 100 characters) " + str(alice_message[0])[:200] print " Alice Seed:",binascii.hexlify(alice_message[1]) print bob_message = sharedb(alice_message) print("\nBob's message is (showing first 100 characters) " + str(bob_message[0])[:200] + '\n\n') shareda(bob_message) print("Alice's key is ") print(str(a_key)) print("Bob's key is ") print(str(b_key)) if a_key == b_key: print("Successful handshake! Keys match.") else: print("Error! Keys do not match.")

The code also makes use of polynomial functions (poly1.py):

import params import precomp import os QINV = 12287 # -inverse_mod(p,2^18) RLOG = 18 def LDDecode(xi0, xi1, xi2, xi3): t = g(xi0) t += g(xi1) t += g(xi2) t += g(xi3) t -= 8 * params.Q t >>= 31 return t & 1 def nh_abs(x): mask = x >> 31 return (x ^ mask) - mask def f(x): b = x * 2730 t = b >> 25 b = x - t * 12289 b = 12288 - b b >>= 31 t -= b r = t & 1 xit = t >> 1 v0 = xit + r t -= 1 r = t & 1 v1 = (t >> 1) + r return (v0, v1, nh_abs(x - v0 * 2 * params.Q)) def g(x): b = x * 2730 t = b >> 27 b = x - t * 49156 b = 49155 - b b >>= 31 t -= b c = t & 1 t = (t >> 1) + c t *= 8 * params.Q return nh_abs(t - x) def int_from_bytes(b): return int(b.encode('hex'), 16) def helprec(coefficients): rand = [] output = [] for i in range(0, 1024): output.append(0) v0 = [0, 0, 0, 0] v1 = [0, 0, 0, 0] v_tmp = [0, 0, 0, 0] for i in range(0, 32): rand.append(int_from_bytes(os.urandom(4))) for i in range(0, 256): rbit = rand[i >> 3] >> (i & 7) & 1 (v0[0], v1[0], k) = f(8 * coefficients[0 + i] + 4 * rbit) (v0[1], v1[1], x) = f(8 * coefficients[256 + i] + 4 * rbit) k += x (v0[2], v1[2], x) = f(8 * coefficients[512 + i] + 4 * rbit) k += x (v0[3], v1[3], x) = f(8 * coefficients[768 + i] + 4 * rbit) k += x k = 2 * params.Q - 1 - k >> 31 v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]) v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]) v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]) v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]) output[0 + i] = (v_tmp[0] - v_tmp[3]) & 3 output[256 + i] = (v_tmp[1] - v_tmp[3]) & 3 output[512 + i] = (v_tmp[2] - v_tmp[3]) & 3 output[768 + i] = (-k + 2 * v_tmp[3]) & 3 return output def rec(v_coeffs, c_coeffs): key = [] tmp = [0, 0, 0, 0] for i in range(0, 32): key.append(0) for i in range(0, 256): tmp[0] = ( 16 * params.Q + 8 * v_coeffs[0 + i] - params.Q * (2 * c_coeffs[0 + i] + c_coeffs[768 + i])) tmp[1] = ( 16 * params.Q + 8 * v_coeffs[256 + i] - params.Q * (2 * c_coeffs[256 + i] + c_coeffs[768 + i])) tmp[2] = ( 16 * params.Q + 8 * v_coeffs[512 + i] - params.Q * (2 * c_coeffs[512 + i] + c_coeffs[768 + i])) tmp[3] = ( 16 * params.Q + 8 * v_coeffs[768 + i] - params.Q * (c_coeffs[768 + i])) key[i >> 3] |= LDDecode(tmp[0], tmp[1], tmp[2], tmp[3]) << (i & 7) return key def bitrev_vector(coefficients): for i in range(0, params.N): r = precomp.bitrev_table[i] if i < r: tmp = coefficients[i] coefficients[i] = coefficients[r] coefficients[r] = tmp return coefficients def invntt(coefficients): coefficients = bitrev_vector(coefficients) coefficients = ntt(coefficients, precomp.omegas_inv_montgomery) coefficients = mul_coefficients(coefficients, precomp.psis_inv_montgomery) return coefficients # Get a random sampling of integers from a normal distribution around parameter # Q. def get_noise(): coeffs = [] for i in range(0, params.N): t = int_from_bytes(os.urandom(4)) d = 0 for j in range(0, 8): d += (t >> j) & 0x01010101 a = ((d >> 8) & 0xff) + (d & 0xff) b = (d >> 24) + ((d >> 16) & 0xff) coeffs.append(a + params.Q - b) return coeffs def ntt(coefficients, omega): for i in range(0, 10, 2): distance = 1 << i for start in range(0, distance): jTwiddle = 0 for j in range(start, params.N - 1, 2 * distance): W = omega[jTwiddle] jTwiddle += 1 temp = coefficients[j] coefficients[j] = temp + coefficients[j + distance] coefficients[j + distance] = montgomery_reduce( W * (temp + 3 * params.Q - coefficients[j + distance])) distance <<= 1 for start in range(0, distance): jTwiddle = 0 for j in range(start, params.N - 1, 2 * distance): W = omega[jTwiddle] jTwiddle += 1 temp = coefficients[j] coefficients[j] = barrett_reduce(temp + coefficients[j + distance]) coefficients[j + distance] = montgomery_reduce( W * (temp + 3 * params.Q - coefficients[j + distance])) return coefficients def poly_ntt(coefficients): coefficients = mul_coefficients(coefficients, precomp.psis_bitrev_montgomery) coefficients = ntt(coefficients, precomp.omegas_montgomery) return coefficients # a and b are the coefficients of these polys as lists. def pointwise(a, b): coefficients = [] for i in range(0, params.N): t = montgomery_reduce(3186 * b[i]) coefficients.append(montgomery_reduce(a[i] * t)) return coefficients # a and b are the coefficients of these polys as lists. def add(a, b): coefficients = [] for i in range(0, params.N): coefficients.append(barrett_reduce(a[i] + b[i])) return coefficients def mul_coefficients(coefficients, factors): for i in range(0, params.N): coefficients[i] = montgomery_reduce(coefficients[i] * factors[i]) return coefficients def montgomery_reduce(a): u = a * QINV u &= (1 << RLOG) - 1 u *= params.Q a += u return a >> 18 def barrett_reduce(a): u = (a * 5) >> 16 u *= params.Q a -= u return a

A fun article on this is [here]