Paper 2023/250

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

Dan Boneh, Stanford University
Jiaxin Guan, Princeton University
Mark Zhandry, NTT Research, Inc., Princeton University

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.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2023
SignaturesIdealized ModelsIsogeniesLower BoundsPost-Quantum Cryptography
Contact author(s)
dabo @ cs stanford edu
jiaxin @ guan io
mzhandry @ gmail com
2023-02-22: approved
2023-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Jiaxin Guan and Mark Zhandry},
      title = {A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2023/250},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.