A small serving of mash: (Quantum) algorithms for SPDH-Sign with small parameters - Mendelsohn Andrew; Dable-Heath Edmund; Ling Cong (Journal of Mathematical Cryptology)
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}· p. Letting λλ be the security parameter of SPDH-Sign, which is taken p=expλp=\exp λ , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large pp. However, for n≈p2n≈ {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.