GRI Quantum Risk Assessment Report – Part 2

A Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions – Part 2 (RSA & ECC)

This report, “A Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions” provides our next update on our ongoing work related to estimating the real-world effort it will take for a quantum computer to compromise specific cryptographic functions at the foundation of protecting our ICT infrastructure.

The cryptographic security of a protocol is typically measured in terms of a ‘bit strength’, which is a number n, such that it takes 2n basic operations, using the best-known methods, to break the security of the protocol. Increasing computational power means that what is considered to be ‘sufficient’ strength increases over time, for example with many applications moving from 80 bits to 112 bits to 128 bits over the past years.

Sometimes cryptanalytic algorithms improve, and the bit strength of a protocol turns out to be substantially lower than previously believed, as happened with the RSA system in the 1980s. Quantum computing brought a paradigm shift that drastically reduces the operations needed to break the current public-key algorithms, and substantially reduces the resources needed to break symmetric key cryptography.

Our initial work focused on symmetric key cryptanalysis, and this next installment is focusing on public key cryptanalysis, where the speed-ups offered by quantum computing are more devastating. Unlike the case with AES and SHA algorithms, increasing key length is not a viable approach to defending against the known quantum algorithms. For example, with AES, doubling key sizes from 128 bits to 256 bits increased our benchmark estimates of the work needed to cryptanalyze on a quantum computer from 2101.4 to 2169.9 which represents an astronomical increase in the required computing resources (by a factor of roughly 268.5 ≈ 4.2 x 1020). In contrast, doubling RSA key sizes from 1024 bits to 2048 bits only increased the benchmark estimate from 3.6 hours to 28.6 hours and from 2.6 million physical qubits to 6.2 million physical qubits, which in comparison is a very modest increase in resources required.

The report also allows for comparisons between ECC and RSA, for example 2.5 hours and 1.8 million physical qubits for NIST ECC P-160 versus 3.6 hours and 2.6 million physical qubits for RSA-1024.

Our ongoing work will apply various optimizations and compare the result to the current benchmarks, and also analyze additional cryptographic functions.