Brevet FR2906058A1 — publié le 20080321

PROCEDE ET SERVEUR DE VERIFICATION DU CONTENU D'UNE URNE VIRTUELLE D'UN SYSTEME DE VOTE ELECTRONIQUE CHIFFRE PAR UN ALGORITHME HOMOMORPHIQUE. La présente invention concerne un serveur et un procédé de vote électronique, ainsi qu'un produit programme d'ordinateur pour mettre en oeuvre le procédé. Un système de vote électronique à distance est un système qui permet le vote de manière dématérialisée en utilisant des machines dédiées ou des terminaux informatiques classiques. Dans un tel système, les données de vote sont transmises à des serveurs à travers un réseau de données classique tel que, par exemple, internet ou le réseau téléphonique public. Selon les types d'élection, de tels systèmes permettent de voter dans des bureaux de vote ou à partir de son bureau ou de son domicile. Les normes de sécurité, de confidentialité et d'authentification sont plus ou moins sévères en fonction du type d'élection, les élections publiques étant celles qui font preuve des exigences les plus élevées. En particulier, pour ces élections, les organismes de gestion du vote exigent de forte garantie sur la qualité des votants et de leurs votes tout en exigeant également une parfaite confidentialité sur le vote de chaque électeur. Pour répondre à ces exigences, les systèmes de vote électronique utilisent différentes techniques de cryptographie avancée. A titre d'exemple, le document B. Schoenmaker, a Fully Auditable Electronic Secret-Ballot election , XOOTIC, 2000, décrit l'utilisation du codage El Gamal pour garantir l'intégrité des bulletins de vote et le comptage de ceux-ci sans qu'il soit possible de connaître le détail d'un bulletin de vote particulier. En effet, l'anonymisation des bulletins de vote est une exigence des systèmes de vote électronique et en particulier des systèmes de vote électronique à distance. 2906058 2 Classiquement, les bulletins de vote chiffrés et validés sont stockés sur un serveur ayant des moyens de stockage faisant office d'urne virtuelle. A ce moment là, les bulletins de vote sont chiffrés et séparés des 5 données relatives aux électeurs. II y a alors un besoin de garantir que le contenu de l'urne correspond bien aux bulletins de vote validés et qu'aucune manipulation frauduleuse n'a affecté ce contenu, manipulation pouvant consister en des tentatives d'ajout ou de suppression de bulletins de vote, ou de modification /remplacement de 10 tout ou partie des bulletins de vote. Pour répondre à ce besoin, selon un aspect de l'invention, il est avantageusement proposé un procédé de vote électronique comportant les étapes de : - saisie et validation de bulletins de vote électronique par des 15 électeurs, -chiffrement de chaque bulletin de vote validé par un algorithme de chiffrement homomorphique opérant entre un groupe dont la loi est notée comme une addition et un groupe dont la loi est notée comme une multiplication, 20 - envoi de chaque bulletin de vote chiffré à un serveur comportant des moyens de stockage de tous les bulletins de vote chiffrés, lesdits moyens de stockage faisant office d'urne virtuelle. Le procédé comporte en outre les étapes de : - initialisation d'un registre à la valeur neutre pour la multiplication 25 à l'ouverture du vote, -multiplication de chaque bulletin chiffré arrivant sur le serveur avec la valeur du registre et remplacement de la valeur du registre par le résultat de la multiplication de telle sorte que la valeur du registre soit égale au produit de tous les bulletins de vote chiffrés arrivés sur le serveur, 30 - vérification du contenu de l'urne virtuelle comportant les sous étapes de : • multiplication de tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, 2906058 3 • comparaison de la multiplication des bulletins de vote stockés avec la valeur du registre, • détection d'une anomalie si la comparaison indique que le registre contient une valeur différente du résultat de la multiplication 5 des bulletins de vote stockés ; Selon un autre aspect de l'invention, un serveur de vote électronique comporte : - des moyens de communication avec des terminaux de vote adaptés pour recevoir des bulletins de vote électronique saisis et validés par 10 des électeurs et chiffrés par un algorithme de chiffrement homomorphique opérant entre un groupe dont la loi est notée comme une addition et un groupe dont la loi est notée comme une multiplication, - un premier multiplieur à deux entrées, la première entrée étant adaptée pour recevoir les bulletins de vote chiffrés la seconde entrée étant 15 connectée à un registre et la sortie étant connectée au registre de telle sorte que chaque bulletin de vote chiffré reçu soit multiplié par la valeur du registre et le produit résultat soit stocké dans le registre, - des moyens de stockage formant une urne virtuelle des bulletins de vote reçus, 20 - un second multiplieur adapté pour multiplier tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, - des moyens de comparaison de la valeur du registre et du résultat du second multiplieur adaptés pour déclencher un drapeau d'anomalie si le résultat est différent de la valeur du registre. 25 Selon un autre aspect de l'invention, un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, comprend des instructions de code de programme pour la mise en oeuvre des étapes de : 30 - initialisation d'un registre à la valeur neutre pour la multiplication à l'ouverture du vote, - multiplication de chaque bulletin chiffré arrivant sur le serveur avec la valeur du registre et remplacement de la valeur du registre par le 2906058 4 résultat de la multiplication de telle sorte que la valeur du registre soit égale au produit de tous les bulletins de vote chiffrés arrivés sur le serveur, vérification du contenu de l'urne virtuelle comportant les sous étapes de : 5 • multiplication de tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, • comparaison de la multiplication des bulletins de vote stockés avec la valeur du registre, • détection d'une anomalie si la comparaison indique que le registre 10 contient une valeur différente du résultat de la multiplication des bulletins de vote stockés ; du procédé précédent. D'autres caractéristiques et modes de réalisation particuliers sont décrits dans les revendications dépendantes. 15 L'invention sera mieux comprise à la lecture de la description qui suit, donnée uniquement à titre d'exemple, et faite en référence aux figures en annexe dans lesquelles : - la figure 1 est une vue schématique d'un mode de réalisation d'un système de vote électronique ; 20 - la figure 2 est une vue schématique d'un mode de réalisation d'un serveur de vote, et, - la figure 3 est un ordinogramme d'un mode de réalisation d'un procédé selon l'invention. En référence à la figure 1, un système de vote électronique à 25 distance comporte au moins un terminal de vote 1 connecté à un serveur de vote 3 par l'intermédiaire d'un réseau de données 5 tel qu'internet ou un réseau téléphonique public. Comme il est bien connu de l'homme du métier, un système de vote comporte également de nombreux autres éléments nécessaires à son fonctionnement tel qu'un serveur de gestion des électeurs, 30 par exemple, qui ne sont pas représentés sur la figure 1 et qui ne seront décrits ci-après que dans la mesure où cela est utile à la compréhension de l'invention et de ses modes de réalisation. 2906058 5 Le terminal de vote 1 et le réseau de vote comporte chacun des moyens 7, 9 de communication permettant d'établir une liaison entre les deux machines. Cette liaison peut être sécurisée afin d'éviter qu'un tiers puisse écouter ou s'intercaler dans la communication. 5 Le terminal de vote 1 comporte également une interface homme-machine 11 classique du type écran-souris /clavier ou du type écran tactile ou tout autre type d'interface homme/machine pertinente pour un homme du métier. Cette interface est pilotée par logiciel. Par exemple, dans un mode de réalisation, le pilotage de l'interface homme-machine est réalisé par un 10 navigateur internet permettant le rendu de page HTML ou plus généralement XML. Le terminal comporte de plus un dispositif 13 d'authentification et de signature, par exemple, un lecteur de cartes à puce. Le dispositif 13 d'authentification permet à l'électeur d'utiliser les moyens 15 15 d'authentification et de signature qui lui ont été fournis par l'organisation du vote. On conçoit aisément que, dans le cadre d'une élection publique, l'organisation mette en place un système d'authentification avancé, par exemple à base de cartes à puce, afin de réduire au maximum les fraudes 20 possibles en utilisant des techniques de cryptographie avancée. Le serveur de vote 3, figure 2, comporte des moyens de stockage 17 faisant office d'urne virtuelle. Ce sont, par exemple, des disques durs dans une grappe RAID permettant de protéger les données stockées d'un incident matériel sur les disques durs. 25 Le serveur de vote 3 comporte également un registre 19 pouvant contenir un nombre entier de valeur élevée relié à un premier multiplieur 21. Le premier multiplieur 21 a deux entrées, la première est reliée aux moyens 9 de communication et la seconde entrée est reliée au registre 19. La sortie du multiplieur 21 est reliée au registre 19 pour y stocker le 30 résultat de la multiplication. Entre les moyens 9 de communication et la première entrée du premier multiplieur 21, le serveur de vote 3 comporte des moyens 23 de 2906058 6 stockage intermédiaire, formant tampon et, en aval de ses moyens 23 de stockage intermédiaire, des moyens 25 de validation des bulletins de vote. Le serveur de vote 3 comporte également un second multiplieur 27 5 connectés aux moyens 17 de stockage de l'urne virtuelle et des moyens 29 de comparaison connectés au registre 21 et à la sortie du second multiplieur 27. Les moyens 29 de comparaison commandent des moyens 31 d'alarme. 10 Le fonctionnement du système de vote électronique va être explicité en relation avec la figure 3. Préliminairement à l'ouverture du vote, le registre 19 est initialisé en 38 à la valeur 1. Sur les terminaux de vote 1, les électeurs préparent et valident en 15 40 leurs bulletins de vote. Ceux-ci sont chiffrés en 42 par les terminaux de vote 1 en utilisant un algorithme de chiffrement homomorphique. En mathématique, un homomorphisme de groupes est une fonction entre ces deux groupes qui respecte la structure des groupes. Ainsi, soit (G, 20 +, neutre 0) un groupe G dont la loi de groupe est notée + et l'élément neutre 0 et (H, x, neutre 1) un groupe H dont la loi de groupe est notée x et l'élément neutre 1 , une fonction f : G ---> H est un homomorphisme de groupes lorsque : d(x, y) E G2 , f(x+y) = f(x) x f(y). Selon cette notation, un algorithme de chiffrement homomorphique se 25 caractérise par le fait que le produit des éléments chiffrés est égal au résultat chiffré de la somme des éléments non chiffrés. Afin de clarifier cette description, les notations d'addition et de multiplication seront utilisées par la suite pour désigner la loi du premier groupe et du second groupe respectivement. Mais l'homme du métier notera que tout homomorphisme et 30 toute opération de groupe est utilisable et donc, que ces notations ne sont que des conventions. Ainsi, si Vi est un bulletin de vote d'un vote comportant n bulletins de vote, l'utilisation d'un algorithme de chiffrement Ch homomorphique donne la relation 2906058 JJ(Ch(Vi)) = Ch(lVi) Cette caractéristique est particulièrement avantageuse dans le cadre d'un système de vote électronique puisque, en considérant que la somme des votes correspond au résultat du scrutin, il est possible d'obtenir ce 5 résultat sans avoir à connaître les votes individuels. Dans la classe des algorithmes de chiffrement homomorphique, la variante de l'algorithme El-Gamal est particulièrement avantageuse en ce qu'elle utilise peu de ressources de calcul et de stockage mais tout homomorphisme et toute opération de groupe est utilisable. 10 Les bulletins de vote ainsi chiffrés sont transmis en 44 au serveur de vote 3 par l'intermédiaire des moyens de communication 7, 9. En réception sur le serveur de vote 3, les bulletins de vote sont, de préférence, stockés temporairement en 46, dans les moyens 23 de stockage intermédiaire. 15 Les moyens 23 de stockage intermédiaire ont un rôle de tampon permettant de déconnecter le flux d'arrivée des bulletins de vote de leurs traitements ultérieurs par le serveur. En effet, comme il est bien connu, le rythme de vote par les électeurs varie fortement en fonction de différents éléments comme l'heure de la journée. Il n'est alors pas toujours possible, 20 pour des raisons techniques et/ou économiques, de dimensionner les moyens de vote, et en particulier, les serveurs de vote pour les instants d'afflux maximum. L'utilisation de la zone de stockage intermédiaire 23 permet alors un lissage du traitement des bulletins de vote. Le bulletin de vote est marqué comme non-traité . 25 Dans un mode particulier de réalisation, avant de stocker le bulletin de vote dans les moyens de stockage intermédiaire, le serveur de vote 3 vérifie que le bulletin de vote provient bien d'un électeur habilité à voter. II vérifie, par exemple, des codes associés au bulletin de vote correspondent aux identifiants de l'électeur. En cas de succès de cette vérification, le 30 serveur de vote 3 annote une liste d'émargement d'électeurs et confirme à l'électeur la prise en compte de son vote. 7 2906058 8 Tant que les moyens 23 de stockage contiennent des bulletins de vote et de manière asynchrone par rapport à l'arrivée des bulletins de vote sur le serveur de vote 3, les moyens 25 de validation effectuent en 48 une preuve de connaissance . Ils vérifient que le bulletin de vote a été chiffré 5 en utilisant la clé de chiffrement El-Gama) prévue pour le vote et que le contenu contient des valeurs correctes par rapport aux consignes de vote. Il est à noter que, grâce en particulier aux caractéristiques de l'algorithme de chiffrement homomorphique, les vérifications sont faites sans déchiffrer le bulletin de vote. 10 Si les vérifications constatent que le bulletin de vote comporte des anomalies, celui-ci est marqué comme invalide ou nul et stocké dans une zone spéciale. Lors du décompte final, il sera compté comme bulletin nul . Chaque bulletin vérifié est accumulé en 50 au produit El-Gamal du 15 vote. Pour cela, le bulletin de vote chiffré est multiplié avec le contenu du registre 19 et le résultat est stocké dans le registre 19 à la place du contenu précédent. Ainsi, le registre 19 contient à tout instant le produit des bulletins de vote vérifiés. 20 En même temps que le contenu du registre est mis à jour, le bulletin de vote est marqué vérifié et stocké en 52 dans l'urne virtuelle. Pour vérifier le contenu de l'urne virtuelle, tous les bulletins de vote chiffrés et stockés dans l'urne virtuelle 17 sont multipliés en 54. Le résultat de cette multiplication est comparé en 56 avec la valeur 25 contenue dans le registre 19. Si la comparaison indique que le registre contient une valeur différente du résultat de la multiplication, une alarme est déclenchée en 58 car cela indique que le contenu de l'urne virtuelle a été manipulé. Ainsi la tenue du registre 19 permet d'effectuer un contrôle 30 d'intégrité de l'urne virtuelle. Le contrôle peut être effectué à tout moment pendant le vote soit par un déclenchement automatique aléatoire, soit sur l'initiative d'un scrutateur. 2906058 9 Le procédé de contrôle décrit permet de renforcer l'intégrité de l'urne virtuelle car il est nettement plus difficile de modifier de manière consistante un bulletin de vote de l'urne virtuelle et le produit contenu dans le registre 17. 5 Pour renforcer la sécurité, il est également possible de donner des droits d'accès différents au registre 17 et à l'urne virtuelle. Pour compléter la vérification de l'intégrité du vote, on vérifie également qu'il n'y a aucun bulletin de vote restant comme marqué non traité . 10 Ainsi, le nombre de bulletins reçus doit être égal à la somme du nombre de bulletins contenus dans l'urne virtuelle plus le nombre de bulletins marqués nuls ou invalides . Pour la clarté de la description, l'élection considérée comporte une seule question. 15 Cependant une élection peut nécessiter des opérations de vote portant sur plusieurs questions. Par exemple, l'élection à plusieurs postes combinée avec des questions référendaires. Les produits homomorphiques, tels que, par exemple, El-Gamal, considérés portent alors sur chaque élément comme pour un vote unitaire. 20 REVENDICATIONS 1. Procédé de vote électronique comportant les étapes de : - saisie et validation (40) de bulletins de vote électronique par des électeurs, -chiffrement (42) de chaque bulletin de vote validé par un algorithme de chiffrement homomorphique et sa clé de chiffrement, algorithme opérant entre un groupe dont la loi est notée comme une addition et un groupe dont la loi est notée comme une multiplication, - envoi (44) de chaque bulletin de vote chiffré à un serveur comportant des moyens de stockage de tous les bulletins de vote chiffrés, lesdits moyens de stockage faisant office d'urne virtuelle, caractérisé en ce qu'il comporte en outre les étapes de : - initialisation (38) d'un registre à la valeur neutre pour la multiplication à l'ouverture du vote, - multiplication (50) de chaque bulletin chiffré arrivant sur le serveur avec la valeur du registre et remplacement de la valeur du registre par le résultat de la multiplication de telle sorte que la valeur du registre soit égale au produit de tous les bulletins de vote chiffrés arrivés sur le serveur, - vérification du contenu de l'urne virtuelle comportant les sous étapes de : • multiplication (54) de tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, • comparaison (56) de la multiplication des bulletins de vote stockés avec la valeur du registre, • détection (58) d'une anomalie si la comparaison indique que le registre contient une valeur différente du résultat de la multiplication des bulletins de vote stockés ; 2. Procédé selon la revendication 1, caractérisé en ce que l'algorithme de chiffrement homomorphique est une variante de l'algorithme EI-Gamal. 2906058 11 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que, l'étape de vérification est déclenchée soit par l'utilisateur, soit de façon automatisée régulièrement ou aléatoirement pendant la durée du vote. 5 4. Procédé selon la revendication 1 ou 2, caractérisé en ce que, avant la multiplication de chaque bulletin chiffré avec la valeur du registre, chaque bulletin de vote est vérifié (48) sans être déchiffré afin d'assurer la validité du bulletin de vote, et seulement les bulletins de vote validés 10 sont multipliés avec la valeur du registre et stockés dans l'urne virtuelle. 5. Procédé selon la revendication 4, caractérisé en ce que, à la réception des bulletins de vote chiffrés par le serveur, ceux-ci sont stockés (46) dans une zone de stockage temporaire avant d'être vérifiés. 15 6. Serveur de vote électronique comportant : - des moyens (9) de communication avec des terminaux de vote adaptés pour recevoir des bulletins de vote électronique saisis et validés par des électeurs et cryptés par un algorithme de chiffrement 20 homomorphique opérant entre un groupe dont la loi est notée comme une addition et un groupe dont la loi est notée comme une multiplication, - un premier multiplieur (21) à deux entrées, la première entrée étant adaptée pour recevoir les bulletins de vote cryptés la seconde entrée étant connectée à un registre (19) et la sortie étant connectée au 25 registre de telle sorte que chaque bulletin de vote chiffré reçu soit multiplié par la valeur du registre et le produit résultat soit stocké dans le registre, - des moyens (17) de stockage formant une urne virtuelle des bulletins de vote reçus, 30 - un second multiplieur (27) adapté pour multiplier tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, 2906058 12 - des moyens (29) de comparaison de la valeur du registre et du résultat du second multiplieur adaptés pour déclencher un drapeau d'anomalie si le résultat est différent de la valeur du registre. 5 7. Serveur selon la revendication 6, caractérisé en ce qu'il comporte en outre des moyens (25) de validation des bulletins de vote reçus tels que seuls les bulletins de vote validés sont transmis au premier multiplieur. 8. Serveur selon la revendication 7, caractérisé en ce qu'il comporte en 10 outre des moyens (23) de stockage intermédiaire en amont des moyens de validation adaptés pour permettre un fonctionnement asynchrone des moyens de validation par rapport au flux de réception des bulletins de vote. 15 9. Serveur selon les revendications 6, 7 ou 8, caractérisé en ce que les bulletins de vote sont chiffrés en utilisant une variante de l'algorithme El-Gamal. 10. Produit programme d'ordinateur téléchargeable depuis un réseau de 20 communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions de code de programme pour la mise en oeuvre des étapes de : -initialisation d'un registre à la valeur neutre pour la multiplication à 25 l'ouverture du vote, - multiplication de chaque bulletin chiffré arrivant sur le serveur avec la valeur du registre et remplacement de la valeur du registre par le résultat de la multiplication de telle sorte que la valeur du registre soit égale au produit de tous les bulletins de vote chiffrés arrivés sur le serveur, 30 - vérification du contenu de l'urne virtuelle comportant les sous étapes de : 5 2906058 13 • multiplication de tous les bulletins de vote chiffrés stockés dans l'urne virtuelle, • comparaison de la multiplication des bulletins de vote stockés avec la valeur du registre, • détection d'une anomalie si la comparaison indique que le registre contient une valeur différente du résultat de la multiplication des bulletins de vote stockés ; du procédé selon l'une quelconque des revendications 1 à 5.