Calculating resource estimates for cryptanalysis

Mathias Soeken

We’re excited to release the Resource Estimation and Cryptography interactive experience in Azure 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):

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.

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";
    }
}

We can estimate this Q# program by submitting it to an Azure Quantum workspace using the azure_quantum Python package. To do so, we are setting up a connection to an Azure Quantum workspace (Learn how to create a workspace). You can find the values for resource_id and location in the Overview page of the Quantum workspace. (The complete code example is available on GitHub)

workspace = Workspace(
    resource_id="",
    location=""
)
estimator = MicrosoftEstimator(workspace)

We then define the input parameters for the job. In there we specify the key size, here 256. We use batching to submit multiple target parameter configurations at once. In here we specify the four configurations that correspond to the realistic and optimistic settings for both gate-based and Majorana qubits. For all configurations, we set the error budget to 0.333, i.e., we compute physical resource estimates considering a success rate about 67%.

params = estimator.make_params(num_items=4)

params.arguments["keysize"] = 256

# Error budget
params.error_budget = 0.333

# Gate-based (realistic)
params.items[0].qubit_params.name = QubitParams.GATE_NS_E3
# Gate-based (optimistic)
params.items[1].qubit_params.name = QubitParams.GATE_NS_E4
# Majorana (realistic)
params.items[2].qubit_params.name = QubitParams.MAJ_NS_E4
params.items[2].qec_scheme.name = QECScheme.FLOQUET_CODE
# Majorana (optimistic)
params.items[3].qubit_params.name = QubitParams.MAJ_NS_E6
params.items[3].qec_scheme.name = QECScheme.FLOQUET_CODE

Finally, we create a job by submitting the Q# operation together with the input parameters, and retrieve the results after it has completed. We then use the result object to create a summary table using the summary_data_frame function. The table contains various entries, but in this example, we only print the numbers of physical qubits and physical runtimes, the same that are plotted in the experience on the Azure Quantum website.

job = estimator.submit(ECCEstimates, input_params=params)
results = job.get_results()

table = results.summary_data_frame(labels=[
    "Gate-based (reasonable)",
    "Gate-based (optimistic)",
    "Majorana (reasonable)",
    "Majorana (optimistic)"
])

print()
print(table[["Physical qubits", "Physical runtime"]])

The output is as follows:

                        Physical qubits Physical runtime
Gate-based (reasonable)           5.87M         21 hours
Gate-based (optimistic)           1.54M         11 hours
Majorana (reasonable)             3.69M          8 hours
Majorana (optimistic)             1.10M          4 hours

The estimates in the table are formatted for better readability. You can also retrieve the non-formatted values, e.g., the number of physical qubits and physical items for the first configuration (gate-based realistic) are access with results[0]["physicalCounts"]["physicalQubits"] and results[0]["physicalCounts"]["runtime"], respectively.

RSA

RSA is one of the oldest, yet widely used, public-key cryptography approaches. The paper How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749) describes an implementation to factor RSA integers based on state-of-the-art quantum operations for phase estimation and quantum arithmetic. The code is mostly similar to the code we are using for ECC estimates described above. However, we implemented the algorithm in Rust, and compiled it to LLVM. Therefore, we submit the QIR, which is the LLVM output, directly to the Azure Quantum Resource Estimator. (The complete code example is available on GitHub)

import urllib.request
bitcode = urllib.request.urlopen("https://aka.ms/RE/some-nice-uri").read()

The entry point in this implementation takes 4 input arguments, the actual product (in this sample the 2048-bit RSA integer from the RSA challenge), a generator, and two parameters to control windowed arithmetic in the implementation. We take its values from the paper, in which 5 is suggested a good value for both of them. Then, we configure the qubit parameters and QEC scheme as above in the input parameters, and submit them together with the bitcode to the resource estimator.

params = estimator.make_params(num_items=4)

params.arguments["product"] = "25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357"
params.arguments["generator"] = 7
params.arguments["exp_window_len"] = 5
params.arguments["mul_window_len"] = 5

# specify error budget, qubit parameter and QEC scheme assumptions
params.error_budget = 0.333
# ...

job = estimator.submit(bitcode, input_params=params)
results = job.get_results()

The code for evaluating the data is the same and returns the following table:

                        Physical qubits Physical runtime
Gate-based (reasonable)          25.17M           1 days
Gate-based (optimistic)           5.83M         12 hours
Majorana (reasonable)            13.40M          9 hours
Majorana (optimistic)             4.18M          5 hours

We can use the same program to compute resource estimates for other RSA integers, including the RSA challenge numbers RSA-3072 and RSA-4096, whose estimates are part of the cryptography experience on the Azure Quantum website.

Advanced Encryption Standard (AES)

The Advanced Encryption Standard (AES) is a symmetric-key algorithm and a standard for the US federal government. In order to obtain the physical resource estimates for breaking AES, we started from the logical estimates in Implementing Grover oracles for quantum key search on AES and LowMC (arXiv:1910.01700, Table 8), with updates on the qubit counts suggested in Quantum Analysis of AES (Cryptology ePrint Archive, Paper 2022/683, Table 7). In principle, we can follow the approach using the AccountForEstimates function as we did for ECC. This operation and the logical counts in the Azure Quantum Resource Estimator are represented using 64-bit integers for performance reasons, however, for the AES estimates we need 256-bit integers. As a result we used an internal non-production version of the resource estimator that can handle this precision. Further details can be made available to researchers if you run into similar precision issues in your resource estimation projects.

Learn more

The Azure Quantum Resource Estimator can be applied to estimate any quantum algorithm, not only cryptanalysis. Learn how to get started in Azure Quantum today with the Azure Quantum documentation. In there you find how to explore all the rich capabilities in various notebooks, with applications in quantum chemistry, quantum simulation, and arithmetic. You can learn how to submit your own quantum programs written in Q#, Qiskit, or directly provided as QIR, as well as how to set up advanced resource estimation experiments and apply customizations such as space/time tradeoffs.

Mathias Soeken Senior Software Engineer, Quantum

Follow