Cutting the GRASS: Threshold GRoup Action Signature Schemes

Michele Battagliola; Giacomo Borin; Alessio Meneghetti; Edoardo Persichetti

Paper 2023/859

Cutting the GRASS: Threshold GRoup Action Signature Schemes

Michele Battagliola, University of Trento, Università Politecnica delle Marche

Giacomo Borin

, University of Trento

Alessio Meneghetti, University of Trento

Edoardo Persichetti

, Florida Atlantic University, Sapienza University of Rome

Abstract

Group actions are fundamental mathematical tools, with a long history of use in cryptography. Indeed, the action of finite groups at the basis of the discrete logarithm problem is behind a very large portion of modern cryptographic systems. With the advent of post-quantum cryptography, however, the method for building protocols shifted towards a different paradigm, centered on the difficulty of discerning 'noisy' objects, as is the case for lattices, codes, and multivariate systems. This method yields promising results for 'core' primitives such as encryption or signature, but can be less than ideal in the case when more advanced functionalities are required. In this work, we show that isomorphism problems which stem from cryptographic group actions, can be viable building blocks for threshold signature schemes. In particular, we construct a full $N$-out-of-$N$ threshold signature scheme, and discuss the efficiency issues arising from extending it to the generic $T$-out-of-$N$ case. To give a practical outlook on our constructions, we instantiate them with the LESS and MEDS frameworks, which are two flavors of code-based cryptographic group actions. Finally, we highlight some ideas that would allow for a more efficient and compact $(T,N)$ threshold variant of LESS, whose security relies on new hardness assumptions.

Note: Added a new appendix for non pseudorandom action

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. CT-RSA
Keywords: Group actions Code equivalence Threshold cryptography Signature schemes Post quantum cryptography LESS
Contact author(s): m battagliola @ staff univpm it
giacomo borin @ studenti unitn it
alessio meneghetti @ unitn it
epersichetti @ fau edu
History: 2024-03-25: last of 3 revisions; 2023-06-07: received; See all versions
Short URL: https://ia.cr/2023/859
License: CC BY

BibTeX

@misc{cryptoeprint:2023/859,
      author = {Michele Battagliola and Giacomo Borin and Alessio Meneghetti and Edoardo Persichetti},
      title = {Cutting the {GRASS}: Threshold {GRoup} Action Signature Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/859},
      year = {2023},
      url = {https://eprint.iacr.org/2023/859}
}