Skip to content

Breaking cryptosystems

Overview

Much of modern cryptography relies on computational assumptions.1 A cryptosystem is considered secure if, assuming that a particular mathematical problem is hard to solve, an adversary cannot learn more than a negligible amount of information about what is being encrypted. The earliest such cryptosystems used particular problems from number theory, and variants are widely deployed to this day [1]. These cryptosystems are in the class of public-key cryptography, which enables any user to perform tasks like encryption, in contrast to symmetric cryptography, in which users have to pre-share a secret key.

Quantum computers use quantum algorithms to solve computational problems, and in some cases they provide a speedup over the best known classical techniques. When they are applied to the underlying computational task in a cryptosystem, a large speedup over classical methods can break the cryptosystem, in that an adversary efficiently learns the encrypted information to a non-negligible degree. One of the first discovered and most famous applications of quantum computing is Shor's algorithm [2], which breaks common methods of public-key cryptography based on number theory, including factoring, discrete logarithm, and elliptic curves. The applications of these public-key cryptosystems include encryption to hide the contents of a message, signatures that prevent tampering and impersonation, and key exchange to generate a key for symmetric cryptography [3]. In this section, we restrict our focus to two of the most widely used cryptosystems: Rivest–Shamir–Adleman (RSA) and elliptic curves.

Actual end-to-end problem(s) solved

The RSA cryptosystem [4] relies on a user choosing a large number \(N\) that is the product of two prime numbers; arithmetic is done modulo \(N\). Denote by \(n=\lceil \log_2(N) \rceil\) the number of bits specifying \(N\). The two prime numbers are kept private, but their product is publicly revealed, along with an exponent \(e\). A message \(m\) is encrypted as \(m^e \bmod N\). By construction, using tricks from number theory, there exists \(d\) such that \((m^e)^d \bmod N = m \bmod N\). That is, exponentiating with \(d\) performs decryption. The user efficiently solves for the necessary value of \(d\) using the Euclidean algorithm, by knowing the prime factors of \(N\), along with \(e\). However, if an adversary is able to find the factors of \(N\) after the construction by the user, they can also solve for \(d\) and thereby decrypt messages. The security of the cryptosystem comes from the difficulty of factoring large numbers, i.e., finding the two primes that multiply to \(N\).

A similar cryptosystem is based on elliptic curves, which has the advantage that classical algorithms attacking it are even less successful than for RSA, so the ratio of bits of security (quantifying the number of attacks needed to learn the encrypted information; see section on weakening cryptosystems for details) relative to key size is larger. Consequently, fewer resources (e.g., communication, complexity of encryption and decryption) are required to implement elliptic curve cryptography. Instead of using the multiplicative group of a finite field, consider points on an elliptic curve [5, 6]:

\[\begin{equation} y^2=x^3+ax+b\,,\quad a,b\in K\,, \end{equation}\]

