Quantum Computing and Quantum Cryptography

Quantum computing is a very rapidly evolving technology that can completely change the way we look at computer science. Using quantum computers, the hardest computational problems (NP problems or even NPC problems) could be solved in polynomial time, rendering most of our current crypto algorithms useless.

Introduction to quantum computing

Quantum computers are fundamentally different from “normal” computers. They are built on qubits, which are quantum objects, instead of “normal” bits, which can only be 1 or 0. In quantum computer science, the qubits are described by a so-called Block sphere. A quantum computer operates on its qubits using quantum gates. Usually the calculation ends with a measurement, which as a side-effect (because of quantum physics fundamentals) forces the measured qubits to a fixed 0 or 1. Usually a quantum program is run many times, and the result becomes visible in the statistics of the measured qubits.

A good introductory article to quantum computing is this article by James Wootton. It explains the fundamentals of quantum computing and the readers can experiment themselves with this Hello Quantum app. James Wootton also wrote what is probably the first game on a quantum computer.

For more in-depth learning and experimentation, there is a larger amount of tutorials, examples and simulation software available as open source on GitHub.

Shor’s algorithm

Most popular public-key crypto algorithms rely on one of three mathematical problems:

• The integer factorization problem
• The discrete logarithm problem
• The elliptic-curve discrete logarithm problem

These three mathematical problems are considered extremely hard (NP hard) and impossible for “normal” computers to solve if the key size is big enough. The mathematician Peter Shor formulated in 1994 an algorithm for quantum computers that can solve all three of these problems (if enough qubits are available). In 2001, Shor’s algorithm was demonstrated by a group at IBM, solving a simple factorization problem and using 7 qubits.

Post quantum cryptography

Since the evolution of quantum computers, cryptographers have started researching new crypto algorithms that are “quantum hard” (resistant against quantum computers). Most public-key crypto algorithms are vulnerable to quantum computers, while most symmetric crypto algorithms and hash functions are believed to be resistant (if the key length is sufficiently large).

The post-quantum cryptography conference describes the latest development in post quantum cryptography.