Voluntary Mind

Quantum Computing and Post Quantum Crypto

While working on BIP324 there has been a lot of conversation about making sure that the encryption scheme is not trivialized in the presence of quantum computers. I’ve always found that topic intimidating so I spent some time studying it at a high-level to engage in the conversation in a more informed way. These are my notes from those few days.

What is a quantum computer?

A quantum computer is a device that manipulates qubits (quantum-bits), just like classical computers manipulate bits. Qubits however are not like bits. A classical bit is either 0 or 1 at any given time. A qubit can be in the 0 and 1 states simultaneously (a phenomenon known as superposition) with some probability of being in each. However when observed, the qubit is either in it’s 0 state or 1 state (with the characteristic probabilities). Qubits can also be entagled. Observing one qubit can tell us about the state of another entangled qubit even if they are very far away.

A quantum computer is not a faster version of a classical computer. It is a new computing paradigm and it is better at some computations than a classical computer.

Physical qubits

Qubits are built and maintained using superconductor circuits. We only know how to maintain them in stable states for very small amounts of time today. The physical construction, decay, etc of qubits is beyond the scope of this post, and we are only going to concern ourselves with the computational aspects.

Qubit representation and characteristics

A qubit is characterized as: alpha |0> + beta |1> where alpha and beta are complex numbers of the form x + y * i such that |alpha|^2 is the probability that when observed, the qubit will read 0, and |beta|^2 is the probability of reading 1. Definitionally, |alpha|^2 + |beta|^2 = 1, so not every pair of complex numbers can be a valid qubit.

Consider the qubit psi = 1/sqrt(2) |0> + 1/sqrt(2) |1>. Here alpha = beta = 1/sqrt(2) + 0 * i and the probability of observing either 0 or 1 is 1/2.

Now consider the qubit phi = i/sqrt(2) |0> - 1/sqrt(2) |1>. The probability of observing this qubit in the 0 or 1 state is the same as psi, but they are fundamentally different qubits as when a quantum algorithm operates on them, they’ll diverge.

Generalizing this, a quantum byte is eight qubits and is represented as: alpha0 |00000000> + alpha1 |00000001> + ... + alpha255 |11111111>. |alphaN|^2 is the probability of observing the quantum byte with value N in [0, 255]. Because for every qubit, |alpha|^2 + |beta|^2 = 1, we can generalize: |alpha0|^2 + |alpha1|^2 + ... + |alpha255|^2 = 1. This is actually easy to prove with two qubits on paper. So we can see that n qubits are characterized by 2^n complex numbers. This is the core reason that a classical computer cannot simulate a quantum computer easily. It requires an exponential amount of memory to simulate.

Quantum algorithms

Classical algorithms manipulate classical bits. This is why the NOT gate, is the most basic classical gate. You can either leave a bit alone of flip it. Quantum algorithms are also known as quantum gates. Each quantum gate is a matrix that can be multiplied with a qubit (or many qubits) to obtain new qubits.

[2x2 quantum gate] * [2xN qubits representation] = [2xN new qubits]

Of course, alpha and beta for the new qubits must also satisfy |alpha|^2 + |beta|^2 = 1, so not every matrix is a valid quantum gate. Valid quantum gates are also unitary matrices. Unitary matrices are also invertible, so all quantum algorithms are invertible.

An identity gate (identity matrix) leaves the qubits unaltered. The Hadamard gate is an interesting gate that can take deterministic qubits |0> and |1> and turn then into uniformly random qubits. Like all quantum gates, it is invertible, and can also convert uniformly random state into deterministic state.

Quantum speedup

A quantum speedup occurs when a quantum computer can do something much faster than a classical computer. The holy grail of quantum computing is exponential quantum speedup: A task that a classical computer can do in exponential time, i.e. O(k^n), but a quantum computer can do in polynomial time, t.e. O(n^k).

How do quantum algorithms affect cryptography?

Quantum algorithms can solve certain problems much more efficiently than classical algorithms. One such problem is Simon’s problem where quantum computers have achieved exponential speedup. This speedup is a problem for symmetric ciphers but only under very specific circumstances.

Shor’s algorithm

American mathematician Peter Shor discovered in 1994, an algorithm that created an exponential quantum speedup in solving essentially all the hard problems that public-key crypto uses: Shor’s algorithm trivializes prime factoring (hard problem RSA is based on), and the discrete-log problem (both DLP, ECDLP; used in Diffie-Hellman and Elliptic Curve Cryptography). In a world with quantum computers, RSA and Diffe-Hellman will look like Caeser’s Cipher.

Grover’s algorithm

In 1996, Lov Grover published the Grover’s algorithm. On a classical computer, searching in a set is an O(N) operation. Using Grover’s algorithm on a quantum computer, search can be accomplished in O(sqrt(N)). This has implications on all brute-force search. A basic brute-force attack on n-bit symmetric crypto using a classical computer takes O(N) = O(2^n) operations. On a quantum computer, this search will take O(2^(n/2)) operations. This means 128-bit security will look like trivial 64-bit security. All of this applies to birthday attacks on hash functions too. But there’s a simple solution: Doubling the key length makes symmetric crypto quantum resistant.

NET IMPACT OF QUANTUM COMPUTING ON CRYPTO: We need to double key lengths for symmetric crypto and hash functions. We need to find quantum resistant techniques to replace RSA, Diffie-Hellman and Elliptic Curve Cryptography.

Post-quantum cryptography

PQC techniques are being proposed and evaluated in a NIST competition. As this post is being written, there are seven known finalists for the third round that can give us quantum-resistant public-key cryptography as well as key exchange mechanisms. PQC techniques come in many flavors.

Code-based techniques

These techniques are based on the idea of error correcting codes. Essentially, if you encode something using the public key and there are upto t-bits of errors along the way, the private key can still decode the original message by correcting the errors. So you could use this to send something on a noisy channel and correct errors. BUT, you could also parametrize for a large number of errors, intentionally add errors and decode on the other side. The issue with such techniques is that the public keys are hundreds of kilobytes. When considering this for something like Bitcoin, we have to be wary of the impact on SPV nodes and other bandwidth constrained environments like mobile wallets.

The only code-based finalist in the third round of the NIST competition is Classic McEliece which is actually from 1978.

Lattice-based techniques

So far the only other viable techniques are from lattice-based cryptography. The underlying hard problems are Short-Integer Solution(SIS) and Learning with errors(LWE) which are both not broken by Shor’s algorithm. Most NIST finalists are lattice techniques. The keys as well as signatures are reasonable in size.

Multivariate cryptography

These techniques are based on the underlying problem of solving multivariate equations. If successful, this could lead to elegant security proofs about the underlying hard problems, but so far the techniques have proven unviable.

Hash-based cryptography

The idea is is that you make priv=K; pub=Hash^W(K) and then for a message M, the signature is sig=Hash^(W-M)(K). The receiver can verify Hash^M(sig) == pub. The techniques are not very popular due to limits on messages that can be signed like: 0 <= M =< W-1 and large signature sizes.

Closing thoughts

So, is all we need to do just double the symmetric crypto key lengths and use the NIST winners for KEM/public-key crypto use cases? Not so fast. There are a few other considerations: