Pour aller plus loin

La caverne d’Ali Baba

En 1989, 2 cryptographes, le Belge Jean-Jacques Quisquater et le Français Louis Guillou, ont signé avec leurs familles, 10 auteurs en tout, plus un collaborateur pour la version anglaise, un article au titre désarmant : How to Explain Zero-Knowledge Protocols to Your Children (comment expliquer les protocoles à divulgation nulle de connaissance à vos enfants ; trad. IA). C’est un conte, et il vaut mieux qu’un cours.

Une caverne se divise, dès l’entrée, en 2 galeries en cul-de-sac, séparées au fond par un mur qu’ouvre un mot magique. Un certain Mick Ali, peut-être descendant d’Ali Baba, prétend connaître le mot sans vouloir le dire. Il entre seul et s’enfonce dans l’une des galeries, sans qu’on voie laquelle ; un journaliste le suit jusqu’à la fourche, jette une pièce et lui crie de ressortir à droite ou à gauche. Celui qui sait ressort toujours du côté demandé, quitte à franchir le mur ; un bluffeur n’a qu’une chance sur 2 de s’être engagé dans la bonne galerie.

Une fois, cela ne prouve rien. La scène est jouée 40 fois, en souvenir des 40 voleurs, et réussie 40 fois : pour un tricheur, ce serait gagner 40 fois de suite à pile ou face, soit moins d’une chance sur 1 000 milliards. Le journaliste est convaincu. Il ne connaît toujours pas le mot.

Vient alors le coup de théâtre, qui est le cœur de l’affaire. Un journaliste concurrent, jaloux de l’exclusivité, filme la même scène avec un sosie qui ignore tout du secret ; la moitié des prises sont ratées, il les coupe au montage et garde 40 réussites. Les 2 films passent le même soir, l’affaire va au tribunal, et ni les juges ni les experts ne parviennent à les distinguer. Moralité des auteurs : puisque le faux ne transmettait rien du secret, et qu’on ne peut le distinguer du vrai, « the genuine tape did not convey knowledge of the secret either » (le vrai film ne transmettait pas davantage la connaissance du secret ; trad. IA).

Tout est là. Goldwasser, Micali et Rackoff ont défini la preuve à divulgation nulle de connaissance par ce critère précis : tout ce que le vérificateur a vu, il aurait pu en fabriquer lui-même, sans le secret et en un temps raisonnable, une copie que nul ne saurait distinguer de l’original, et cela même s’il avait triché dans ses questions. Les mathématiciens appellent « simulateur » le procédé qui fabrique cette copie. Le premier journaliste était convaincu parce qu’il avait choisi lui-même, au hasard et sur le moment, le côté à exiger. Son film ne convainc personne, parce que rien n’y distingue l’épreuve de sa contrefaçon.

La conviction ne se transmet pas à un tiers ; au vérificateur, seule passe la vérité de la proposition.

Une preuve qui ne voyage pas, puis une preuve qui voyage

La caverne a un défaut, pour une démocratie : elle ne convainc que celui qui pose les questions. Or nous voulons que tous vérifient le même tirage, chacun de son côté, sans avoir assisté à rien.

En 1988, Manuel Blum, Paul Feldman et Silvio Micali ont montré qu’on pouvait se passer de l’interaction, pourvu que celui qui prouve et celui qui vérifie partagent d’avance une courte chaîne de chiffres tirée au hasard ; la version publiée en 1991 par Blum, De Santis, Micali et Persiano en donne la forme achevée. La preuve s’écrit alors une fois pour toutes, et quiconque peut la vérifier, demain ou dans 10 ans. C’est ce qui rend concevable un tirage « vérifiable par tout citoyen ».

Cette commodité a 2 prix, et nous les disons. Le premier tient à la chaîne partagée. Dans la version de 1988, elle est simplement tirée au hasard ; mais les preuves compactes qu’emploient aujourd’hui beaucoup de systèmes la fabriquent à partir d’ingrédients secrets, et celui qui les connaîtrait pourrait forger de fausses preuves. Ces systèmes ouvrent donc leur vie par une « cérémonie », où plusieurs participants apportent chacun leur part de hasard, l’ensemble restant sûr pourvu qu’un seul d’entre eux ait détruit la sienne ; Zcash a procédé ainsi à son lancement, et l’on verra plus bas ce qu’il en est advenu. D’autres systèmes se passent de cérémonie, au prix de preuves plus lourdes. On reconnaît, transposée dans les mathématiques, la règle que notre texte pose pour les opérateurs : une fraude doit se voir dès lors qu’un seul fonctionne loyalement.

