A Guide to the Design of Digital Signatures based on Cryptographic Group Actions
Published in Preprint, 2023
This paper is a joint work with Edoardo Persichetti, Paolo Santini, Federico Pintore and Krijn Reijnders. The preprint can be found here.
The Legacy
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, that can be greatly optimized thanks to the distributive properties of the exponentiation, the same properties used by the Shor algorithm to break discrete logarithm on a quantum computer.
New Group Actions
However, luckily for post-quantum cryptography, several new group actions are emerging, for example from isogenies of ellyptic curves or equivalence of linear codes or tensors. With them a variety of techniques aimed at improving their performance and efficiency are emerging. Most of these techniques can be explained as transforming one $\Sigma$-protocol into another, while essentially preserving security.
Contributions
In this work, we present a unified taxonomy of such techniques. In particular, we describe all techniques as tranformation of protocols and we visualise them as graphs with set elements as vertices and linking group elements as edges.
Known Optimisation Techniques
We start by introducing the more established ones, like the use multiple set elements as public keys (MK) or restricting the challenge vectors to the ones with a fixed number of non-zero ones (FW).
We also discuss the use of Seed Trees (ST) to optimize the representation of pseudorandom elements, improving on the bounds used by the community and show how to build a sequential puncturable PRF tailored to specific techniques introduced later.
MPC-in-the-Head for Group Actions
We then analyse the use of the MPC-in-the-Head paradigm in the context of group actions, that recently received some interest from the community.
We combine it with other optimizations and introduce some modifications on the paradigm, obtaining the following results:
- the plain MPC-in-the-Head used for (non-commutative) group actions (MPC) do not have the potential to improve upon the current state-of-the-art optimizations, since the graphs we obtains from the multiparty version of the protocol can be rendered to a subsets of the ones obtained before;
- we show that part of the edges computed during the verification step can be skipped by increasing slightly the communication possible (Skip), in this way, for some particular group actions, it is still possible to use MPC-in-the-Head to obtain optimal signatures;
- for the case of abelian and effective group actions we discuss also how to use the well known Hypercube model (Cube) to further improve the protocol parameter.
A Big Table
Furthermore, as expected, we apply the results of our analysis to the (group action-based) candidates in the current NIST call for digital signatures. As a byproduct of our analysis, we then provide a detailed table with all the core informations on the combinations of the studied techniques, that you can find below (or better in the paper).
| MK | FW | ST | MPC | Skip | Cube | Max Sig Size | Pk Size | Sign Time | Ver Time | Condition |
|---|---|---|---|---|---|---|---|---|---|---|
| - | - | - | - | - | - | $t \ell_G$ | $\ell_X + \lambda$ | $t$ | $t$ | $t = \lambda$ |
| ✔️ | - | - | - | - | - | $t \ell_G$ | $s\ell_X + \lambda$ | $t$ | $t$ | $(s + 1)^t \geq 2^\lambda$ |
| - | ✔️ | - | - | - | - | $(t-w)\lambda + w \ell_G$ | $\ell_X + \lambda$ | $t$ | $t$ | $\binom{t }{w} \geq \lambda$ |
| - | - | ✔️ | - | - | - | $N_{\mathsf{seed}}\lambda + w \ell_G$ | $\ell_X + \lambda$ | $t$ | $t$ | $(s + 1)^t \geq 2^\lambda$ |
| - | - | - | ✔️ | - | - | $t ((m-1)\lambda + \ell_G)$ | $\ell_X + \lambda$ | $t m$ | $t m$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| - | - | - | ✔️ | ✔️ (L) | - | $t \big( (m-1)\lambda + \ell_G + 2 \lambda \big)$ | $\ell_X + \lambda$ | $t m$ | $t\left(1 + \frac{m}{2}\right)$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| - | - | - | ✔️ | ✔️ (R) | - | $t ( (m-1)\lambda + \ell_G)$ | $\ell_X + \lambda$ | $t m$ | $t\left(1 + \frac{m}{2}\right)$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| - | - | - | ✔️ | - | ✔️ | $t ((m - 1)\lambda + \ell_G)$ | $\ell_X + \lambda$ | $t \log(m)$ | $t \log(m)$ | $(m + 1)^t \geq 2^\lambda$ |
| - | ✔️ | ✔️ | - | - | - | $N_{\mathsf{seed}}\lambda + w \ell_G$ | $\ell_X + \lambda$ | $t$ | $t$ | $\binom{t }{w} \geq \lambda$ |
| ✔️ | ✔️ | ✔️ | - | - | - | $N_{\mathsf{seed}}\lambda + w \ell_G$ | $s \ell_X + \lambda$ | $t$ | $t$ | $\binom{t }{w}s^w \geq \lambda$ |
| - | - | ✔️ | ✔️ | - | - | $t (\lceil\log(m)\rceil\lambda +\ell_G)$ | $\ell_X + \lambda$ | $t m$ | $t m$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| ✔️ | - | ✔️ | ✔️ | - | - | $t (\lceil\log(m)\rceil\lambda +\ell_G)$ | $s \ell_X + \lambda$ | $t m$ | $t m$ | $(s m+1)^t \geq 2 ^ {\lambda}$ |
| - | ✔️ | ✔️ | ✔️ | - | - | $N_{\mathsf{seed}} \lambda + w (\lceil\log(m)\rceil\lambda +\ell_G )$ | $\ell_X + \lambda$ | $t m$ | $t m$ | $\binom{t }{w}m^w \geq 2 ^ {\lambda}$ |
| ✔️ | ✔️ | ✔️ | ✔️ | - | - | $N_{\mathsf{seed}} \lambda + w (\lceil\log(m)\rceil\lambda +\ell_G )$ | $s \ell_X + \lambda$ | $t m$ | $t m$ | $\binom{t }{w}(s m)^w \geq 2 ^ {\lambda}$ |
| - | - | ✔️ | ✔️ | - | ✔️ | $t(\log(m) \lambda + \ell_G)$ | $\ell_X + \lambda$ | $t \log(m)$ | $t \log(m)$ | $(m + 1)^t \geq 2^\lambda$ |
| ✔️ | - | ✔️ | ✔️ | - | ✔️ | $t (\log(m)\lambda +\ell_G)$ | $s \ell_X + \lambda$ | $t \log(m)$ | $t \log(m)$ | $(s m + 1)^t \geq 2^\lambda$ |
| - | - | ✔️ | ✔️ | ✔️ (L) | - | $t( \lceil\log(m)\rceil \lambda + \ell_G + 2 \lambda)$ | $\ell_X + \lambda$ | $t m$ | $t(1+ \frac{m}{2})$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| ✔️ | - | ✔️ | ✔️ | ✔️ (L) | - | $t( \lceil\log(m)\rceil \lambda + \ell_G + 2 \lambda)$ | $s \ell_X + \lambda$ | $t m$ | $t(1+ \frac{m}{2})$ | $(s m+1)^t \geq 2 ^ {\lambda}$ |
| - | - | ✔️ | ✔️ | ✔️ (R) | - | $t( \ell_G + 3 \lambda)$ | $\ell_X + \lambda$ | $t m$ | $t(1+ \frac{m}{2})$ | $(m+1)^t \geq 2 ^ {\lambda}$ |
| ✔️ | - | ✔️ | ✔️ | ✔️ (R) | - | $t( \ell_G + 3 \lambda)$ | $s \ell_X + \lambda$ | $t m$ | $t(1+ \frac{m}{2})$ | $(s m+1)^t \geq 2 ^ {\lambda}$ |
| - | ✔️ | ✔️ | ✔️ | ✔️ (L) | - | $N_{\mathsf{seed}}3 \lambda + w (\lceil\log(m)\rceil\lambda +\ell_G + 2 \lambda )$ | $\ell_X + \lambda$ | $t m$ | $t + w\frac{m+1}{2}$ | $\binom{t }{w}m^w \geq 2 ^ {\lambda}$ |
| ✔️ | ✔️ | ✔️ | ✔️ | ✔️ (L) | - | $N_{\mathsf{seed}}3 \lambda + w (\lceil\log(m)\rceil\lambda +\ell_G + 2 \lambda )$ | $s \ell_X + \lambda$ | $t m$ | $t + w\frac{m+1}{2}$ | $\binom{t }{w}(s m)^w \geq 2 ^ {\lambda}$ |
Recommended citation: Giacomo Borin, Edoardo Persichetti, Paolo Santini, Federico Pintore and Krijn Reijnders. "A Guide to the Design of Digital Signatures based on Cryptographic Group Actions." Cryptology ePrint Archive (2023).
Download Paper