Brevet FR3043811A1 — publié le 20170519

Procédé d'identification d'une entité DOMAINE TECHNIQUE GENERAL La présente invention concerne le domaine de l'identification d'une entité, individu ou objet. Plus précisément, elle concerne un procédé d'identification biométrique dans lequel la comparaison à des données biométriques de référence est déléguée à un dispositif distant dans le cadre d'un protocole de calcul publiquement vérifiable. ETAT DE LA TECHNIQUE Du fait de la miniaturisation croissante des systèmes de calculs numériques, il existe dorénavant une large gamme de dispositifs numériques dotés d'une puissance de calcul variable, de la carte à puce au supercalculateur en passant par le smartphone et l'ordinateur personnel. Dans un tel cadre il peut être intéressant pour un dispositif doté d'une puissance de calcul limitée de déléguer des calculs couteux à un dispositif distant doté d'une puissance de calcul plus importante. Une telle délégation a particulièrement été rendue plus facile ces dernières années par le développement des réseaux de communication à haut débit et d'une offre de calculs déportés dans le cloud. Une telle délégation de calculs pose néanmoins le problème de la confiance pouvant être accordée aux résultats de calcul transmis par un exécutant distant. Des erreurs de calcul peuvent en effet se produire, aussi bien du fait de problèmes techniques indépendants de la volonté de l'exécutant, que du fait d'une action volontaire et malicieuse. Ainsi, d'importants efforts ont été réalisés afin de mettre au point un protocole de calcul, dit de calcul vérifiable, permettant à un exécutant distant de prouver au dispositif ayant commandé un calcul que celui-ci a été exécuté correctement. Pendant longtemps, les protocoles mis au point sont cependant restés applicable uniquement à des fonctions spécifiques, ou bien sont restés inexploitables en pratique du fait de l'importante quantité de calculs nécessaire au donneur d'ordre pour vérifier la preuve fournie par l'exécutant. Le protocole Pinocchio présenté dans la publication « Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova, Pinocchio: Nearly Practical Verifiable 3043811 2 Computation, in Proceedings of the IEEE Symposium on Security and Privacy, IEEE, 21 May 2013 » a été un des premiers protocoles de calcul vérifiable permettant à l'exécutant de calculer de manière vérifiable l'application d'une fonction quelconque et au donneur d'ordre de vérifier la preuve associée en un 5 temps de calcul inférieur à celui nécessaire pour réaliser le calcul lui-même, permettant ainsi au donneur d'ordre d'effectivement tirer avantage de la délégation du calcul malgré le surcout lié à la vérification de la preuve. Le protocole Pinocchio présente néanmoins l'inconvénient majeur de nécessiter une puissance de calcul importante du côté de l'exécutant. Le coût de 10 production de la preuve d'un calcul par ce protocole est en effet supérieur de plusieurs ordres de grandeur à celui du calcul lui-même. Le protocole Pinocchio repose sur une transcription de la fonction à évaluer sous la forme d'un circuit arithmétique et la construction du programme arithmétique quadratique (QAP, « Quadratic Arithmetic Program ») correspondant. 15 Le coût de calcul augmente alors avec le nombre de multiplieurs dans ce circuit arithmétique. Un tel nombre peut rapidement devenir important, par exemple dans le cas où la fonction comprend une boucle dont chaque itération doit être représentée explicitement par ses propres opérateurs dans le circuit. Ceci limite l'emploi pratique d'un tel protocole à l'évaluation de fonctions très simples. 20 Ce protocole a ensuite été amélioré au travers du protocole Geppetto, présenté dans la publication « Craig Costello, Cedric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur, Geppetto: Versatile Verifiable Computation, in Proceedings of the IEEE Symposium on Security and Privacy, IEEE, 18 May 2015 ». Ce nouveau protocole 25 de calcul vérifiable propose de découper la fonction à évaluer en plusieurs sous- fonctions, éventuellement utilisées plusieurs fois pour l'évaluation de la fonction globale, par exemple à chaque itération d'une boucle. La preuve de l'évaluation de cette fonction peut ensuite être construite à partir des preuves moins couteuses relatives à l'évaluation de telles sous-fonctions. Le circuit arithmétique total peut 30 alors être grandement simplifié par rapport à celui du protocole Pinocchio, limitant grandement le nombre de multiplieurs à employer. Le coût total de production de la preuve pour l'exécutant est alors réduit par rapport à celui du protocole Pinocchio. Le coût de calcul d'une preuve dans le cadre du protocole Geppetto reste cependant croissant avec le nombre de multiplieurs nécessaires à la 35 représentation de la fonction à évaluer sous forme de circuit arithmétique. Une 3043811 3 technique d'amorçage (« bootstrapping ») a été introduite pour améliorer la situation ; toutefois la mise en oeuvre de ce procédé dégrade les performances. Dans le cadre d'une identification biométrique il est nécessaire de comparer une empreinte biométrique à une multitude d'empreintes biométriques de 5 référence, en un temps suffisamment court pour être supporté par l'individu à identifier. Une telle comparaison entre deux empreintes biométriques représentées chacune sous forme d'un vecteur u, respectivement u', de N entiers binaires u, ou u'' peut être mise en oeuvre en calculant le produit scalaire u.u' entre ces deux vecteurs. Le circuit arithmétique correspondant à un tel produit scalaire est 10 représenté en figure 1. Il comprend alors au moins N multiplieurs prenant chacun en entrée un entier u, et l'entier u', correspondant. Un tel nombre de multiplieurs implique une quantité de calcul par les protocoles décrits ci-dessus trop importante pour être réalisée en temps réel, rendant ainsi de tels protocoles inadaptés à une utilisation dans le cadre d'un procédé d'identification biométrique. 15 Il existe donc un besoin d'un procédé d'identification biométrique permettant de déléguer à une entité distante la comparaison d'empreintes biométriques dans le cadre d'un protocole de calcul vérifiable, pour un coût de calcul, production et vérification de preuve comprises, permettant une exécution en 20 temps réel. PRESENTATION DE L'INVENTION La présente invention propose selon un premier aspect un procédé d'identification 25 biométrique d'une entité, par un système d'identification biométrique comprenant un dispositif client et un dispositif de calcul distant, comprenant : - un calcul d'au moins une valeur de correspondance entre au moins une donnée biométrique de l'entité u et au moins une donnée biométrique de référence u', par application d'une fonction F auxdites données 30 biométriques, chacune desdites données étant un vecteur de N entiers binaires u, ou u', avec 1 i N, chaque entier étant codé sur n bits, ladite fonction comprenant un produit scalaire entre une donnée biométrique de l'entité et une donnée biométrique de référence, ledit calcul mettant en oeuvre un procédé non-interactif de calcul publiquement vérifiable 35 comprenant des étapes de : 3043811 4 - représentation de ladite fonction sous forme d'un circuit arithmétique comprenant des fils transportant des valeurs du corps premier fini Zc n avec q un nombre premier, et reliant des opérateurs d'addition et de multiplication, 5 - conversion dudit circuit arithmétique en une représentation polynomiale, QAP (« Quadratic Arithmetic Program ») ou multiQAP, - génération d'une clé publique d'évaluation et d'une clé publique de vérification en fonction de ladite représentation polynomiale, 10 - obtention par le dispositif de calcul distant du circuit arithmétique et de la clé publique d'évaluation, - pour chaque donnée biométrique de l'entité, détermination d'au moins une valeur de correspondance entre ladite donnée biométrique et au moins une donnée biométrique de référence 15 par le dispositif de calcul distant en évaluant le circuit arithmétique ayant pour entrées la donnée biométrique de l'entité et la donnée biométrique de référence, - pour chaque valeur de correspondance déterminée, génération par le dispositif de calcul distant d'une preuve de la correction de 20 l'exécution du calcul de la valeur de correspondance, dite preuve générée, à partir de ladite représentation polynomiale, de la clé publique d'évaluation et du résultat de l'évaluation du circuit arithmétique, - transmission par le dispositif de calcul distant desdites valeurs de 25 correspondance et desdites preuves générées au dispositif client, - vérification desdites preuves reçues par le dispositif client à l'aide de la clé de vérification publique, - une identification de l'entité par le dispositif client en fonction des valeurs 30 de correspondance et du résultat de ladite vérification de preuves, caractérisé en ce que : - la représentation de ladite fonction comprend l'encodage d'un nombre entier k>1 d'entiers binaires d'un vecteur d'une donnée biométrique sur au moins un fil d'entrée du circuit, 3043811 5 - et la fonction F comprenant au moins m produits scalaires, m étant un diviseur de la longueur N des vecteurs de données biométriques, ^ si le diviseur m est égal à 2 ou 3, le circuit comprend au moins N/km opérateurs de multiplication reliés 5 aux fils d'entrée du circuit, une mémoire de stockage, et au moins un opérateur d'addition, et l'évaluation du circuit comprend itérativement un calcul de chacun des m produits scalaires à l'aide desdits N/km opérateurs de multiplication, un stockage des m résultats des calculs desdits produits 10 scalaires dans ladite mémoire de stockage et une sommation desdits résultats à l'aide dudit opérateur d'addition, ^ si le diviseur m est supérieur ou égal à 4, le circuit comprend au moins un premier sous-circuit de calcul de produit scalaire comprenant N/km premiers opérateurs de multiplication 15 reliés aux fils d'entrée du circuit et une première mémoire de stockage, et un second sous-circuit de calcul de produit scalaire comprenant N/km seconds opérateurs de multiplication reliés aux fils d'entrée du circuit et une seconde mémoire de stockage, chacun desdits sous-circuit étant également relié à une sortie de la mémoire de stockage de l'autre sous- 20 circuit, et l'évaluation du circuit comprend itérativement un calcul de chacun des m produits scalaires en utilisant alternativement le premier ou le second sous-circuit pour calculer la somme du produit scalaire des valeurs des fils d'entrée de ce sous-circuit et de la valeur stockée dans 25 la mémoire de stockage de l'autre sous-circuit. Ceci permet au dispositif client de déléguer le calcul des produits scalaires nécessaires à l'identification biométrique de l'entité, tout en lui permettant de vérifier l'exactitude des calculs réalisés par le dispositif distant, le tout pour un coût modéré du fait de la complexité réduite des circuits utilisés pour représenter la 30 fonction de produit scalaire. De tels circuits comprennent en effet environ de l'ordre de k*m moins de multiplieurs que le circuit selon l'état de l'art. L'étape de vérification desdites preuves reçues peut comprendre une vérification de couplages par lot. 35 3043811 6 Dans un premier mode de mise en oeuvre, si le diviseur m de la longueur N des vecteurs de données biométriques est égal à 1, étant donné un environnement bilinéaire asymétrique (q, G1, G2, GT, g1, 92, e) où q est un nombre premier G1, G2 et GT trois groupes d'ordre q, g1 un générateur de G1, 92 un générateur de G2, et e un 5 couplage bilinéaire non-dégénéré e: G1 x G2 GT et le circuit arithmétique étant représenté sous la forme d'un QAP du circuit Q = (t, V, W, Y) de taille p et de degré 6, avec V={vi}, W={wi}, Y={yi}, 0 i p, et étant donnés Iio = {1, ..., 0} l'ensemble des indices correspondants aux fils d'entrée/sortie du circuit et Imid = tO + 1, ..., pl l'ensemble des indices des fils 10 intermédiaires du circuit n'étant pas des fils d'entrée du circuit, - l'étape de génération d'une clé publique d'évaluation et d'une clé publique de vérification comprend : - la génération d'aléas r'rw, s, av, aw,ay, fi, y dans Zci, - la définition des coefficients ry = r, - rw, gvi = girv, gwi = 91rw, 9w2 = 92rw, 15 93/1 = 91rY et 9y2 = 92rY, - la génération de la clé publique d'évaluation EKF égale à (EKF1, EKF2) où 19v1vi(s).1 jawiwi(s).1 iyi(s)-1 ia f a,.,, aw.wi(s)1 f ayyi(s)1 mid iermid J/Eimid EKF, = I9viav-vi(s)1 tgylig-i(s) - gwlig.wi(s) - gylig-yi(s)) lElmid EKF2 = (tgw2wi(s)}iElmid) - la génération de la clé publique de vérification VKF égale à (VKF1, VKF2) où : VKF1 = tgv1vi(s)lie[1,6], (93,131i(s)lie[1,6]) VKF2 = (92, 92av, 92aw, 92aY, 92Y 2e 'Y 2t(s) w2w i(s)) ie [le) -la génération par le dispositif de calcul distant d'une preuve de la correction de 20 l'exécution du calcul d'une valeur de correspondance comprend, {cilie[1,19] étant l'ensemble des valeurs du circuit déterminées lors de l'étape de détermination de la valeur de correspondance: - la détermination d'un polynôme h(x) tel que p(x) = h(x) - t(x) avec p(x) = (v 0(x) + ci - vi (x)) - (wo (x) + ci - wi (x)) - 670(x) + 25 Eei_i ci - Yi (x)), - le calcul de la preuve générée n- = (n-1, n-2) avec : 3043811 7 gvivrnid(s), gwiwrnid(s), g yiymid(s) h(S), Tel = g viav.vrnid(s) gwiaw.wrnid(s), g ylayynuci(s ) 1 Tel = (gw2wm'cl(s)) gvifl'vinid(s) . gwifl'winid(s) . gyli3 Ymid(s) où : vrnid(x) = ci - vi(X), wmid (X) = ci wi(x) et Yinici(x) = Eielmid ci Y i(X), 5 -et, dans lequel lesdites preuves reçues par le dispositif client étant égales à (TTo, TTr2) avec TTrl sous la forme : (gV1Vnlid, gW1Wnlid, gylYmid 91H gwlWmid gylY 91z) et ur2 sous la forme gw2wmid, la vérification d'une preuve reçue comprend la mise en oeuvre des tests d'égalité suivants : 10 - e(9viv0(s) - 9v1 vi°(s) - gvivmid, 9vv2 (s) - 9w2 wi° (s) - gw2 Wnlid) = e(e gy2t(s)) . e(gyiyo(s) . gyiyio(s) . gyjnlid, g2 - e ((gylvi mid)di ' (9w1w 'nid)d2 - (g ylY 'nid)d3 92) = (e vil/midr1 g 2dv) e((9w1wmid)c12, 92aw) - e ((gytYmid)d3 92aY), - e(91z 92Y) = e(9v1vInid - 9w1wmid - 93nYmid, 92.Y) 15 où 9v1vi°(s) = fIe i(gvivi(s))', 9wzwi°(s) [lB 1(9w2w'(s)r et gyiYio(s) = irlfgyji(s)ret (d1, d2, d3) des éléments de Zq sur .1 bits avec .1 un paramètre de sécurité. La vérification de la preuve d'un calcul est ainsi accélérée par rapport au protocole Pinocchio, grâce à la vérification simultanée de plusieurs couplages. 20 Dans un deuxième mode de mise en oeuvre, si le diviseur m de la longueur N des vecteurs de données biométriques est supérieur ou égal à 2, étant donné un environnement bilinéaire asymétrique (q, G1, G2, GT, g1, 92,0 où q est un nombre premier G1, G2 et GT trois groupes d'ordre q, gi un générateur de G1, 92 un 25 générateur de G2, et e un couplage bilinéaire non-dégénéré e: G1 x G2 GT, le circuit arithmétique étant représenté sous la forme d'un multi-QAP Q = (tBblbE[1,e],t,17 ,Y) de taille p et de degré 8, avec fR b ,bE [1,e] un ensemble de ,t's banques Bb de Q utilisées dans le calcul de la fonction F, et V={vi}, W={wi}, Y={yi} avec 0 i p , 30 - l'étape de génération d'une clé publique d'évaluation et d'une clé publique de vérification comprend : 3043811 8 - une génération d'aléas s,t(abv,abw,aby, yb)lbe[v], r', rwdans Zc - une définition des coefficients suivants : ry = r, - rw, gvi = 91rv, 9v2 = 92n,, 9w1 = g1rw 9w2 = g2 rw 9y1 = 91rY et gy2 = 921-Y, - une génération de la clé publique d'évaluation EKF égale à : (tEKFblbe [1, e],{915.1} ie [1,8] , gv1t(s), gw1t(s), gy1t(s), gv2t(s), gw2 t(s), gy2 t (s)) 5 où chaque clef publique de banque EKFb est égale à (EKFb1, EKFb2) avec : / gvivi(s),gwiwi(s)giYi(S), gVlabV.Vi(S), gWlabW.Wi(S), gyl abY.Yi (S.) \ EKFb1 = Clll flb.Vi(S) ry CW1 flb.141i(S) ry cy1 flb.31i(S) iEB b \ g via blit (S) g wia bWt(S) g yia byt(S) g vi_fl b't (S) g wifl b't (S) g ylig b't (S) EKFb2 = (Igw2wi(s)}ieBb,9w2abw.t(s)) - une génération de la clé publique de vérification VKF égale à : (t171(FblbE[1,e], 91, 92, 9y2 t(s)) où chaque clef publique de banque VKFb est égale à (g2 abv, g2abw, g2aby, g2 Yb, g2bilb), -la détermination d'une valeur de correspondance comprend, la fonction F étant 10 découpée en co sous-fonctions F1, , F, et a = ((f1, (Ta-- T1e))) étant un le [1,L] ordonnancement de longueur L avec fi e [1, , col, l'évaluation de chaque sous fonction FÛ, à partir des données biométriques de l'entité et de référence et la détermination des valeurs i du circuit, -la génération par le dispositif de calcul distant d'une preuve de la correction de 15 l'exécution du calcul d'une valeur de correspondance comprend, pour chaque 1 = {1, ..., : - pour chaque banque Bb telle que b E A, avec A s [1, -e] l'ensemble des indices b E [1, -e] tels que Tib # 0, F = UbEABb, (C,'} IEBbune instance de la banque Bb, A = fcilier l'ensemble des valeurs de F : 20 o une génération d'aléas de mises en gage dans Zq : ob = (obv, obw, oby), o un calcul d'un digest Db égal à (Dbl,Db2) à partir de l'instance de la banque de variables Bb Bb(Tib) = {Ci E A}ieBb et des aléas de mise en gage ob et tel que : - si la banque Bb est une banque d'entrée/sortie : 25 Dbl = (9v1v(b)(s), gytY(b)(s)) et Db2 = (9w2w(b)(s)), si la banque Bb n'est pas une banque d'entrée/sortie : Dbl = 3043811 9 9v1 9w1 gw1w(b"s), g yly(b"s), gvlabv.v(b"s) , gwlabw.w(b"s), g ylabY.Y(b"s) cnvi lgb'v(b)(s) ' c nwt )gb.w(b)(5) . 93,1 Ply(b)(s) Db2 = (9w2141(b)(S)) avec : v(b)(s) = EiEBb c1 - vi (s) + oh, - t(s), w(b)/(s) = EiEBb c1 - w1 (s) + obw - t(s), y(b)s) = EiEBb Ci . Y i(s) + 0 by ' t(s), 5 - une détermination d'un polynôme h(0(x) tel que p(1)(x) = h(1)(x) - t(x) avec P(1)(x) = (vo(x) + EiEF Ci . V j(X) + EbEA °bv . t(x)) ' (WO(X) + EiEr ci . w1 (x) + EbEA obw - t(x)) - (Yo (x) + Eier ci - Yi (x) + EbEA oby - t(x)) - un calcul d'un élément de preuve Tr(1) égal à glh(1)(s) -et, dans lequel lesdites preuves reçues par le dispositif client étant de la forme 10 D1(1), ..., De(1) , n- (1) , ... , D i(L) , ... , De(L) , KM où pour tout 1 E {1, ..., L} et b e fl, ..., -PI : vb(0 wb (0 yb(0 v'(1) wbi(i) yb' (i) z (0 ( w (0)) et Db(1) (( - gvi ,gwi , gyi , gvi ,gwi , gyi ,gib ' g w2b 7141) = gH (l), la vérification d'une preuve reçue (E8) comprend : - une vérification des L - -e digests, pour l e {1, ..., L} et b E 15 {1, ..., -e} comprenant la mise en oeuvre des tests d'égalité suivants : o ,(0 e vvi , g2 Cebv) = e (gyv f(1) , 92) o (0 e (g wi , 92abw) = e (g ww , 92) o e(, (1) gyYbi , g2 abY) = e (gyY_ (1), 92) e (gizb(1) 92n) = e(gyv(1) gwvvib:(1) gyl,(1) o g2Pb'Yb) 20 - une vérification des L preuves comprenant pour l E {1, ..., L} la mise en oeuvre du test d'égalité suivant : e e e e n(9,,,,:(/)),1-1(9z2b (0) e (0 (0 , gy2t(s)) . e n(9,,,,(/)),92 (b=1 b =1 b =1 La vérification de la preuve d'un calcul est ainsi accélérée par rapport au protocole Geppetto, grâce à la vérification simultanée de plusieurs couplages. 25 Dans un troisième mode de mise en oeuvre, si le diviseur m de la longueur N des vecteurs de données biométriques est supérieur ou égal à 2, étant donné un environnement bilinéaire asymétrique (q, G1, G2, GT, g1, 92, e) où q est un nombre 3043811 10 premier G1, G2 et GT trois groupes d'ordre q, 91 un générateur de G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e: G1 x G2 GT, le circuit arithmétique étant représenté sous la forme d'un multi-QAP Q = (tBblbE[1,e],t,17 ,W,Y) de taille p et de degré 8, avec fR b,bE[1,e] un ensemble de e 5 banques Bb de Q utilisées dans le calcul de la fonction F, et V={vi}, W={wi}, Y={yi} avec 0 i p , - l'étape de génération d'une clé publique d'évaluation et d'une clé publique de vérification comprend : - une génération d'aléas s,a (Gbv, - a bw, aby, Pb, Yb)) be[v],rv, rwdans Zq, 10 - une définition des coefficients suivants : ry = rv ' rw, 9v1 = 91rv, 9v2 = 92rv, 9w1 = 91rw, 9w2 = 92rw, 934 = 91rY et 9y2 = 92rY, - une génération de la clé publique d'évaluation EKF égale à : (tEKFb IbE [1t(s) t(s) t(s) t(s) t(s) t(s)) » 191sl ie [1,8] 9v1 9w1 9y1 9v2 9w2 9y2 où chaque clef publique de banque EKFb est égale à (EKFb1, EKFb2) avec : 7 gvivi(s), gwi wi(s), gyi yi(s), gviabv.vi(s), gwiabw.wi(s), gyiaby.yi(s) \ { 9v1flb.vi(s) ' 9w1flb.wi(s) ' 9y1flb.Yi(s) tEBb \ 9v1abv.t(s), gwiabw.t(s), gyiabyt(s), gviflb-t(s), gwiflb.t(s), gyiflb.t(s) EKFb2 = (t9w2w`(s))tEBb, 9w2abw.t(s)) - une génération de la clé publique de vérification VKF égale à : 15 (t171(FbIbe[1,m, 91, 92, 9y2t(s)\ ) où chaque clef publique de banque VKFb est égale à (g2 abv, g2abw, g2aby, 92 Yb, g2flbilb), -la détermination d'une valeur de correspondance comprend, la fonction F étant découpée en co sous-fonctions F1, ..., Fa, et a = ((f1, (T11, ... , T1e))) étant un 1E [1,L] ordonnancement de longueur L avec fi E {1, ..., co}, une évaluation de chaque sous 20 fonction Fa, à partir des données biométriques de l'entité et de référence et une détermination des valeurs du circuit, -la génération par le dispositif de calcul distant d'une preuve de la correction de l'exécution du calcul d'une valeur de correspondance comprend, pour chaque 1= {1, ...,L}: 25 - pour chaque banque Bb telle que b E A, avec A s [1,-e] l'ensemble des indices b E [1, -e] tels que Tib # 0, F = UbEA Bb, (CA. une instance de la JEBb banque Bb, A = fcilier l'ensemble des valeurs de F : EKFb1 = 3043811 11 o une génération d'aléas de mises en gage dans Zq : ob = (obv, obw, oby), o un calcul d'un digest Db égal à (Dbl,Db2) à partir de l'instance de la banque de variables Bb Bb(Tib) = {Ci E A}ieBb et des aléas de mise en gage ob et tel que : 5 si la banque Bb est une banque d'entrée/sortie : Db1 = (9v1v(b)(s), _y1 g Y(b)(s)) et Db2 = (gw2w(b)(s)), si la banque Bb n'est pas une banque d'entrée/sortie : Db1 = (9v1v(b)(S), 9w1 9y1 g yle)(S) , gv1abv.v(b)(S) , 9W1abw.141(b)(S) gylabY.Y(b)(S) nv1 . c PI'v(b)(s) nw1 9y1 Pl'w(b)(s) . PlY(b)(s) c Db2 = (9w2w(b)(s)) avec : v(b)(s) = EiEBb ci - vi (s) + ob, - t(s), 10 w(b)/(s) = EiEBb ci - wi (s) + obw - t(s), y(b)s) = EiEBb ci - Yi (s) oby - t(s), - une détermination d'un polynôme h(0(x) tel que p(1)(x) = h(1)(x) - t(x) avec _ (' + v (,''^ + v tr,'\ (', (,'^ + v - y-'0^A,) z1EF (-1 vj^,,t) Z,bEAubv U'v 0 z,iEr ei - wi(x) EbEA obw - t(x)) - (y0(x) + EiEr ci - YI (x) + EbEA oby - t(x)) 15 - un calcul d'un élément de preuve Tr(1) égal à g1h(1)(s) -et, dans lequel lesdites preuves reçues par le dispositif client étant de la forme D1(1), ..., D»), n-(1), ..., D1(L), ..., Re(L), n-(L) où pour tout / E {1, ...,L} et b E fl, ..., -el : ( ' \(1)=/vi(0wi (0 yi (0 vi(t) wi (i) yi (i) z (0» 0/ w (0 Db Vv , gw , gy , gv , gw , gy , gi 42 1 ) et 20 n-(0 = 0(1), la vérification d'une preuve reçue comprend, étant donné un paramètre de correction À : - une sélection d'un vecteur aléatoire (d1, ...,d3.e) d'éléments de taille À, - une vérification par lot des L - -e digests comprenant la mise en oeuvre -e fois des tests d'égalité suivants, pour b E {1, ..., -e} : d,,+1 , (o)d1 / =1 , mn L ( w' (I)) 25 o e (1-1Ki(giv/bil , g2abv) - e (1-1 a , 92 abw . e Hf =1(9 yYbii(1))d2 L+1 ( , g2abY) dL+1 = e ( =i(gvi?))di i, v(0) rif 111=1 cw1 11=1(g ; ib(1))d2 L+I , 92) 3043811 12 O v (0 w (0 (0)d1 R e ) ,g2n) = e (Ilf= 1 (g vi - - 93,i , 921- bit b) z (01d1 - une vérification par lot des L preuves comprenant la mise en oeuvre du test d'égalité suivant : e (gvvr) ,1 ,g'',w2,,' bs-')) 1=1 b=1 L (e di , b=1 L = e (HW (1 ))di , g y2t(s)) - e (/) di /=, 1=1 b=1 Ceci permet de rendre la vérification d'une preuve encore plus rapide grâce à la 5 vérification par lot des digests de la preuve. L'identification de l'entité peut comprendre une comparaison des valeurs de correspondance à un seuil prédéterminé. La fonction F peut comprendre une comparaison du résultat du produit scalaire 10 entre lesdites données biométriques de l'entité et de référence à un seuil prédéterminé. Une telle comparaison à un seuil permet de décider si les données biométriques comparées sont suffisamment proches pour conclure à une identification réussie de l'entité à identifier. 15 L'encodage de k entiers binaires ui ou u'i sur un fil d'entrée d'un jème opérateur de f(z-1)N . (z-1)N , -F(J 1)k-E1) 1)k-E1)(11,) multiplication, j N/k , est égal à m (.1) ou m 1-" avec 1 z m, et est donné par la formule : Ek((j-1)k+1)(x) = Le" .À- 0-1)k+i = 2e1 x(j-1)k-E1 --- 2ek- x(j-i)k+k i=1 avec El, ...,Ek des entiers prédéterminés. 20 Plusieurs entiers des données biométriques peuvent ainsi être encodés sur chaque fil d'entrée, réduisant le nombre de multiplieurs nécessaires au calcul du produit scalaire entre une donnée biométrique de l'entité et une donnée biométrique de référence. 25 Selon un deuxième aspect, l'invention concerne un produit programme d'ordinateur comprenant des instructions de code pour l'exécution d'un procédé selon le premier aspect lorsque ce programme est exécuté par un processeur. 3043811 13 Selon un troisième aspect, l'invention concerne un système d'identification biométrique comprenant un dispositif client et un dispositif de calcul distant caractérisé en ce que ledit dispositif client et ledit dispositif de calcul distant comprennent chacun un processeur, une interface et une mémoire pour mettre en 5 oeuvre les étapes du procédé d'identification selon le premier aspect. De tels produit programme d'ordinateur et système présentent les mêmes avantages que ceux évoqués pour le procédé selon le premier aspect. 10 PRESENTATION DES FIGURES D'autres caractéristiques et avantages de la présente invention apparaîtront à la lecture de la description qui va suivre d'un mode de réalisation préférentiel. Cette description sera donnée en référence aux dessins annexés dans lesquels : 15 - la figure 1 illustre un circuit arithmétique correspondant à une implémentation naïve d'un produit scalaire pour l'identification biométrique d'une entité ; - la figure 2 représente un système d'identification selon un mode de réalisation de l'invention ; 20 - la figure 3 est un diagramme schématisant une mise en oeuvre d'un procédé d'identification selon l'invention ; - les figures 4a et 4b illustrent un circuit arithmétique pour l'identification biométrique d'une entité selon un premier mode de mise en oeuvre de l'invention; 25 - les figures 5a et 5b illustrent un exemple de mise en oeuvre du circuit des figures 4 pour N = 3000, n = 8, q = 256, k = 3 ; - les figures 6a à 6c illustrent un circuit arithmétique pour l'identification biométrique d'une entité selon un deuxième mode de mise en oeuvre de l'invention; 3043811 14 - les figures 7a et 7b illustrent un circuit arithmétique pour l'identification biométrique d'une entité selon un troisième mode de mise en oeuvre de l'invention; 5 DESCRIPTION DETAILLEE La présente invention concerne une mise en oeuvre d'un procédé d'identification biométrique d'une entité 1 par un système d'identification 2 comprenant un dispositif client 3 et un dispositif de calcul distant 4 susceptibles 10 d'être reliés entre eux par un réseau de communication 5, comme représenté en figure 2. Une telle entité peut être un individu ou bien un objet possédant des données biométriques tel qu'un passeport biométrique. Le dispositif client et le dispositif de calcul distant peuvent chacun comprendre une mémoire vive et des moyens de stockage internes tels qu'une 15 mémoire non volatile réinscriptible (mémoire flash ou mémoire EEPROM) et des moyens de traitement comportant un processeur. Ils peuvent également comprendre une interface leur permettant de dialoguer entre eux, de type filaire tel qu'une liaison Ethernet, ou sans-fil tel qu'une connexion Wfi ou Bluetooth. Le procédé mis en oeuvre a alors pour but de permettre au dispositif de 20 déléguer au dispositif de calcul distant les calculs nécessaires à l'identification biométrique de l'entité à identifier, de façon à ce que les calculs réalisés par le dispositif de calcul distant soient publiquement vérifiables, le tout en une durée suffisamment courte pour être acceptable dans le cadre d'un procédé d'identification. 25 Pour réaliser une telle identification biométrique, le dispositif client acquiert au moins une donnée biométrique de l'entité à identifier u. Afin d'identifier l'entité, cette au moins une donnée biométrique u doit être comparée à une ou plusieurs données biométriques de référence u', mémorisées préalablement. A titre d'exemple, de telles données biométriques peuvent être des 30 empreintes digitales, ADN, vocales ou bien encore des images d'iris ou de réseaux veineux. Chacune de ces données biométriques est un vecteur de N entiers binaires u, ou u', avec i N. Chaque entier u, ou u', est codé sur n bits. Par exemple dans le cas d'une donnée biométrique de visage, on peut typiquement avoir N = 3000 et n = 8. 3043811 15 Le dispositif client peut comprendre ou être relié à un dispositif de capture de telles données biométriques, tel qu'un lecteur d'empreinte digitale, un microphone, ou un dispositif d'imagerie d'iris. Ce dispositif de capture peut être employé pour acquérir la donnée biométrique u acquise pour l'entité 1. Les 5 données biométriques de référence u' peuvent être stockées dans les moyens de stockage du dispositif client ou du dispositif de calcul distant. Le procédé d'identification peut comprendre les étapes décrites ci-dessous en référence à la figure 3. 10 Tout d'abord au moins une valeur de correspondance peut être calculée F1 entre au moins une donnée biométrique de l'entité u et au moins une donnée biométrique de référence u', par application d'une fonction F auxdites données biométriques. La fonction F comprend un produit scalaire entre une donnée biométriques de l'entité et une donnée biométrique de référence. Un tel produit 15 scalaire permet en effet de calculer un score S = E,v_1(u, - lir]) d'autant plus élevé que les données comparées sont semblables. Un tel score peut alors être utilisé comme valeur de correspondance. Afin de déterminer si une tentative d'identification a réussi, les valeurs de correspondance peuvent être comparées à un seuil prédéterminé T. Alternativement, la fonction F peut comprendre la 20 comparaison du résultat du produit scalaire entre les données biométriques de l'entité u et de référence u', ie du score S, à ce seuil prédéterminé T. Le calcul de la valeur de correspondance peut alors comprendre le calcul de la valeur (S - T) et la valeur de correspondance issue d'un tel calcul peut être un bit de signe prenant par exemple la valeur 1 si S-T >0, la valeur 0 sinon. 25 Afin de garantir la qualité du résultat obtenu, le calcul d'une telle valeur de correspondance F1 met en oeuvre un procédé non-interactif de calcul publiquement vérifiable. Un tel procédé se découpe généralement en trois phases : - une représentation de la fonction F à évaluer sous forme de 30 système de contraintes représenté sous la forme d'un circuit arithmétique. - une transformation de ce circuit arithmétique en représentation polynomiale appelée « Quadratic Arithmetic Programs » (abrégé en QAP dans la suite). 3043811 16 - une génération d'une preuve de la correction de l'exécution du calcul à partir du QAP. Le procédé non-interactif de calcul publiquement vérifiable mis en oeuvre 5 comprend plus précisément tout d'abord une étape de représentation El de ladite fonction F sous forme d'un circuit arithmétique. Un tel circuit arithmétique comprend des fils transportant des valeurs du corps premier fini Zq, avec q un nombre premier, et reliant des opérateurs d'addition et de multiplication. Typiquement la taille q des valeurs des fils du circuit peut être égale à 256 bits. 10 Le circuit arithmétique est ensuite converti E2 en une représentation polynomiale, QAP (« Quadratic Arithmetic Program ») ou multi-QAP. De telles représentations et la façon de les obtenir à partir d'un circuit arithmétique sont décrites plus en détail dans les publications référencées ci-dessus concernant les protocoles Pinocchio et Geppetto existants. 15 Puis une clé publique d'évaluation et une clé publique de vérification sont générées E3 en fonction de ladite représentation polynomiale. Le dispositif de calcul distant obtient E4 ensuite le circuit arithmétique, et la clé publique d'évaluation. Les étapes de représentation sous forme de circuit arithmétique E1, de 20 conversion en une représentation polynomiale E2 et de génération des clés E3 peuvent être mises en oeuvre par le dispositif client lui-même. Alternativement ces étapes peuvent être déléguées à un tiers de confiance. De telles étapes étant indépendantes de la valeur des données biométriques à comparer, elles peuvent être mises en oeuvre une unique fois, préalablement aux comparaisons de 25 données biométriques décrites ci-dessous, et n'ont pas besoin d'être répétées tant que le format des données biométriques à comparer ne change pas. Pour chaque donnée biométrique de l'entité, au moins une valeur de correspondance entre ladite donnée biométrique et au moins une donnée biométrique de référence est ensuite déterminée E5 par le dispositif de calcul 30 distant en évaluant le circuit arithmétique avec pour entrées la donnée biométriques de l'entité et la donnée biométrique de référence. Pour chaque valeur de correspondance déterminée, le dispositif de calcul distant génère E6 une preuve de la correction de l'exécution du calcul de la valeur de correspondance, dite preuve générée, à partir de ladite représentation 35 polynomiale, de la clé publique d'évaluation et du résultat de l'évaluation du circuit 3043811 17 arithmétique. Il transmet E7 ensuite les valeurs de correspondance et lesdites preuves générées au dispositif client. Ce dernier vérifie E8 alors les preuves reçues à l'aide de la clé de vérification publique. L'étape de vérification desdites preuves reçues E8 peut 5 comprendre ou non une vérification de couplages par lot. Enfin l'entité est identifiée F2 par le dispositif client en fonction des valeurs de correspondance et du résultat de ladite vérification de preuves. 10 Les entiers u, et u,' constituant les données de l'entité et les données de référence sont usuellement encodés sur un nombre de bits n bien inférieur à la taille q des valeurs des fils du circuit. A titre d'exemple le nombre de bits n peut être égal à 8 bits et la taille q peut être égale à 256 bits. Afin de limiter le nombre de multiplieurs nécessaires à la représentation de la fonction F sous forme d'un 15 circuit arithmétique, plusieurs entiers u' respectivement u,' sont encodés sur chaque fil d'entrée du circuit arithmétique. La représentation de ladite fonction El comprend alors l'encodage d'un nombre entier k>1 d'entiers binaires d'un vecteur d'une donnée biométrique sur au moins un fil d'entrée du circuit. En pratique, l'encodage Ek(U-1)k+1)(u) ou Ek(U-1)k+1)(ut) de k entiers binaires u, ou u', sur un 20 fil d'entrée d'un jème opérateur de multiplication, j N/k, peut être défini par la formule : Ek(U-1)k+1)(x) 2 E- - x(j-ijk+i = 2E1 -- x(j-ijk+1 + - -- 2ek - x(j-i)k+k i=1 avec El, ...,Ek des entiers prédéterminés. -1)k+i)(u) et Ek((i-i)k+i)711,. Un multiplieur ayant en entrée Ek((i ) présente 25 alors sur son fil de sortie le produit des encodages des k entiers binaires u, ou u', successifs codés sur ses fils d'entrée. Ce produit est noté Eu.uf,k(- i)k+ = Ek((j-1)k+1) (u) Ek((j -1)k+1) fur \ ). A titre d'exemple, pour j = 1, on a : = 22'c1 - u1 - uri_ + 2E2 - (u1 - 1112 + u2 - 11'1) + 22-E2 - u2 - 1112 + --- + 22-Ek - Uk - Uri, Pour réduire davantage le nombre de multiplieurs du circuit arithmétique, le 30 procédé mis en oeuvre propose également de séparer le calcul du produit scalaire 3043811 18 de la donnée biométrique de l'entité u et de la donnée biométrique de référence u' de longueurs N en plusieurs calculs de produits scalaires de vecteurs de taille inférieure issus d'un fractionnement des vecteurs u et u'. La combinaison des résultats de ces produits scalaires permet alors d'obtenir le score S correspondant 5 au résultat du produit scalaire de u et u'. Pour cela, la fonction F comprenant au moins m produits scalaires, la fonction F peut être décomposée en au moins m occurrences de sous-fonctions, m étant un diviseur m de la longueur N des vecteurs de données biométriques. Seules les sous-fonctions distinctes sont alors représentées par leur propre sous- 10 circuit dans le circuit arithmétique, diminuant ainsi le nombre de multiplieurs du circuit. Afin de combiner la décomposition du produit scalaire de u et u' en m sous-produits scalaires, et le codage de k entiers sur chaque fil d'entrée du circuit, il est possible de choisir k tel que k divise m. Le produit scalaire de u et u' peut alors être décomposé en m sous-produits scalaires de vecteurs de longueur N/km. 15 La somme des résultats de ces m produits scalaire permet d'obtenir un score encodé S défini par la formule suivante : N/k = Eu.u, k(o-i)k+i) i=i N/k = (22.E1 (1-1(j-1)k+1 .1-1(j-i)k+1) 2c2 (--- ) --- 22.ck(ujk.1-1j113) i=1 et de la forme suivante si on déploie l'expression ci-dessus et que l'on rassemble les termes par puissance de 2: = 22'c1 - ai + 2c2 - az + 22'2 - a2 + 2E3 - a3 + - -- + 22.ck - ak avec ai les termes en 20 22 'ci rassemblant les produits d'entiers ui et u'i de mêmes indices utiles pour le calcul du produit scalaire et u et u', et avec ai les termes en 2E2, ..., 2ck rassemblant les produits restants, produits croisés d'entiers ui et u'; d'indices différents inutiles pour le calcul du produit scalaire de u et u'. Pour extraire le score S de sa version encodée S, il est possible d'extraire 25 les k sous-termes correspondants aux coefficients 22-E1, 22-Ek (c'est-à-dire les éléments a1, a2, ak), puis de les additionner. Les paragraphes ci-dessous présentent les spécificités du procédé pour différentes plages de valeur du diviseur m. m peut être déterminé en réalisant un 3043811 19 compromis entre les puissances de calcul du dispositif client et du dispositif de calcul distant ainsi que notamment des mémoires. Dans un premier mode de mise en oeuvre dans lequel le diviseur m est égal à 1, la fonction F peut être mise sous la forme du circuit représenté en figures 4a 5 et 4b. Un tel circuit comprend alors N/k multiplieurs d'entrée prenant chacun en entrée E k ((i I)k+ (u) et E k ((i I)k+ 1) 7u,, ) avec j N/k. Sur les figures 4a et 4b, ces multiplieurs sont notés r, et les fils d'entrée sont numérotés de 1 à 2N/k. Les N/k fils de sortie des multiplieurs portent les valeurs Eu.u/((j - i)k+ 1) dont la somme est égale au score encodé S décrit ci-dessus. Le circuit comporte un multiplieur de 10 sortie supplémentaire, numéroté rr,,,k+i, nécessaire à la conversion du circuit sous forme de QAP. Ce multiplieur multiplie la sortie du produit scalaire par 1 afin de ne pas modifier le score encodé S. Enfin, un séparateur (« Split gate ») est employé afin d'extraire les coefficients a, avec i k correspondant aux termes du produit scalaire u.u'. La sommation de ces termes d'abord séparés du score encodé puis 15 reconstitués par multiplication par des puissances de deux et additionnés permet d'obtenir le score S. Les figures 4a et 4b correspondent à une mise en oeuvre dans laquelle le score est comparé au seuil prédéterminé T. La valeur (S-T) est alors calculée et fournie en entrée d'un deuxième séparateur afin d'extraire le bit de signe indiquant le résultat de la comparaison. 20 Plus précisément, on entendra par la suite par séparateur une porte arithmétique qui permet de séparer un entier bit par bit. Etant donné un entier a E ZZq que l'on sait tenir sur r bits, le séparateur contient un fil d'entrée (contenant l'entier a) et fils de sortie. Sa définition, en termes de contraintes arithmétiques élémentaires, est donnée par exemple dans l'article Pinocchio cité, paragraphe 3.2. Elle est 25 rappelée à titre indicatif. Notons ici Co le fil d'entrée et c1, ..., cr les fils de sortie. Le circuit arithmétique de la porte dite « séparateur » est défini comme suit : - la concaténation des bits en sortie est égale à l'entrée 2 2i-1- - C1 = co i=i - chaque fil de sortie contient une valeur booléenne (0 ou 1) : Vi E tl, ..., TI: ci - (1 - ci) = 0 Lorsqu'on utilise une porte « séparateur » au sein d'un circuit, l'entier est 30 déterminé comme une borne supérieure atteinte étant donné la taille des entrées 3043811 20 du circuit et l'ensemble des portes arithmétiques situées entre les entrées et le séparateur. Un exemple de mise en oeuvre est représenté en figures 5a et 5b pour N = 3000, n = 8, q = 256, k = 3. Dans un tel mode de mise en oeuvre, les valeurs 5 suivantes peuvent être utilisées pour les paramètres Ei : E1 = 0, E2 = 26, E3 = 78. Dans un deuxième mode de mise en oeuvre dans lequel le diviseur m est égal à 2 ou 3, la fonction F peut être décomposée en une fonction F1 calculant un sous-produit scalaire entre deux vecteurs de taille N/km, à utiliser m fois, et une 10 fonction F2 calculant la somme de m valeurs, correspondant à un score codé, et réalisant l'extraction du score correspondant égal au produit scalaire recherché. Comme représenté en figures 6a à 6c, le circuit correspondant comprend alors au moins N/km opérateurs de multiplication reliés aux fils d'entrée du circuit, une mémoire de stockage, et au moins un opérateur d'addition, et l'évaluation du 15 circuit comprend itérativement un calcul de chacun des m produits scalaires à l'aide desdits N/km opérateurs de multiplication, un stockage des m résultats des calculs desdits produits scalaires dans ladite mémoire de stockage et une sommation desdits résultats à l'aide dudit opérateur d'addition. Avec F1 et F2 ainsi définis, l'évaluation de la fonction F correspond alors à 20 m applications de la fonction F1 suivies d'une application de la fonction F2 . Le circuit représenté en figures 6a à 6c comprend ainsi N/km multiplieurs d'entrée prenant chacun en entrée, lors de l'itération z de la fonction F1, Ek((z-mi)N mi) ijk+i) ijk+i)(u) et Ek((z-,u' ) avec 1 j N/km. Sur les figures 6a à 6c, ces multiplieurs sont notés r, et les fils d'entrée sont numérotés de 1 à 2N/km. 25 Les m applications de la fonction F1 permettent de calculer les sous-scores codés gz , pour z e {1, m} : N I'kin Sz =Eu u k((z-1).(N lin)+U-1).k+1) , j =1 A titre d'exemple, pour z = 1, on a : 3043811 21 N/k.m. = wuik ((j-1)k+1) , j=1 Ni = (22.ei (110-1)k+1.11(1-1)k+1) 2e2 + - -- 22.£k 1=1 - (Ulk - U;k)) Les N/km fils de sortie des multiplieurs portent ainsi lors de l'itération z les ( m (z-1) N+0 1)k+1 valeurs Eu.uf,kl ) dont la somme est égale au score encodé SZ décrit ci- dessus. Le circuit comporte un multiplieur de sortie supplémentaire, numéroté rN/km+1, nécessaire à la conversion du circuit sous forme de QAP. Les m sous- 5 scores codés SZ, notés g,(°ut)sur les figures 6a à 6c, sont stockés dans la mémoire de stockage correspondant aux m bus (« Bus Bank ») du procédé de calcul vérifiable. L'évaluation de la fonction F2, avec en entrée les m valeurs issues des bus, notées g,(in) sur les figures 6a à 6c, permet d'obtenir le score codé S décrit ci-dessus. 10 Comme dans le cas du circuit des figures 4a et 4b, un premier séparateur permet de récupérer les termes a, avec i k correspondant aux termes du produit scalaire u.u'. La sommation de ces termes permet d'obtenir le score S qui est ensuite comparé au seuil prédéterminé T. Selon une variante non représenté, la fonction F1 peut comprendre le 15 décodage du sous-score codé g, obtenu lors de son évaluation en un sous-score S. . Un tel décodage peut être réalisé de manière similaire au décodage du score codé S présenté ci-dessus. La fonction F2 comprend alors uniquement la sommation des sous-scores Sz pour obtenir le score S correspondant au produit scalaire u.u', selon la formule : m m 7N/km k =1Uz - lez z=1 1Sz =1 1U 11 (z-1)-(N Im)+(j-1)-k+i U(z-1)-(N Im)+(j-1)-k+i z=1 z=1 j=1 i=1 = (1i,121) = S 20 Dans un troisième mode de mise en oeuvre dans lequel le diviseur m est supérieur ou égal à 4, il est possible de décomposer la fonction F en une fonction F1 et une fonction F2, à utiliser alternativement et m fois au total, qui prennent chacune en entrée deux vecteurs de taille %In et un sous-score, et retournent en 3043811 22 sortie un sous-score mis à jour défini comme la somme du sous-score donné en entrée avec le résultat du produit scalaire des vecteurs fournis en entrée ; et une fonction F3 qui décode un score codé S en un score S. Comme représenté en figures 7a et 7b, le circuit comprend alors au moins 5 un premier sous-circuit de calcul de produit scalaire comprenant N/km premiers opérateurs de multiplication reliés aux fils d'entrée du circuit, pour l'évaluation de la fonction F1 pour z impair, et une première mémoire de stockage, et un second sous-circuit de calcul de produit scalaire comprenant N/km seconds opérateurs de multiplication reliés aux fils d'entrée du circuit, pour l'évaluation de la fonction F2 10 pour z pair, et une seconde mémoire de stockage, chacun desdits sous-circuit étant également relié à une sortie de la mémoire de stockage de l'autre sous-circuit, et l'évaluation du circuit comprend itérativement un calcul de chacun des m produits scalaires en utilisant alternativement le premier ou le second sous-circuit pour calculer la somme du produit scalaire des valeurs des fils d'entrée de ce 15 sous-circuit et de la valeur stockée dans la mémoire de stockage de l'autre sous- circuit. Avec F1, F2 et F3 ainsi définis, l'évaluation de la fonction F correspond alors à m applications alternativement de la fonction F1 et de la fonction F2 suivies d'une application de la fonction F3 . 20 Le circuit représenté en figures 7a et 7b comprend ainsi deux ensembles de N/km multiplieurs d'entrée. Lors de l'itération z de la fonction F1 ou F2, les N/km multiplicateurs du sous-circuit concerné prennent alors chacun en entrée, Ek((z-r+(. i)k+i) , 1)k+1) 0.0 et Ek((z-ml)N+ ) avec j N/km. Sur les figures 7a et 7b, ces multiplieurs sont notés r, avec respectivement j N/km et N/km +2 1. Les paragraphes ci-dessous décrivent plus en détail ces opérations en fonction de la valeur du diviseur m. Cas m = 1: Dans le premier mode de mise en oeuvre où m=1, un 30 environnement bilinéaire asymétrique (q, G1, G2, GT, g1, g2, e) est défini avec q est un nombre premier, G1, G2 et GT trois groupes d'ordre q, ,q1 un générateur de G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e: G1 x G2 GT. 3043811 24 Le circuit arithmétique peut être représenté sous la forme d'une représentation polynomiale du circuit Q = (t, V, W, Y) de taille p et de degré 6, avec V={vi}, W={wi}, Y={yi}, 0 i p. Sont notés par la suite : 5 - Iio = [1, ..., O} l'ensemble des indices correspondants aux fils d'entrée/sortie du circuit, - Imid = {O + 1, ...,p} l'ensemble des indices des fils intermédiaires du circuit n'étant pas des fils d'entrée du circuit. Lors de l'étape de génération E3 d'une clé publique d'évaluation et d'une 10 clé publique de vérification, des aléas rwrw,s,a,,aw,ay,fl,y sont tout d'abord générés dans ZZq. Puis les coefficients suivants sont définis : ry = r, - rw, gvi= 91rv, gwi= rw 9w2 = 92 rw 93,1 = 91rY et 9y2 = 92 rY - La clé publique d'évaluation EKF est ensuite générée comme égale à 15 (EKF1, EKF2) où fa I 19vivi(s)lieirnid, 19w1wi (5.) iai(s)1 EKF, = Igviavvi(s)) lElmid, tgwiaw.wi(s))lEl -mid 'tY g laYYi(s))lElmid iE[1,8]'Lgvie.vi(s)e gwlwi(s) yle.Y i(s)) EKF2 = (19w2wi(s) lElmici) La clé publique de vérification VKF est également générée comme égale à (VKF1, VKF2) où : VKF1 = (91, (9vivi(s)lie[1,6], (93,131i(s)lie[1,6]) VKF2 = (92, 92av, 92aw, 92aY , 92Y, e."1, 9y2t(s), tgw2wi(s)ii,[1,6]). 20 Le dispositif de calcul distant obtient E4 ensuite le circuit arithmétique, et la clé publique d'évaluation. Pour chaque donnée biométrique de l'entité, au moins une valeur de correspondance entre la donnée biométrique de l'entité et au moins une donnée biométrique de référence peut alors être déterminée E5 par le dispositif de calcul 25 distant en évaluant le circuit arithmétique reçu à partir des données biométriques de l'entité et de référence. L'ensemble des valeurs du circuit {ci}ie[1,p] peut alors être obtenu. La génération E6 par le dispositif de calcul distant, pour chaque valeur de correspondance déterminée, d'une preuve de la correction de l'exécution du calcul lElmid 3043811 25 de la valeur de correspondance, dite preuve générée = (Kt, Tt2) peut comprendre alors : -la détermination d'un polynôme h(x) tel que p(x) = h(x) - t(x) avec p(x) = (vo(x) + ci - vi(x)) - (wo(x) + ci - wi(x)) - 670(x) + 5 Ee,_, ci - Yi (x)), - le calcul de : gv Vinid (S), 9w, (S) gy, Yrnid (S), h(S) = gv1Cev.Vnlid(S), gw1aw.wmid(s), gy1aY.Ymid(s), et n:2 = (9w2w7nid(s)) 9v1e.vInid(s) - 9w1e.wInid(s) - gyte.YInid(s) où : 77mid (x) = Cl - Vi(X), Wmid(X) = Ci - Wi(X) etmid Ymid(X) = ci yi(x). 10 Le dispositif de calcul distant transmet E7 ensuite les valeurs de correspondance et lesdites preuves générées au dispositif client. Les preuves reçues par le dispositif client sont de la forme (rro, 1ri-2) avec : "no sous la forme : (gvi 1/m-id gw1Wmid g y1Y mid g1H gv1V'mid gw1lei mid g y1Y mid g12) et ur2sous la forme gw2wmid. 15 Le dispositif client vérifie E8 ensuite chaque preuve reçue (rro, Trr2) en mettant en oeuvre les tests d'égalité suivants : - ecgvivo(s) . gvivio(s) . gvivmid, 9w2wo(s) . 9w2wio(s) . gw2wmid) = e(gix, gy2t(s)) . e(gyiyo(s) . gyiyio(s) . gyjntid, g2 - e ((gvtvi mid)d1 ' (9w1e mid)d2 (g y1Y mid)d3 g2) = e((gviVniid)rli, g2 (XV) 20 e((gw1wnlid)d2 92aw) - e ((93,1Ymid)d3 , g 2aY) - e(giZ g2Y) = e(g mid - gwiWmid - g yiY mid g2flit) où 9vivi°(s) = [19/-1(9vivi(s))CL, gw2wi°(s) = re-1(9w2wi(s))ci et c3,n1 io(s) = ei(gyiYi(s))ciet (d1, d2, d3) des éléments de ZZq sur .1 bits avec .1 un paramètre de sécurité. Dans ce mode de mise en oeuvre, l'étape de vérification desdites 25 preuves reçues comprend donc une vérification de couplages par lot. Cas m > 1 : On appelle banque B un sous-ensemble des indices [1, p] (autrement dit un sous-ensemble des fils du circuit) et une instance d'une banque B est un ensemble de valeurs pour ces indices (par exemple notés IcilieB). 3043811 26 La fonction F est découpée en co sous-fonctions . Par exemple dans le cas des figures 6 et 7 on peut choisir respectivement co = 2 et co = 3 comme décrit ci-dessus. On définit G = ((f1e11, ..., Tu)))le[1,L] un ordonnancement de longueur L avec 5 fi e {1,...,co} l'indice de la fonction à calculer. A titre d'exemple, dans le cas m = 2 ou m = 3 décrit ci-dessus en référence aux figures 6a à 6c, L=m+1 et la fonction F est séparée en deux fonctions F1, F2. Les banques utilisées sont : (Bi0, BL1, BL2, BBm) où : - Bi, : banques de type entrée/sortie. Nombre d'instances : m + 1 10 - BL1 : banque de type local pour F1. Nombre d'instances : m - BL2 : banque de type local pour F2. Nombre d'instance : 1 - BB1, , BBm: banques de type bus. Une instance de chaque. L'ordonnancement des preuves, de longueur m + 1, est : a = ((1, (1,1,0,1,0, ... 0)), ..., (1, (m, m, 0, ...,1)), (2, (m + 1,0,1, ...,1))) Autrement dit, l'ordonnancement des preuves est : 15 - Pour l E {1,...,m}: digest de BL1(1), mise en gage de BB1, preuve avec BLi (1), entrées B10(1), et bus BB1. - Pour l = m + 1 : digest de BL2, preuve avec BL2, entrées B10(1), et tous les bus BB1, BBm A titre d'exemple, dans le cas m > 4 décrit ci-dessus en référence aux figures 7a et 20 7b, la fonction F est séparée en trois fonctions F1, F2, F3. Les banques utilisées sont : (Bi0, BL1, BL2, BL3, BB1, BB2) où : - Bi, : banques de type entrée/sortie. Nombre d'instances : m + 1 - BLi : banque de type local pour F1. Nombre d'instances : [m/21 - BL2 : banque de type local pour F2. Nombre d'instance : [m/2i 25 - B : banque de type local pour F3. Nombre d'instance : 1 - BB1,BB2 : banques de type bus. [m/21 instances de la première [mh] instances de la seconde. L'ordonnancement des preuves, de longueur m + 1, est : G = (61, a2, --- am, am+i) où : 3043811 27 - Pour / e {1, ...,m} : o Si / impair : digest de BL1([1/21), mise en gage de BB1, preuve avec BL1([1/21), entrées Bfr,(1), et bus BB1. = (1, (1, [1/21,0,0,[1/21,[1/21- 1)) o Si / pair : digest de BL2([1/21), mise en gage de BB2, preuve avec 5 BL2([1121), entrées Bfr,(1), et bus BB2. (2,(1,0,[11 21,0,[11 21- 1,[1121)) - Pour / = m + 1 : digest de BL3, preuve avec BL3, entrées Bic»), et la banque de bus BB1 (si m est impair) ou BB2 (sinon). 6/ = (3, (m + 1,0,0,1, [1 - 1121, 0)) ou a1 = (3, (m + 1,0,0,1,0, [1 - 1121)). Pour un nombre x la notation [921 (respectivement [92]) désigne l'entier naturel 10 supérieur ou égal (respectivement inférieur ou égal) à la valeur rationnelle x/2. Pour plus d'informations concernant l'utilisation des banques et d'un tel ordonnancement, les paragraphes ci-dessous peuvent être lus à la lumière de la publication référencée ci-dessus décrivant le protocole Geppetto dont le protocole présenté ci-dessous est dérivé. 15 Dans ces deuxième et troisième modes de mise en oeuvre, un environnement bilinéaire asymétrique (q,G1,G2,GT, q1, 92, e) est défini avec q est un nombre premier, G1, G2 et GT trois groupes d'ordre q, 91 un générateur de G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e: G1 x G2 GT. 20 Le circuit arithmétique peut être représenté sous la forme d'un multi-QAP Q = bibE[1,e],b,bEL1e, t, V, W, Y) de taille p et de degré 8, avec fR 1 r,un ensemble de banques Bb de Q utilisées dans le calcul de la fonction F, et V={vi}, W={wi}, Y={yi} avec 0 i p. Lors de l'étape de génération E3 par le dispositif client d'une clé publique 25 d'évaluation et d'une clé publique de vérification, des aléas s,{(abv,abw,aby,fib,yb)}be[v],r',rw sont générés dans Zq. Puis les coefficients suivants sont définis : ry = r, - rw, 9v1 = 91rv, 9v2 = 92r1, 9w1 = 91rw, 9w2 = 92rw, 934 = 91rY et 9y2 = 92rY - 3043811 28 La clé publique d'évaluation EKF est alors générée comme égale à : (tEKFbIbE[1,e], Igtslie[1,8], Cui , Cw1 , Cy1 , Cv2 , Cw2 , Cy2 )- , t(s) , t(s) , t(s) , t(s) , t(s) , (s) Chaque clef publique de banque EKFb est égale à (EKFb1,EKFb2) et générée en 5 calculant : 9v1vi(s), 9w1wi(s), gyi Yi(s), 9viabv.vi(s), 9wi abw.wi(s), 9y1abY.Yi(s), { Cnlll igb'vi(s) . C ryW1 . c flb.141i(S) ryy1 flb.31i(S) IEBb gviabv-t(s), gwiabw-t(s), gyiabyt(s), gviflb-t(s), gwiflb-t(s), gyiflb-t(s) E KFb2 = ( I glgw2wi(s)). , w2abw-t(s)). EBb La clé publique de vérification VKF est également générée comme égale à : ({17KFb}bE[1,e],91, 92, 9y2t(s)). Chaque clef publique de banque VKFb est égale à (92abv, g2abw, g2aby, g2 Yb, 92flblib). 10 Le dispositif de calcul distant obtient E4 le circuit arithmétique et la clé publique d'évaluation. Pour chaque donnée biométrique de l'entité, au moins une valeur de correspondance entre ladite donnée biométrique et au moins une donnée biométrique de référence peut alors être déterminée E5 par le dispositif de calcul 15 distant en évaluant le circuit arithmétique reçu à partir des données biométriques de l'entité et de référence. Le dispositif de calcul distant évalue chaque sous fonction FÛ, à partir des données biométriques de l'entité et de référence pour obtenir la valeur de correspondance et les valeurs du circuit. La génération E6 par le dispositif de calcul distant, pour chaque valeur de 20 correspondance déterminée, d'une preuve de la correction de l'exécution du calcul de la valeur de correspondance peut comprendre pour chaque l = {1, ...,L} une liste de digests et de preuves obtenus comme décrits ci-dessous. Soit A s [1, -e] l'ensemble des indices b E [1, -e] tels que Tib # 0 dans l'ordonnancement G = ((f1, (T11, --- Tle))) le [1,1_]. 25 On note par la suite : F = UbEABb , (c1} jeBbune instance de la banque Bb et A = fcilier l'ensemble des valeurs de F. Pour chaque banque Bb telle que b E A, -le dispositif de calcul distant génère des aléas de mises en gage ob = (obv, obw, oby) dans Zq. EKFb1 = J 3043811 29 -il calcule ensuite le digest D b égal à (Dbl, Db2) à partir de l'instance de la banque de variables Bb B b(T 1b) = [Ci E AlieBb et des aléas de mise en gage Ob. De tels digests sont tels que : o si la banque Bb est une banque d'entrée/sortie : Db1 = vlv(b)(s) g y131(b)(s)) 5 et D b2 = (g w2w(b) (s)) ' o si la banque Bb n'est pas une banque d'entrée/sortie : = (gll1V gW1 gy1 gll1 v(b)(s) w(b)(s) y (b) (s) bv.,(b)(s), g bw.w(b)(s) g yi a by y (b) (s) 9v1 (b) V1 cy s) gyiply(b)(s) plv(s) aW1 pl.w(b)( D b2 = (9w2w(b)(s)) avec : v(b)(s) = EiEBb ci - vi (s) + 0bv - t(s), w(b)(s) = EiEBb ci - wi (s) + 0bw - t(s), 10 y(b)(s) EiEBb ci - Yi(s) + oby - t(s). Le dispositif de calcul distant détermine ensuite un polynôme h(0(x) tel que p(1)(x) = h(1) (x) - t(x) avec p(0(x) = (vo(x) + EiEr ci - vj(x) + EbEA Obv - t(x)) - (IN o(X) EiEr ci - w (x) + EbEA obw - t(x)) - (y0(x) + EiEr ci - yj (x) + EbEA oby - t(x)) 15 Enfin, il calcule un élément de preuve Tr(1) égal à g1h(1)(s) . Le dispositif de calcul distant transmet E7 ensuite les valeurs de correspondance et lesdites preuves générées comprenant la liste de digests et d'éléments de preuve calculés au dispositif client. Les preuves reçues par le dispositif client sont de la forme : 20 D1(1), ... Re(1),71-(1) , ... , D1(L) , ... , Re(L) , KM où pout tout 1 E {1, ..., L}et E {1, ...,,e} : ( v (0 ,,,, (1) y (i) ii(1) Wb(l) y'(1) Zb(0) l w (01 Db(1) = ( ,gwib_ ,,q), ,g,,_ ,,qw_ ,gybi ,gi *g.,2b ) et (1) g 1 (I) - Deux variantes de mise en oeuvre de vérification de la preuve reçue E8 25 sont explicitées ci-dessous. Dans une première variante de mise en oeuvre, le dispositif client vérifie ensuite chaque preuve reçue en mettant en oeuvre : 3043811 30 une vérification des L - -e digests, pour 1 E {1, ..., L} et b E {1, ..., -e} (1) comprenant les tests d'égalité suivants : o , e (gyvi , g2 abv) = e (gyvf(1) , 92) o ( e (g wv v0 , 92abw) = e (g ww , 92) "(1) 5 - e yYbi , g2 abY) = e (9v_ (1), 92) o e (g iz b(1) 2y b) = e (g Vb(1) Wv v ib_(1) 913,,-(1) g2 P b une vérification des L preuves comprenant pour 1 E {1, ..., L} le test d'égalité suivant : e (gvb(/) n (gww2b (0)) e (0 gy2t(s)) e(n Yb (0 b=1Vi ) b=1 b=1 gyi g2 10 Dans une deuxième variante de mise en oeuvre, le dispositif client vérifie ensuite chaque preuve reçue en mettant en oeuvre une vérification par lot (« batch verification ») comprenant, étant donné un paramètre de correction À. : une sélection d'un vecteur aléatoire (d1, ..., d3.e) d'éléments de taille À., une vérification par lot les L - -e digests, en -e fois en mettant en oeuvre les 15 tests d'égalité suivants, pour b E {1, ..., -e} : ,(0)d1 ,,,,(0)dL+1 o e (1-1K1(gyvbi 92abv) - e (rif =1(9Z_ 92abw - f (I) d21J+1 111=1 (gWW1b cvlif(1) di r[L e (1-1K1(gYb g2abY)= e ir[L1=1 (' yi yb (I) )d2.L+1 11=1 (g311 92 L Zb (1) (0 W. (I) Y. (1)\ o e nt=1 ) 92Y b = e F=1 vvi' - gwi: - gyï ) , g 2fl b) 20 une vérification par lot les L preuves en mettant en oeuvre le test d'égalité suivant: f V b(1)\di e ( W b(1))/ H (0)di , g y2t(s)) Hf =le (rg =1V' vt ) '11=1 gw2 = e (1-1K1(g1 / y (0\d1 e (rif=i r-g=1 vy;_ ) ..« , _2), et en option une vérification de l'appartenance des éléments sur lesquels 25 les couplages s'appliquent à leurs groupes respectifs. 3043811 31 Le procédé mis en oeuvre permet ainsi de réaliser une identification biométrique en comparant des données biométriques dans le cadre d'un protocole de calcul publiquement vérifiable tout en minimisant le temps nécessaire à la production et à la vérification des preuves relatives à la bonne exécution de ce 5 calcul, grâce à la minimisation du nombre de multiplieurs employés pour représenter ce calcul sous forme de circuit arithmétique. REVENDICATIONS1. Procédé d'identification biométrique d'une entité, par un système d'identification biométrique comprenant un dispositif client et un dispositif de calcul distant, comprenant : - un calcul (FI) d'au moins une valeur de correspondance entre au moins une donnée biométrique de l'entité u et au moins une donnée biométrique de référence u', par application d'une fonction F auxdites données biométriques, chacune desdites données étant un vecteur de N entiers binaires u, ou u', avec 1 i N, chaque entier étant codé sur n bits, ladite fonction comprenant un produit scalaire entre une donnée biométrique de l'entité et une donnée biométrique de référence, ledit calcul mettant en oeuvre un procédé non-interactif de calcul publiquement vérifiable comprenant des étapes de : - représentation (El) de ladite fonction sous forme d'un circuit arithmétique comprenant des fils transportant des valeurs du corps premier fini Zc n avec q un nombre premier, et reliant des opérateurs d'addition et de multiplication, - conversion (E2) dudit circuit arithmétique en une représentation polynomiale, QAP (« Quadratic Arithmetic Program ») ou multi- QAP, - génération (E3) d'une clé publique d'évaluation et d'une clé publique de vérification en fonction de ladite représentation polynomiale, - obtention (E4) par le dispositif de calcul distant du circuit arithmétique et de la clé publique d'évaluation, - pour chaque donnée biométrique de l'entité, détermination (E5) d'au moins une valeur de correspondance entre ladite donnée biométrique et au moins une donnée biométrique de référence par le dispositif de calcul distant en évaluant le circuit arithmétique ayant pour entrées la donnée biométrique de l'entité et la donnée biométrique de référence, - pour chaque valeur de correspondance déterminée, génération (E6) par le dispositif de calcul distant d'une preuve de la 3043811 33 correction de l'exécution du calcul de la valeur de correspondance, dite preuve générée, à partir de ladite représentation polynomiale, de la clé publique d'évaluation et du résultat de l'évaluation du circuit arithmétique, 5 - transmission (E7) par le dispositif de calcul distant desdites valeurs de correspondance et desdites preuves générées au dispositif client, - vérification (E8) desdites preuves reçues par le dispositif client à l'aide de la clé de vérification publique, 10 - une identification (F2) de l'entité par le dispositif client en fonction des valeurs de correspondance et du résultat de ladite vérification de preuves, caractérisé en ce que : - la représentation de ladite fonction (El) comprend l'encodage d'un nombre 15 entier k>1 d'entiers binaires d'un vecteur d'une donnée biométrique sur au moins un fil d'entrée du circuit, - et la fonction F comprenant au moins m produits scalaires, m étant un diviseur de la longueur N des vecteurs de données biométriques, ^ si le diviseur m est égal à 2 ou 3, 20 le circuit comprend au moins N/km opérateurs de multiplication reliés aux fils d'entrée du circuit, une mémoire de stockage, et au moins un opérateur d'addition, et l'évaluation du circuit (E5) comprend itérativement un calcul de chacun des m produits scalaires à l'aide desdits N/km opérateurs de 25 multiplication, un stockage des m résultats des calculs desdits produits scalaires dans ladite mémoire de stockage et une sommation desdits résultats à l'aide dudit opérateur d'addition, ^ si le diviseur m est supérieur ou égal à 4, le circuit comprend au moins un premier sous-circuit de calcul de 30 produit scalaire comprenant N/km premiers opérateurs de multiplication reliés aux fils d'entrée du circuit et une première mémoire de stockage, et un second sous-circuit de calcul de produit scalaire comprenant N/km seconds opérateurs de multiplication reliés aux fils d'entrée du circuit et une seconde mémoire de stockage, chacun desdits sous-circuit étant 3043811 34 également relié à une sortie de la mémoire de stockage de l'autre sous-circuit, et l'évaluation du circuit (E5) comprend itérativement un calcul de chacun des m produits scalaires en utilisant alternativement le premier 5 ou le second sous-circuit pour calculer la somme du produit scalaire des valeurs des fils d'entrée de ce sous-circuit et de la valeur stockée dans la mémoire de stockage de l'autre sous-circuit. 2. Procédé d'identification selon la revendication précédente dans lequel l'étape 10 de vérification desdites preuves reçues (E8) comprend une vérification de couplages par lot. 3. Procédé d'identification selon l'une des revendications précédentes, dans lequel : 15 si le diviseur m de la longueur N des vecteurs de données biométriques est égal à 1, étant donné un environnement bilinéaire asymétrique (q,Gi,G2,GT,g1,92,e) où q est un nombre premier G1, G2 et GT trois groupes d'ordre q, g1 un générateur de G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e:Glx G2 20 GT et le circuit arithmétique étant représenté sous la forme d'un QAP du circuit Q = (t, V, W, Y) de taille p et de degré 6, avec V={vi}, W={wi}, Y={yi}, 0 i p, et étant donnés Iio = {1, ..., 0} l'ensemble des indices correspondants aux fils d'entrée/sortie du circuit et Imid = tO + 1, ...,p1 l'ensemble des indices des fils intermédiaires du circuit n'étant pas des fils d'entrée du circuit, 25 - l'étape de génération (E3) d'une clé publique d'évaluation et d'une clé publique de vérification comprend : - la génération d'aléas rwrw,s,a,,aw,ay, fi, y dans Zc - la définition des coefficients ry = r, - rw, 9v1 = girv, 9144 = 91 rw 9w2 = 9zrw 93/1 = 91rY et 9y2 = 92rY, 30 - la génération de la clé publique d'évaluation EKF égale à (EKF1, EKF2) où f a 7 1,9'1)1 vi(s) tgw1wi(s)liEirnid' ia Yi (s)1 jEITnid' EKF, = ayyi(s)1 mid \ 1 tg si}ie[1,8] tgvl e.vi(s) . 9wie.wi(s) . gyte.Yi(s)) \ 3043811 EKF2 = (19w2w1(s)1iEimid) - la génération de la clé publique de vérification VKF égale à (VKF1, VKF2) où : VKF1 = (gi,Igvivi(s)11e[1,6],[93,1Yi(s)1ie[1,6]) VKF2 = (92, 92av, 92aw, 92aY, 92 92 9y2 t(s), [9w2wi(s)1-E[1,6]) -la génération (E6) par le dispositif de calcul distant d'une preuve de la correction de l'exécution du calcul d'une valeur de correspondance comprend, fcilie[1,p] étant l'ensemble des valeurs du circuit déterminées lors de l'étape de détermination de 5 la valeur de correspondance: - la détermination d'un polynôme h(x) tel que p(x) = h(x) - t(x) avec p(x) = (vo(x) + ci - vi (x)) - (wo (x) + ci - wi (x)) - 670(x) + Ee,-1 ci - Yi (x)), - le calcul de la preuve générée n- = (n-1, n-2) avec : 9vivmid(s), 9wiwmid(s), gyl Ymid(s), gl h(s), 10 TL1= gvlav.vmid(s), gwl aw.wmid(s), gyl aY.Ymid(s),TC2 = (gw2wmid(s)) gvle.vmid(s) - gwle.wmid(s) - gyle.Ymid(s) où : vmid (x) = EiElmid Ci Vi(X), Wmid(X) = ci wi (x) et Ymid(X) = ci Yi (x) -et, dans lequel lesdites preuves reçues par le dispositif client étant égales à (rro, 15 TTr2) avec -n-r1 sous la forme : (g v1V mid gw1Wmid gylYmid,g1H gvlv'mid gwlWmid gylY 91Z) et ur2 sous la forme gw2wmid, la vérification d'une preuve reçue (E8) comprend la mise en oeuvre des tests d'égalité suivants : - ecgvivo(s) . gvivio(s) . gylvmid,9w2w0(s). 9w2wio(s). gw2wrnid) _ 20 e(e gy2t(s)) . e(gyiyo(s) . gyiyio(s) . gyjntid, g2), - e ((gviv, rnid)di (gwiw, ?nid) d2 (gyi yr mi ,a)d3, 92 = e((gvi limid) g2 av) e((9w114/Inid)d2 92aw) - e ((gyjnlid)d3 92aY), - e(giz 92Y) = e(gviVmid - gwiWmid - gyiYmid, g2flit) Où gylvio(s) = Ile i(gvivi(s))ci, 9w2 wi° (s) = [Pt 1(9w2 wi(s)) et 9y1Yio(s) = 25 IIB 1(9y1yi(s))ciet d2, d3) des éléments de ZZq sur À bits avec À un paramètre de sécurité. 4. Procédé d'identification selon la revendication 1 dans lequel : 3043811 36 si le diviseur m de la longueur N des vecteurs de données biométriques est supérieur ou égal à 2, étant donné un environnement bilinéaire asymétrique (q, G1, G2, GT, 91, 92, e) où q est un nombre premier G1, G2 et GT trois groupes d'ordre q, 91 un générateur de 5 G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e:Glx G2 GT, le circuit arithmétique étant représenté sous la forme d'un multi-QAP Q = (tBblbe[1,e],t,17,W,Y) de taille p et de degré 8, avec 1 fR b,bE[1,e] un ensemble de banques Bb de Q utilisées dans le calcul de la fonction F, et V={vi}, W={wi}, Y={yi} avec 0 i p , 10 - l'étape de génération (E3) d'une clé publique d'évaluation et d'une clé publique de vérification comprend : - une génération d'aléas s,a 1(---bwabw,aby,flb,yb)lbe[v],r',rwdans Zq, - une définition des coefficients suivants : ry = rv ' rw, 9v1 = 91rv, 9v2 = 92rv, 9wi = 91rw 9w2 = 92rw 9y1 = 911-Y et 9y2= 92r Y, 15 - une génération de la clé publique d'évaluation EKF égale à : ({EKFb }bE [1t(s) t(s) t(s) t(s) t(s) t(s)) »ie [1,8], Uv1 9w1 y1 , 9v2 9w2 9y2 iEBb 9v1abv.t(s), gwiabw.t(s), gyiabyt(s), gviflb-t(s), gwiflb.t(s), gyiflb.t(s) EKFb 2 = (9w2 WL (S) LEBb , `11WLabw't(S)) - une génération de la clé publique de vérification VKF égale à : ({171(Fb }bE [1,e], 91, 92, 9y2t(s)) où chaque clef publique de banque VKFb est égale à (g2abv, g2abw, g2aby, 92 Yb, g2flbilb), 20 -la détermination d'une valeur de correspondance (E5) comprend, la fonction F étant découpée en co sous-fonctions F1, ..., Fa, et G = ((f1, (T11, T1e))) étant le [1,1_,] un ordonnancement de longueur L avec fi E {1, ..., co}, l'évaluation de chaque sous fonction Fa, à partir des données biométriques de l'entité et de référence et la détermination des valeurs du circuit, 25 -la génération (E6) par le dispositif de calcul distant d'une preuve de la correction de l'exécution du calcul d'une valeur de correspondance comprend, pour chaque 1=[1,...,L}: où chaque clef publique de banque EKFb est égale à (EKFb1, EKFb2) avec : 7 g vil) L(S) g wiW L(S) g y 131t(s) g v bV.V L(S) g vna bWW L(S) g yia by L(S) EKFb1 = b L(S) flb.WL (S') cry flb.31L(S) Clll cw1 y1 3043811 37 - pour chaque banque Bb telle que b E A, avec A s [1, -e] l'ensemble des indices b E [1, -e] tels que Tib # 0, F = UbEABb, ICI} I EBb une instance de la banque Bb, A = fcilier l'ensemble des valeurs de F : o une génération d'aléas de mises en gage dans Zq : ob = (obwobw,oby), 5 o un calcul d'un digest Db égal à (Dbl,Db2) à partir de l'instance de la banque de variables Bb : Bb(T(b) = {Ci E A}ieBb et des aléas de mise en gage ob et tel que : si la banque Bb est une banque d'entrée/sortie : Dbl = (gylv(b)(s), g y 131 (b) (s)) et Db2 = (gw2w(b)(s)), 10 si la banque Bb n'est pas une banque d'entrée/sortie : Dbl = ( v(b)(s) , w (b) ( s) , y(b)(s ) , abb.v(b)(s) , abww(b) (s) gY1 ab Y y(b)(s) Cvl , Cw1 , cyl , cvl , Cwl avlgb.v(b)(s) .awlgb.w(b)(s) .aylgb.Y(b)(s) Db2 = (gw2w(b)(s)) avec : v(b)(s) = EiEBb ci - v i(s) + oh, - t(s) , w(b)/(s) = EiEBb ci - w1(s) + obw - t(s) , y(b)s) = EiEBb ci - yi (s) + oby - t(s), 15 - une détermination d'un polynôme h(0(x) tel que p(0(x) = h(0(x) - t(x) avec P(1)(x) = (vo(x) + EiEF Ci ' vj(x) + EbEA Obv . t(x)) ' (wo(x) + E iEr Ci ' Wi (X) + EbEA 0 bw - t(x)) - 670(X) + EiEr ci - Yi (x) + EbEA oby - t(x)) - un calcul d'un élément de preuve Tr(1) égal à g1h(1)(s) -et, dans lequel lesdites preuves reçues par le dispositif client étant de la forme 20 D1(1), ..., Re(1) , n- (1) , ...,D1,) ... , Re(L) , n-(L) où pour tout / E {1, ..., L} et b e ti, ...,,e1 : (1) =vf co wb (i) y (i) v(0 wi(i) ybi(i) z (0 i w (0 Db gy ,gwi ,q) ,q,_ ,q'_ ,gyi ,gi J ,vw2\ ) et (( (0 H (0 n- = , la vérification d'une preuve reçue (E8) comprend : - une vérification des L - -e digests, pour l E {1, ..., L} et 25 [1, ..., -e} comprenant la mise en oeuvre des tests d'égalité suivants : v (1) = e (9,,v ib(1) 92) = e (gwi , 92 o e , g 2" bv) v v b(1) w, (1) o e , g 2abw) b e 3043811 38 o e(,,(1) gyibi ,g2abY) = e(gyY(1),92) ( z (0 i vb(1) Wb(1) Yb a . ) o yg 1 , g2I-'11 Yb e ,g'i_ b ' 92n) = e V'vt - gwt - - une vérification des L preuves comprenant pour / e {1, ... , L} la mise en oeuvre du test d'égalité suivant : e Figvb(1)) e(0 t(s) e ( yb (1) =(0,9y2 vyt b =1 5 5. Procédé d'identification selon l'une des revendications 1 ou 2 dans lequel : si le diviseur m de la longueur N des vecteurs de données biométriques est supérieur ou égal à 2, étant donné un environnement bilinéaire asymétrique (q, G1, G2, GT, 91, 92, e) où q 10 est un nombre premier G1, G2 et GT trois groupes d'ordre q, gi un générateur de G1, 92 un générateur de G2, et e un couplage bilinéaire non-dégénéré e: G1 x G2 GT, le circuit arithmétique étant représenté sous la forme d'un multi-QAP Q = (tBblbe[1,e],t,17 ,W,Y) de taille p et de degré 8, avec f R b bE [1,e] un ensemble de e banques Bb de Q utilisées dans le calcul de la fonction F, et V={vi}, W={wi}, Y={yi} 15 avec 0 i p , - l'étape de génération (E3) d'une clé publique d'évaluation et d'une clé publique de vérification comprend : - une génération d'aléas s, ((abv, abw,aby,fib, Yb)jbe[v], ry, rw dans Zq, - une définition des coefficients suivants : ry = rv ' rw, 9v1 = 91rv, 9v2 = 92rv, , 20 9wi = 91r w, 9w2 = 92r w, 9y1 = 91rY et 9y2= 92rY, - une génération de la clé publique d'évaluation EKF égale à : (tEKFb IbE [1,e], 1911 t(s) , iE[1,61, Ulll , U t(s) , W1 , U t(s) , yl , U t (s) , v2 , U t (s) , w2 , U y2 , t (s)) où chaque clef publique de banque EKFb est égale à (EKFb1, EKFb2) avec : (b=1 b=1 92) EKFb1 = 7 gvivi(s), gwiwi(s), gy1Yi(s), g vlabliVi(S), gwlabw.Wi(S) gylaby'Y i(S) \ { nvl flb'v i(s) . c nw1 igt.'w i(s) . (7 igb.Yi(s) c cy1 tEBb EKFb2 \ 9v1abv.t(s), gwiabw.t(s), gyiabyt(s), gviflb-t(s), gwiflb.t(s), gyiflb.t(s) = (19w2WL(S)IteBb, 9w2 abw.t(s)) J - une génération de la clé publique de vérification VKF égale à : (t171(FbIbE[1,e], 91, 92, 9y2t(s)) où chaque clef publique de banque VKFb est 25 égale à (g2aby, g2abw, 92aby, 92Y b g2flblib), 3043811 39 -la détermination d'une valeur de correspondance (E5) comprend, la fonction F étant découpée en co sous-fonctions F1, ...,F,, et a = ((f1, (T11, ... , T1e))) étant 1E [1,L] un ordonnancement de longueur L avec fi e {1, ..., co}, une évaluation de chaque sous fonction FÛ, à partir des données biométriques de l'entité et de référence et 5 une détermination des valeurs du circuit, -la génération (E6) par le dispositif de calcul distant d'une preuve de la correction de l'exécution du calcul d'une valeur de correspondance comprend, pour chaque 1 = {1, ... , 1,} : - pour chaque banque Bb telle que b E A, avec A s [1, -e] l'ensemble des 10 indices b E [1, -e] tels que Tib # 0, F = UbEABb, (C11 une instance de la I EBb banque Bb, A = fcilier l'ensemble des valeurs de F : o une génération d'aléas de mises en gage dans Zq : ob = (obwobw,oby), o un calcul d'un digest Db égal à (Dbl,Db2) à partir de l'instance de la banque de variables Bb : Bb(T(b) = {Ci E A}ieBb et des aléas de mise en 15 gage ob et tel que : - si la banque Bb est une banque d'entrée/sortie : Dbl = (gylv(b)(s), gyle)(s)) et Db2 = (gw2w(b)(s)), si la banque Bb n'est pas une banque d'entrée/sortie : Dbl = 9v1V(b)(S) , 9W1W(b)(S) , g 31131(b) Cs) , 9V1Cebv.V(b) Cs) , 9W1Cebw.W(b)(S) , g ylabY.31(b) Cs) ( cri P'0,(b)(S) ry )gb.w(b)(s) . r, )gby(b)(s) vi ' cwi c yl Db2 = (gw2w(b)(s)) avec : 20 v(b)(s) = EiEBb ci - vi(s) + ob, - t(s), w(b)(s) = EiEBb ci - wi(s) + obw - /t(s) y(b)(s) = EiEBb ci - Yi (s) oby - t(s), - une détermination d'un polynôme h(/)(x) tel que p(/)(x) = h(/)(x) - t(x) avec P(1)(x) = (vo(x) + iEr Ci - VI (X) + EbEA Obv - t(x)) - (Wo (X) + iEr Ci - 1411(X) + 25 EbEA obw - t(x)) - 670(x) + iEr Ci - YI (X) + EbEA Oby - t(x)) - un calcul d'un élément de preuve Tr(1) égal à glh(1)(s) -et, dans lequel lesdites preuves reçues par le dispositif client étant de la forme D1(1), ..., D»), It(1), D1(L), Re(L), It(L) où pour tout / E {1, ..., L} et b E 3043811 Db (0 (gbf , gwib: , g).,,_ , gvbii , giy: , gybi , gi b , gw2 ( V (1) W (1) Y (0 Iii (1) lei (i) Y' (i) Z (0 ( Wh (0)) et ) n-(0 = 0(1), la vérification (E8) d'une preuve reçue comprend, étant donné un paramètre de correction À : - une sélection d'un vecteur aléatoire (d1, ..., d3.e) d'éléments de taille il, 5 - une vérification par lot des L - -e digests comprenant la mise en oeuvre -e fois des tests d'égalité suivants, pour b E {1, ..., -e} : ,,(0) d1 d1,+1 ( W'(1)) o e rif=i(g,,1 , 92 abv . e i Hi1L =1 9144 , 92 abw . ( d2 L-E/ , (0) ) ( Vb(1))di . FIL -1 e 1-1Ki(gyYbi ,92aby = e riKi o',1 i=i ,.,w1 ( y (I) \ d2 L+1 Hf =dg 3,1 ) , 92 i 10 o e (Z (I) \di v (0 w (I) y (0 )d 1 r-IF=1 vi_ b ) , g2Y b) = e(rlf=1(gyf - 9w1 - gy;_ ,g2flblib) - une vérification par lot des L preuves comprenant la mise en oeuvre du test d'égalité suivant : ne H (g1V,f (1) )d I n(gz2b(o) L (.e L e H())di nY b ) g2 (1)dl = e([1( 1 91 , gy2t(s)) e (y1 (FIFI 1=1 1=1 b =1 6. Procédé d'identification selon l'une des revendications précédentes dans lequel 15 l'identification de l'entité comprend une comparaison des valeurs de correspondance à un seuil prédéterminé. 7. Procédé d'identification selon l'une des revendications 1 à 5 dans lequel la fonction F comprend une comparaison du résultat du produit scalaire entre 20 lesdites données biométriques de l'entité et de référence à un seuil prédéterminé. 8. Procédé d'identification selon l'une des revendications précédentes dans lequel l'encodage de k entiers binaires u, ou u', sur un fil d'entrée d'un jème opérateur de (z-1)N 25 multiplication, j N/k, est égal à Ek( m +(j i)k+i)f u.i) ou Ek((z-m1-)N+(j 1)k+1) (u') ) avec 1 z m, et est donné par la formule : 1=1 b =1 b =1 3043811 41 Ek((j-1)k+1)(x) =1.1 Le" x(j-ijk+i = 2E1 x(j-ijk+1 + - -- 2ek x(j-i)k+k i=1 avec El, ...,Ek des entiers prédéterminés. 9. Produit programme d'ordinateur comprenant des instructions de code pour l'exécution d'un procédé selon l'une quelconque des revendications 5 précédentes lorsque ce programme est exécuté par un processeur. 10. Système d'identification biométrique (2) comprenant un dispositif client (3) et un dispositif de calcul distant (4) caractérisé en ce que : ledit dispositif client et ledit dispositif de calcul distant comprennent chacun un 10 processeur, une interface et une mémoire pour mettre en oeuvre les étapes du procédé d'identification selon l'une quelconque des revendications 1 à 8.