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

Abstract

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order p3{p}^{3} and exponent p2{p}^{2} 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 n<(p−1)p6n\lt \left(p-1){p}^{6}: we develop a method to solve instances when n≤poly(logp)⋅pn\le {\rm{poly}}\left(\log p)\hspace{0.25em}\cdot p. Letting λ\lambda be the security parameter of SPDH-Sign, which is taken p=expλp=\exp \lambda , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large pp. However, for n≈p2n\approx {p}^{2} 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.

Keywords

• semidirect product
• discrete logarithm
• signatures
• group actions
• cryptanalysis
• 11t71
• 94a60
• 68q12