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

Andrew Mendelsohn; Edmund Dable-Heath; Cong Ling

Paper 2023/1963 Original: eprint.iacr.org/2023/1963 ↗

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

Andrew Mendelsohn

Edmund Dable-Heath

Cong Ling

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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
History: 2025-03-05: last updated; 2023-12-27: published
Short URL: https://ia.cr/2023/1963
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2023/1963}
}