On the success probability of the quantum algorithm for the short DLP

• URL: http://arxiv.org/abs/2309.01754v1
• Date: Mon, 4 Sep 2023 18:26:45 GMT
• Title: On the success probability of the quantum algorithm for the short DLP
• Authors: Martin Eker{\aa}
• Abstract summary: We prove a lower bound on the probability of Ekeraa-Haastad's algorithm recovering the short $d$ in a single run. By our bound, the success probability can easily be pushed as high as $1 - 10-10$ for any short $d$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Eker{\aa} and H{\aa}stad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Eker{\aa}-H{\aa}stad's algorithm solves the short DLP in groups of unknown order. In this work, we prove a lower bound on the probability of Eker{\aa}-H{\aa}stad's algorithm recovering the short logarithm $d$ in a single run. By our bound, the success probability can easily be pushed as high as $1 - 10^{-10}$ for any short $d$. A key to achieving such a high success probability is to efficiently perform a limited search in the classical post-processing by leveraging meet-in-the-middle techniques. Asymptotically, in the limit as the bit length $m$ of $d$ tends to infinity, the success probability tends to one if the limits on the search space are parameterized in $m$. Our results are directly applicable to Diffie-Hellman in safe-prime groups with short exponents, and to RSA via a reduction from the RSA integer factoring problem (IFP) to the short DLP.

Related papers

• Tight Success Probabilities for Quantum Period Finding and Phase Estimation [2.2329417756084093]
  We consider a general post-processing algorithm which succeeds whenever the measured $hatell$ is within some tolerance $M$ of a positive integer multiple of $2n / r$.<n>We give new (tight) lower and upper bounds on the success probability that converge to 1.<n>Our analysis allows for the careful exploitation of the tradeoffs between the complexity of the quantum circuit and the effort spent in classical processing when optimizing the probability of success.
  arXiv  Detail & Related papers  (2025-06-25T15:14:59Z)
• Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q [0.0]
  We simulate quantum circuits that operate on general pairs of modulo $p and order $q. We show how much the strength of safe-prime groups and Schnorr groups is the same if $p$ is equal. In particular, it was experimentally and theoretically shown that when a carryer is used in the addition circuit, the cryptographic strength of a Schnorr group with $p=$48$ bits under Shor's algorithm is almost equivalent to that of a safe-prime group with $p=$48$ bits.
  arXiv  Detail & Related papers  (2025-03-31T10:39:10Z)
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem [2.90985742774369]
  We show that the SDLP is even easier in some important special cases. We show that SPDH-Sign and similar cryptosystems whose security assumption is based on the presumed hardness of the SDLP are insecure against quantum attacks.
  arXiv  Detail & Related papers  (2023-12-21T16:58:59Z)
• Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
  We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
  arXiv  Detail & Related papers  (2023-11-05T03:33:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• On the success probability of quantum order finding [0.0]
  We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order $r$ in a single run. Asymptotically, in the limit as $r$ tends to infinity, the probability of successfully recovering $r$ in a single run tends to one.
  arXiv  Detail & Related papers  (2022-01-19T18:58:18Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism [16.996435043565594]
  We give the first-time algorithm to estimate the mean of a $d$-positive probability distribution with covariance from $tildeO(d)$ independent samples subject to pure differential privacy. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms.
  arXiv  Detail & Related papers  (2021-11-25T09:31:15Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
  We show that any of the algorithms randomized local search, algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function. We also prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark.
  arXiv  Detail & Related papers  (2020-04-13T00:24:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.