Brevet FR2896062A1 — publié le 20070713

Arrière-plan de l'invention Le domaine de l'invention est celui du commerce électronique dans lequel un utilisateur peut obtenir des biens ou des services, par exemple auprès d'un marchand, en échange de monnaie électronique ou de coupons électroniques. A ce sujet, l'invention sera décrite dans le contexte de la monnaie électronique, mais elle s'applique exactement de la même façon à celui des coupons électroniques, la seule différence entre la monnaie et les coupons résidant dans le fait que la monnaie électronique est émise par un organisme bancaire, alors que les coupons électroniques sont émis par un organisme marchand. On rappelle que les pièces de monnaie électronique sont des pièces virtuelles obtenues, lors d'un protocole de retrait, auprès d'une banque, cette banque débitant le compte bancaire de l'utilisateur en fonction du nombre et du montant des pièces électroniques délivrées. De la même façon, les coupons électroniques sont des coupons virtuels délivrés par un marchand ; ils correspondent typiquement à des bons d'achat. De façon connue, la monnaie électronique doit préserver les avantages de la monnaie traditionnelle. Par exemple, il ne doit pas être possible de relier les pièces entre elles, c'est-à-dire qu'il ne doit pas être possible de savoir si deux pièces proviennent d'un même porte-monnaie électronique. Bien entendu, il ne doit pas non plus être possible de dépenser plusieurs fois la même pièce de monnaie électronique. La monnaie électronique présente en outre des avantages par rapport à la monnaie usuelle puisque, notamment, dans le commerce électronique, une transaction peut se faire sans contact visuel entre l'acheteur et le vendeur, l'acheteur pouvant souhaiter rester anonyme. Les procédés de paiement et de vérification selon l'invention respectent ces contraintes. De façon connue, les protagonistes intervenant dans les systèmes de paiement électronique sont : - l'utilisateur qui retire des pièces auprès d'une banque ou des coupons électroniques auprès d'un marchand et qui dépense ces pièces ou coupons, de façon anonyme ou non, pour obtenir un bien ou un service payant ; - une banque ou un marchand qui délivre les pièces de monnaie ou les coupons électroniques à l'utilisateur, ces organismes définissant les valeurs des pièces ou des coupons au moment de la création du système ; et - les fournisseurs de service ou marchands qui délivrent les services ou les biens en échange des pièces ou coupons électroniques. L'invention se situe plus particulièrement dans le cadre des schémas de paiement électronique hors ligne, c'est-à-dire tels que l'intervention de la banque n'est pas nécessaire au moment de la dépense d'une pièce de monnaie ou d'un coupon par un utilisateur chez un marchand. Plusieurs schémas de paiement électronique ont été proposés dans la littérature. La plupart de ces schémas permettent de retirer une seule pièce de monnaie ou coupon électronique à la fois. Ainsi lorsqu'un utilisateur souhaite retirer k pièces de monnaie, le protocole de retrait doit être effectué k fois. Nous nous intéressons dans le cadre de cette invention aux schémas de paiement électroniques qui permettent de retirer efficacement plusieurs pièces de monnaie ou coupons électroniques en une fois. Récemment, un schéma de monnaie électronique dénommé "Compact e-cash" a été proposé. Ce schéma permet de retirer plusieurs pièces en un seul protocole. Pour plus de renseignements sur Compact e-cash, l'homme du métier peut se reporter au document "Jan Camenisch, Susan Hohenberger et Anna Lysyanskaya. Compact E-Cash. In Ronald Cramer, éditeur, Eruocrypt'05, volume 3494 de Lecture Notes in Computer Science, pages 302-321. Springer 2005. Cependant, le protocole Compact e-cash ne propose pas de solution pour dépenser efficacement plusieurs pièces de monnaie, ce problème, dit de multidépenses, étant laissé ouvert par les auteurs du document précité. Objet et résumé de l'invention L'invention propose un nouveau schéma de paiement électronique permettant de dépenser un nombre quelconque de pièces ou de coupons électroniques en une seule fois et la vérification que cette dépense est licite. A cet effet, et selon un premier aspect, la présente invention concerne un procédé de paiement électronique utilisant un sous-ensemble de pièces d'un porte-monnaie électronique constitué par un ensemble de pièces, chacune des pièces du sous-ensemble comportant un numéro de série calculé par une fonction pseudo aléatoire à partir d'une même graine et d'un index de cette pièce dans l'ensemble précité. Ce procédé comporte : - une étape de calcul de données de preuve pour valider le paiement en gardant secrets la graine et les index ; et - une étape de fourniture des numéros de série et des données de preuve à un tiers apte à valider le paiement. Conformément à l'invention, les données de preuve permettent de prouver que : - chacun des numéros de série a été calculé à partir de la graine ; - pour un nombre de pièces du sous ensemble appelées pièces témoins , ce nombre étant strictement inférieur au cardinal de ce sous- ensemble, l'index de chaque pièce témoin est un index d'un élément de l'ensemble ; et que - tous les numéros de série des pièces du sous-ensemble sont liés entre eux par une relation déterminée. Selon un deuxième aspect, l'invention concerne un procédé de vérification de la validité d'un paiement électronique effectué avec des pièces électroniques. Ce procédé comporte : - une étape d'obtention des numéros de série de ces pièces et de données de preuve permettant de valider ledit paiement ; et - une étape de validation ou de rejet du paiement après vérification des 35 données de preuve. Conformément à l'invention, ces données de preuve permettent de prouver : - la connaissance d'une graine, et que chacun des numéros de série a été calculé par une fonction pseudo aléatoire à partir de cette graine ; - la connaissance d'un index d'au moins une pièce électronique appelée pièce témoin dont on a obtenu le numéro de série, et que cet index est un index d'un élément d'un ensemble déterminé de pièces ; et que - tous les numéros de série des pièces dont on a obtenu le numéro de série sont liés entre eux par une relation déterminée. L'invention est particulièrement avantageuse lorsqu'elle est utilisée pour effectuer et vérifier des dépenses faisant intervenir plusieurs pièces du porte-monnaie, leurs index n'étant pas nécessairement consécutifs. Elle s'applique aussi pour une dépense ne faisant intervenir qu'une pièce. Les procédés de paiement électronique et de vérification selon l'invention préservent les propriétés du paiement électroniques, notamment l'anonymat. Ces procédés peuvent s'appliquer à tout schéma de monnaie électronique qui utilise une fonction pseudo aléatoire pour calculer le numéro de série qui identifie une pièce donnée. Ces procédés s'appliquent en particulier aux schémas de monnaie électronique utilisant la construction générique de compact e-cash. Dans le contexte de l'invention, un porte-monnaie électronique contient un ensemble de pièces indexées et dont les numéros de série sont obtenus par une fonction pseudo aléatoire à partir d'une même graine. Le cardinal de cet ensemble est fixé. Il constitue la taille du porte-monnaie électronique. Dans ce document, on dira que les pièces électroniques utilisées pour une même dépense constituent un sous-ensemble de l'ensemble des 30 pièces du porte-monnaie électronique. Conformément à l'invention, on applique, au moment du paiement, la fonction pseudo aléatoire à tous les index des pièces de ce sous-ensemble, en utilisant la graine du porte-monnaie électronique. On constitue ainsi un groupe de résultats de la fonction pseudo aléatoire. 35 Conformément à l'invention, on calcule ensuite des données de preuve sur ce groupe pris dans son ensemble. Cette étape est caractéristique du procédé de paiement selon l'invention. En effet, si l'on suivait l'enseignement de l'art antérieur, on calculerait des données de preuve indépendantes entre elles, ces données de preuve portant sur tous les éléments du groupe de résultats précité. Les données de preuve conformes à l'invention permettent, au moment de la vérification du paiement, de prouver, d'une part, que chaque résultat du groupe a été obtenu licitement, c'est à dire par la fonction pseudo aléatoire et avec la même graine. Ceci prouve que les pièces utilisées pour le paiement proviennent du même porte-monnaie électronique. Il reste ensuite à prouver que l'index de toutes les pièces utilisées pour le paiement est compatible avec la taille fixée du porte-monnaie électronique, sans quoi des paiements pourraient être effectuées avec des pièces certes obtenues avec la même graine, mais situées en dehors du porte-monnaie. Comme mentionné précédemment, l'art antérieur incite, pour ce faire, à prouver que chaque index est dans une plage constituée par les index des pièces du porte-monnaie électronique. Cette opération, qui doit se répéter pour chaque pièce est très coûteuse. Conformément à l'invention, on effectue cette preuve que pour certaines pièces du sous-ensemble, appelées pièces témoins . De façon préférée on effectue cette preuve que pour une seule pièce témoin, quelque soit le nombre de pièces dépensées. Conformément à l'invention, une fois cette preuve apportée pour la ou les pièces témoins, on apporte la preuve que les index des autres pièces du sous-ensemble est compatible avec la taille du porte-monnaie électronique en prouvant que toutes les pièces du sous-ensemble sont liées entre elles par la relation déterminée. Cette dernière preuve est beaucoup moins coûteuse. Dans un mode particulier de réalisation de l'invention, les données de preuve comportent : - un challenge calculé à l'aide d'une fonction déterministe et non prédictible à partir notamment d'un engagement obtenu à partir d'une combinaison des numéros de série et d'un aléa ; et - une réponse à ce challenge calculé à partir du challenge, de la graine et de l'aléa. Dans ce mode particulier de réalisation, le procédé de vérification selon l'invention comporte : - une étape de calcul d'un engagement test par une combinaison prenant en compte les numéros de série, et le challenge et la réponse compris 5 dans les données de preuve ; - une étape de calcul d'un challenge test à l'aide d'une fonction déterministe et non prédictible portant notamment sur l'engagement test ; et - une étape de comparaison du challenge et du challenge test pour valider 10 ou rejeter le paiement. Ce mode de réalisation permet avantageusement de limiter le volume d'informations à fournir au tiers vérificateur. Dans un mode particulier de réalisation, le procédé de paiement selon l'invention comporte une étape de calcul de la graine à partir d'une 15 clef privée associée à une donnée de contrôle, et les données de preuve permettent de prouver que cette donnée de contrôle a été obtenue licitement en utilisant la graine du porte-monnaie électronique. Dans un mode de réalisation particulièrement avantageux, cette donnée de contrôle est calculée conjointement avec l'organisme émetteur 20 de la monnaie électronique (à savoir une banque) ou des coupons. Cette caractéristique permet d'apporter la preuve que la monnaie a été émise par cet organisme émetteur. Dans un mode particulier de réalisation de l'invention, le nombre de pièces témoins est nul et le procédé de paiement comporte une étape 25 au cours de laquelle on associe à l'index de chacune des pièces du porte-monnaie électronique, une image de cet index par une permutation secrète (les index étant pris dans l'ordre). On rappelle qu'une permutation est une fonction bijective dont l'ensemble d'arrivée coïncide avec l'ensemble de définition. 30 Au moment de la dépense on fournit en outre au tiers apte à valider la dépense, et pour chacune des pièces du sous-ensemble, son numéro de série en association avec l'image de son index par cette permutation. Conformément à l'invention, l'index reste secret. 35 Dans ce mode particulier de réalisation, le procédé de vérification selon l'invention comporte : - une étape d'obtention, pour chacune des pièces utilisées pour le paiement, et en association avec le numéro de série de cette pièce, une image de l'index de cette pièce par une permutation secrète ; et - une étape au cours de laquelle on vérifie que cette image est un élément de l'ensemble des pièces. Dans ce mode particulier de réalisation, on révèle donc à l'organisme marchand l'image de l'index des pièces par une permutation. De ce fait, les index ne sont pas reçus consécutivement par l'organisme vérificateur, et celui-ci ne peut pas connaître l'état du porte-monnaie électronique, même après avoir reçu plusieurs pièces de ce porte-monnaie. Ce mécanisme permet avantageusement de ne mémoriser que l'index de la dernière pièce utilisée (qui caractérise l'état du porte-monnaie), ceci afin de ne pas réutiliser une pièce déjà utilisée pour une autre dépense. Dans un mode particulier de réalisation, les différentes étapes des procédés de paiement et de vérification sont déterminées par des instructions de programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en oeuvre dans un dispositif de traitement de données ou dans un ordinateur, ce programme comportant des instructions adaptées à la mise en oeuvre des étapes d'un procédé de paiement ou de vérification tel que décrit ci-dessus. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. L'invention vise également un dispositif de paiement électronique utilisant un sous-ensemble de pièces d'un porte-monnaie électronique constitué par un ensemble de pièces, chacune des pièces de ce sous-ensemble comportant un numéro de série calculé par une fonction pseudo aléatoire à partir d'une même graine et d'un index de la pièce dans l'ensemble. Ce dispositif comporte : - des moyens de calcul de données de preuve pour valider le paiement en gardant secrets la graine et l'index ; et - des moyens de fourniture des numéros de série et des données de preuve à un dispositif tiers apte à valider le paiement. Les données de preuve permettent de prouver que : - chacun des numéros de série a été calculé à partir de la graine ; - pour un nombre de pièces du sous ensemble appelées pièces témoins , ce nombre étant strictement inférieur au cardinal du sous- ensemble, l'index de chaque pièce témoin est un index d'un élément de l'ensemble ; et - tous les numéros de série des pièces de ce sous-ensemble sont liés entre eux par une relation déterminée. L'invention vise aussi un dispositif de vérification de la validité d'un paiement électronique effectué avec des pièces électroniques comportant : - des moyens pour obtenir des numéros de série des pièces et des données de preuve permettant de valider ledit paiement ; et - des moyens pour valider ou rejeter le paiement après vérification desdites données de preuve. Les données de preuve permettent de prouver : - la connaissance d'une graine et que chacun des numéros de série a été calculé par une fonction pseudo aléatoire à partir de la graine ; - la connaissance d'un index d'au moins une pièce électronique appelée pièce témoin dont on a obtenu le numéro de série, et que cet index est un index d'une pièce d'un porte-monnaie électronique ; et que - tous les numéros de série des pièces dont on a obtenu le numéro de série sont liés entre eux par une relation déterminée. Brève description des dessins D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures : - la figure 1 représente un dispositif de paiement électronique et un dispositif de vérification conformes à l'invention dans un mode particulier de réalisation ; - les figures 2 et 3 représentent respectivement, sous forme d'organigramme, les principales étapes d'un procédé de paiement électronique et d'un procédé de vérification conformes à l'invention dans un premier mode de réalisation ; - les figures 4 et 5 représentent respectivement, sous forme d'organigramme, les principales étapes d'un procédé de paiement électronique et d'un procédé de vérification conformes à l'invention dans un deuxième mode de réalisation ; - les figures 6 et 7 représentent respectivement, sous forme d'organigramme, les principales étapes d'un procédé de paiement électronique et d'un procédé de vérification conformes à l'invention dans un troisième mode de réalisation ; - les figures 8 et 9 représentent respectivement, sous forme d'organigramme, les principales étapes d'un procédé de paiement électronique et d'un procédé de vérification conformes à l'invention dans un quatrième mode de réalisation. Description détaillée de plusieurs modes de réalisation Dans la suite de ce document, nous adoptons les notations suivantes : - G est un groupe cyclique d'ordre p, p étant un nombre premier ; - g est un élément générateur de G ; - Zp représente l'ensemble des entiers modulo p ; -POK(x, pred(x)) sont les éléments de preuve non interactive de connaissance de x vérifiant le prédicat pred pour X. Dans les modes de réalisation détaillés décrits ici, on considère qu'un utilisateur détient un porte-monnaie électronique PME constitué par un ensemble de N pièces retirées auprès d'une banque. Pour simplifier, la notation PME désigne à la fois le porte-monnaie électronique et l'ensemble de pièces que constitue ce porte-monnaie. Ces pièces sont indexées. Elles comportent un index J compris entre 0 et N-1. Les index J sont des éléments de Zp. Ces index J ne sont pas révélés, ce qui signifie qu'ils sont gardés secrets par l'utilisateur. Par contre, et conformément à l'invention, des éléments permettant de prouver que l'index J appartient à la plage [0, ., N-1] sont calculés au moment de la dépense, et envoyés à un tiers apte à valider le paiement, par exemple au marchand...DTD: Chaque pièce du porte-monnaie électronique PME est identifiée par son numéro de série Si. Conformément à l'invention le numéro de série Si de chaque pièce est calculé à l'aide d'une fonction pseudo aléatoire, à partir d'une graine s propre au porte-monnaie PME, et de l'index J de cette pièce. La graine s est un élément de Zp. Dans les modes de réalisation décrit ici, on utilise la fonction pseudo aléatoire fDYg,s(.) de Dodis et Yampolskyi, définie dans le document : A Verifiable Random Function with Short Proofs and Keys. In Public Key Cryptography, volume 3386 of LNCS, pages 416-431, 2005 (ci-après [DY05]), et telle que : fDYg,s(J) = gl / (s + J) On se place dans le contexte dans lequel l'utilisateur effectue une dépense de v pièces du porte-monnaie PME auprès d'un marchand. Ces v pièces constituent un sous-ensemble du porte-monnaie électronique PME. Dans les exemples de réalisation décrits ici, les index des v pièces de ce sous-ensemble (et donc les numéros de série de ces pièces) sont liés entre eux par une relation R déterminée. Dans l'exemple de réalisation décrit ici, cette relation R établit 5 que les index de ces pièces sont des entiers consécutifs dans Zp. Premier mode de réalisation La figure 1 représente, de façon schématique, un dispositif 10 de paiement électronique conforme à l'invention constitué, dans cet 10 exemple, par une carte à microcircuits. Cette carte à microcircuits comporte un processeur 11, une mémoire morte 12, une mémoire vive 13 et des moyens 14 de communication avec un lecteur de cartes à puce. La mémoire morte 12 est adaptée à mémoriser un programme 15 d'ordinateur conforme à l'invention, ce programme comprenant des instructions pour exécuter des étapes d'un procédé de paiement électronique dans l'un quelconque des quatre modes de réalisation qui seront décrits ultérieurement. A la figure 1, on a référencé 20 un dispositif de vérification de la 20 validité d'un paiement électronique conforme à l'invention. Dans cet exemple, ce dispositif est constitué par un lecteur de cartes à puce. Ce dispositif comporte à cet effet une interface physique 25 adaptée à recevoir la carte à puce 10. 25 Il comporte également un processeur 21, une mémoire morte 22, une mémoire vive 23 et des moyens 24 de communication compatibles avec les moyens 14 de communication de la carte à puce 10. La mémoire morte 22 est adaptée à mémoriser un programme d'ordinateur conforme à l'invention, ce programme comprenant des 30 instructions pour exécuter les étapes d'un procédé de paiement électronique dans l'un quelconque des quatre modes de réalisation décrits ci-dessous. On supposera par la suite que le lecteur 20 de cartes à puce est celui d'un marchand, pour effectuer une dépense, insère sa carte à puce 35 10 dans ce lecteur. La figure 2 représente, sous forme d'organigramme, les principales d'un procédé de paiement conforme à l'invention dans un premier mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par la carte à puce 10 de la figure 1. On considère que les v pièces utilisées pour la paiement ont les indices J à J+v-1. Une représentation équivalente de ces pièces sera utilisée: l'indice de la première pièce à dépenser sera J (qui est pris égal au J initial, incrémenté de v-1), et celui de la dernière pièce de la dépense sera J-v+1 (qui correspond donc au J initial). Au cours d'une première étape [10, la carte à puce 10 calcule les numéros de série So à Sv-1 des pièces à dépenser en utilisant la fonction pseudo aléatoire fDYg,s(.) : So = fDYg,s(J) = gl / (s + J + 1) Si = fDYg,s(J+1) = g1/(s+J+1-1) = g1/(s+J) Sv1 = fDYg,s(J+v) = g1/(s+J+1ù(vù1)) = g1/(s+J +2-v) Par construction, ou plus exactement de par la propriété des fonctions pseudo aléatoires, les éléments Sk ne peuvent pas être reliés entre eux. Cela signifie qu'il est impossible, sans la connaissance de la graine s, de distinguer s'ils ont été calculés avec la même fonction pseudo aléatoire ou non. Au cours d'une étape [20, la carte à puce 10 calcule des données de preuve POK qui permettront au lecteur de carte 20 de valider la dépense. La carte à puce 10 doit notamment prouver que les relations suivantes sont vérifiées : Sos+J+1 = g Sis+J+1 Si-1 = g Ses+J+1 Sz-z = g Sv4s+3+1 Sv-1-(v ù 1) = g Ce qui donne, en notant z = s + J + 1, le système d'équation (E) suivant :30 SoZ = g S1z = g. S1 S2z = g. S22 Sv 1z = 9. 1v-1 Conformément à l'invention les données de preuve POK permettent de prouver, en gardant la graine s et les index J secrets que : - tous les numéros de série So à Sv-1 ont été calculé à partir de la graine s, - pour un nombre de pièces dépensées appelées pièces témoins , ce nombre étant strictement inférieur au nombre de pièces dépensées, l'index J de chaque pièce témoin est un index d'une pièce du porte-monnaie PME (c'est-à-dire que J c [0,N-1]) ; et que - toutes les pièces utilisées pour la dépense sont liées entre elles par la relation R, c'est-à-dire d'index consécutifs dans Zp. Dans l'exemple de réalisation décrit ici, on utilise une seule pièce témoin, à savoir la pièce de numéro de série So. Ainsi, en utilisant les notations définies ci-dessus : POK = POK(J, z ; carte à puce 10 fournit les numéros de série So à Sv-1 et les données de preuve POK au lecteur 20. La figure 3 représente, sous forme d'organigramme, les principales d'un procédé de vérification conforme à l'invention dans ce premier mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par le lecteur de carte à puce 20 de la figure 1. Au cours d'une étape F10, la carte à puce 20 obtient les numéros de série So à Sv-1 et les données de preuve POK fournies par la carte à puce 10 à l'étape E30. Au cours d'une étape F20, le lecteur de carte à puce 20 vérifie ces données de preuve. Puis, au cours d'une étape F30, le lecteur de carte à puce 20 accepte le paiement si ces données de preuve sont correctes et le rejette dans le cas contraire. 25 30 35 Au So 5+3+1 = g J c [v-1,N+v-2], SoZ= g, S1 = g.Sl, ..., Sv-1z = 9•Sv-1v-1) cours d'une étape E30, la Deuxième mode de réalisation La figure 4 représente, sous forme d'organigramme, les principales d'un procédé de paiement conforme à l'invention dans un 5 deuxième mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par la carte à puce 10 de la figure 1. Au cours d'une première étape G10, similaire à l'étape E10 décrite en référence à la figure 2, la carte à puce 10 calcule les numéros 10 de série So à Sv_1 en utilisant la fonction pseudo aléatoire fDYg,s(.). Puis, au cours d'une étape G20, la carte à puce 10 calcule des données de preuve POK qui permettront au lecteur de carte 20 de valider la dépense. Cette étape G20 comporte cinq sous étapes référencées G21 à G25. 15 On rappelle que la carte à puce 10 doit prouver la connaissance de z vérifiant le système d'équations (E). Au cours d'une première sous étape G21, la carte à puce 10 calcule v éléments wo à wv_1 de Zp de la façon suivante : w; = H(info, Sc), ..., Sv_1, i), pour i compris entre 0 et v-1 ; où : 20 - H est une fonction de hachage ; et - info représente des informations qui caractérisent la dépense en cours, par exemple le montant de la dépense, la date, l'heure, la référence du marchand, etc. Avantageusement, l'utilisation de la fonction de hachage H, par 25 nature déterministe et non prédictible, fait que les valeurs w; sont considérées comme des valeurs aléatoires qui ne peuvent être prévues par le lecteur de carte à puce 20. Au cours d'une deuxième sous étape G22, la carte à puce 10 calcule deux valeurs A et B telles que : 30 A=fSr et B=fl(g.Si)w` La carte à puce 1`0 doit donc prouver la connaissance de z tel que: AZ=B. Au cours d'une troisième sous étape G23, la carte à puce 10 choisit au hasard un élément r dans Zp et calcule Q = Ar. 35 Au cours d'une quatrième sous étape G24, la carte à puce 10 calcule un challenge c : c = H(info,So,A, B, Q). Au cours d'une cinquième sous étape G25, la carte à puce 10 calculeune réponse y au challenge c : y = r + c.z Au cours d'une étape G30, similaire à l'étape E30 décrite en référence à la figure 2, la carte à puce 10 fournit les numéros de série So à Sv_1 et les données de preuve POK, constituées, dans ce deuxième mode de réalisation par le challenge c et la réponse y à ce challenge. La figure 5 représente, sous forme d'organigramme, les principales d'un procédé de vérification conforme à l'invention dans ce deuxième mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par le lecteur de carte à puce 20 de la figure 1. Au cours d'une étape H10, le lecteur de carte à puce 20 obtient les numéros de série So à Sv_1 et les données de preuve POK, à savoir le challenge c et la réponse y à ce challenge, fournies par la carte à puce 10 à l'étape G30. Au cours d'une étape H20, le lecteur de carte à puce 20 calcule une combinaison des équations du système (E) à partir d'éléments calculés à l'aide de la fonction de hachage H et des numéros de série So à Sv_1. Cette étape H20 comporte quatre sous étapes référencées H21 à H24. Au cours d'une première sous étape H21, le lecteur de carte à puce 20 calcule v éléments wo à wv_1 de Zp de la façon suivante : w; = H(info, Sc), ..., Sv_1, i), pour i compris entre 0 et v-1. Au cours d'une deuxième sous étape H22, le lecteur de carte à puce 20 calcule deux valeurs A et B telles que : A=f Sr et B=fJ(g.S )1I Au cours d'une trôisième sous étape H23, le lecteur de carte à 30 puce 20 calcule un engagement test Q' par une combinaison prenant en compte les numéros de série So à Sv_1, le challenge c et la réponse y : Q'= AY . B-`. Au cours d'une quatrième sous étape H24, le lecteur de carte à puce 20 calcule un challenge test c' : 35 c' = H(info, Sc), ..., Sv_1, A, B, Q'). Puis, au cours d'une étape H30, le lecteur de carte à puce 20 accepte le paiement si le challenge c et le challenge test c' sont égaux et le rejette dans le cas contraire. Dans le deuxième mode de réalisation, les données de preuve POK sont moins volumineuses. On privilégiera donc ce mode de réalisation lorsque l'on souhaite minimiser le volume de données échangé entre le dispositif de paiement et le dispositif de vérification. En revanche, le traitement des données de preuve par le dispositif de vérification est plus complexe dans le deuxième mode de réalisation. On privilégiera donc le premier mode de réalisation lorsque l'on souhaite minimiser le volume de données traité par le dispositif de vérification. Troisième mode de réalisation La figure 6 représente, sous forme d'organigramme, les principales d'un procédé de paiement conforme à l'invention dans un troisième mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par la carte à puce 10 de la figure 1. Dans ce mode de réalisation, chaque carte à puce 10 est enregistrée auprès d'une autorité de certification avec une clé publique pku et une clé privée sku telles que : pku=gu et sku=u. Au cours d'une étape préliminaire du protocole de retrait de ces 25 pièces, la carte à puce 10 obtient de la banque une donnée de contrôle constituée par une signature 6 : - de sa clé privée u ; - d'un élément s calculé conjointement par la banque et la carte à puce 10, mais connu uniquement de la carte à puce; 30 et - d'un élément t choisi par la carte à puce 10 et conservé secret. Par la suite on notera VS la vérification d'une signature 6. La carte à puce 10 obtient ainsi un porte-monnaie électronique 35 PME constitué par un ensemble de N pièces. Au moment d'effectuer une dépense, la carte à puce 10 reçoit, du lecteur de carte à puce 20, au cours d'une étape I6, un challenge B. Nous supposerons comme précédemment que cette dépense implique les v pièces du porte monnaie électronique PME d'index J à J+v- 1. Au cours d'une étape I7, la carte à puce 10 calcule, de la façon déjà décrite, le numéro de série So d'une pièce témoin, à savoir ici la pièce d'index J, par la formule : So = fDYg,s(J) = gl (S + J + l) Dans ce mode de réalisation, la fonction pseudo aléatoire fDYg,s(.) utilise la graine s correspondant à l'élément calculé conjointement par la banque et la carte à puce 10. Cette caractéristique peut permettre à la banque de détecter une double dépense effectuée avec cette pièce. Au cours d'une étape I8, la carte à puce 10 calcule, avec le challenge B, une donnée de sécurité T, cette donnée T permettant éventuellement de lever l'anonymat en cas de double dépense avec cette pièce. Dans l'exemple de réalisation décrit ici, la donnée de sécurité T 20 se calcule comme suit : T = pkU . gBI(t+J+1) Au cours d'une étape I10, similaire à l'étape E10 décrite en référence à la figure 2, la carte à puce 10 calcule les numéros de série SI 25 à Sv_1 en utilisant la fonction pseudo aléatoire fDYg,s(.), la graine s correspondant à l'élément calculé conjointement par la banque et la carte à puce 10. Dans ce troisième mode de réalisation, les données de preuve POK permettent de prouver que la donnée de contrôle 6 a été obtenue 30 licitement en utilisant la graine s, calculée conjointement par la banque et la carte à puce 10 Au cours d'une étape I20, la carte à puce 10 calcule des données de preuve POK permettant de prouver que : - les valeurs So et T ont été correctement calculées ; 35 -que l'index J est positif et strictement inférieur à N ; - qu'elle possède une signature 6 de la banque de la graine s, de l'élément t, et de la clé privée u ; et - que les v numéros de série So à Sv-1 sont liés par la relation R. Soit, avec les notations précédentes : SoS +]+1 = 9 J c [v-1,N+v-2], SoZ=g, SIZ=g.SI,... Sv-lZ=g.Sv_1v-1, T= pkU .g R/(t+J+ VS = vrai). Au cours d'une étape I30, similaire à l'étape E30 décrite en référence à la figure 2, la carte à puce 10 fournit les numéros de série So à 15 Sv-1 et ces données de preuve POK. La figure 7 représente, sous forme d'organigramme, les principales d'un procédé de vérification conforme à l'invention dans ce troisième mode de réalisation. 20 Dans l'exemple décrit ici, ce procédé est mis en oeuvre par le lecteur de carte à puce 20 de la figure 1. Au cours d'une étape J10, le lecteur de carte à puce 20 obtient les numéros de série So à Sv-1 et les données de preuve POK fournies par la carte à puce 10 à l'étape I30 : 25 POK = POK(s, t, u, J, z, o- ; So s +3 + 1 = g, J c [v-1,N+v-2], SoZ=g, SIZ=g.SI,... Sv-lZ = g. Sv 30 T= pkU .g VS = vrai). Au cours d'une étape J20, le lecteur de carte à puce 20 vérifie cette preuve de connaissance, et notamment que la signature a été obtenue licitement par la carte à puce 10. 35 Puis, au cours d'une étape J30, le lecteur de carte à puce 20 accepte le paiement si cette preuve est correcte et le rejette dans le cas contraire. POK = POK(s, t, u, J, z, o- ; 10 Quatrième mode de réalisation La figure 8 représente, sous forme d'organigramme, les principales d'un procédé de paiement conforme à l'invention dans un quatrième mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par la carte à puce 10 de la figure 1. Au cours d'une étape K5, on associe à l'index J; de chacune des pièces du porte-monnaie électronique PME, une image J;' de cet index par une permutation secrète. Au cours d'une étape K10, similaire à l'étape E10 décrite en référence à la figure 2, la carte à puce 10 calcule les numéros de série So à Sv-1 en utilisant la fonction pseudo aléatoire fDYg,s(.), mais en utilisant les images J;' précédemment calculées : So = fDYg,s(J'o) = gl/ (s+ro+1) Si = fDYg,s(J'i) = gl / ( s + J'1 + 1) Sv-1 = fDYg,s(J'v) = g1 (s + ]'v 1 + 1) Puis, au cours d'une étape K20, la carte à puce 10 calcule des données de preuve POK, identiques à celles similaires à celles calculées au cours de l'étape E20 du premier mode de réalisation. Toutefois, il n'est pas nécessaire que ces données POK permettent de prouver la connaissance des images celles-ci étant destinées à être révélées. Ainsi, en reprenant les notations : POK = POK(s ; Sos So''o+l = g, Sis . S1''1+1 = g, ..., Sv 1s • Sv 1''v 1+1 = g). Au cours d'une étape K30, la carte à puce 10 fournit les numéros de série So à Sv-i, avec les images J;' des index J; correspondants, et les données de preuve POK au lecteur 20. La figure 9 représente, sous forme d'organigramme, les principales d'un procédé de vérification conforme à l'invention dans ce quatrième mode de réalisation. Dans l'exemple décrit ici, ce procédé est mis en oeuvre par le lecteur de carte à puce 20 de la figure 1. Au cours d'une étape L10, le lecteur de carte à puce 20 obtient les numéros de série So à Sv-i, avec les images J' des index J correspondants, et les données de preuve POK, fournis par la carte à puce 10 à l'étape K30. Au cours d'une étape L15, le lecteur de carte à puce 20 vérifie que chacune des images J' est positive et strictement inférieure à N, taille 5 du porte-monnaie électronique PME. Au cours d'une étape L20, le lecteur de carte à puce 20 vérifie les données de preuve POK, d'une façon similaire à celles déjà décrites pour les trois autres modes de réalisation. Puis, au cours d'une étape L30, le lecteur de carte à puce 20 10 accepte le paiement si ces données de preuve sont correctes et le rejette dans le cas contraire. REVENDICATIONS 1. Procédé de paiement électronique utilisant un sous-ensemble de (v) pièces d'un porte-monnaie électronique constitué par un ensemble (PME) de (N) pièces, chacune (i) des (v) pièces dudit sous-ensemble comportant un numéro de série (Si) calculé (E10, I7, I10) par une fonction pseudo aléatoire (FDYG,S) à partir d'une même graine (s) et d'un index (J) de ladite pièce dans ledit ensemble (PME), ce procédé comportant : - une étape (E20) de calcul de données de preuve (POK) pour valider ledit paiement en gardant secrets ladite graine (s) et ledit index (J) ; et une (E30, G30) étape de fourniture desdits numéros de série (Si) et desdites données de preuve (POK) à un tiers apte à valider ledit paiement ; ledit procédé étant caractérisé en ce que lesdites données de preuve (POK) permettent de prouver que : - chacun desdits numéros de série (Si) a été calculé à partir de ladite graine (s) ; - pour un nombre de pièces dudit sous ensemble appelées pièces témoins , ce nombre étant strictement inférieur au cardinal dudit sous-ensemble, ledit index (J) de chaque pièce témoin est un index d'un élément dudit ensemble (PME) ; et que - tous les numéros de série des pièces dudit sous-ensemble sont liés entre eux par une relation (R) déterminée. 2. Procédé de paiement selon la revendication 1, caractérisé en ce que lesdites données de preuve (POK) comportent : - un challenge (c) calculé (G24) à l'aide d'une fonction (H) déterministe et non prédictible à partir notamment d'un engagement (Q) obtenu (G23) à partir d'une combinaison desdits numéros de série (Si) et d'un aléa (r) ; et - une réponse (y) audit challenge (c) calculée (G25) à partir dudit challenge (c), de ladite graine (s) et dudit aléa (r). 3. Procédé de paiement selon la revendication 1 ou 2 caractérisé 35 en ce qu'il comporte :- une étape (I5) de calcul de ladite graine (s) à partir d'une clef privée (u) associée à une donnée de contrôle (6) ; et en ce que : - lesdites données de preuve (POK) permettent de prouver que ladite donnée de contrôle (6) a été obtenue licitement en utilisant ladite graine (s). 4. Procédé de paiement selon l'une quelconque des revendications 1 à 3 dans lequel ledit nombre de pièces témoins est nul, caractérisé en ce qu'il comporte : - une étape (K5) au cours de laquelle on associe à l'index (J) de chacune desdites pièces du porte-monnaie électronique (PME), une image (J') de cet index par une permutation secrète ; et en ce que - on fournit (K30) en outre audit tiers, et pour chacune des pièces dudit sous-ensemble, son numéro de série (Si) en association avec ladite image (J') de son index (J) par cette permutation. 5. Dispositif de paiement électronique utilisant un sous-ensemble de (v) pièces d'un porte-monnaie électronique constitué par un ensemble (PME) de (N) pièces, chacune (i) des (v) pièces dudit sous- ensemble comportant un numéro de série (Si) calculé par une fonction pseudo aléatoire (FDYG,S) à partir d'une même graine (s) et d'un index (J) de ladite pièce dans ledit ensemble (PME), ce dispositif comportant : - des moyens de calcul de données de preuve (POK) pour valider ledit paiement en gardant secrets ladite graine (s) et ledit index (J) ; et - des moyens de fourniture desdits numéros de série (Si) et desdites données de preuve (POK) à un dispositif tiers apte à valider ledit paiement ; ledit dispositif étant caractérisé en ce que lesdites données de preuve (POK) permettent de prouver que : - chacun desdits numéros de série (Si) a été calculé à partir de ladite graine (s) ; - pour un nombre de pièces dudit sous ensemble appelées pièces témoins , ce nombre étant strictement inférieur au cardinal dudit sous-ensemble, ledit index (J) de chaque pièce témoin est un index d'un élément dudit ensemble (PME) ; et- toutes les pièces dudit sous-ensemble sont liées entre elles par une relation (R) déterminée. 6. Dispositif de paiement électronique selon la revendication 5 caractérisé en ce qu'il est constitué par une carte à microcircuit. 7. Programme d'ordinateur comportant des instructions pour l'exécution des étapes du procédé de paiement électronique selon l'une quelconque des revendications 1 à 4 lorsque ledit programme est exécuté par un ordinateur. 8. Support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé de paiement électronique selon l'une quelconque des revendications 1 à 4. 9. Procédé de vérification de la validité d'un paiement électronique effectué avec des pièces électroniques comportant : - une étape ([10, H10) d'obtention des numéros de série (Si) desdites pièces et de données de preuve (POK) permettant de valider ledit paiement ; et - une étape (E30) de validation ou de rejet dudit paiement après vérification desdites données de preuve (POK), ledit procédé étant caractérisé en ce que lesdites données de preuve 25 (POK) permettent de prouver : - la connaissance d'une graine (s) et que chacun desdits numéros de série (Si) a été calculé par une fonction pseudo aléatoire (FDYG,S) à partir de ladite graine (s) ; - la connaissance d'un index (J) d'au moins une pièce électronique appelée 30 pièce témoin dont on a obtenu le numéro de série (Si), et que cet index (J) est un index d'un élément d'un ensemble (PME) déterminé de pièces ; et que - tous les numéros de série (Si) des pièces dont on a obtenu le numéro de série sont liés entre eux par une relation (R) déterminée. 35 10. Procédé de vérification selon la revendication 9, caractérisé en ce que lesdites données de preuve (POK) comportent un challenge (c) et une réponse (y) à ce challenge, et en ce qu'il comporte : - une étape (H23) de calcul d'un engagement test (Q') par une 5 combinaison prenant en compte lesdits numéros de série (Si), ledit challenge (c) et ladite réponse (y) ; - une étape (H24) de calcul d'un challenge test (c') à l'aide d'une fonction (H) déterministe et non prédictible portant notamment sur ledit engagement test (Q') ; et 10 - une étape (H30) de comparaison dudit challenge (c) et dudit challenge test (c') pour valider ou rejeter ledit paiement. 11. Procédé de vérification selon la revendication 9 ou 10, caractérisé en ce que lesdites données de preuve (POK) permettent de 15 prouver la connaissance d'une donnée de contrôle (6) utilisée pour calculer ladite graine (s). 12. Procédé de vérification selon l'une quelconque des revendications 9 à 11 dans lequel ledit nombre de pièces témoins est nul 20 caractérisé en ce qu'il comporte : - une étape (L10) d'obtention, pour chacune des pièces utilisées pour ledit paiement, et en association avec le numéro de série (Si) de cette pièce, une image (J') d'un index (J) de cette pièce par une permutation secrète ; et 25 - une étape (L15) au cours de laquelle on vérifie que ladite image (J') est un élément dudit ensemble (PME). 13. Dispositif de vérification de la validité d'un paiement électronique effectué avec des pièces électroniques comportant : 30 - des moyens pour obtenir des numéros de série (Si) desdites pièces et des données de preuve (POK) permettant de valider ledit paiement ; et - des moyens pour valider ou rejeter ledit paiement après vérification desdites données de preuve (POK), ledit dispositif étant caractérisé en ce que lesdites données de preuve 35 (POK) permettent de prouver :- la connaissance d'une graine (s) et que chacun desdits numéros de série (Si) a été calculé par une fonction pseudo aléatoire (FDYG,S) à partir de ladite graine (s) ; - la connaissance d'un index (J) d'au moins une pièce électronique appelée pièce témoin dont on a obtenu le numéro de série (Si), et que cet index (J) est un index d'une pièce d'un porte-monnaie électronique (PME) ; et -que toutes lesdites pièces dont on a obtenu le numéro de série (Si) sont liées entre elles par une relation (R) déterminée. 14. Dispositif de vérification selon la revendication 13, caractérisé en ce qu'il est constitué par un lecteur de carte à puce. 15. Programme d'or dinateur comportant des instructions pour l'exécution des étapes du procédé vérification selon l'une quelconque des revendications 9 à 12 lorsque ledit programme est exécuté par un ordinateur. 16. Support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé de vérification selon l'une quelconque des revendications 9 à 12.