Elaboration of E_voting system based on elliptic curve cryptography

'

&

$

%

UNIVERSITÉ DE NGAOUNDÉRÉFaculté des Sciences

Département de Mathématique etInformatique

THE UNIVERSITY OF NGAOUNDEREFaculty of Science

Department of Mathematics andComputer science

Mémoire de Master RechercheMention : Ingénierie Informatique

Parcours : Systèmes et Logiciels en EnvironnementsDistribués

ÉLABORATION D’UN SYSTÈME DE

VOTE ÉLECTRONIQUE À CRÉDIT

ANONYME RÉSISTANT À LACOERCITION

Présenté par

AMBASSA PACÔME LANDRYMatricule : 05J460FS

Titulaire d’une Licence en Sciences et Techniques de l’InformatiqueOption : Architectures et Réseaux

Soutenu publiquement le 11 Janvier 2013Devant le jury constitué de :

David BEKOLLE, Professeur Université de Ngaoundéré PrésidentDaniel TIEUDJO, Maître de Conférences Université de Ngaoundéré DirecteurJean Michel NLONG II, Chargé de Cours Université de Ngaoundéré Examinateur

Année Académique 2010 – 2011

Dédicace

Ce mémoire est dédié à mes parents

MEMOIRE DE MASTER c©AMBASSA Pacôme Landry U.N SLED 2010-2011

Remerciements

Je rends grâce à Dieu, pour avoir rendu possible ce travail.C’est avec une immense joie que j’adresse mes premiers remerciements à mon en-

cadreur, Pr TIEUDJO Daniel, qui a su m’initier à la recherche. Je tiens à le remercierpour sa disponibilité et sa rigueur dans le travail ainsi que pour m’avoir accordÃl’ unegrande liberté nécessaire à l’accomplissement de ce travail, tout en gardant un regardcritique et avisé.

J’adresse également mes remerciements au chef du Département de Mathématiqueset Informatique de la Faculté des Sciences, Pr David BEKOLLE.

J’exprime toute ma gratitude et ma reconnaissance à l’endroit des enseignants du dé-partement de Mathématiques et Informatique de la Faculté des Sciences de l’Universitéde Ngaoundéré, en particulier : Dr NLONG, Dr DAMAKOA, Dr YENKE, Dr HOUPA, DrTCHOUA, Dr KAMGANG et le Dr KAMLA pour ses remarques pendant nos séminaires.

J’exprime toute ma gratitude à Monsieur DIBAI, mon professeur de Physique enclasse de terminale D qui n’est pas étranger à ma décision d’entreprendre des études enInformatique.

La famille et les amis sont indispensables lors d’un travail comme celui ci. Je remer-cie particulièrement mes parents pour m’avoir donné la chance de faire des études dansde très bonnes conditions et pour leur soutien. Je voudrais remercier mes soeurs, mesfrères ainsi que tous mes amis.

Merci à tous mes camarades de promotion, pour avoir affronté ensemble toutes lesdifficultés.

Merci à tous mes camarades du laboratoire de Mathématiques et Expérimentale(LME), TCHAWA, NANGA , HABIBATOU, NZOMOU, DJIODOP, CIDJEU, FOTSO,KOWE, FOHOUE, TCHAWU,TOUOMGUEM, DJATCHA, FOTSA. Vos remarques etsuggestions ont contribué à l’amélioration de ce travail.

Merci à NLEND Éliane de partager quotidiennement mes joies et mes peines.Enfin, je remercie tous ceux dont le nom n’apparait pas dans cette page et qui ont

contribué d’une manière ou d’une autre à la réalisation de ce travail.


Résumé

Voter est un devoir citoyen dans toutes sociétés modernes. C’est un acte fondamentalqui s’avère nécessaire lorsqu’il faut faire un choix. Le vote électronique est un systèmeélectoral qui permet de s’exprimer de manière anonyme dans un environnement in-formatique. Dans ce travail, nous concevons un nouveau schéma de vote électroniquequi assure la completude et est résistant à la coercition. En effet, afin de satisfaire lapropriété de résistance à la coercition nous définissons un crédit anonyme qui est unjeton cryptographique représenté par une signature agrégée transmise à l’électeur lorsde la phase d’enregistrement par les autorités. Ce schéma utilise les systèmes crypto-graphiques sur les courbes elliptiques et assure les propriétés étendues d’un vote élec-tronique. Finalement, nous illustrons numériquement le schéma proposé à l’aide de laplateforme SAGE.

Mots clés : Vote électronique, Résistance à la coercition, Crédit anonyme, Courbeelliptique.


Abstract

Voting is a civic duty in all modern societies. It is a fundamental act that is necessarywhen it comes to make a choice. Electronic voting is an electoral system that allows thischoice anonymously in a computer environment. In This work we formulate a new elec-tronic voting scheme. Our scheme is complete and coercion resistant electronic voting.To satisfy this property we defined a anonymous credential which is cryptographic tokenrepresented by aggregate signatures (signature of Boneh ) which is transmitted to thevoter during the registration phase by the authorities. This scheme uses elliptic curvecryptosystems and provides extended properties of electronic voting. finally numericalllustration of the proposed scheme using SAGE platform was done.

Keys words : Electronic voting , Coercion-resistance, anonymous credential, ellipticcurve.


Table des matières

Dédicace i

Remerciements ii

Résumé iii

Abstract iv

Table des matières vi

Liste des figures vi

Liste des tableaux vii

INTRODUCTION GÉNÉRALE 1

1 PRÉLIMINAIRES 41.1 Généralités sur le vote électronique . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Notion de vote électronique . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Déroulement d’un vote électronique . . . . . . . . . . . . . . . . . . 71.1.3 Propriétés du vote électronique . . . . . . . . . . . . . . . . . . . . . 81.1.4 Définition de quelques concepts sur le vote électronique . . . . . . . 9

1.2 Cryptographie du vote électronique . . . . . . . . . . . . . . . . . . . . . . . 101.2.1 Services de sécurité d’un système de vote électronique . . . . . . . 101.2.2 Primitives cryptographiques . . . . . . . . . . . . . . . . . . . . . . . 111.2.3 Propriétés du vote et lien cryptographique . . . . . . . . . . . . . . 25

1.3 Courbes elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.3.1 Courbes elliptiques définies sur un corps quelconque . . . . . . . . 251.3.2 Courbes elliptiques définies sur un corps fini . . . . . . . . . . . . . 291.3.3 Problème du logarithme discret sur les courbes elliptiques . . . . . 311.3.4 Multiplication scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . 311.3.5 Les systèmes cryptographiques utilisant les courbes elliptiques . . 311.3.6 Sécurité et choix des courbes elliptiques pour la cryptographie . . . 33


Liste des figures vi

2 PRÉSENTATION DE QUELQUES SCHÉMAS DE VOTE ÉLECTRONIQUE 362.1 Schéma de Juels, Catalano et Jakobsson . . . . . . . . . . . . . . . . . . . 36

2.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.1.2 Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.1.3 Vérification du crédit anonyme . . . . . . . . . . . . . . . . . . . . . 392.1.4 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.2 Schéma de Porkodi, Arumuganathan et Vidya . . . . . . . . . . . . . . . . 412.2.1 Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.2.3 Illustration numérique . . . . . . . . . . . . . . . . . . . . . . . . . 442.2.4 Extension au vote à multiples candidats . . . . . . . . . . . . . . . 452.2.5 Illustration numérique pour une élection à quatre candidats . . . 462.2.6 Illustration du non receipt freeness . . . . . . . . . . . . . . . . . . 48

3 PROPOSITION D’UN SCHÉMA DE VOTE 493.1 Outils cryptographiques utilisés . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.1.1 Crédit anonyme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.1.2 Système cryptographique ElGamal distribué Version elliptique . 513.1.3 Mixnet à rechiffrement universellement vérifiable . . . . . . . . . 523.1.4 Preuve non interactive à divulgation nulle de connaissance basée

sur les ECC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.1.5 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2 Présentation du schéma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.2.1 Description détaillée du schéma . . . . . . . . . . . . . . . . . . . . . 563.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 Illustration numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.3.1 Présentation de la plate forme SAGE ( System for Algebra and Geo-

metry Experimentation) . . . . . . . . . . . . . . . . . . . . . . . . . 633.3.2 Modes d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.3.3 Détails d’implémentation . . . . . . . . . . . . . . . . . . . . . . . . 653.3.4 Illustration numérique avec SAGE pour une élection à quatre can-

didats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673.4 Synthèse de quelques résultats . . . . . . . . . . . . . . . . . . . . . . . . . 73

CONCLUSION GÉNÉRALE 74

BIBLIOGRAPHIE 75


Liste des figures

1.1 Mixnet de Chaum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.2 Mixnet à rechiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.3 Interpolation de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.4 Protocole de génération de clé distribuée de Pedersen . . . . . . . . . . . . 231.5 Protocole de déchiffrement distribué . . . . . . . . . . . . . . . . . . . . . . 241.6 Courbes elliptiques définies sur le corps R . . . . . . . . . . . . . . . . . . . 261.7 Addition et doublement d’un point . . . . . . . . . . . . . . . . . . . . . . . 281.8 cas particulier d’addition et doublement . . . . . . . . . . . . . . . . . . . . 281.9 Courbes elliptiques définies sur les corps Fq . . . . . . . . . . . . . . . . . . 29

2.1 Phase d’enregistrement du schéma de Juels et al . . . . . . . . . . . . . . 372.2 Phase de vote du schéma de Juels et al . . . . . . . . . . . . . . . . . . . . 382.3 Phase de décompte du schéma de Juels et al . . . . . . . . . . . . . . . . . 392.4 Schéma de Juels, Catalano et Jakobsson . . . . . . . . . . . . . . . . . . . . 40

3.1 Mécanisme d’une signature agrégée . . . . . . . . . . . . . . . . . . . . . . 503.2 Protocole de déchiffrement distribué . . . . . . . . . . . . . . . . . . . . . . 52


Liste des tableaux

1.1 Tableau récapitulatif des propriétés d’un e-vote et lien cryptographique . 251.2 Points de la courbe d’équation y2 = x3 − 2x− 1 mod 23 . . . . . . . . . . . 301.3 Tableau comparatif des tailles de clés de ElGamal(nombre), RSA et ElGa-