Le second prix : une preuve qui voyage peut devenir un reçu. Si le votant peut prouver à n’importe qui ce qu’il a voté, il peut le prouver à celui qui le paie ou le menace. C’est pourquoi le Titre I, article 12 n’admet un dispositif électronique que s’il permet à chaque électeur de vérifier que son suffrage a été pris en compte tel qu’il l’a émis, « sans pouvoir le prouver à quiconque » (2°), et pourquoi « nul ne peut exiger d’un électeur qu’il révèle ou prouve le sens de son vote » (Titre II, article 9, 4°). La preuve sert le décompte et la qualité de membre ; elle ne doit jamais servir de quittance.

Ce qu’elle prouve, chez nous

Le tirage. Notre texte en fixe le cadre : chaque tirage au sort « s’opère sur une liste arrêtée et scellée avant le tirage, au moyen d’un aléa produit en public, que nul ne peut maîtriser seul, et d’un programme dont le code source est publié » (Titre II, article 9, 1°). Concrètement, on publie d’abord l’empreinte de la liste, une sorte de sceau qui interdit de la changer ensuite sans que cela se voie ; l’aléa naît en public, si bien que personne ne peut recommencer le tirage jusqu’à obtenir l’Agora qui lui plaît ; puis on publie une preuve que les 7 777 personnes retenues sortent bien de cette liste, par cette méthode et de cet aléa, sans publier leurs noms. La preuve porte sur ce que l’article 8 appelle la régularité du tirage, rien de plus, rien de moins. Elle ne suppose aucun fichier où l’on rapprocherait les noms des fonctions, ce que le 5° du Titre II, article 8 interdit en toutes lettres.

La qualité. Chaque personne tirée reçoit un titre, « par un moyen numérique ou non numérique à son choix » (même 5°). Avec lui, elle prouve qu’elle est l’une des 7 777, non laquelle. C’est le geste qu’accomplit déjà, avec la puce d’un passeport biométrique, l’outil ukrainien dont parle la riposte « Des applications référendaires existent déjà : vous arrivez après la bataille ».

L’unicité. Du titre et de l’identifiant d’un scrutin, ou d’un sujet, on tirera un marqueur à usage unique (en anglais nullifier). Le même titre donne toujours le même marqueur pour le même scrutin : un second bulletin qui le porte est reconnu. Selon la règle que fixera la loi organique, il sera refusé, ou il remplacera le premier, comme en Estonie, où l’électeur contraint peut revoter ; pour les scrutins du peuple, notre texte a déjà tranché, puisque « le suffrage exprimé en personne l’emporte sur tout suffrage émis à distance » (Titre II, article 9, 4°). Sans le secret du titre, nul ne remonte du marqueur à la personne.

Appliqué à chaque sujet, le même procédé permet ce que l’article 8 exige depuis sa version 10 : que « chaque membre ne compte qu’une fois pour un même sujet », sans que l’on puisse relier ses contributions d’un sujet à l’autre. Reste une question que les notes de l’article posent elles-mêmes : le procédé suffit-il à garantir que nul ne siège 2 fois à l’Agora, d’une session à l’autre, sans fichier centralisé, et relève-t-il de la loi organique ? Nous ne la tranchons pas ici.

Ce qu’elle ne prouve pas

La liberté de celui qui vote. Une preuve établit qu’un bulletin est valide, non qu’il a été rempli librement. Le cryptographe Ari Juels et ses coauteurs ont posé dès 2005 les exigences d’un vote qui résiste à la contrainte ; l’entrée L’application référendaire les expose. Notre réponse n’est pas mathématique : un titre remis sur papier si on le préfère, et le droit de délibérer et de voter par un moyen non numérique, notamment en mairie, dans des conditions qui garantissent « le secret de son vote et celui de sa qualité » (Titre II, article 8, 6°).

