Fully Homomorphic Encryption and Post-Quantum Cryptography

There has been a lot of discussion recently about Post-Quantum Cryptography, or PQC. The reason is that security experts are worried about what could happen if someone developed a quantum computer. Due to Shor’s algorithm, a quantum computer would be able to break most cryptography – namely RSA and ECC cryptography – which is the backbone of our modern economy... To prevent this disastrous scenario, the National Institute for Standards and Technology (NIST), the US agency for standards, initiated an effort some years ago to find replacement, “post-quantum” algorithms for RSA and ECC, i.e. algorithms which would resist the potential decryption efforts of a quantum computer.

In July 2022, NIST announced the (partial) culmination of this year-long effort. The decision was made to select one encryption algorithm (Kyber) and three signature algorithms (Dilithium, Falcon and SPHINCS+) for a formal standardization process. Over the next few years, we expect Kyber, Dilithium, Falcon and SPHINCS+ will move from academic papers into formal standards documents, and then eventually into products.

This decision is a strong endorsement by NIST of cryptographic schemes based on hard problems arising from lattices. Of the four selected algorithms, three (Kyber, Dilithium and Falcon) are based on lattices. 

Lattice Hard Problems

All public key encryption and signature algorithms are based on a hard problem. The RSA algorithm is based on the hard problem of factoring large integers into their prime components, while ECC algorithms are based on the hard problem of solving discrete logarithm problems on an elliptic curve. However, factoring integers and solving discrete logarithms is exactly what Shor’s algorithm does. Thus, if we are to have post-quantum cryptography, then we need hard mathematical problems which are resistant to quantum computers.

Lattice problems are exactly that: a mathematical problem which appears to be resistant to quantum computers. NIST’s endorsement of lattice based cryptography gives further weight to the body of expert knowledge that believes lattice-based cryptography is a solution to the problems raised by the potential of quantum computers.

In two dimensions, a lattice is just an infinite set of dots across a plane. The dots are generated by taking integer linear combinations of two “basis vectors” (as we are working in a two-dimensional plane). In the picture, these are the black two vectors. The main hard mathematical problem is to find two short vectors which also generate the lattice – in this example, the two red vectors. In two dimensions, this problem seems ridiculously easy. However, as we scale the number of dimensions higher, it becomes very difficult indeed. So difficult, in fact, that we do not believe that even a quantum computer will be able to solve this hard problem.

Determining the exact dimension on which to base cryptography, and exactly how the initial (black) basic vectors should be chosen, is a subtle task. Academics have worked on various tools to help guide them in how to select parameters. The most famous of these is the Lattice Estimator, initially developed by Martin Albrecht:

https://github.com/malb/lattice-estimator

Lattice Cryptography and Homomorphic Encryption

Now we have a hard problem on which to base standard cryptography, i.e. public key encryption and public key signatures, which is resistant to the invention of a quantum computer. And we have such a strong  belief that this is indeed the hard problem on which to base our future internet that a government body, NIST, has endorsed lattice-based cryptography as one of the ways forward.

This is great news for homomorphic encryption. It turns out that ALL practical Fully Homomorphic Encryption schemes are also based on the hard problems in lattices, outlined above. In particular, the TFHE scheme utilized by Zama is built upon lattice-based cryptography. This means that TFHE can benefit from all the analysis and design work which the community is currently investing in lattice-based cryptography.

Indeed, Zama makes use of the same lattice difficulty-estimator software (above) that is utilized by the NIST candidates. Zama is one of the sponsors of this software, and a number of Zama employees are involved in its design and maintenance. 

So not only is Zama helping the world move to Fully Homomorphic Encryption, but we are also indirectly aiding in the move to a post-quantum future.

Additional links

• Zama's newsletter
• Zama on twitter
• Read our research papers