Cutting the GRASS: Threshold GRoup Action Signature Schemes

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, other group actions, such as isogeny-based ones, received interest from the cryptographic community, attracted by the possibility of translating old discrete logarithm-based functionalities. Usually, research focuses on abelian group actions; however in this work we show that isomorphism problems which stem from non-abelian cryptographic group actions can be viable building blocks for threshold sig- nature 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 two different flavors of code-based cryptographic group actions, respectively at the basis of the LESS and MEDS signature schemes, two of NIST’s candidates in the recent call for post-quantum standardization.