01 janv. 2016

Éléments pour un vote électronique cryptographiquement vérifiable

12 Nov. 2016: ajout de la vérification des résultats

Maintenant que nous avons abordé le chiffrement asymétrique de ElGamal et ses propriétés, nous pouvons assembler ces différents éléments pour étudier un système de vote électronique qui serait cryptographiquement vérifiable.

Pour commencer il faut rappeler que le vote est destiné à collecter l’avis sincère des individus d’un groupe sur une décision spécifique. La sincérité de la collecte dépend aussi bien de la qualité de la question que de la constitution du/des groupe(s), du comptage des avis ou encore de l’absence de pression individuelle avant ou après le vote. À cet effet le vote classique avec des bulletins papiers utilise des procédures bien établies où la diffusion des bulletins, les isoloirs, les urnes transparentes … et au final les observateurs permettent de s’assurer de la sincérité de l’expression de chacun. Ces procédures imposent une unité de lieux et de temps.
Le vote électronique (depuis un ordinateur connecté à Internet) permet de s’affranchir des contraintes de déplacements, autorise une durée de vote plus longue et facilite le décompte des choix.
Pour des votes à forts enjeux cette contrainte de temps et de lieux est pourtant de nos jours symboliquement importante : se déplacer un jour particulier pour exprimer son choix démontre une volonté réelle de s’exprimer.
D’autre part, lorsque les déplacements sont difficiles ou impossibles, certains votes permettent l’envoi de bulletins par correspondance. Dans ce cas il n’est pas possible de s’assurer de l’identité réelle de la personne qui glisse son bulletin dans l’enveloppe ni qu’elle effectue son choix sans contrainte. De la même façon si une personne vote depuis son ordinateur il n’est pas possible de garantir qui est réellement derrière le clavier. Ce vote par correspondance est autorisé ou accepté par les parties lorsque ce risque est acceptable : l’effort pour organiser une fraude généralisée semble comme peu probable.

Si le vote électronique permet de s’affranchir des distances et permet une durée de vote plus longue, nous voyons déjà que ce type de vote ne résout pas les questions d’organisation du scrutin, de qualité des questions, de définition des groupes, de vote sans contrainte. Il faut également s’assurer que chaque individu ait accès à un ordinateur connecté et soit capable de s’en servir. Pour terminer, comme tout système informatique il peut y avoir des dysfonctionnements (bugs) qui ne sont pas ou difficilement observables même par des experts. L’objet de ce billet est alors de présenter des technologies qui permettent de s’assurer de l’absence de dysfonctionnement lors de la manipulation des bulletins en autorisant la vérification du vote sans lever l’anonymat des votants.

Tous les calculs présentés dans ce billet sont effectués à partir de formulaires traités sur la page que vous êtes en train de lire et donc par votre ordinateur. Il suffit de consulter le source de cette page pour avoir tous les codes nécessaires. Notez que le chiffrement est utile et même nécessaire à l’expression démocratique. Il suffit de savoir manipuler de grands nombres entiers pour effectuer un chiffrement efficace. Interdire ou limiter l’usage des technologies de chiffrement quelle qu’en soit la raison est donc totalement absurde. Ceux qui proposent ce type de solution sont soit totalement incompétents soit vraiment malhonnêtes.

Déroulement du scrutin

Lorsque le processus électoral a été accepté entre les parties concernées et donc que les modalités du scrutin, du risque acceptable aux listes électorales ont été définis, on peut démarrer un processus de vote électronique.

Préparation

Nous avons vu qu’il est possible de transmettre des bulletins chiffrés par chaque électeur à un destinataire grâce à la clé publique que tous les électeurs connaissent. L’ensemble de ces bulletins est une urne électronique. Il faut alors commencer par créer une clé publique pour le scrutin.
Comme vous pouvez le tester sur le formulaire ci-dessous cette clé est composée à partir des clés publiques de chaque partie (ici Alice et Bob). On peut noter que les clés privées de chaque partie ne sont jamais réunies sur le même ordinateur et leur usage individuel ne permet pas d’accéder au contenu de l’urne ou d’un bulletin. Ces clés privées ne seront réunies que à l’issu du scrutin pour déchiffrer les résultats.