mal(ECC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.1 Valeurs numériques des votes chiffrés pour un référendum . . . . . . . . . 442.2 Valeurs numériques de la phase de décompte lors d’un référendum . . . . 452.3 Valeurs numériques des votes chiffrés pour un vote à candidats multiples 472.4 Valeurs numériques de la phase de décompte lors d’une élection à quatre

candidats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.5 Utilisation des informations pour retrouver le candidat choisi . . . . . . . 48

3.1 Représentation des voix de chaque candidat . . . . . . . . . . . . . . . . . . 603.2 Valeurs numériques des votes . . . . . . . . . . . . . . . . . . . . . . . . . . 693.3 Valeurs des votes rechiffrés . . . . . . . . . . . . . . . . . . . . . . . . . . . 703.4 Élimination des double votes . . . . . . . . . . . . . . . . . . . . . . . . . . 713.5 Tableau de vote unique et valide . . . . . . . . . . . . . . . . . . . . . . . . 71


INTRODUCTION GÉNÉRALE

Le vote selon Connes [5] est une technique permettant à un groupe de personnesd’opérer un choix collectif parmi plusieurs propositions, en agrégeant des préférencesindividuelles. Les choix individuels sont additionnés, soit en les traitant à égalité, soit enles pondérant : en leur affectant un poids variable en fonction des critères déterminés.Ce qui contribue à la formation d’un résultat brut associant une valeur numérique àchaque proposition. Le résultat ainsi obtenu est ensuite interprété pour déterminer siun choix collectif a été valablement exprimé et si oui, lequel ?

L’institution de la démocratie comme régime politique dans nos cités a conduit à unemultiplication du nombre de consultations électorales : on vote pour tout et partout. Ilfaut noter que, le coût d’une élection ou d’un référendum reste très élevé ; cependanten dépit de l’augmentation croissante du nombre de consultations électorales, le tauxde participation aux échéances électorales baisse de plus en plus pour plusieurs raisonsparmi lesquelles : les longues files d’attentes observées devant les bureaux de vote etla fraude électorale qui contribue au désintérêt d’une partie non négligeable de la po-pulation. Avec le développement rapide de l’Informatique et des Applications web, il estdésormais possible de diminuer ce coût et de rendre le processus de vote moins contrai-gnant grâce aux protocoles de votes électroniques (plus particulièrement des systèmesde votes qui utilisent Internet).

Le vote électronique est la collection à distance des choix des électeurs grâce auxmoyens électroniques impliqués dans la construction, la transmission et le décomptedes votes. Il offre de nombreux avantages : un plus grand nombre d’électeurs grâce àl’aisance induite par la possibilité de voter à partir de n’importe quel lieu (confort de sondomicile, lieu de travail), un coût réduit et un calcul plus rapide des résultats pour neciter que ceux-ci.

Malgré ses avantages, le vote par Internet est susceptible d’être altéré par des faillestelles que la coercition. En effet, elle consiste à influencer l’électeur lors de son choix afinde le pousser à voter pour un candidat particulier. A celle ci, on pourrait ajouter l’achatdes votes. Ces failles sont possibles parce que les électeurs votent à partir des lieux noncontrôlés. En outre, ces failles (coercition et achat des votes) peuvent être automatiséespour atteindre un plus grand nombre d’électeurs. Pour Jefferson et al. [2], "Internet



facilite l’achat de vote à grande échelle en permettant aux acheteurs d’automatiser leprocessus".

En 1994, Benaloh propose une solution à ces problèmes qui consiste à empêcher lesélecteurs de créer ou d’obtenir des informations qui prouvent comment ils votent. Decette façon, puisque les électeurs ne peuvent fournir la preuve de leur vote, il supposequ’ils ne peuvent être contraints à voter pour un certain candidat ou de vendre leursvotes. Mais cette solution n’est pas satisfaisante étant donné qu’elle fonctionne unique-ment lorsque les attaquants sont passifs (n’interagissent pas avec l’électeur pendant levote).

Dans [13], Juels, Catalano et Jakobsson définissent une notion appelée résistanceà la coercition, plus complète en ce qui concerne les attaques coercitives dans le votepar Internet. En effet, ils considèrent que les électeurs peuvent être contraints à s’abs-tenir de voter, à révéler des informations secrètes utilisées pour voter et à émettre desvotes aléatoires ; il s’agit de l’une des plus fortes propriétés pour la sécurité d’un systèmede vote par internet. Ils proposent également le premier schéma qui satisfait cette pro-priété. Ils utilisent pour cela un crédit anonyme : qui consiste à assigner un jeton uniqueà chaque votant lors de la phase d’enregistrement, ce qui permet de rendre anonyme levotant lors de son vote. Les limites de ce schéma sont : son inefficience parce que laphase de décompte s’exécute en temps quadratique [24] et son manque de complétude.

Le schéma de Juels et al comme la majorité des travaux sur le vote électroniquerepose sur les systèmes de la théorie des nombres. Or la cryptographie sur les nombresa montré quelques limites. Pour pallier cette vulnérabilité (décelée par les chercheursphysiciens), les mathématiciens se sont lancés à la recherche de nouvelles plateformesqui se substitueraient à celle des nombres.

En 1985, Miller et Koblitz posent indépendamment les bases de la Cryptographiebasée sur les courbes elliptiques (Elliptic Curve Cryptography, en abrégée ECC). Lasécurité de ces systèmes repose sur le problème du logarithme discret sur les courbeselliptiques. L’algorithme connu (Rho Pollard) comme étant le plus efficace pour résoudreun tel problème est à temps exponentiel, contrairement au chiffrement RSA (Rivest,Shamir, Adleman) pour lequel il existe des algorithmes à temps sous-exponentiel. Ainsi,à niveau de sécurité équivalent, ECC requiert des clés beaucoup plus petites que le RSA.Par exemple, il est couramment admis qu’utiliser un RSA avec une longueur de clé de1024 bits offre le même niveau de sécurité qu’un ECC avec une longueur de clé de 160bits [19]. L’utilisation des données plus petites offre beaucoup d’avantages : les calculssont plus rapides, la consommation électrique globale est diminuée et l’espace mémoireest réduit.

Les systèmes basés sur les courbes elliptiques sont de plus en plus utilisés par lesÉtats et les entreprises. C’est ainsi que les gouvernements des USA, Canada et GrandeBretagne pour ne citer que ceux là ont commencé à utiliser la cryptographie sur les



courbes elliptiques dans leur système de sécurité. De même, le navigateur web Mozillamet en place un système permettant aux clients de la messagerie de signer des messageset de vérifier l’identité des expéditeurs par les cryptosystèmes sur les courbes elliptiques[20]. La publication de courbes elliptiques standardisées par le NIST (National Instituteof Standards and Technology ) en 2000 a contribué à accélérer ce processus d’utilisationdes cryptosystèmes basés sur les courbes elliptiques.

En 2011, Dans [16], Porkodi et al propose une nouvelle approche de schéma de vote.Ce schéma de vote repose sur les systèmes cryptographiques des courbes elliptiques.La principale limite de ce schéma est qu’il n’assure pas la propriété de résistance à lacoercition.

L’utilisation d’un outil tel que l’isoloir physique, lors des consultations électoralesdans nos pays (vote traditionnel) permet conceptuellement de protéger l’électeur de lacoercition même si ce n’est pas le cas dans la pratique. Mais dans le vote par Internetde tels outils n’existent pas. La protection du votant passe par la satisfaction par lesystème de vote de la propriété de résistance à la coercition. L’une des solutions consisteà utiliser un crédit anonyme.

L’objectif de ce travail est de concevoir un système de vote électronique qui utilise lecrédit anonyme pour assurer la propriété de résistance à la coercition et dont la sécuritérepose sur les systèmes cryptographiques issus de la théorie des courbes elliptiques.

Ce document est divisé en trois chapitres : le premier chapitre est consacré aux pré-liminaires et comprend entre autres des généralités sur le vote électronique, ensuite lesprimitives cryptographiques utilisées pour offrir les services de sécurité sont détailléeset enfin une brève introduction sur les courbes elliptiques. Dans le second chapitre, nousprésentons quelques schémas de vote électronique, plus précisément ceux proposés dans[13] et [16]. Et le troisième chapitre fait l’objet de notre proposition d’un schéma de voteélectronique par internet résistant à la coercition que nous illustrons numériquementgrâce à la plate-forme SAGE ( System for Algebra and Geometry Experimentation).


CHAPITRE 1

PRÉLIMINAIRES

Dans ce chapitre, nous présentons d’abord les généralités sur le vote électronique,et sa définition d’un point de vue cryptographique en termes de services de sécuritéofferts. Nous énumérons ensuite les différentes primitives cryptographiques utiliséespour garantir ces services et enfin nous introduisons les courbes elliptiques.

1.1 Généralités sur le vote électronique

1.1.1 Notion de vote électronique

Le vote électronique est une élection ou référendum qui implique le recours à desmoyens électroniques au moins lors de l’enregistrement du suffrage. Son but est de fairemieux que le vote traditionnel en permettant à l’électeur de s’exprimer de manière ano-nyme dans un environnement informatique.

On distingue généralement deux types de vote électronique : le vote hors ligne et levote en ligne [7]

– Dans le vote hors ligne, on conserve les outils traditionnels à l’instar des bureauxde vote, des isoloirs , et on utilise l’urne électronique désignée par le terme machineà voter. En pratique, il s’agit d’un ordinateur permettant à l’électeur de voter. Lesavantages de ce type de vote sont : il permet une comptabilisation rapide des bulle-tins mais également, offre aux électeurs la possibilité de voter à partir de n’importequel bureau vote.

– Le vote en ligne (à distance) consiste à rendre possible le vote à partir d’un termi-nal situé à distance du système de vote. Dans ce cas, le vote de l’électeur transitepar un réseau de communication, entre le terminal et le système de vote. Concrè-tement, le vote électronique à distance peut s’effectuer :– par Internet (via un site Internet auquel l’électeur se connecte),– par téléphone (via un serveur vocal interactif),– au moyen de tout autre équipement connecté à distance au système de vote.

Le vote électronique présente de nombreux avantages par rapport au vote tradition-nel :


1.1. GÉNÉRALITÉS SUR LE VOTE ÉLECTRONIQUE 5

1. La facilité et la flexibilité du vote pour l’électeur : l’électeur n’a plus besoinde se trouver en un lieu déterminé (bureau de vote) ni à faire la queue pour voter.La flexibilité permet d’étendre la durée du vote (il est désormais possible de votersur plusieurs jours et à n’importe quel moment).

2. La simplification de l’organisation et de la gestion du vote : par la sup-pression de nombreuses contraintes matérielles liées aux scrutins traditionnels(organisation de bureaux de vote physiques, achat d’urnes, édition et impressiondes bulletins de vote, mobilisation du personnel).

3. La facilité et la rapidité du dépouillement : étant donné que le dépouillementet le calcul des résultats se font de manière automatique.

4. L’harmonisation et la synchronisation des opérations de vote : à traversl’uniformisation complète des conditions du vote, qu’il s’agisse de la présentationdes choix possibles (candidats), de l’expression du vote ou de l’accès à l’information.

5. L’augmentation du taux de participation : du fait de la possibilité de voter àpartir du confort de son domicile ou de n’importe quel autre lieu.

Il faut noter que ces avantages ne sont pleinement obtenus qu’au moyen du vote àdistance par Internet. C’est pour cette raison que dans ce travail nous nous intéressonsessentiellement à ce système. Il permet à un groupe de personnes d’effectuer un vote àdistance et se compose d’une suite d’algorithmes protocolaires exécutés sur les différentsordinateurs des acteurs du système. Les principaux intervenants d’un tel système sont :les votants et les autorités [17].

1. Les votants 1 notés Vi : ce sont eux qui votent lors de l’élection concernée, i estl’identifiant du votant ; on y retrouve un sous ensemble constitué des candidatsnoté cr qui compétissent lors de l’élection. Ces candidats peuvent être des per-sonnes physiques, des partis politiques ou généralement un ensemble de choixpossibles. Toutefois, les actions de l’électeur sont réduites au minimum il peut :s’abstenir de participer au vote s’il le désire, arrêter le processus de vote avant lafin. Dans ce dernier cas de figure, son vote n’est pas considéré.

2. Les autorités électorales : elles sont responsables de la conduite de l’élection,leur puissance de calcul est grande et offre la possibilité de traiter un gros volumede données. Ces autorités peuvent également être défaillantes. Nous distinguons :

– Les autorités d’enregistrement (Rj) : elles s’occupent de l’enregistrement desélecteurs auprès des institutions de votes.

– Les autorités de comptage (décompte) (Tj) : elles s’occupent du décomptedes votes.

1. encore appelés électeurs



1.1.1.1 Types de votes

Un vote dépend du type d’élection. Sa structure se définit en fonction de la ques-tion posée au votant lors du passage au bureau de vote et de la manière d’y répondre.Nous présentons une liste des principaux types de votes auxquels un votant peut êtreconfronté [23],[17] :

1. Le vote Oui/Non : le votant est invité à répondre à une question par "oui" ou par"non". Le vote peut être représenté par un bit (0 ou 1).

2. Le vote 1-parmi-n : le votant vote pour un candidat parmi les n choix possibles.Le vote est représenté par une valeur ∈ [0, n] avec n ∈ N∗. Notons que le choix 0représente le bulletin blanc.

3. Le vote k-parmi-n : le votant vote pour k candidats parmi les n choix possibles.L’ordre n’est pas important. Le vote est représenté par un k-tuple (c1, c2, ..., ck) oùci ∈ [1, n] avec n ∈ N∗.

4. Le vote k-parmi-n ordonné : le votant vote pour k candidats parmi les n choixpossibles et ordonne son choix du meilleur au moins bon. Le vote est représentépar un k-tuple (c1, c2, ..., ck). Les ci sont deux a deux distincts où ci ∈ [1, n] et ci estplus important que ci+1.

5. Le vote 1-parmi-l-parmi-n : le votant choisit d’abord un ensemble parmi les l pos-sibles et dans cet ensemble sélectionné, il choisit n éléments. Le vote est représentépar un k + 1-uplet (i, c1, c2, ..., ck) où les ci sont les éléments du iéme ensemble.

6. Le vote structuré : Pour ce type il y a n niveaux de possibilités. le votant par-court les niveaux du premier au dernier. Au iéme niveau, il peut choisir ki pos-sibilités du sous ensemble Si des possibilités de ce niveau. Si et ki dépendentde ses choix dans les niveaux précédents. Le vote est représenté par un uplet(c11, ..., c1k1 , ..., ci1, ..., ciki , ..., cn1, ..., cnkn) , où {ci1, ..., ciki} ⊂ Si.

7. Le vote par écrit : l’électeur formule sa propre réponse et l’écrit sur le bulletin.Le vote est une chaine de caractère de taille fixe.

Un exemple de vote Oui/Non serait un référendum de type « êtes-vous d’accord avec...». Une élection présidentielle comme celle organisé au Cameroun, est une élection detype « 1-parmi-n »où l’on choisit le candidat qu’on souhaite voir à la présidence parmiles n possibilités. Dans un système de vote k-parmi-n ordonné, le candidat choisi enpremier dans la liste des choix d’un votant obtient le plus de points. Au décompte final,le candidat dont le nombre de points accumulé est le plus grand gagne l’élection. Cesystème de vote est considéré comme le plus démocratique [17]. Un cas particulier estl’élection parlementaire où l’électeur choisit ses représentants, mais ceux ci doivent êtredes candidats d’un même parti politique. C’est un exemple de vote 1-parmi-l-parmi-koù l représente le nombre de partis politiques et K le nombre de candidats sélectionnés.L’ensemble des candidats sélectionnés peut être ordonné ou non.



Après avoir parlé des types de vote, il est maintenant question de montrer commentcommuniquent les différents acteurs du système.

1.1.1.2 Modèle de communication

Dans cette partie nous présentons les différents canaux de communication utilisésdans les systèmes de vote électronique. On distingue généralement :

1. Le tableau de vote public 2noté (BB), qui est publiquement accessible en lec-ture. Tous les participants au processus de vote peuvent librement y publier desinformations. Toutefois lorsqu’on rajoute sur le tableau public une information x,aucun des participants n’a le droit de supprimer ou modifier x. Il est donc considérécomme un canal public possédant une mémoire.

2. Les canaux anonymes 3, ce sont des canaux qui garantissent l’anonymat del’émetteur d’un message. Le récepteur du message qui transite par ce canal neconnait pas l’identité de l’émetteur. Il est difficile, voire impossible de retracer lemessage jusqu’à son origine. Nous parlerons de la réalisation de ce canal à la Sec-tion1.2.2.2.

3. Le canal inécoutable 4 : c’est un canal secret entre deux participants. La com-munication à travers ce canal est impossible à observer car il est physiquementsécurisé. Aucune autre entité en dehors de celles qui participent à la communi-cation ne peut accéder au message. Les acteurs de la communication ne peuventpas prouver ce qui leur a été envoyé. Dans certains schémas de votes on supposel’existence d’un tel canal entre l’électeur et l’autorité.

1.1.2 Déroulement d’un vote électronique

Tout comme les schémas de vote classique, les schémas de vote électronique se dé-roulent en cinq phases qui composent le processus complet. Ces phases sont :

1. Phase de configuration (Initialisation) : c’est pendant cette phase que la loi élec-torale et les règles sont fixées (type de vote, représentation des candidats,..) ; lesparamètres sont générés pour permettre à l’élection d’avoir lieu. Elle correspond àla convocation du corps électoral pour le vote classique (cas du Cameroun). Cettephase est placée sous l’autorité de l’institution chargée d’organiser l’élection.

2. Phase d’enregistrement : c’est durant cette phase que l’enregistrement des vo-tants auprès de l’institution de vote est effectué. Pendant cet enregistrement uncrédit anonyme est transmis à l’électeur par les autorités d’enregistrement.

2. bulletin board en anglais3. anonymous channel4. untappable channel



3. Phase de vote : les votants sont invités à procéder à la construction et la trans-mission de leur vote ; ce dernier étant soigneusement chiffré à l’aide de primitivescryptographiques .

4. Phase de décompte : Les autorités chargées du décompte parcourent le tableaude votes déchiffrent et comptent les voix.

5. Phase de publication : Les votants constatent le résultat de l’élection et véri-fient si celle-ci s’est déroulée correctement. Dans le cas où la vérification n’est pasconcluante, ils contestent l’élection en apportant la preuve. Dans le cas contraire,si tout s’est bien passé, chacun des votants est persuadé que l’élection est règle-mentaire. Et l’autorité désignée publie le résultat de l’élection

1.1.3 Propriétés du vote électronique

Un protocole de vote, pour être utilisable doit vérifier un certain nombre de proprié-tés. Dans cette partie, nous présentons brièvement chacune d’entre elles.

Ces propriétés sont :

1. Secret des votes : personne ne doit pouvoir faire le rapprochement entre un élec-teur et son vote.

2. Éligibilité : seuls les électeurs enregistrés doivent pouvoir voter. Cette propriétéest vérifiée si l’intrus ne peut pas obtenir les paramètres d’authentification (iden-tifiant, mot de passe) de la phase d’enregistrement lui permettant de continuer leprocessus.

3. Pas de double vote : aucun électeur ne doit pouvoir voter deux fois lors d’unemême élection. Toutefois, dans le cas contraire son vote ne doit pas être comptabi-lisé plus d’une fois. Il ne faudrait pas rejeter les votes valides.

4. Pas de résultat Partiel (Équité) : personne ne doit être capable d’obtenir desrésultats partiels. car la connaissance de ces résultats pourrait influencer les élec-teurs n’ayant pas encore voté.

5. Vérifiabilité individuelle : chaque votant doit pouvoir vérifier que son vote a étécorrectement introduit et comptabilisé.

6. Vérifiabilité universelle : chaque votant doit pouvoir vérifier que le résultat pu-blié est bien la somme de tous les votes valides émis, comptabilisés sans modifica-tion.

7. Précision : l’élection est précise si le vote n’est pas altéré, par conséquent lesrésultats du vote ne doivent pas être modifiés en ajoutant des votes invalides ouen changeant le contenu des bulletins par exemple (intégrité).

8. Complétude : Un vote valide doit être comptabilisé et un vote invalide ne doit pasêtre comptabilisé.



9. Receipt-freeness (Sans Reçu) : elle représente une forme forte de confidentia-lité. Définie par Benaloh en 1994 [24] comme suit : aucun électeur ne doit être ca-pable de prouver la manière dont il a voté, d’obtenir ou d’être capable de construireun reçu de son vote, (c’est à dire un document prouvant comment il a voté). Cettepropriété est importante pour la prévention contre la vente des votes.

10. Résistance à la coercition : la coercition consiste à forcer quelqu’un à voter d’unecertaine manière et de s’en assurer par la suite.

Les propriétés ci-dessus sont hiérarchisées en deux niveaux [15]. Un niveau inférieurconstitué des exigences de base (éligibilité, secret, précision, vérifiabilité individuelle, ...)devant être accomplies dans chaque système de vote. Un niveau supérieur (vérifiabilitéuniverselle, Receipt-freeness, résistance à la coercition) regroupe les exigences avancéespour les systèmes de vote.

1.1.4 Définition de quelques concepts sur le vote électronique

1.1.4.1 Résistance à la coercition

La notion de résistance à la coercition a été étudiée dans [13] en vu d’étendre lapropriété de receipt-freeness, puisque pendant que le receipt-freeness protège contre lesattaquants passifs, c’est-à-dire qui ne communiquent pas avec le votant lors du vote,la résistance à la coercition le protège contre les attaquants actifs, c’est-à-dire ceux quipeuvent communiquer avec le votant pendant le processus de vote et l’obliger à faire deschoix contraires à sa volonté.

Un système de vote est dit résistant à la coercition s’il est receipt-freeness et supposequ’aucun attaquant ne doit forcer un électeur à voter d’une manière particulière ou às’abstenir de voter. Il doit être particulièrement difficile pour l’adversaire de déterminersi l’électeur sous la contrainte vote bien comme il le désire. De plus, la résistance à lacoercition doit protéger contre trois principales attaques :

– Attaque par randomisation : ici l’attaquant force le votant à émettre une chainede caractères aléatoires comme son vote avec pour objectif de rendre nul l’intentionde vote avec une grande probabilité. Dans un protocole résistant à la coercition, cevote ne sera pas pris en compte et sera supprimé lors de l’étape de vérificationpuisque le candidat choisi n’est pas valide

– Attaque par abstention forcée : elle consiste pour l’attaquant à contraindre levotant à ne pas émettre de vote.

– Attaque par simulation : ici l’attaquant force le votant à lui révéler les informa-tions qu’il utilise pour voter (crédit anonyme, clés,...) afin de voter à sa place.


1.2. CRYPTOGRAPHIE DU VOTE ÉLECTRONIQUE 10

1.1.4.2 Crédit anonyme

Il permet de prouver une propriété ou un droit lié à son possesseur, sans révélerl’identité de celui-ci. De plus il protège les informations privées de son possesseur enfournissant la propriété d’anonymat. Par ailleurs, il prend souvent la forme d’un jetoncryptographique pouvant être montré par son possesseur à une organisation afin deprouver une propriété liée à son identité. Ce jeton est créé et certifié par une autorité deconfiance qui garantit son authenticité.

1.2 Cryptographie du vote électronique

1.2.1 Services de sécurité d’un système de vote électronique

La cryptographie peut être définie comme étant l’étude des techniques mathéma-tiques utilisées pour la sécurisation de l’information. Le but de cette science est doncd’assurer un certain nombre de services de sécurité parmi lesquels : la confidentialité,l’authentification, la non-répudiation, l’intégrité et l’anonymat.

Un schéma de vote électronique est un système cryptographique qui offre les servicessus-cités :

1.2.1.1 La confidentialité

Elle consiste à garder secret le contenu des votes pendant la phase de vote et à lerendre accessible aux autorités uniquement lors de la phase de décompte. Ce service estlié aux propriétés du secret et du receipt freeness. La confidentialité dans les schémasde vote électronique est assurée par les systèmes de chiffrement.

1.2.1.2 L’authentification

Elle consiste à garantir que l’électeur est bien identifié comme une personne autori-sée à voter et que le vote (message émis) est bien celui d’un membre du groupe d’élec-teurs. Dans les schémas de vote électronique, on distingue généralement deux typesd’authentification :

– L’authentification externe ou identification : elle fournit le lien entre l’électeur etla liste électorale (des électeurs éligibles), elle peut consister en une simple corres-pondance entre le nom de l’électeur et cette liste. Elle peut être réalisée par destechniques symétriques conventionnelles (authentification par mot de passe) oupar des techniques asymétriques (signature,...).

– L’authentification interne : elle est généralement utilisée pour authentifier le votei.e vérifier qu’il s’accompagne d’un crédit valide.



1.2.1.3 L’anonymat

Il permet de dissimuler l’identité de l’électeur lorsqu’il émet son vote. De sorte qu’ilsoit difficile de faire le lien entre un électeur et son vote. Ce service est nécessaire lorsde la phase de vote. L’anonymat est assuré dans les schémas de vote électronique pardes outils tels que les réseaux de mélangeurs, les signatures aveugles,...

1.2.1.4 L’intégrité

De manière générale, l’intégrité (ou intégrité des données) désigne l’état des donnéesqui, lors de leur traitement, de leur conservation ou de leur transmission, ne subissentaucune altération, destruction volontaire ou accidentelle, et conservent un format per-mettant leur utilisation. Elle consiste à garantir qu’un message n’a pas été modifié parune personne autre que son auteur. En ce qui concerne le vote, l’intégrité suppose que latransmission des votes lors de la phase de vote ne doit pas altérer ceux-ci ; ou encore queles résultats du vote ne doivent pas être modifiés (par exemple le contenu des bulletinsne doit pas être modifié lors du décompte). Pour garantir l’intégrité, on utilise des fonc-tions de hachage qui réduisent des données de longueur variable en une " empreinte"de petite taille appelée haché ou condensat. Les exemples de fonctions de hachage sontMD5 (Message Digest numéro 5) et SHA (Secure Hash Algorithm ). Après avoir subi lesattaques, MD5 n’est plus sûr. Il existe aujourd’hui cinq algorithmes de hachage approu-vés par le NIST (National Institute of Standards and Technology) : SHA-1, SHA-224,SHA-256, SHA-384, et SHA-512.

1.2.1.5 La non-répudiation

Elle consiste à garantir qu’un électeur ayant émis son vote ne puisse nier l’avoirfait. De même que les autorités ne puissent nier avoir reçu ce vote. Afin de garantir ceservice, les signatures électroniques sont généralement utilisées.

1.2.2 Primitives cryptographiques

Dans cette partie nous présentons les primitives cryptographiques qui sont utiliséesdans les systèmes de vote électronique pour obtenir ces services de sécurité.

1.2.2.1 Primitives de confidentialité

Le service de confidentialité est assuré dans le vote électronique par le chiffrement.Généralement le plus utilisés étant les systèmes de chiffrement homomorphique.



Chiffrement homomorphiqueSystème très souvent utilisé pour effectuer des opérations sur des données chif-

frées tout en préservant leur confidentialité. Soient M l’espace des messages clairs etC l’espace des textes chiffrés. Soit Enc un schéma de chiffrement défini par les troisalgorithmes suivants :

– Algorithme de génération des clés : prend en entrée les paramètres publics dusystème et renvoie une paire clé publique/clé privée, Pk/Sk ;

– Algorithme de chiffrement (Chiff) : est un algorithme probabiliste qui prend enentrée la clé publique Pk, un messagem dansM et une valeur aléatoire r et renvoieun chiffré c, avec c = Chiff(m, r).

– Algorithme de déchiffrement (Dec) : est un algorithme déterministe qui prend enentrée un chiffré c et la clé secrète Sk de déchiffrement et renvoie le message m ∈M associé à c ∈ C ou un symbole d’erreur avec Dec(c) = m.

Définition 1.2.1. Un algorithme est probabiliste lorsqu’il utilise une source addition-nelle d’aléa. Ainsi, deux chiffrements probabilistes d’un même message donneront desrésultats différents avec une grande probabilité. On parle d’algorithme déterministedans le cas contraire.

Soient ⊕ et ⊗ des lois de groupes dans M et C respectivement.

Définition 1.2.2. Soient M l’espace des textes clairs et C l’espace des chiffrés. Suppo-sons que M et C munis respectivement de ⊕ et ⊗ sont des groupes. Le chiffrement Encest homomorphique si étant donnés deux chiffrés c1 = chiff(m1, r1) et c2 = chiff(m2, r2)

des messages m1 et m2 on a :

c1 ⊗ c2 = chiff(m1 ⊕m2, r)

Dec(c1 ⊗ c2) = Dec(chiff(m1 ⊕m2, r)) = m1 ⊕m2

Notons que les deux lois ⊕ et ⊗ peuvent être identiquesComme cryptosystèmes homomorphiques nous pouvons citer : le chiffrement ElGa-

mal, EC-ElGamal, Paillier,...

Exemple 1.2.1. Système cryptographique ElGamalLe cryptosystème asymétrique ElGamal du nom de son inventeur Taher ElGamal en

1985. La sécurité de ce schéma repose sur le problème du logarithme discret.

a. Algorithme



Génération des clésChaque entité crée la clé publique et la clé privée correspondantea). Engendrer un grand nombre premier p et un générateur g du groupemultiplicatif Z∗p .b). Choisir un entier aléatoire x,1 ≤ x ≤ p− 2 et calculer h = gx (mod p).c). La clé publique est (p, g, h) et la clé privée est x.Bob chiffre un message pour Alice, qu’Alice déchiffre.1.Chiffrement : Bob effectue les actions suivantes :a). Obtenir la clé publique (p, g, h) de Alice.b). Représenter le message m comme un entier m ∈ [0, p− 1].c). Choisir un entier k,1 ≤ k ≤ p− 2

d). Calculer c1 = gk (mod p) et c2 = mhk (mod p).e). Envoyer le texte chiffré c = (c1, c2) à Alice.2.Déchiffrement : Pour récupérer le message Alice procède de la manièresuivante :a). Calculer cp−1−x

1 (mod p) (NB : cp−1−x1 = c−x1 = g−xk)

b). Récupérer m = (c−x1 )c2 (mod p).

b. Propriété homomorphique

Propriété homomorphique multiplicative : le cryptosystème vérifie la propriétéhomomorphique multiplicative :

Preuve. Supposons que nous avons deux chiffrés c1 = (gk1 ,m1hk1) et c2 = (gk2 ,m2h

k2)

des messages m1 et m2. le produit des chiffrés donne :

chiff(m1, k1)chiff(m2, k2) = (gk1 ,m1hk1)(gk2 ,m2h

k2))

= [gk1+k2 , (m1m2)hk1+k2 ]

= chiff(m1m2, k1 + k2)

D’où chiff(m1, k1)chiff(m2, k2) = chiff(m1m2, k1 + k2)

Remarque 1.2.1. Dans les systèmes de vote la propriété homomorphique multiplica-tive du chiffrement est très peu utilisée.

Propriété homomorphique additive : une modification du chiffrement ElGa-mal, appelée ElGamal exponentiel est utilisée dans certains schémas de vote. Le butest de rendre la propriété homomorphique additive. Cette propriété est intéressanteparce qu’elle permet lors du déchiffremment d’obtenir directement les voix de chaquecandidat. Lors de cette modification le message est représenté par gm. Après le chiffre-ment d’un message m avec le chiffrement ElGamal exponentiel, le chiffré est représenté



comme suit :C = (gk, gmhk)

Soient m1 et m2 deux messages chiffrés comme c1 = (gk1 , gm1 hk1) et c2 = (gk2 , gm2 h

k2).Le produit de ces chiffrés donne :

chiff(m1, k1)chiff(m2, k2) = (gk1 , gm1 hk1)(gk2 , gm2 h

k2)

= [gk1+k2 , (gm1+m2)hk1+k2 ]

= chiff(m1 +m2)

Ce qui revient à chiffrer m1 +m2 soit chiff(m1, k1)chiff(m2, k2) = chiff(m1 +m2, k1 + k2)

Exemple 1.2.2. soient (p, g, λ, h) la clé publique, r1, r2, r3 des entiers aléatoire, α =

