Calculer, engager et anonymiser avec des primitives spécialisées

Calculer, engager et anonymiser avec des primitives spécialisées

Le chiffrement protège un message, la signature prouve son origine. Mais certains problèmes ne se résument ni à cacher ni à signer : tirer au sort entre parties qui se méfient les unes des autres, prouver qu’un identifiant figure dans une liste sans publier la liste, calculer une moyenne de salaires sans que personne ne voie les salaires, prouver un droit sans décliner son nom. Cette fiche regroupe les primitives conçues pour ces situations : engagements, accumulateurs, calcul multipartite, chiffrement homomorphe et signatures anonymisantes. Elle insiste sur ce qu’elles coûtent et sur ce qu’elles laissent fuir, car leur sophistication a une fâcheuse tendance à faire oublier l’adresse IP de l’utilisateur.

Explication de la marmotte

Dans une enveloppe scellée, on peut glisser sa réponse à une devinette avant que la solution soit connue, puis l’ouvrir plus tard devant tout le monde. Ce chapitre présente des outils qui rendent ce genre de promesse possible avec des nombres : prouver, calculer ensemble ou rester anonyme, sans dévoiler ce qu’on garde pour soi.

→ Lire l’explication complète de la marmotte

S’engager maintenant, révéler plus tard

Un engagement (commitment) fonctionne en deux temps. Pendant la phase de commit, une partie choisit une valeur m, calcule un objet c qui la fige et publie c. Pendant la phase de reveal, elle publie m et l’aléa utilisé, et chacun recalcule c pour vérifier la correspondance. Le terme français historique est la mise en gage.

Deux propriétés définissent un engagement correct. Le hiding (masquage) garantit que c ne révèle rien de m avant l’ouverture. Le binding (liaison) garantit que l’auteur ne peut pas ouvrir c sur une autre valeur m'. Un résultat classique interdit d’avoir les deux de façon parfaite, c’est-à-dire contre un adversaire de puissance illimitée : il faut choisir laquelle des deux repose sur une hypothèse calculatoire.

La construction la plus courante utilise une fonction de hachage : c = SHA-256(r || m), avec SHA-256 (Secure Hash Algorithm, 256 bits) et r un aléa de 32 octets. Le binding découle de la résistance aux collisions, le hiding de l’aléa r et du comportement pseudo-aléatoire du hachage. Sans r, l’engagement sur « oui » ou « non » se casse en deux essais : il suffit de hacher les deux réponses possibles et de comparer. C’est l’erreur la plus fréquente.

L’engagement de Pedersen travaille dans un groupe où le logarithme discret est difficile : c = g^m · h^r, où personne ne connaît le logarithme de h en base g. Il est parfaitement masquant (pour tout m, il existe un r donnant le même c) et calculatoirement liant (ouvrir sur deux valeurs reviendrait à calculer ce logarithme). Il est aussi additivement homomorphe : le produit de deux engagements engage sur la somme, ce qui sert aux votes.

Un engagement n’est pas un chiffrement : il n’existe aucune clé permettant à un tiers de l’ouvrir, seul l’auteur détient de quoi le faire. Les applications vont du tirage au sort à pile ou face par téléphone, décrit par Manuel Blum au début des années 1980, aux enchères scellées, aux votes, et surtout au premier message de nombreuses preuves à divulgation nulle, détaillées dans Prouver sans révéler : ZK et identification.

Prouver l’appartenance efficacement

Un accumulateur à sens unique, introduit par Benaloh et de Mare en 1993, condense un ensemble en une valeur courte, et permet de prouver qu’un élément en fait partie grâce à un witness (témoin) lui aussi court. L’exemple canonique est l’accumulateur RSA (Rivest-Shamir-Adleman) : avec un module N dont personne ne doit connaître la factorisation et des éléments représentés par des nombres premiers x₁, …, xₙ,

A  = g^(x₁ · x₂ · … · xₙ) mod N        valeur publiée
wᵢ = g^(produit de tous les xⱼ sauf xᵢ) mod N   témoin de xᵢ
vérification : wᵢ^xᵢ ≡ A (mod N)

La preuve tient en une seule valeur de la taille du module, quel que soit le nombre d’éléments. L’arbre de Merkle joue un rôle voisin avec une preuve de taille logarithmique : vingt condensés suffisent pour un million de feuilles, sans module secret à générer. Le premier exige une mise en place de confiance : qui connaît la factorisation de N fabrique de faux témoins.

La non-appartenance se prouve aussi : les accumulateurs universels (Li, Li et Xue, 2007) utilisent l’identité de Bézout pour montrer qu’un premier y ne divise pas l’exposant accumulé. C’est utile pour prouver qu’un identifiant ne figure pas sur une liste de révocation.

La révocation est précisément le point douloureux. Retirer un élément change A, donc invalide tous les témoins, que chaque détenteur doit mettre à jour. Les accumulateurs dynamiques (Camenisch et Lysyanskaya, 2002) rendent cette mise à jour possible sans secret, mais elle impose de diffuser les changements et de suivre leur historique. Côté identité, un porteur d’attestation prouve « mon identifiant n’est pas révoqué » sans dire lequel, si la preuve est elle-même à divulgation nulle. Les coûts : vérification rapide, mises à jour coûteuses, gouvernance du paramètre initial lourde. Oublier la révocation lors de la conception, c’est construire un système où une attestation volée reste valide pour l’éternité.

Calculer sans exposer les entrées

Le MPC (Multi-Party Computation, calcul multipartite sécurisé) permet à plusieurs parties de calculer une fonction de leurs entrées privées en n’apprenant que le résultat. Deux grandes familles coexistent.

Les garbled circuits (circuits brouillés), dus à Andrew Yao dans les années 1980, conviennent à deux parties. La première traduit la fonction en circuit booléen et remplace chaque valeur de fil par une étiquette aléatoire, puis chiffre la table de vérité de chaque porte. La seconde évalue le circuit sur des étiquettes qu’elle ne sait pas interpréter. Elle obtient les étiquettes de ses propres entrées par OT (Oblivious Transfer, transfert inconscient), présenté plus bas.

Les protocoles à partage de secret découpent chaque entrée en parts additives ou en parts de Shamir, et les parties calculent sur les parts. Les additions sont gratuites ; les multiplications demandent une interaction. Le prétraitement déplace ce coût : avant de connaître les entrées, les parties préparent des triplets de multiplication de Beaver, consommés ensuite pendant une phase en ligne rapide. Le protocole SPDZ (2012) suit ce modèle. Le MPC utilise donc le partage de secret, mais ne s’y réduit pas : partager un secret le met en lieu sûr, le MPC calcule avec lui. La page Partager un secret et distribuer la confiance traite le premier sujet.

Le modèle d’adversaire change tout. Un participant semi-honnête suit le protocole mais tente de déduire des informations de ce qu’il voit ; un participant malveillant dévie à volonté. Un protocole sûr dans le premier modèle peut s’effondrer dans le second. Il faut aussi préciser le seuil : majorité honnête ou non, nombre de participants corrompus tolérés. Une première application institutionnelle notable est la vente aux enchères de quotas de betterave sucrière au Danemark en 2008.

Le chiffrement homomorphe permet de calculer directement sur des chiffrés. Le chiffrement partiellement homomorphe supporte une seule opération : Paillier (1999) additionne, ElGamal multiplie. Le chiffrement somewhat homomorphic supporte additions et multiplications, mais en nombre limité, car chaque opération augmente un bruit intégré au chiffré ; au-delà d’un seuil, le déchiffrement échoue. Le FHE (Fully Homomorphic Encryption) lève cette limite grâce au bootstrapping, proposé par Craig Gentry en 2009 : on évalue homomorphiquement l’algorithme de déchiffrement pour obtenir un chiffré frais, au bruit réduit. Les schémas actuels se nomment BGV (Brakerski-Gentry-Vaikuntanathan), BFV (Brakerski/Fan-Vercauteren), CKKS (Cheon-Kim-Kim-Song, arithmétique approchée sur des réels) et TFHE (Torus FHE, bootstrapping rapide porte par porte).

