You sure can quant on me!

So, I recently treated myself with a Nintendo switch. Let’s say computer time has been limited lately…Saving Hyrule has been kind of my priority :)

I recently took a course called Kryptering 3 (advanced cryptography), which mostly is about post-quantom cryptography and the corresponding algorithms. Yesterday I fell into some writing mode again, so today I’m gonna talk a bit about quantom computers and show a “quantom safe” algorithm - GGH.

What is Quantom computers and why you should care

A regular computer has it’s lowest information represented as a bit, one or zero. A quantom computer has its lowest information represented as a qubit. Reading a qubit is different from reading a bit. A bit is always one or zero, but a qubit is represented as a normalized superposition of either one or zero (this is black magic). This gives quantom computers special properties, which in short makes quantom computers incredibly fast at solving specific problems. Or rather, given this quantom property we can construct specific algorithms which utilizes these to solve specific problems. You may have heard about one of these algorithms - Shor’s algorithm.

A common myth is that quantom computers breaks all encryption. This is not true. Rather shor’s algorithm (in theory) solves the integer factorization and discrete logarithm problem in polynomial time.

What does this mean then? Well, the encryption schemes which builds on these problems are broken with suffiently good quantom computers. Any schemes that comes to mind? How about RSA, ECDSA and Diffie-Hellman? Which all are asymmetric algorithms. Symmetric algorithms (like AES) seems to be fine for now, i.e. there is no quantom algorithm which breaks these like Shor’s algorithm breaks some asymmetric schemes.

Cool and all, but this sounds like real sci-fi. I shouldn’t care right?

Google just declared quatom supremacy and earlier this year Martin Ekerå and Craig Gidney wrote a paper which described how to factor 2048-bit RSA integers in 8 hours.

Such quantom computers are not here yet though. But according to Martin Ekerå - they can be in the next 10-25 years.

Ahhh, everythings on fire!!

Well, this sucks :D But don’t worry too much just yet, there are solutions to this.

So, Shor’s algorithm solves the integer factorization and discrete logarithm problem in polynomial time. Can we build asymmetric schemes which depends on other problems? Looks like we can!

GGH (and don’t use this)

A fairly simple algorithm (compared to other post-quantom schemes) is GGH. It is broken though, so don’t use it. But it’s easier than others to explain.

Math, math and math

Vector space

First we need to have something called vector space. A vectorspace V over R is defined if V is closed under addition and multiplication for all vectors in V and elements i R. This means that the result of adding two arbitrary vectors from V is in V, and the scalar multiplication of an arbitrary vector in V and element in R is in V. It’s easier to show -

u,v in V
a in R

u+v in V
au in V

There are more rules to this (read my other posts).

A vectorspace V has a base B=(v1,v2,…,vm) if B is linearly independant and every vector, v can be written like a linear combination of B.

Lattice

A Lattice is a vector space with a base (linearly independant vectors) which generates the lattice.

Example:

L = lattice
(v_1,v_2,...,v_n) = base

Given the base v_1=(1,0) and v_2=(2,1) where v_1,v_2 in R^2 the lattice L is described as

L = {xv1, yv2} = {x+2y, y} for all elements x,y in Z

The lattice can be represented as all points {x,y} in the plane.

Here comes the problem

One problem which is hard to solve (in higher dimensions) is the Closest vector problem. Given a vector w in R, find the closest vector v to w in the vector space V, i.e. find the vector v in V with the shortest distance to w

GGH

Keys

Pick n random linearly independant vectors from Z^n and set the private key

V = (v_1,v_2,...,v_n)^T

Pick a random matrix U with order n such as determinant U = +-1

Set the public key W to

W = UV

Encryption

The plaintext p should be coded in such a way that p=(p_1,p_2,…,p_n) is in Z^n.

Pick a random efemary key r in Z^n. I will describe why below.

The ciphertext is then given by

c = pW + r

Decryption

We have a vector c which is not in V. Why not? Because we introduced a noise, r.

To find the original message p we first need to find pW (which is a vector in V). To do this we find the closest vector to c. This means that me remove the noise introduced by r.

pW = solve_CVP(c, V)
p = pWW^-1 = pI = p

Solving approximate CVP can be done by Babai’s algorithm. But not knowing V (the private key) makes it a really hard problem to solve.

Conclusion

As you can see above, GGH is built on the closest vector problem (and not integer factorization or discrete logarithms). GGH is very broken though! But there are other post-quantom algorithms which work much better (such as McEliece and NTRU).

This was a basic introduction to post-quantom cryptography and why we all should care. Next post will be a introduction to homomorphic encryption (yay, more buzzwords!).