Brevet FR2949033A1 — publié le 20110211

PROCEDE DE RECHERCHE D'UNE ENTITE A L'AIDE D'UN DISPOSITIF VERIFICATEUR ET DISPOSITIFS ASSOCIES La présente invention concerne la recherche d'une entité appartenant à un ensemble d'entités. On entend par entité, tout élément matériel et/ou logiciel, éventuellement associé à un dispositif, un système ou un individu. A titre d'exemples non limitatifs, on peut citer un marqueur d'identification sans fil, tel qu'une étiquette RFID (Radio Frequency IDentification), un badge d'accès, une carte à puce, un téléphone portable, un ordinateur connecté à un réseau, ou autre. Pour rechercher une entité, il est connu d'utiliser un dispositif vérificateur. Ce dernier peut également prendre des formes diverses en fonction du type d'entités qu'il vise à rechercher. Il peut par exemple s'agir d'un lecteur d'identification sans fil, tel qu'un lecteur RFID, d'un capteur, d'un serveur, ou autre. Le dispositif vérificateur et les entités communiquent entre eux par l'intermédiaire d'au moins un canal de communication prévu à cet effet, qui peut être filaire ou sans fil selon les besoins. Selon une première méthode connue, la recherche d'une entité appartenant à un ensemble d'entités à l'aide d'un dispositif vérificateur est effectuée en transmettant sur le canal de communication depuis chaque entité un identifiant respectif, et en analysant au dispositif vérificateur les identifiants reçus pour conclure à la présence ou non de l'entité recherchée. Selon une deuxième méthode connue, la recherche est effectuée en transmettant depuis le dispositif vérificateur l'identifiant de l'entité recherchée par l'intermédiaire du canal de communication, puis le cas échéant en recevant sur le canal de communication une réponse de l'entité ayant reconnu son identifiant dans cette transmission. Cette deuxième méthode est plus économique que la première, car elle permet de limiter le nombre de messages échangés sur le canal de communication et le traitement nécessaire au dispositif vérificateur pour trouver l'entité recherchée. Elle n'est cependant pas sans poser de problèmes. En particulier, elle ne protège pas l'identité des entités. Cela peut être particulièrement gênant lorsque les entités se rapportent à des individus, le respect de la vie privée de ces derniers n'étant alors pas assuré. C'est également gênant lorsque les entités se rapportent à du matériel ayant une valeur marchande et/ou financière, dont on souhaite empêcher la traçabilité par des tiers. En effet, un attaquant à l'écoute du canal de communication peut intercepter l'identifiant transmis par le dispositif vérificateur et découvrir, en détectant la réponse envoyée, à quelle entité cet identifiant appartient. Un but de la présente invention est de permettre une recherche d'entité améliorant la protection de son identité. L'invention propose ainsi un procédé de recherche d'une entité appartenant à un ensemble d'entités à l'aide d'un dispositif vérificateur, le dispositif vérificateur et les entités dudit ensemble d'entités étant agencés pour échanger des informations par l'intermédiaire d'au moins un canal de communication, chaque entité dudit ensemble d'entités possédant un premier identifiant respectif à partir duquel une pluralité de représentants peuvent être obtenus. Ce procédé comprend les étapes suivantes : - obtenir au dispositif vérificateur un premier mot d'identification relatif à une entité recherchée, le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée d'une première fonction de codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable ; et - transmettre, depuis le dispositif vérificateur, le premier mot d'identification obtenu sur le canal de communication. L'utilisation d'une fonction de codage capable de générer un premier mot d'identification dépendant d'une partie seulement des représentants - 2 2949033 -3- permet d'améliorer considérablement la protection de l'identité des entités par rapport à l'art antérieur mentionné en introduction. Selon des modes de réalisation avantageux pouvant être combinés de toutes les manières envisageables : 5 - le procédé comprend en outre les étapes suivantes, mises en oeuvre par chaque entité dudit ensemble d'entités à l'écoute du canal de communication : o recevoir un mot d'identification correspondant au premier mot d'identification transmis sur le canal de communication ; et 10 o appliquer une première fonction d'identification associée à la première fonction de codage au mot d'identification reçu et à une information connue par ladite entité parmi le premier identifiant de ladite entité et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit premier 15 identifiant, de façon à vérifier si ladite entité correspond à l'entité recherchée ; et/ou - une indication de la valeur du paramètre variable utilisée pour former le premier mot d'identification obtenu est transmise depuis le dispositif vérificateur sur le canal de communication, et pour chaque entité dudit 20 ensemble d'entités à l'écoute du canal de communication, ladite application de la première fonction d'identification tient compte de l'indication de la valeur du paramètre variable reçue ; et/ou - lorsque le résultat de ladite application de la première fonction d'identification révèle que ladite entité correspond à l'entité recherchée, 25 ladite entité envoie une réponse au dispositif vérificateur par l'intermédiaire du canal de communication ; et/ou - ladite entité possède un deuxième identifiant à partir duquel une pluralité de représentants peuvent être obtenus, on obtient à ladite entité un deuxième mot d'identification par application d'une deuxième fonction de 30 codage à une information connue par ladite entité parmi le deuxième identifiant de ladite entité et au moins un représentant de la pluralité de 2949033 -4- représentants pouvant être obtenus à partir dudit deuxième identifiant de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit deuxième identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable, la réponse 5 envoyée par ladite entité au dispositif vérificateur par l'intermédiaire du canal de communication inclut le deuxième mot d'identification ; et/ou - on reçoit au dispositif vérificateur un mot d'identification correspondant au deuxième mot d'identification inclus dans ladite réponse, le dispositif vérificateur applique une deuxième fonction d'identification associée à la 10 deuxième fonction de codage au mot d'identification reçu au dispositif vérificateur et à une information connue par le dispositif vérificateur parmi le deuxième identifiant de ladite entité et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit deuxième identifiant, de façon à effectuer une vérification 15 complémentaire d'une correspondance entre ladite entité et l'entité recherchée ; et/ou - la première fonction de codage est agencée pour que, lorsqu'elle est appliquée au premier identifiant de l'entité recherchée, ledit paramètre variable sélectionne au moins un représentant de la pluralité de 20 représentants pouvant être obtenus à partir dudit premier identifiant, ladite application de la première fonction d'identification comprend une comparaison entre ledit représentant sélectionné par ledit paramètre variable et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir du premier identifiant de ladite entité ; 25 et/ou - la valeur du paramètre variable utilisée pour former le premier mot d'identification obtenu est choisie de façon aléatoire ou quasi aléatoire ; et/ou - le premier mot d'identification obtenu est transmis sur le canal de 30 communication depuis le dispositif vérificateur de façon codée à l'aide d'un code correcteur d'erreurs ; et/ou 2949033 -5- - le canal de communication est un canal sans-fil, tel qu'un canal radio, et le dispositif vérificateur comprend un lecteur d'identification sans fil et certaines au moins des entités de l'ensemble d'entités comprennent des marqueurs d'identification sans fil ; et/ou 5 - la faculté d'obtenir la pluralité de représentants pouvant être obtenus à partir d'un identifiant n'est donnée qu'à l'entité dudit ensemble d'entités possédant ledit identifiant et au dispositif vérificateur ; et/ou - la première fonction de codage est agencée pour qu'un même premier mot d'identification puisse être le résultat de l'application de la première 10 fonction de codage à plusieurs identifiants distincts parmi l'ensemble de tous les identifiants possibles. L'invention propose en outre un dispositif vérificateur agencé pour échanger des informations avec un ensemble d'entités par l'intermédiaire d'au moins un canal de communication, chaque entité dudit ensemble d'entités 15 possédant un premier identifiant respectif à partir duquel une pluralité de représentants peuvent être obtenus. Ce dispositif vérificateur comprend : - une unité d'obtention d'un premier mot d'identification relatif à une entité recherchée, le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée d'une première fonction de 20 codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable ; et - une unité de transmission sur le canal de communication du premier mot 25 d'identification obtenu par ladite unité d'obtention. L'invention propose aussi une entité appartenant à un ensemble d'entités capables d'échanger des informations avec un dispositif vérificateur par l'intermédiaire d'au moins un canal de communication et possédant chacune un premier identifiant respectif à partir duquel une pluralité de 30 représentants peuvent être obtenus. Ladite entité comprend : 2949033 -6- - une unité de réception d'un mot d'identification correspondant à un premier mot d'identification transmis sur le canal de communication par le dispositif vérificateur, le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée d'une première 5 fonction de codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable ; et - une unité d'application d'une première fonction d'identification associée 10 à la première fonction de codage au mot d'identification reçu et au premier identifiant de ladite entité et à une information connue par ladite entité parmi le premier identifiant de ladite entité et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, de façon à vérifier si ladite entité 15 correspond à l'entité recherchée. L'invention propose encore un système de recherche d'une entité appartenant à un ensemble d'entités à l'aide d'un dispositif vérificateur, le système comprenant des moyens adaptés pour la mise en oeuvre du procédé mentionné plus haut. 20 D'autres particularités et avantages de la présente invention apparaîtront dans la description ci-après d'exemples de réalisation non limitatifs, en référence aux dessins annexés, dans lesquels : - la figure 1 est un schéma d'architecture pour un exemple de système capable de mettre en oeuvre l'invention ; 25 - les figures 2 à 4 sont des schémas montrant des exemples non-limitatifs de réalisation de l'invention. La figure 1 montre un dispositif vérificateur 1 et un ensemble d'entités agencés pour échanger des informations par l'intermédiaire d'un canal de communication 2. Les entités 3-5 représentées peuvent constituer à elles 30 seules l'ensemble des entités existantes. En variante, elles peuvent ne correspondre qu'aux entités capables de communiquer par l'intermédiaire du canal de communication à un instant donné. D'autres entités peuvent alors -7- éventuellement s'y ajouter ou les remplacer à d'autres instants d'observation. Comme indiqué en introduction, chaque entité 3-5 peut consister en tout élément matériel et/ou logiciel, éventuellement associé à un dispositif, un système ou un individu. Dans l'exemple de la figure 1, les entités 3-5 ont été représentées comme étant des marqueurs d'identification sans fil, tels que des étiquettes RFID (Radio Frequency IDentification). En variante, il pourrait s'agir de badges d'accès, de cartes à puce, de téléphones portables, d'ordinateurs connectés à un réseau, ou autres. Les entités 3-5 peuvent en outre ne pas toutes être de la même nature. A titre d'illustration, elles pourraient se rapporter à un téléphone portable pour la première, à une étiquette RFID associée à une marchandise pour la deuxième, et à un ordinateur pour la troisième. Le dispositif vérificateur 1 peut lui aussi prendre des formes diverses en fonction du type d'entités qu'il vise à rechercher, comme également rappelé en introduction. Il peut par exemple s'agir d'un lecteur d'identification sans fil, tel qu'un lecteur RFID comme illustré sur la figure 1, d'un capteur, d'un serveur, ou autre. Le canal de communication 2, quant à lui, est adapté à l'échange d'informations entre le dispositif vérificateur 1 et les entités 3-5. Selon les besoins, il peut être filaire ou bien sans-fil. Dans l'exemple de la figure 1, le canal de communication 2 est un canal radio puisque le dispositif vérificateur 1 est un lecteur RFID et que tout ou partie des entités 3-5 sont des étiquettes RFID. Lorsque des entités de nature différente doivent pouvoir communiquer avec le dispositif vérificateur, plusieurs canaux de communication peuvent être utilisés. Par exemple, un canal de communication filaire et un canal de communication sans-fil peuvent être utilisés en relation avec des entités filaires et sans-fil respectivement. De plus, le canal de communication 2 peut être simple, c'est-à-dire qu'il offre une communication directe entre le dispositif vérificateur 1 et les entités 3-5, par exemple via une fréquence radio donnée. En alternative, ce canal de communication 2 peut être plus élaboré. Il peut par exemple consister en un ensemble de ressources de communications d'un réseau de communication, comme un réseau informatique, un réseau de télécommunication ou autre. 2949033 -8- Selon l'invention, on recherche une entité appartenant à l'ensemble des entités mentionné plus haut, par exemple l'entité 4, à l'aide du dispositif vérificateur 1. Autrement dit, on cherche à savoir, à l'aide du dispositif vérificateur 1, si l'entité 4 est à l'écoute du canal de communication 2. Lorsque 5 le canal de communication 2 est un canal de faible portée, cela revient à chercher si l'entité 4 est à proximité du dispositif vérificateur 1. On comprendra que la nature du dispositif vérificateur 1, des entités 3-5 et du canal de communication 2 sera adaptée à l'application visée. Ainsi, si l'on souhaite pouvoir contrôler la présence d'individus à l'intérieur de sites 10 sensibles ou bien l'accès d'un faible nombre d'individus à des sites sensibles, on peut par exemple utiliser des badges d'accès équipés de puces RFID associés à des individus comme entités, un lecteur RFID comme dispositif vérificateur, et un canal radio utilisant des fréquences adaptées à la technologie RFID comme canal de communication. En variante, si l'on souhaite 15 conditionner la mise en oeuvre d'une application informatique en ligne à un contrôle d'identité, le canal de communication peut alors consister en des ressources de communication d'un réseau informatique, les entités utilisées peuvent comprendre des ordinateurs connectés à ce réseau, et le dispositif vérificateur est par exemple un serveur connecté à ce réseau. 20 Bien sûr, bien d'autres exemples d'application peuvent être envisagés selon les principes de l'invention, comme cela apparaîtra à l'homme du métier. Chacune des entités 3-5 possède un identifiant respectif, au sens où il existe une association entre cette entité et l'identifiant respectif. Une pluralité de représentants peuvent être obtenus à partir d'un tel identifiant. Par exemple, 25 un identifiant m relatif à une entité peut être directement composé d'une pluralité de représentants mk, avec k allant de 1 à un entier n, c'est-à-dire que m=(mi,m2,...,mn). Dans ce cas, chaque représentant mk peut être obtenu à partir de l'identifiant m par une simple sélection au sein de m. De façon plus générale, la pluralité de représentants mk peuvent être obtenus à partir de 30 l'identifiant m correspondant à l'aide d'une ou plusieurs fonctions de génération fk prévues à cet effet. Ceci peut par exemple s'exprimer comme suit : mk=fk(m). On peut aussi prévoir qu'une même fonction de génération f permette de 2949033 -9- déduire tous les représentants mk à partir de l'identifiant m, par exemple par un processus itératif, en obtenant successivement les différents représentants à partir d'un ou plusieurs représentants déjà obtenus. Un identifiant est par exemple une chaîne de valeurs, par exemple des 5 éléments binaires, des octets ou autres. Dans le cas où m=(mi,m2,...,mn), chaque représentant mk peut par exemple constituer ou une plusieurs valeurs successives de m. D'autres constructions sont bien sûr possibles, comme cela apparaîtra à l'homme du métier. Chaque identifiant est de préférence unique, pour éviter une ambigüité 10 entre des entités ainsi identifiées. En revanche, certains identifiants peuvent éventuellement avoir des représentants communs. Les identifiants peuvent être formés selon un modèle donné. A titre d'exemple, les identifiants peuvent être formés comme des chaînes de n éléments binaires, ce qui permet d'avoir 2n identifiants au total. On peut ainsi 15 obtenir un nombre d'identifiants possibles plus élevé que le nombre d'entités réellement en jeu. Chacune des entités 3-5 est capable de connaître son identifiant, ou bien la pluralité de représentants pouvant être obtenus à partir de son identifiant. Cette connaissance peut provenir de ce que l'identifiant et/ou les 20 représentants correspondants sont stockés dans une mémoire de l'entité concernée. En variante, elle peut être acquise par consultation d'une mémoire externe, par réception de ces informations à partir d'une mémoire externe, ou autre. Le dispositif vérificateur 1, quant à lui, est capable de connaître 25 l'identifiant et/ou la pluralité de représentants pouvant être obtenus à partir de l'identifiant de chacune des entités de l'ensemble des entités. Là encore, cette connaissance peut provenir d'un stockage dans une mémoire du dispositif vérificateur 1, d'une consultation d'une mémoire externe, d'une réception de ces informations à partir d'une mémoire externe, ou autre. 30 Avantageusement, la faculté d'obtenir la pluralité de représentants pouvant être obtenus à partir d'un identifiant n'est donnée qu'à l'entité possédant cet identifiant et au dispositif vérificateur. Ceci peut être réalisé de -10-plusieurs façons. Par exemple, l'identifiant en question peut être stocké dans des mémoires protégées qui ne sont accessibles qu'à l'entité possédant cet identifiant d'une part et au dispositif vérificateur d'autre part. L'identifiant n'est jamais transmis sur le canal de communication. L'identifiant de ladite entité n'étant pas connu des tiers, ces derniers sont dans l'incapacité d'obtenir ses représentants. En variante ou en complément, les représentants de l'identifiant en question peuvent être stockés dans des mémoires protégées qui ne sont accessibles qu'à l'entité possédant cet identifiant d'une part et au dispositif vérificateur d'autre part. Ils ne sont pas tous transmis simultanément sur le canal de communication. Les tiers ne peuvent donc pas connaître les représentants relatifs à ladite entité. On peut aussi prévoir que l'identifiant en question soit une donnée publique, mais que la fonction de génération permettant d'obtenir les représentants correspondants soit secrète. De cette façon, on évite qu'un tiers disposant de l'identifiant puisse en déduire les représentants correspondants. La recherche d'une entité selon l'invention met en oeuvre la notion de code d'identification. Un exemple de cette notion de code d'identification est notamment décrit dans l'article de Rudolf Ahlswede et Gunter Dueck intitulé � Identification via Channels �, IEEE transactions in information theory, Vol.35, No. 1, publié en janvier 1989. De façon générale, un mot c d'un tel code d'identification, ci-après appelé un mot d'identification, est calculé par application d'une fonction de codage à un identifiant m à partir duquel une pluralité de représentants mk, avec k allant de 1 à un entier n, peuvent être obtenus. La fonction de codage fc est choisie pour que le mot d'identification obtenu dépende d'une sous-partie de la pluralité de représentants mk. Autrement dit, le mot d'identification peut dépendre d'un ou plusieurs représentants mk de m, mais pas de tous les représentants La sous-partie de la pluralité de représentants mk dont dépend le mot d'identification est déterminée par au moins un paramètre variable. 2949033 -11- Une fonction d'identification fi est associée à la fonction de codage fc utilisée pour calculer le mot d'identification c à partir de l'identifiant m. Les propriétés du code d'identification sont par exemple telles que : - si yl est un mot obtenu par application de la fonction de codage fc à 5 l'identifiant m, l'application de la fonction d'identification fi à yl et à m ou certains au moins de ses représentants conclut à tort à une absence de correspondance avec une probabilité inférieure à x1 ; et - si y2 est un mot obtenu par application de la fonction de codage fc à l'identifiant m' distinct de m, l'application de la fonction d'identification fi à 10 y2 et à m ou certains au moins de ses représentants conclut à tort à une correspondance avec une probabilité inférieure à X2. Plus X1 et a,2 sont faibles, plus le code d'identification est fiable. Avantageusement, la fonction de codage fc utilisée dans le cadre de la présente invention peut être en outre agencée pour qu'un même mot 15 d'identification puisse être le résultat de l'application de cette fonction de codage fc à plusieurs identifiants distincts parmi l'ensemble de tous les identifiants possibles. A titre d'exemple non limitatif, si les identifiants consistent chacun en une série de représentants, certains représentants pouvant être communs entre au moins deux identifiants distincts, une fonction 20 de codage fc consistant à sélectionner un représentant de rang donné dans une série de représentants pourra parfois retourner une même valeur en étant appliquée à deux identifiants distincts. Un exemple spécifique et intéressant de code d'identification pouvant être utilisé dans le cadre de la présente invention est celui qui est décrit dans 25 l'article de Pierre Moulin et Raft Koetter intitulé � A framework for the Design of Good Watermark Identification Codes �, Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California ; p. 565-574; ISBN / ISSN: 0-8194-6112-1, publié en janvier 2006. Tout autre code d'identification peut bien sûr être mis en oeuvre en remplacement ou en 30 complément de celui-ci. La recherche d'une entité selon l'invention se fait en obtenant dans une 2949033 -12- unité d'obtention du dispositif vérificateur 1, un mot d'identification c relatif à l'entité recherchée. Cette obtention peut être effectuée par un calcul selon les principes exposés ci-dessus, réalisé au dispositif vérificateur, dans un dispositif distinct transmettant le mot d'identification calculé au dispositif vérificateur, ou 5 bien de façon partagée entre ces deux dispositifs. En variante, cette obtention peut être réalisée en retrouvant le mot d'identification c relatif à l'entité recherchée, par exemple dans une mémoire du dispositif vérificateur 1. Une fois le mot d'identification c obtenu au dispositif vérificateur 1, une unité de transmission de ce dernier le transmet sur le canal de communication 10 2. Le canal de communication 2 étant commun à toutes les entités, le mot d'identification transmis peut être reçu par toute entité 3-5 à l'écoute de ce canal. Chaque entité 3-5 ayant reçu, à l'aide d'une unité de réception appropriée, un mot d'identification correspondant au mot d'identification 15 transmis (éventuellement à des erreurs de transmission près, lorsque le canal de communication 2 introduit des erreurs, par exemple parce qu'il est bruité), peut alors avantageusement appliquer, à l'aide d'une unité d'application appropriée, la fonction d'identification fi associée à la fonction de codage fc au mot d'identification reçu et à une information qu'elle connaît parmi son 20 identifiant et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir de son identifiant, de façon à vérifier si ladite entité correspond à l'entité recherchée. Pour renforcer la fiabilité de la vérification effectuée par chaque entité 3-5, le mot d'identification obtenu par le dispositif vérificateur 1 est 25 avantageusement transmis avec un code de transmission qui est un code correcteur d'erreurs. Tout code correcteur d'erreurs connu peut être utilisé à cet effet. Chaque entité 3-5 dispose alors avantageusement de la fonction de décodage associée qui lui permet de retrouver le mot d'identification transmis par le dispositif vérificateur 1, exempt d'erreur ou du moins avec une quantité 30 d'erreur limitée. On privilégiera un code correcteur d'erreurs adapté à la nature des entités 3-5, du dispositif vérificateur 1 et du canal de communication 2. A titre 2949033 -13- d'exemple, si les échanges d'informations ont lieu sur un canal de communication 2 sans-fil et très bruité, un code correcteur d'erreurs robuste, avec par exemple une forte redondance sera favorisé. Le mode de construction des identifiants et de leurs représentants peut 5 également être pris en compte dans le choix du code correcteur d'erreurs utilisé. Par exemple, si au moins une des probabilités X1 et a,2 mentionnées plus haut est élevée, on peut vouloir privilégier un code correcteur d'erreurs capable de corriger une quantité importante d'erreurs pour ne pas aggraver les faibles performances de l'identification. 10 Des exemples de réalisation non limitatifs vont désormais être décrits pour illustrer le type de vérification possible selon l'invention. Dans tous ces exemples, on reprend l'architecture de la figure 1, et on suppose que l'on recherche l'entité 4 à l'aide du dispositif vérificateur 1. Dans l'exemple illustré sur la figure 2, les identifiants des entités sont 15 des chaînes de valeurs consistant en des séries de représentants. En particulier, l'entité 4 a pour identifiant m=(mi,m2,...,mn), dont m1,m2,...,mn sont les représentants. Dans un premier temps, le dispositif vérificateur 1 choisit un nombre i entre 1 et n. Le choix de i peut se faire de façon aléatoire ou quasi aléatoire. 20 Puis, le dispositif vérificateur 1 sélectionne le représentant m; de m de rang i dans la chaîne m=(mi,m2,...,mn). C'est ce représentant m; qui constitue alors le mot d'identification c dans ce cas. Dans cet exemple, le choix du représentant par son rang dans l'identifiant m est un paramètre variable qui détermine la sous-partie de la 25 pluralité de représentants pouvant être obtenus à partir de l'identifiant m, en l'occurrence un seul des n représentants. En variante, plusieurs indices au lieu du seul indice i pourraient être choisis pour sélectionner plus d'un représentant. Par exemple, le tirage éventuellement aléatoire des nombres (i,j) entre 1 et n pourrait permettre 30 d'obtenir un mot d'identification c du type (m;,mi) ou encore toute combinaison entre m; et mi, comme par exemple m; + mi. 2949033 -14- A l'étape 6 de la figure 2, le dispositif vérificateur 1 transmet le mot d'identification m; obtenu sur le canal de communication 2. Avantageusement, le dispositif vérificateur 1 transmet également sur le canal de communication 2 le nombre i ayant servi à sélectionner le représentant m;, ou toute autre 5 indication de la valeur de i. Ces deux informations peuvent être transmises dans un même message ou bien dans deux messages distincts. Par la suite, chacune des entités 3-5 à l'écoute du canal de communication 2 ayant reçu un mot d'identification correspondant au mot d'identification m; transmis par le dispositif vérificateur 1 peut vérifier si elle est 10 l'entité recherchée. En particulier, l'entité 4 reçoit un mot d'identification mi qui correspond à m;, éventuellement à quelques erreurs de transmission près. Elle reçoit aussi avantageusement le nombre i qui correspond à i, éventuellement à quelques erreurs de transmission près. 15 La fonction de codage fc mise en oeuvre par le dispositif vérificateur 1 consistait à sélectionner un représentant parmi la pluralité de représentants m1,m2,...,mn de l'entité 4. La fonction d'identification fi associée à cette fonction de codage et mise en oeuvre par l'entité 4 (ainsi que par chacune des autres entités à l'écoute du canal de communication 2) consiste, quant à elle, à 20 retrouver le représentant de rang i au sein de l'identifiant m de l'entité 4, puis à le comparer au mot d'identification mi reçu. En cas de concordance, l'entité 4 considère qu'elle est bien l'entité recherchée et envoie avantageusement une réponse 7 via le canal de communication 2 au dispositif vérificateur 1 pour l'en informer. 25 On notera que si le nombre i n'est pas transmis par le dispositif vérificateur 1, la vérification est toujours possible à l'entité 4, mais en comparant le mot d'identification mi à tout ou partie des représentants plutôt qu'au seul représentant de rang i . Dans l'exemple ci-dessus, on a considéré que l'entité 4 pouvait 30 connaître son identifiant m, par exemple parce qu'elle le stockait en mémoire. 2949033 -15- Si seuls les représentants m1,m2,...,mn de m sont connus par l'entité, sans que leur ordre au sein de m le soit, on peut également procéder à une comparaison du mot d'identification mi reçu avec tout ou partie des représentants connus de l'entité 4. 5 Dans ces deux derniers cas, une concordance entre le mot d'identification mi reçu et l'un quelconque des représentants connus ou obtenus à partir de m par l'entité 4 peut suffire à conclure que l'entité 4 est bien l'entité recherchée. Dans le cas où l'entité 4 envoie une réponse 7 au dispositif vérificateur 10 1 par l'intermédiaire du canal de communication 2, cette réponse peut simplement signifier que l'entité 4 se considère comme correspondant à l'entité recherchée. A l'inverse, si les entités 3 et 5 ne se considèrent pas comme correspondant à l'entité recherchée, elles n'envoient pas de réponse au dispositif vérificateur 1. Ce dernier est alors capable de conclure que l'entité 4 15 est bien celle qu'il recherche. La fonction de codage étant probabiliste, et non déterministe, il est possible que plusieurs entités se considèrent comme étant l'entité recherchée. Dans ce cas, le dispositif vérificateur 1 peut recevoir plusieurs réponses 7 à sa requête 6 depuis plusieurs entités par l'intermédiaire du canal de 20 communication 2. Il pourra alors avantageusement affiner sa recherche pour identifier l'entité recherchée. A titre d'exemple, il pourra réinterroger les entités 3-5 en choisissant et en transmettant un couple (j,m;) distinct de (i,m;). Avantageusement, le couple (j,m;) transmis sera choisi pour éviter une nouvelle ambigüité entre les entités qui ont envoyé des réponses 7, c'est-à-dire de façon 25 qu'une seule de ces entités se considère comme correspondant à l'entité recherchée. Dans l'exemple illustré sur de la figure 2, la réponse 7 envoyée par l'entité 4 par l'intermédiaire du canal de communication 2 contient de l'information basée sur le même principe que la requête 6. 30 A cet effet, en plus de m, l'entité 4 connaît, de par un stockage dans sa mémoire par exemple, un deuxième identifiant M=(M1,M2,...,Mn) ou bien tout 2949033 -16- ou partie de ses représentants M1,M2,...,Mn sans considération d'ordre. Elle dispose en outre d'une deuxième fonction de codage Fc qui peut être différente ou identique à fc. L'entité 4 est alors capable d'obtenir un deuxième mot d'identification par application de la deuxième fonction de codage Fc à 5 l'information qu'elle connaît parmi M et au moins un des représentants M1,M2,...,Mn. Dans l'exemple de la figure 2, la deuxième fonction de codage Fc est la même que fc et son paramètre variable est fixé à la même valeur que celle choisie par le dispositif vérificateur 1, c'est-à-dire i. Ainsi, la réponse 7 envoyée 10 par l'entité 4 inclut le deuxième mot d'identification M. Le nombre i peut éventuellement être transmis en plus de M; si le dispositif vérificateur 1 ignore que la deuxième fonction de codage Fc utilise la même valeur de paramètre variable que fc. Il est possible que le deuxième identifiant M soit en fait le même que le 15 premier identifiant m. Dans ce cas, la réponse 7 inclura de préférence un couple (j,m;) distinct de (i,m;). Le fait d'inclure ainsi de l'information supplémentaire dans la réponse 7 peut permettre au dispositif vérificateur 1 d'effectuer une vérification complémentaire d'identité. On notera que ce mode de fonctionnement n'est 20 pas limité au type d'identifiant décrit en référence à la figure 2, mais pourrait s'appliquer quel que soit le format d'identifiant utilisé. Pour effectuer une telle vérification complémentaire d'identité, le dispositif vérificateur 1 dispose avantageusement d'une deuxième fonction d'identification Fi associée à la deuxième fonction de codage Fc. Comme cela 25 a été décrit en relation avec l'entité 4, le dispositif vérificateur 1 applique la deuxième fonction d'identification Fi au mot d'identification Mi reçu au dispositif vérificateur 1 et à une information connue par le dispositif vérificateur 1 parmi l'identifiant M de l'entité 4 et au moins un de ses représentants M1,M2,...,Mn. Cette vérification complémentaire permet de confirmer ou au contraire 30 d'infirmer que l'entité 4 est l'entité recherchée. Cette option est intéressante car elle limite les erreurs d'identification susceptibles de survenir dans le modèle -17-probabiliste de l'invention. Par rapport aux méthodes de l'art antérieur mentionnées en introduction, l'exemple qui vient d'être décrit permet de comprendre que l'invention peut autoriser une recherche d'entité améliorant la protection de son identité. En effet, un attaquant à l'écoute du canal de communication 2 et n'ayant pas une connaissance a priori des identifiants des entités et de leurs représentants ne sera en général pas capable de retrouver l'identifiant m de l'entité 4 à partir des représentants transmis m; et M. La tâche de l'attaquant à l'écoute du canal de communication 2 est rendue particulièrement difficile, du fait que le codage réalisé est probabiliste, et non déterministe, car il dépend d'au moins un paramètre variable. De ce fait, des mots d'identification différents peuvent permettre d'identifier une même entité. En outre, le nombre total de mots d'identification possibles est bien plus élevé que le nombre total d'identifiants. Il est donc quasi impossible pour un attaquant de découvrir tous les mots d'identification se rapportant à une entité donnée en écoutant le canal de communication 2 pendant un temps limité. Et même si l'attaquant était capable de connaître les identifiants de certaines entités et/ou leurs représentants, il ne serait pas forcément en mesure de conclure avec certitude quant à l'identité de l'entité ayant envoyé une réponse, notamment dans le cas où la fonction de codage est susceptible de conduire à un même mot d'identification lorsqu'elle est appliquée à plusieurs identifiants distincts. Ainsi, l'invention peut notamment permettre d'améliorer le respect de la vie privée d'individus et de rendre plus difficile la traçabilité de matériel. Un autre avantage de l'invention réside dans son efficacité. Dans l'exemple décrit en référence à la figure 2, si l'on suppose que chaque représentant m1,m2,...,mn constituant l'identifiant m consiste en un octet, c'est- à-dire huit bits, la recherche peut ne nécessiter approximativement que la 2949033 -18- transmission d'un octet (transmission de mi à l'étape 6). En comparaison, la transmission de l'intégralité de l'identifiant m=(mi,m2,...,mn) par le dispositif vérificateur, comme dans l'art antérieur, nécessite quant à elle n octets. Les avantages ci-dessus ne sont pas limités à l'exemple décrit en 5 référence à la figure 2 comme cela apparaîtra à l'homme du métier. La figure 3 montre un autre exemple de réalisation de l'invention. Dans cet exemple, chacune des entités 3-5 possède un identifiant sous la forme d'un polynôme respectif. Les représentants pouvant être obtenus à partir d'un tel identifiant sont par exemple des évaluations de ce polynôme en différents 10 points, ou des coefficients de ce polynôme. Par exemple, l'identifiant relatif à l'entité 4 peut être le polynôme p(x) et les représentants correspondants peuvent être les évaluations de ce polynôme en un ensemble de points déterminés x1,x2,...,xn avec n entier, soit p(xi), p(x2),...,p(xn). 15 La fonction de codage fc utilisée par le dispositif vérificateur 1 dans ce cas peut par exemple consister à sélectionner aléatoirement une de ces évaluations, par exemple p(x;). Ce mot d'identification p(x;) est transmis depuis le dispositif vérificateur 1 sur le canal de communication 2 à l'étape 8. A réception d'un mot d'identification correspondant, chacune des 20 entités 3-5 à l'écoute du canal de communication 2 le compare à tout ou partie des évaluations qu'elle a par exemple elle-même en mémoire, pour déterminer une éventuelle adéquation. En cas de concordance par exemple pour l'entité 4, cette dernière envoie une réponse 9 au dispositif vérificateur 1 par l'intermédiaire du canal de 25 communication 2. Cette réponse peut par exemple inclure une évaluation p(Xi) obtenue par application du polynôme p à un point X; distinct de En variante, la réponse 9 pourrait inclure une évaluation P(x;), où P est un polynôme distinct de p. En variante encore, la réponse 9 pourrait inclure une évaluation p(xi) avec j différent de i. 30 La figure 4 montre un autre exemple de réalisation, dans lequel chaque entité a pour identifiant un nombre, par exemple compris entre 1000 et 10000, 2949033 -19- et dans lequel les représentants pouvant être obtenus à partir de cet identifiant sont des vecteurs binaires de longueur fixe, par exemple 20000, et dont le poids est égal à l'identifiant correspondant. Ainsi, tous les représentants m1,m2,...,mn pouvant être obtenus à partir de l'identifiant N, avec N compris 5 entre 1000 et 10000, ont par exemple un nombre de 1 égal à N et un nombre de 0 égal à 20000-N, ces représentants différant entre eux par la position des 0 et des 1. On comprendra que ces valeurs numériques sont données à titre illustratif uniquement et ne sauraient limiter la généralité du propos. Le dispositif vérificateur 1 qui recherche l'entité 4 d'identifiant N choisit 10 par exemple aléatoirement un représentant m; de l'identifiant N, c'est-à-dire un vecteur binaire ayant N bits à 1 et 20000-N bits à 0. Puis il transmet le représentant m; en tant que mot d'identification sur le canal de communication 2 à l'étape 10. L'entité 4 connaît son identifiant N, par exemple parce qu'elle le stocke 15 dans sa mémoire. A la réception d'un mot d'identification de longueur 20000 correspondant au représentant transmis m;, l'entité 4 calcule son poids, c'est-à-dire son nombre de 1 et le compare à N. Il s'agit là d'une fonction d'identification appliquée au mot d'identification reçu et à l'identifiant N de l'entité 4. 20 En cas d'égalité, l'entité 4 considère qu'elle est l'entité recherchée et envoie une réponse 11 au dispositif vérificateur 1 par l'intermédiaire du canal de communication 2. Cette réponse peut être interprétée comme telle par le dispositif vérificateur 1. Dans cet exemple, la réponse 11 ne contient pas d'autre information utile. 25 L'homme du métier comprendra que les exemples décrits en référence aux figures 2 à 4 ne sont pas limitatifs. Beaucoup d'autres possibilités peuvent être envisagées selon les principes généraux de l'invention décrits plus haut. En particulier, des fonctions de codage et/ou d'identification différentes de celles qui ont été décrites peuvent être utilisées. 30 On notera que tout ou partie des opérations décrites en référence aux différentes figures peuvent être mises en oeuvre en totalité ou en partie de façon logicielle, c'est-à-dire à l'aide d'un produit programme d'ordinateur 2949033 - 20 - comprenant des instructions de code adaptées à cet effet. En alternative ou en complément, certaines au moins de ces étapes peuvent être réalisées à l'aide d'un circuit électronique. REVENDICATIONS1. Procédé de recherche d'une entité appartenant à un ensemble d'entités à l'aide d'un dispositif vérificateur (1), le dispositif vérificateur et les entités dudit ensemble d'entités étant agencés pour échanger des informations par l'intermédiaire d'au moins un canal de communication (2), chaque entité dudit ensemble d'entités possédant un premier identifiant respectif à partir duquel une pluralité de représentants peuvent être obtenus, le procédé comprenant les étapes suivantes : - obtenir au dispositif vérificateur un premier mot d'identification (m;;p(x;)) relatif à une entité recherchée (4), le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée d'une première fonction de codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable (i) ; et - transmettre, depuis le dispositif vérificateur, le premier mot d'identification obtenu sur le canal de communication. 2. Procédé selon la revendication 1, comprenant en outre les étapes suivantes, mises en oeuvre par chaque entité (3-5) dudit ensemble d'entités à l'écoute du canal de communication (2) : - recevoir un mot d'identification correspondant au premier mot d'identification (m;;p(x;)) transmis sur le canal de communication ; et - appliquer une première fonction d'identification associée à la première fonction de codage au mot d'identification reçu et à une information connue par ladite entité parmi le premier identifiant de ladite entité et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, de façon à vérifier si ladite entité correspond à l'entité recherchée (4). 2949033 - 22 - 3. Procédé selon la revendication 2, dans lequel une indication de la valeur du paramètre variable (i) utilisée pour former le premier mot d'identification obtenu (m;) est transmise depuis le dispositif vérificateur (1) sur le canal de communication (2), et dans lequel pour chaque entité (3-5) dudit 5 ensemble d'entités à l'écoute du canal de communication, ladite application de la première fonction d'identification tient compte de l'indication de la valeur du paramètre variable reçue. 4. Procédé selon la revendication 2 ou 3, dans lequel, lorsque le résultat de ladite application de la première fonction d'identification révèle que 10 ladite entité (3-5) correspond à l'entité recherchée (4), ladite entité envoie une réponse (7;9;11) au dispositif vérificateur (1) par l'intermédiaire du canal de communication (2). 5. Procédé selon la revendication 4, dans lequel ladite entité (3-5) possède un deuxième identifiant à partir duquel une pluralité de représentants 15 peuvent être obtenus, dans lequel on obtient à ladite entité un deuxième mot d'identification (M;;p(X;)) par application d'une deuxième fonction de codage à une information connue par ladite entité parmi le deuxième identifiant de ladite entité et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit deuxième identifiant de façon à dépendre d'une sous- 20 partie de la pluralité de représentants pouvant être obtenus à partir dudit deuxième identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable (i), et dans lequel la réponse (7;9;11) envoyée par ladite entité au dispositif vérificateur (1) par l'intermédiaire du canal de communication (2) inclut le deuxième mot d'identification. 25 6. Procédé selon la revendication 5, dans lequel on reçoit au dispositif vérificateur (1) un mot d'identification correspondant au deuxième mot d'identification (M;;p(X;)) inclus dans ladite réponse (7;9;11), et dans lequel le dispositif vérificateur applique une deuxième fonction d'identification associée à la deuxième fonction de codage au mot d'identification reçu au dispositif vérificateur et à une information connue par le dispositif vérificateur parmi le deuxième identifiant de ladite entité (3-5) et au moins un représentant de la pluralité de représentants pouvant être obtenus à partir dudit deuxième 2949033 - 23 - identifiant, de façon à effectuer une vérification complémentaire d'une correspondance entre ladite entité et l'entité recherchée. 7. Procédé selon l'une quelconque des revendications 2 à 6, dans lequel la première fonction de codage est agencée pour que, lorsqu'elle est 5 appliquée au premier identifiant de l'entité recherchée (4), ledit paramètre variable (i) sélectionne au moins un représentant (m;) de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, et dans lequel ladite application de la première fonction d'identification comprend une comparaison entre ledit représentant sélectionné par ledit paramètre variable et 10 au moins un représentant de la pluralité de représentants pouvant être obtenus à partir du premier identifiant de ladite entité. 8. Procédé selon l'une quelconque des revendications précédentes, dans lequel la valeur du paramètre variable (i) utilisée pour former le premier mot d'identification (m;) obtenu est choisie de façon aléatoire ou quasi 15 aléatoire. 9. Procédé selon l'une quelconque des revendications précédentes, dans lequel le premier mot d'identification (m;) obtenu est transmis sur le canal de communication (2) depuis le dispositif vérificateur (1) de façon codée à l'aide d'un code correcteur d'erreurs. 20 10. Procédé selon l'une quelconque des revendications précédentes, dans lequel le canal de communication (2) est un canal sans-fil, tel qu'un canal radio, et dans lequel le dispositif vérificateur (1) comprend un lecteur d'identification sans fil et certaines au moins des entités de l'ensemble d'entités (3-5) comprennent des marqueurs d'identification sans fil. 25 11. Procédé selon l'une quelconque des revendications précédentes, dans lequel la faculté d'obtenir la pluralité de représentants pouvant être obtenus à partir d'un identifiant n'est donnée qu'à l'entité (3-5) dudit ensemble d'entités possédant ledit identifiant et au dispositif vérificateur (1). 12. Procédé selon l'une quelconque des revendications précédentes, 30 dans lequel la première fonction de codage est agencée pour qu'un même 2949033 - 24 - premier mot d'identification puisse être le résultat de l'application de la première fonction de codage à plusieurs identifiants distincts parmi l'ensemble de tous les identifiants possibles. 13. Dispositif vérificateur (1) agencé pour échanger des informations 5 avec un ensemble d'entités par l'intermédiaire d'au moins un canal de communication (2), chaque entité dudit ensemble d'entités possédant un premier identifiant respectif à partir duquel une pluralité de représentants peuvent être obtenus, le dispositif vérificateur comprenant : - une unité d'obtention d'un premier mot d'identification (m;;p(x;)) relatif à 10 une entité recherchée (4), le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée d'une première fonction de codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant déterminée par au moins un paramètre variable 15 (i) ; et - une unité de transmission sur le canal de communication du premier mot d'identification obtenu par ladite unité d'obtention. 14. Entité (3-5) appartenant à un ensemble d'entités capables d'échanger des informations avec un dispositif vérificateur (1) par 20 l'intermédiaire d'au moins un canal de communication (2) et possédant chacune un premier identifiant respectif à partir duquel une pluralité de représentants peuvent être obtenus, ladite entité comprenant : - une unité de réception d'un mot d'identification correspondant à un premier mot d'identification (m;;p(x;)) transmis sur le canal de 25 communication par le dispositif vérificateur, le premier mot d'identification étant formé par application au premier identifiant de l'entité recherchée (4) d'une première fonction de codage de façon à dépendre d'une sous-partie de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, ladite sous-partie étant 30 déterminée par au moins un paramètre variable (i) ; et 2949033 -25- - une unité d'application d'une première fonction d'identification associée à la première fonction de codage au mot d'identification reçu et au premier identifiant de ladite entité et à une information connue par ladite entité parmi le premier identifiant de ladite entité et au moins un 5 représentant de la pluralité de représentants pouvant être obtenus à partir dudit premier identifiant, de façon à vérifier si ladite entité correspond à l'entité recherchée. 15. Système de recherche d'une entité (4) appartenant à un ensemble d'entités à l'aide d'un dispositif vérificateur (1), le système comprenant des ~o moyens adaptés pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 12.