Quantum computing and post-quantum cryptography – Andrew Savchenko

Classical cryptography is designed to withstand cryptanalysis with classical computers. Quantum cryptography uses properties of quantum mechanics for crypto applications, e.g. to generate random numbers. That is not the topic of this talk. Postquantum cryptography is cryptography resilient to quantum computing and is the topic of this talk.

A qubit is an analog bit of information. Quantum logic gates operate on them.

A qubit is based on the spin of an electron. The wave function Q has an amplitude for spin up and for spin down – it’s a combination of the two states, they are superimposed. If you combine multiple electrons, they will have more states, 2N possible states for N qubits. But the different states will have different probabilities. Thus, 42 qubits are sufficient to save a 4TB harddisk. However, only N bits can be extracted from them. Also what you read are random bits with different probabilities – the results are not deterministic.

States can be manipulated by affecting the amplitudes of different qubits.

There are several implementations of qubits: electron spin, atomic nucleus, photon, … . None of them are stable, they decay very fast. They get errors easily, and they build up quickly, so they have to be corrected. Qutrits are more stable but harder to implement and to manipulate.

Quantum storage transfers the state to more permanent storage, so it can survive about 2s.

Quantum gates can be modelled as matrices applied to the amplitudes. Again several implementations exist. Operations are reversible, until measurement is done. Since the result of the operation is probabilistic, it must either be checked or repeated to get an accurate result. Checking e.g. in cryptanalysis: just verify with a classical computer if the key that was computed is correct.

Quantum computing can perform some operations very fast, e.g. a DFFT in (log N)2 instead of N log N, using 2N qubits. 3072-bit RSA can be broken in 6144 qubits, the equivalent 256-bit DSA (ECC) in 1800 qubits.

Quantum brute forcing can be done with Grover’s algorithm. If you have N unknown inputs with 1 known output, it can brute force it in O(sqrt(N)) operations (while traditional brute forcing would require O(N)).

The concrete impact on crypto is as follows:

  • Symmetric crypto is safe but key size is halved.
  • Common asymmetric crypto is dead, especially elliptic curves.
  • New quantum resistant asymmetric algorithms are developed, with implementations in gnupg and openssl fork. Only “resistant” because it can’t be proven that no algorithm exists to solve it quickly.

D-Wave systems has a 2000-qubit machine (which operates at 0.015K so definitely not room temperature). It is targeted at optimisation problems using quantum annealing, so not for cryptanalysis. Sizes are still growing exponentially.

Since the new quantum-resistant algorithms are not very well proven yet, it’s best to combine them with classical algorithms (ECC, RSA).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s