A small serving of mash: (Quantum) algorithms for SPDH-Sign with small parameters
Andrew R. Mendelsohn, Edmund Dable-Heath, Cong Ling · Journal of Mathematical Cryptology · 2025
Abstract We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order p 3 {p}^{3} and exponent p 2 {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 ) p 6 n\lt \left(p-1){p}^{6} : we develop a method to solve instances when n ≤ poly ( log p ) ⋅ p n\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 p p . However, for n ≈ p 2 n\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.