Brevet FR3043811A1 (20170519)
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.\n<CLM>\1\tProcé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.\n<CLM>\1\tProcé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é.\n<CLM>\1\tProcé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)\n<CLM>\1\t= 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\n<CLM>\1\tProcé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\n<CLM>\1\tEKFb1 = 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\n<CLM>\1\tProcé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é.\n<CLM>\1\tProcé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é.\n<CLM>\1\tProcé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.\n<CLM>\1\tProduit 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.\n<CLM>\1\tSystè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.