La remise des titres. La preuve ne dit pas non plus comment chaque personne tirée apprend qu’elle l’est, et reçoit son titre, sans que personne fasse le rapprochement : c’est l’affaire du calcul réparti entre les opérateurs. Le titre sur papier, que notre texte permet, est ici le point faible, car celui qui l’imprime pourrait en connaître le secret. Les notes de l’article 8 posent elles-mêmes la question ; nous ne prétendons pas l’avoir résolue.

L’honnêteté de celui qui fait tourner la machine. La documentation de MACI le dit avec une franchise qui l’honore : « No one except a trusted coordinator should be able to decrypt a vote » (personne, hormis un coordinateur de confiance, ne devrait pouvoir déchiffrer un vote ; trad. IA). Les preuves y empêchent un coordinateur malhonnête de fausser le décompte, et la chaîne Ethereum, de censurer un bulletin ; rien ne l’empêche de lire. Pis : il reste le seul à qui le votant peut prouver son vote, si bien que, complice d’un corrupteur, il rétablirait le reçu que MACI voulait abolir.

Un MACI tel qu’il est documenté ne satisferait donc pas notre texte, qui veut qu’aucun opérateur n’accède aux données des votants. Il faudrait répartir la clé entre plusieurs opérateurs (on parle de déchiffrement à seuil), et ce n’est pas gratuit : plus il faut d’opérateurs pour lire, mieux le secret est gardé, mais plus un seul d’entre eux peut bloquer le dépouillement. C’est à la loi organique de fixer le seuil, et aux auditeurs de le vérifier. La preuve atteste l’exactitude d’un calcul, pourvu que le logiciel et ses paramètres soient sains ; le secret, lui, dépend de la manière dont on partage les clés.

La justesse du logiciel. Le 1^er mars 2018, un cryptographe de l’entreprise qui développait Zcash découvrit une faille dans l’article savant de 2014 sur lequel reposait la monnaie : la procédure qui fabriquait les paramètres produisait, par erreur, des éléments en trop, grâce auxquels un tricheur pouvait faire accepter de fausses preuves. Ces éléments figuraient dans la transcription publique de la cérémonie de lancement : la cérémonie, qui devait protéger la monnaie, portait la faille. L’entreprise l’a écrit sans détour : « an attacker could have created fake Zcash without being detected » (un attaquant aurait pu créer de faux Zcash sans être détecté ; trad. IA).

Selon elle, la faille avait échappé pendant des années à des cryptographes réputés, à des auditeurs extérieurs et aux équipes qui avaient bâti d’autres projets sur le même code. Entre la découverte et le correctif, elle retira la transcription et prétendit, par une version de couverture, qu’elle avait été effacée par accident ; la faille fut corrigée par une mise à jour du réseau le 28 octobre 2018, la transcription reconstituée et republiée ensuite, et l’affaire révélée le 5 février 2019. Elle dit n’avoir vu aucun signe qu’une fausse pièce ait été frappée.

Retenons la leçon, qui n’accable personne : une preuve atteste que le programme a dit oui ; elle n’atteste pas que le programme avait raison de le dire. Et pendant 11 mois, les utilisateurs ont ignoré ce que savaient 4 personnes. Notre texte ne règle pas encore le sort d’une faille découverte entre 2 audits : délai de divulgation, information de la Cour de garantie démocratique, suspension du dispositif. Il prévoit seulement, et c’est déjà beaucoup, que tout citoyen peut saisir la Cour d’un manquement, et qu’alors l’Agora délibère et vote selon un mode physique jusqu’à ce qu’il y soit remédié (Titre II, article 8, 6°). Le reste est à écrire ; votre aide est la bienvenue.

La vérité de ce qu’on lui donne. La preuve établit que le tirage s’est fait sur la liste scellée, non que cette liste est la vraie. Une liste qui compterait des fantômes, ou qui oublierait un quartier, donnerait un tirage parfaitement prouvé et parfaitement faux. Les informaticiens ont pour cela un proverbe moins élégant que la caverne : déchets à l’entrée, déchets à la sortie.

