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.
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
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
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
[0, 255]. Because for every qubit,
|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.
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]
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
|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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
- Existing RSA, DH, ECC techniques have been battle-tested for decades and we have much lesser experience with PQC techniques. The careful approach will be to layer the techniques. For example, you can do a traditional ECDH, and then using the shared secret, do a PQC KEM like Classic McEliece to then generate another shared secret that you’ll upgrade the symmetric encryption stream to. This is the current thought process for BIP324 as well. Someone looking to break the stream will need to break both techniques. So in case the PQC scheme you pick is broken by some number theoretic advancement, the floor of security is still from the pre-quantum scheme.
- PQC keys are hard to make as indistinguishable from random as say ECDH with libsecp256k1. So they are less censorship-resistant: this is another argument for layering described above.
- Once PQC schemes are standardized, we will need to pick secure parameters. NIST focuses a lot on parameter selection too. But sometimes, the reasoning is not super clear and the NSA is involved. A secure PQC scheme with weak parameter selection will still leave us vulnerable.
- Pre-quantum schemes can also be made more quantum resistant. For example, Signal uses not just the public keys exchanged, but also the past messages in a conversation to derive the keys for the symmetric crypto schemes. This increases what is required of the attacker in order to properly execute an attack using a quantum computer.
- Encryption is more important than signatures: When you encrypt something, the user should be able to expect confidentiality for a human lifetime of 70-80 years. So, we need to think about upgrading encryption before signatures. With signatures, you can do things like ask users to sign a new public PQC key with the old private key to reassign ownership to the PQC public key. I suspect there will be some clever upgrade paths like that for Bitcoin L1 users. Encryption needs more urgent attention in terms of quantum resistance.