International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies

Authors:
Dan Boneh , Stanford University
Jiaxin Guan , Princeton University
Mark Zhandry , NTT Research & Princeton University
Download:
DOI: 10.1007/978-3-031-30589-4_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.
BibTeX
@inproceedings{eurocrypt-2023-32880,
  title={A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30589-4_18},
  author={Dan Boneh and Jiaxin Guan and Mark Zhandry},
  year=2023
}