{0, 1}. Supposons que nous avons trois candidats. Un vote chiffré avec le cryptosys-tème ElGamal exponentiel se représente par (gr1 mod p, gαhr1 mod p), (gr2 mod p, gαhr2

mod p), (gr3 mod p, gαhr3 mod p). Lorsque un électeur choisit de voter pour le secondcandidat alors on a : (gr1 , g0hr1), (gr2 , g1hr2), (gr3 , g0hr3). Le produit de n votes est donnépar (g

∑ni=1 r1i , g

∑ni=1 αih

∑ni=1 r1i), g

∑ni=1 r2i , g

∑ni=1 αih

∑ni=1 r2i), g

∑ni=1 r3i , g

∑ni=1 αih

∑ni=1 r3i)

Après le déchiffrement on obtient g∑n

i=1 αi pour le candidat correspondant i.e. le nombrede voix en faveur de ce candidat.

Rechiffrement

Définition 1.2.3. Une fonction de rechiffrement (Rechiff) : est un mécanisme proba-biliste qui prend en entrée un chiffrement asymétrique probabiliste c = chiff(m, r), unevaleur aléatoire r∗ différente de r qui est utilisé lors du chiffrement et renvoie un chiffréc, avec c = Rechiff(c, r∗). tel qu’on a :

Rechiff(c, r∗) = (chiff(m, r))(chiff(1, r∗)) = chiff(m, r + r∗)

Dec(c) = Dec(Rechiff(c, r∗)) = Dec(c)

Dans le cadre du vote électronique, les opérations de chiffrement et de rechiffrement,sont généralement effectuées par des entités distinctes.

Exemple 1.2.3. Soient Enc un système de chiffrement ElGamal classique où la clépublique est donné par (p, g, h). La fonction de chiffrement renvoie le chiffré c = (c1, c2)

où c1 = gk et c2 = mhk en appliquant la fonction de rechiffrement nous obtenons

Rechiff(c, r∗) = Rechiff(c1, c2, r∗) = (c1, c2)(gr

∗, hr

∗) = (gr+r

∗,mhr+r

∗)



1.2.2.2 Primitives d’anonymat

Les mixnets, les signatures aveugles et le crédit anonyme assurent généralementl’anonymat dans les schémas de vote électronique.

a. MixnetUn mixnet (ou "Mix Network") 5 est un protocole appelé "multiparty computation-

and-communication". Il fournit un mécanisme pour établir un canal de communicationanonyme. Il est l’élément central dans certains systèmes de vote. Le mixnet est une boîtenoire qui prend en entrée un grand nombre de messages (données) et qui a pour but decacher la correspondance entre entrée et sortie. Ce protocole est utilisé pour garantirl’anonymat de l’émetteur du message : on ne sait pas d’où il vient.Il existe deux types basiques de Mixnets : Mixnet à déchiffrement (decryption mixnet,Chaumian mixnet, Onion mixnet) et le Mixnet à rechiffrement (reencryption mixnet)[23].

a.i. Mixnet à déchiffrementEn 1981, Chaum invente le mixnet à déchiffrement. C’est une suite de permutations

appliquées sur des messages chiffrés ; chacune de ces permutations est réalisée par uneentité appelée mixeur (mélangeur). Pour envoyer un paquet m de manière anonyme viaun mixnet, il suffit de chiffrer ce paquet m successivement à l’aide des clés publiques dechaque mixeur. Ainsi à chaque passage par un mixeur, le message chiffré perd une partiede son chiffrement et ensuite il est redirigé vers un autre mixeur pour finir par êtretotalement déchiffré après le dernier mixeur. La Figure 1.1 illustre son fonctionnement.

Soit M , un mixnet qui possède k mixeurs, notés Mi avec 1 ≤ i ≤ k, chacun possé-dant une paire de clés publique et privée (PKi, SKi). Chaque mixeur possède le mêmenombre d’entrées que de sorties et associe à chaque entrée une sortie via une table depermutation.

Initialement chacun des l votes Bj pour j = 1, ..., l est chiffré successivement avecles clés PK1, ..., PKk. Chacun des mélangeurs Mi reçoit l chiffrés partiels de la formeCj = Ei(Ei−1...E1(Bj)). Le mélangeur Mi déchiffre et applique une permutation secrèteaux éléments Cj = Ei−1(Ei−2...E1(Bj)) qu’il envoie au mélangeur suivant Mi−1.

Remarque 1.2.2. Notons que si un seul des mixeurs ne fonctionne pas correctementle message ne sera pas déchiffré. Dans la pratique, les Mixnets à déchiffrement sont trèspeu utilisés dans les schémas de vote électronique.

5. Réseau de mélangeur en Français



Mixnet

MMMA

MMMB

MMMC

MMMD

MMA

MMB

MMC

MMD

MB

MC

MD

MA

B

D

C

A

B

D

C

A

Mixeur Mixeur Mixeur

FIGURE 1.1 – Mixnet de Chaum

a.ii. Mixnet à rechiffrementun autre type de mixnet, appelé Mixnet à rechiffrement : 6 réalise une permutation

(un mélange) sur les messages entrant mais ne les déchiffrent pas. Cependant, pourpermettre l’anonymat, il ne faut pas se contenter de brouiller l’entrée car l’ensemble deschiffrés associé à un message reste alors inchangé, et il est possible dans ce cas retrouverla source du chiffré. Il faut donc que les messages en entrée des mixeurs soient différentsdes messages en sortie. Chaque mixeur rechiffre donc les messages reçus en entrée. Lesystème cryptographique ElGamal permet le rechiffrement d’un message chiffré. 7

La Figure 1.2 illustre le fonctionnement d’un tel mixnet.

Remarque 1.2.3. généralement on utilise la technique du partage de secret (voiresection 1.2.2.5) sur la clé de déchiffrement pour assurer la robustesse [1]. Les mixnetsà rechiffrement sont plus robustes que les mixnets à déchiffrement car le mauvais fonc-tionnement d’un des mixeurs n’altère pas tout le processus.

a.iii. Mixnet vérifiable :Lorsque chacun des mélangeurs est à même de fournir une preuve que ce travail a

bien été effectué (que le mélange a bien été effectué, que les valeurs n’ont pas été modi-fiées, rajoutées ou enlevées), on parle alors de réseaux de mélangeurs universellementvérifiables (mixnets universellement vérifiables).

6. "re-encryption mixnets" en anglais7. i.e. transformer un chiffré en un autre qui conserve le même message (clair) d’origine.



Mixnet

MA

MB

MC

MD

MA MB

MC

MD

MA

Mixeur Mixeur Mixeur

MB

MC

MD

MB

MD

MC

MA

MB

MA

MC

MD

FIGURE 1.2 – Mixnet à rechiffrement

b. Signature aveugleIntroduite en 1982 par Chaum pour assurer l’anonymat en cryptographie. Elle per-

met à un utilisateur de faire signer un message dont le contenu est inconnu au signa-taire. Afin que cet anonymat perdure après la divulgation du message signé, il faudraitque le signataire ne puisse pas relier les signatures finales aux interactions qu’il a euesavec les différents utilisateurs. C’est pourquoi, un protocole de signature aveugle se dé-roule en trois étapes : Tout d’abord, l’utilisateur masque (aveugle) son message avantde l’envoyer au signataire. Cette procédure peut se réaliser de diverses manières avecou sans l’implication du signataire. Ensuite, le signataire signe le message aveuglé qu’ilreçoit et envoie le message signé à l’utilisateur. Pour finir, l’utilisateur désaveugle lemessage signé de sorte qu’il correspond au message initial.

Application : cette méthode, à l’origine conçue pour les protocoles de monnaie élec-tronique, a été utilisée par Fujioka et al en 1993 pour résoudre le problème de validationdes votes sans sacrifier le secret : la signature aveugle permet de remplir les conditionsnécessaires au déroulement légal d’un vote. L’utilisateur (électeur) choisit son vote quireprésente ici son message. Il l’aveugle ensuite en utilisant la première étape d’une si-gnature aveugle. Puis il s’authentifie auprès d’une autorité qui représente le signataire.Ceci lui permet d’émarger et de prouver son éligibilité. L’autorité signe le message aveu-glé et l’utilisateur le désaveugle. Il peut maintenant déposer son vote et la signaturedans l’urne. Ainsi, le système a l’assurance que le vote a été authentifié et est valide sila signature est correcte, et l’autorité est incapable de relier les votes.



c. Crédit anonymeC’est un outil permettant de rendre le vote d’un électeur anonyme.Utilisé pour la première fois dans [13], il offre aux votants un système d’authenti-

fication et d’anonymat. Dans la littérature la génération du crédit s’effectue de deuxmanières :

– Le votant propose son crédit à l’institution de vote [23]– Le votant reçoit ce crédit anonyme de l’institution de vote de manière sûr 8 [13].

Après réception ou émission du crédit, le votant pourra l’attacher à son vote pour s’au-thentifier auprès de l’institution de vote, n assurer que le vote vient bien de lui.

Sa sécurité repose sur le secret entre l’institution et le votant. Il empêche le votantde vendre son vote car il est quasiment impossible de prouver à l’attaquant que le créditanonyme utilisé est valide ou pas. Ce système protège les utilisateurs de la coercitionpuisqu’il est mis en place pour qu’il soit impossible à un attaquant de distinguer unvote associé à un faux crédit d’un vote associé au véritable crédit (i.e celui transmis parl’institution de vote).

Dans la littérature, le crédit anonyme est généralement une chaine de caractèresalphanumériques [13], un mot de vote [23] ou encore une signature [2].

1.2.2.3 Primitives d’intégrité

Fonction de hachageUne fonction de hachageH est une fonction particulière qui, à partir d’une donnée de

taille arbitraire fournie en entrée, calcule une empreinte - appelée le haché - de taille fixe(typiquement, 128, 160 ou 256 bits). Les fonctions de hachage à usage cryptographiquedoivent satisfaire les propriétés suivantes :

1. Sens unique : il est très difficile de trouver le contenu du message à partir de sonempreinte (attaque sur la première pré-image). Autrement dit, étant donné y, ilest difficile de trouver un x tel que H(x) = y en un temps raisonnable.

2. Résistance à une deuxième pré-image : à partir d’un message donné et de sonempreinte, il est très difficile de générer un autre message qui donne la mêmeempreinte (attaque sur la seconde pré-image). Autrement dit, étant donné y =

H(x), il est difficile de trouver en temps raisonnable s 6= x tel que H(s) = y.

3. Résistance aux collisions : il est très difficile de trouver deux messages aléa-toires qui donnent la même empreinte. Autrement dit, il est difficile de trouver xet s (x 6= s) tels que H(x) = H(s) en temps raisonnable.

8. sûr ici signifie que le secret de ce crédit anonyme ne peut être révélé à un individu extérieur à lacommunication.



1.2.2.4 Primitives d’authentification et de vérification

Primitives d’authentificationComme cités ci-dessus les mécanismes d’authentification pour les schémas de vote

électronique sont de deux ordres (interne et externe). Authentification externe (iden-tification) utilise les techniques cryptographiques symétriques (Mot de passe) ou asy-métriques (signatures). En ce qui concerne l’authentification interne, les primitives quiassurent également l’anonymat peuvent être utilisées (signatures aveugles, crédit ano-nyme).

Primitives de vérification ou preuves Elles offrent des fonctionnalités essentiellesparticulièrement utiles pour les schémas de vote où la confidentialité doit être préservée.Dans les schémas de vote, Les preuves généralement rencontrées sont les preuves àdivulgation nulle de connaissance [24].

Une preuve à divulgation nulle de connaissance est un protocole à deux parties entreun prouveur et un vérificateur. Elle permet au prouveur de convaincre le vérificateurqu’il connait un secret, sans le révéler.

En pratique, ce système se présente souvent sous la forme d’un protocole de typedéfie/réponse (challenge-réponse).

Dans les preuves à divulgation nulle de connaissance, on distingue : la preuve àdivulgation nulle de la connaissance d’un logarithme discret, la preuve à divulgationnulle de connaissance d’égalité du logarithme discret, la preuve à divulgation nulle deconnaissance de validité du contenu d’un message chiffré

a. Preuve à divulgation nulle de la connaissance d’un logarithme discretSoit g le générateur du groupe multiplicatif Z∗p d’ordre p. Un prouveur P connait le

logarithme discret de h = gl, soit l. Il souhaite le prouver à un vérificateur sans que cedernier puisse prendre connaissance de l. Cette preuve est généralement réalisée par leprotocole de Schnorr [23].

Protocole de Schnorr

1. Prouveur choisit un nombre aléatoire v (mod p).

2. Prouveur calcule t = gv et envoie cette valeur au Vérificateur.

3. Vérificateur calcule le challenge c = H(g, h, t) où H est une fonction de hachage etenvoie c au prouveur.

4. Prouveur calcule alors r = v − cl (mod p) et l’envoie au Vérificateur.

5. Vérificateur peut maintenant s’assurer que t′ = grhc est bien égal à t. Si tel estle cas, alors le Prouveur a prouvé la connaissance de l sans le communiquer auVérificateur



b. Preuve à divulgation nulle de connaissance d’égalité du logarithme dis-cret

Un prouveur P connait le logarithme discret l tel que x = gl et y = hl. Il souhaitele prouver à un vérificateur sans que ce dernier puisse prendre connaissance de l. Cettepreuve se réalise par le protocole de Chaum-Pedersen [22]. Dans le vote on l’utilise lorsdu Déchiffrement distribué (voir section 1.2.2.6)

c. Preuve à divulgation nulle de connaissance de validité du contenu d’unmessage chiffré

[14] introduit une méthode permettant de savoir si un message m chiffré est valide.Dans les schémas de vote on utilise cette preuve pour garantir l’exactitude du vote

émis i.e. qu’il est le chiffrement du choix d’un candidat valide sans dévoiler celui-ci.

Preuve non-interactive à divulgation nulle de connaissanceL’électeur peut prouver que son vote est correct. Cependant, cette preuve nécessite

une interaction avec le vérificateur, ce qui n’est pas possible en pratique dans un schémade vote. En effet, il faut que toute entité puisse vérifier que le vote est correct. Ainsi, ilest nécessaire de rendre cette preuve non interactive. Pour cela, on utilise le résultatde Fiat et Shamir qui permet de remplacer l’interaction avec le vérificateur par unefonction de hachage.

1.2.2.5 Partage de secret

En 1979, Shamir invente l’idée du partage de clé secrète 9. Cette idée repose sur lareconstruction de l’équation d’un polynôme grâce à la connaissance d’un certain nombrede ses points. Ceci par l’interpolation de Lagrange qui stipule que la connaissance de npoints d’un polynôme de degré t − 1 permet de reconstruire l’équation de ce polynôme(voir Figure 1.3).

Distribution des parts Soit D une entité de confiance, appelée dealer pour partagerun secret s à n entités nommées Pi, D va créer f(x) un polynôme aléatoire de degrét− 1 < n, tel que f(0) = s.

f(x) = s+t∑i=1

aixi (1.1)

Pour tout i ∈ [1, n], D calcule n points de son polynôme :

(xi, yi) = (i, f(i)) (1.2)

9. secret sharing en anglais



et va envoyer ∀i, le point (xi, yi) à l’entité Pi. Chaque entité Pi possède donc un point d’unpolynôme de degré t− 1.

Reconstruction du secret Si t entités parmi les n coopèrent, ils peuvent reconstruirel’équation du polynôme par l’interpolation de Lagrange. Il apparait évident que s’ils ontl’équation du polynôme cela implique qu’ils ont la valeur de la clé secrète, Cette clé se-crète est la valeur du polynôme f(x) pour x = 0.

– Supposons la connaissance de n points : (x1, y1), (x2, y2), ..., (xn, yn),d’un polynôme de degré t− 1, noté f(x).

– Les polynômes de Lagrange associés à chaque point peuvent êtrecalculés comme suit :

li(x) =t∏

j=1,j 6=i

x− xixj − xi

(1.3)

– Le polynôme d’interpolation :

f(x) =∑i

yi.li(x) (1.4)

est le seul polynôme de degré t− 1 (au plus) passant par tous cesn points.

– La valeur de s = f(0) est calculée comme suit :

s = f(0) =t∑i

yi

(t∏

j=1,j 6=i

xixi − xj

)(1.5)

FIGURE 1.3 – Interpolation de Lagrange

Si par contre t− 1 entités coopèrent, elles ne peuvent pas reconstruire ce polynôme.la technique décrite est appelée partage de secret à seuil (t, n). Où t est le seuil c’est

à dire le nombre minimum d’entités qui doivent coopérer pour retrouver le secret.Dans le contexte du vote électronique, on l’utilise d’une part dans la construction des

systèmes cryptographiques à seuil (voire section 1.2.2.6) et d’autre part dans les Mixnetsoù on partage la clé privée (utilisée pour le déchiffrement) pour assurer la Robustessedu système [1].

1.2.2.6 Systèmes cryptographiques distribués

Définition des cryptosystèmes distribuésLa sécurité de la clé privée est faible si elle est détenue par une entité. Il serait in-

téressant de partager cette clé à plusieurs entités de manière à ce qu’il soit impossible



pour une seule de déchiffrer un message.Un cryptosystème est dit distribué (Threshold cryptosystem) si pour déchiffrer un mes-sage chiffré, plusieurs entités sont nécessaires.La technique pour le réaliser utilise leprincipe du Partage de secret ( section 1.2.2.5). On publie une clé publique et on partagela clé privée entre différentes entités. Ainsi lorsque, le cryptosystème est dit distribuéà seuil t de n, seules t entités sur n (t < n) sont nécessaires pour déchiffrer correctementle message.

Cryptosystème ElGamal distribuéUn cryptosystème à seuil est composé d’un protocole de génération de clés et d’un Proto-cole de déchiffrement distribué. Nous présentons le Cryptosystème ElGamal distribué.Le protocole de génération des clés a été initialement proposé par Pedersen. la versiondécrite ici est une simplification du schéma de Pedersen donné par Gennaro et al dans[8]. Le Protocole de déchiffrement distribué quant à lui provient de Cramer et al.

a. Génération de clésAvant de générer les clés, les autorités définissent conjointement les paramètres du

système (p, g, y). Pour cela elles utilisent un algorithme qui produit ces clés de manièrecoopérative.

Cette méthode consiste à permettre à un groupe d’autorités de coopérer pour générerun secret, sans l’aide d’une entité de confiance, comme l’était le dealer.

Pedersen dans [9] propose de faire de chacune des n autorités un dealer : Chacunedes entités Pi choisit un secret si, un polynôme fi(x) de degré t − 1 tel que fi(0) = si etva calculer des points de son polynôme pour les distribuer aux autres entités. La partde secret d’une entité Pi sera alors calculée comme étant la somme des points qui lui ontété envoyés.

Lors de l’élaboration des clés publiques et privées, un certain nombre d’autoritésparticipant à l’élaboration de la clé sont défaillantes et peuvent transmettre des infor-mations incorrectes aux autres entités. Le protocole de génération de clé distribué sedoit donc d’utiliser un système permettant de vérifier que les informations transmisessont cohérentes. D’où l’utilisation lors du partage du protocole de partage de secret véri-fiable de Feldman 10.La Figure 1.4 illustre le protocole de génération de clé vérifiable de Pedersen.

N.B : nous ne présentons pas l’algorithme de chiffrement parce qu’il est identique àcelui du chiffrement ElGamal classique de la section (1.2.1)

10. Feldman’s verifiable secret sharing (VSS) protocol en anglais.



Protocole de génération de clé

1. Chaque autorité Ai choisit un polynôme aléatoire fi(x) de degré t−1 dans Zq[x].

fi(x) = ai0 + ai1x+ ...+ ait−1xt−1 (1.6)

où fi(0) = ai0 = xi et yi = Xi0 = gxi . Ai, diffuse Xik = gaik pour k = 0, ..., t − 1.Chaque autorité Ai calcule et envoie de manière privée la part secrète sij àl’autorité Aj :

sij = fi(j) pourj = 1, ..., n (1.7)

2. Chaque autorité Aj vérifie si :

gsij =t−1∏k=0

(Xik)jk (1.8)

Si cette égalité n’est pas vérifiée alors l’autorité Aj diffuse une plainte contreAi.

3. Chaque autorité Ai qui en tant que dealer a reçu une plainte de Aj diffuse lesvaleurs sij qui satisfont l’équation (1.8).

4. L’autorité Ai est disqualifiée si :– plus de t− 1 autorités se plaignent d’une autorité Ai,– une des parts secrète révélée sij ne permet pas de vérifier l’équation (1.8),Par convention [9], les parts secrètes partagées par l’autorité disqualifiée serontmises à xi = 0 et yi = 1.

5. chaque autorité peut définir Q comme l’ensemble des autorités non disquali-fiées.

6. Chaque autorité Ai non-disqualifiée calcule sa part du secret comme étant :

si =∑j∈Q

sji (1.9)

7. La clé publique y est calculée comme suit :

y =∏i

yi (1.10)

8. La clé privée partagée x ne peut être calculée par une seule entité mais peutêtre représentée par :

x =∑i

xi (1.11)

FIGURE 1.4 – Protocole de génération de clé distribuée de Pedersen

b. Déchiffrement distribuéDans [6], Cramer et al propose un protocole de déchiffrement distribuée tel que



présenté à la Figure 1.5. Les entités déchiffrent ensemble le message chiffré (c1, c2) =

(gr, hrm), avec m ∈ Gq.

Protocole de déchiffrement distribué

