Paper 2023/250 Original: eprint.iacr.org/2023/250 ↗
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2023-02-21: last updated
- 2023-02-21: published
- Short URL
- https://ia.cr/2023/250
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2023/250}
}