A small serving of mash: (Quantum) algorithms for SPDH-Sign with small parameters
File(s)
Published version
Author(s)
Mendelsohn, Andrew
Dable-Heath, Edmund
Ling, Cong
Type
Journal Article
Abstract
We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order p3 and exponent p2 for certain exponentially large parameters. This implies an attack on SPDH-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)p6: we develop a method to solve instances when n ≤ poly(log p) · p. Letting λ be the security parameter of SPDH-Sign, which is taken p = exp λ, we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large p. However, for n ≈ p2 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.
Date Issued
2025-03-04
Date Acceptance
2025-01-13
Citation
Journal of Mathematical Cryptology, 2025, 19
ISSN
1862-2976
Publisher
De Gruyter
Journal / Book Title
Journal of Mathematical Cryptology
Volume
19
Copyright Statement
© 2025 the author(s), published by De Gruyter. This work is licensed under the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/)
License URL
Identifier
10.1515/jmc-2024-0025
Subjects
semidirect product
discrete logarithm
signatures
group actions
cryptanalysis MSC 2020: 11T71
94A60
68Q12
Publication Status
Published
Article Number
ARTN 20240025