Paper 2023/250
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies
, Princeton University, NTT Research, Inc., Princeton UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in EUROCRYPT 2023
- Keywords
- SignaturesIdealized ModelsIsogeniesLower BoundsPost-Quantum Cryptography
- Contact author(s)
-
dabo @ cs stanford edu
jiaxin @ guan io
mzhandry @ gmail com - History
- 2023-02-22: approved
- 2023-02-21: received
- See all versions
- Short URL
- https://ia.cr/2023/250
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/250,
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{https://eprint.iacr.org/2023/250}},
url = {https://eprint.iacr.org/2023/250}
}
