The paper is a joint work with Michele Battagliola, Alessio Meneghetti and Edoardo Persichetti; it can be downloaded here and it has been published and presented at CT-RSA 2024. We proceed here with a brief summary of the main points.

Threshold Signatures

A $T,N$-threshold digital signature scheme is a protocol designed to distribute the right to sign messages to any subset of at least $T$ out of $N$ key owners. Then, any subset of malicious users of size up to the threshold $T$ won’t be able to forge a valid signature alone.

Recently the design and the standardization of Multi-Party Threshold Schemes received much more interest, even from NIST, since the can be used, for example, to enable a more fine-grained control of secret assets, to perform Secure Multi-Party Computation and to improve Distributed Ledger Technologies.

Group Actions

For any group action $\star : G \times X \to X$ we can always define a digital signature via a non interactive proof of knowledge of a secret linking group element $g$ such that $g \star x = y$, where $x,y$ is our public key. The simple idea can be summarized by the diagram

The core idea of the $\Sigma$ protocol is that the verifier produces a new ephemeral set element $\tilde{x} = \tilde{g}\star x$, then showing or the full black arrow ($\tilde{g}$) or the gray dashed one ($\tilde{g}g^{-1}$), but never both of them together.

When considering the exponentiation on a cyclic group we get the core idea behind the Schnorr signature, however, luckily for post-quantum cryptography, several new group actions are emerging from which we can also define digital signatures, for example from isogenies of ellyptic curves or equivalence of linear codes or tensors. More on the design of these signatures can be read here.

MPC of a Group Action

It is clear that multiple parties having access to additive shares $x_1,x_2,…,x_N$ of $x = \sum x_i$ can compute the exponentiation $g^x$ by multiplying the exponentiation of their shares $g^{x_1} \cdot g^{x_2} \cdots g^{x_N} = g^{\sum x_i}$. This idea can be adapted to use also any kind of LSSS. It is folklore that using multiplicative shares $ g = g_1 \cdot g_2 \cdots g_N$ we can do the same with any group actions:

note that the computations are sequential and if $G$ is non-commutative the order matters. This procedure can be employed, for example, to obtain a Distributed Key Generation for $\star$ between $N$ users.

Contributions

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.

For abelian group actions (i.e. CSIFiSh and SCALLOP as of today) the community already explored several combinations of techniques to obtain secure distributed key and signature generation, however the protocols employed usually strongly rely in the commutativity of the group or make the resulting primitive mostly unpractical because of eccessive use of NIZKPs.

The Non-Abelian Case

In the paper we showed how the core ideas of multiparty computation can still be used to define a threshold scheme, in fact the triangular diagram from before can still be computed by multiple users in a recursive flavour:

This natural and naive $N$-out-of-$N$ scheme can be rendered to an $T$-out of-$N$ threshold protocol by using Replicated Secret Sharing. This create a clear trade off between the simplicity of the construction and an exponential increase of communication cost between the parties. However, since the most important use cases like $(2,3)$ or $(3,5)$ have small $T,N$, we still get efficient threshold signatures.

Security of the Scheme

With respect to this we showed that a secure Distributed Key Generation can be achieved by adapting known ad-hoc crafted ZKPs, but this requires to send two parallel pairs of elements: \(x_1 \xrightarrow{g \ \star} {y}_1 \text{ and } x_2 \xrightarrow{g \ \star} {y}_2 \ ;\) so we require as additional security assumption that this additional pair does not help the recover of the secret $g$.

Remark: recently it has been showed that for some particular instances of hamming code equivalence for specific choice of parameters this addidiotional pair can be used to recover the secret monomial map, however in the appendix we proposed a possible workaround, even if this new technique need further inspections.

With respect to the Signature Generation by using some additional rounds and secure randomness (also called salt) we can achieve security against malicious users without intensive ZKPs, differently from previous research directions. Also, as an interesting corollary, this additional randomness can be used to prove the security in the QROM model.

Instantiations

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. Also we showed that almost all the optimizations already proposed for the signatures can be adapted also to the multiparty case, gaining usable and efficient schemes. As a proof of concept we report here the results in $\mathsf{KiB}$ and $\mathsf{MiB}$ for the thresholdization of MEDS (parameters from version 1.1):

Recommended citation: Battagliola, Michele, Giacomo Borin, Alessio Meneghetti, and Edoardo Persichetti. "Cutting the GRASS: Threshold GRoup Action Signature Schemes." CT-RSA 2024.
Download Paper