Génération des clés

Alice :
Clé publique : Clé privée: à ne pas diffuser
Bob : (sur un autre ordinateur)
Clé publique : Clé privée: à ne pas diffuser

Scrutin :
Clé privée: Non calculée. Les clés privées de Alice et Bob ne sont pas connues.
Clé publique :

Par soucis de lisibilité j’ai limité la création du nombre premier à un nombre à 5 chiffres au lieu des 610 chiffres qui devraient être utilisés.

La génération aléatoire de ce premier chiffre est essentielle à la conservation du secret de l’urne et des bulletins. La fonction javascript Math.random() que j’utilise dans ces exemples n’est pas suffisamment aléatoire. On dit qu’elle n’est pas cryptographiquement sûre. On pourrait précalculer plus rapidement les nombres premiers les plus probables pour déchiffrer les bulletins. Dans un système en production il faut utiliser des fonctions aléatoires cryptographiquement sûres et donc fortement et irrégulièrement aléatoires. Ils en existent plusieurs, même en javascript et donc utilisables par tout ordinateur.

Vote

L’isoloir est alors l’ordinateur de l’électeur. Dès que la clé publique du scrutin est connue l’électeur peut générer un bulletin chiffré. Le formulaire ci-dessous permet de générer un bulletin pour nos 3 électeurs de démonstration. Un seul choix est possible : il faut cocher ou non la case “choix”. Observez le bulletin généré. alpha et beta sont le choix chiffré (0 ou 1). Il n’est pas possible de savoir quel choix a été coché. Nous avons vu dans les principes du chiffrement ElGamal qu’il était possible de chiffrer une autre valeur que 0 ou 1 et ainsi fausser les résultats. J’ai ajouté dans le formulaire la possibilité de frauder.
Grâce aux preuves à divulgation nulle de connaissance ou preuves de chiffrement (proof) associées au bulletin tout le monde peut détecter cette tentative de fraude et donc refuser ce bulletin.

Les preuves de chiffrement sont composées de deux groupes de valeurs A, B, challenge, réponse. Un groupe de valeurs correspond au choix réel de l’électeur. C’est la vraie preuve. Le second groupe est la preuve de l’autre choix possible. C’est une preuve simulée. En mélangeant l’ordre de ces preuves il n’est pas possible de distinguer la vraie preuve de la preuve simulée et donc de connaître le choix réel de l’électeur. Si plus de deux choix sont possibles il faut créer toutes les autres preuves simulées et ajouter une preuve globale qui permettra de déterminer le nombre de choix sélectionnés.

Ce bulletin chiffré est néanmoins vérifiable par tout le monde : il suffit de tester les preuves, sans déchiffrer le bulletin, pour s’assurer que le contenu est acceptable et éliminer un mauvais bulletin suite à un bug ou par volonté de frauder.

Bulletin
Bulletin :

Lorsque la période de vote est ouverte le bulletin peut être transmis sur le serveur qui centralise tous les bulletins chiffrés dans une urne électronique. Le serveur doit naturellement vérifier le contenu des bulletins et éliminer les bulletins qui ne seraient pas conformes.
Le serveur doit également gérer la liste d’émargement : il doit s’assurer de l’identité de l’électeur et vérifier qu’il n’a déposé qu’un seul bulletin.
On voit que le bulletin ne contient aucune information permettant d’associer un électeur et un bulletin. Il faut par contre que l’électeur soit capable de vérifier que son bulletin est bien dans l’urne. Un bulletin chiffré contenant plusieurs milliers de caractères est difficilement mémorisable, on utilise alors une somme cryptographique (hash) de ce bulletin qui est calculé sur le poste de l’utilisateur et sur le serveur.
Par précaution, on peut s’assurer que le serveur ne contient pas de lien entre l’identité de l’électeur et le hash du bulletin. Si les parties se mettent d’accord elles pourraient déchiffrer un bulletin et connaître le choix de l’électeur. En réalité , elles n’ont pas de raisons valables de se mettre d’accord puisque le choix leur est potentiellement favorable, par contre une partie pourrait capturer les clés privées adverses.

