Signature en anneau bLSAG

2024-06-21
cryptographie, mathématiques

Une signature en anneau (ring signature) est une preuve cryptographique qu'un message est intègre et a été authentifié par une personne parmi une assemblée donnée, sans révéler son identité.

Par exemple, les membres d'un jury pourraient chacun annoncer son verdict anonymement, de sorte que ni les autres juré·es ni le public ne puissent établir un lien entre un verdict et une personne. Afin de s'assurer de l'authenticité des verdicts, chaque verdict est accompagné d'une signature en anneau qui permet de prouver qu'il a bien été émis par un membre du jury.

Il existe plusieurs algorithmes de signature en anneau. Sera présenté ici bLSAG, qui a la propriété de permettre de détecter le cas où deux signatures auraient été émises par la même personne. Dans l'exemple du jury, on s'assure ainsi que personne n'a voté deux fois.

Ce résumé de bLSAG prend comme source le document Zero to Monero 2.0.0 (page 29) ainsi que la bibliothèque Rust nazgul qui implémente plusieurs schémas de signature en anneau dont bLSAG. Il sert de documentation supplémentaire à la bibliothèque Rust orodruin que j'ai développée pour implémenter les transactions anonymes dans Duniter.

Prérequis : bases d'algèbre et de cryptologie. La connaissance des courbes elliptiques n'est pas nécessaire.

#Notations

• $\mathbb{Z}/l\mathbb{Z}$ les nombres entiers modulo $l$
• $E$ une courbe elliptique (ensemble fini de points, formant un groupe sur lequel le problème du logarithme discret est supposé difficile)
• $G$ un générateur de $E$
• $\mathbin\Vert$ opérateur de concaténation
• $x[n]$ le reste par la division de $x$ par $n$
• $H$ une fonction de hachage cryptographique (en fonction du contexte, son image est dans $\mathbb{Z}/l\mathbb{Z}$ ou dans $E$)
• On parlera d'anneau $\mathcal{R}$, au sens d'un ensemble ordonné de clés publiques, et non de la structure algébrique d'anneau. C'est ambigü mais c'est le terme consacré, comme en anglais ring.

#Signature

La signature $\sigma(m)$ d'un message $m$, par la clé secrète $k_\pi$ dont la clé publique $K_\pi$ est dans l'anneau $\mathcal{R}=\{K_1,\ldots,K_n\}$, est obtenue comme suit :

• $k_\pi \in \mathbb{Z}/l\mathbb{Z}$ la clé privée d'Alice
• $K_\pi = G k_\pi \in E$ la clé publique d'Alice
• $\tilde K_\pi = k_\pi H(K_\pi) \in E$ l'image de la clé d'Alice
• $r_1,\ldots,r_{\pi-1},\alpha,r_{\pi+1},\ldots,r_n$ nombres aléatoires dans $\mathbb{Z}/l\mathbb{Z}$
• $c_{\pi+1} = H(m \mathbin\Vert \alpha G \mathbin\Vert \alpha H(K_\pi))$
• $\forall i \in \{\pi+1,\ldots,n,1,\ldots,\pi-1\},\ c_{(i+1)[n]} = H(m \mathbin\Vert r_i G + c_i K_i \mathbin\Vert r_i H(K_i) + c_i \tilde K_\pi)$
• $r_\pi = \alpha - c_\pi k_\pi$
• $\sigma(m) = (\mathcal{R}, \tilde K_\pi, c_1, (r_1, \ldots, r_n))$

#Vérification

• Vérifier $l\tilde K_\pi=0$
• $c_1' = c_1$
• $\forall i \in \{1,\ldots,n\},\ c_{i+1}' = H(m \mathbin\Vert r_i G + c_i' K_i \mathbin\Vert r_i H(K_i) + c_i' \tilde K_\pi)$
• Vérifier $c_1 = c_{n+1}'$

