# Signature de cercle

La signature de cercle (en anglais : Ring signature), aussi appelé signature d’anneau, est un procédé cryptographique permettant à une personne de signer électroniquement de façon anonyme un message ou un document au nom d’un « cercle ». Les membres de ce cercle sont choisis par l’auteur de la signature et ne sont pas nécessairement informés de leur implication dans la création de la signature électronique. La seule contrainte est qu’ils doivent tous avoir une clef cryptographique publique.
La signature de cercle a donné lieu à un dérivé: la signature de cercle à seuil, où la signature est initiée par un nombre prédéfini de membres du cercle.

## Principe

Comme l'indique le titre de l'article où elle est décrite pour la première fois, How to Leak a Secret, le but premier de cette signature est de permettre la fuite d'information.
Dans cet article est donné l'exemple d'un membre d'un cabinet ministériel voulant donner à un journaliste des informations sur le premier ministre. Il ne désire évidemment pas divulguer son identité, mais souhaite que le journaliste sache que la fuite vient du cabinet et non pas d'un plaisantin. La signature de cercle lui permet ainsi de signer en tant que membre du cabinet ministériel, et non en tant qu'individu, sans que ses collègues soient au courant, ni que quiconque puisse remonter à lui, contrairement à la signature de groupe qui impose une coopération des membres inclus dans la signature et la possibilité pour une personne déterminée à l'initialisation de connaître l'identité du signataire.
Une autre utilisation proposée dans cet article est celle permettant de générer une signature qui n'aura de valeur que pour le destinataire. Ainsi la source envoie un document signé à l'aide d'une signature de cercle comprenant sa clef et celle du destinataire. Ce dernier, sachant qu'il ne l'a pas produit, a donc la preuve que le message provient bien de la source. Mais s'il montre le document à un tiers, ce dernier ne peut pas être sûr que le message n'est pas un faux, créé par le destinataire.

## Définition

Une signature d’anneau est définie comme étant la donnée de quatre algorithmes, certains similaires à ceux d’une signature numérique: (Init, Gén, Signer, Vérifier). Ceux-ci fonctionnent de la manière suivante :
* L'initialisation Init prend en entrée un paramètre de sécurité et renvoie une chaîne de référence commune ρ.
* La génération de clefs Gén, qui est lancée par l'utilisateur, prend en entrée la chaîne de référence commune, et renvoie un couple de clefs : une clef de vérification vk, et une clef de signature sk.
* La signature Signer prend en entrée la clef de signature sk, la chaîne de référence commune, le message à signer, un ensemble R de clefs de vérification telle que celle associée à la clef de signature sk y appartient. Et cet algorithme renvoie une signature σ.
* La vérification Vérifier prend en entrée la chaîne de référence commune, un ensemble R de clefs de vérifications, un message M et une signature σ, et renvoie accepte ou rejette.
Ces algorithmes vont de pair avec des notions de sécurité associés, qui sont la correction de la signature, qui spécifie que si une signature est honnêtement générée, alors elle sera toujours acceptée. La non-falsifiabilité, qui requiert que sans posséder de clefs privée associée à un des éléments de l'ensemble R, il est impossible de concevoir une signature valide, et l’anonymat, qui dit qu'il est impossible de lier une signature à son signataire.

## Le schéma de Rivest, Shamir et Tauman

Dans cette partie, une description du schéma proposé par Rivest, Shamir et Tauman est donnée.
Dans ce schéma, l'utilisateur génère une signature σ pour le message M à signer, un aléa v, son couple clef privée/publique et les clefs publiques des autres membres du cercle R = (pk$_i$)$_{i∈[1;n]}$. De plus ce schéma dépend d’un schéma de chiffrement (Enc, Dec).
Les utilisateurs peuvent ainsi vérifier cette signature à l'aide de σ, M, v et de l'ensemble des clefs publiques impliquées dans le processus de création.

### Signature

Le signataire génère un haché σ du message M et choisit ensuite un nonce v$_0$. Pour chaque clef publique pk$_i$ ∈ R autre que la sienne, le signataire choisit une valeur x$_i$ aléatoirement, la chiffre avec la clef publique pk$_i$ et effectue une disjonction exclusive du résultat avec la valeur v avant d'appliquer une permutation symétrique E$_σ$ au résultat, ce qui donnera une nouvelle valeur « v$_i$ ».
Ce qui donne itérativement : v$_i$ := E$_σ$ (Enc$_{pki}$(x$_i$) ⊕ v$_{i-1}$)
On recommence la manipulation avec les autres clefs publiques.
À la fin, on se retrouve avec une valeur v = v$_n$. On recherche alors la valeur y qui, mise en ou exclusif avec le v trouvé et permuté avec E$_σ$, permet de retrouver v$_0$. Autrement dit v$_0$ = E$_σ$(y ⊕ v). On utilise enfin la clef privée pour retrouver l'antécédent de y par le chiffrement, c'est-à-dire x = Dec$_{sk}$(y).
Finalement la signature renvoyée sera Σ = (v, (x$_i$)$_i$)

### Vérification

Le destinataire refait les calculs v$_i$ = E$_σ$ (f (x$_i$) ⊕ v$_{i+1}$) pour toutes les clefs publiques de la signature et vérifie qu'il retrouve bien le v original à la fin.
La taille de la signature est linéaire en N, qui correspond à la taille du cercle, car il faut spécifier les aléas x$_i$ utilisées par chaque participants.

### Preuve de concept

Ci-suit une preuve de concept implantée en Python ou Python3 du papier original, utilisant RSA comme cryptosystème asymétrique. Le cercle contient quatre membres.

## Autres Schémas

Par la suite, d'autres schémas ont été conçus, dont celui de Dodis, Kiayias, Nicolosi et Shoup, qui propose un schéma à signatures de taille constante en le nombre d'utilisateurs en utilisant des accumulateurs et le schéma d'authentification de Fiat-Shamir. Une autre version, dans le modèle standard, possédant une taille qui croît comme la racine carrée du nombre d'utilisateurs (O(√N)) a été proposée par Chandran, Groth et Sahai.

## Cryptomonnaies

La technologie Cryptonote utilise des signatures de cercles. Celle-ci est utilisée dans des crypto-monnaies comme Monero, Bytecoin ou DarkNote.
Le principe de signature d’anneau a également été portée sur ShadowCash, une crypto-monnaie inspirée de Bitcoin.