Quantum Code-Cracking Takes Another Hit: Lattice-based Cryptography

Public-key crypto-systems rely these days on approaches founded in mathematical methods which are provably hard to crack. The easiest to understand requires factorization of a key based on the product of two large prime numbers. Much has been made recently of the ability of quantum computers to crack this style of encryption. A more complex method requires solving b[SUP]k[/SUP] = g where b and g are real number elements of a finite group and k must be an integer. This is the discrete logarithm problem in elliptic curve cryptography. A quantum computing algorithm has also been developed for this case. Therefore, in theory, widely known public key methods are crackable unless perhaps the key is unmanageably large.

But encryption systems are now turning to another method – lattice-based cryptography with noise. The approach rests in effect on solving linear equations – a very well studied problem for which excellent solutions exist – but then adds noise to the values. It turns out that Gaussian elimination, the foundation to any of these solutions, is very brittle in the presence of even small amounts of noise in the sense that it is difficult to extract a correct or even approximate solution in these cases.

The method is based on something called Learning with Errors which was derived in the course of studying a machine-learning problem. This has been adapted to something even more cryptically :rolleyes: called Ring Learning with Errors which operates over the ring of polynomials in a finite field (which, it turns out, is related to solving optimization problems on lattices, which, it turns out, is related the linear equation problem). Public key exchange involves exchanging two polynomials: a(x) and b(x) = a(x).s(x) + e(x) where s(x) is the secret and e(x) is a small random error polynomial. In a return exchange, the two parties can come to agreement on the key. I’m not even going to attempt to explain the detail of the exchange here – I’m still inching my way through the paper.

Cracking lattice-based methods is provably as hard as some other hard problems in lattice theory, and you can dial in ever higher levels of difficulty by increasing the rank of the polynomials and other factors. I haven’t seen comparisons with complexity in factoring large numbers but I assume you can dial up the lattice method to a point that it becomes just as computationally hard to solve. But what is most important is that quantum computing has not been shown to offer any advantage in speeding up attacks on this style of encryption (some believe it may be impossible for QC to provide any speedup though this has not been proven). In effect, before quantum computing has had a chance to make a dent on encryption code-cracking, it has quite probably become obsolete (for this purpose).

This is no longer limited to academic research. Quantum-hardened encryption was added to OpenSSL in 2014 and a freeware version is available on GitHub so it’s reasonable to assume that more implementations are out there.

If you are determined to wade through the math (as I said earlier, I am still inching my way through this article), click HERE. A broader view of post-quantum cryptography is HERE.

More articles by Bernard…