1. Pour chaque part secrète si de x, on note ρi l’engagement envers si :

ρi = gsi

Chaque autorité Pj peut calculer l’engagement ρi de la manière sui-vante :

ρi =n∏j=1

gsji =n∏j=1

(yj

t∏l=1

X il

jl)

2. Chaque autorité Pi calcule son déchiffrement partiel wi = c1si et le dif-

fuse accompagné d’une preuve à divulgation nulle de connaissance que :

loggρi = logc1wj

Notons que prouver cette égalité revient à prouver que le déchiffrementpartiel a bien été réalisé à l’aide de la part secrète si. Cette preuve estune preuve d’égalité du logarithme discret expliquée en section 1.2.2.4.

3. Pour tout sous-ensemble ∆ à t entités dont la preuve d’égalité est valide,le message d’origine peut être retrouvé en utilisant l’interpolation deLagrange :

m =c2∏

i∈∆wλj,∆i

où :λi,∆ =

∏l∈∆|{i}

l

l − i

FIGURE 1.5 – Protocole de déchiffrement distribué

Ce protocole est vérifiable étant donné que chaque étape peut être refaite et vérifiée.


1.3. COURBES ELLIPTIQUES 25

1.2.3 Propriétés du vote et lien cryptographique

Dans cette partie nous faisons un récapitulatif des différentes propriétés du vote élec-tronique, le lien avec les services de sécurité et les primitives cryptographiques utiliséespour les assurer.

TABLEAU 1.1 – Tableau récapitulatif des propriétés d’un e-vote et lien cryptographique

Propriétés d’un e-vote Services de sécurité Primitives cryptographiques Exemples de primitivesSecret des votes Confidentialité Chiffrement homomorphique ElGamal, Paillier,...Receipt-freenes RechiffrementÉligibilité Authentification Technique symétrique Mot de passe

Technique asymétrique SignaturePrécision Intégrité Fonction de hachage SHA

Non répudiation Signature ElGamalMixnet Déchiffrement

Secret des votes Anonymat RechiffrementSignature aveugle RSA

Confidentialité Chaine de caractèresRésistance à la coercition Crédit anonyme Mot de vote

Anonymat SignatureVérifiabilité individuelle Preuves ValiditéVérifiabilité universelle Chaum Pedersen

1.3 Courbes elliptiques

L’objectif de ce travail est d’élaborer un système de vote électronique dont la sécu-rité s’appuie sur les cryptosystèmes construits sur les courbes elliptiques. Il importede faire une brève présentation de celles-ci. Notons que certaines démonstrations ma-thématiques ne seront pas détaillées. Le lecteur voulant obtenir plus de détails pourraconsulter [11].

Historiquement, les courbes elliptiques sont apparues dans la résolution de nom-breux problèmes bien avant la naissance de la cryptographie à clé publique. De nom-breux problèmes de gravitation ou d’électromagnétisme ont par exemple été résolus pardes calculs d’intégrales elliptiques ; on en retrouve en particulier dans des travaux d’Eu-ler et de Gauss. Mais les courbes elliptiques interviennent aussi dans la résolution denombreux problèmes en théorie des nombres.

1.3.1 Courbes elliptiques définies sur un corps quelconque

Définition 1.3.1. Soit k un corps, on appelle équation de Weierstrass sur k une équa-tion de la forme :

E : y2 + a1xy + a3y = x3 + a2x2 + a4x+ a6 (1.12)

avecai ∈ k. Cette équation est celle d’une courbe. Une courbe donnée par une telle équa-tion est dite lisse ou non singulière si le système d’équation suivant n’admet pas desolution



{a1y = 3x2 + 2a2x+ a4

2y + a1x+ a3 = 0

Autrement dit si les dérivés partielles en x et en y de

f(x, y) = y2 + a1xy + a3y − x3 − a2x2 − a4x− a6

ne s’annulent pas simultanément.

Définition 1.3.2. Soit k un corps, une courbe elliptique E définie sur k est une courbelisse définie par l’équation de Weierstrass :

E : y2 + a1xy + a3y = x3 + a2x2 + a4x+ a6 (1.13)

où ai ∈ k

La figure 1.6(a) représente la courbe elliptique définie par l’équation y2+y = x3−7x+6

sur R. La figure 1.6(b) illustre la courbe définie par y2 = x3 − 3x+ 4 sur R.

(a) Courbe elliptique d’équation y2+y = x3−7x+6 (b) Courbe elliptique d’équation y2 = x3 − 3x+ 4

FIGURE 1.6 – Courbes elliptiques définies sur le corps R

Nous pouvons définir E(k)

Définition 1.3.3. L’ensemble des points k-rationnels d’une courbe elliptique définiesur un corps k et noté E(k) est donné par :

E(k) = {(x, y) ∈ K ×K | y2 + a1xy + a3y = x3 + a2x2 + a4x+ a6} ∪ O

où O est un point k-rationnel appelé point à l’infini.

Remarque 1.3.1. Sur la définition de la courbe



la courbe E est définie sur k parce-que les coefficients ai de l’équation (1.13) sont deséléments de k. Notons que si E est définie sur k, alors E est également définie sur touteextension de k

Définition 1.3.4. Soit E une courbe elliptique. Vérifier que la courbe est non singu-lière peut se faire algébriquement en calculant ∆ le discriminant de E donné par lesquantités suivantes :∆ = −b2

2b8 − 8b34 − 27b2

6 + 9b2b4b6

où b2 = a21 + 4a2

b4 = 2a4 + a1a3

b6 = a33 + 4a6

b8 = a21a6 + 4a2a6 − a1a3a4 + a2a

23 − a2

4

c4 = b22 − 24b4

c6 = −b32 + 36b2b4 − 216b6

Théorème 1.3.1. Soit E une courbe donnée par une équation de Weierstrass. Alors Eest non singulière (lisse) si et seulement si ∆ 6= 0.

Définition 1.3.5. Lorsque ∆ 6= 0, la notion d’Invariant j de la courbe est définie par :

j(E) =c3

4

∆

Théorème 1.3.2. Soit k un corps de caractéristique p. Deux courbes données par leurséquations de Weierstrass dont ∆ 6= 0 sont isomorphes si elles ont le même j-invariant. Laréciproque est vraie si k est un corps algébriquement clos.

Preuve. Pour la preuve voir [12]Soit p la caractéristique du corps k ; si p 6= 2, 3 alors en faisant des changements

de variables successifs, l’équation (1.13) peut être ramené à une équation réduite de laforme :

E : y2 = x3 + ax+ b avec ∆ = −16(4a3 + 27b2) 6= 0.

Loi de groupe

Définition 1.3.6. Soit E une courbe elliptique définie sur un corps k , soient P et Qdeux points de E(k).

1. Si P et Q sont deux points distincts, et L, la droite passant par P et Q, Il existeun unique troisième point R qui est le point d’intersection entre L et E. Soit L∗ ladroite verticale passant par R. Le symétrique de R par rapport à l’axe des abscissesest le point P +Q ∈ E(k).

2. Si P et Q sont confondus, on définit L, la tangente à la courbe E qui passe parP . Il existe un unique troisième point R qui est le point d’intersection entre L et



E. Le symétrique de R par rapport à l’axe des abscisses [2]P ∈ E(k) appelé Ledoublement de P .

(a) Addition P +Q avec P 6= Q (b) Doublement P +Q avec P = Q

FIGURE 1.7 – Addition et doublement d’un point

Remarque 1.3.2. Cas particulier :

(a) Addition P +Q+O = O (b) Doublement P + P +O = O

FIGURE 1.8 – cas particulier d’addition et doublement

Théorème 1.3.3. la loi + précédente définit une structure de groupe commutatif sur E,ayant O comme élément neutre.

Preuve.

1. La loi+ est associative soient P,Q,R ∈ E : (P +Q) +R = P + (Q+R)

2. La loi + est commutative soient P,Q ∈ E alors P +Q = Q+ P

3. Il existe un point O ∈ E tel que O + P = P +O = P

4. Pour tout élément P ∈ E ,−P ∈ E tel que P +−P = −P + P = O



La démonstration mathématique de ces différents points est détaillée dans [12].Les formules algébriques pour cette loi de groupe dérivent de cette description géo-

métrique [11].

Formules algébriques pour la loi de groupe Lorsque la caractéristique du corpsest différente de 2 ou 3 les formules algébriques pour cette loi de groupe sont les sui-vantes :

l’opposé d’un point P = (x, y) ∈ E(k) est donné par le point −P = (x,−y) ∈ E(k).Les formules d’addition et de doublement sur k sont les suivantes. soient P,Q ∈ E(k) oùP = (x1, y1) et Q = (x2, y2) :

1. si P 6= ±Q alors P +Q = (x3, y3) avec :x3 = ( y2−y1

x2−x1)2 − x1 − x2

y3 = (x1 − x3)( y2−y1

x2−x1)− y1

2. si P = Q alors 2P = (x3, y3) avec :x3 = (3x2

1+a

2y1)2− 2x1

y3 = (x1 − x3)(3x2

1+a

2y1)− y1

En cryptographiques on s’intéresse surtout aux courbes elliptiques définies sur descorps finis (par exemple Fp, avec p 6=2,3), puisque le cardinal de ces courbes est connu etles calculs sont plus aisés.

1.3.2 Courbes elliptiques définies sur un corps fini

Lorsque le corps est fini la courbe n’est pas dans un espace continue. Sa représenta-tion est constituée d’un ensemble de points discrets (Figure 1.9)

(a) Courbe elliptique d’équation y2 = x3 + 2x + 3sur F997

(b) Courbe elliptique d’équation y2 = x3 + 10x + 4sur F13

FIGURE 1.9 – Courbes elliptiques définies sur les corps Fq



Nombre de points d’une courbe elliptique définie sur un corps finiSoit E une courbe elliptique définie sur Fq, q = pm où p est la caractéristique du corps

Fq et m ∈ N∗ . On note #E(Fq) le nombre de points de E(Fq). #E(Fq) est appelé l’ordredu groupe des points de E sur le corps fini Fq [11]. Le théorème de Hasse donne uneapproximation du nombre de points de E(Fq). Ce théorème est très important en cryp-tographie étant donné que compter les points d’une courbe elliptique est indispensabledans la recherche des courbes sures pour la cryptographie (voir section 1.3.6.1).

Remarque 1.3.3. Soit E(Fq) une courbe donnée par l’équation de Weierstrass (1.13),cette équation a au plus deux solutions pour chaque choix de x dans Fq, on peut doncdire que : #E(Fq) ≤ 2q + 1

Théorème 1.3.4. (Hasse) Soit E une courbe elliptique définie sur Fq, alors #E(Fq) =

q + 1− t avec |t| ≤ 2√q

Preuve. La démonstration de ce théorème est donnée dans [12].

Corollaire 1.3.1. |#E(Fq)− (q + 1)| ≤ 2√q

Définition 1.3.7 (Ordre d’un point). Soit P un élément du groupe formé des pointsd’une courbes E définie sur Fq, l’ordre de P est le plus petit entier n tel que [n]P = O.

Remarque 1.3.4. On note 〈P 〉 l’ensemble des points engendrés par P i.e. [i]P ; 0 ≤ i ≤ n− 1

où n est l’ordre de P . L’ensemble 〈P 〉 forme un sous-groupe cyclique de E(Fq) engendrépar P .

Exemple 1.3.1. Soit E une courbe elliptique définie sur le corps F23 d’équation y2 =

x3 − 2x− 1. L’ensemble des points de cette courbe est représenté dans le tableau 1.2

TABLEAU 1.2 – Points de la courbe d’équation y2 = x3 − 2x− 1 mod 23

Point Ordre Point Ordre Point Ordre Point OrdreO 1 (8, 9) 14 (13, 13) 28 (19, 9) 28(2, 7) 7 (8, 14) 14 (14, 1) 28 (19,14) 28(2,16) 7 (10, 6) 28 (14, 22) 28 (20, 1) 28(4, 3) 28 (10, 17) 28 (15, 3) 14 (20, 22) 28(4, 20) 28 (12, 1) 7 (15, 20) 14 (21, 8) 4(7, 11) 14 (12, 22) 7 (17, 5) 7 (21, 15) 4(7, 12) 14 (13, 10) 28 (17,18) 7 (22, 0) 2

– Le point (4, 3) comme tous les points d’ordre 28 sont les générateurs du sous-grouped’ordre maximal de la courbe d’équation y2 = x3 − 2x− 1.

– Le point (7, 11) est un générateur d’un sous-groupe différent de celui qui précèdeet d’ordre 14.

– L’ordre de la courbe #E(F23) est 28.– L’ordre des points de la courbe est un facteur de l’ordre de la courbe. Dans cet

exemple, les ordres 14, 7, 4, 2 sont des facteurs de 28.



Généralement, on va choisir des courbes sur Fq telles que #E(Fq) = hp avec h petitappelé cofacteur et p un grand nombre premier.

1.3.3 Problème du logarithme discret sur les courbes elliptiques

Nous avons une définition générale des courbes elliptiques, ainsi que des formulesd’addition et de doublement. Dans cette partie, nous rappelons le problème du loga-rithme discret, et voir son application sur les courbes elliptiques.

Nous avons vu que le groupe formé par l’ensemble des points d’une courbe est ungroupe abélien fini. De manière analogue au problème du logarithme discret sur ungroupe multiplicatif, on peut définir le problème du logarithme discret sur les courbeselliptiques (ECDLP : Elliptic Curve Discrete Logarithm Problem).

Définition 1.3.8 (Problème du Logarithme Discret sur les courbes elliptiques). SoientE une courbe elliptique définie sur un corps fini (Fp), 〈P 〉 un sous-groupe cyclique deE(Fp) d’ordre premier n engendré par le point P et un point Q ∈ 〈P 〉, chercher l’entierk ∈ [0, n− 1] tel que Q = [k]P . L’entier k est le logarithme discret de Q en base P .

La difficulté du Problème du Logarithme Discret sur les courbes elliptiques est es-sentielle pour la sécurité des systèmes cryptographiques construis sur les courbes ellip-tiques.

1.3.4 Multiplication scalaire

Comme nous venons de le voir, la cryptographie sur les courbes elliptiques repose surle problème du logarithme discret sur un groupe formé des points de la courbe.

Définition 1.3.9. Soient E une courbe elliptique définie sur Fq, P un point de E(Fq) etk ∈ Z. La multiplication scalaire, notée [k]P , est la fonction définie comme suit :

E(Fp)× Z −→ E(Fp)(P, k) 7−→ [k]P = P + P + ...+ P︸︷︷︸

k fois

avec [0]P = O et [k]P = [−k] (−P )

1.3.5 Les systèmes cryptographiques utilisant les courbes ellip-tiques

Soit E une courbe elliptique définie sur Fp. Soit P un générateur de E(Fp), supposonsque l’ordre du point P est le nombre premier n. Alors le sous-groupe cyclique de E(Fp)généré par P est :〈P 〉 = {O, P, [2]P, ..., [n− 1]P} ⊆ E(Fp) avec [n]P = O.Afin de concevoir un cryptosystéme sur les courbes elliptiques la fonction à calculer estla multiplication scalaire de ce point P par k. Cette fonction est dite « à sens unique » :



connaissant l’entier k et le point P , il est facile de calculer Q = [k]P mais connaissantQ et P il est difficile de retrouver k. La sécurité de ce cryptosystème repose donc surle problème du logarithme discret sur les courbes elliptiques (Elliptic Curve DiscreteLogarithm Problem, ECDLP).

1.3.5.1 Le Cryptosystème ElGamal elliptique

Supposons que Bob souhaite envoyer un message à Alice sous forme chiffré de sorteque Alice soit la seule à pouvoir le déchiffrer.

Génération des clésChaque entité crée la clé publique et la clé privée correspondantea). Choisir une courbe elliptique E définie sur Fp et un point primitif P deE(Fp) d’orde q,b). Choisir un entier aléatoire d ∈ [1, q − 1] et calculer Q = [d]P .c). La clé publique est (E,P,Q) , clé privée= d

Bob chiffre un message m pour Alice, qu’Alice déchiffre.1.Chiffrement : Bob effectue les actions suivantes :a). Obtenir la clé publique (E,P,Q) de Alice.b). Représenter le message m comme un élément de m ∈ E(Fp),c). Choisir aléatoirement un entier k ∈ [1, q − 1]

d). Calculer c1 = [k]P et c2 = [k]Q+m.e). Envoyer le texte chiffré c = (c1, c2) à Alice.2.Déchiffrement : Pour récupérer le message Alice procède de la manièresuivante :calcul m = c2 − [d] c1.

Il est facile de vérifier que la phase de déchiffrement permet de retrouver le messageclair. En effet, c2 − [d] c1 = ([k]Q+m)− [dk]P = ([kd]P +m)− ([kd]P ) = m

RechiffrementLe système de chiffrement ElGamal elliptique offre la propriété de rechiffrement :– Choisir un entier aléatoire s, 1 ≤ s ≤ n− 1

– Modifier le chiffré avec c1′= c1 + [s]P et c2

′= c2 + [s]Q

Nous remarquons que ce processus modifie le chiffré mais préserve le message en clair.

Rechiff (chiff(m, k), s) = (chiff (m, k) + chiff (1, s))

= ([k]P + [s]P,m+ [k]Q+ [s]Q)

= ([k + s]P,m+ [k + s]Q)



Propriété homomorphiqueCe cryptosystème admet une propriété homomorphique additive :Supposons que nous avons deux chiffrés c1 = ([k1]P,m1 + k1([d]P )) et c2 = ([k2]P,m2 + k2([d]P ))

des messages m1 et m2

chiff (m1, k1) + chiff (m2, k2) = ([k1]P,m1 + k1([d]P )) + ([k2]P,m2 + k2([d]P ))

= ([k1 + k2]P, (m1 +m2) + [k1 + k2] ([d]P ))

= chiff (m1 +m2, (k1 + k2))

1.3.5.2 Le Protocole d’échange de clés de Diffie-Hellman

DescriptionSupposons que Alice et Bob, souhaitent partager un secret commun K. Pour cela ils

utilisent comme moyen de communication un canal non sécurisé où l’information peutêtre intercepté.Pour ce partage, ils s’entendent sur le choix d’une courbe elliptique E définie sur Fp etun point primitif P de E(Fp) d’ordre n.Alice choisit sécrètement a ε [1, n− 1], calcule A = [a]P mod p et transmet A à Bob.Bob choisit sécrètement b ε [1, n− 1], calcule B = [b]P mod p et transmet B à Alice.À la réception Alice peut calculer [a]B mod p et bob peut calculer [b]A mod p et onobtient la clé secrète commune K avec :K = [ab]P = [a]B = [b]A

paramètres publics : une courbe elliptique E définie sur Fpun générateur P d’ordre n

secrets a, b ε [1, n− 1]

Alice Bob

choisit a ε [1, n− 1] choisit b ε [1, n− 1]

calcul A = [a]P mod p

A−→calcul B = [b]P mod p

B←−K = [ab]P = [a]B K = [ba]P = [b]A

1.3.6 Sécurité et choix des courbes elliptiques pour la cryptogra-phie

L’un des principaux avantages de l’utilisation des cryptosystèmes sur les courbeselliptiques est qu’ils utilisent des clés (en bit) de petites tailles. Alors que pour le même



niveau de sécurité le système cryptographique RSA utilise des clés environ 6 fois pluslongues.

Le tableau 1.3 représente le nombre de bits en taille des clés pour RSA et pour lesystème cryptographique basé sur les courbes elliptiques pour un niveau de sécuritééquivalent.

TABLEAU 1.3 – Tableau comparatif des tailles de clés de ElGamal(nombre), RSA etElGamal(ECC)

Niveau de sécurité ( bits) Taille minimum des clés ( bits)ElGamal(nombre) RSA ElGamal(ECC)

80 1024 1024 160112 2048 2048 224128 3072 3072 256192 7680 7680 384256 15360 15360 512

La force des cryptosystèmes sur courbes elliptiques par rapport à ceux sur les nombres(RSA, ElGamal) est la difficulté de résoudre le problème du logarithme discret sur legroupe formé des points de cette courbe elliptique. Ces groupes sont beaucoup moinsconnus et surtout différents d’une courbe à l’autre.

1.3.6.1 Choix d’une courbe pour la cryptographie et du point générateur

Choix de la courbeEn général il existe une multitude d’algorithme pour choisir une courbe elliptique

sûre en cryptographie. Dans ce document nous ne présentons qu’un seul :

1. Choisir un grand nombre premier p qui sera la caractéristique du corps.

2. Choisir de manière aléatoire les coefficients a et b et définir l’équation de la courbeE : y2 = x3 + ax+ b.

3. Déterminer l’ordre de la courbe #E(Fp).

4. Vérifier que :

– #E(Fp) ne divise pas pk − 1 pour tout k ≤ (log p)2. En pratique utilisé k ≤ 20 .– #E(Fp) 6= p

5. Vérifier que #E(Fp) est divisible par un nombre premier n suffisamment grandn > 2160

6. Vérifier que le grand nombre premier n qui divise #E(Fp), ne divise pas pk − 1



Choix de point générateurAprès avoir choisi la courbe elliptique, il est indispensable de déterminer le point G,

générateur du sous-groupe dont l’ordre est le plus grand facteur premier de #E(Fp).

1. Choisir de manière aléatoire un point G ∈ E(Fp) et le plus grand nombre premiern qui divise #E(Fp).

