Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys

• URL: http://arxiv.org/abs/2509.06549v1
• Date: Mon, 08 Sep 2025 11:03:49 GMT
• Title: Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys
• Authors: Timo Glaser, Alexander May, Julian Nowakowski,
• Abstract summary: We study the fundamental problem of guessing cryptographic keys.<n>We find that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting.
• Score: 43.5605535402594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution $D$, as e.g. in LPN, LWE or for passwords. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search. We give the first tight analysis for Montanaro's algorithm, showing that its runtime is $2^{H_{2/3}(D)/2}$, where $H_{\alpha}(\cdot)$ denotes Renyi entropy with parameter $\alpha$. Interestingly, this is a direct consequence of an information theoretic result called Arikan's Inequality (1996) -- which has so far been missed in the cryptographic community -- that tightly bounds the runtime of classical key guessing by $2^{H_{1/2}(D)}$. Since $H_{2/3}(D) < H_{1/2}(D)$ for every non-uniform distribution $D$, we thus obtain a super-quadratic quantum speed-up $s>2$ over classical key guessing. As another main result, we provide the first thorough analysis of guessing in a multi-key setting. Specifically, we consider the task of attacking many keys sampled independently from some distribution $D$, and aim to guess a fraction of them. For product distributions $D = \chi^n$, we show that any constant fraction of keys can be guessed within $2^{H(D)}$ classically and $2 ^{H(D)/2}$ quantumly per key, where $H(\chi)$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $2^{H_{1/2}(D)}$ classically and $2^{H_{2/3}(D)/2}$ quantumly. Since $H(D) < H_{2/3}(D) < H_{1/2}(D)$, this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting, both classically and quantumly.

Related papers

• Geometric Discord of any arbitrary dimensional bipartite system and its application in quantum key distribution [0.0]
  Entangled quantum states are regarded as a key resource in quantum key distribution protocols.<n>We will focus on one such measure of quantum correlation, known as geometric quantum discord (GQD)<n>We find that for a certain range of GQD, the successful generation of the secret key is not guaranteed.
  arXiv  Detail & Related papers  (2025-09-05T08:46:24Z)
• Quantum Security Analysis of the Key-Alternating Ciphers [2.5383384004287937]
  We study the quantum security of key-alternating ciphers (KAC)<n>We give the first nontrivial quantum key-recovery attack on multi-round KAC in the $Q1$ model.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space.<n>Despite its significant benefits, incorporating the non-linear function raises substantial challenges in both statistical and computational efficiency.<n>We propose an algorithm that achieves a regret of $widetildemathcalO(dH2sqrtK + kappa-1d2H2)$, eliminating the dependence on $kappa-1$ in the dominant term for the first time
  arXiv  Detail & Related papers  (2024-05-27T11:31:54Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Post-Quantum Security of the Even-Mansour Cipher [14.141778162933013]
  Even-Mansour cipher is secure against classical attacks. Even-Mansour can still be proven secure in natural, "post-quantum" setting.
  arXiv  Detail & Related papers  (2021-12-14T16:43:34Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  We show that $1D$ random quantum circuits have a spectral gap scaling as $Omega(n-1)$, provided that $t$ is small compared to the local dimension: $t2leq O(q)$. Our second result is an unconditional spectral gap bounded below by $Omega(n-1log-1(n) t-alpha(q))$ for random quantum circuits with all-to-all interactions.
  arXiv  Detail & Related papers  (2020-12-09T19:00:50Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.