English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The semidirect discrete logarithm problem (SDLP) is the following analogue ofthe 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'salgorithm crucially depends on commutativity, it is believed not to beapplicable to the SDLP. Previously, the best known algorithm for the SDLP wasbased on Kuperberg's subexponential time quantum algorithm. Still, the problemplays a central role in the security of certain proposed cryptosystems in thefamily of \textit{semidirect product key exchange}. This includes a recentlyproposed signature protocol called SPDH-Sign. In this paper, we show that theSDLP is even easier in some important special cases. Specifically, for a finitegroup $G$, we describe quantum algorithms for the SDLP in $G\rtimes\mathrm{Aut}(G)$ for the following two classes of instances: the first one iswhen $G$ is solvable and the second is when $G$ is a matrix group and a powerof $\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 securityassumption is based on the presumed hardness of the SDLP in the cases describedabove are insecure against quantum attacks. The quantum ingredients we rely onare not new: these are Shor's factoring and discrete logarithm algorithms andwell-known generalizations.

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