Paper 2024/1510

Group Factorisation for Smaller Signatures from Cryptographic Group Actions

Giuseppe D'Alconzo, Polytechnic University of Turin
Alessio Meneghetti, University of Trento
Edoardo Signorini, Telsy, Polytechnic University of Turin
Abstract

Cryptographic group actions have gained significant attention in recent years for their application on post-quantum Sigma protocols and digital signatures. In NIST's recent additional call for post-quantum signatures, three relevant proposals are based on group actions: LESS, MEDS, and ALTEQ. This work explores signature optimisations leveraging a group's factorisation. We show that if the group admits a factorisation as a semidirect product of subgroups, the group action can be restricted on a quotient space under the equivalence relation induced by the factorisation. If the relation is efficiently decidable, we show that it is possible to construct an equivalent Sigma protocol for a relationship that depends only on one of the subgroups. Moreover, if a special class of representative of the quotient space is efficiently computable via a canonical form, the restricted action is effective and does not incur in security loss. Finally, we apply these techniques to the group actions underlying LESS and MEDS, showing how they will affect the length of signatures and public keys.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
digital signaturespost-quantumcode equivalence
Contact author(s)
giuseppe dalconzo @ polito it
alessio meneghetti @ unitn it
edoardo signorini @ telsy it
History
2024-09-30: approved
2024-09-26: received
See all versions
Short URL
https://ia.cr/2024/1510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1510,
      author = {Giuseppe D'Alconzo and Alessio Meneghetti and Edoardo Signorini},
      title = {Group Factorisation for Smaller Signatures from Cryptographic Group Actions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1510},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.