2. Vérifier que [n]G = O i.e. n est l’ordre de G

Le NIST publie des paramètres standards à donner aux courbes pour leurs effica-cités. L’une des courbes recommandées est la courbe P-192 sur le corps fini (Fp) avecp = 2192− 264− 1. Notons que Gx et Gy représentent les coordonnées en x et y du point debase G d’ordre n.

p = 6277101735386680763835789423207666416083908700390324961279

La courbe E d’équation y2 = x3 − 3x+ b sur (Fp) est donnée par :

b = 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1

Gx = 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012

Gy = 07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811

n = FFFFFFFF FFFFFFFF FFFFFFFF 99DEF836 146BC9B1 B4D22831


CHAPITRE 2

PRÉSENTATION DE QUELQUESSCHÉMAS DE VOTE

ÉLECTRONIQUE

Trois approches dominent la littérature scientifique concernant l’élaboration des sché-mas de vote électronique. Plusieurs méthodes sont basées sur les mixnets introduits parDavid Chaum. Ensuite d’autres méthodes se basent sur les signatures aveugles propo-sées par Chaum. Enfin les méthodes basées sur le chiffrement homomorphique. Dansce chapitre nous présentons deux schémas de vote électronique : le premier construitsur les mixnets et proposé par Juels et al, le dernier proposé par Porkodi et basé sur lesystème de chiffrement homomorphique (ElGamal elliptique).

2.1 Schéma de Juels, Catalano et Jakobsson

Ce schéma de vote est le premier à fournir la propriété de résistance à la coercition.Il utilise les canaux anonymes tels que les mixnets (voire Section 1.2.2.2) et introduit lanotion de crédit anonyme.

2.1.1 Principe

L’idée principale de ce schéma de vote est de protéger le votant d’attaques éventuellesen lui permettant d’attacher à son vote un crédit anonyme non valide. Le système devradonc agir de la même manière avec le votant, qu’il reçoive un crédit anonyme valide ounon. Ainsi, l’attaquant reste dans le doute face au votant : « A-t-il utilisé le bon créditanonyme ? Ou non ? ». Ce schéma permet également au votant d’effectuer des votes mul-tiples, le dernier vote émis est celui qui est considéré lors du décompte final. Il utilise :

– Le système cryptographique ElGamal (voire Section 1.2.1) pour ses propriétés dechiffrement et de rechiffrement.

– Les preuves non interactives à divulgation nulle de connaissance,– Les mixnets à rechiffrement.


2.1. SCHÉMA DE JUELS, CATALANO ET JAKOBSSON 37

La supposition selon laquelle la phase d’enregistrement est inattaquable est faite dansce schéma.

2.1.2 Fonctionnement

Phase de configuration Les paires de clés (SKR, PKR) et (SKT , PKT ) sont généréespour les autorités d’enregistrement et celles du décompte. Ces clés publiques PKR,PKT

sont publiées de même que les paramètres du système.

Phase d’enregistrement Les autorités d’enregistrement R vérifient l’éligibilité dechaque votant Vi, génèrent et transmettent à Vi un crédit anonyme. Ils publient sur lestableaux publics l’identifiant du votant, IDi à côté de son crédit anonyme chiffré à l’aidede la clé publique PKT . Soit L la liste électorale. L est conservé dans BB contenant tousles crédits anonymes chiffrés publiés par les autorités dans BB

Pour l’illustration voir Figure (2.1)

FIGURE 2.1 – Phase d’enregistrement du schéma de Juels et al

Phase de vote Le votant Vi transmet son vote vi qui sera publié sur le tableau de votepublique. Ce bulletin de vote est composé d’un crédit anonyme chiffré, du vote chiffréà l’aide de la clé publique PKT et d’une preuve de validité montrant que le vote chiffréreprésente le chiffrement d’un candidat valide. Il faut noter que le chiffrement du créditanonyme effectué par le votant n’est pas le même que celui effectué par R. En effet, lechiffrement ElGamal est un chiffrement probabiliste.




FIGURE 2.2 – Phase de vote du schéma de Juels et al

Phase de décompte Les autorités chargées du décompte Tj effectuent les actionssuivantes :

1. Vérification que toutes les preuves contenues dans BB sont correctes. Tout voteayant une preuve invalide est éliminé. Soit A1 et B1 les liste contenant les chiffrésde candidat et crédit respectivement.

2. Élimination des double vote. Pour éliminer les doublons, il applique un test d’éga-lité (PET) sur chaque paire de chiffré contenue dans B1 et supprime les entréesoù les valeurs sont identiques. Soient A2 et B2 les chiffrés (vote et crédit anonyme)restants.

3. MélangerA2 etB2 à l’aide d’un mixnet qui renvoieA3 etB3. La liste L est égalementmixée et on obtient L′.

4. Comparer des crédits anonymes de la liste L′ avec ceux de la liste B3, éliminationdes votes si le crédit anonyme chiffré dans B3 ne correspond à aucun élément de laliste L′ (voir Section 2.1.3). A4 est le vecteur de vote valide.

5. déchiffrer A4 et décompter les voix pour publier le résultat de l’élection.




FIGURE 2.3 – Phase de décompte du schéma de Juels et al

2.1.3 Vérification du crédit anonyme

Deux chiffrements d’un même crédit anonyme sont différents l’un de l’autre (le chif-frement ElGamal est probabiliste), il faut mettre en place une technique de comparaisonde crédit anonyme de telle manière que les autorités de vote ne puissent avoir accès aucontenu du crédit anonyme (déchiffré). Si le contenu de ce crédit est accessible à une au-torité de vote, alors cette autorité de vote peut lever l’anonymat du vote de cet électeur.

Pour pallier ce problème, le schéma de vote de Juels et al utilise un « test d’égalitéde messages orignaux ou message en clair » (PET, Plaintext Equality Test). Ce test estune fonction qui prend en entrée deux chiffrés réalisés par le système de chiffrementElGamal 1 et retourne le chiffré de 1 si les messages chiffrés sont égaux et celui de 0dans le cas contraire.

Exemple 2.1.1. Supposons c1 = (x1, y1) = (gr1 , hr1m1) et c2 = (x2, y2) = (gr2 , hr2m2)

deux chiffrés. PET prend c1 et c2 et calcule c3 = (x3, y3) = (gr3 , hr3m3) = (x1

x2, y1

y2) =

(g(r1−r2), h(r1−r2)m1

m2) si m1 = m2, alors m1

m2= m3 = 1. Après ce test, il suffit à Tj de déchiffrer

c3 = (x3, y3). Si le résultat du déchiffrement est 1 alors c1 et c2 sont des chiffrements d’unmême message. Ainsi Tj vérifie la validité du crédit mais n’a aucune idée sur le véritablecrédit anonyme voir [24].

Nous donnons l’illustration graphique du schéma complet à la Figure (2.4). Notonsque les numéros 1,2,3 représentent les actions menées lors des différentes phases (1pour l’enregistrement, 2 pour le vote, 3 pour le décompte).

2.1.4 Analyse

Propriétés respectées Ce schéma assure les propriétés suivantes :

1. Le schéma original de Juels et al utilise un système cryptographique ElGamal exponentiel. Il estdonc possible d’adapter le test d’égalité de messages orignaux à d’autres systèmes basés sur le problèmedu Logarithme discret



FIGURE 2.4 – Schéma de Juels, Catalano et Jakobsson

(1) Receipt-freeness (sans reçu) : Ce schéma offre la possibilité de vérifier le cré-dit après avoir mixé les votes. Dans ce cas le votant est dans l’impossibilité d’obte-nir des informations pour concevoir un reçu.

(2) résistance à la coercition : Ce schéma est Receipt-freeness, en plus il donne lapossibilité au votant d’effectuer de faux votes (i.e accompagné de crédit non valide)tout en permettant également à ce dernier de distribuer des crédits non valide auxattaquants.

(3) Vérifiabilité universelle : Toute les étapes de ce schéma peuvent être vérifié :de la génération des clés aux décomptes. Ce schéma utilise un tableau de vote (BB)qui est publiquement accessible.

Limites(1) Efficience : Étant donné que le test d’égalité du crédit anonyme est réalisé sur

l’ensemble de tous les crédits, ce schéma est inefficient car le décompte des votess’effectue en temps quadratique en fonction du nombre de votes (électeurs) [24].Des améliorations sont proposées :– L’utilisation d’une table de hachage pour détecter des collisions de crédit ano-

nyme plus facilement a été proposée dans [22]. L’idée étant de créer une em-preinte aveugle de ce crédit en élevant le chiffré du crédit anonyme à une cer-taine puissance z et ensuite, en déchiffrant le résultat, les autorités de décompteobtiennent une empreinte déterministe du crédit anonyme sans en connaitre sa


2.2. SCHÉMA DE PORKODI, ARUMUGANATHAN ET VIDYA 41

véritable valeur. Il est par conséquent plus facile de détecter les collisions à l’aidede cette empreinte.

– L’ amélioration de Smith conduit a un schéma efficient mais non sécurisé. Leschéma amélioré a été attaqué par [2] qui propose un algorithme qu’un at-taquant pourrait faire tourner pour voir si le votant qu’il attaque lui a bienfourni un crédit anonyme valide. Le décompte des votes reste donc quadratique.Preuve. Supposons que l’attaquant force l’électeur à lui révéler son crédit σ. Apartir de ce dernier il crée deux tuples ; l’un constitué du chiffrement de σ etl’autre du chiffrement de σ2. ces chiffrés sont publiés dans BB. Lors de la phasede décompte et après utilisation du schéma de Smith, les autorités de décomptepublient σk et σ2k sur BB. Après le calcule du carré des différents éléments, l’at-taquant est par conséquent capable de déterminer la correspondance entre leséléments calculés et ceux de BB. Si les entrées des votes correspondant à σ et σ2

sont éliminés par Tj, alors l’attaquant en déduit que σ est invalide.

– Weber [24] propose une modification considérée également comme cassée. Icil’attaquant est capable de déterminer si un vote associé à un crédit connu estcomptabilisé ou non

De ce qui précède nous pouvons dire que la recherche concernant la suppressionde la complexité quadratique du schéma de Juel et al reste encore d’actualité.

(2) Complétude : Ce schéma de vote n’assure pas la complétude puisqu’il est pos-sible qu’un vote valide ne soit pas finalement comptabilisé.Preuve. Lors de la phase de décompte, plus précisément pendant la suppressiondes doubles vote, ces derniers sont éliminés de manière aléatoire (selon l’ordred’arriver). Dans ce cas des entrées contenant des votes valides peuvent être sup-primées et ces votes valides non comptabilisés.

2.2 Schéma de Porkodi, Arumuganathan et Vidya

Ce schéma de vote proposé par Porkodi et al et publié dans [16] intitulé Multi-authority Electronic Voting Scheme Based on Elliptic Curve. Cet article propose unschéma de vote pour un référendum (scrutin de type Oui/Non), puis l’étend à un scrutinà candidat multiple (scrutin de type 1-parmi-n) .

2.2.1 Fonctionnement

Les participants au processus électoral sont les votants (Vi), i ∈ [1,m], les autorités(Aj), j ∈ [1, n], et une entité supérieure appelée centre de confiance.



Phase de configuration– Le centre de confiance choisit une courbe elliptique E définie sur le corps Fp, un

point P d’ordre q et le secret s ∈ Z∗q.– Le centre de confiance publie E, P , q et h = sP dans BB (tableau public).– le centre de confiance choisit aléatoirement un polynôme secret f(x) = s + a1x +

a2x2 + ...+ at−1x

t−1( mod q) et calcul s1 = f(1), s2 = f(2),...,sn = f(n)

– Le centre de confiance partage le secret s entre n autorités (c’est à dire qu’il envoiela paire secrète (i, f(i)) aux différentes autorités Ai où i est l’identifiant).

Au moins t autorités parmi les n sont nécessaires pour reconstruire la clé secrète s àpartir du schéma à seuil (t, n) de Shamir

Publication de la clé publique des autorités hi = siP dans BB. le votant effectue sonchoix (Oui/Non), le chiffre grâce au chiffrement ElGamal. Le choix oui est représentépar 1 et non par (−1).

Phase de vote Le votant Vi choisit un secret αi ∈ Z∗q, sélectionne son vote vi ∈ {1,−1},le chiffre en ci = (ci,1, ci,2) = (αiP, αih+ viP ) et l’envoie au tableau de vote public. Ce voteest accompagné d’une preuve de validité.

Phase de décompte Tous les acteurs qui accèdent aux informations publiques dutableau de vote peuvent calculer :

c = (c1, c2) = (m∑i=1

ci,1,m∑i=1

ci,2) = ((m∑i=1

αi)P, (m∑i=1

αi)h+ dP )

puisque le chiffrement ElGamal est homomorphique alors c = (c1, c2) est le chiffrementde dP où d =

∑mi=1 vi est la différence entre le nombre de voix pour le (oui) et celle

du (non). Le décompte final est effectué par au moins t autorités honnêtes parmi lesn (n > t). Notons J l’ensemble de ces autorités honnêtes. Ces autorités Aj envoientwj = sj(c1) avec leur identifiant j. Dès lors que tous les Aj ∈ J ont envoyé leur messagewj le résultat final peut être retrouvé en calculant c2 − s(c1).

La valeur de s(c1) est obtenue à partir de wj = sj(c1) en effectuant les calculs sui-vants :

∑j∈J

(∏

k∈J,k 6=j

(k

k − j)wj) =

∑j∈J

(∏

k∈J,k 6=j

(k

k − j)(sj, c1))

=∑j∈J

(∏

k∈J,k 6=j

(k

k − j)sj(c1))

= s(c1) par le schéma de partage de Shamir



De même

c2 − s(c1) = (m∑i=1

αi)sP + dP − s(m∑i=1

αi)P )

= (m∑i=1

αi)sP + dP − (m∑i=1

sαi)P )

= dP avec αi(sP ) = (αis)P

La valeur d représente la différence entre le vote positif (oui) et le vote négatif (non).Cette valeur s’obtient en calculant les points m(−P ), (m − 1)(−P ), ..., P, 2P, ...mP et encomparant à chaque fois le résultat obtenu à la valeur de dP . Notons x le nombre de voixpour "oui" et y celle pour "non". Les valeurs de ces nombres s’obtiennent en résolvant lesystème d’équations {

x− y = d

x+ y = m

2.2.2 Analyse

Dans [16], le schéma de Porkodi et al, assure les propriétés suivantes :

1. Éligibilité : les votants et les autorités doivent être enregistrées au centre deconfiance car seuls les acteurs enregistrés sont autorisés à envoyer leur message.

2. Secret : pendant la phase de vote seuls les votes chiffrés sont envoyés sur le ta-bleau de vote public. Ainsi un attaquant n’a aucune information sur le contenu duvote et ne peut donc pas lier le votant à son vote.

3. Vérifiabilité universelle : Les votes chiffrés et les preuves de validité associéessont envoyés sur le tableau public. Ainsi tout le monde peut vérifier la validité duchiffrement des votes et celle du résultat final.

4. Équité : Il est difficile d’avoir les résultats partiels car pour déchiffrer le contenudu bulletin il faut connaitre la clé sécrète s du système i.e résoudre le problème dulogarithme discret sur les courbes elliptiques.

5. Robustesse : Le décompte final est effectué en se basant sur le chiffrement dis-tribué à seuil (t, n) de ElGamal qui peut tolérer la défection d’au maximum (n− t)autorités. Tout vote invalide peut être détecté et exclu du décompte final.

Remarque 2.2.1. ce schéma ne satisfait pas les propriétés suivantes :– Sans reçu(receipt-freeness) : parce-que le votant détient des informations qu’il peut

utiliser pour prouver de quelle manière il a voté.– Résistance à la coercition : puisque ne satisfaisant pas la propriété de receipt-

freeness.



Preuve.Étant donné que l’électeur connait P, h, αi. Il peut utiliser ces informations pour prou-

ver de quel manière il a voté c’est à dire il peut calculer ci = (ci,1, ci,2) = (αiP, αih + viP ).le calcul du point αiP est évident. En ce qui concerne le point αih + viP il suffit de fairevarier vi ∈ {1,−1}.

2.2.3 Illustration numérique

Phase d’initialisation : supposons que le système a un ensemble de 14 participantsparmi lesquels 8 électeurs et 6 autorités. Le centre de confiance choisit une courbe ellip-tique E définie sur le corps Fp d’équation y2 = x3 − 4 (mod 211) avec p = 211. Le centrede confiance sélectionne le point de base P de coordonnées (94,57) d’ordre q = 241 et lepolynôme secret f(x) = 52 + 15x + 11x2 + 14x3 + 28x4 (mod 241). La clé privée du centrede confiance est s = 52.Le centre de confiance transmet le secret partagé aux différentes autorités Ai via uncanal sécurisé ; c’est à dire que pour i ∈ [1, 6] le centre de confiance envoie les paires(i, si) = (i, f(i)) soit (1, s1) = (1, 120), (2, s2) = (2, 204), (3, s3) = (3, 191), (4, s4) = (4, 158),(5, s5) = (5, 131), (6, s6) = (6, 85) aux autorités.Le centre de confiance publie sur le tableau publique E, p, P , q, h = sP = (82, 134)

et les points siP pour i = 1, 2, ..., 6. Les valeurs respectives sont les suivantes (196, 29),(175, 155), (6, 210), (87, 50), (118, 56), (54, 138). Puisque le degré du polynôme secret est 4,le décompte final s’effectue si et seulement si au moins 5 autorités réunissent leur partde secret.

Phase de vote : chaque votant Vi chiffre son vote viP ∈ {P,−P} en (ci,1, ci,2) = (αiP, αih+

viP ) et l’envoie dans le tableau vote publique. Le tableau ci dessous donne le chiffrés desvotes de 8 électeurs :

TABLEAU 2.1 – Valeurs numériques des votes chiffrés pour un référendum

Numéro Votant Vi ci,1 = αiP ci,2 = αih+ viP1 V1 (50,57) (45,179)2 V2 (195,72) (145,127)3 V3 (159,114) (89,196)4 V4 (20,191) (69,191)5 V5 (159,114) (79,136)6 V6 (191,196) (83,124)7 V7 (17,30) (74,210)8 V8 (20,191) (69,191)



Phase de décompte : dès lors que les votants émettent leurs votes (ci,1, ci,2) pouri = 1, 2, ..., 8 sur le tableau publique il est possible de calculer c1 =

∑8i=1 ci,1 = (36, 34) et

c2 =∑8

i=1 ci,2 = (172, 16) qui représentent les valeurs numériques de la somme des votes.Supposons que les 6 autorités (J = {A1, ..., A6}) partagent leurs clés partielles dans l’op-tique de reconstruire la clé secrète. les autorités de décompte calculent

∏k∈J,k 6=j(

kk−j )wj)

pour j = 1, 2, ..., 6. Le tableau 2.4 donne les valeurs de wj et∏

k∈J,k 6=j(kk−j )wj).

TABLEAU 2.2 – Valeurs numériques de la phase de décompte lors d’un référendum

Autorités wj = Sjc1

∏k∈J,k 6=j(

kk−j )wj)

A1 (182,100) (34,138)A2 (209,58) (183,153)A3 (207,96) (181,209)A4 (23,66) (111,145)A5 (30,153) (64,17)A6 (168,205) (168,6)

Dès lors, le calcule de s(c1) =∏

k∈J,k 6=j(kk−j )wj) = (124, 119) est possible. De même une

fois la clé reconstruite, le calcul de dP s’effectue de la manière suivante : c2 − s(c1) =

dP = (124, 119). d est retrouvée en calculant les points −8P , −7P , −6P ,..., P ,...,8P eten comparant à chaque fois le résultat obtenu à la valeur de dP . après calcul on a d =