where \(K\) is a field. A special group operation can be defined over points \((x,y)\) lying on the elliptic curve. Then, given a secret number \(c\) and a point \(P = (x,y)\), the point \(P\) can be added to itself under this operation \(c\) times, yielding the point \(P'=cP\), which can be efficiently computed from \(c\) and \(P\). Multiplication by \(c\) is analogous to the exponentiation in RSA, above. The assumption of hardness is in the following problem, known as the elliptic curve discrete logarithm problem (ECDLP): For two points \(P,P'\) on an elliptic curve, find an integer \(c\) such that \(P'=cP\). As an example of this cryptosystem, for a publicly known point \(P\), a receiver chooses a secret \(c\) and publishes \(cP\). The sender chooses a random integer \(d\) and encrypts the message \(m\) as \(m+ d(cP)\), also sending \(dP\). Since group multiplication is commutative, to decrypt the message, the receiver multiplies \(dP\) by \(c\) and subtracts the product from the encrypted message.

Dominant resource cost/complexity

Shor's algorithm [2] solves the number-theoretic problem of order finding: given \(n\)-bit positive integer \(N\) and \(x\) coprime to \(N\), find the smallest integer \(r\) such that \(x^r=1 \bmod N\). Factoring was shown to reduce to order finding. In particular, there is an efficient, otherwise classical algorithm, of classical complexity \(\mathcal{O}\left( n^3 \right)\) [7], that uses order finding as a quantum subroutine. To describe the quantum algorithm for order finding, let the function \(f\) denote modular exponentiation, i.e., \(f(e) = x^e \bmod N\), and note that \(f\) is periodic with (unknown) period \(r\). Also, let \(L\) be a large integer such that an interval of length \(L\) contains many periods, i.e., \(L \gg r\). It can be shown that \(L \geq N^2\) is sufficient. There are three steps. First, an equal superposition over the numbers \(\{0,\ldots,L-1\}\) is formed and the function \(f\) is computed into an ancilla register yielding the state \(L^{-1/2}\sum_{e=0}^{L-1} \ket{e}\ket{f(e)}\). Second, a measurement is performed on the ancilla register, which, due to the periodicity of the function \(f\), yields a state \((\lceil L/r \rceil)^{-1/2} \sum_{j=0}^{\lfloor L/r \rfloor}\ket{rj + y}\) for \(0\leq y<r\) a random and unknown integer.2 Third, a quantum Fourier transform is performed. In the case that \(L\) is a multiple of \(r\), the result is

\[\begin{equation} \frac{\sqrt{r}}{L}\sum_{j=0}^{L/r} \sum_{z=0}^{L-1}e^{2\pi i z(rj+y)/L} \ket{z} = \frac{1}{\sqrt{r}}\sum_{\ell=0}^{r-1}e^{2\pi i \ell y/r} \ket{\ell L/r } \,, \end{equation}\]

where the equality follows since coefficients of \(\ket{z}\) for which \(z\) is not equal to \(\ell L/r\) for some integer \(\ell\) vanish due to destructive interference. Measurement of this state then produces an outcome \(\ell L/r\) for a random choice of \(\ell\). The value of \(r\) can be classically computed by dividing the measurement outcome by \(L\) and determining the value of the denominator of the rational number that results; repetition may be required since \(\ell\) and \(r\) could have common divisors. If \(L/r\) is not an integer, the measurement outcome is (with high probability) an integer close to \(\ell L / r\) for some integer \(\ell\). One can deduce the rational number \(\ell/r\) (which allows for the determination of \(r\)) from the estimate of \(\ell L /r\) by writing it as a continued fractions expansion, with classical complexity \(\mathcal{O}\left( n^3 \right)\) [7].

This entire procedure can alternatively be viewed as quantum phase estimation applied to the unitary \(U\) that sends \(\ket{y}\mapsto \ket{xy \bmod N}\) for all \(y\) relatively prime to \(N\), performed with at least \(2n\) bits of precision.

The number of qubits for order finding is \(\mathcal{O}\left( n \right)\), which stems from the number of bits specifying the problem: the first register has size \(2n\), and the ancilla register holding the result \(f(e)\) has size \(n\). Naively, the number of operations is \(\mathcal{O}\left( n^2 \right)\) for the quantum Fourier transform and \(\mathcal{O}\left( n^3 \right)\) for implementing the coherent modular exponentiation \(\ket{e}\ket{0} \mapsto \ket{e}\ket{x^e \bmod N}\). The bottleneck in the complexity is thus from reversible circuits for modular arithmetic. These circuits are closely related to those in classical computing that have been optimized. The best scaling in theory is achieved with algorithms that have large prefactors in their complexity, making them impractical to implement except for large numbers: \(\mathcal{O}\left( n^2\log(n) \right)\) is possible asymptotically, using integer multiplication with \(\mathcal{O}\left( n\log(n) \right)\) scaling [8]. Alternatively, optimization may be performed to, e.g., increase qubit count and decrease gate count. For example, an approximate version of the quantum Fourier transform is implemented with \(\mathcal{O}\left( n\log(n) \right)\) gates and allows factoring with \(\mathcal{O}\left( \log (n) \right)\)-depth quantum circuits [9], at the cost of extra overhead in number of qubits and gates; allowing for \(\mathcal{O}\left( \log^2 (n) \right)\)-depth preserves the circuit size \(\mathcal{O}\left( n^3 \right)\).

A related approach proposed by Regev [10] for quantum factoring has quantum circuit size of only \(\widetilde{\mathcal{O}}\left( n^{3/2} \right)\) gates but the circuit has to be run \(\mathcal{O}\left( n^{1/2} \right)\) times. Furthermore, the algorithm relies on a plausible number-theoretic assumption. The reduction in quantum circuit size may lead to more favorable resource counts in practice.

Essentially the same quantum algorithm of Shor is readily applied to elliptic curves, as well as the discrete logarithm problem (i.e., find \(r\) such that \(a^r=b\) for \(a,b\in G\) where \(G\) is a group) that also is used as a computationally hard problem for cryptography. These applications are all instances of the hidden subgroup problem: Find the generators for subgroup \(K\) of a finite group \(G\), given a quantum oracle performing \(U\ket{g}\ket{h}=\ket{g}\ket{h \oplus f(g)}\), where \(f:G\to X\) (\(X\) is a finite set) is a function that is promised to be constant on the cosets of \(K\) and take unique values on each coset. In the case of period finding, \(G\) is the group \(\mathbb{Z}/L\mathbb{Z}\) under addition, and the hidden subgroup is \(K = \{0,r,2r,\ldots,L-r\}\) (technically a subgroup only if \(r\) divides \(L\)); one can verify that \(f(g) = x^g \bmod N\) is constant on each coset of \(K\). The procedure outlined above for period finding can be applied to other groups, where it is called "the standard method" [11] (which requires generalizing the quantum Fourier transform to arbitrary groups). For abelian groups, the hidden subgroup \(K\) can be determined with \(\mathrm{polylog}(|G|)\) queries to \(f\), but the method does not work for nonabelian groups, such as the symmetric group and the dihedral group.

Existing error corrected resource estimates

The minimum recommended key size for RSA is 2048 bits [12]. Optimizations in the circuits [13, 14] and incorporation of hardware constraints [15] have led to decreasing but also more realistic resource estimates. For key size 2048, assuming nearest-neighbor connectivity, about \(14000\) logical qubits (which includes space for routing and distillation; see sections on quantum error correction and lattice surgery) and \(3\times 10^9\) Toffoli gates are necessary [16].

For elliptic curve cryptography, the minimum recommended key size to ensure 128-bit security, is 256 bits [12] (achieving the same level of security with RSA requires a key size of 3072 bits [17, 18]). For breaking 256-bit elliptic curve cryptography, it is estimated that around three times fewer logical qubits, and 100 times fewer Toffoli gates are required (compared to 3072-bit RSA) [18]. Similar to factoring, improvements have been made in circuit compilation [19] and hardware considerations [20], resulting in an estimate of 2871 logical qubits and \(5.76\times 10^9\) \(T\) gates (note that one Toffoli gate costs around 4 \(T\) gates). As a conclusion, breaking elliptic curve cryptography is easier than factoring for quantum computers in practice [21], relative to their practical difficulty on classical computers.

In both cases (2048-bit RSA [16, 22] and 256-bit elliptic curves [20]), given current hardware schemes based on surface codes, the number of physical qubits is estimated to be on the order of \(10\) million and the computation runs for around \(10\) hours. For a discussion on how to convert between logical and physical resources, see the section on fault-tolerant quantum computation. Optimization based on the particular architecture can give improvements to these estimates. For example, assuming a logarithmic number of nonlocal links, as in photonic implementations, enables breaking elliptic curves around 200 times faster [23]. The algorithms considered in the resource estimates above do not achieve the best known asymptotic scaling, which comes at the cost of large constant prefactors.

Caveats

While the popular cryptosystems based on number-theoretic problems are rendered insecure for public-key cryptography, there exist alternatives that are believed to be secure against quantum computers: e.g., based on error-correcting codes or lattices [3]. These alternative computational problems are believed to be hard for both classical and quantum computers. The National Institute of Standards and Technology (NIST) of the United States plans to provide standards by 2024 to prompt implementation [24]. The class of symmetric cryptography (see a standard text [1] for details) involves computations that do not have much structure, and also is not broken by quantum computers. Instead, the number of bits of security is reduced.

Prior experimental demonstrations of Shor's algorithm have used knowledge of the answer in order to optimize the circuit and thus lead to sizes that are experimentally feasible on non-error-corrected devices. Meaningful demonstration should avoid such shortcuts [25], which are not available in realistic cryptographic scenarios.

Comparable classical complexity and challenging instance sizes

The best known classical algorithm for factoring is the number field sieve, which has time complexity super-polynomial in number of bits \(n\): namely, it scales as \(\mathcal{O}\left( \exp(p\cdot n^{1/3}\log^{2/3}(n)) \right)\), where \(p>1.9\). With a hybrid quantum-classical algorithm applying amplitude amplification on the number field sieve, \(p= 1.387\) can be achieved using a number of qubits scaling only as \(\mathcal{O}\left( n^{2/3} \right)\) [26]. Classically, problems of size 795 bits have been factored, taking 76 computer core-years, which distributed in parallel over a cluster took 12 days; the same team then extended the record to 829 bits [17].

Several algorithms attacking elliptic curve cryptography have complexity \(\mathcal{O}\left( 2^{n/2} \right)\) [27], leading to the recommended doubling of key size compared to bits of security. In practice, a problem of size 117 bits was solved [28].

Speedup

The number of gates to implement Shor's algorithm is \(\widetilde{\mathcal{O}}\left( n^2 \right)\) asymptotically using fast multiplication on large numbers [29]. More practically, without incurring the time overhead and additional storage space of fast multiplication, the scaling is \(\mathcal{O}\left( n^3 \right)\). Assuming classical and quantum gates are polynomially related in time complexity, the speedup is super-polynomial. However, there are no tight lower bounds on the classical complexity of factoring or ECDLP; it remains possible that more efficient classical algorithms could be discovered.

NISQ implementations

The large circuit depth, complicated operations, and high number of qubits needed to implement Shor's algorithm make faithful NISQ implementation challenging. However, there have been several attempts to ease implementation at the expense of losing the guarantees of Shor's algorithm, in the hope that the output is still correct with some nonzero probability, which could be vanishing.

One approach [30] is to simplify several operations and make them approximate. The outcome is that the circuit depth is \(\mathcal{O}\left( n^2 \right)\), saving a factor of \(n\) [14]. The depth is then about \(10^8\) to factor a 1024-bit instance of RSA, so for relevant sizes, error correction is still required. Implementation of the approximate algorithm, including experimentally, allowed for the successful factorization of larger problem instances than had been possible before. This approximate version is not NISQ in the usual sense of involving noisy circuits, but rather introduces some uncontrolled approximation error in return for reducing the depth, for the possibility of a useful result. Another approach is to encode the factoring problem in a variational optimization circuit. Again, performance is not guaranteed; moreover, variational optimization applied to generic problems is expected to have, at best, a quadratic improvement compared to classical methods, leaving no hope for breaking cryptography. Classical simulation on small problem sizes shows that the algorithm can succeed [31], as does experimental implementation on a superconducting quantum processor [32]. We emphasize that, generally, these NISQ approaches have no evidence or arguments for scaling to cryptographically relevant system sizes.

Outlook

The existence of Shor's algorithm implies common RSA and elliptic curve schemes are theoretically not secure, and resource estimates have made clear what scale of quantum hardware would break them. While such hardware does not exist currently, progress towards such a device can be used to inform the speed of transitioning to quantum-resistant encryption [33]. Currently, from a hardware perspective, the field of quantum computing is far from implementing algorithms that would break encryption schemes used in practice. The estimates above suggest that the resources required would be millions of physical qubits performing billions of Toffoli gates running on the timescale of days. In contrast, current state-of-the-art is on the order of one hundred noisy physical qubits, with progress towards demonstration of a single logical qubit. Running fault-tolerant quantum computation requires extra overhead, such as magic state factories (see the sections on quantum error correction and lattice surgery). Thus, the gap between state-of-the-art hardware and the requirements for breaking cryptosystems is formidable. Moreover, a linear increase in key size will increase, e.g., the number of Toffoli gates by a power of three, which can be substantial. Therefore, considering the experimental challenges, likely only the most sensitive data will be at risk first, rather than common transactions. Consequently, these highly confidential communications will likely adopt post-quantum cryptography first to avoid being broken. However, insecure protocols often linger in practice, so quantum computers can exploit any vulnerabilities in deployed systems that have not been addressed. For example, RSA keys of size 768 bits have been found in commercial devices (note that such key sizes can already be broken classically [17]). In addition, intercepted messages, encrypted with RSA or elliptic curves, can be stored now and decrypted later, once large-scale quantum computers become available.

The resilience of candidates for post-quantum cryptography is under active investigation. In particular, specialized quantum attacks [34] can reduce the number of bits of security, weakening the cryptosystem. Classical attacks have even broken certain cryptosystems [35]. Note that these attacks affect the feasibility of particular proposals, but there exist other post-quantum candidates that have no known weaknesses.

A sensitive area that warrants additional discussion is cryptocurrency, since much of the encryption relies on the compromised, number-theoretic, public-key cryptography. Moreover, changing the cryptographic protocol of the currency requires that most of the users reach a consensus to do so, which can be challenging to coordinate, even if the technical hurdles of adopting post-quantum encryption are overcome. Cryptocurrency wallets that have revealed their public key (for example, via a transaction reusing a public key assigned to that wallet previously) can be broken using Shor's algorithm. An attack is also possible during the short time-window in which the key is revealed during a single transaction [36]. Different cryptocurrencies have different levels of susceptibility to these types of attacks [37, 38]. Nevertheless, the mining of cryptocurrency is not broken, but only weakened by quantum computers.

Bibliography

  1. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography: Third Edition. CRC Press, Boca Raton, FL, 2021.

  2. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. Earlier version in *FOCS'94*. arXiv: https://arxiv.org/abs/quant-ph/9508027. doi:10.1137/S0097539795293172.

  3. Daniel J. Bernstein and Tanja Lange. Post-quantum cryptography. Nature, 549(7671):188–194, 9 2017. ePrint: https://eprint.iacr.org/2017/314. URL: https://doi.org/10.1038/nature23461, doi:10.1038/nature23461.

  4. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 2 1978. URL: https://doi.org/10.1145/359340.359342, doi:10.1145/359340.359342.

  5. Neal Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203–209, 1 1987. doi:10.2307/2007884.

  6. Victor S. Miller. Use of elliptic curves in cryptography. In Hugh C. Williams, editor, Advances in Cryptology – CRYPTO 1985, 417–426. Berlin, Heidelberg, 1986. Springer Berlin Heidelberg. doi:10.1007/3-540-39799-X\_31.

  7. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. doi:10.1017/CBO9780511976667.

  8. David Harvey and Joris van der Hoeven. Integer multiplication in time \(o(n\mathrm log\, n)\). Annals of Mathematics, 193(2):563 – 617, 2021. URL: https://doi.org/10.4007/annals.2021.193.2.4, doi:10.4007/annals.2021.193.2.4.

  9. R. Cleve and J. Watrous. Fast parallel circuits for the quantum fourier transform. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), volume, 526–536. 2000. arXiv: https://arxiv.org/abs/quant-ph/0006004. doi:10.1109/SFCS.2000.892140.

  10. Oded Regev. An efficient quantum factoring algorithm. arXiv: https://arxiv.org/abs/2308.06572, 2023.

  11. Andrew M. Childs and Wim van Dam. Quantum algorithms for algebraic problems. Reviews of Modern Physics, 82:1–52, 1 2010. arXiv: https://arxiv.org/abs/0812.0380. URL: https://link.aps.org/doi/10.1103/RevModPhys.82.1, doi:10.1103/RevModPhys.82.1.

  12. Elaine Barker and Quynh Dang. Recommendation for key management, part 3: application-specific key management guidance. Technical Report SP 800-57 Part 3 Rev. 1, National Institute of Standards and Technology, Gaithersburg, MD, 2015. doi:10.6028/NIST.SP.800-57pt3r1.

  13. Stephane Beauregard. Circuit for shor's algorithm using 2n+3 qubits. Quantum Information and Computation, 3(2):175–185, 3 2003. arXiv: https://arxiv.org/abs/quant-ph/0205095. doi:10.26421/QIC3.2-8.

  14. Thomas Häner, Martin Roetteler, and Krysta M. Svore. Factoring using 2n + 2 qubits with toffoli based modular multiplication. Quantum Information and Computation, 17(7–8):673–684, 6 2017. arXiv: https://arxiv.org/abs/1611.07995. doi:10.26421/QIC17.7-8-7.

  15. Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: towards practical large-scale quantum computation. Physical Review A, 86:032324, 9 2012. arXiv: https://arxiv.org/abs/1208.0928. URL: https://link.aps.org/doi/10.1103/PhysRevA.86.032324, doi:10.1103/PhysRevA.86.032324.

  16. Craig Gidney and Martin Ekerå. How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum, 5:433, 4 2021. arXiv: https://arxiv.org/abs/1905.09749. URL: https://doi.org/10.22331/q-2021-04-15-433, doi:10.22331/q-2021-04-15-433.

  17. Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann. Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, 62–91. Cham, 2020. Springer International Publishing. arXiv: https://arxiv.org/abs/2006.06197. doi:10.1007/978-3-030-56880-1\_3.

  18. Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, 241–270. Cham, 2017. Springer International Publishing. arXiv: https://arxiv.org/abs/1706.06752. doi:10.1007/978-3-319-70697-9\_9.

  19. Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken. Improved quantum circuits for elliptic curve discrete logarithms. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography, 425–444. Cham, 2020. Springer International Publishing. arXiv: https://arxiv.org/abs/2001.09580. doi:10.1007/978-3-030-44223-1\_23.

  20. Mark Webber, Vincent Elfving, Sebastian Weidt, and Winfried K. Hensinger. The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime. AVS Quantum Science, 4(1):013801, 2022. arXiv: https://arxiv.org/abs/2108.12371. URL: https://doi.org/10.1116/5.0073075, arXiv:https://doi.org/10.1116/5.0073075, doi:10.1116/5.0073075.

  21. John Proos and Christof Zalka. Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Information and Computation, 3(4):317–344, 7 2003. arXiv: https://arxiv.org/abs/0301141.

  22. Jinyoung Ha, Jonghyun Lee, and Jun Heo. Resource analysis of quantum computing with noisy qubits for shor's factoring algorithms. Quantum Information Processing, 21(2):60, 1 2022. URL: https://doi.org/10.1007/s11128-021-03398-1, doi:10.1007/s11128-021-03398-1.

  23. Daniel Litinski. How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates. arXiv: https://arxiv.org/abs/2306.08585, 2023. arXiv:2306.08585.

  24. Gorjan Alagic, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, Daniel Smith-Tone, and Yi-Kai Liu. Status report on the third round of the nist post-quantum cryptography standardization process. Technical Report NISTIR 8413, National Institute of Standards and Technology, Gaithersburg, MD, 2022. doi:10.6028/NIST.IR.8413-upd1.

  25. John A. Smolin, Graeme Smith, and Alexander Vargo. Oversimplifying quantum factoring. Nature, 499(7457):163–165, 2013. URL: https://doi.org/10.1038/nature12290, doi:10.1038/nature12290.

  26. Daniel J. Bernstein, Jean-François Biasse, and Michele Mosca. A low-resource quantum factoring algorithm. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography, 330–346. Cham, 2017. Springer International Publishing. ePrint: https://eprint.iacr.org/2017/352. doi:10.1007/978-3-319-59879-6\_19.

  27. Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography, Second Edition. Chapman and Hall/CRC, 2008.

  28. Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann. Faster elliptic-curve discrete logarithms on fpgas. ePrint: https://eprint.iacr.org/2016/382, 2016.

  29. David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill. Efficient networks for quantum factoring. Physical Review A, 54:1034–1063, 8 1996. arXiv: https://arxiv.org/abs/quant-ph/9602016. URL: https://link.aps.org/doi/10.1103/PhysRevA.54.1034, doi:10.1103/PhysRevA.54.1034.

  30. Martina Rossi, Luca Asproni, Davide Caputo, Stefano Rossi, Alice Cusinato, Remo Marini, Andrea Agosti, and Marco Magagnini. Using shor's algorithm on near term quantum computers: a reduced version. Quantum Machine Intelligence, 4(2):18, 7 2022. arXiv: https://arxiv.org/abs/2112.12647. URL: https://doi.org/10.1007/s42484-022-00072-2, doi:10.1007/s42484-022-00072-2.

  31. Eric Anschuetz, Jonathan Olson, Alán Aspuru-Guzik, and Yudong Cao. Variational quantum factoring. In Quantum Technology and Optimization Problems, 74–85. Springer, 2019. arXiv: https://arxiv.org/abs/1808.08927. URL: https://link.springer.com/chapter/10.1007/978-3-030-14082-3\_7, doi:10.1007/978-3-030-14082-3\_7.

  32. Amir H. Karamlou, William A. Simon, Amara Katabarwa, Travis L. Scholten, Borja Peropadre, and Yudong Cao. Analyzing the performance of variational quantum factoring on a superconducting quantum processor. npj Quantum Information, 7(1):156, 10 2021. arXiv: https://arxiv.org/abs/2012.07825. URL: https://doi.org/10.1038/s41534-021-00478-z, doi:10.1038/s41534-021-00478-z.

  33. Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. Technical Report NISTIR 8105, National Institute of Standards and Technology, Gaithersburg, MD, 2016. doi:10.6028/NIST.IR.8105.

  34. Chris Peikert. He gives c-sieves on the csidh. In Advances in Cryptology – EUROCRYPT 2020, 463–492. Berlin, Heidelberg, 2020. Springer-Verlag. ePrint: https://eprint.iacr.org/2019/725. URL: https://doi.org/10.1007/978-3-030-45724-2\_16, doi:10.1007/978-3-030-45724-2\_16.

  35. Wouter Castryck and Thomas Decru. An efficient key recovery attack on sidh. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, 423–447. Cham, 2023. Springer Nature Switzerland. ePrint: https://eprint.iacr.org/2022/975. doi:10.1007/978-3-031-30589-4\_15.

  36. Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. Quantum attacks on bitcoin, and how to protect against them. Ledger, 8 2018. arXiv: https://arxiv.org/abs/1710.10377. URL: https://ledger.pitt.edu/ojs/ledger/article/view/127, doi:10.5195/ledger.2018.127.

  37. Itan Barmes and Bram Bosch. Quantum computers and the bitcoin blockchain. 2019. https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html, accessed: 2023-09-30. URL: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html.

  38. Itan Barmes, Bram Bosch, and Marc Verdonk. Quantum risk to the ethereum blockchain - a bump in the road or a brick wall? 2022. https://www2.deloitte.com/nl/nl/pages/risk/articles/quantum-risk-to-the-ethereum-blockchain.html, accessed: 2023-09-30.

  1. An example of a cryptosystem not requiring computational assumptions is the one-time pad. ↩

  2. If \(r\lfloor L/r \rfloor+y \geq L\), then the \(j = \lfloor L/r \rfloor\) term does not appear in the expression. ↩