Puisqu’il n’y a pas de lien entre électeur et bulletin et que les bulletins sont chiffrés, l’urne peut être accessible en lecture à tout le monde. Les électeurs peuvent s’assurer que leurs bulletins sont bien pris en compte. Des observateurs peuvent s’assurer que l’urne se remplie régulièrement.

Contenu serveur Contenu de la liste d’émargement :

Contenu de l’urne :

On voit que le serveur est maintenant assez simple : il gère la liste d’émargement, vérifie et enregistre les bulletins. Plus un service est simple moins il risque d’avoir des bugs. Il devient également plus facile de vérifier qu’il n’y a pas de lien entre bulletin et électeur.

Résultats

Lorsque la période de vote est close, plus aucun bulletin n’est accepté dans l’urne. Nous avons vu que le système cryptographique ElGamal permet d’effectuer une somme homomorphique des bulletins sans avoir besoin de les déchiffrer. Cette opération peut être effectuée par tout autre ordinateur que le serveur, à partir de l’ensemble des bulletins chiffrés. Il peut s’agir de l’ordinateur des parties ou des observateurs. Le comptage et recomptage sont accessibles à tous.

Le résultat final est déchiffré par l’utilisation des clés privées (en rouge) qui ont été générées par le premier formulaire et qui ont été soigneusement et séparément conservées.
Avec le résultat on communique publiquement une preuve de connaissance de la clé privée (ici preuve de Schnorr). Tout le monde peut alors vérifier à partir de cette preuve et de la clé publique que la clé privée a bien déchiffré le résultat, sans avoir eu besoin de transmettre cette clé privée.

Addition pour Scrutin
Multiplication homomorphe des bulletins

Solutions log discrets: {}
Résultat :

Vérification de la validité de la clé de déchiffrement
Clé publique :

Discussion

Il apparaît ici que l’usage de bulletins chiffrés avec le système cryptographique ElGamal et de preuves de chiffrement permet de ne plus dépendre d’une boîte noire qui effectue toutes les opérations de manipulation des bulletins. Les opérations de préparation, de vote et de comptage peuvent être clairement distinguées et déléguées. Cela augmentent considérablement la confiance que l’on peut avoir dans une système de vote électronique.

Il existe aujourd’hui deux logiciels libres qui permettent de mettre en œuvre un vote cryptographiquement vérifiable : Helios qui a déjà été utilisé par plusieurs élections réelles et Belenios qui est encore un projet de recherche. Il existe également Pyrios une application en langage Go qui permet de vérifier une urne produite par helios. Vous avez maintenant les éléments pour développer vos propres systèmes de vote électronique vérifiable.

Il reste cependant plusieurs questions qui n’ont pas été abordées ici.
Du point de vue de l’utilisateur, il faut trouver une représentation ergonomique pour rendre intuitive la perception d’un bulletin chiffré, inciter à réaliser sa vérification ou encore générer un bulletin sur une machine qui ne risque pas d’être vérolée.
Du côté serveur il faut mettre en place une identification forte des électeurs qui dissuaderai la tentation de vendre son droit de vote. Il faut également choisir si la liste d’émargement est diffusable à tout électeur et s’assurer de sa cohérence.
Les techniques de chiffrement actuelles seront peut-être décryptables dans quelques années. Il faudrait alors s’assurer que l’ensemble des bulletins soient détruits à l’issue de toutes les procédures de recours or il est impossible de garantir la suppression de copies numériques. Le lien entre bulletin et liste d’émargement doit alors rester strictement et définitivement secret.
Pour lutter contre le risque de vote sous contrainte, certains imaginent plusieurs solutions comme la possibilité de déposer plusieurs bulletins ou de faux bulletins mais cela semble peut compatible avec la nécessité que l’électeur puisse vérifier que son choix sincère est bien pris en compte. Le vote électronique ne peut alors que se substituer au vote par correspondance.

lab.yvesago.net

De l'informaTIC