Recherche & développement Protocole de vote E-Poll Réunion de lancement AVOTÉ 18 janvier 2008, Cachan Jacques Traoré

recherche & développement

Protocole de vote E-PollRéunion de lancement AVOTÉ

18 janvier 2008, Cachan

Jacques Traoré

Réunion de lancement AVOTÉ – 18 janvier 2008 – p2 Orange Labs - Research & Development

Le Projet E-Poll

s E-Poll, projet européen de vote électronique : QMinistère de l'intérieur français, France Télécom, Siemens, Ministère de

l'intérieur italien et Vodafone

s Vote assisté par ordinateur, mais dans un bureau de vote

pour le vote institutionnel

s Pas de bouleversement des usages

s Nomadisme autorisé : vote hybride

s Authentification biométrique

s Expérimentations :QVotes doublons : Avellino, Mérignac (Présidentielles 2002), Campobasso,

Vandoeuvre (Législatives 2002), Issy les Moulineaux (Référendum 2005)

QVotes exclusifs sur systèmes E-Poll : Cremona, Ladispoli, Czestochova,

Ladispoli (sept.2004), Université de Lyon II et Nantes (déc. 2004)


Les UV mix-net en pratique

Proving a Shuffle [Furokawa-Sako 01] 36nk

A Verifiable Secret Shuffle [Neff01] 16nk

Optimistic Mixing [Golle et al. 02]*

Fair Blind Signatures and hybrid mix-net [Canard, Gaud,

Traoré 06]

6 + 12k

(13k)

Nombre d'exponentiations modulaires requises pour générer la preuve complète (pour n bulletins et k mélangeurs).

*cassé (Abe, ACISP’03)

Il faut 4 heures pour dépouiller 100 000 bulletins avec le système de Furokawa-Sako (k = 3, p = 1024, q = 160)

La plupart de ces systèmes sont brevetés…


Le Protocole de FOO en pratiques Sensus et EVOX

Q Fujioka, Okamoto, Ohta, “A Practical Secret Voting Scheme for Large Scale Elections”, Auscrypt’92

Qpas de résultats partiels

Q3 étapes pour voter (ne satisfait pas la propriété de "vote and go")

Q Sensus: Washington University http://lorrie.cranor.org/voting/sensus

Q EVOX : MIT, http://theory.lcs.mit.edu/~cis/voting/voting.html

s Votopia Q Ohkubo, Miura, Abe, Fujioka et Okamoto, "An improvement of a practical secret voting scheme", ISW'99

QProjet Coréen - Japonais : NTT, Samsung, Université de Tokyo, IRIS…

Q Expérimentation lors de la coupe du monde 2002

Q Vote en deux étapes; satisfait la propriété de "vote and go"

Q Quelques failles de sécurité… [Canard, Gaud, Traoré, Financial Cryptography 2006]


Voting Results

3662 voters: 3474 from Korea and 90 from Japan


Les acteurs

possèdent des clés de signature

Authentifie les votants et délivre des signatures aveugles

Déchiffrent et permutent les bulletins

Déchiffrent de manière distribuée les bulletins

Collecte les bulletins

Voters

Admin Server

Mix Servers

Scrutateurs

Ballot Box


System Overview

BBServer

Admin Server

Mix Servers

Tally Servers

Voter

DB

DB

(1) Blind Sig

(3) Mixing

(4) Tallying

(2) Ballot Casting

(5) Counting Results


Phase de vote (1)

Mrs Smith

Electoral List

Mr DupondMr BakerMr Durand..Mrs Smith

SK

PK

Admin Server

Bush

N°56422

= Encryption with PK of the talliers

Bush

N°56422

AS

Bush

N°56422

X

AS

Bush

N°56422


Dépôt du bulletin

Mrs Smith

Bush

N°56422

AS

Mix 1 Mix 2

Ballot Box

EPK2[vote]== EPK1[EPK2[vote]]

• Analogie avec le vote par correspondance

Smith


Alice

Bob

Carla

N°33786 Kerry

AS

N°56789 Bush

AS

N°12378 Bush

AS

Ballot Box List L

Alice

Bob

Carla

Dépouillement (I)

Mix 1

Mix 2


Dépouillement (cas 1)

N°33786 Kerry

AS

N°56789 Bush

AS

N°12378 Bush

AS

List L

Tous les bulletins portent la signature de AS et les signatures sont valides

Distributed Decryption N°33786

Kerry

N°56789 Bush

N°12378 Bush

Résultats


Alice

Bob

Carla

N°33786 Kerry

AS

N°56789 Bush

AS

N°12378 Bush

AS

List L

Alice

Bob

Carla

Back Tracing

Alice

Bob

Carla

A signature is invalid !

Mix 1 Mix 2

Proof

Proof

Si un mix a triché, il est exclu du système !

Si un votant a déposé un bulletin invalide, son bulletin est retiré de l'urne


Failles du protocole Votopia

Alice

Bill

Carla

complicedu Mix 1Mix 1

Alice est membre du parti X

