Post-Quantum Cryptography

Browse any popular science blog or news site and you will not have to look far before finding announcements of new breakthroughs and records in the construction of quantum computers. Clearly, a lot of resources are being spent to build quantum computers. And for good reason — the potential applications to pharmaceutics and materials science are veritable goldmines. But how does the advent of quantum computers affect cryptography?

Hash functions, block ciphers, their modes of operations, as well as symmetric authenticated encryption schemes are barely affected. Quantum computers excel when solving problems that exhibit a particular mathematical structure. As far as we know, these keyed and unkeyed primitives do not possess the kind of structure that would make a quantum attack exponentially faster than a classical one. While there are generic quantum search algorithms that can be deployed, these perform better than their classical on paper only and in the worst case extending the key by a few bits suffices to ensure the same security.

The threat of quantum computers is completely different when it comes to public key cryptography, particularly cryptosystems based on the RSA and elliptic curve discrete logarithm problems. A quantum algorithm known as Shor’s algorithm solves these hard problems in the blink of an eye. Fortunately, there are hard mathematical problems that can achieve the same thing but seem immune to Shor’s algorithm. However, many of the security proofs showing that an attacker who breaks the cryptosystem can be made to solve the hard problem, assume adversaries incapable of quantum computations. In order to have a strong security argument, the security proofs must be reconsidered in the setting where the attacker possesses a quantum computer.

The field of post-quantum cryptography deals with

  • alternative branches of mathematics, their computational problems, and their quantum complexity
  • the construction of useful and performant cryptographic schemes from these computational problem
  • the security proofs for these cryptosystems especially in the setting where attackers have quantum computers.

Resources