A Small Serving of Mash: (Quantum) Algorithms for SPDH-Sign with Small Parameters

Andrew Mendelsohn; Edmund Dable-Heath; Cong Ling

Paper 2023/1963

A Small Serving of Mash: (Quantum) Algorithms for SPDH-Sign with Small Parameters

Andrew Mendelsohn, Imperial College London

Edmund Dable-Heath, The Alan Turing Institute

Cong Ling, Imperial College London

Abstract

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order $p^3$ and exponent $p^2$ for certain exponentially large parameters. This implies an attack on SPDH-Sign, a signature scheme based on the SDLP, for such parameters. We also take a step toward proving the quantum polynomial time equivalence of SDLP and SCDH.

Note: Added DOI of published version.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. Journal of Mathematical Cryptology
DOI: 10.1515/jmc-2024-0025
Keywords: semidirect product discrete logarithm quantum algorithm digital signatures
Contact author(s): am3518 @ ic ac uk
edable-heath @ turing ac uk
cling @ ieee org
History: 2025-03-05: revised; 2023-12-27: received; See all versions
Short URL: https://ia.cr/2023/1963
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1963,
      author = {Andrew Mendelsohn and Edmund Dable-Heath and Cong Ling},
      title = {A Small Serving of Mash: (Quantum) Algorithms for {SPDH}-Sign with Small Parameters},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1963},
      year = {2023},
      doi = {10.1515/jmc-2024-0025},
      url = {https://eprint.iacr.org/2023/1963}
}