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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
semidirect productdiscrete logarithmquantum algorithmdigital signatures
Contact author(s)
am3518 @ ic ac uk
edable-heath @ turing ac uk
cling @ ieee org
History
2023-12-31: approved
2023-12-27: received
See all versions
Short URL
https://ia.cr/2023/1963
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2023/1963}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.