In a previous post I discussed what the advent of a quantum computer would mean to classical public key cryptography. All of our existing deployed public key techniques are based on the difficulty of factoring numbers or of finding discrete logarithms. Both of these problems are considered hard in classical computing, however a quantum computer (if it could be built) would solve both of these problems in polynonial time.
The potential creation of a quantum computer leads people to consider what would happen to cryptography if one were built. The key issue is that of finding a replacement for public key encryption and digital signatures. These underpin our entire digital economy, from bank cards through to internet transactions.
As previously explained we cannot copy quantum states, thus any replacement technology for our existing public key schemes needs to work on classical bits. In addition, almost all computers in a post- quantum world will still be classical. Thus we need to replace our existing public key schemes by classical algorithms working on classical data.
However, to maintain security against quantum computers we need to find algorithms which are secure against such computers. This is the problem to which the subject of Post-Quantum Cryptography addresses itself. A number of candidate systems have been proposed and are currently being thoroughly examined by the cryptographic community.
One of the most popular ways of designing such Post-Quantum systems is to use a mathematical structure called a lattice. A lattice is like a grid, but is in n-dimensional space. There are many ways of representing a lattice in an algorithm some of these ways are better than others. It turns out we can use this multitude of representations for cryptographic purposes. As a secret key we use a nice representation, and as a public key we use a less nice representation. It is believed, for suitably chosen representations and lattices, which even a quantum computer cannot efficiently find a method of transforming the less nice representation into a nice one. Using this idea we can build encryption schemes like NTRU, homomorphic encryption schemes like BGV, and signature schemes such as BLISS.