arXiv:2209.02814 · Lecture notes in computer science

A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak Fayyaz Shahandashti

Published Jan 1, 2024• 4 citations

arXiv HTML PDF

DOI: 10.1007/978-3-031-62743-9_7

Related papers

On the Semidirect Discrete Logarithm Problem in Finite Groups

Christopher Battarbee, Giacomo Borin, Julian Brough +10 more

Lecture notes in computer scienceDec 11, 20242 citations

Quantum algorithm for solving hyperelliptic curve discrete logarithm problem

Yan Tang Huang, Zhaofeng Su, Fangguo Zhang +2 more

Quantum Information ProcessingJan 2, 202031 citations

New Quantum Algorithms for Modular Inverse and Their Application on the Elliptic Curve Discrete Logarithm Problem

Kurama Ryo, Noboru Kunihiro

IEICE Technical Report; IEICE Tech. Rep.Jul 16, 20191 citation

Quantum Algorithm for Solving the Discrete Logarithm Problem in the Class Group of an Imaginary Quadratic Field and Security Comparison of Current Cryptosystems at the Beginning of Quantum Computer Age

Arthur Schmidt

Lecture notes in computer scienceJan 1, 20066 citations

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

Muhammad Imran, Gábor Ivanyos

Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $$G\rtimes {{\,\textrm{End}\,}}(G)$$ G⋊End(G) for a finite semigroupG. Given $$g\in G, \sigma \in {{\,\textrm{End}\,}}(G)$$ g∈G,σ∈End(G) , and $$h=\prod _{i=0}^{t-1}\sigma ^i(g)$$ h=∏i=0t-1σi(g) for some integert, the SDLP $$(G,\sigma )$$ (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\rtimes {\textrm{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 $$\sigma $$ σ 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.

arXiv:2312.14028Designs Codes and CryptographyMay 21, 20247 citations

Quantum Computing for Discrete Logarithms

Song Yuan Yan

Springer eBooksJan 1, 20153 citations

arXiv:2209.02814 · Lecture notes in computer science

A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak Fayyaz Shahandashti

Published Jan 1, 2024• 4 citations

arXiv HTML PDF

DOI: 10.1007/978-3-031-62743-9_7

Related papers

On the Semidirect Discrete Logarithm Problem in Finite Groups

Christopher Battarbee, Giacomo Borin, Julian Brough +10 more

Lecture notes in computer scienceDec 11, 20242 citations

Quantum algorithm for solving hyperelliptic curve discrete logarithm problem

Yan Tang Huang, Zhaofeng Su, Fangguo Zhang +2 more

Quantum Information ProcessingJan 2, 202031 citations

New Quantum Algorithms for Modular Inverse and Their Application on the Elliptic Curve Discrete Logarithm Problem

Kurama Ryo, Noboru Kunihiro

IEICE Technical Report; IEICE Tech. Rep.Jul 16, 20191 citation

Arthur Schmidt

Lecture notes in computer scienceJan 1, 20066 citations

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

Muhammad Imran, Gábor Ivanyos

Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes {{\,\textrm{End}\,}}(G)$ G⋊End(G) for a finite semigroupG. Given $g\in G, \sigma \in {{\,\textrm{End}\,}}(G)$ g∈G,σ∈End(G) , and $h=\prod _{i=0}^{t-1}\sigma ^i(g)$ h=∏i=0t-1σi(g) for some integert, the SDLP $(G,\sigma )$ (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\rtimes {\textrm{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 $\sigma$ σ 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.Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $$G\rtimes {{\,\textrm{End}\,}}(G)$$ G⋊End(G) for a finite semigroupG. Given $$g\in G, \sigma \in {{\,\textrm{End}\,}}(G)$$ g∈G,σ∈End(G) , and $$h=\prod _{i=0}^{t-1}\sigma ^i(g)$$ h=∏i=0t-1σi(g) for some integert, the SDLP $$(G,\sigma )$$ (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\rtimes {\textrm{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 $$\sigma $$ σ 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.

arXiv:2312.14028Designs Codes and CryptographyMay 21, 20247 citations

Quantum Computing for Discrete Logarithms

Song Yuan Yan

Springer eBooksJan 1, 20153 citations

Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup

G\rtimes {{\,\textrm{End}\,}}(G)

G⋊End(G) for a finite semigroupG. Given

g\in G, \sigma \in {{\,\textrm{End}\,}}(G)

g∈G,σ∈End(G) , and

h=\prod _{i=0}^{t-1}\sigma ^i(g)

h=∏i=0t-1σi(g) for some integert, the SDLP

(G,\sigma )

(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\rtimes {\textrm{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

\sigma

σ 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.