2. Notons x le nombre de voix pour "oui" et y celle pour "non". Les valeurs de x et ys’obtiennent en résolvant le système d’équations{

x− y = 2

x+ y = 8

Soit x = 5 et y = 3

Le résultat du référendum est publié, le nombre de voix pour est de 5 et le nombrede voix contre est 3.

2.2.4 Extension au vote à multiples candidats

Codage des candidats Supposons que lors du vote les électeurs V1, ..., Vm choisissentparmi les candidats représentés par u1, u2, ..., ur au lieu des deux choix précédents [−1, 1].Lors du chiffrement le message (candidat choisi) doit être représenté (encodé) commeun point d’une courbe elliptique. Pour le faire, le centre de confiance choisit "r" points debase P1, P2, ..., Pr ∈ E(Fp) et encode vj par Pj et publie cet encodage.

Phase de vote l’électeur Vi chiffre son choix uj comme ci = (ci,1, ci,2) = (αiP, αih+Pj) etl’envoie sur le tableau de vote publique. Ce votant montre par une preuve qu’il connaitci,1 = αiP et que αih = ci,2 − Pj.



Phase de décompte Tous les acteurs qui accèdent aux informations publiques du ta-bleau de vote peuvent calculer :

c = (c1, c2) = (m∑i=1

ci,1,

m∑i=1

ci,2) = ((m∑i=1

αi)P, (m∑i=1

αi)h+ (r∑j=1

djPj))

où dj représente le nombre de vote en faveur de uj, c = (c1, c2) est le chiffrementdes choix u1, ..., ur. Le décompte final s’effectue par au moins t autorités honnêtes parmiles n (n > t). Notons J l’ensemble de ces autorités honnêtes. Ces autorités Aj envoientwj = sj(c1) avec leur identifiant j. Dès lors que tous les Aj ∈ J ont communiqué wj, ledécompte est possible en calculant :

c2 − s(c1) =r∑j=1

djPj

Ces autorités vont obtenir la valeur numérique des votes (d1, ..., dr) en calculant∑r

j=1 djPj

pour des valeurs satisfaisantes :

r∑j=1

dj = m, 0 ≤ dj ≤ m

et les comparer avec la somme obtenue de c2 − s(c1).

2.2.5 Illustration numérique pour une élection à quatre candi-dats

Phase d’initialisation : supposons que le système admet un ensemble de 16 parti-cipants parmi lesquels 10 électeurs et 6 autorités. Le centre de confiance choisit unecourbe elliptique E définie sur le corps Fp d’équation y2 = x3 − 4 (mod 211) avec p = 211.Le centre de confiance sélectionne le point de base P de coordonnées (94,57) d’ordreq = 241 et le polynôme secret f(x) = 52 + 60x+ 26x2 + 24x3 + 13x4 (mod 241). La clé privéedu centre de confiance est s = f(0) = 52.Le centre de confiance transmet le secret partagé aux différentes autorités Ai via uncanal sécurisé ; c’est à dire que pour i ∈ [1, 6] le centre de confiance envoie les paires(i, si = f(i)) soit (1, s1) = (1, 175), (2, s2) = (2, 194), (3, s3) = (3, 239), (4, s4) = (4, 29),(5, s5) = (5, 77), (6, s6) = (6, 3) aux autorités Ai pour i = 1, ..., 6.Supposons que les électeurs ont le choix des candidats représentés par u1, u2, u3, u4. Lecentre de confiance choisit quatre points différents de P = (94, 57) appelés P1 = (2, 2),P2 = (6, 1), P3 = (13, 100), P4 = (14, 29) et code u1, u2, u3, u4 comme les points P1, P2, P3, P4

Le centre de confiance publie sur le tableau public E, p, q, h = sP = (82, 134) et les pointssiP pour i = 1, 2, ..., 6. Les valeurs respectives sont les suivantes (182, 100), (167, 30),



(124, 192), (27, 30), (121, 210), (137, 37). Puisque le degré du polynôme secret est 4, le dé-compte final sera effectué si et seulement si au moins 5 autorités réunissent leur clé.

Phase de vote : chaque votant Vi chiffre son vote comme (ci,1, ci,2) = (αiP, αih + Pj)

où Pj ∈ {P1, P2, P3, P4}et l’envoie dans le tableau vote public. Les votes chiffrés des 10électeurs sont donnés par le tableau 2.3 suivant :

TABLEAU 2.3 – Valeurs numériques des votes chiffrés pour un vote à candidats mul-tiples

Numéro Votant Vi ci,1 = αiP ci,2 = αih+ Pj1 V1 (60,96) (130,203)2 V2 (39,92) (89,196)3 V3 (174,163) (118,56)4 V4 (206,90) (67,57)5 V5 (144,69) (14,29)6 V6 (95,194) (20,20)7 V7 (16,111) (81,136)8 V8 (93,134) (107,87)9 V9 (150,85) (71,126)

10 V10 (130,8) (27,181)

Phase de décompte : Dès lors que la phase de vote se termine, les votes sont dispo-nibles sur le tableau public. il est donc possible de calculer c1 =

∑10i=1 ci,1 = (119, 113) et

c2 =∑10

i=1 ci,2 = (87, 161) qui sont les valeurs numériques de la somme des votes chiffrés.Supposons que les 6 autorités (J = {A1, ..., A6}) partagent (j, wj = sjc1) leurs partssecrètes dans l’optique de reconstruire la clé secrète. les autorités de décompte cal-culent

∏k∈J,k 6=j(

kk−j )wj) pour j = 1, 2, ..., 6. Le tableau 2.4 donne les valeurs de wj et∏

k∈J,k 6=j(kk−j )wj) :

TABLEAU 2.4 – Valeurs numériques de la phase de décompte lors d’une élection àquatre candidats

Autorités wj = Sjc1

∏k∈J,k 6=j(

kk−j )wj)

A1 (80,136) (159,97)A2 (72,14) (207,115)A3 (51,136) (34,73)A4 (50,57) (74,10)A5 (168,6) (23,66)A6 (179,199) (45,32)

Dès lors, s(c1) =∑

j∈J∏

k∈J,k 6=j(kk−j )wj) = (70, 200). Une fois la clé reconstruite, le

calcul du résultat s’effectue de la manière suivante : c2− s(c1) =∑4

j=1 djPj = 4P1 + 2P2 +

2P3 + 2P4 = (99, 31). Nous obtenons le tableau de résultat ci dessous :



Tableau des résultatsIdentifiant nombre de voix

P1 4P2 2P3 2P4 2

Le vainqueur est le candidat représenté par P1.

2.2.6 Illustration du non receipt freeness

L’électeur connait P, h, αi,ci,1 = αiP et ci,2 = αih+viP . Il peut utiliser ces informationspour prouver de quel manière il a voté c’est à dire calculer Pj = ci,2 − αih.

Exemple 2.2.1. Supposons que le votant V1 a utilisé l’entier α1 = 42 pour chiffrer sonvote alors il est possible d’utiliser α1 pour calculer Pj = c1,2−α1h = (130, 203)− (50, 57) =

(2, 2). Le votant V1 a voté pour le candidat P1 = (2, 2).

Nous obtenons le tableau 2.5 qui donne la valeur du vote de chaque électeur :

TABLEAU 2.5 – Utilisation des informations pour retrouver le candidat choisi

Numéro Votant Vi ci,1 = αiP ci,2 = αih+ Pj αi Pj = ci,2 − αih1 V1 (60,96) (130,203) 42 (2,2)2 V2 (39,92) (89,196) 32 (2,2)3 V3 (174,163) (118,56) 34 (6,1)4 V4 (206,90) (67,57) 35 (13,100)5 V5 (144,69) (14,29) 54 (13,100)6 V6 (95,194) (20,20) 24 (2,2)7 V7 (16,111) (81,136) 26 (2,2)8 V8 (93,134) (107,87) 57 (14,29)9 V9 (150,85) (71,126) 12 (6,1)10 V10 (130,8) (27,181) 41 (14,29)


CHAPITRE 3

PROPOSITION D’UN SCHÉMA DEVOTE

Après avoir détaillé quelques schémas de vote électronique dans le chapitre précé-dent. Nous présentons dans ce chapitre un schéma de vote résistant à la coercition quiapporte des solutions à certaines limites observées dans les systèmes du Chapitre 2. Lenouveau schéma repose sur la cryptographie basée sur les courbes elliptiques et sur ladéfinition d’un crédit anonyme que l’électeur associe à son vote.

Le schéma de vote que nous présentons dans ce chapitre permet au votant d’associerà son vote un crédit anonyme, lui offre (votant) la possibilité de voter plusieurs fois eten cas d’attaque lui permet d’associer à ses votes des crédits non valides .

Les principaux acteurs de notre schéma sont :

1. Les votants notés Vi avec i ∈ [1,m] ;

2. les candidats cr avec r ∈ [1, k], cr ∈ Vi ;

3. Les autorités d’enregistrement (Rj) avec j ∈ [1, l].

4. Les autorités de comptage (Tj) avec j ∈ [1, n].

3.1 Outils cryptographiques utilisés

Ce schéma requiert un certain nombre de primitives cryptographiques pour assurersa sécurité. Nous présentons entre autre :

3.1.1 Crédit anonyme

Le crédit anonyme est un élément essentiel pour assurer la propriété de résistanceà la coercition dans les systèmes de vote électronique. Dans certains schémas tels queJCJ [13] le crédit est une chaine de caractères alphanumériques. Pour notre schéma,nous proposons que ce crédit anonyme soit généré par les autorités d’enregistrement ettransmis à l’électeur comme un certificat lors de son enregistrement. Toutefois malgréle fait qu’il est généré par les autorités, celles ci ne doivent pas prendre connaissance


3.1. OUTILS CRYPTOGRAPHIQUES UTILISÉS 50

de son contenu ; pour le réaliser nous utilisons des systèmes cryptographiques appeléssignatures agrégées (Aggregate Signatures).

Signatures agrégéesLa notion de signature agrégée a été introduite dans [3] par Boneh et al. Une signature

agrégée est une signature électronique qui consiste à permettre à plusieurs signatairesde signer des messages différents et ensuite d’agréger ces différentes signatures en uneseule. Autrement dit, étant donné n signatures de n messages (les messages peuventêtre distincts) mi (1 ≤ i ≤ n) provenant de n signataires (avec une paire de clé publiquePKi et privée SKi) et ensuite agréger toutes ces n signatures en une seule.

La figure suivante (Figure 3.1) illustre le mécanisme de cette signature.

m1

m2

mn

...............

sign1(SK1)

sign2(SK2)

signn(SKn)

σ1

σ2

σn

collecte σ1 + σ2 + ...+ σn

FIGURE 3.1 – Mécanisme d’une signature agrégée

Schéma de signature agrégée basé sur les courbes elliptiquesLe schéma de Boneh et al [3] peut être modifié et construit sur le groupe constitué des

points d’une courbe elliptique. Sa sécurité repose sur le problème du logarithme discret.Le schéma se compose de trois algorithmes : un algorithme de génération des clés, unalgorithme de signature et un algorithme d’agrégation.

Soient F = E(Fp) le groupe de points de la courbe E définie sur un corps Fp, P ungénérateur de F d’ordre q, H : {0, 1}∗ → F une fonction de hachage.

Génération des clésChaque entité crée la clé publique et la clé privée correspondantea). choisir aléatoirement x ∈ Z∗q et calculer v = [x]P ;b). la clé publique est v et la clé privée x ;



SignaturePour chaque signataire avec la clé publique v, la clé privée x et le messagem ∈ {0, 1}∗ :a). calculer h = H(m) où h ∈ F ;b). calculer σ = [x]h c’est la signature ;

AgregationPour un ensemble de signataire Si (i ∈ [1, l]) :a). le signataire i fournit une signature σi de mi ∈ {0, 1}∗ ;b). calculer δ =

∑ni=1 σi la signature agrégée est δ ;

3.1.2 Système cryptographique ElGamal distribué Version ellip-tique

Le système cryptographique ElGamal sur les courbes elliptiques est analogue à celuides nombres. De ce fait nous introduisons une version distribuée similaire à la Section1.2.2.6. Pour notre schéma nous utilisons cette version du cryptosystème. Soient E unecourbe elliptique définie sur Fp et G un point de E(Fp) d’ordre q. La clé privée s estpartagée entre n autorités Aj (1 ≤ j ≤ n).

Génération de clé– Choisir une courbe elliptique E définie sur Fp et G un point de E(Fp) d’ordre q

premier– Choisir un entier aléatoire k ∈ [1, q − 1] et calculer h = [s]G.– La clé publique est (E,G, h), clé privée= s

– Exécuter le partage de secret à seuil (t, n) de Shamir. Pour cela générer aléatoi-rement un polynôme P (x) de degré t − 1 : P (x) = a0 + a1x + ... + at−1x

t−1 aveca0 = P (0) = s et partager les parts secrètes sj = P (j) aux autorités de décomptegrâce au partage de clé de Diffie Hellman.

– Le calcul de la valeur de s = P (0) s’effectue comme suit :

s = P (0) =t∑i

P (i)

(t∏

j=1,j 6=i

i

i− j

)(3.1)

N.B : sj est la part secrète de l’autorité j et hj = [sj]G est la clé publique de cetteautorité.

Le Chiffrement La clé publique est le triplet (E,G, h). Pour chiffrer un messagem ∈ E(Fp), on choisit un nombre aléatoire k ∈ [1, q − 1] et on calcule c = (c1, c2) avecc1 = [k]G et c2 = [k]h+m



Déchiffrement distribuéLes autorités déchiffrent ensemble le message chiffré (c1, c2) = ([k]G, [k]h+m), avec

m ∈ E(Fp), sans reconstruire la clé privée s.

Protocole de déchiffrement distribué

1. Chaque autorité Pj calcule son déchiffrement partiel wj = [sj] c1 et lediffuse accompagné d’une preuve à divulgation nulle de connaissanced’égalité du logarithme discret que :

logghj = logc1wj

Notons que cette preuve d’égalité signifie que le déchiffrement partielréalisé à l’aide de la part de secret sj est correcte. Cette preuve est sem-blable à celle de la section 1.2.2.4.

2. Pour tout sous-ensemble ∆ à t autorités dont la preuve précédente estvalide, on retrouve le message d’origine en utilisant l’interpolation deLagrange :

m = c2 − [s] c1

où :[s] c1 =

∑j∈∆

λj∈∆wj

λj,∆ =∏

k∈∆,k 6=j

(k

k − j

)

FIGURE 3.2 – Protocole de déchiffrement distribué

3.1.3 Mixnet à rechiffrement universellement vérifiable

Dans le contexte du vote électronique, on utilise les mixnets pour créer un canalanonyme lors de la transmission des votes le secret du vote est assuré car il est difficiled’établir le lien entre les votes émis (i.e. à l’entrée du canal) et les votes en sortie (i.e. lasortie du canal de vote) transmis pour le décompte.

La mise en oeuvre d’un tel mixnet commence par le chiffrement d’un message m

avec la clé publique du destinataire à l’aide d’un système cryptographique permettantle rechiffrement (ElGamal elliptique pour notre cas). Ensuite le message chiffré est en-voyé à travers un mixnet M à rechiffrement où chaque mixeur Mi effectue les actionssuivantes :

1. Recevoir à son entrée e un message chiffré c. Avec ElGamal elliptique ,



c = ([k]G, [k]h+m) où G est un générateur du groupe de point de la courbe ellip-tique, h la clé publique et k un entier aléatoire ∈ [1, p− 1] choisi par l’expéditeur etéventuellement modifié par les mixeurs précédents si Mi 6= M1.

2. Choisir un autre entier aléatoire s ∈ [1, p− 1] et calculer :

c∗ = ([k]G+ [s]G,m+ [k]h+ [s]h) = ([k + s]G,m+ [k + s]h)

3. Vérifier que le rechiffrement est correcte par une preuve de rechiffrement

4. Regarder dans la table de permutation la sortie f associée à l’entrée e.

5. Envoyer le paquet c∗ sur l’entrée f du prochain mixeur Mi+1 s’il existe. Si Mi est ledernier mixeur, alors le processus se termine et c∗ envoyé à BB.

3.1.4 Preuve non interactive à divulgation nulle de connais-sance basée sur les ECC

3.1.4.1 Preuve à divulgation nulle de connaissance d’égalité du loga-rithme discret

Cette preuve est réalisée par le protocole de Chaum-Pedersen

version Elliptique du protocole de Chaum-PedersenLa version elliptique de ce protocole est la suivante : Supposons que le prouveur

connait deux quantités qui ont le même logarithme discret en x pour deux clés pu-bliques G et T . Le prouveur et le vérificateur s’accordent sur une courbe elliptiqueE définie sur le corps fini Fp, des points G ∈ E(Fp) et T ∈ E(Fp) . Le prouveur af-firme connaitre x tel que B = [x]G et C = [x]T il veut prouver cela au vérificateursans lui révéler la valeur de x.

(a) Prouveur choisit un nombre aléatoire r mod p.

(b) Prouveur calcule les points K = [r]G et L = [r]T ensuite envoie ces valeurs auVérificateur.

(c) Vérificateur choisit un nombre aléatoire c = H(B,G,C, T,K, L) où H est unefonction de hachage et envoie c au prouveur.

(d) Prouveur calcule alors m = r + cx mod p et envoie m au Vérificateur.

(e) Vérificateur s’assure que [m]G = K + [c]B et [m]T = L+ [c]C

Cette preuve est utilisée lors du Déchiffrement distribué (voire section 3.1.2)



3.1.4.2 Preuve à divulgation nulle de connaissance de validité du contenud’un message chiffré : version elliptique

Nous donnons la version basée sur les courbes elliptiques de la méthode Byoung-cheon Lee. Cette preuve permet de vérifier qu’un message m chiffré (représentantle candidat) est valide i.e étant donné M = m1,m2, ...,mL un ensemble de messageconsidéré comme valide le prouveur veut montrer que mk son message chiffré estdans M sans dévoiler mk

Paramètres– Les paramètres d’un système de chiffrement Elgamal version elliptique ou h =

[s]G est la clé publique de l’autorité de décompte et k un entier aléatoire utilisépour le chiffrement

– Soit M = m1,m2, ...,mL ensemble de messages considérés comme valides dansnotre cas M représente l’ensemble des candidats.

– Le prouveur chiffre son message mk (vote pour le kième candidat) à l’aide duchiffrement ElGamal elliptique et obtient la paire

(c1, c2) = ([k]G,mk + [k]h)

– Le prouveur choisit aléatoirement un entier w ∈ Zq et calcule :

ak = [w]G

bk = [w]h