Les coûts réalistes restent sévères. Un chiffré FHE pèse couramment des dizaines ou des centaines de kilo-octets, et une opération coûte plusieurs ordres de grandeur de plus que son équivalent en clair. Le MPC paie en bande passante et en allers-retours réseau. Ces outils se justifient quand aucune partie de confiance n’est acceptable, pas pour protéger une base de données au repos, où un chiffrement AEAD (Authenticated Encryption with Associated Data) classique fait le travail pour une fraction du prix.

Anonymat cryptographique

Les signatures aveugles, inventées par David Chaum au début des années 1980, permettent d’obtenir une signature sur un message que le signataire ne voit pas. Avec RSA, le demandeur masque m en m' = m · rᵉ mod N, le signataire renvoie s' = m'ᵈ mod N, et le demandeur retire le masque : s = s' · r⁻¹ = mᵈ mod N. Le signataire ne peut ensuite pas relier s à la séance de signature. Le RFC 9474 (2023) normalise une variante sûre, et les jetons anonymes du type Privacy Pass reposent sur des mécanismes voisins. Une signature aveugle n’est pas une signature anonyme : le signataire est parfaitement identifié, c’est le lien entre la séance et le jeton qui disparaît.

Les signatures inconscientes (oblivious signatures, Chen 1994) inversent la perspective : le destinataire obtient une signature sur un message parmi plusieurs, et le signataire ignore lequel. Elles reposent sur le transfert inconscient, primitive dans laquelle un émetteur propose deux valeurs, le récepteur en obtient une seule, et l’émetteur ignore laquelle. Le transfert inconscient est une brique universelle : le MPC peut entièrement se construire dessus.

Les signatures de groupe (Chaum et van Heyst, 1991) prouvent qu’un membre d’un groupe a signé sans dire lequel, mais un gestionnaire peut lever l’anonymat. Les signatures en anneau (Rivest, Shamir et Tauman, 2001) n’ont pas de gestionnaire : le signataire choisit librement les autres membres de l’anneau, et personne ne peut l’identifier. L’attestation anonyme des TPM (Trusted Platform Module), nommée DAA (Direct Anonymous Attestation), et les credentials anonymes du type Idemix ou U-Prove prolongent ces idées : prouver des attributs signés par un émetteur, éventuellement un seul attribut, sans rendre les présentations reliables entre elles.

Les mixnets (Chaum, 1981) brouillent la relation entre messages entrants et sortants : chaque relais reçoit un lot de messages chiffrés en couches, en retire une, les mélange et les retarde. Tor applique le routage en oignon sans mélange ni retard, au profit de la latence et au détriment de la résistance à un observateur global. La diffusion anonyme par réseaux DC (Dining Cryptographers) offre davantage, pour une communication coûteuse.

La PSI (Private Set Intersection) permet à deux parties de calculer l’intersection de leurs ensembles sans révéler le reste : deux entreprises trouvent leurs clients communs sans échanger leurs fichiers. Elle protège le calcul, pas le résultat : une partie qui soumet un ensemble d’un seul élément apprend si cet élément est chez l’autre. C’est là qu’intervient la confidentialité différentielle (differential privacy, Dwork et coauteurs, 2006), qui n’est pas de la cryptographie : elle ajoute du bruit calibré par un paramètre ε aux résultats publiés pour borner ce qu’on apprend d’un individu. La cryptographie protège le chemin, la confidentialité différentielle la sortie.

