Brevet FR2842680A1 — publié le 20040123

PROCEDE DE SIGNATURE DE LISTE ET APPLICATION AU VOTE ELECTRONIQUE. La présente invention concerne le domaine général de la sécurité des services accessible par un réseau de transmission de données numériques, et plus précisément le domaine de la signature électronique. Elle s'applique notamment, mais non exclusivement au vote électronique ou encore à la pétition électronique. La signature électronique d'un message met en oeuvre un mécanisme relevant de la cryptographie dite à clé publique: le signataire qui possède une clé secrète ou privée et une clé publique associée, peut produire une signature de message à l'aide de la clé secrète. Pour vérifier la signature, il suffit de disposer de la clé publique. Dans certaines applications comme le vote électronique, le signataire doit pouvoir rester anonyme. A cet effet, on a mis au point ce que l'on appelle la 20 signature électronique anonyme permettant à l'aide d'une clé publique de déterminer si le signataire d'un message possède certains droits (droit de signer le message, droit de posséder la clé secrète ayant été utilisée pour signer le message, etc.), tout en préservant l'anonymat du signataire. En outre, dans les applications de vote ou de pétition électronique, chaque personne autorisée ne doit pouvoir signer qu'une seule fois. Parmi les signatures anonymes, il existe également ce que l'on appelle la signature aveugle permettant à une personne d'obtenir la signature d'un message d'une autre entité, sans que celle-ci ait à connaître le contenu du 30 message et puisse établir plus tard le lien entre la signature et l'identité du signataire. Cette solution de signature aveugle nécessite donc l'intervention d'une entité intermédiaire qui produit les signatures. Dans les applications comme le vote ou la pétition électronique, cette solution fait intervenir une autorité habilitée qui signe le vote de chaque électeur ou la pétition pour chaque pétitionnaire. On a également proposé le concept de signature de groupe qui permet à chaque membre d'un groupe de produire une signature telle qu'un vérificateur - 2 possédant une clé publique adéquate peut vérifier que la signature a été émise par un membre du groupe sans pouvoir déterminer l'identité du signataire. Ce concept est par exemple décrit dans le document: [1] "A Practical and Provably Secure Coalition-Resistant Group Signature Scheme" de G. Ateniese, J Camenisch, M. Joye et G. Tsudik, in M. Bellare, Editor, Advance in Cryptology - CRYPTO 2000, vol. 1880 of LNCS, p. 255270, Springer-Verlag 2000. Cependant, dans ce concept, une autorité de confiance peut lever à tout moment cet anonymat et déterminer l'identité d'une personne du groupe ayant émis une 10 signature. En outre, ce type de signature est dit "non reliable", c'est-à-dire qu'il ne permet pas de déterminer si oui ou non deux signatures ont été émises par la même personne sans lever l'anonymat de la signature. Les signatures de groupe sont utilisées dans de nombreuses applications, telles que la vente aux enchères électronique, la monnaie électronique ou encore le vote électronique. La 15 signature de groupe ne convient pas parfaitement à cette dernière application puisqu'elle autorise une autorité de confiance à accéder à l'identité d'un signataire, et ne permet pas de relier deux signatures émises par une même personne sans déterminer l'identité du signataire. En outre, le document [1] ne prévoit pas de processus de révocation d'un membre du groupe. Pour remédier à ce dernier inconvénient, le document [2] "Efficient Revocation of Anonymous Group membership Certificates and Anonymous Credentials" de J. Camenisch et A. Lysysanskaya, publié par Cryptologie ePrint Archive IACR. 2002, prévoit d'ajouter à ce concept un processus de révocation (ce document 25 sera aussi publié par M. Jung, Editor CRYPTO 2002, Springer-Verlag 2002). Toutefois, cette solution n'apporte pas de solution aux problèmes de la préservation de l'anonymat du signataire et de "reliabilité" de deux signatures. Dans une application de vote électronique, il est en outre nécessaire pour 30 assurer une sécurité se rapprochant au maximum du vote traditionnel, de garantir les propriétés suivantes. Nul ne doit être capable de connaître même partiellement les résultats du scrutin avant sa clôture. Tout le monde doit pouvoir se convaincre de la validité du résultat final du scrutin. Enfin, une autorité habilitée doit être capable de retirer ou de révoquer le droit de vote d'une personne. Qu'il s'agisse du vote hors ligne, c'est-à-dire de l'utilisation d'une machine à voter électronique installée dans un bureau de vote, ou du vote en ligne, c'est-à- -3 dire à distance, via le réseau Internet par exemple, les systèmes proposes actuellement, utilisant une signature de groupe telle que décrite dans le document [1] et complétée dans le document [2], ne remplissent pas ces conditions, mis à part la révocation du droit de signature. Par ailleurs, l'application du concept de signature aveugle au vote électronique est une solution dont la mise en oeuvre est lourde, car elle oblige l'électeur à se connecter plusieurs fois à chaque élection. En outre, si le scrutin se passe mal, on ne peut pas déterminer qui en est le responsable: un électeur ou l'organisateur du scrutin. On a également proposé, notamment dans le document [3] "Untraceable Electronic Mail Return Addresses and Digital Pseudonym" de D. Chaum, ACM 1981, le concept de réseaux mélangeurs, chaque mélangeur étant une fonction 15 produisant une liste de nombres déchiffrés à partir d'une liste de nombres chiffrés, tout en cachant la correspondance entre les nombres chiffrés et les nombres déchiffrés. Appliquée au vote électronique, cette technique présente l'inconvénient majeur de ne pas permettre de vérifier la validité d'un vote sans compromettre le secret de celui-ci. Dans le document [4] "A Secure and Optimal Efficient Multi-Authority Election Scheme", de Cramer, Gennaro, et Schoenmakers, Eurocrypt'97, LNCS - Springer-Verlag, il est décrit ce que l'on appelle le chiffrement homomorphe permettant d'effectuer des calculs de base sur des nombres chiffrés. Les solutions basées sur ce procédé ne sont cependant pas applicables aux scrutins impliquant un grand nombre d'électeurs. La présente invention a pour but de supprimer cet inconvénient. Cet objectif est atteint par la prévision d'un procédé de signature de liste comprenant au moins: - une phase d'organisation consistant pour une autorité de confiance à définir des paramètres de mise en oeuvre d'une signature électronique anonyme, dont une clé privée et une clé publique correspondante, - une phase d'enregistrement de personnes dans une liste de membres autorisés à générer une signature électronique propre aux membres de la liste, au cours 35 de laquelle chaque personne à enregistrer calcule une clé privée à l'aide de paramètres fournis par l'autorité de confiance et de paramètres choisis aléatoirement par la personne à enregistrer, et l'autorité de confiance délivre à chaque personne à enregistrer un certificat de membre de la liste, -4 - une phase de signature au cours de laquelle un membre de la liste génère et émet une signature propre aux membres de la liste, cette signature étant construite de manière à contenir une preuve que le membre de la liste ayant émis la signature, connaît un certificat de membre de la liste, et - une phase de vérification de la signature émise comprenant des étapes d'application d'un algorithme prédéfini pour mettre en évidence la preuve que la signature a été émise par une personne en possession d'un certificat de membre de la liste. Selon l'invention, ce procédé comprend en outre une phase de définition d'une séquence consistant pour l'autorité de confiance à générer un numéro de séquence à utiliser dans la phase de signature, une signature générée durant la phase de signature comprenant un élément de signature qui est commun à toutes les signatures émises par un même membre de la liste avec un même numéro de 15 séquence et qui contient une preuve que le numéro de séquence à été utilisé pour générer la signature, la phase de vérification comprenant en outre une étape de vérification de la preuve que le numéro de séquence a été utilisé pour générer la signature. Selon un mode de réalisation de l'invention,, la phase d'organisation comprend la définition d'un paramètre commun dépendant de la composition de la liste, la phase d'enregistrement d'une personne dans la liste comprenant la définition d'un paramètre propre à la personne à enregistrer qui est calculé en fonction du paramètre dépendant de la composition de la liste et qui est intégré au certificat 25 remis à la personne, la phase d'enregistrement comprenant une étape de mise à jour du paramètre commun dépendant de la composition de la liste, le procédé comprenant en outre une phase de révocation pour retirer un membre de la liste, consistant à modifier le paramètre commun dépendant de la composition de la liste, pour tenir compte du retrait du membre de la liste, et une phase de mise à 30 jour des certificats des membres de la liste pour tenir compte de modifications de la composition de la liste. Selon un mode de réalisation de l'invention, une signature propre à un membre de la liste et possédant le certificat [Ai, e1] comprend des paramètres TI, T2, T3 tels que: T1 = Aib' (mod n), T2 = go' (mod n), T3 = geihm (mod n), wo étant un nombre choisi aléatoirement lors de la phase de signature, et b, g, h et n étant des paramètres généraux de mise en oeuvre de la signature de groupe, tels que les paramètres b, g et h ne peuvent pas se déduire les uns des autres par des fonctions d'élévation de puissance entière modulo n, de sorte que le nombre Ai, et donc l'identité du membre de la liste possédant le certificat [Ai, e1] ne peut pas se déduire d'une signature émise par le membre. De préférence, le numéro d'une séquence utilisé pour générer une signature de liste est calculé en fonction d'une date de début de séquence. Avantageusement, la fonction de calcul du numéro d'une séquence est de la forme: F(d) = (H(d))2 (mod n) dans laquelle H est une fonction de hachage résistante aux collisions, d est la 15 date de début de la séquence, et n est un paramètre général de mise en oeuvre de la signature de groupe. Selon un mode de réalisation de l'invention, une signature émise par un membre de la liste contient un paramètre qui est calculé en fonction du numéro de séquence et de la clé privée du membre signataire. Selon un mode de réalisation de l'invention, le paramètre T4 d'une signature émise par un membre de la liste et dépendant du numéro de séquence m et de la clé privée xi du membre signataire est obtenu par la formule suivante: T4= mxi (mod n) n étant un paramètre général de mise en oeuvre de la signature de groupe, et la signature comprenant la preuve que le paramètre T4 a été calculé avec la clé privée xi du membre de la liste qui a émis la signature. L'invention concerne également un procédé de vote électronique comprenant une phase d'organisation des élections, au cours de laquelle une autorité organisatrice procède à la génération de paramètres nécessaires à un scrutin, et attribue à des scrutateurs des clés leur permettant de déchiffrer et vérifier des bulletins de vote, une phase d'attribution d'un droit de signature à chacun des 35 électeurs, une phase de vote au cours de laquelle les électeurs signent un bulletin de vote, et une phase de dépouillement au cours de laquelle les scrutateurs vérifient les bulletins de vote, et calculent le résultat du scrutin en fonction du contenu des bulletins de vote déchiffrés et valides. - 6 Selon l'invention, ce procédé met en oeuvre un procédé de signature de liste tel que défini ci-avant, pour signer les bulletins de vote, chaque électeur étant enregistré comme membre d'une liste, et un numéro de séquence étant généré pour le scrutin, pour détecter si un même électeur a émis ou non plusieurs bulletins de vote pour le scrutin. Selon un mode de réalisation de l'invention, la phase d'organisation comprend la remise à chaque scrutateur d'une clé publique et d'une clé privée, les bulletins de vote étant chiffrés à l'aide d'une clé publique obtenue par le produit 10 des clés publiques respectives de tous les scrutateurs, et la clé privée de déchiffrement correspondante étant obtenue en calculant la somme de clés privées respectives de tous les scrutateurs. Avantageusement, le chiffrement des bulletins de vote est effectué à l'aide d'un algorithme de chiffrement probabiliste. Selon un mode de réalisation de l'invention, les bulletins de vote émis par les électeurs sont stockés dans une base de données publique, le résultat de la vérification et du dépouillement de chaque bulletin de vote étant stocké dans la 20 base de données en association avec le bulletin de vote, et la clé privée de déchiffrement des bulletins de vote étant publiée. Un mode de réalisation préféré de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels: La figure 1 représente un système permettant la mise en oeuvre des procédés de signature de liste et de vote électronique, selon l'invention; Les figures 2 à 8 illustrent sous la forme d'organigrammes les 30 différentes procédures qui sont exécutées conformément aux procédés de signature de liste et de vote électronique, selon l'invention. La présente invention propose un procédé de signature de liste dans lequel toutes les personnes autorisées, c'est-à-dire appartenant à la liste, peuvent 35 produire une signature qui est anonyme, et n'importe qui est capable de vérifier la validité de la signature sans avoir accès à l'identité du membre de la liste qui a signé. Un tel procédé peut être mis en oeuvre dans le système représenté sur la figure 1. Ce système comprend des terminaux 2 mis à la disposition des utilisateurs et connectés à un réseau de transmission 5 de données numériques, tel que le réseau Internet. Chaque terminal 2 est avantageusement connecté à un lecteur 8 de carte à puce 7. Par le réseau 5, les utilisateurs peuvent se connecter à un serveur 6 donnant accès à des informations par exemple stockées dans une base de données 4. Ce système comprend également un calculateur 1 d'une autorité de confiance qui délivre notamment les cartes à puces 7 aux utilisateurs. Le procédé de signature de liste selon l'invention reprend dans le procédé de signature de groupe décrit dans le document référencé [1], les procédures suivantes: - une procédure d'organisation d'une d'un groupe de signataires, qui consiste à mettre en place les différents paramètres et clés publiques nécessaires, - une procédure d'enregistrement dans laquelle une personne à inscrire dans le groupe reçoit d'une autorité de confiance un droit de signature, c'est-à-dire une clé privée et un certificat autorisés, - une procédure de signature proprement dite au cours de laquelle une personne possédant un droit de signature signe un message, et - une procédure de vérification consistant à appliquer un algorithme de vérification à une signature pour vérifier que la signature a été produite par une personne possédant un droit de signature. L'invention prévoit en outre une disposition pour garantir l'anonymat d'un signataire, même vis-à-vis d'une autorité de confiance, ainsi qu'une procédure d'organisation d'une séquence consistant à définir un numéro de séquence à 30 utiliser pour générer des signatures de liste, la vérification d'une signature comprenant en outre une étape de vérification que la signature est unique pour un numéro de séquence donné. Le procédé selon l'invention peut également comporter une procédure de 35 révocation, telle que définie dans le document référencé [2]. A l'aide de cette procédure de révocation, une autorité de confiance peut retirer à un membre de la liste, les droits de signature qu'elle lui a précédemment attribués, à partir de l'identité du membre. La mise en place de cette possibilité de révocation -8 implique l'exécution par les membres de la liste d'une procédure de mise à jour au cours de laquelle les membres de la liste mettent à jour leurs certificats pour prendre en compte les modifications (ajout ou retraits) effectuées dans la liste des personnes autorisées à signer. La figure 2 illustre les différentes étapes de la procédure d'organisation 10 exécutée sur le calculateur 1 de l'autorité de confiance. Conformément au document référencé [1], cette procédure consiste à choisir 11 des nombres entiers suivants: - s>l, k, lI, - ? X2, YI, Y2 qui sont des longueurs de nombres entiers en nombres de bits, avec: 2 > 41P (1) 1 >sQ(2+k)+2 (2) Y2 > + 2 (3) YI > E(Y2 + k) + 2 (4) et à définir les ensembles de nombres entiers suivants A =]21 2, 211 + 212[ et r =]2Y' 22, 21 + 22[. Cette procédure consiste également à choisir une fonction de hachage résistante aux collisions H telle qu'une séquence binaire de longueur quelconque notée {0, 1} est transformée en une séquence binaire de longueur k notée {0, 1}k. Ensuite, le calculateur 1 de l'autorité de confiance génère aléatoirement, à l'étape 12, des nombres premiers p' et q' de taille l,, tels que p = 2p' + 1 et q = 2q' + 1 sont aussi des nombres premiers. Ensuite, il calcule à l'étape 13 le module n = pq et génère aléatoirement à l'étape 14 des nombres entiers a, a4, b, 30 g et h dans l'ensemble QR(n) des résidus quadratiques de n, c'est-à-dire l'ensemble des nombres entiers y tels y = x2 (mod n), x étant un nombre entier. On considère alors que la clé publique PK de l'autorité de confiance est constituée de la séquence de nombres entiers (n, a, ao, b, g, h) et que la clé privée de celle-ci est constituée de la séquence de nombres entiers (p', q'). Pour être enregistré par l'autorité de confiance, un utilisateur souhaitant devenir membre de la liste exécute sur son terminal 2 la procédure 20 illustrée sur la figure 3. L'exécution de cette procédure engage un dialogue avec le calculateur -9 1 de l'autorité de confiance qui exécute alors une procédure 20'. La procédure 20 comprend tout d'abord une étape 21 de génération aléatoire de nombres entiers xi et Y, respectivement dans les intervalles]0, 2x2L et]0, n2[. A partir de ces nombres entiers, on calcule 22 un nombre entier CI tel que: Ci gXihr(modn) (5) A l'étape 23, on construit la preuve U de la connaissance de deux nombres at et 3 (c'est-à-dire xi et 7) tels que CI = gah (mod n). Une telle preuve est par exemple constituée en choisissant aléatoirement deux 10 nombres entiers r1 et r2 dans l'ensemble des nombres binaires signés à F(211) + k) bits, noté {0, 1} (21p+k) et en calculant les nombres suivants: dl = grhr2 (mod n), (6) c = H(gllhllCllldl), (7) dans laquelle le symbole Il représente l'opérateur de concaténation, si =ri ca, (8) S2= r2- cp. (9) si et S2 étant des nombres entiers relatifs. La preuve U est alors égale à (c, si, S2, CI). Le nombre CI et la preuve U sont ensuite envoyés à l'autorité de confiance qui vérifie à l'étape 21' la preuve U et que Ci se trouve dans l'ensemble QR(n) des résidus quadratiques de n. Dans l'exemple précédent, la vérification de la preuve U consiste à calculer: t1-ClggSh 2(modn), et (10) c' =H(glIhlIC 1 tî). (11) La preuve est vérifiée si c' = c et si s1 et S2 appartiennent à l'ensemble {O, 1i} i(2lp+k)+1 Si tel est le cas, le calculateur 1 de l'autorité de confiance génère aléatoirement 22' deux nombres entiers ai, Pi dans l'intervalle]0, 212[, et envoie ces nombres au terminal 2 de l'utilisateur. Dans la procédure 20, le terminal de l'utilisateur calcule alors à l'étape 24 les nombres entiers xi et C2 en appliquant les formules suivantes: xi=2 + (aifi+Pi(mod2 2)), et (12) C2 = aXi(modn). (13) - 10 Puis, il construit à l'étape 25 les preuves suivantes (par exemple selon le même principe que la preuve U): - la preuve V de connaître un nombre a appartenant à l'ensemble A tel que: C2 = a' (mod n) (14) - la preuve W de connaître trois nombres Y, Y, 8 tels que f3 E]- 2X2, 2X2[ et C2/aX2 = aP et (15) ci g(g2)h8 (16) C2 et les preuves V et W sont ensuite envoyés au calculateur 1 de l'autorité de confiance qui vérifie 23' les preuves V et W, et que C2 appartient à l'ensemble QR(n). Si tel est le cas, il génère 24' aléatoirement un nombre premier e1 appartenant à l'ensemble r et applique la formule suivante: Ai =(C2ao) 1i(modn) (17) et renvoie à l'utilisateur les entiers Ai et ei considérés comme un certificat [Ai, e] d'appartenance de l'utilisateur à la liste. Le calculateur 1 crée 26' alors une nouvelle entrée dans une table des membres 20 de la liste, par exemple dans la base de données 4, dans laquelle il mémorise le certificat [Ai, ei] en vue de modifications de la liste (par exemple révocations de membres), et de préférence les messages échangés entre l'autorité de confiance et l'utilisateur durant cette procédure d'enregistrement de l'utilisateur. Par ailleurs, l'utilisateur peut contrôler 26 l'authenticité du certificat reçu en vérifiant que l'équation suivante est satisfaite: axi =Ai'(modn) (18) A la fin de cette procédure d'enregistrement 20, l'utilisateur dispose donc d'une 30 clé privée xi et d'un certificat [Ai, ei] de membre de la liste, qui sont par exemple mémorisés dans une carte à puce 7. A l'aide d'un tel certificat, l'utilisateur peut générer une signature d'un message M appartenant à l'ensemble {0, 1}. A cet effet, l'autorité de confiance publie selon l'invention un numéro m de 35 séquence, choisi aléatoirement dans l'ensemble QR(n). Ce numéro devra être utilisé par les membres de la liste pour signer un message durant une séquence - 11 donnée. Les numéros respectifs de séquences différentes ne doivent pas pouvoir être liés. En particulier, il doit être impossible de calculer un logarithme discret d'un numéro de séquence donné, par rapport à la base d'un autre numéro de séquence, c'est-à-dire qu'il ne doit pas être possible en pratique de calculer des nombres entiers x et y tels que: mx = m'y (mod n), m et m' étant des numéros de séquence. Ce numéro m de séquence peut être calculé en fonction de la date de début de la séquence: m = F(date). Cette fonction F est par exemple choisie égale à: F(d) =(H(d))2 (mod n) (19) dans laquelle i' une fonction de hachage résistante aux collisions, telle qu'une séquence binaire de longueur quelconque notée {0, l} * est transformée en une séquence binaire de longueur 2lp notée {0, i} 21P. Il est donc facile de vérifier la validité du numéro de séquence en appliquant la formule (19). La procédure de signature d'un message est conçue pour permettre notamment à un utilisateur de démontrer qu'il connaît un certificat de membre et une clé privée de membre et qu'il utilise le bon numéro de séquence. Pour signer un message M, un membre de la liste doit exécuter, par exemple sur 20 sa carte à puce 7 connectée à un terminal 2 et mémorisant son certificat [Ai, ej] et sa clé privée xi, une procédure 30 de signature, illustrée sur la figure 4. Cette procédure comprend tout d'abord une étape 31 de génération aléatoire d'un nombre o appartenant à l'ensemble {0, 1}21P. Elle comprend en outre une étape 32 consistant à calculer les nombres suivants à partir de o: Tl = Aib' (mod n), (20) T2 = gO (mod n), (21) T3 = geih' (mod n). (22) Conformément à l'invention, on calcule également le nombre suivant: T4 = mxi(mod n) (23) A l'étape 33 suivante, on génère d'une manière aléatoire les nombres r1 dans l'ensemble des nombres binaires signés à E(y2+k) bits, noté {0, 1} E(y2+k), r2 dans 35 l'ensemble {0, 1} (X2+k), r3 dans l'ensemble {0, 1}s(Y1+2lP+k+l) et r4 dans l'ensemble {0, 1}E(21P+k). Puis, à l'étape 34, on calcule les grandeurs suivantes: di = Tîrl/(ar2Y3) (mod n) (24) d2= T2 rl/gr3 (mod n) (25) - 12 d3 = gr4 (mod n) (26) d4 = grhr4 (mod n) (27) Conformément à l'invention, on calcule également le nombre suivant: d5 = mr2 (mod n) (28) Puis, à l'étape 35, on calcule les nombres suivants: c = H(mllbllgllhllaolialIT1IfT21IT31IT41di lld2lld3lld4lld5llM), (29) dans laquelle Il représente l'opération de concaténation, s, = r1 - c(ej - 2T1) , (30) S2 = r2 - c(xj - 2X1), (31) S3 = r3 - cepco, (32) S4 = r2- co, (33) SI, S2, S3, S4 étant des nombres entiers relatifs. La signature est enfin constituée de l'ensemble de nombres suivants: (C, SI, S2, S3, S4, TI, T2, T3, T4)- (34) qui est par exemple émise par le réseau 5. La vérification d'une signature d'un message M se déroule en exécutant la procédure 40 illustrée sur la figure 5. Cette procédure comprend tout d'abord à l'étape 41, le calcul des nombres suivants: t =acTs-c2 /(a 2-c2 bS3)(modn) (35) t2=T2S /g 3(modn) (36) t3=T 2g5(modn) (37) t4 = Tcgs,-c2' hS4(modn) (38) Selon l'invention, elle comprend également le calcul des nombres suivants: t T5 = s2-m (modn) (39) c' = H(ml Ibl Iglihl 14 alIT, IT21IT3IlT411t, Ilt2j jt3ilt4l jt5sIM) (40) La signature est authentique si les conditions suivantes sont vérifiées à l'étape 42: c' = c (41) - 13 SI E {O, 1}4Y2+k)+1 (42) S2 E {O, 1}( 2+), (43) S3 E {O, l}8(yl+21p+k+l)+l (44) S4 E {O, 1}E(21p+k)+l. (45) Si ces conditions ne sont pas vérifiées, la signature n'est pas valable (étape 45). En outre, en accédant à toutes les signatures qui ont été produites pendant une séquence donnée, par exemple dans la base de données 4, on peut vérifier facilement à l'étape 43, à l'aide du paramètre T4, si un membre de la liste a 10 signé plusieurs fois: toutes les signatures émises par un membre de la liste comprennent un paramètre T4 ayant la même valeur pour un numéro de séquence donné. Il est en outre à noter qu'un membre ne peut pas tricher en utilisant une autre valeur car T4 est fortement lié à TI. En effet, la formule de calcul de Tl peut aussi être écrite de la manière suivante: Tei =aoaxib de la liste pour ce numéro de séquence (étape 46). Pour inclure une possibilité de révocation d'un membre de la liste, le procédé qui vient d'être décrit peut être modifié de la manière suivante. La procédure d'organisation 10 de la liste comprend en outre à l'étape 14, le choix aléatoire d'un nombre u appartenant à l'ensemble QR(n), et la définition de deux ensembles Eadd et Edel qui sont initialement vides. La clé publique PK de l'autorité de confiance est alors constituée de la séquence de nombres entiers (n, a, ao, b, g, h, u) et des ensembles Eadd et Ede1. Durant la procédure d'enregistrement 20, 20', le calculateur 1 de l'autorité de confiance attribue à l'étape 25' le paramètre ui au nouveau membre Ui de la liste, ce paramètre étant tel que ui = u, et met à jour la valeur du paramètre u en remplaçant cette valeur par uei. Le certificat du nouveau membre regroupe alors les entiers Ai, ei et u1, ce certificat étant mémorisé à l'étape 26' pour des modifications futures et - 14 transmis au nouveau membre. L'autorité de confiance introduit également le nombre e, attribué aunouveau membre dans l'ensemble Eadd5 A la réception de son certificat, le nouveau membre vérifie en outre que: u.ei = u (mod n) (47) Les autres membres Uj de la liste doivent alors exécuter une procédure de mise à jour pour prendre en compte l'arrivée du nouveau membre et donc la 10 modification du paramètre de liste u. Cette procédure consiste à recalculer leur paramètre uj de la manière suivante: uj = uei (mod n) (48) De cette manière, la relation (47) est toujours vérifiée pour tous les couples (uj, ej) de tous les membres de la liste. La procédure de révocation d'un membre Uk de la liste dont le certificat est (Ak, ek, Uk) consiste pour l'autorité de confiance à modifier le paramètre u de la manière suivante: u=ul/ek (modn) (49) et à introduire le paramètre ek dans l'ensemble Edel. En outre, chaque membre non révoqué Uj de la liste doit prendre en compte cette révocation (changement du paramètre u) en recalculant son paramètre uj de la manière suivante: uj = uibua (mod n) (50) a et b étant tels que aej + bek = 1 Pour déterminer a et b, il suffit d'appliquer l'algorithme d'Euclide étendu consistant à effectuer une série de divisions euclidiennes. Il est à noter que le membre révoqué (possédant ek) ne peut pas déterminer a et b à l'aide de la formule (50) qui devient ek(a + b) = 1, et donc recalculer le paramètre Uk. Durant la procédure 30 de signature par un membre de la liste, il faut en outre à l'étape 31 choisir aléatoirement des nombres wb, W2 et w3 de longueur binaire égale à 21p, c'est-à-dire appartenant à l'ensemble {0, 11}21P, et calculer à l'étape - 15 32 les nombres suivants: T5 = geihwl(modn) (51) T6 =uihW2 (modn) (52) T7 =gW2 hw(modn) (53) Il faut aussi à l'étape 33 choisir aléatoirement des nombres r5, r6, r7 appartenant à l'ensemble {O, î} (2lp+k) et des nombres r8 et r9 appartenant à l'ensemble {0,}(yl+21p+k+1), puis calculer à l'étape 34 les nombres suivants d6 = grlhrs (mod n) (54) (17 grhr7 (mod n) (55) d6= T6r'/hd8 (mod n) (56) dg = T7rl/(gr8hr9) (mod n) (57) Le nombre c inclut alors les éléments suivants: c = H(mllbjlgllhllaoialIT1 IIT21IT31IT41IT5IlT6IIT7ldil Id2Id3 Id4l d5ild6Ild7Ild8IldglIM) (58) Il faut encore calculer à l'étape 35: S5 = r5 - cwI (59) S6 = r6 - Cw2 (60) S7 = r7 - CW3 (61) s8 = r8 - ceiw2 (62) sg = r9 - ceiw3 (63) La signature est alors constituée de l'ensemble de nombres suivants (c, sI, s2, S3, S4, S5, S6, S7, s8, s9, Tl, T2, T3, T4, T5, T6, T7). (64) La procédure 40 de vérification d'une signature comprend alors en outre le calcul des nombres suivants à l'étape 41 t6 = gSI-c2lhs5(modn) (65) t7 =T7 gs6hs7(modn) (66) t8 u C gSi-C2t' /hs'(modn) (67) t9=Tg sc2 /(gs8hs9) (modn) (68) c' = H(mllbllgllhllaollalTî 11T21T31IT41IT51jT61IT711tllt2llt3llt4lt5llt6llt7llt8llt9llM) (69) - 16 La signature est authentique si les conditions supplémentaires suivantes sont vérifiées à l'étape 42: S5 E {0, 1}(21p+k)+1 (70) S6 E {0, 1} E(21P+k)+1 (71) S7 E {0, 1}8(21p+k)+ 1 (72) S8 E {0 1}E(Yl+21p+k+l)+I et (73) S9 E {0,1}E(yl+21p+k+l)+l (74) Il est à noter que contrairement à la signature de groupe décrite dans le document [1], il n'est pas possible pour l'autorité de confiance de retrouver l'identité d'un signataire, c'est-à-dire le nombre Ai du certificat du signataire à partir d'une signature de liste telle que décrite. En effet, contrairement au procédé décrit dans ce document, l'autorité de confiance n'utilise pas une clé 15 privée x pour générer le paramètre b, et donc le nombre Ai ne peut pas être déduit de T1 et T2En outre, la signature générée par un membre révoqué Uk sera détectée invalide. En effet, le paramètre T6 fait intervenir le paramètre uk qui a été déterminé à 20 partir du paramètre commun u, et le paramètre t8 qui est calculé pour vérifier la signature fait intervenir également le paramètre u qui a été modifié à la suite de la révocation du membre k. Il en résulte que, lors de la vérification de signature, les paramètres T6 et t8 sont incohérents, et donc que l'égalité entre c et c' ne peut pas être vérifiée par la signature du membre k. Le procédé de signature de liste qui vient d'être décrit peut être appliqué à un procédé de vote électronique. Le procédé de vote électronique selon l'invention comprend plusieurs phases dont l'exécution des procédures du procédé de signature de liste décrit ci-avant. Ce procédé implique l'intervention d'une autorité de confiance 1 organisatrice des élections qui exécute à cet effet une procédure 50 d'organisation du scrutin. Cette procédure consiste à générer les données nécessaires au bon déroulement des élections, une base de données publique accessible à tous dans laquelle sont 35 recueillis les bulletins de vote. Au cours de l'organisation du scrutin, on désigne également des scrutateurs qui vont dépouiller les votes et déterminer le résultat de l'élection. - 17 L'autorité organisatrice procède tout d'abord à la génération des différents paramètres nécessaires à la mise en place d'une signature de liste, en exécutant la procédure 10 d'organisation d'une signature de liste. Les électeurs doivent ensuite préalablement s'inscrire, par exemple dans une mairie, sur une liste électorale de manière à recevoir toutes les données nécessaires, à savoir une clé privée xi et un certificat (Ai, ei, u1), pour générer une signature de liste. A l'aide de ces paramètres, les électeurs peuvent participer à toutes les élections futures. Cette procédure d'inscription peut par exemple être exécutée entre une carte à puce 7 et un terminal 2, la carte à puce mémorisant à la fin de la procédure le certificat de l'électeur. Avant une élection, l'autorité organisatrice procède à la mise à jour des listes électorales en exécutant la procédure 20, 20' pour les électeurs nouvellement inscrits, et en enlevant (révoquant) les droits de signature de liste à toutes les 15 personnes rayées des registres électoraux (par exemple les personnes ayant quitté la circonscription ou déchues de leurs droits civiques). Ces révocations sont réalisées en exécutant la procédure de révocation décrite ci-avant. A l'étape 51 de la procédure 50, l'autorité organisatrice publie également un numéro de séquence m nécessaire à la mise en place d'une nouvelle séquence de signature 20 de liste, de manière à empêcher les électeurs de voter (signer) deux fois à cette élection. Par ailleurs, les scrutateurs vont créer 52 les paires de clés publiques/privées nécessaires, de telle sorte qu'ils doivent tous coopérer pour pouvoir déchiffrer 25 un message chiffré avec la clé publique. A cet effet, le système cryptographique mis en place est choisi de manière à permettre à un électeur de chiffrer un message (bulletin de vote) à l'aide d'au moins une clé publique, tout en imposant la coopération de tous les scrutateurs pour utiliser la ou les clés privées correspondantes, et ainsi déchiffrer le message. Le partage de la clé privée de déchiffrement entre tous les scrutateurs peut être effectué de la manière suivante. On considère g un générateur du groupe cyclique G. Une clé privée xi 35 respective est attribuée à chaque scrutateur i qui calcule le nombre yi appartenant à G tel que: Yi = gxi (75) - 18 La clé publique Y à utiliser par les électeurs est obtenue par la formule suivante: Y=]lYj (76) i et la clé privée X correspondante partagée par tous les scrutateurs i est la suivante: X=Zx, (77) i On peut arriver à un résultat analogue en procédant à un chiffrement en utilisant toutes les clés publiques respectives des scrutateurs. Le déchiffrement nécessitant la connaissance de toutes les clés privées correspondantes. Avant d'aller voter, chaque électeur doit mettre à jour son certificat de signature de liste conformément à la procédure de modification décrite ciavant, à l'aide des paramètres publiés précédemment. Si l'électeur n'est pas radié des listes électorales, cette modification peut être effectuée. Pendant l'ouverture des bureaux de vote, chaque électeur émet un bulletin de vote en exécutant sur un terminal une procédure 60. A l'étape 61, l'électeur sélectionne son vote vi et chiffre celui-ci à l'aide de la clé publique des 20 scrutateurs pour obtenir un vote chiffré Di. Puis il signe le vote chiffré à l'aide du procédé de signature de liste pour obtenir une signature Si. Le bulletin de vote constitué de l'ensemble (Di, Si) du vote et de la signature, est ensuite publié de manière anonyme dans une base de données publique 4. A l'étape 62, le chiffrement du vote est réalisé en utilisant un algorithme de chiffrement probabiliste (c'est-à-dire que la probabilité que deux chiffrements d'un même message soient identiques est quasiment nulle), tel que par exemple l'algorithme de El Gamal ou de Paillier. Si on applique l'algorithme de El Gamal, le chiffrement est effectué en calculant les nombres suivants: aj = vjYr et bj = gr (78) dans lesquels r est un élément aléatoire. Le vote Vj chiffré est alors constitué par le couple Dj = (aj,bj). L'électeur Ej calcule 63 ensuite la signature de liste du vote chiffré Sj = Sigijste(ajllbj), Sigljste étant la signature de liste telle que décrite ci-avant, en exécutant la procédure 30 par sa carte à puce 7, laquelle est transmise au terminal 2. L'électeur Ej a ainsi généré son bulletin de vote (Di, Sj) qu'il envoie 64 à la base de données publique 4 au moyen d'un canal de transmission anonyme, c'est-à- - 19 dire interdisant de relier un message transmis à l'émetteur de celuici. L'électeur peut à cet effet utiliser un terminal public ou un réseau de mélangeurs. A la fin du scrutin, les scrutateurs effectuent le dépouillement du scrutin en exécutant la procédure 70 sur le terminal 3. Cette procédure consiste tout d'abord à générer 71 la clé privée de déchiffrement X à partir de leurs clés privées respectives xi et à l'aide de la formule (77). Puis, à l'étape 72, ils accèdent à la base de données publique 4 des bulletins de vote pour obtenir les bulletins de vote (Di, Si) et pour les déchiffrer. Le déchiffrement proprement dit des bulletins de vote consiste pour chaque bulletin de vote émis (étape 73) à vérifier 74 la signature Si en exécutant la procédure 40 de vérification de signature de liste décrite ci-avant, et si la signature est valable et unique (étape 75), à déchiffrer 76 le vote chiffré Dj en appliquant la formule suivante: v = aj/bjx (79) Les votes v; ainsi déchiffrés et vérifiés, avec le résultat de la vérification correspondante sont introduits 77 dans la base de données 4 des bulletins de vote, en association avec le bulletin de vote (Dj, Sj). La clé privée de déchiffrement X est également publiée pour permettre à tous de vérifier le dépouillement des bulletins de vote. Une fois que tous les bulletins de vote ont été dépouillés, cette procédure 70 25 calcule à l'étape 78 le résultat de l'élection et met à jour la base de données publique des bulletins de vote en y inscrivant ce résultat, et éventuellement la clé privée de déchiffrement X. Il est aisé de constater que les propriétés énoncées ci-avant, nécessaires à la 30 mise en place d'un système de vote électronique, sont vérifiées par le procédé décrit ci-dessus. En effet, chaque électeur ne peut voter qu'une seule fois puisqu'il est facile de retrouver dans la base de données deux signatures émises par un même électeur pour un même scrutin (pour un même numéro de séquence). Dans ce cas, les scrutateurs peuvent ne pas prendre en compte les deux votes ou ne comptabiliser qu'un seul vote s'ils sont identiques. Alternativement, on peut prévoir qu'à l'étape 64 d'insertion d'un vote dans la base de données 4, on vérifie que le vote émis par l'électeur ne figure pas déjà dans la base de données en y recherchant le paramètre T4 propre à l'électeur. Si - 20 on détecte ainsi que l'électeur a déjà voté pour ce scrutin, le nouveau vote n'est pas inséré dans la base de données 4. Ensuite, il n'est pas possible de commencer à dépouiller les bulletins de vote avant la fin du scrutin si au moins un des scrutateurs respecte la règle, puisqu'il faut la présence de tous les scrutateurs pour dépouiller un bulletin de vote. Enfin, le résultat de l'élection est vérifiable par tous puisque les scrutateurs fournissent dans la base de données tous les éléments nécessaires (en particulier la clé privée de dépouillement) pour procéder à une telle vérification, et que la 10 vérification d'une signature est accessible à tous en utilisant la clé publique PK=(n, a, ao, b, g, h, u) de l'autorité de confiance. Ainsi n'importe qui peut effectuer le dépouillement de la même manière que les scrutateurs et donc s'assurer qu'il a été effectué de manière correcte. Les clés des scrutateurs sont bien entendu obsolètes à la fin du scrutin, puisqu'elles sont publiées. - 21 REVENDICATIONS 1. Procédé de signature de liste comprenant au moins: - une phase d'organisation (10) consistant pour une autorité de confiance (1) à définir des paramètres de mise en oeuvre d'une signature électronique anonyme, dont une clé privée et une clé publique correspondante, - une phase d'enregistrement (20, 20') de personnes dans une liste de membres autorisés à générer une signature électronique propre aux membres de la liste, au cours de laquelle chaque personne (2) à enregistrer calcule (24) une 10 clé privée (xi) à l'aide de paramètres fournis par l'autorité de confiance et de paramètres choisis aléatoirement par la personne à enregistrer, et l'autorité de confiance délivre (25') à chaque personne à enregistrer un certificat ([Ai, ej]) de membre de la liste, - une phase de signature (30) au cours de laquelle un membre de la liste génère 15 (35) et émet (36) une signature propre aux membres de la liste, cette signature étant construite de manière à contenir une preuve que le membre de la liste ayant émis la signature, connaît un certificat ([Ai, et]) de membre de la liste, et - une phase de vérification (40) de la signature émise comprenant des étapes 20 (41, 42) d'application d'un algorithme prédéfini pour mettre en évidence la preuve que la signature a été émise par une personne en possession d'un certificat de membre de la liste, caractérisé en ce qu'il comprend en outre une phase de définition d'une séquence consistant pour l'autorité de confiance (1) à générer un numéro de 25 séquence (m) à utiliser dans la phase de signature (30), une signature (Sig1,ste) générée durant la phase de signature comprenant un élément de signature (T4) qui est commun à toutes les signatures émises par un même membre de la liste avec un même numéro de séquence et qui contient une preuve que le numéro de séquence (m) à été utilisé pour générer la signature, la phase de vérification (40) 30 comprenant en outre une étape de vérification (43) de la preuve que le numéro de séquence (mi) a été utilisé pour générer la signature. 2. Procédé selon la revendication 1, caractérisé en ce que la phase d'organisation (10) comprend la définition d'un 35 paramètre commun (u) dépendant de la composition de la liste, la phase d'enregistrement (20, 20') d'une personne dans la liste comprenant la définition d'un paramètre (u1) propre à la personne à enregistrer qui est calculé en fonction du paramètre (u) dépendant de la composition de la liste et qui est intégré au - 22 certificat ([Ai, e1, ui]) remis à la personne, la phase d'enregistrement (20, 20') comprenant une étape de mise à jour du paramètre commun (u) dépendant de la composition de la liste, le procédé comprenant en outre une phase de révocation pour retirer un membre de la liste, consistant à modifier le paramètre commun (u) dépendant de la composition de la liste, pour tenir compte du retrait du membre de la liste, et une phase de mise à jour des certificats des membres de la liste pour tenir compte de modifications de la composition de la liste. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'une signature propre à un membre de la liste et possédant le certificat [Ai, ei] comprend des paramètres TI, T2, T3 tels que: Tl = Aib' (mod n), T2 = gO (mod n), T3 = geihe (mod n), " étant un nombre choisi aléatoirement lors de la phase de signature (30), et b, g, h et n étant des paramètres généraux de mise en oeuvre de la signature de groupe, tels que les paramètres b, g et h ne peuvent pas se déduire les uns des autres par des fonctions d'élévation de puissance entière modulo n, de sorte que le nombre Ai, et donc l'identité du membre de la liste possédant le certificat [Ai, e1] ne peut pas se déduire d'une signature émise par le membre. 4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce que le numéro (m) d'une séquence utilisé pour générer une signature de liste est calculé en fonction d'une date de début de séquence. 5. Procédé selon la revendication 4, caractérisé en ce que la fonction de calcul du numéro d'une séquence est de la forme: F(d) = (H(d))2 (mod n) dans laquelle H est une fonction de hachage résistante aux collisions, d est la date de début de la séquence, et n est un paramètre général de mise en oeuvre de la signature de groupe. 6. Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'une signature (Sigit,) émise par un membre de la liste contient un paramètre (T4) qui est calculé en fonction du numéro de séquence et de la clé privée (xi) du membre signataire. - 23 7. Procédé selon la revendication 6, caractérisé en ce que le paramètre T4 d'une signature émise par un membre de la liste et dépendant du numéro de séquence m et de la clé privée xi du membre signataire est obtenu par la formule suivante: T4 = mxi (mod n) n étant un paramètre général de mise en oeuvre de la signature de groupe, et en ce que la signature comprend la preuve que le paramètre T4 a été calculé avec la clé privée xi du membre de la liste qui a émis la signature. 8. Procédé de vote électronique comprenant une phase d'organisation (50) des élections, au cours de laquelle une autorité organisatrice procède à la génération de paramètres nécessaires à un scrutin, et attribue à des scrutateurs des clés leur permettant de déchiffrer et vérifier des bulletins de vote, une phase d'attribution d'un droit de signature à chacun des électeurs, une 15 phase de vote (60) au cours de laquelle les électeurs signent un bulletin de vote, et une phase de dépouillement (70) au cours de laquelle les scrutateurs vérifient les bulletins de vote, et calculent le résultat du scrutin en fonction du contenu des bulletins de vote déchiffrés et valides, caractérisé en ce qu'il met en oeuvre un procédé de signature de liste selon l'une 20 des revendications 1 à 7, pour signer les bulletins de vote, chaque électeur étant enregistré comme membre d'une liste, et un numéro de séquence (m) étant généré pour le scrutin, pour détecter si un même électeur a émis ou non plusieurs bulletins de vote pour le scrutin. 9. Procédé selon la revendication 8, caractérisé en ce que la phase d'organisation (50) comprend la remise à chaque scrutateur d'une clé publique et d'une clé privée, en ce que les bulletins de vote (vi) sont chiffrés (62) à l'aide d'une clé publique (Y) obtenue par le produit des clés publiques (yi) respectives de tous les scrutateurs, et en ce que la clé privée 30 (X) de déchiffrement correspondante est obtenue en calculant la somme de clés privées (xi) respectives de tous les scrutateurs. 10. Procédé selon la revendication 9, caractérisé en ce que le chiffrement (62) des bulletins de vote est effectué à l'aide d'un algorithme de chiffrement probabiliste. 11. Procédé selon l'une des revendications 8 à 10, caractérisé en ce que les bulletins de vote émis par les électeurs sont stockés - 24 dans une base de données publique (4), en ce que le résultat de la vérification et du dépouillement de chaque bulletin de vote est stocké dans la base de données en association avec le bulletin de vote, et en ce que la clé privée (X) de déchiffrement des bulletins de vote est publiée.