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.
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.
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo p and Order q
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulopand orderq. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs ofpandqup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of orderq, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs ofpandq, extrapolated the circuit sizes obtained, and compared them forp=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same ifpis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length ofpin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group withp=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group withp=1024bits.
Solving the discrete logarithm problem (DLP) with quantum computers is a fundamental task with important implications. Beyond Shor's algorithm, many researchers have proposed alternative solutions in recent years. However, due to current hardware limitations, the scale of DLP instances that can be addressed by quantum computers remains insufficient. To overcome this limitation, we propose a distributed quantum discrete logarithm algorithm that reduces the required quantum register size for solving DLPs. Specifically, we design a distributed quantum algorithm to determine whether the solution is contained in a given set. Based on this procedure, our method solves DLPs by identifying the intersection of sets containing the solution. Compared with Shor's original algorithm, our approach reduces the register size and can improve the success probability, while requiring no quantum communication.
The quantum algorithm with polynomial time for discrete logarithm problem proposed by Shor is one of the most significant quantum algorithms, but a large number of qubits may be required in the Noisy Intermediate-scale Quantum (NISQ) era. The main contributions of this paper are as follows: (1) A distributed quantum algorithm for discrete logarithm problem is designed, and its space complexity and success probability exhibit certain advantages to some extent; (2) The classical error correction technique proposed by Xiao and Qiu et al. is generalized by extending three bits to more than three bits.
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.
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.
We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order r, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as r→∞, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm d and r are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if r is known when computing d. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.