On comprend maintenant l'explication du nom de signature en anneau. On forme un anneau, ou un cercle, avec toutes les clés, et on fait faire un tour de l'anneau au challenge. Chaque clé le modifie à son tour. Pour retomber sur le même challenge à la fin, il faut qu'une clé quelque part dans l'anneau, sans qu'on puisse savoir où, ait fait la bonne modification qui annule le bruit créé par les autres.

#Correction

Montrons que l'algorithme de vérification est correct. Rappelons les définitions suivantes :

• $k_\pi$ la clé privée d'Alice
• $K_\pi = G k_\pi$ la clé publique d'Alice
• $\tilde K_\pi = k_\pi H(K_\pi)$ l'image de la clé d'Alice
• $c_{\pi+1} = H(m \mathbin\Vert \alpha G \mathbin\Vert \alpha H(K_\pi))$
• $\forall i \in \{\pi+1,\ldots,n,1,\ldots,\pi-1\},\ c_{(i+1)[n]} = H(m \mathbin\Vert r_i G + c_i K_i \mathbin\Vert r_i H(K_i) + c_i \tilde K_\pi)$
• $r_\pi = \alpha - c_\pi k_\pi$

Le but est de construire successivement les $c_i'$ afin de trouver $c_1=c_{n+1}'$ si la signature est authentique.

$$ \begin{align*} c_1 = c_{n+1}' &\Leftrightarrow \begin{cases} r_n G + c_n K_n = r_n G + c_n' K_n \\ r_n H(K_n) + c_n \tilde K_\pi = r_n H(K_n) + c_n' \tilde K_\pi \end{cases} \\ &\Leftrightarrow \begin{cases} c_n K_n = c_n' K_n \\ c_n \tilde K_\pi = c_n' \tilde K_\pi \end{cases} \\ &\Leftarrow c_n = c_n' \\ &\Leftrightarrow \begin{cases} c_{n-1} K_{n-1} = c_{n-1}' K_{n-1} \\ c_{n-1} \tilde K_\pi = c_{n-1}' \tilde K_\pi \end{cases} \\ &\Leftarrow c_{\pi+1} = c_{\pi+1}' \quad\text{par récurrence} \\ &\Leftrightarrow \begin{cases} \alpha G = r_\pi G + c_\pi K_\pi &\quad\text{(1)}\\ \alpha H(K_\pi) = r_\pi H(K_\pi) + c_\pi \tilde K_\pi &\quad\text{(2)} \end{cases} \end{align*} $$

Montrons que (1) et (2) sont vrais :

$$ \begin{align*} \text{(1)} &\Leftrightarrow \alpha G = (\alpha - c_\pi k_\pi) G + c_\pi K_\pi \\ &\Leftrightarrow \alpha G = \alpha G + c_\pi k_\pi + c_\pi K_\pi G \\ &\Leftarrow K_\pi = k_\pi G \end{align*} $$

$$ \begin{align*} \text{(2)} &\Leftrightarrow \alpha H(K_\pi) = (\alpha - c_\pi k_\pi) H(K_\pi) + c_\pi \tilde K \\ &\Leftrightarrow \alpha H(K_\pi) = \alpha H(K_\pi) - c_\pi k_\pi H(K_\pi) + c_\pi k_\pi H(K_\pi) \end{align*} $$

La signature est donc correcte.

#Sécurité

Sans faire de preuve de sécurité, ayons une intuition de ce pourquoi le système est sûr :

La signature est-elle infalsifiable, c'est-à-dire que la forger nécessite bien de connaître $k_\pi$ ? On voit que les preuves de (1) et (2) utilisent $r_\pi = \alpha - c_\pi k_\pi$, donc la clé privée.

La signature est-elle anonyme, c'est-à-dire qu'on ne peut pas retrouver $\pi$ ? On a que $r_\pi$ est bruité par $\alpha$. On ne peut pas distinguer $r_\pi$ des autres $r_i$, puisqu'ils sont aléatoires uniformes comme $\alpha$ et $c_\pi$ (qui est un hash), et que $k_\pi$ est secret.