Reste le sujet que toutes ces primitives laissent de côté : les métadonnées. Une présentation anonyme envoyée depuis une adresse IP fixe, à 8 h 02 chaque matin, avec une taille caractéristique, n’est anonyme que sur le papier. Et l’anonymat cryptographique n’est pas une conformité réglementaire : l’émission traite des données personnelles, et les journaux restent nominatifs.

Exemples et ateliers

Tirage au sort commit/reveal. Trois parties veulent tirer un nombre entre 0 et 9 sans que l’une puisse influencer le résultat. Chacune choisit une graine sᵢ de 32 octets et un aléa rᵢ de 32 octets, puis publie son engagement :

import hashlib, secrets
s = secrets.token_bytes(32)          # contribution au tirage
r = secrets.token_bytes(32)          # aléa de masquage
c = hashlib.sha256(b"tirage-2026|" + r + s).hexdigest()   # publié en phase 1
# phase 2 : publication de r et s, vérification par tous
# résultat = SHA-256(s1 || s2 || s3) interprété comme entier, modulo 10

Les longueurs fixes évitent toute ambiguïté de concaténation, le préfixe de contexte empêche de réutiliser un engagement d’un autre tirage. Le défaut résiduel est connu : la dernière partie à révéler connaît le résultat avant les autres et peut refuser d’ouvrir. La parade n’est pas cryptographique mais procédurale : une non-révélation vaut forfait, ou un dépôt de garantie est perdu. La page Équité, vote, contrats et divulgation contrôlée développe ce genre de protocole. Le biais modulo est ici négligeable (2²⁵⁶ n’est pas divisible par 10, mais l’écart est de l’ordre de 2⁻²⁵²).

Choisir entre ZK, MPC et FHE. Le choix dépend de qui détient les données et de qui calcule.

Situation	Outil adapté	Raison
Une partie détient les données et doit prouver un résultat à une autre	ZK (Zero-Knowledge)	Le vérificateur n’a pas besoin des données, seulement d’être convaincu
Plusieurs parties détiennent chacune une partie des entrées	MPC	Aucune ne doit voir les entrées des autres
Un client délègue un calcul à un serveur qui ne doit rien voir	FHE	Le serveur calcule à l’aveugle, le client seul déchiffre
Les données doivent seulement être stockées à l’abri	AEAD	Aucun calcul tiers n’est nécessaire

Fuites d’un système de credentials anonymes. Prenons une attestation d’âge présentée à un site. La cryptographie peut rendre deux présentations non reliables et ne révéler que « plus de 18 ans ». Restent visibles : l’émetteur de l’attestation (s’il n’existe qu’un émetteur par pays, le pays fuit), l’heure de présentation, l’adresse IP, l’empreinte du navigateur, et la vérification de révocation si elle interroge en direct l’émetteur. Une liste de révocation téléchargée en entier fuit moins qu’une requête ciblée.

Pièges classiques

Le premier piège est d’utiliser le FHE là où un AEAD suffit : un facteur à plusieurs zéros pour aucune propriété utile. Le deuxième est d’ignorer les métadonnées : l’anonymat d’une signature en anneau survit mal à une adresse IP. Le troisième est d’oublier la révocation, découverte le jour où une attestation est volée. Le quatrième est de confondre anonymat cryptographique et conformité, en présentant une primitive comme une réponse juridique. Le cinquième, plus subtil, est de négliger le modèle de participants malveillants : un protocole MPC prouvé sûr contre des participants semi-honnêtes n’offre aucune garantie contre un participant qui envoie des valeurs fausses.

À ne pas confondre

Un engagement fige une valeur que seul son auteur peut ouvrir ; un chiffrement permet à un détenteur de clé de lire. Le MPC calcule sur des entrées privées ; le partage de secret se contente de répartir une valeur. Le FHE permet le calcul délégué ; le chiffrement de stockage protège des données inertes. Une signature aveugle cache le message au signataire, qui reste identifié ; une signature anonyme (de groupe ou en anneau) cache le signataire lui-même.

FAQ

