Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem

• URL: http://arxiv.org/abs/2312.14028v1
• Date: Thu, 21 Dec 2023 16:58:59 GMT
• Title: Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
• Authors: Muhammad Imran and G\'abor Ivanyos
• Abstract summary: 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.
• Score: 2.90985742774369
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in \mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. Previously, the best known algorithm for the SDLP was 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 of \textit{semidirect 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 group $G$, we describe quantum algorithms for the SDLP in $G\rtimes \mathrm{Aut}(G)$ for the following two classes of instances: the first one is when $G$ is solvable and the second is when $G$ is a matrix group and a power of $\sigma$ with a polynomially small exponent is an inner automorphism of $G$. 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.

Related papers

• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• Weak Schur sampling with logarithmic quantum memory [0.0]
  We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group.
  arXiv  Detail & Related papers  (2023-09-21T10:02:46Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  We present a differentially private streaming clustering framework which only requires an offline DP coreset or clustering algorithm as a blackbox. Our framework is also differentially private under the continual release setting, i.e., the union of outputs of our algorithms at every timestamp is always differentially private.
  arXiv  Detail & Related papers  (2023-07-14T16:11:22Z)
• Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
  We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model. We show the quantum complexity lower bounds and almost matching algorithms of the DL and related problems in this model. variations of Shor's algorithm can take advantage of classical computations to reduce the number of quantum group operations.
  arXiv  Detail & Related papers  (2023-07-06T15:32:50Z)
• Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH [5.398058794903461]
  The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves. We introduce a new quantum-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(loglog p)$ many prime factors.
  arXiv  Detail & Related papers  (2023-05-31T14:30:32Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)

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.