A small serving of mash: (Quantum) algorithms for SPDH-Sign with small parameters

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>p</m:mi> </m:mrow> <m:mrow> <m:mn>3</m:mn> </m:mrow> </m:msup> </m:math> {p}³ and exponent <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>p</m:mi> </m:mrow> <m:mrow> <m:mn>2</m:mn> </m:mrow> </m:msup> </m:math> {p}² for certain exponentially large parameters. This implies an attack on SPDH-Sign, Pronounced “SPUD-Sign”. a signature scheme based on the SDLP, for such parameters. In particular, SDLP instances over such groups are parameterised by an <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>n</m:mi> <m:mo><</m:mo> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>p</m:mi> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> <m:msup> <m:mrow> <m:mi>p</m:mi> </m:mrow> <m:mrow> <m:mn>6</m:mn> </m:mrow> </m:msup> </m:math> n< (p-1){p}⁶ : we develop a method to solve instances when <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>n</m:mi> <m:mo>≤</m:mo> <m:mi mathvariant="normal">poly</m:mi> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>log</m:mi> <m:mi>p</m:mi> </m:mrow> <m:mo>)</m:mo> </m:mrow> <m:mspace width="0.25em"/> <m:mo>⋅</m:mo> <m:mi>p</m:mi> </m:math> n≤ {poly}(log p){0.25em}· p . Letting <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>λ</m:mi> </m:math> λ be the security parameter of SPDH-Sign, which is taken <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>p</m:mi> <m:mo>=</m:mo> <m:mi>exp</m:mi> <m:mi>λ</m:mi> </m:math> p=exp λ , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>p</m:mi> </m:math> p . However, for <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>n</m:mi> <m:mo>≈</m:mo> <m:msup> <m:mrow> <m:mi>p</m:mi> </m:mrow> <m:mrow> <m:mn>2</m:mn> </m:mrow> </m:msup> </m:math> n≈ {p}² and larger, our method no longer completely solves the SDLP instances. We also study the linear hidden shift problem for a group action corresponding to SDLP and take a step towards proving the quantum polynomial time equivalence of SDLP and the semidirect computational Diffie–Hellman problem.