– Pour tout i tel que (k 6= i) et (j ≤ L), le Prouveur choisit ri, di ∈ Zq et calcule :{ai = [ri]G+ [di] c1

bi = [ri]h+ [di] (c2 −mi)

– Le Prouveur calcule un challenge c ∈ Zq à l’aide d’un modèle d’oracle aléatoire

c = H(a1, b1, ..., aL, bL)

– En utilisant ce challenge (c) le Prouveur calcule :{dk = c−

∑k 6=i di

rk = w − kdk

– Finalement le Prouveur envoie {a1, b1, d1, r1, ..., aL, bL, dL, rL} au Vérificateur

Le Vérificateur vérifie la valeur de c en calculant

c = d1+...+dL = H([r1]G+ [d1] c1, [r1]h+ [d1] (c2 −m1), ..., [rL]G+ [dL] c1, [rL]h+ [dL] (c2 −mL))



Le Vérificateur vérifie la valeur de ai et celle de bi pour i = 1, ..., L{ai = [ri]G+ [di] c1


Cette preuve est utilisée dans le système de vote pour garantir que le candidat crchoisi par l’électeur appartient réellement à l’ensemble des candidats qui compé-tissent lors de cette élection.

Fonctionnement de la preuveLe vérificateur vérifie les ai et bi de la manière suivante

(a) Pour tout ai , bi avec i 6= k{ai = [ri]G+ [di] c1


(b) Pour vérifier ak, nous partons de la valeur calculée par le prouveur qui estak = [w]G. Le vérificateur quant à lui s’assure que :

ak = [rk]G+ [dk] c1

= [w − kdk]G+ [dk] c1

= [w]G− [kdk]G+ [kdk]G

= [w]G

(c) De même pour vérifier bk, nous partons de la valeur calculée par le prouveurqui est donnée par bk = [w]h. Le vérificateur va s’assurer que :

bk = [rk]h+ [dk] (c1 −mk)

= [w − kdk]h+ [dk] (c1 −mk)

= [w − kdk]h+ [dk] ([k]h+mk −mk)

= [w]h− [kdk]h+ [kdk]h

= [w]h

Remarque 3.1.1. Lorsque le prouveur essaye d’octroyer plusieurs voix en seulvote (c1, c2) = ([k]G, 20mk+[k]h) ou vote pour plusieurs candidats (c1, c2) = ([k]G,mk+

mk−1 + [k]h) ou encore tente de nuire à un candidat en réduisant ces voix pendantqu’il en octroie plusieurs à un autre (c1, c2) = ([k]G, 20mk − 10mk−1 + [k]h) alors lapreuve ne sera pas correcte puisque pendant la vérification, la valeur de bk ne serapas égale à celle de [rk]h+ [dk] (c1 −mk)


3.2. PRÉSENTATION DU SCHÉMA 56

3.1.5 Hypothèses

Avant de présenter de manière détaillée notre schéma de vote, il est important defaire quelques hypothèses. Nous supposons que :

(a) L’attaquant ne peut contrôler ou interagir avec l’électeur en permanence aucours de la procédure de vote. Cependant, il peut interagir avec l’électeur oc-casionnellement pendant le vote ;

(b) Les ordinateurs que les électeurs utilisent pour le vote sont dignes de confiance.Nous ne considérons pas les attaques où l’adversaire peut contrôler l’ordina-teur de l’électeur (par exemple au moyen de malwares) en vue d’obtenir sonvote ou d’autres informations privées.

(c) Les Attaques par déni de service ne sont pas pris en considération.

(d) Les mesures de sécurités seront prises en ce qui concerne l’hébergement etl’exploitation de l’architecture technique lors de la mise en oeuvre pratique dusystème :

– L’hébergement sécurisé des serveurs (salles informatiques protégées contreles intrusions, l’incendie, les pannes d’électricité, les excès de température,les pannes matériels et autres dommages susceptibles de perturber le sys-tème, procédure d’administration sécurisée des serveurs et des éléments destockage des données),

– La duplication du système de vote, par la mise en place d’un système de se-cours, fonctionnant en "miroir "du système principal (le système de secourstraite en parallèle du système principal les mêmes données que ce dernier),

3.2 Présentation du schéma

3.2.1 Description détaillée du schéma

3.2.1.1 Phase de configuration

Durant cette phase, les paramètres du système sont initialisés, les clés des dif-férentes autorités sont établies et les informations publiques sont publiées sur letableau de vote public.

(a) Choisir une courbe elliptique E d’équation y2 = x3 + ax+ b et G un générateurde E(Fp) d’ordre q (nombre premier de longueur ≥ 160 bits).

(b) Les autorités de décompte Tj (1 ≤ j ≤ n) coopèrent dans la génération desparamètres d’un système cryptographique ElGamal elliptique à seuil (t, n). Ilsobtiennent une clé publique h et chaque autorité de décompte possède une part



secrète sj. Seul t autorités parmi les n seront nécessaires pour « reconstruirela clé secrète grâce à l’interpolation de Lagrange (voire Section 1.2.2.6).

(c) Génération des clés des autorités d’enregistrement.

(d) Enregistrement des candidats cr et représentation de ces différents candidatscomme des points Pr ∈ E(Fp) (voir 3.2.1.1). Notons que nous représentonsl’abstention comme un candidat.

Représentation des candidats Supposonsm le nombre d’électeurs et k le nombrede candidats. Soit P un générateur de E(Fp). Dans notre schéma comme dans [10]les candidats cr (r ∈ [1, k]) sont représentés par le point Pr = [(m+ 1)r]P

3.2.1.2 Phase d’enregistrement

Un électeur Vi doit être inscrit (enregistré dans la base de données) pour pouvoirvoter. Nous supposons que cette inscription ne se fait pas en ligne. Par exemple,nous proposons qu’elle se fasse dans un bureau d’enregistrement, comme l’inscrip-tion sur les listes électorales dans le système traditionnel.

L’électeur va se faire enregistrer par les autorités d’enregistrement Rj dans unbureau muni d’un isoloir. Pour cela :

(a) L’électeur Vi se rend dans ce bureau d’enregistrement avant l’élection un jourde son choix (dans la période légale) muni d’une pièce (carte d’identité) pourmontrer qu’il remplit les conditions légales pour être électeur.

(b) Après vérification des informations, Il est ensuite conduit vers un isoloirmuni d’un ordinateur.

(c) Les autorités d’enregistrement de ce bureau utilisent la "carte " du votantpour initialiser le processus i.e. rentrer ces informations personnelles et safiliation dans le système, le votant vérifie les informations à l’écran et si ellessont conformes à celles de la carte, il les valide.

(d) Le système transmet à l’électeur un crédit anonyme δ =∑n

i=1 σi. Ce crédit estgénéré par les autorités d’enregistrement qui coopèrent pour le faire 1.

(e) L’électeur Vi génère Si = chiffR(δi) et l’envoie aux autorités d’enregistrement.

(f) Les autorités d’enregistrement rechiffrent Si.

(g) Le votant choisit un mot de passe pi et un identifiant IDi qu’il enregistre dansle système et il les utilisera pour s’authentifier lors de la phase de vote. Notonsque c’est le haché de ces informations qui est enregistré dans le système.

1. comme la clé privée dans un cryptosystème à seuil



Tout au long de la phase de vote, l’électeur s’authentifie avant d’émettre son vote.Cette étape est comparable à la vérification manuelle (identification) effectuéedans les bureaux de vote lors des élections traditionnelles. Une fois l’authentifi-cation réussie, le votant peut voter pour le candidat de son choix sinon l’accès ausystème lui est refusé. le but est de permettre que seul les électeurs éligibles (préa-lablement inscris) puissent voter.

3.2.1.3 Phase de vote

Au cours de cette phase, l’électeur construit son vote qui sera par la suite transmissur tableau de vote public BB.

(a) Le votant Vi s’identifie auprès du système en entrant son ID et son mot depasse pi.

(b) Le votant Vi vote vi de la manière suivante : Il choisit aléatoirement (αi, βi, εi)

et calcule le tuple (chiff T (Pr), chiffR(δi),∆i, π), où chiff T (Pr) = (ci1, ci2) = ([αi]G, [αi]h+

Pr) est le chiffrement du candidat choisi par l’électeur avec la clé publique desautorités de décompte, chiffR(δi) est le chiffrement de son crédit anonyme avecla clé publique des autorités d’enregistrement,∆i = [εi] δi est une multiplica-tion scalaire , π est la preuve de validité du choix du candidat. Si le votant estsous la pression d’un attaquant qui souhaite le faire voter pour un candidatautre que celui qu’il a choisi, il utilise un crédit non valide qu’il associera aucandidat de l’attaquant : car ce dernier n’a aucune idée du crédit valide duvotant.

(c) Vi transmet son vote qui sera affiché sur le tableau de vote publique via uncanal anonyme (mixnet à rechiffrement universellement vérifiable)

Lorsque la plage de temps au cours de laquelle les électeurs peuvent voter s’achèvealors la phase de vote est terminée et on passe à la quatrième phase qui est la phasede décompte.

3.2.1.4 Phase de décompte

Durant cette phase les actions suivantes sont effectuées.

(a) Pour chaque entrée du tableau de vote public BB, Les autorités de décomptevérifient que la preuve de validité est correcte et éliminent les entrées où elleest incorrecte. Il en résulte un tableau de la forme :

Tableau brut des votes∆i chiff T (δi) chiff T (Pr) π

... ... ...



(b) Pour chaque entrée du tableau brut des votes, les autorités de décompte re-cherchent les valeurs dupliquées de ∆i et éliminent les entrées où le vote estassocié à un crédit anonyme non valide, par une Comparaison des crédits ano-nymes i.e. ils comparent les chiffrés de différents crédits à l’aide du test d’éga-lité de messages orignaux (voire Section 2.1.3) et éliminent les entrées où lerechiffré du crédit qui accompagne le vote d’un candidat ne correspond à au-cun rechiffré de crédit enregistré par les autorités d’enregistrement. Une desrègles qui régissent cette élection est la suivante : lorsqu’un électeur vote plu-sieurs fois et que les votes sont valides (accompagnés d’un crédit valide), lesdoubles votes de cet électeur seront éliminés dans le tableau de vote publiqueselon l’ordre d’enregistrement .i.e les votes les plus anciens seront suppriméset seul le plus récent sera comptabilisé.

... ... ...∆i chiff T (δi) chiff T (Pr)

... ... ...∆i chiff T (δi) chiff T (pr)... ... ...

Il en résulte un tableau des votes uniques et valides.

(c) Sommer tous les chiffrés des choix des candidats cr contenus dans le tableaudes votes uniques et valides. Soit :

ct = (c1, c2)

=

(m∑i=1

ci1,m∑i=1

ci2

)

=

([m∑i=1

(αi)

]G,

[m∑i=1

(αi)

]h+

(k∑r=1

[dr]Pr

))

Où dr ∈ [1,m] représente le nombre de vote en faveur du candidat cr.

(d) Coopérer pour déchiffrer ct. (voire 3.1.2) afin d’obtenir D =∑

r [dr]Pr accompa-gné d’une preuve à divulgation nulle de connaissance d’égalité des logarithmesdiscret qui montre que D est un déchiffrement distribué de ct. Le déchiffre-ment se fait par le sous ensemble d’autorité(J = {T1, ..., Tt}) i.e t autoritésparmi les n.



Pour déchiffrer ces t autorités calculent la somme des déchiffrements partielsgrâce à l’interpolation de Lagrange de la manière suivante :

P (x) =t∑

j=1

si∏

1≤i≤t

i 6=j

x− ji− j

[P (0)] c1 =

t∑i=1

si∏

1≤i≤t

i 6=j

j

j − i

c1 =〉 [P (0)] c1 =

[ t∑i=1

si

]c1

∏1≤i≤t

i 6=j

j

j − i

Après le calcul de [s] c1, Le déchiffrement de la somme des votes s’obtient encalculant c2 − [s] c1.

(e) Compter les voix. Le décompte des voix s’effectue en calculant les valeurs de(d1, d2, .., dk) pour cela on calcule de la somme

∑r [dr]Pr et on compare le résul-

tat à celui du calcul de c2 − [s] c1. Lorsque le calcul donne des valeurs égales,puisque les Pr sont connus on déduit directement dr, (r ∈ [1, k]).

Considérons le candidat c0 représenté par le point P lorsqu’il reçoit une voix,[2]P dans le cas ou deux suffrages ont été exprimés en sa faveur et [m]P s’ilreçoit les voix de tous les candidats. En procédant de façon similaire pour lesautres candidats nous obtenons le tableau suivant

TABLEAU 3.1 – Représentation des voix de chaque candidat

1 vote 2 votes · · · m votesc0 P [2]P · · · [m]Pc1 [(m+ 1)]P [2(m+ 1)]P · · · [m(m+ 1)]Pc2 [(m+ 1)2]P [2(m+ 1)2]P · · · [m(m+ 1)2]P...

......

......

ck[(m+ 1)k

]P

[2(m+ 1)k

]P · · ·

[m(m+ 1)k

]P

Remarque 3.2.1. pour k ≥ 3 La détermination de dr lors du calcule de la somme∑kr=0 [dr]Pr avec Pr = [(m+ 1)r]P dans le groupe E(Fp) est une instance du pro-

blème de sac à dos précisément le problème de la somme de sous-ensemble qui estNP-complet [10].

Formulation du problème : soient Q un point de E(Fp), Pr = [(m+ 1)r]P lesdifférents candidats (r ∈ [1, k]) nous cherchons l’ensemble d’entiers (d0, d1, ..., dk) telque

Q =k∑r=0

[dr]Pr =k∑r=0

[dr(m+ 1)r]P



.

Dans notre cas, étant donné que l’élection que nous voulons illustrer est du type1-parmi-k alors nous serons forcément confrontés à ce problème. La méthode quenous utilisons pour déterminer dr (r ∈ [1, k]) est la méthode naïve. Elle consisteen une recherche exhaustive i.e à comparer la valeur de Q à celle de la somme∑k

r=0 [dr]Pr où les dr ∈ [1,m] jusqu’a ce qu’elles coïncident.

3.2.1.5 Phase de vérification et de publication

Pour vérifier le résultat de l’élection tous les acteurs peuvent effectuer les actionssuivantes :

(a) Vérifier que le chiffrement ct est égal à la somme de tous les chiffrements descandidats du tableau de vote valide.

(b) Vérifier que la preuve montrant que D est un déchiffrement distribué de ct estcorrect

Après vérification, le résultat final est publié.

3.2.2 Analyse

Cette analyse consiste à évaluer les propriétés vérifiées par notre schéma et leslimites de celui ci.

3.2.2.1 Évaluation des propriétés

Un schéma de vote pour être sécurisé doit satisfaire un certain nombre de pro-priétés (voir section 1.1.3). Nous évaluons le schéma présenté dans la section pré-cédente pour vérifier qu’il respecte les conditions de sécurité.

(a) Secret des votes : dans le schéma de vote proposé tous les votes sont secrets.Preuve. le chiffrement ElGamal du candidat choisi par de l’électeur avec laclé publique des autorités de décompte rend confidentiel ce choix pour un at-taquant. obtenir cette information reviendrait à résoudre le problème du lo-garithme discret sur les courbes elliptiques ou à obtenir la clé privée dont lareconstruction nécessite la présence d’au moins t autorités parmi les n

(b) Éligibilité : Seuls les électeurs enregistrés peuvent voter.Preuve. l’étape d’identification qui est la toute première de la phase de voteempêche les acteurs non enregistrés d’accéder au système



(c) Pas de double vote : Impossibilité pour un électeur de voter deux fois lorsd’une même élection.Preuve. Notre schéma admet qu’un électeur vote plusieurs fois. Toutefois, unseul vote par électeur sera comptabilisé. Puisque les votes transmis avec lemême crédit sont supprimés après vérification de la validité du crédit mis àpart celui avec le crédit valide qui sera considéré lors du décompte final .

(d) Pas de Résultat Partiel (Équité) : personne n’obtient des résultats partielsdans notre schéma.Preuve. Un attaquant peut déchiffrer un vote uniquement s’il détient la cléprivée des autorités de décompte. Or obtenir cette clé reviendrait à résoudrele problème du logarithme discret sur les courbes elliptiques ou à obtenir laclé privée dont la reconstruction nécessite la présence d’au moins t autoritésparmi les n

(e) Vérifiabilité universelle : tout acteur est capable de vérifier l’exactitude durésultat final.Preuve. Le tableau de vote public et les preuves non interactives contribuentà le faire. Ainsi la collection de vote (somme de tous les votes uniques et va-lides) est vérifiable de même que le déchiffrement qui conduit aux résultatsfinaux.

(f) Précision : l’élection est précise si le vote ne doit pas être altéré, par consé-quent les résultats du vote ne doivent pas être modifiés en ajoutant des votesinvalides ou en changeant le contenu des bulletins par exemple (intégrité).Preuve. Lors de la transmission une preuve de rechiffrement est effectuée àchaque étape, afin d’assurer que le choix du votant n’a pas été modifié.

(g) Complétude : l’élection est complète si tous les votes valides sont comptabi-lisés et les votes non valides ne le sont pas.Preuve. Lors de l’élimination des doubles votes (phase de décompte) un testest effectué sur la validité du crédit ce qui empêche de supprimer des entréescontenant des votes valides.

(h) Receipt-freeness (Sans Reçu) : l’électeur ne peut pas prouver pour qui il avoté.Preuve. Le rechiffrement du vote par le mixnet empêche l’électeur de conser-ver une information (l’entier aléatoire α) utilisée lors du chiffrement. D’autrepart l’électeur est incapable de prouver à un attaquant que son crédit est va-lide et il est impossible pour l’attaquant de distinguer un vote valide d’un votenon valide.

(i) Résistance à la coercition : Nous venons de montrer que notre schéma estReceipt-freeness. Il est maintenant question de montrer qu’il protège de trois


3.3. ILLUSTRATION NUMÉRIQUE 63

attaques coercitives.

Preuve.– Attaque par randomisation : Dans notre schéma l’électeur accompagne son

vote d’une preuve de validité. Tous les votes avec une preuve invalide sontéliminés. Si un attaquant observe l’électeur et l’oblige à voter pour un can-didat aléatoire, ce vote sera probablement supprimé.

– Attaque par abstention forcée : elle est possible si l’attaquant peut savoirqui a voté ? Notre schéma protège contre cette attaque puisqu’il ne révèleaucune information sur l’identité des électeurs.

– Attaque par simulation : elle est possible si l’attaquant peut forcer l’élec-teur à lui révéler son crédit afin de voter à sa place. notre schéma offre lapossibilité à l’électeur de tromper l’attaquant en lui révélant un faux crédit.ce qui aura pour effet de créer un vote invalide..

Notre schéma est donc résistant à la coercition.

3.2.2.2 Limites

Nous observons toutefois quelques limites :

(1) Pas de vérifiabilité individuelle : Notre schéma n’offre pas la possibilité auxélecteurs de vérifier le contenu de leur vote après l’avoir émis. Nous sacrifionscette propriété au profit du receipt freeness.

(2) Le schéma proposé à ce niveau est approprié pour une élection à un nombre decandidat k ≤ 2 puisque le décompte des voix est complexe

3.3 Illustration numérique

3.3.1 Présentation de la plate forme SAGE ( System for Alge-bra and Geometry Experimentation)

La plateforme SAGE ( System for Algebra and Geometry Experimentation) estun logiciel mathématique libre destiné à la recherche et à l’enseignement en al-gèbre, géométrie, arithmétique, théorie des nombres, cryptographie, calcul scienti-fique et dans d’autres domaines apparentés. Le modèle de développement de SAGEcomme ses caractéristiques techniques se distinguent par un souci extrême d’ou-verture, de partage, de coopération et de collaboration. Il rassemble de nombreuxprogrammes et bibliothèques libres dans une interface commune basée sur le lan-gage de programmation Python.



SAGE est distribué sous licence libre, selon les termes de la GNU General Pu-blic License (GPL) version 2 ou ultérieure. Cette dernière autorise la copie, l’étude,la modification, l’amélioration et la distribution de SAGE et de son code source.SAGE intègre la plupart des logiciels open-source et offre également une interfaceavec les logiciels propriétaires Magma, Maple et Mathematica.

SAGE est gratuit et Open Source et son téléchargement se fait à partir du liensuivant : http://sagemath.org.

3.3.2 Modes d’utilisation

SAGE a trois modes d’utilisation :

(a) Il peut être utilisé en ligne de commande.

Pour lancer SAGE en ligne de commande, il faut entrer :

> sage

Vous verrez apparaitre :

--------------------------------------------------------------

| Sage Version 5.0.1, Release Date: 2012-06-10 |

| Type notebook() for the GUI, and license() for information.|

--------------------------------------------------------------

sage:

(b) Il peut exécuter des programmes interprétés ou compilés avec un compilateurCython, via un fichier *.py ou *.spyx .

(c) Le mode le plus convivial est l’interface graphique notebook. Ce mode fonc-tionne avec un mécanisme client-serveur et s’utilise avec un navigateur web.Ce dernier permet de partager les ressources d’une machine ou d’échangerdes feuilles de calcul worksheet. Il permet de programmer des fonctions etd’évaluer directement les expressions.

3.3.2.1 Composants de SAGE

SAGE contient un nombre important de logiciels et de bibliothèques spécialiséessous une même interface. Il intègre notamment :

– GAP le logiciel d’algèbre, le langage de calcul Octave, le logiciel de statistiqueR, le logiciel d’arithmétique pari/GP, le logiciel pour l’algèbre commutative, noncommutative et de manipulation de polynômes multivariés Singular, le logicielde calcul formel Maxima.


http://sagemath.org


– Il comprend aussi le logiciel GMP-ECM pour la factorisation des entiers en uti-lisant des courbes elliptiques, une librairie cryptographique généraliste Libg-crypt, ECLib pour l’énumération des courbes elliptiques, le logiciel de crypto-graphie OpenCDK, une librairie Python de cryptographie Python CryptographyTollkit (PyCrypto) qui implémente des fonctions de hachage et les algorithmescryptographiques à clé publique.

– Une interface pour les logiciels propriétaires Magma, Maple et Mathematica.

La liste complète des composants de Sage est disponible à l’adresse suivante :http ://sagemath.org/links-components.html.

3.3.3 Détails d’implémentation

Nous décrivons les différentes classes et fonction implémentées pour notre système

3.3.3.1 Classe Vote

Cette classe crée l’objet vote avec les fonctions suivantes :

– generate_key_pair : qui génère les clés publiques et privées de l’objet électeurself.private_key, self.public-key.sage: generate_public_key(self,10007,4,20)

(1009, Elliptic Curve defined by y^2 = x^3 + 4x + 20 over Finite

Field of size 10007, (5919:4268:1))

– encrypt : chiffre un message représenté par un point. Elle prend en entrée lemessage et la clé publique et renvoie un chiffré.sage: Alice = Vote(10007,4,20)

sage:x=372

sage:y=441

sage: encrypt(point, Alice.public_key)

((292 : 8254 : 1), (2829 : 7423 : 1)

– reencrypt : rechiffre le chiffré obtenu précédemment. Elle prend en entrée lechiffré, la clé publique et renvoie un nouveau chiffrésage: Alice = Vote(10007,4,20)

sage:x=372

sage:y=441

sage:reencrypt(encrypt(point, Alice.public_key),Alice.public_key)

((3644 : 6345 : 1), (3833 : 5853 : 1))

– decrypt : déchiffre le chiffré obtenu précédemment. Elle prend en entrée le chiffréet la clé privée et renvoie le message en clairsage: Alice = Vote(10007,4,20)

sage:x=372



sage:y=441

sage:print decrypt(encrypt(point, Alice.public_key),

Alice.private_key)

(372: 441 : 1)

– Test-egal : teste si deux chiffrés obtenus à partir d chiffrement ElGamal, sont deschiffrements d’un même message. Elle prend en entrée deux chiffrés et renvoiele chiffrement du point à l’infini si les deux message sont égaux et le chiffrementd’un autre point dans le cas contraire.sage: Alice = Vote(10007,4,20)

sage: test_egal(encrypt(point, Eregistrement.public_key),

reencrypt(v,Eregistrement.public_key))

((2234 : 6486 : 1), (6108 : 4734 : 1))

3.3.3.2 Classe Credit

Cette classe crée un objet crédit pour chaque électeur avec les fonctions suivantes :

– Map : fonction de hachage qui prend en entrée un x ∈ {0, 1}∗ et renvoie unélément du groupe E(Fp).sage: generate_public_key(self,10007,4,20)

(10007, Elliptic Curve defined by y^2 = x^3 + 4x + 20 over Finite

Field of size 10007, (5919 : 4268 : 1), (3820 : 9194 : 1))

sage: E=EllipticCurve(GF(10007),[4,20])

sage: m=E.cardinality()

sage: P=E.map(m,m,’test’)

sage: P

(0: 1 : 0)

– Sign : Elle prend en entrée le point renvoyé par Map et la clé privée et renvoieune signature.

– Aggregate : Prend en entrée les signatures obtenues précédemment et renvoiela somme de ces dernières.

3.3.3.3 Fonction Secret-share

Cette fonction est une implémentation du partage de clé de Shamir. Elle prend enentrée l’entier à partager, le nombre et les différentes parts , l’entier représentantle seuil et renvoie le polynôme aléatoire et la clé initialement partagée.

sage: p = next_prime(251)

sage: m = 248

sage: pieces = 5

sage: threshold =3



sage: shares(m,pieces,threshold)

(1, 47),(2, 34),(3, 209),(4, 58),(5, 95)

sage: P=recover( [(1, 88),(5, 150), (3, 30)] )

sage: print ’le polynôme est ’,P

le polynôme est 215*x^2 + 139*x + 248

sage: print ’Secret est =’, P(x=0)

Secret est = 248

3.3.4 Illustration numérique avec SAGE pour une élection àquatre candidats

Supposons que nous avons 8 autorités (3 d’enregistrements et 5 de décomptes), 10électeurs et 4 candidats.

3.3.4.1 Phase d’initialisation

Dans cette phase les paramètres du système sont initialisés :– Nous choisissons Une courbe elliptique E d’équation y2 = x3 +4x+20 (mod 10007)

avec p = 10007 et un point de base G de coordonnées (2, 6) d’ordre 2011.– Nous générons les clés des autorités de décompte pour un système cryptogra-

phique ElGamal distribué.– Nous choisissons la clé privée s = 248 et calculons la clé publique correspon-

dante h = [s]G = (5919, 4268)

– Nous exécutons la fonction secret-share partage (partage à seuil(3, 5)

– génération du polynôme secret P (x) = 215x2 + 139x+ 248 (mod 257)

– calcul des paires (i, si) = (i, P (i)) soit (1, s1) = (1, 88), (2, s2) = (2, 101),(3, s3) = (3, 30), (4, s4) = (4, 132), (5, s5) = (5, 150) et partage à Tj grâce aupartage de clé de Diffie- Hellman.

– Seuls 3 autorités sur les 5 seront nécessaires pour « reconstruire la clé privée.– Nous générons les clés des autorités d’enregistrement la clé privée SkR = n = 329

et la clé publique correspondante est PkR = [n]G = (8850, 665)

– Enregistrement des candidats cr et représentation de ces différents candidatscomme des points de E(Fp). Nos 4 candidats sont représentés par :

Tableau des candidatsNuméros Nom encodage

0 Abstention P0 = P (372,441)1 Candidat 1 P1 = [(10 + 1)]P = [11]P (7587,5187)2 Candidat 2 P2 = [(10 + 1)2]P = [121]P (4158,1719)3 Candidat 3 P3 = [(10 + 1)3]P = [1331]P (2057,5956)

Les informations suivantes sont publiques E, p, G, q, h = [s]G.



3.3.4.2 Phase d’enregistrement

L’électeur se fait enregistrer par les autorités d’enregistrement Rj avec j ∈ [1, 3]

dans un bureau d’enregistrement. ces autorités d’enregistrement transmettent àchaque électeur un crédit anonyme δ est généré par l’exécution de la class Créditde la manière suivante.

sage: Credit.generate_key_pair()

sage: pub = Credit.public_key()

sage: priv = Credit.private_key()

Les clés produites sont utilisées pour signer un message

sage: msg="Hello"

sage: m=E.cardinality()

sage: P= Credit.map(m,m,msg)

sage: signA1= Credit.sign(P, priv)

Les différentes signatures sauvegardées dans un fichier sont agrégées

sage: save (signA1, signature_file)

sage: s=load(signature_file)

sage: c=Credit.aggregate(s)

sage: c

(8909 : 9177 : 1)

Pour les 10 électeurs nous obtenons les valeurs suivantes :

Tableau des électeurs

Identifiant votant crédit(δi)1 V1 (3363 , 649 )2 V2 (8909 , 9177 )3 V3 (2637 , 6635 )4 V4 (3988 , 7365 )5 V5 (5331 , 9187 )6 V6 (2128 , 3659 )7 V7 (1840 , 4566 )8 V8 (942 , 7912 )9 V9 (1842 , 9216 )10 V10 (9445 , 3839 )

3.3.4.3 Phase de vote

Au cours de cette phase, chaque votant Vi construit son vote vi représenté par :



chiff T (Pr) = (ci1, ci2) = ([αi]G, [αi]h + Pr) où Pr ∈ {P0, P1, P2, P3} , chiffR(δi), ∆i =

[εi] δi. Pour un électeur Bob nous avons :

sage: Bob = Electeur(10007,4,20)

sage: encrypt(point, T.public_key)

((755 : 5751 : 1), (6282 : 4084 : 1)

Les votes de 10 électeurs sont donnés dans le tableau 3.2 ci dessous. Notons quenous permettons à certains électeurs de voter 2 ou 3 fois.

TABLEAU 3.2 – Valeurs numériques des votes

chiffrement candidat chiffrement créditci1 = [αi]G ci2 = [αi]h+ Pr [βi]G [βi]h+ δi ∆i = [εi] δi

1 (755 ,5751 ) (6282 ,4084) (8266 , 8509) (682 , 5185 ) (2052 , 9153 )2 (6398,7981) (79, 3699) (8452, 9255) (1501, 5053) (6499,6674)3 (292,8254) (2829, 7423) (1286, 6603) (6298, 8735) (738, 2180)4 (5328, 262) (6618, 5577) (2546, 1912) (952, 7400) (1284, 4271)5 (7233, 3289) (8155, 4502) (9936,7976) (3141, 623) (7039, 7012)6 (2758, 2407) (8290, 2404) (4213, 633) (1255, 3720) (9740, 2390)7 (1501, 4954) (4893, 515) (1536, 3970) (3467, 4297) (8266, 1498)8 (8494, 4038) (9804, 2913) (426, 6193) (3880, 1072) (7759, 8044)9 (7775, 706) (5617, 9050) (6455, 9969) (2291, 3627) (7088, 9113)10 (6656, 6110) (2433, 1433) (2885 : 7192) (8266, 1498) (5055, 7047)11 (2597, 2974) (6141, 3797) (7692, 1505) (2057, 4051) (738 ,2180)12 (5305, 503) (8728, 8426) (9127, 481) (3820, 9194) (738, 2180)13 (4349, 2593) (5463, 471) (7160, 8309) (7780, 1857) (1284, 4271)14 (9078, 2582) (5386, 9200) (5404, 6462) (9332, 4147) (6499, 6674)15 (2229, 6908) (8455, 9906) (1363, 6474) (8276, 19) (7039, 7012)



Lors de la transmission de ces votes, le système les rechiffres pour assurer lereceipt freeness. Sur le tableau de vote public, nous aurons donc les valeurs devotes rechiffrés tel qu’illustré dans le tableau 3.3 ci-dessous :

TABLEAU 3.3 – Valeurs des votes rechiffrés

rechiffrement candidat rechiffrement créditci1 = [γi]G ci2 = [γi]h+ Pr [λi]G [λi]h+ δi ∆i = [ωi] δi

1 (5787, 3794) (662, 1280) (3569, 53 ) (9086, 2549) (4681, 8556)2 (850, 3576) (7433, 7140) (4598, 8374) (9239, 7897) (2031, 7870 )3 (3644, 6345) (3833, 5853) (3013,3711) (4435,3965 ) (5755, 4552 )4 (9064, 5957) (161, 8646) (1048, 5603) (6409, 3499) (6836, 8203)5 (9167, 7773) (3093, 721) (5755, 4552) (216, 1262) (4453, 8742)6 (8601, 5258) (4130, 8767) (3985, 6905) (4732, 1991) (8839, 8576)7 (7170, 30) (2030, 8942) (2597, 7033) (4095, 5743) (3467, 5710)8 (6108, 4734) (4252, 7785) (6452, 5050) (3283, 7764) (9086, 7458)9 (8051, 9792) (6820,4660) (8671 ,1234) (9100, 8126) (150 , 9556)10 (4997, 8577) (8991, 8514) (1303,6131) (3675,3756) (6355, 5304)11 (439, 3284) (1228, 1351) (5100, 1175) (3031, 439) (5755, 4552)12 (2829,7423) (2234, 6486) (8671 ,1234) (4215, 6891) (5755, 4552)13 (3000, 3982) (8732, 5994) (7603, 3516) (9863, 1816 ) (6836, 8203)14 (6035, 3650) (8665, 2226) (8591,5200 ) (9830, 4351) (2031, 7870)15 (9402,9125) (1255,6287) (2714 , 4636) (9386 , 2769 ) (4453,8742)



3.3.4.4 Phase de décompte

– Les autorités de décompte recherchent les valeurs dupliquées de ∆i et éliminentles entrées où le vote est associé à un crédit anonyme non valide, par une Com-paraison des crédits anonymes i.e. qu’ils comparent les chiffrés de différents cré-dits à l’aide de la fonction test_egal et éliminent les entrées où le rechiffré ducrédit qui accompagne le vote d’un candidat ne correspond à aucun rechiffré decrédit enregistré par les autorités d’enregistrement. Le tableau 3.4 illustre cetteopération.

TABLEAU 3.4 – Élimination des double votes

rechiffrement candidat rechiffrement créditci1 = [γi]G ci2 = [γi]h+ Pr [λi]G [λi]h+ δi ∆i = [ωi] δi(5787, 3794) (662, 1280) (3569, 53 ) (9086, 2549) (4681, 8556)(850, 3576) (7433, 7140) (4598, 8374) (9239, 7897) (2031, 7870 )/////////(3644, ////////6345) /////////(3833, ////////5853) ////////////////(3013,3711) ///////////////(4435,3965//) /////////(5755, ///////4552 /)(9064, 5957) (161, 8646) (1048, 5603) (6409, 3499) (6836, 8203)/////////(9167, ////////7773) /////////(3093, //////721) /////////(5755, ////////4552) ///////(216,////////1262) /////////(4453, ////////8742)(8601, 5258) (4130, 8767) (3985, 6905) (4732, 1991) (8839, 8576)(7170, 30) (2030, 8942) (2597, 7033) (4095, 5743) (3467, 5710)(6108, 4734) (4252, 7785) (6452, 5050) (3283, 7764) (9086, 7458)(8051, 9792) (6820,4660) (8671 ,1234) (9100, 8126) (150 , 9556)(4997, 8577) (8991, 8514) (1303,6131) (3675,3756) (6355, 5304)(439, 3284) (1228, 1351) (5100, 1175) (3031, 439) (5755, 4552)////////////////(2829,7423) /////////(2234, ////////6486) ////////(8671 /////////,1234) /////////(4215, ////////6891) /////////(5755, ////////4552)/////////(3000, ////////3982) /////////(8732, ////////5994) /////////(7603, ////////3516) /////////(9863, ///////1816 /) /////////(6836, ////////8203)/////////(6035, ////////3650) /////////(8665, ////////2226) ///////////////(8591,5200//) /////////(9830, ////////4351) /////////(2031, ////////7870)(9402,9125) (1255,6287) (2714 , 4636) (9386 , 2769 ) (4453,8742)

Nous obtenons un tableau des votes uniques et valides représenté dans le ta-bleau 3.5

TABLEAU 3.5 – Tableau de vote unique et valide

rechiffrement candidat rechiffrement créditci1 = [γi]G ci2 = [γi]h+ Pr [λi]G λih+ δi ∆i = [ωi] δi(5787, 3794) (662, 1280) (3569, 53 ) (9086, 2549) (4681, 8556)(850, 3576) (7433, 7140) (4598, 8374) (9239, 7897) (2031, 7870 )(9064, 5957) (161, 8646) (1048, 5603) (6409, 3499) (6836, 8203)(8601, 5258) (4130, 8767) (3985, 6905) (4732, 1991) (8839, 8576)(7170, 30) (2030, 8942) (2597, 7033) (4095, 5743) (3467, 5710)(6108, 4734) (4252, 7785) (6452, 5050) (3283, 7764) (9086, 7458)(8051, 9792) (6820,4660) (8671 ,1234) (9100, 8126) (150 , 9556)(4997, 8577) (8991, 8514) (1303,6131) (3675,3756) (6355, 5304)(439, 3284) (1228, 1351) (5100, 1175) (3031, 439) (5755, 4552)(9402,9125) (1255,6287) (2714 , 4636) (9386 , 2769 ) (4453,8742)



– Sommer tous les chiffrés des choix des candidats Pr contenus dans le tableau desvotes uniques et valides. Soit :

C = (c1, c2)

=

(10∑i=1

ci1,

10∑i=1

ci1

)

=

([10∑i=1

(γi)

]G,

[10∑i=1

(γi)

]h+

(3∑r=0

[dr]Pr

))

Soit c1 =∑10

i=1 ci1 = (1556, 6700) et c2 =∑10

i=1 ci2 = (9839, 3723)

– Déchiffrer les votes.Le déchiffrement s’effectue par (J = {T1, ..., T3}) i.e 3 autorités parmi les 5.Pour déchiffrer ces 3 autorités de décompte partagent les paires (j, sj) et cal-culent [s] c1 = [P (0)] c1 de la manière suivante :

[P (0)] c1 =

3∑i=1

si∏

1≤i≤t

i 6=j

j

j − i

c1 =〉 [P (0)] c1 =

[ 3∑i=1

si

]c1

∏1≤i≤t

i 6=j

j

j − i

supposons que nous avons les parts des 3 premières autorités (1, 88), (2, 101),(3, 30). Nous calculons

[P (0)] c1 = [s1] c12·3

(2−1)(3−1)+ [s2] c1

1·3(1−2)(3−2)

+ [s3] c11·2

(1−3)(2−3)

= [88] c1

(62

)+ [101] c1

(3−1

)+ [30] c1 mod 257

= [264] c1 − [46] c1 + [30] c1 = [248] c1

= (6163, 6689)

Après le calcul de [s] c1 = (6163, 6689), le déchiffrement de la somme des votess’obtient en calculant c2 − [s] c1 = (3647, 9144).

– Compter les voix. Le décompte des voix découle du calcul de la somme∑3

r=0 [dr]Pr

où les dr sont des éléments de 1,2,...,10. En comparant le résultat à celui ducalcul de c2− [s] c1. Pour notre exemple après calcul nous obtenons

∑3r=0 [dr]Pr =

[3]P0 + [2]P1 + [4]P2 + P3 = (3647, 9144)


3.4. SYNTHÈSE DE QUELQUES RÉSULTATS 73

3.3.4.5 Phase de publication des résultats

Après le décompte des voix obtenues par les différents candidats et la vérifica-tion, les résultats sont publiés

Tableau des résultatsNuméros Nom nombre de voix

0 Abstention 31 Candidat 1 22 Candidat 2 43 Candidat 3 1

Le vainqueur est le candidat 2.

3.4 Synthèse de quelques résultats

Nous présentons dans cette partie quelque résultats important :

(a) Le schéma proposé satisfait la propriété de résistance à la coercition puisquenous mettons en place un système capable d’accepter des crédits non valides.En effet, un électeur en cas d’attaque vote non valide et lorsqu’il est mis horsdanger vote valide ce qui n’est pas le cas dans le schéma de Porkodi et al.

(b) Le receipt- frenness s’obtient dans notre schéma par l’utilisation d’un mix-net à rechiffrement universellement vérifiable pour rechiffrer les votes alorsque cette propriété n’est pas assurée dans le schéma de Porkodi et al.

(c) la complétude est assurée par la comparaison effectuée sur tous les votesprovenant d’un même électeur. En effet, avant de supprimer les multiplesvotes nous effectuons un test qui permet d’identifier les votes non valides cequi n’est pas le cas dans le schéma de Juel et al.


CONCLUSION GÉNÉRALE

L’objectif de ce travail était d’élaborer un système de vote électronique résistantà la coercition. Ce système devait utiliser un crédit anonyme et répondre aux exi-gences avancées d’un vote électronique à savoir : la résistance à la coercition, lereceipt-freeness et la vérifiabilité.

Le vote électronique est un système cryptographique qui assure plusieurs ser-vices de sécurité. Pour cela, il utilise plusieurs primitives cryptographiques. Cesprimitives cryptographiques et les différents services de sécurité qu’elles assurentont été présentés, puis nous avons présenté le schéma de vote publié dans [13] etmontrer que celui ci n’assure pas la propriété de complétude. De même, le schémade vote publié dans [16] a été étudié et nous avons montré qu’il n’est pas résistantà la coercition. Nous avons proposé un schéma de vote électronique qui utilise descryptosystèmes sur les courbes elliptiques par exemple chiffrement ElGamal dis-tribué version elliptique et un crédit anonyme construit à partir d’une modificationde la signature agrégée publiée dans [3]. La sécurité de notre schéma repose surle problème du logarithme discret sur les courbes elliptiques. En effet, le schémade vote proposé est le résultat d’une combinaison des systèmes cryptographiquesprésentés dans ce document. La plate-forme SAGE nous a permis d’illustrer nu-mériquement les différentes phases de ce schéma. Cependant, le schéma proposén’offre pas aux électeurs la possibilité de vérifier individuellement le contenu deleurs votes et le décompte des voix conduit au problème du sac à dos.

En perspective, il sera question : d’utiliser algorithme de résolution du problèmede sac à dos éfficient afin de réduire le temps utilisé lors du décompte, d’implémen-ter et de mettre en oeuvre un prototype du schéma proposé, de faire une preuvede sécurité formelle de ce schéma à l’aide de méthodes formelles qui permettentune bonne analyse des protocoles cryptographique, de gérer les attaques dues àl’utilisation d’Internet, d’adapter le système de manière à être utilisé sur des équi-pements légers tels que les téléphones en lieu et place d’ordinateurs pour effectuerle vote d’autant plus que ces équipements sont plus accessibles au grand publiccontrairement aux ordinateurs.


Bibliographie

[1] B. Adida : Advances in cryptographic voting systems, PhD thesis, Massachu-setts Institute of Technology, 2006.

[2] R. Araujo : On Remote and Voter-Verifiable Voting, thesis, Technischen Uni-versität Darmstadt, 2008.

[3] D. Boneh, C. Gentry, B. Lynn, and H. Shacham : Aggregate and verifiablyencrypted signatures from bilinear maps, In E. Biham, editor, Proceedings ofEurocrypt 2003, volume 2656 of LNCS, pages 416-32. Springer-Verlag, 2003.

[4] J. Clark : Democracy Enhancing Technologies : Toward deployable and incoer-cible E2E elections, thesis, University of Waterloo, Ontario, Canada, 2011.

[5] F. Connes : La sécurité des systèmes de vote, thèse, Université Panthéon-AssasParis II- École doctorale de droit public, 2009.

[6] R. Cramer, R. Gennaro and B. Schoenmakers : A secure and optimally efficientmulti-authority election scheme. Advances in Cryptology , Lecture Notes inComputer Science 1233, pp. 103–118. Springer-Verlag, 1997.

[7] S. Delaune, F. Klay and S. Kremer : Spécification du protocoles de vote électro-nique, Rapport technique prouvé, 2005.

[8] R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin : Secure Distributed KeyGeneration for Discrete-Log Based Cryptosystems, Eurocrypt’99, 1999.

[9] R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin : Secure Applications of Pe-dersen’s Distributed Key Generation Protocol, Topics in Cryptology 2003, MarcJoye editor, Lecture Notes in Computer Science 2612,pp. 373–390. SpringerBerlin / Heidelberg,2003.

[10] S. S. Godia : An electronic voting platform with elliptic curve criptography,Treball final de carrera, Universitat de Lleida, 2011.

[11] D.Hankerson, A.Menezes, and S.Vanstone : Guide to Elliptic Curve Crypto-graphy, Springer, 2004.

[12] M. Joye : Introduction élémentaire à la théorie des courbes elliptiques, Techni-cal report, CG-1995/1, UCL Crypto Group, Louvain-la-Neuve, 1995.


BIBLIOGRAPHIE 76

[13] A. Juels, D. Catalano and M. Jakobsson : Coercion-resistant electronic elec-tions, ACM Workshop On Privacy In The Electronic Society, Cryptology ePrintArchive, Report 2002/165, 2005.

[14] B. Lee : Zero-Knowledge Proofs, Digital Signature Variants, and Thier appli-cations, PhD thesis, School of Engineering, Information and CommunicationsUniversity, Daejon, Korea 2002.

[15] B. Meng : A Secure Internet Voting Protocol Based on Non-interactive DeniableAuthentication Protocol and Proof Protocol that Two Ciphertexts are Encryp-tion of the Same Plaintext , Journal of Networks, VOL. 4, No. 5, July 2009.

[16] C. Porkodi, R. Arumuganathan and K. Vidya : Multi-authority Electronic Vo-ting Scheme Based on Elliptic Curves India International Journal of NetworkSecurity, Vol.12, No.2, PP.84-91, 2010.

[17] Z. Rjaskova : Electronic Voting Schemes, PhD thesis, Comenius University,Bratislava, 2002.

[18] SAGE Mathematical Software, Version 5.1, http ://www.sagemath.org

[19] SEC1 : Elliptic Curve Cryptography Standard for Efficient Cryptography,TheSECG Group, 2000.

[20] M.Z. Seet : Elliptic Curve Cryptography : Improving the Pollard-Rho Algo-rithm, Masters Thesis, School of Mathematics and Statistics, The Universityof New South Wales, 2007

[21] M. J. Smart : Anonymity VS. Traceability : Revocable anonymity in remoteelectronic voting protocol, thesis, University of Birmingham, United Kingdom2012.

[22] W. Smith : Cryptography meets voting, Temple University, 2005.

[23] M. Stennier : Etude, analyse et prototype d’implémentation d’un système devote à distance, Master’s thesis, Université Libre de Bruxelles, Belgium, 2011.

[24] S. Weber : A Coercion-Resistant Cryptographic Voting Protocol - Evaluationand Prototype Implementation, PhD thesis, Darmstadt University of Techno-logy, Department of Computer Science, 2006.
