Abstract The discrete logarithm problem over a multiplicative group of integer modulo n is the key ingredient in the ElGamal encryption system. This problem has been proven to be tractable in polynomial time on a quantum computer by Shor's algorithm. This algorithm makes use of basic quantum gates, circuits, measurements and it has been experimented in the circuit‐gate framework of quantum computing. On the other hand, the adiabatic framework of quantum computing with the quantum annealers such as the D‐Wave machine that simulates the adiabatic process has become very popular, showing its potential for making a practical pathway to achieve quantum speedup. Furthermore, much progress has been reported recently on the tractability of the integer factoring problem, which is the other widely‐used encryption method, on quantum annealers. In this context, it is important to explore the tractability of the discrete logarithm problem too using quantum annealers. In this work we present a first step made in this direction, by converting the discrete logarithm problem over a multiplicative group into the problem of minimizing a binary quadratic form, a standard problem format acceptable to a quantum annealer. Our formulation was tested for small‐scale problem instances using the quantum‐classical hybrid platform PyQUBO and we discuss the computational challenges and propose several potential improvements to the formulation.
Abstract The discrete logarithm problem over a multiplicative group of integer modulo n is the key ingredient in the ElGamal encryption system. This problem has been proven to be tractable in polynomial time on a quantum computer by Shor's algorithm. This algorithm makes use of basic quantum gates, circuits, measurements and it has been experimented in the circuit‐gate framework of quantum computing. On the other hand, the adiabatic framework of quantum computing with the quantum annealers such as the D‐Wave machine that simulates the adiabatic process has become very popular, showing its potential for making a practical pathway to achieve quantum speedup. Furthermore, much progress has been reported recently on the tractability of the integer factoring problem, which is the other widely‐used encryption method, on quantum annealers. In this context, it is important to explore the tractability of the discrete logarithm problem too using quantum annealers. In this work we present a first step made in this direction, by converting the discrete logarithm problem over a multiplicative group into the problem of minimizing a binary quadratic form, a standard problem format acceptable to a quantum annealer. Our formulation was tested for small‐scale problem instances using the quantum‐classical hybrid platform PyQUBO and we discuss the computational challenges and propose several potential improvements to the formulation.
This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations, assuming the use of the best publicly available special-class quantum computer: the quantum annealer. We achieve new computational experiment results by solving the largest instance of the factorization problem ever announced as solved using quantum annealing, with a size of 29 bits. The core idea of the improved approach is to leverage known subexponential classical method to break the problem down into many smaller computations and perform the most critical ones on a quantum computer. This approach does not reduce the complexity class, but it assesses the pragmatic capabilities of an attacker. It also marks a step forward in the development of hybrid methods, which in practice may surpass classical methods in terms of efficiency sooner than purely quantum computations will.
The discrete logarithm problem is a significant challenge in number theory,and due to the difficulty of solving it,classical computers lack efficient algorithms for this task.As a result,the discrete logarithm problem is widely used in public key cryptosystems,and if it were cracked,it would pose a direct threat to the security of these systems.However,with the advent of quantum computing,researchers have begun exploring quantum computers as a potential solution for the discrete logarithm problem.Currently,most quantum algorithms for solving the discrete logarithm problem are based on Shor’s algorithm.However,due to Shor’s inherent limitations,these algorithms often face issues such as large quantum circuit depth,high qubit usage and complex post-processing steps.This makes it difficult for Shor’s algorithm to be implemented on NISQ computers.To address these issues,this paper proposes a novel approach by introducing a variational quantum algorithm for solving the discrete logarithm pro-blem.This algorithm leverages the parallelism of quantum computing to compute the modular exponentiation of parameterized quantum states.It also designs a marked solution circuit that maps valid solutions of the discrete logarithm problem onto auxiliary qubits.Then,a classical optimizer is used to iteratively adjust the parameters within the parameterized quantum circuit,continuously reducing the value of a designed loss function.Finally,the optimized parameters from the classical optimizer are fed into the measurement circuit,where the solution to the discrete logarithm problem can be obtained with high probability.Compared to Shor’s algorithm,the proposed method significantly reduces the required number of qubits and nearly halves the quantum circuit depth.Furthermore,this paper provides a detailed design of the quantum circuit and verifies the correctness of the proposed algorithm using the Qiskit package in Python.
The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.
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.
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.
In quantum cryptanalysis, Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problem, and elliptic curve discrete logarithm problems, widely used in cryptographic applications in cyberspace. Shor's quantum algorithm can potentially crack most protocols and schemes of asymmetric encryption (public key cryptography). In general, all known quantum algorithms can be divided into two groups: providing exponential gain (for example, Shor's algorithm) and providing quadratic gain (for example, Grover's algorithm). Particular attention is paid to the Shor quantum algorithm and other polynomial algorithms capable of solving cryptanalysis problems with the required reliability and complexity in polynomial time. For quantum computing, all cryptographies are divided into quantum-secure and quantum-insecure. Algorithms and cryptosystems of symmetric encryption are attributed to quantum-secure but with at least twice the key length increased. This chapter presents an overview of the concepts discussed in the subsequent chapters of this book.