Le FHE est-il utilisable en production ?
Pour des calculs ciblés (scores, comparaisons, petits modèles), des bibliothèques maintenues existent, comme OpenFHE, Microsoft SEAL ou TFHE-rs. Pour un traitement généraliste, le surcoût reste prohibitif. Une preuve de concept mesurée sur les données réelles s’impose avant tout engagement, au sens commercial du terme.

Conclusion

Ces primitives résolvent des problèmes que le chiffrement et la signature ordinaires ne savent pas poser, chacune avec un coût, un modèle d’adversaire et des fuites résiduelles, métadonnées en tête. Le bon réflexe consiste à formuler d’abord qui détient quoi et qui ne doit rien voir, puis à choisir l’outil le plus simple qui y répond, ce qui reste très souvent un AEAD bien utilisé.

🐝 Ce qui arrive si on s’en passe

Sans engagement, un tirage au sort ou une enchère laisse au dernier participant à parler la possibilité d’ajuster sa réponse à celles des autres, et personne ne peut ensuite démontrer la triche. Sans calcul protégé, mettre des données en commun oblige à désigner une partie qui voit tout, et qui devient la cible unique de quiconque veut l’ensemble. Sans attestations anonymes ni signatures de groupe, prouver un droit revient à décliner son identité à chaque usage : chaque vérification laisse une trace nominative, et le recoupement de ces traces reconstitue un parcours que personne n’avait l’intention de publier. La confidentialité promise par le service devient alors une simple politique, révocable par quiconque accède aux journaux.

🦫 Explication de la marmotte 🍫

Ce chapitre regroupe des outils mathématiques qui protègent autre chose qu’un simple message. Le premier est l’engagement. Une personne choisit une valeur, calcule une empreinte qui la fixe et publie seulement cette empreinte. Plus tard, elle révèle la valeur et chacun vérifie qu’elle correspond. Deux propriétés comptent : l’empreinte ne doit rien laisser deviner de la valeur, et la personne ne doit pas pouvoir changer d’avis après coup. Un deuxième outil permet de prouver qu’un élément appartient ou non à une liste sans montrer toute la liste, à condition de savoir gérer les retraits. D’autres méthodes permettent à plusieurs participants de calculer un résultat commun sans que chacun voie les données des autres, ou de faire un calcul directement sur des données chiffrées. Ces calculs coûtent très cher en temps et en mémoire, et certaines méthodes accumulent une erreur qu’il faut régulièrement effacer. Enfin, des signatures particulières permettent de prouver qu’on fait partie d’un groupe sans dire qui l’on est. Toutes ces protections laissent des fuites : les informations autour de l’échange, comme son heure ou sa taille, restent visibles. Le chapitre insiste aussi sur les participants qui trichent volontairement, et rappelle qu’un outil lourd est inutile quand un chiffrement ordinaire suffit.

À lire aussi

• Chaînes de blocs, wallets et cryptographie économiqueExpliquer les blockchains comme assemblage de primitives cryptographiques, protocoles distribués et incitations, en séparant clairement sécurité cryptographique et sécurité économique.
• Hachage dans les systèmes: intégrité, arbres et preuvesRegrouper les usages systémiques du hachage: empreintes, arbres, preuves, déduplication, chaînes d’intégrité et limites de sécurité.

Pages voisines

La citent

• Ce que le bout en bout laisse voir

Calculer, engager et anonymiser avec des primitives spécialisées

Elle cite

• ⇄Lien dans les deux sens :Équité, vote, contrats et divulgation contrôlée
• ⇄Lien dans les deux sens :Partager un secret et distribuer la confiance
• ⇄Lien dans les deux sens :Chiffrement homomorphe dans le cloud : promesses et limites réelles
• Prouver sans révéler : ZK et identification
• Attestation distante TPM et démarrage mesuré
• Confidentialité différentielle pour télémétrie produit

⇄ : les deux pages se citent l’une l’autre.