Je ne vais pas déposer

mon bulletin

valide dans l'urne

N°33786 Kerry

AS

N°45678 Kerry

AS

N°12378 Bush

AS

List L


ExempleSupposons qu'il y ait :

- 200 votants

- Mix 1 a 9 complices

- Mix 1 supporte Bob.

AllyBobcandidate

du parti Xcandidatdu parti Y

Sondage d'opinions

52% 48%

En utilisant une des 2 failles

49.7% 50.3%


Contre-mesures possibles

s Demander aux votants de participer au dépouillementQContradiction avec la propriété de "vote and go"QDifficilement imaginable en pratique

s Demander au Mix 1 de prouver qu'il a correctement déchiffré et brassé les bulletinsQne marche pas en cas de collusion du Mix 1 et du Mix 2QLe schéma resterait vulnérable à une "randomization attack"

s Utiliser un mix net "universellement vérifiable"QQuel serait l'intérêt d'utiliser des signatures aveugles dans ce cas ?

s Notre solution : utiliser des signatures aveugles équitables


Modèle d'un schéma de signature aveugle équitable

(message, signature) Vue du protocolenon-corrélable

Signature Tracing

Session Tracing

Autorité de révocation

Utilisateur Signataire

Protocole de signature


Signatures aveugles équitables: sécurité.

Q Intraçabilité prouvé dans le modèle de l'oracle aléatoire sous l'hypothèse

DDH.

Q One-more Unforgeability prouvé dans le modèle de l'oracle aléatoire sous l'hypothèse du

"Strong-RSA"

Q Révocation – Il est 'impossible" de contourner les mécanismes de traçage prouvé dans le modèle de l'oracle aléatoire sous l'hypothèse du

"Strong-RSA"

Modèle de sécurité + Schéma prouvé sûr dans ce modèle : Hufschmitt, Traoré, Pairing'07


Phase de vote (1)

Jouent également le rôle de 'mélangeurs'

Scutateurs

Voter

Bush

N°56422

Chiffre son bulletin en utilisant les clés des scrutateurs

Obtient une signature aveugle équitable de son bulletin

AS


Dépôt du bulletin

Mrs Smith

Mix 1 Mix 2

Ballot Box

• Analogie avec le vote par correspondance

AS

EPK2[vote]== EPK1[EPK2[vote]]Smith

The anonymity of the Fair Blind Sig of "absentee" voters is revoked!


Alice

Bob

Carla

Ballot Box List L

Alice

Bob

Carla

Dépouillement (I)

Alice

Bob

Carla

Mix 1

Mix 2

AS

AS

AS


Dépouillement (cas 1) Tous les bulletins portent la signature de AS et les signatures sont valides

N°33786 Kerry

N°56789 Bush

N°12378 Bush

RésultatsList L

AS

AS

AS

les scrutateurs révèlent leur clé privée !


Alice

Bob

Carla

Alice

Bob

Carla

Back Tracing (I)

Alice

Bob

Carla

Mix 1 Mix 2

Proof

Proof

AS

AS

AS

List L

Si une signature est invalide, révoquée ou dupliquée

Si un votant a déposé un bulletin invalide, son bulletin est retiré de l'urne On lève l'anonymat de la signature aveugle qu'il a demandée.


Back Tracing (II)

Alice

Bob

Carla

Alice

Bob

Carla

Alice

Bob

Carla

List L

AS

AS

AS

If a mix server cheats. We retrieve all the private keys of the mix-servers.

If penalties for cheating are severe this will preclude any attempt!

N°33786 Kerry

N°56789 Bush

N°12378 Bush

Results

Decrypt,

permute,

and prove

correct

Decrypt using the revealed

keys


E-Poll en pratiques Outils cryptographiques :

QPKI: FT PKI Certatoo/Applatoo

QMix-net: nous avons utilisé le "mix-net hybride" d'Abe et Ohkubo (Asiacrypt'01)

QFair Blind signature scheme : nous avons utilisé le schéma de Gaud et Traoré (Financial

Crypto 2003)

s Expérimentations lors d'élections étudiantes (décembre 2004) QUniversités de Nantes et Lyon IIQ10 000 votantsQTous les bulletins étaient valides ! (nous n'avons pas eu besoin de lancer la procédure

de "Back Tracing")

s Expérimentation lors du référendum sur la constitution européenneQVille d'Issy-les-MoulineauxQ1 000 votantsQTous les bulletins étaient valides !


Conclusion

s Le protocole de vote E-poll appartient à la catégorie des "Optimistic mix-net based voting protocol"QSi les mix-net sont honnêtes, le dépouillement est extrêmement rapideQSi un mix triche, le dépouillement prend beaucoup plus de temps (utilisation d'un mix-net universellement vérifiable)

s E-Poll s'avère plus efficace que les autres systèmes du même type (confirmé en pratique)

Documents

Recherche & développement Protocole de vote E-Poll Réunion de lancement AVOTÉ 18 janvier 2008, Cachan Jacques Traoré