C’est pourquoi le Titre I, article 12 rend la liste électorale de chaque bureau consultable par tout électeur du ressort (4°). Et, comme le reconnaît l’entrée L’application référendaire, la preuve d’identité repose en dernier ressort sur des papiers que signe l’État.

Ce qu’il faut décider. La preuve dit « c’est exact » ; elle ne dit jamais « c’est juste ». Et quand un calcul refuse un bulletin ou un titre, la personne doit pouvoir demander qu’un être humain réexamine et tranche (Titre V, article 3-1, 2°).

Ce que nous concédons

Qui vérifiera vraiment ? Le Titre I, article 12 pose une exigence que la preuve ne satisfait pas seule : « Tout citoyen doit pouvoir vérifier, sans connaissances techniques particulières, les étapes essentielles du scrutin et l’exactitude du résultat » (2°). Disons-le franchement : une preuve à divulgation nulle n’est pas une étape que le citoyen vérifie sans compétence. Seuls quelques spécialistes refont le calcul, et les autres font confiance à ce qu’ils publient.

Ce que chacun vérifie seul, ce sont la liste de son bureau (4°), le résultat de chaque bureau publié avant toute centralisation (2°) et la voie de papier (1°). La preuve s’ajoute à ces contrôles ; elle ne les remplace pas. Les notes de l’article 12 laissent d’ailleurs ouverte la question de savoir qui juge du critère « sans connaissances techniques particulières ». Le programme de vérification est enfin lui-même un logiciel, qu’il faut croire ; la parade connue consiste à en disposer de plusieurs, écrits par des équipes qui s’ignorent, et c’est à la loi organique ou aux auditeurs de l’exiger.

Des hypothèses que personne n’a démontrées. La généralité de la méthode, démontrée en 1986 et publiée en 1991 par Oded Goldreich, Silvio Micali et Avi Wigderson pour tout ce qui se vérifie efficacement, vaut sous l’hypothèse que des fonctions de chiffrement sûres existent : c’est une conjecture que les spécialistes tiennent pour très solide, non un théorème. Les preuves compactes qu’emploient Zcash ou MACI reposent, elles, sur des hypothèses plus fortes et plus jeunes : c’est le prix de leur légèreté.

Certaines constructions en usage ne résisteraient pas à un ordinateur quantique assez puissant, qui n’existe pas encore ; et ce qu’on chiffre aujourd’hui sur un registre public et éternel, une machine de demain pourra le lire. Le secret d’un vote doit durer plus longtemps que la cryptographie qui le protège : raison de plus pour que les audits suivent l’état de l’art, et pour ne rien inscrire au registre qui puisse un jour trahir quelqu’un.

L’argument d’autorité. « C’est mathématique » peut faire taire aussi sûrement que « c’est la loi ». Une technique que presque personne ne comprend risque d’enfanter un clergé, et le citoyen sommé de croire les experts n’a guère gagné au change. Notre parade est ailleurs que dans les mathématiques : la voie de papier, que chacun comprend, demeure, et la voix du plus méfiant pèse autant, en mairie, que celle du plus savant. Le reproche de solutionnisme qu’adresserait un lecteur sévère, discuté dans l’entrée L’application référendaire, vaut ici plus qu’ailleurs.

La complexité, enfin. Chaque couche ajoutée est une surface d’erreur de plus ; Zcash l’a montré. Quand un procédé simple suffit, il l’emporte.

Ce que cela change

Il a fallu à la France plus de 25 ans de débats, rappelle Roger-Pol Droit, pour imposer l’enveloppe et l’isoloir, par la loi du 29 juillet 1913, bien après les colonies australiennes, pionnières dès les années 1850. Le rideau protégeait l’électeur du regard du patron, du notable et du voisin. La preuve à divulgation nulle de connaissance est la cousine mathématique du dépouillement public : chacun voit que les bulletins sont comptés, nul ne voit à qui ils appartiennent. Mais elle n’a pas de rideau.

C’est un dépouillement public sans visages. Ce n’est pas un isoloir.

Voilà pourquoi nous gardons la mairie. Nous ne vous demandons pas de croire les mathématiciens ; nous vous demandons de garder le droit de les vérifier, et des bulletins de papier pour le jour où vous ne ferez plus confiance à personne.