[Resource Topic] 2023/250: A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies

Welcome to the resource topic for 2023/250

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

Authors: Dan Boneh, Jiaxin Guan, Mark Zhandry

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.

ePrint: https://eprint.iacr.org/2023/250

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .