Introduction
We’re excited to release the Resource Estimation and Cryptography interactive experience in Microsoft Quantum. This experience offers a deep dive into the potential implications of fault-tolerant quantum computing on common cryptographic systems. Thanks to the power of the Azure Quantum Resource Estimator, we can provide estimates of the number of qubits required and expected runtime for a range of quantum algorithms that could be used to break these cryptographic systems across different assumptions of hardware configurations. These estimates help generate actionable insights that can help inform every organization on their path to a quantum-safe future.
This blog offers an inside look into the computation of these estimates. Our resource estimator supports various input formats for quantum programs, including Q# and Qiskit, which are then translated into QIR, the Quantum Intermediate Representation. In addition to customizable qubit parameters, we also utilize predefined models in our experience. To perform resource estimation of physical hardware components from logical resource counts (which do not take the overhead for quantum error correction into account) extracted from papers, we utilize a specialized resource estimation operation in Q#. Furthermore, we have developed an algorithm in Rust and translated it into QIR by leveraging the LLVM framework, which also powers QIR. The following three sections delve into the specific details for each encryption algorithm addressed in our interactive experience.
In the experience we compare the following three cryptographic algorithms in different key strengths (for elliptic curve cryptography, these correspond to concrete prime field Weierstrass curves, which you can lookup via the link):
Algorithm | Standard | Enhanced | Highest |
Elliptic curve | P-256 | P-384 | P-521 |
RSA | 2048 | 3072 | 4096 |
AES | 128 | 192 | 256 |
In the estimation, we assume that we lower the quantum algorithm to a sequence of physical quantum gates. For these we assume the following two choices of qubits and error rates. The values are based on some pre-defined qubit parameters available in the resource estimator. The Majorana and gate-based pre-defined parameters in the resource estimator correspond to topological and superconducting qubit types in the experience, respectively.
Qubit type and error rate | Majorana (reasonable) | Majorana (optimistic) | Gate-based (reasonable) | Gate-based (optimistic) |
Measurement time | 100 ns | 100 ns | 100 ns | 100 ns |
Gate time | 100 ns | 100 ns | 50 ns | 50 ns |
Measurement error rate | 0.0001 | 0.000001 | 0.001 | 0.0001 |
Gate error rate | 0.05 | 0.01 | 0.001 | 0.0001 |
Elliptic curve cryptography (ECC)
Elliptic curve cryptography (ECC) is a public-key cryptography approach based on the algebraic structure of elliptic curves. The approach requires smaller key sizes compared to approaches such as RSA, while providing an equal security against classical cryptanalysis methods. The paper Improved quantum circuits for elliptic curve discrete logarithms (arXiv:2001.09580) describes a quantum algorithm to solve the elliptic curve discrete logarithm problem (ECDLP) based on Shor’s algorithm. We make use of the Q# operation AccountForEstimates (also find details on how to use the operation) that allows us to derive physical resource estimates from previously computed logical ones. This operation is very helpful when logical estimates have already been computed, as for example in this paper and listed in there as part of Table 1.
From that table we extract the relevant metrics, which are the number of T gates, the number of measurement operations, and the number of qubits. The other metrics are not relevant for the computation, since the physical resource estimation relies on Parallel Synthesis Sequential Pauli Computation (PSSPC, Appendix D in arXiv:2211.07629), which commutes all Clifford operations and replaces them by multi-qubit Pauli measurements. The paper discusses various optimization flags in the implementation to minimize the logical qubit count, T count, or the logical depth. We found that the physical resource estimates are best, both for physical qubits and runtime, when using the option to minimize qubit count. The following Q# program includes the estimates for the considered key sizes 256, 384, and 521.
open Microsoft.Quantum.ResourceEstimation;
operation ECCEstimates(keysize: Int) : Unit {
if keysize == 256 {
use qubits = Qubit[2124];
AccountForEstimates([
TCount(7387343750), // 1.72 * 2.0^32
MeasurementCount(118111601) // 1.76 * 2.0^26
], PSSPCLayout(), qubits);
} else if keysize == 384 {
use qubits = Qubit[3151];
AccountForEstimates([
TCount(25941602468), // 1.51 * 2.0^34
MeasurementCount(660351222) // 1.23 * 2.0^29
], PSSPCLayout(), qubits);
} else if keysize == 521 {
use qubits = Qubit[4258];
AccountForEstimates([
TCount(62534723830), // 1.82 * 2.0^35
MeasurementCount(1707249501) // 1.59 * 2.0^30
], PSSPCLayout(), qubits);
} else {
fail $"keysize {keysize} is not supported";
}
}