Fully Homomorphic Encryption and Post-Quantum Cryptography

October 5, 2022

Nigel Smart

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

Read more related posts

No items found.

Privacy is necessary for an open society in the electronic age. Privacy is not secrecy. A private matter is something one doesn't want the whole world to know, but a secret matter is something one doesn't want anybody to know. Privacy is the power to selectively reveal oneself to the world.If two parties have some sort of dealings, then each has a memory of their interaction. Each party can speak about their own memory of this; how could anyone prevent it? One could pass laws against it, but the freedom of speech, even more than privacy, is fundamental to an open society; we seek not to restrict any speech at all. If many parties speak together in the same forum, each can speak to all the others and aggregate together knowledge about individuals and other parties. The power of electronic communications has enabled such group speech, and it will not go away merely because we might want it to.Since we desire privacy, we must ensure that each party to a transaction have knowledge only of that which is directly necessary for that transaction. Since any information can be spoken of, we must ensure that we reveal as little as possible. In most cases personal identity is not salient. When I purchase a magazine at a store and hand cash to the clerk, there is no need to know who I am. When I ask my electronic mail provider to send and receive messages, my provider need not know to whom I am speaking or what I am saying or what others are saying to me; my provider only need know how to get the message there and how much I owe them in fees. When my identity is revealed by the underlying mechanism of the transaction, I have no privacy. I cannot here selectively reveal myself; I must always reveal myself.Therefore, privacy in an open society requires anonymous transaction systems. Until now, cash has been the primary such system. An anonymous transaction system is not a secret transaction system. An anonymous system empowers individuals to reveal their identity when desired and only when desired; this is the essence of privacy.Privacy in an open society also requires cryptography. If I say something, I want it heard only by those for whom I intend it. If the content of my speech is available to the world, I have no privacy. To encrypt is to indicate the desire for privacy, and to encrypt with weak cryptography is to indicate not too much desire for privacy. Furthermore, to reveal one's identity with assurance when the default is anonymity requires the cryptographic signature.We cannot expect governments, corporations, or other large, faceless organizations to grant us privacy out of their beneficence. It is to their advantage to speak of us, and we should expect that they will speak. To try to prevent their speech is to fight against the realities of information. Information does not just want to be free, it longs to be free. Information expands to fill the available storage space. Information is Rumor's younger, stronger cousin; Information is fleeter of foot, has more eyes, knows more, and understands less than Rumor.We must defend our own privacy if we expect to have any. We must come together and create systems which allow anonymous transactions to take place. People have been defending their own privacy for centuries with whispers, darkness, envelopes, closed doors, secret handshakes, and couriers. The technologies of the past did not allow for strong privacy, but electronic technologies do.We the Cypherpunks are dedicated to building anonymous systems. We are defending our privacy with cryptography, with anonymous mail forwarding systems, with digital signatures, and with electronic money.Cypherpunks write code. We know that someone has to write software to defend privacy, and since we can't get privacy unless we all do, we're going to write it. We publish our code so that our fellow Cypherpunks may practice and play with it. Our code is free for all to use, worldwide. We don't much care if you don't approve of the software we write. We know that software can't be destroyed and that a widely dispersed system can't be shut down.Cypherpunks deplore regulations on cryptography, for encryption is fundamentally a private act. The act of encryption, in fact, removes information from the public realm. Even laws against cryptography reach only so far as a nation's border and the arm of its violence. Cryptography will ineluctably spread over the whole globe, and with it the anonymous transactions systems that it makes possible.For privacy to be widespread it must be part of a social contract. People must come and together deploy these systems for the common good. Privacy only extends so far as the cooperation of one's fellows in society. We the Cypherpunks seek your questions and your concerns and hope we may engage you so that we do not deceive ourselves. We will not, however, be moved out of our course because some may disagree with our goals.The Cypherpunks are actively engaged in making the networks safer for privacy. Let us proceed together apace.Onward. By Eric Hughes. 9 March 1993.