This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models. - In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring. - In the quantum generic group model (QGGM), we study the complexity of variants of the discrete logarithm. We prove the logarithm DL lower bound in the QGGM even for the composite order setting. We also prove an asymptotically tight lower bound for the multiple-instance DL problem. Both results resolve the open problems suggested in a recent work by Hhan, Yamakawa, and Yun. - In the quantum generic ring model we newly suggested, we give the logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also give a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm. - Finally, we prove a lower bound for the basic index calculus method for solving the DL problem in a new idealized group model regarding smooth numbers. The quantum lower bounds in both models allow certain (different) types of classical preprocessing. All of the proofs are significantly simpler than the previous proofs and are through a single tool, the so-called compression lemma, along with linear algebra tools. Our use of this lemma may be of independent interest.
This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models. - In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring. - In the quantum generic group model (QGGM), we study the complexity of variants of the discrete logarithm. We prove the logarithm DL lower bound in the QGGM even for the composite order setting. We also prove an asymptotically tight lower bound for the multiple-instance DL problem. Both results resolve the open problems suggested in a recent work by Hhan, Yamakawa, and Yun. - In the quantum generic ring model we newly suggested, we give the logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also give a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm. - Finally, we prove a lower bound for the basic index calculus method for solving the DL problem in a new idealized group model regarding smooth numbers. The quantum lower bounds in both models allow certain (different) types of classical preprocessing. All of the proofs are significantly simpler than the previous proofs and are through a single tool, the so-called compression lemma, along with linear algebra tools. Our use of this lemma may be of independent interest.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup G⋊End(G) G⋊End(G) for a finite semigroupG. Given g∈G,σ∈End(G) g∈G,σ∈End(G) , and h=∏i=0t−1σi(g) h=∏i=0t-1σi(g) for some integert, the SDLP (G,σ) (G,σ) , forgandh, asks to determinet. As Shor’s algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. For generic semigroups, the best known algorithm for the SDLP is based on Kuperberg’s subexponential time quantum algorithm. Still, the problem plays a central role in the security of certain proposed cryptosystems in the family ofsemidirect product key exchange. This includes a recently proposed signature protocol called SPDH-Sign. In this paper, we show that the SDLP is even easier in some important special cases. Specifically, for a finite groupG, we describe quantum algorithms for the SDLP in G⋊Aut(G) G⋊Aut(G) for the following two classes of instances: the first one is whenGis solvable and the second is whenGis a matrix group and a power of σ σ with a polynomially small exponent is an inner automorphism ofG. We further extend the results to groups composed of factors from these classes. A consequence is that SPDH-Sign and similar cryptosystems whose security assumption is based on the presumed hardness of the SDLP in the cases described above are insecure against quantum attacks. The quantum ingredients we rely on are not new: these are Shor’s factoring and discrete logarithm algorithms and well-known generalizations.
In this article, we investigate whether combining Regev's reduction with the Cheng-Wan reduction can yield an alternative quantum algorithm for the discrete logarithm problem (DLOG) in finite abelian groups. Cheng and Wan reduce DLOG over finite fields to bounded-distance decoding of low-rate Reed-Solomon codes at a large decoding radius. Regev's reduction, in turn, exploits a decoder for the high-rate dual code with a lower noise level to obtain a quantum algorithm for decoding the original low-rate code at a larger radius. The Cheng-Wan instances therefore provide a natural setting in which to explore the power of Regev's framework.
We first extend the Cheng-Wan reduction to the discrete logarithm problem in finite abelian groups, assuming access to embeddings of their cyclic factors. We also establish NP-hardness of Reed-Solomon bounded-distance decoding at asymptotically vanishing rate, reaching the rate regime relevant to Cheng-Wan, while the radius at which we establish hardness remains beyond the Cheng-Wan radius. We then instantiate Regev's reduction at the Cheng-Wan parameters and, under a conjecture on the performance of the induced BDD algorithm on the structured Cheng-Wan instances, characterize the noise threshold for the quantum decoding problem(QDP) sufficient to solve DLOG.
We evaluate known decoders in this regime and show that a quantum decoder based on unambiguous state discrimination(USD) enables Regev's reduction to reach a strictly stronger decoding regime than the standard classical Reed-Solomon decoders we consider. Nevertheless, the QDP noise threshold required by the Cheng-Wan reduction is asymptotically 4/3 times that achieved by USD. Going beyond the USD framework, we show that every Cheng-Wan instance can be solved through Regev's reduction using a suitable Pretty Good Measurement and its inverse, although no efficient implementation of it is known.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.
Abstract In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in (Z/NZ)× that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
We present our perspectives on the current status of, integer factoring and discrete logarithm, algorithms underlying the strength of classical public-key cryptography protocols used in key-exchange, encryption and digital signatures. We present an expository overview of the algebraic, number-theoretic and algorithmic principles behind the canonical, powerful algorithms used in the factoring of large, composite RSA modulii. These cover the two main ideas of group order based methods, and quadratic congruence based methods. We provide the resource estimates for the record breaking factoring based on the general number field sieve. Next we present an overview of the algorithmic theory of quantum computation behind, the polynomial time Shor's quantum algorithm for, period finding in hidden subgroup structure problems. This algorithm has played a key role in advancing post-quantum cryptography, and also in the exciting, contemporary developments in quantum computing, networking, sensing, and materials science as a whole. Latest advances in quantum computing rest on a variety of physics, engineering, algorithms, compilation, hardware, software techniques. There are several tradeoffs based on number of qubits, coherence times, control issues, errors and fault tolerance. In this environment, nuances of mathematical ideas, behind every step of the intricate arithmetical and algebraic computations under quantum models plays a significant role. We provide an overview of some of the recent ideas behind such algorithms. We conclude with a recent deep question on the ultimate feasibility of ultra large-scale, error-free, discrete, quantum computations required typically in cryptanalysis.