La démocratie n'est pas un vote, c'est un décompte des voix.
Tom StoppardPour les chercheurs en cryptographie, le vote électronique n'est principalement pas lié à la machine à voter et non au vote en ligne - c'est juste un
domaine pour la recherche mathématique . La recherche sur le vote électronique crée des protocoles, des composants mathématiques clés,
des systèmes de vote sécurisés et
vérifiables , ou des systèmes dans lesquels les auditeurs et les électeurs indépendants peuvent vérifier en toute sécurité l'exactitude du décompte des votes. Ces systèmes ne sont pas de simples travaux théoriques, mais déjà de véritables technologies utilisées pour de vraies élections: à Tacoma Park, Maryland, les électeurs ont fait confiance au système
Scantegrity II , basé sur des bulletins de vote en papier à encre invisible, et les cryptographes eux-mêmes ont utilisé les systèmes de vote en ligne
Helios pour l'
élection des dirigeants.
Le vote électronique est un sujet extrêmement compliqué, donc dans cet article je me limiterai aux concepts clés: qu'est-ce que la vérification vocale sûre signifie, comment puis-je compter les votes sans aborder chacun individuellement et ce qui empêche les électeurs de tricher. Je ne vous donnerai pas une description complète de l'ensemble du protocole du vote électronique avec toutes ses nuances, mais ceux qui le souhaitent peuvent rechercher indépendamment des travaux sur ce sujet,
qui sont nombreux .
Confirmation sécurisée
À quoi s'attendre d'un système de vote sécurisé?
Premièrement, et le plus évident: vous devez vérifier que les bulletins de vote sont correctement comptés, c'est-à-dire que tout le monde puisse confirmer que le dépouillement final est effectué en fonction du nombre de bulletins remplis par les électeurs. Le chèque ne doit donner aucune information supplémentaire, à l'exception des totaux. En particulier, le réviseur ne devrait pas pouvoir deviner qui a voté. Cela équivaut au décompte manuel classique des bulletins papier.
Deuxièmement, il est nécessaire que tout électeur puisse s'assurer que son vote est compté et compté correctement. Cela doit être fait sans divulguer son vote, et dans un cas plus général, l'électeur ne devrait pas être en mesure de prouver pour qui il a voté. Cela est fait pour éliminer la coercition et pour permettre aux électeurs de choisir librement un candidat sans craindre les conséquences de leur choix.
Enfin, le système de vote devrait être protégé contre la fraude: l'électeur ne devrait pas pouvoir voter plus d'une fois et il ne devrait pas être possible de modifier ou de copier le bulletin de vote. De plus, seuls les électeurs inscrits doivent pouvoir voter.
Donc, pour résumer: nous avons besoin de l'examen du public, de la confiance des électeurs, de la résistance à la coercition et de l'intégrité des élections. Ces principes ont été mis en avant dans une étude fondamentale de Chaum, Neff et al., Publiée au début des années 2000.
Principes de base
La plupart des protocoles de vote électronique classiques fonctionnent comme suit:
- L'électeur reçoit un jeton sous forme de bulletin, qui change selon son choix. Différents électeurs reçoivent des bulletins de vote différents.
- L'électeur chiffre le bulletin de vote (en utilisant un type de cryptage spécial qui permet à la magie du vote électronique de fonctionner, et l'envoie pour que les organisateurs du vote reçoivent un bulletin de vote crypté.
- Les organisateurs publient des newsletters cryptées sur le babillard, la «chaîne de diffusion publique avec mémoire», dans le jargon cryptographique - en termes simples, sur quelque chose comme Pastebin.
- Les organisateurs combinent des bulletins de vote cryptés pour calculer un résultat mis en cache. Ensuite, ils le décodent (mais pas les bulletins de vote eux-mêmes!) Et publient les résultats.
- Après avoir reçu le résultat et les voix cryptées, n'importe qui peut vérifier son exactitude.
Nombre sécurisé: cryptage homomorphique
À la 4ème étape, les organisateurs combinent des cryptogrammes pour créer un nouveau cryptogramme cryptant la somme des votes individuels. Pour cela, les schémas de vote électronique utilisent le schéma de cryptage Enc (), dans lequel vous pouvez calculer Enc (v1 + v2), ayant seulement Enc (v1) et Enc (v2) à portée de main, et sans connaître la clé de cryptage. De tels schémas de chiffrement sont appelés
homomorphes .
Par exemple, s'ils sont grandement simplifiés, les électeurs américains font ce qui suit le 8 novembre:
- Ils reçoivent la newsletter Clinton et la newsletter Trump des organisateurs (pour simplifier, nous ne considérerons que deux candidats).
- Ils écrivent Enc (1) sur un bulletin de vote et Enc (0) sur l'autre, en utilisant la clé publique émise par les organisateurs comme clé.
Les bulletins de vote cryptés sont ensuite publiés sur le tableau d'affichage avec la pièce d'identité de l'électeur. Je sais tout ce qui a voté, mais il est impossible de comprendre pour qui exactement, car chaque Enc (0) et Enc (1) sont uniques, et nous utilisons un cryptage fort et aléatoire. Si le cryptage était déterministe, l'électeur pourrait être contraint de révéler sa voix en calculant à nouveau Enc (0) et en le comparant avec la valeur inscrite au tableau.
Enfin, les organisateurs combinent tous les bulletins de vote pour Clinton et obtiennent le résultat d'Enc (le nombre de votes pour Clinton), puis ils font de même avec les bulletins de vote pour Trump et obtiennent Enc (le nombre de votes pour Trump). Ensuite, ils prennent la clé de déchiffrement et déchiffrent ces deux valeurs, déclarant le gagnant.
Comment trouver un schéma de cryptage homomorphe? Assez facile - les circuits comme RSA et ElGamal sont homomorphes dans leur forme de base car ils satisfont l'équation
Enc (v1) × Enc (v2) = Enc (v1 × v2)
Mais ce n'est pas exactement ce dont nous avons besoin - c'est un homomorphisme multiplicatif, mais nous avons besoin d'un homomorphisme additif. Il existe des astuces qui transforment les schémas RSA et ElGamal en schémas addictivement homomorphes, mais au lieu de cela, je vais montrer un schéma moins connu qui est immédiatement homomorphe additif:
le cryptosystème Paye crypte le message v1 en
Enc (v1) = g
v1 r1
n mod n
2Où n = pq et g sont fixes, et r1 est un entier aléatoire de] 1; n
2 [. Par conséquent, nous avons:
Enc (v1) × Enc (v2) = (g
v1 r1
n ) × (g
v2 r2
n ) mod n
2 = g
v1 + v2 (r1r2)
n mod n
2 = Enc (v1 + v2)
Autrement dit, le schéma Peye peut être utilisé pour calculer les votes chiffrés.
Pour tricher, un électeur peut vouloir écrire Enc (10000) au lieu de Enc (1) dans le bulletin de vote pour ajouter des votes au candidat. En cas de mauvaises intentions, vous pouvez écrire Enc (very_large_number) pour que cela entraîne un débordement de l'ensemble et une défaillance de l'ensemble du système. Comment garantir la validité vocale (0 ou 1) sans déchiffrement?
La solution est la
connaissance zéro non interactive (NIZK). La preuve NINR est un objet cryptographique très complexe et extrêmement puissant: dans notre cas, elle permettra à l'électeur de prouver que son cryptogramme contient 0 ou 1, mais sans montrer le message chiffré lui-même. Dans le cas général, les preuves NINR permettent au prouveur de convaincre le vérificateur de la véracité de la déclaration en lui envoyant uniquement un ensemble de données sans aucun autre type d'interaction.
Le système le plus simple sans divulgation est peut-être
le schéma de Schnorr : disons que vous connaissez la solution au problème de logarithme discret (la tâche difficile derrière
DSA et le chiffrement sur les courbes elliptiques), et vous voulez prouver que vous connaissez sa solution sans divulguer la solution elle-même. Autrement dit, vous connaissez x tel que g
x = y mod p, et l'examinateur ne connaît que g, y et p. Pour convaincre le critique, vous jouez au jeu suivant:
- Choisissez un nombre aléatoire r et envoyez la valeur g r au testeur (obligation).
- Vous obtenez un nombre aléatoire s du testeur (appel).
- Envoyer au vérificateur s = r + cx.
- L'examinateur calcule g s = g r + cx et vérifie qu'il est égal à g r × y c = g r × (g x ) c .
Dans ce protocole interactif, le prouveur ne divulgue pas la valeur de x, car il n'envoie que des nombres aléatoires. Cependant, seul le prouveur qui connaît x peut envoyer s, réussissant le dernier test.
Pour transformer un tel protocole interactif en un protocole non interactif (qui peut être envoyé avec un seul ensemble de données), des preuves NINR sont construites. Nous jouons à ce jeu par nous-mêmes et faisons semblant d'être un testeur afin que le vrai testeur s'assure que nous ne pouvons pas proposer la preuve NINR sans connaître la déclaration prouvée.
Conclusion
Idées clés discutées dans cet article:
- Le principal problème d'un système de vote électronique sécurisé est l'audibilité publique. Ceci est réalisé en publiant des newsletters cryptées dans un forum accessible au public. Les électeurs doivent également décrire le mécanisme qui procède lui-même à la confirmation.
- L'exactitude du vote est confirmée en autorisant chaque électeur avec une pièce d'identité unique et en donnant aux électeurs un accès qui leur permet de vérifier que leur bulletin de vote 1) a été compté et 2) n'a pas été modifié.
- Les électeurs ne peuvent pas être punis pour avoir voté pour de «mauvais» candidats en raison de la résistance à la coercition, qui, en particulier, est obtenue grâce à un cryptage imprévisible et probabiliste.
- La confidentialité des bulletins de vote est garantie par le fait que les votes chiffrés ne sont pas déchiffrés, et seul le résultat créé à l'aide du chiffrement homomorphique est déchiffré.
- L'escroquerie ne fonctionne pas si nous forçons les électeurs à publier des preuves cryptographiques de la validité de leur bulletin de vote en utilisant NINR.
Les concepts et les technologies décrits ici peuvent sembler profonds et complexes, mais en réalité ce n'est que la pointe de l'iceberg. Vous ne pouvez pas créer un système de vote électronique fonctionnant en toute sécurité simplement en suivant la description. Par exemple, j'ai omis des détails tels que la façon dont les électeurs vérifient leurs bulletins de vote dans la pratique, la raison de l'utilisation du serveur NINR, etc. L'essentiel est que tout protocole de vote électronique sécurisé est une chose très compliquée et pleine de nuances, et la mise en œuvre réelle ajoute une complexité supplémentaire en raison de facteurs humains et organisationnels.
Pour en savoir plus sur la cryptographie liée au sujet du vote électronique, vous pouvez étudier ces matériaux de qualité: