Identification method of an entity

Abstract

A biometric identification method of an entity including computation of a matching value between biometric data of an entity u and reference biometric data u, by application of a function F to the biometric data. A non-interactive, publicly verifiable computation method is performed wherein representation of the function is obtained by converting an arithmetic circuit into a polynomial representation. A matching value is obtained by evaluating the arithmetic circuit and the reference biometric data as inputs. Proof of correction of the computation execution of the matching values is obtained. Verification of said received proof. The function is encoded with an integer k>1 of a vector of a biometric datum on at least one input wire of the circuit. The function includes at least m scalar products. Evaluation of the circuit is iteratively computed depending on the value of m.

Claims

1. A biometric identification method of an entity, by a biometric identification system comprising a client device and a remote computation device, comprising: computation of at least one matching value between at least one biometric datum of the entity u and at least one reference biometric datum u, by application of a function F to said biometric data, each of said data being a vector of N binary integers u.sub.i or u.sub.i with 1iN, each integer being coded on n bits, said function F comprising a scalar product between a biometric datum of the entity and a reference biometric datum, said computation performing a non-interactive, publicly verifiable computation method comprising steps of: representation of said function F in form of an arithmetic circuit comprising wires transporting values of finite prime field .sub.q, with q a prime number, and connecting addition and multiplication operators, conversion of said arithmetic circuit into a polynomial representation, QAP (Quadratic Arithmetic Program) or multi-QAP, generation of a public evaluation key and of a public verification key as a function of said polynomial representation, obtaining by the remote computation device of the arithmetic circuit and of the public evaluation key, for each biometric datum of the entity, determination of at least one matching value between said biometric datum and at least one reference biometric datum by the remote computation device by evaluating the arithmetic circuit having as inputs the biometric datum of the entity and the reference biometric datum, for each determined matching value, generation by the remote computation device of a proof of correction of computation execution of matching value, so-called generated proof, from said polynomial representation, the public evaluation key and result of the evaluation of the arithmetic circuit, transmission by the remote computation device of matching values and generated proofs to the client device, verification of said generated proofs received by the client device by means of the public verification key, identification of the entity by the client device as the function of the matching values and result of said verification of the generated proofs, wherein: representation of said function F comprises encoding an integer k>1 of binary integers of a vector of a biometric datum on at least one input wire of the arithmetic circuit, and the function F comprising at least m scalar products, m being a divider of length N of biometric data vectors, if the divider m is equal to 2 or 3, the arithmetic circuit comprises at least N/(k*m) multiplication operators connected to input wires of the arithmetic circuit, a storage memory, and at least one addition operator, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by means of said N/(k*m) multiplication operators, storage of m results of computations of said scalar products in said storage memory and summation of said results by means of said addition operator, if the divider m is greater than or equal to 4, the arithmetic circuit comprises at least one first computation sub-circuit of the scalar product comprising N/(k*m) first multiplication operators connected to input wires of the arithmetic circuit and a first storage memory, and a second computation sub-circuit of the scalar product comprising N/(k*m) second multiplication operators connected to the input wires of the arithmetic circuit and a second storage memory, each one of said first and second computation sub-circuits being also connected to an output of the storage memory of the other one of said first and second computation sub-circuits, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by using alternatively one of said first and second computation sub-circuit to compute sum of the scalar product of values of the input wires of the used one of said first and second computation sub-circuits and value stored in the storage memory of the other one of said first and second computation sub-circuits, wherein said biometric identification method delegates to a remote entity a comparison of biometric datum in terms of a protocol of verifiable computations suitable for a real-time execution.

2. The identification method according to claim 1, wherein the verification of said received proofs comprises batch verification of pairings.

3. The identification method according to claim 1, wherein: if the divider m of the length N of the biometric data vectors is equal to 1, given an asymmetric bilinear environment (q, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e) where q is a prime number G.sub.1, G.sub.2 and G.sub.T three groups of order q, g.sub.1 a generator of G.sub.1, g.sub.2 a generator of G.sub.2, and e a non-degenerate bilinear pairing e: G.sub.1G.sub.2.fwdarw.G.sub.T and the arithmetic circuit being represented in form of a QAP of the circuit Q=(t, V, W, Y) of size and degree , with V={vi}, W={wi}, Y={yi}, 0i, and given I.sub.io={1, . . . , } set of indices corresponding to input/output wires of the arithmetic circuit and I.sub.mid={+1, . . . , } set of indices of intermediate wires of the arithmetic circuit not being input wires of the arithmetic circuit, the generation of the public evaluation key and of the public verification key comprises: generation of random variables r.sub.v, r.sub.w, s, .sub.v, .sub.w, .sub.y, , in .sub.q, definition of coefficients r.sub.y=r.sub.v.Math.r.sub.w, g.sub.v1=g.sub.1.sup.r.sup.v, g.sub.w1=g.sub.1.sup.r.sup.w, g.sub.w2=g.sub.2.sup.r.sup.w, g.sub.y1=g.sub.1.sup.r.sup.y and g.sub.y2=g.sub.2.sup.r.sup.y, generation of public evaluation key EK.sub.F equal to (EK.sub.F1, EK.sub.F2) where ${\mathrm{EK}}_{F1}=\left(\begin{array}{c}{\left\{g_{v1}^{v_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{w1}^{w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{y1}^{y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},\\ {\left\{g_{v1}^{{}_v.Math.v_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{w1}^{{}_w.Math.w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{y1}^{{}_y.Math.y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},\\ {\left\{g_1^{s^i}\right\}}_{i\left[1,\right]},{\left\{g_{v1}^{.Math.v_i\left(s\right)}.Math.g_{w1}^{.Math.w_i\left(s\right)}.Math.g_{y1}^{.Math.y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}}\end{array}\right)$ ${\mathrm{EK}}_{F2}=\left({\left\{g_{w2}^{w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}}\right)$ generation of public verification key VK.sub.F equal to (VK.sub.F1, VK.sub.F2) where:
VK.sub.F1=(g.sub.1,{g.sub.v1.sup.v.sup.i.sup.(s)}.sub.i[1,],{g.sub.y1.sup.y.sup.i.sup.(s)}.sub.i[1,])
VK.sub.F2=(g.sub.2,g.sub.2.sup..sup.v,g.sub.2.sup..sup.w,g.sub.2.sup..sup.y,g.sub.2.sup.,g.sub.2.sup..Math.,g.sub.y2.sup.t(s),{g.sub.w2.sup.w.sup.i.sup.(s)}.sub.i[1,]) generation by the remote computation device of the proof of correction of the computation execution of a matching value comprises, {c.sub.i}.sub.i[1,] being set of values of the arithmetic circuit determined during determination of the determined matching value: determination of a polynomial h(x) such that p(x)=h(x).Math.t(x) with p(x)=(v.sub.0(x)+.sub.i=1.sup.c.sub.i.Math.v.sub.i (x)).Math.(w.sub.0(x)+.sub.i=1.sup.c.sub.i.Math.w.sub.i(x))(y.sub.0(x)+.sub.i=1.sup.c.sub.i.Math.y.sub.i(x)), computation of generated proof =(.sub.1, .sub.2) with: ${}_1=\left(\begin{array}{c}{g}_{v1}^{v_{\mathrm{mid}}\left(s\right)},g_{w1}^{w_{\mathrm{mid}}\left(s\right)},g_{y1}^{y_{\mathrm{mid}}\left(s\right)},g_1^{h\left(s\right)},\\ g_{v1}^{{}_v.Math.v_{\mathrm{mid}}\left(s\right)},g_{w1}^{{}_w.Math.w_{\mathrm{mid}}\left(s\right)},g_{y1}^{{}_y.Math.y_{\mathrm{mid}}\left(s\right)},\\ g_{v1}^{.Math.v_{\mathrm{mid}}\left(s\right)}.Math.g_{w1}^{.Math.w_{\mathrm{mid}}\left(s\right)}.Math.g_{y1}^{.Math.y_{\mathrm{mid}}\left(s\right)}\end{array}\right),{}_2=\left(g_{w2}^{w_{\mathrm{mid}}\left(s\right)}\right)$ where:
v.sub.mid(x)=.sub.iI.sub.midc.sub.i.Math.v.sub.i(x),w.sub.mid(x)=.sub.iI.sub.midc.sub.i.Math.w.sub.i(x) and y.sub.mid(x)=.sub.iI.sub.midc.sub.i.Math.y.sub.i(x), and, wherein said proofs received by the client device being equal to (.sub.r1, .sub.r2) with .sub.r1 in form of: (g.sub.v1.sup.V.sup.mid, g.sub.w1.sup.W.sup.mid, g.sub.y1.sup.Y.sup.mid, g.sub.1.sup.H, g.sub.v1.sup.V.sup.mid, g.sub.w1.sup.W.sup.mid, g.sub.y1.sup.Y.sup.mid, g.sub.1.sup.Z) and .sub.r2 in the form g.sub.w2.sup.w.sup.mid, the verification of a received proof comprises performing following equality tests:
e(g.sub.v1.sup.v.sup.o.sup.(s).Math.g.sub.v1.sup.v.sup.io.sup.(s).Math.g.sub.v1.sup.V.sup.mid,g.sub.w2.sup.w.sup.o.sup.(s).Math.g.sub.w2.sup.w.sup.io.sup.(s).Math.g.sub.w2.sup.W.sup.mid)=e(g.sub.1.sup.H,g.sub.y2.sup.t(s)).Math.e(g.sub.y1.sup.y.sup.o.sup.(s).Math.g.sub.y1.sup.y.sup.io.sup.(s).Math.g.sub.y1.sup.Y.sup.mid,g.sub.2),
e((g.sub.v1.sup.V.sup.mid).sup.d.sup.1.Math.(g.sub.w1.sup.W.sup.mid).sup.d.sup.2.Math.(g.sub.y1.sup.Y.sup.mid).sup.d.sup.3,g.sub.2)=e((g.sub.v1.sup.V.sup.mid).sup.d.sup.1,g.sub.2.sup..sup.v).Math.e((g.sub.w1.sup.W.sup.mid).sup.d.sup.2,g.sub.2.sup..sup.w).Math.e((g.sub.y1.sup.Y.sup.mid).sup.d.sup.3,g.sub.2.sup..sup.y),e((g.sub.1.sup.Z,g.sub.2.sup.)=e(g.sub.v1.sup.V.sup.mid.Math.g.sub.w1.sup.W.sup.mid.Math.g.sub.y1.sup.Y.sup.mid,g.sub.2.sup..Math.) where g.sub.v1.sup.v.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.v1.sup.v.sup.i.sup.(s)).sup.c.sup.i, g.sub.w1.sup.w.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.w1.sup.w.sup.i.sup.(s)).sup.c.sup.i, and g.sub.y1.sup.y.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.y1.sup.y.sup.i.sup.(s)).sup.c.sup.i and (d.sub.1, d.sub.2, d.sub.3) elements of .sub.q on bits with a security parameter.

4. The identification method according to claim 1 wherein: if the divider m of the length N of the biometric data vectors is greater than or equal to 2, given an asymmetric bilinear environment (q, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e) where q is a prime number G.sub.1, G.sub.2 and G.sub.T three groups of order q, g.sub.1 a generator of G.sub.1, g.sub.2 a generator of G.sub.2, and e a non-degenerate bilinear pairing e: G.sub.1G.sub.2.fwdarw.G.sub.T, the arithmetic circuit being represented in form of a multi-QAP Q=({B.sub.b}.sub.b[1,l],t,V,W, of size and degree , with {B.sub.b}.sub.b[1,l] a set of l banks B.sub.b of Q used in the computation of the function F, and V={vi}, W={wi}, Y={yi} with 0i, the generation of the public evaluation key and of the public verification key comprises: generation of random variables s, {(.sub.bv, .sub.bw, .sub.by, .sub.b,.sub.b)}.sub.b[1,l], r.sub.v, r.sub.w in .sub.q, definition of following coefficients: r.sub.y=r.sub.y.Math.r.sub.w, g.sub.v1=g.sub.1.sup.r.sup.v, g.sub.v2=g.sub.2.sup.r.sup.v, g.sub.w1=g.sub.1.sup.r.sup.w, g.sub.w2=g.sub.2.sup.r.sup.w, g.sub.y1=g.sub.1.sup.r.sup.y and g.sub.y2=g.sub.2.sup.r.sup.y, generation of public evaluation key EK.sub.F equal to:
({EK.sub.Fb}.sub.b[1,l],{g.sub.1.sup.s.sup.i}.sub.i[1,],g.sub.v1.sup.t(s),g.sub.w1.sup.t(s),g.sub.y1.sup.t(s),g.sub.v2.sup.t(s),g.sub.w2.sup.t(s),g.sub.y2.sup.t(s)) where each public bank key EK.sub.Fb is equal to (EK.sub.Fb1, EK.sub.Fb2) with: ${\mathrm{EK}}_{\mathrm{Fb}1}=\left(\begin{array}{c}{\left\{\begin{array}{c}{g}_{v1}^{v_i\left(s\right)},g_{w1}^{w_i\left(s\right)},g_{y1}^{y_i\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v_i\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w_i\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y_i\left(s\right)},\\ g_{v1}^{{}_b.Math.v_i\left(s\right)}.Math.g_{w1}^{{}_b.Math.w_i\left(s\right)}.Math.g_{y1}^{{}_b.Math.y_i\left(s\right)}\end{array}\right\}}_{i{B}_b},\\ g_{v1}^{{}_{\mathrm{bv}}.Math.t\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.t\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.t\left(s\right)},g_{v1}^{{}_b.Math.t\left(s\right)},g_{w1}^{{}_b.Math.t\left(s\right)},g_{y1}^{{}_b.Math.t\left(s\right)}\end{array}\right)$
EK.sub.Fb2=({g.sub.w2.sup.w.sup.i.sup.(s)}.sub.iB.sub.b,g.sub.w2.sup..sup.bw.sup.,t(s)) generation of the public verification key VK.sub.F equal to: ({VK.sub.Fb}.sub.b[1,l], g.sub.1, g.sub.2, g.sub.y2.sup.t(s)) where each public bank key VK.sub.Fb is equal to (g.sub.2.sup..sup.bv, g.sub.2.sup..sup.bw, g.sub.2.sup..sup.by, g.sub.2.sup..sup.b, g.sub.2.sup..sup.b.sup..Math..sup.b), determination of a matching value comprises, function F being divided into sub-functions F.sub.1, . . . , F.sub. and =((f.sub.l, (T.sub.l1, . . . , T.sub.ll))).sub.l[1,L] being a scheduling of length L with .sub.l {1, . . . , }, evaluation of each sub-function F.sub. from the biometric data of the entity and the reference biometric data and determination of the values of the arithmetic circuit, generation by the remote computation device of the proof of correction of the computation execution of a matching value comprises, for each l={1, . . . , L}: for each bank B.sub.b such that b, with .Math.[1,l] set of indices b[1,l] such that T.sub.lb0,=U.sub.bB.sub.b, {c.sub.j}.sub.jB.sub.b an instance of bank B.sub.b, ={c.sub.i}.sub.i set of values of : generation of pledging random variables in .sub.q: o.sub.b=(o.sub.bv, o.sub.bw, o.sub.by), computation of a digest D.sub.b equal to (D.sub.b1,D.sub.b2) from the instance of the bank B.sub.b: B.sub.b.sup.(T.sup.lb.sup.)={c.sub.i}.sub.iB.sub.b and pledging random variables o.sub.b and such that: if the bank B.sub.b is an input/output bank:
D.sub.b1=(g.sub.v1.sup.v.sup.(b).sup.(s),g.sub.y1.sup.y.sup.(b).sup.(s)) and D.sub.b2=(g.sub.w2.sup.w.sup.(b).sup.(s)), if the bank B.sub.b is not input/output bank: $D_{b1}=\left(\begin{array}{c}{g}_{v1}^{v^{\left(b\right)}\left(s\right)},g_{w1}^{w^{\left(b\right)}\left(s\right)},g_{y1}^{y^{\left(b\right)}\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v^{\left(b\right)}\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w^{\left(b\right)}\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y^{\left(b\right)}\left(s\right)},\\ g_{v1}^{{}_b.Math.v^{\left(b\right)}\left(s\right)}.Math.g_{w1}^{{}_b.Math.w^{\left(b\right)}\left(s\right)}.Math.g_{y1}^{{}_b.Math.y^{\left(b\right)}\left(s\right)}\end{array}\right)$ $D_{b2}=\left(g_{w2}^{w^{\left(b\right)}\left(s\right)}\right)$
with:
v.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.v.sub.i(s)+o.sub.bv.Math.t(s),
w.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.w.sub.i(s)+o.sub.bw.Math.t(s),
y.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.y.sub.i(s)+o.sub.by.Math.t(s), determination of a polynomial h.sup.(l)(x) such that p.sup.(l)(x)=h.sup.(l)(x).Math.t(x) with p.sup.(l)(x)=(v.sub.0(x)+.sub.ic.sub.i.Math.v.sub.j(x)+.sub.bo.sub.bv.Math.t(x)).Math.(w.sub.0(x)+.sub.ic.sub.i.Math.w.sub.j(x)+.sub.bo.sub.bw.Math.t(x))(y.sub.0(x)+.sub.ic.sub.i.Math.y.sub.j(x)+.sub.bo.sub.by.Math.t(x)) computation of a proof element .sup.(l) equal to g.sub.1.sup.h.sup.(l).sup.(s), and, wherein said proofs received by the client device being of the form D.sub.1.sup.(1), . . . , D.sub.l.sup.(1), .sup.(1), . . . , D.sub.1.sup.(L), . . . , D.sub.l.sup.(L), .sup.(L) where for all l{1, . . . , L} and b{1, . . . ,l}: $D_b^{\left(l\right)}=\left(\left(g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_1^{Z_b^{\left(l\right)}}\right),\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)$ and .sup.(l)=g.sub.1.sup.H.sup.(l), verification of the received proof comprises: verification of L.Math.l digests, for l{1, . . . , L} and b{1, . . . , l} comprising performing following equality tests: $e\left(g_{v1}^{V_b^{\left(l\right)}},g_2^{{}_{\mathrm{bv}}}\right)=e\left(g_{v1}^{V_b^{\left(l\right)}},g_2\right)$ $e\left(g_{w1}^{W_b^{\left(l\right)}},g_2^{{}_{\mathrm{bw}}}\right)=e\left(g_{w1}^{W_b^{\left(l\right)}},g_2\right)$ $e\left(g_{y1}^{Y_b^{\left(l\right)}},g_2^{{}_{\mathrm{by}}}\right)=e\left(g_{y1}^{Y_b^{\left(l\right)}},g_2\right)$ $e\left(g_1^{Z_b^{\left(l\right)}},g_2^{{}_b}\right)=e\left(g_{v1}^{V_b^{\left(l\right)}}.Math.g_{w1}^{W_b^{\left(l\right)}}.Math.g_{y1}^{Y_b^{\left(l\right)}},g_2^{{}_b.Math.{}_b}\right)$ verification of L proofs comprising for l{1, . . . , L} performing following equality test: $e\left(\underset{b=1}{\overset{}{.Math.}}\left(g_{v1}^{V_b^{\left(l\right)}}\right),\underset{b=1}{\overset{}{.Math.}}\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)=e\left(g_1^{H^{\left(l\right)}},g_{y2}^{t\left(s\right)}\right).Math.e\left(\underset{b=1}{\overset{}{.Math.}}\left(g_{y1}^{Y_b^{\left(l\right)}}\right),g_2\right).$

5. The identification method according to claim 1 wherein: if the divider m of the length N of the biometric data vectors is greater than or equal to 2, given an asymmetric bilinear environment (q, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e) where q is a prime number G.sub.1, G.sub.2 and G.sub.T three groups of order q, g.sub.1 a generator of G.sub.1, g.sub.2 a generator of G.sub.2, and e a non-degenerate bilinear pairing e: G.sub.1G.sub.2.fwdarw.G.sub.T, the arithmetic circuit being represented in form of a multi-QAP Q=({B.sub.b}.sub.b[1,l], t, V, W, of size and degree , with {B.sub.b}.sub.b[1,l] a set of l banks B.sub.b of Q used in computation of the function F, and V={vi}, W={wi}, Y={yi} with 0i, the generation of the public evaluation key and the public verification key comprises: generation of random variables s,{(.sub.bv,.sub.bw,.sub.by, .sub.b, .sub.b)}.sub.b[1,l], r.sub.v, r.sub.w in .sub.q, generation of random variables s,{(.sub.bv, .sub.bw, .sub.by, .sub.b, .sub.b)}.sub.b[1,l], r.sub.v, r.sub.w in .sub.q, definition of the following coefficients: r.sub.y=r.sub.b.Math.r.sub.w, g.sub.v1=g.sub.1.sup.r.sup.v, g.sub.v2=g.sub.2.sup.r.sup.v, g.sub.w1=g.sub.1.sup.r.sup.w, g.sub.w2.sup.r.sup.w=g.sub.2.sup.r.sup.w, g.sub.y1=g.sub.1.sup.r.sup.y and g.sub.y2=g.sub.2.sup.r.sup.y, generation of the public evaluation key EK.sub.F equal to:
({EK.sub.Fb}.sub.b[1,l],{g.sub.1.sup.s.sup.i}.sub.i[1,],g.sub.v1.sup.t(s),g.sub.w1.sup.t(s),g.sub.y1.sup.t(s),g.sub.v2.sup.t(s),g.sub.w2.sup.t(s),g.sub.y2.sup.t(s)) where each public bank key EK.sub.Fb is equal to (EK.sub.Fb1, EK.sub.Fb2) with: ${\mathrm{EK}}_{\mathrm{Fb}1}=\left(\begin{array}{c}{\left\{\begin{array}{c}{g}_{v1}^{v_i\left(s\right)},g_{w1}^{w_i\left(s\right)},g_{y1}^{y_i\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v_i\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w_i\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y_i\left(s\right)},\\ g_{v1}^{{}_b.Math.v_i\left(s\right)}.Math.g_{w1}^{{}_b.Math.w_i\left(s\right)}.Math.g_{y1}^{{}_b.Math.y_i\left(s\right)}\end{array}\right\}}_{i{B}_b},\\ g_{v1}^{{}_{\mathrm{bv}}.Math.t\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.t\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.t\left(s\right)},g_{v1}^{{}_b.Math.t\left(s\right)},g_{w1}^{{}_b.Math.t\left(s\right)},g_{y1}^{{}_b.Math.t\left(s\right)}\end{array}\right)$ ${\mathrm{EK}}_{\mathrm{Fb}2}=\left({\left\{g_{w2}^{w_i\left(s\right)}\right\}}_{i{B}_b},g_{w2}^{{}_{\mathrm{bw}}.Math.t\left(s\right)}\right)$ generation of the public verification key VK.sub.F is equal to: ({VK.sub.Fb}.sub.b[1,l], g.sub.1, g.sub.2, g.sub.y2.sup.t(s)) where each public bank key VK.sub.Fb is equal to (g.sub.2.sup..sup.bv, g.sub.2.sup..sup.bw, g.sub.2.sup..sup.by, g.sub.2.sup..sup.b, g.sub.2.sup..sup.b.sup..Math..sup.b), determination of the matching value comprises, function F being divided into sub-functions F.sub.1, . . . , F.sub. and =((f.sub.l, (T.sub.l1, . . . , T.sub.ll))).sub.l[1,L] being a scheduling of length L with .sub.l {1, . . . , }, evaluation of each sub-function F.sub. from the biometric data of the entity and the reference biometric data and determination of the determined values of the arithmetic circuit, generation by the remote computation device of the proof of correction of the computation execution of the matching value comprises, for each l={1, . . . , L}: for each bank B.sub.b such that b, with .Math.[1,l] the set of indices b[1,l] such that T.sub.lb0,=U.sub.bB.sub.b, {c.sub.j}.sub.jB.sub.b an instance of the bank B.sub.b, ={c.sub.i}.sub.i the set of values of : generation of pledging random variables in .sub.q: o.sub.b=(o.sub.bv, o.sub.bw, o.sub.by), computation of a digest D.sub.b equal to (D.sub.b1,D.sub.b2) from the instance of the bank B.sub.b: B.sub.b.sup.(T.sup.lb.sup.)={c.sub.i}.sub.iB.sub.b and pledging random variables o.sub.b and such that: if the bank B.sub.b is input/output bank:
D.sub.b1=(g.sub.v1.sup.v.sup.(b).sup.(s),g.sub.y1.sup.y.sup.(b).sup.(s)) and D.sub.b2=(g.sub.w2.sup.w.sup.(b).sup.(s)), if the bank B.sub.b is not the input/output bank: $D_{b1}=\left(\begin{array}{c}{g}_{v1}^{v^{\left(b\right)}\left(s\right)},g_{w1}^{w^{\left(b\right)}\left(s\right)},g_{y1}^{y^{\left(b\right)}\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v^{\left(b\right)}\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w^{\left(b\right)}\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y^{\left(b\right)}\left(s\right)},\\ g_{v1}^{{}_b.Math.v^{\left(b\right)}\left(s\right)}.Math.g_{w1}^{{}_b.Math.w^{\left(b\right)}\left(s\right)}.Math.g_{y1}^{{}_b.Math.y^{\left(b\right)}\left(s\right)}\end{array}\right)$ $D_{b2}=\left(g_{w2}^{w^{\left(b\right)}\left(s\right)}\right)$
with:
v.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.v.sub.i(s)+o.sub.bv.Math.t(s),
w.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.w.sub.i(s)+o.sub.bw.Math.t(s),
y.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.y.sub.i(s)+o.sub.by.Math.t(s), determination of a polynomial h.sup.(l)(x) such that p.sup.(l)(x)=h.sup.(l)(x).Math.t(x) with p.sup.(l)(x)=(v.sub.0(x)+.sub.ic.sub.i.Math.v.sub.j(x)+.sub.bo.sub.bv.Math.t(x)).Math.(w.sub.0(x)+.sub.ic.sub.i.Math.w.sub.j(x)+.sub.bo.sub.bw.Math.t(x))(y.sub.0(x)+.sub.ic.sub.i.Math.y.sub.j(x)+.sub.bo.sub.by.Math.t(x)) computation of the proof element .sup.(l) equal to g.sub.1.sup.h.sup.(l).sup.(s), and, wherein said proofs received by the client device being of form D.sub.1.sup.(1), . . . , D.sub.l.sup.(1), .sup.(1), . . . , D.sub.1.sup.(L), . . . , D.sub.l.sup.(L), .sup.(L) where for all l{1, . . . , L} and b{1, . . . ,l}: $D_b^{\left(l\right)}=\left(\left(g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_1^{Z_b^{\left(l\right)}}\right),\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)$ and .sup.(l)=g.sub.1.sup.H.sup.(l), verification of the received proof comprises, given a correction parameter : selection of a random vector (d.sub.1, . . . , d.sub.3.Math.l) of elements of size , batch verification of L.Math.l digests comprising performing l times the following equality tests, for b{1, . . . , l}: $e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l},g_2^{{}_{\mathrm{bv}}}\right).Math.e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{w1}^{W_b^{\left(l\right)}}\right)}^{d_{L+l}},g_2^{{}_{\mathrm{bw}}}\right).Math.e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_{2.Math.L+l}},g_2^{{}_{\mathrm{by}}}\right)=e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l}.Math.\underset{l=1}{\overset{L}{.Math.}}{\left(g_{w1}^{W_b^{\left(l\right)}}\right)}^{d_{L+1}}.Math.\underset{l=1}{\overset{L}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_{2.Math.L+l}},g_2\right)$ $e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_1^{Z_b^{\left(l\right)}}\right)}^{d_l},g_2^{{}_b}\right)=e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}.Math.g_{w1}^{W_b^{\left(l\right)}}.Math.g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_l},g_2^{{}_b.Math.{}_b}\right)$ batch verification of the L proofs comprising performing the following equality test: $\underset{l=1}{\overset{L}{.Math.}}e\left(\underset{b=1}{\overset{}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l},\underset{b=1}{\overset{}{.Math.}}\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)=e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_1^{H^{\left(l\right)}}\right)}^{d_l},g_{y2}^{t\left(s\right)}\right).Math.e\left(\underset{l=1}{\overset{L}{.Math.}}\underset{b=1}{\overset{}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_l},g_2\right).$

6. The identification method according to claim 1, wherein the identification of the entity comprises comparison of the matching values with a predetermined threshold.

7. The identification method according to claim 1, wherein the function F comprises comparison of result of the scalar product between said biometric data of the entity and said reference biometric data with a predetermined threshold.

8. The identification method according to claim 1, wherein the encoding of k binary integers u.sub.i or u.sub.i on an input wire of an j.sup.th multiplication operator, 1jN/k, is equal to $E_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u\right)\mathrm{or}{E}_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u^{}\right)$ with 1zm, and is given by the formula: $E_k^{\left(\left(j-1\right)k+1\right)}\left(x\right)=\underset{i=1}{\overset{k}{.Math.}}{2}^{{\mathrm{.Math.}}_i}.Math.x_{\left(j-1\right)k+i}=2^{{\mathrm{.Math.}}_1}.Math.x_{\left(j-1\right)k+1}+\mathrm{.Math.}+2^{{\mathrm{.Math.}}_k}.Math.x_{\left(j-1\right)k+k}$ with .sub.1, . . . , .sub.k predetermined integers.

9. A computer program product comprising code instructions for execution of a method according to a biometric identification method of an entity, by a biometric identification system comprising a client device and a remote computation device, comprising: computation of at least one matching value between at least one biometric datum of the entity u and at least one reference biometric datum u, by application of a function F to said biometric data, each of said data being a vector of N binary integers u.sub.i or u.sub.i with 1iN, each integer being coded on n bits, said function F comprising a scalar product between a biometric datum of the entity and a reference biometric datum, said computation performing a non-interactive, publicly verifiable computation method comprising steps of: representation of said function F in form of an arithmetic circuit comprising wires transporting values of finite prime field .sub.q, with q a prime number, and connecting addition and multiplication operators, conversion of said arithmetic circuit into a polynomial representation, QAP (Quadratic Arithmetic Program) or multi-QAP, generation of a public evaluation key and of a public verification key as a function of said polynomial representation, obtaining by the remote computation device of the arithmetic circuit and of the public evaluation key, for each biometric datum of the entity, determination of at least one matching value between said biometric datum and at least one reference biometric datum by the remote computation device by evaluating the arithmetic circuit having as inputs the biometric datum of the entity and the reference biometric datum, for each determined matching value, generation by the remote computation device of a proof of correction of computation execution of matching value, so-called generated proof, from said polynomial representation, the public evaluation key and result of the evaluation of the arithmetic circuit, transmission by the remote computation device of matching values and generated proofs to the client device, verification of said generated proofs received by the client device by means of the public verification key, identification of the entity by the client device as the function of the matching values and result of said verification of the generated proofs, wherein: representation of said function F comprises encoding an integer k>1 of binary integers of a vector of a biometric datum on at least one input wire of the arithmetic circuit, and the function F comprising at least m scalar products, m being a divider of length N of biometric data vectors, if the divider m is equal to 2 or 3, the arithmetic circuit comprises at least N/(k*m) multiplication operators connected to the input wires of the arithmetic circuit, a storage memory, and at least one addition operator, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by means of said N/(k*m) multiplication operators, storage of m results of computations of said scalar products in said storage memory and summation of said results by means of said addition operator, if the divider m is greater than or equal to 4, the arithmetic circuit comprises at least one first computation sub-circuit of the scalar product comprising N/(k*m) first multiplication operators connected to input wires of the arithmetic circuit and a first storage memory, and a second computation sub-circuit of the scalar product comprising N/(k*m) second multiplication operators connected to the input wires of the arithmetic circuit and a second storage memory, each one of said first and second computation sub-circuits being also connected to an output of the storage memory of the other one of said first and second computation sub-circuits, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by using alternatively one of said first and second computation sub-circuit to compute sum of the scalar product of values of the input wires of the used one of said first and second computation sub-circuits and value stored in the storage memory of the other one of said first and second computation sub-circuits, wherein said biometric identification method delegates to a remote entity a comparison of biometric datum in terms of a protocol of verifiable computations suitable for a real-time execution, when said computer program product is executed by a processor.

10. A biometric identification system comprising a client device and a remote computation device wherein: said client device and said remote computation device each comprise a processor, an interface and a memory for performing steps of an identification method according to a biometric identification method of an entity, by a biometric identification system comprising a client device and a remote computation device, comprising: computation of at least one matching value between at least one biometric datum of the entity u and at least one reference biometric datum u, by application of a function F to said biometric data, each of said data being a vector of N binary integers u.sub.i or u.sub.i with 1iN, each integer being coded on n bits, said function F comprising a scalar product between a biometric datum of the entity and a reference biometric datum, said computation performing a non-interactive, publicly verifiable computation method comprising steps of: representation of said function F in form of an arithmetic circuit comprising wires transporting values of the finite prime field .sub.q, with q a prime number, and connecting addition and multiplication operators, conversion of said arithmetic circuit into a polynomial representation, QAP (Quadratic Arithmetic Program) or multi-QAP, generation of a public evaluation key and of a public verification key as a function of said polynomial representation, obtaining by the remote computation device of the arithmetic circuit and of the public evaluation key, for each biometric datum of the entity, determination of at least one matching value between said biometric datum and at least one reference biometric datum by the remote computation device by evaluating the arithmetic circuit having as inputs the biometric datum of the entity and the reference biometric datum, for each determined matching value, generation by the remote computation device of a proof of correction of computation execution of matching value, so-called generated proof, from said polynomial representation, the public evaluation key and result of the evaluation of the arithmetic circuit, transmission by the remote computation device of matching values and generated proofs to the client device, verification of said generated proofs received by the client device by means of the public verification key, identification of the entity by the client device as the function of the matching values and result of said verification of the generated proofs, wherein: representation of said function F comprises encoding an integer k>1 of binary integers of a vector of a biometric datum on at least one input wire of the arithmetic circuit, and the function F comprising at least m scalar products, m being a divider of length N of biometric data vectors, if the divider m is equal to 2 or 3, the arithmetic circuit comprises at least N/(k*m) multiplication operators connected to input wires of the arithmetic circuit, a storage memory, and at least one addition operator, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by means of said N/(k*m) multiplication operators, storage of m results of computations of said scalar products in said storage memory and summation of said results by means of said addition operator, if the divider m is greater than or equal to 4, the arithmetic circuit comprises at least one first computation sub-circuit of the scalar product comprising N/(k*m) first multiplication operators connected to input wires of the arithmetic circuit and a first storage memory, and a second computation sub-circuit of the scalar product comprising N/(k*m) second multiplication operators connected to the input wires of the arithmetic circuit and a second storage memory, each one of said first and second computation sub-circuits being also connected to an output of the storage memory of the other one of said first and second computation sub-circuits, and evaluation of the arithmetic circuit iteratively comprises computation of each of the m scalar products by using alternatively one of said first and second computation sub-circuit to compute sum of the scalar product of values of the input wires of the used one of said first and second computation sub-circuits and value stored in the storage memory of the other one of said first and second computation sub-circuits, wherein said biometric identification method delegates to a remote entity a comparison of biometric datum in terms of a protocol of verifiable computations suitable for a real-time execution.

Description

PRESENTATION OF THE FIGURES

(1) Other characteristics and advantages of the present invention will emerge from the following description of a preferred embodiment. This description will be given in reference to the appended drawings, in which:

(2) FIG. 1 illustrates an arithmetic circuit corresponding to naive implementation of a scalar product for biometric identification of an entity;

(3) FIG. 2 illustrates an identification system according to an embodiment of the invention;

(4) FIG. 3 is a diagram showing an implementation of an identification method according to the invention;

(5) FIGS. 4a and 4b illustrate an arithmetic circuit for biometric identification of an entity according to a first mode of operation of the invention;

(6) FIGS. 5a and 5b illustrate an example implementation of the circuit of FIG. 4 for N=3000, n=8, q=256, k=3;

(7) FIGS. 6a to 6c illustrate a arithmetic circuit for biometric identification of an entity according to a second mode of operation of the invention;

(8) FIGS. 7a and 7b illustrate an arithmetic circuit for biometric identification of an entity according to a third mode of operation of the invention;

DETAILED DESCRIPTION

(9) The present invention relates to implementing a biometric identification method of an entity 1 by an identification system 2 comprising a client device 3 and a remote computation device 4 capable of being connected together by a communications network 5, as represented in FIG. 2. Such an entity can be an individual or else an object having biometric data such as a biometric passport.

(10) The client device and the remote computation device can each comprise a random access memory and internal storage means such as rewritable non-volatile memory (flash memory or EEPROM memory) and processing means comprising a processor. They can also comprise an interface for dialoguing with each other, of wired type such as an Ethernet link, or wireless such as a Wifi or Bluetooth connection.

(11) The aim of this method carried out is to allow the device to delegate to the remote computation device the computations necessary for biometric identification of the entity to be identified, so that the computations made by the remote computation device are publicly verifiable, all this happening over a sufficiently short period to be acceptable in terms of an identification method.

(12) For conducting such biometric identification the client device acquires at least one biometric datum of the entity to be identified u. To identify the entity, this at least one biometric datum u must be compared to one or more reference biometric data u, stored in advance.

(13) By way of example, such biometric data can be fingerprints, DNA, voice or even iris images or venous networks. Each of these biometric data is a vector of N binary integers u.sub.i or u.sub.i with 1iN. Each integer u.sub.i or u.sub.i is coded on n bits. For example in the case of a face biometric datum, there can typically be N=3000 and n=8.

(14) The client device can comprise or be connected to a device for capturing such biometric data, such as a fingerprint reader, a microphone, or an iris-imaging device. This capture device can be employed to acquire the biometric datum u acquired for the entity 1. The reference biometric data u can be stored in the storage means of the client device or of the remote computation device.

(15) The identification method can comprise the steps described hereinbelow in reference to FIG. 3.

(16) First of all at least one matching value can be computed F1 between at least one biometric datum of the entity u and at least one reference biometric datum u, by application of a function F, so-called correlation function, to said biometric data. Function F comprises a scalar product between a biometric datum of the entity and a reference biometric datum. Such a scalar product in fact computes a score S=.sub.j=1.sup.N(u.sub.j.Math.u.sub.j) which is all the higher since the data compared are similar. Such a score can be used as matching value. To determine if an attempt at identification has succeeded, the matching values can be compared to a predetermined threshold T. Alternatively, function F can comprise the comparison of the result of the scalar product between the biometric data of the entity u and the reference biometric data u, i.e. of the score S, to this predetermined threshold T. Computation of the matching value can comprise computation of the value (ST) and the matching value coming from such computation can be a sign bit for example taking the value 1 if ST>0, the value 0 if not.

(17) To ensure the quality of the result obtained, computation of such a matching value F1 employs a non-interactive, publicly verifiable computation method. Such a method generally being divided into three phases: representation of the function F to be evaluated in the form of a system constraints represented in the form of an arithmetic circuit. transformation of this arithmetic circuit into polynomial representation called Quadratic Arithmetic Programs (abbreviated to QAP below). generation of a proof of correction of the computation execution from the QAP.

(18) The non-interactive, publicly verifiable computation method carried out more precisely first comprises a representation step E1 of said function F in the form of an arithmetic circuit. Such an arithmetic circuit comprises wires transporting values of the finite prime field Zq, with q a prime number, and connecting addition and multiplication operators. Typically the size q of the values of the circuit wires can be equal to 256 bits.

(19) The arithmetic circuit is then converted E2 into a polynomial representation, QAP (Quadratic Arithmetic Program) or multi-QAP. Such representations and the way to attain them from an arithmetic circuit are described in more detail in the publications cited hereinabove on the existing Pinocchio and Geppetto protocols.

(20) Next a public evaluation key and a public verification key are generated E3 as a function of said polynomial representation. The remote computation device then obtains E4 the arithmetic circuit and the public evaluation key.

(21) The representation steps in the form of an arithmetic circuit E1, conversion into a polynomial representation E2 and generation of keys E3 can be conducted by the client device itself. Alternatively these steps can be delegated to a trusted third party. Since such steps are independent of the value of the biometric data to be compared, they can be conducted once only, prior to comparisons of biometric data described hereinbelow, and do not need to be repeated as long as the format of the biometric data to be compared does not change.

(22) For each biometric datum of the entity at least one matching value between said biometric datum and at least one reference biometric datum is then determined E5 by the remote computation device by evaluating the arithmetic circuit with the biometric data of the entity and the reference biometric datum as inputs.

(23) For each determined matching value the remote computation device generates E6 a proof of correction of the computation execution of the matching value, so-called generated proof, from said polynomial representation, the public evaluation key and the result of evaluation of the arithmetic circuit. It then transmits E7 the matching values and said generated proofs to the client device.

(24) The latter verifies E8 the received proof by means of the public verification key. The verification step of said received proofs E8 can comprise or not batch verification of pairings.

(25) Finally the entity is identified F2 by the client device as a function of the matching values and the result of said verification of proofs.

(26) The integers u.sub.i and u.sub.i constituting the data of the entity and the reference data are usually encoded on a number of bits n far less than the size q of the values of wires of the circuit. By way of example the number of bits n can be equal to 8 bits and the size q can be equal to 256 bits. To limit the number of multipliers necessary for representation of the function F in the form of an arithmetic circuit, several integers u respectively u.sub.i are encoded on each input wire of the arithmetic circuit. Representation of said function E1 comprises encoding an integer k>1 of binary integers of a vector of a biometric datum on at least one input wire of the circuit. In practice, encoding E.sub.k.sup.((j1)k+1)(u) or E.sub.k.sup.((j1)k+1)(u) of k binary integers u.sub.i or u.sub.i on an input wire of a j.sup.th multiplication operator, 1jN/k, can be defined by the formula:

(27) $E_k^{\left(\left(j-1\right)k+1\right)}\left(x\right)=\underset{i=1}{\overset{k}{.Math.}}{2}^{{\mathrm{.Math.}}_i}.Math.x_{\left(j-1\right)k+i}=2^{{\mathrm{.Math.}}_1}.Math.x_{\left(j-1\right)k+1}+\mathrm{.Math.}+2^{{\mathrm{.Math.}}_k}.Math.x_{\left(j-1\right)k+k}$
with .sub.1, . . . , .sub.k predetermined integers.)

(28) A multiplier having on input E.sub.k.sup.((j1)k+1)(u) and E.sub.k.sup.((j1)k+1)(u) has on its output wire the product of encodings of successive k binary integers u.sub.i or u.sub.i coded on its input wires. This product is noted E.sub.u.Math.u,k.sup.((j1)k+1)=E.sub.k.sup.((j1)k+1)(u). E.sub.k.sup.((j1)k+1)(u). By way of example, for j=1, there is: E.sub.u.Math.u,k.sup.(1)=2.sup.2.Math..sup.1.Math.u.sub.1.Math.u.sub.1+2.sup..sup.2.Math.(u.sub.1.Math.u.sub.2+u.sub.2.Math.u.sub.1)+2.sup.2.Math..sup.2.Math.u.sub.2.Math.u.sub.2+ . . . +2.sup.2.Math..sup.k.Math.u.sub.k.Math.u.sub.k

(29) To further reduce the number of multipliers of the arithmetic circuit, the method as carried out also proposes splitting computation of the scalar product of the biometric datum of the entity u and of the reference biometric datum u of lengths N into several computations of scalar products of vectors of lesser size coming from splitting of the vectors u and u. The combination of the results of these scalar products produces the score S corresponding to the result of the scalar product of u and u.

(30) For this, function F comprising at least m scalar products, function F can be decomposed into at least m occurrences of sub-functions, m being a divider m of the length N of the biometric data vectors. Only the split sub-functions are represented by their own sub-circuit in the arithmetic circuit, reducing the number of multipliers of the circuit. To combine decomposition of the scalar product of u and u into m scalar sub-products, and coding of k integers on each input wire of the circuit, it is possible to select k such that k divides m. The scalar product of u and u can be decomposed into m scalar sub-products of vectors of length N/km. The sum of the results of these m scalar products produces an encoded score {tilde over (S)} defined by the following formula:

(31) $\begin{array}{c}\tilde{S}=\underset{j=1}{\overset{N/k}{.Math.}}{E}_{u.Math.u^{},k}^{\left(\left(j-1\right)k+1\right)}\\ =\underset{j=1}{\overset{N/k}{.Math.}}\left(\begin{array}{c}{2}^{2.Math.{\mathrm{.Math.}}_1}.Math.\left(u_{\left(j-1\right)k+1}.Math.u_{\left(j-1\right)k+1}^{}\right)+\\ 2^{{\mathrm{.Math.}}_2}.Math.\left(\mathrm{.Math.}\right)+\mathrm{.Math.}+2^{2.Math.{\mathrm{.Math.}}_k}.Math.\left(u_{\mathrm{jk}}.Math.u_{\mathrm{jk}}^{}\right)\end{array}\right)\end{array}$
and of the following form if the expression hereinabove is deployed and if the terms are gathered by power of 2: {tilde over (S)}=2.sup.2.Math..sup.1.Math.a.sub.1+2.sup.2.Math..sup.2.Math.a.sub.2+2.sup.2.Math..sup.2.Math.a.sub.2+2.sup.2.Math..sup.3.Math.a.sub.3+ . . . +2.sup.2.Math..sup.k.Math.a.sub.k with a.sub.i the terms at 2.sup.2.Math..sup.i gathering the products of integers u.sub.i and u.sub.i of the same indices useful for computing the scalar product and u and u, and with a.sub.i the terms at 2.sup..sup.2, . . . , 2.sup..sup.k gathering the remaining products, cross products of integers u.sub.i and u.sub.j of different indices not useful for computation of the scalar product of u and u.

(32) To extract the score S from its encoded version {tilde over (S)}, it is possible to extract the k sub-terms corresponding to the coefficients 2.sup.2.Math..sup.1, . . . , 2.sup.2.Math..sup.k (i.e., the elements a.sub.1, a.sub.2, . . . , a.sub.k), then add them.

(33) The paragraphs hereinbelow present the specific features of the method for different ranges of value of the divider m. m can be determined by making a compromise between the computational powers of the client device and the remote computation device as well especially as memories.

(34) In a first mode of operation in which the divider m is equal to 1, function F can be put in the form of the circuit represented in FIGS. 4a and 4b. Such a circuit comprises N/k input multipliers each taking on input E.sub.k.sup.((j1)k+1)(u) and E.sub.k.sup.((j1)k+1)(u) with 1jN/k. In FIGS. 4a and 4b these multipliers are noted r.sub.j and the input wires are numbered from 1 to 2N/k. The N/k output wires of the multipliers carry the values E.sub.u.Math.u,k.sup.((j1)k+i) whereof the sum is equal to the encoded score {tilde over (S)} described hereinabove. The circuit comprises an additional output multiplier, numbered r.sub.N/k+1, necessary for conversion of the circuit in the form of QAP. This multiplier multiplies the output of the scalar product by 1 so as not to modify the encoded score {tilde over (S)}. Finally, a split gate is employed to extract the coefficients a.sub.i with 1ik corresponding to the terms of the scalar product u.Math.u. The summation of these terms first split from the encoded score then reconstituted by multiplication by powers of two and added produces the score S. FIGS. 4a and 4b correspond to an execution in which the score is compared to the predetermined threshold T. The value (ST) is computed and provided on input with a second split gate to extract the sign bit indicating the result of the comparison. More precisely, hereinbelow split gate means an arithmetic gate which splits an integer bit by bit. Given an integer a.sub.q, as is known to keep on bits, the split gate contains an input wire (containing the integer a) and output wires. In terms of elementary arithmetic constraints, its definition is given for example in the cited article Pinocchio, paragraph 3.2. It is recalled here by way of indication. It is clear that c.sub.0 is the input wire and c.sub.1, . . . , c.sub. the output wires. The arithmetic circuit of the gate so-called split gate is defined as follows: concatenation of the bits on output is equal to the input

(35) $\underset{i=1}{\overset{}{.Math.}}{2}^{j-1}.Math.c_j=c_0$ each output wire contains a Boolean value (0 or 1):
i{1, . . . ,}:c.sub.j.Math.(1c.sub.j)=0
When a split gate gate is used within a circuit, the integer is determined as an achieved upper limit given the size of the circuit inputs and all the arithmetic gates located between the inputs and the split gate.

(36) An example of implementation is represented in FIGS. 5a and 5b for N=3000, n=8, q=256, k=3. In such an mode of operation, the following values can be used for the parameters .sub.i:.sub.1=0, .sub.2=26, .sub.3=78.

(37) In a second mode of operation in which the divider m is equal to 2 or 3, function F can be decomposed into a function F1 computing a scalar sub-product between two vectors of size N/km, to be used m times, and a function F2 computing the sum of m values, corresponding to a coded score, and performing extraction of the corresponding score equal to the preferred scalar product.

(38) As represented in FIGS. 6a to 6c, the corresponding circuit comprises at least N/km multiplication operators connected to the input wires of the circuit, a storage memory, and at least one addition operator, and evaluation of the circuit iteratively comprises computation of each of the m scalar products by means of said N/km multiplication operators, storage of the m results of computations of said scalar products in said storage memory and summation of said results by means of said addition operator.

(39) With F.sub.1 and F.sub.2 defined as such, evaluation of function F corresponds to m applications of function F.sub.1 followed by application of function F.sub.2. The circuit represented in FIGS. 6a to 6c comprises N/km input multipliers each taking on input, during the iteration z of the function F1,

(40) $E_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u\right)$$\mathrm{and}$$E_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u^{}\right)$
with 1jN/km. In FIGS. 6a to 6c these multipliers are noted r.sub.j and the input wires are numbered from 1 to 2 N/km.

(41) The m applications of function F.sub.1 compute the coded sub-scores {tilde over (S)}.sub.z, for z{1, . . . , m}:

(42) ${\tilde{S}}_z=\underset{j=1}{\overset{N/k.Math.m}{.Math.}}{E}_{u.Math.u^{},k}^{\left(\left(z-1\right).Math.\left(N/m\right)+\left(j-1\right).Math.k+1\right)}$

(43) By way of example, for z=1, there is:

(44) 0$\begin{array}{c}{\tilde{S}}_1=\underset{j=1}{\overset{N/k.Math.m}{.Math.}}{E}_{u.Math.u^{},k}^{\left(\left(j-1\right)k+1\right)}\\ =\underset{j=1}{\overset{N/k.Math.m}{.Math.}}\left(\begin{array}{c}{2}^{2.Math.{\mathrm{.Math.}}_1}.Math.\left(u_{\left(j-1\right)k+1}.Math.u_{\left(j-1\right)k+1}^{}\right)+\\ 2^{{\mathrm{.Math.}}_2}.Math.\left(\mathrm{.Math.}\right)+\mathrm{.Math.}+2^{2.Math.{\mathrm{.Math.}}_k}.Math.\left(u_{\mathrm{jk}}.Math.u_{\mathrm{jk}}^{}\right)\end{array}\right)\end{array}$

(45) During the iteration z the N/km output wires of the multipliers thus carry the values

(46) $E_{u.Math.u^{},k}^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}$
whereof the sum is equal to the encoded score {tilde over (S)}.sub.z described hereinabove. The circuit comprises an additional output multiplier, numbered r.sub.N/km+1, necessary for conversion of the circuit into the form of QAP. The m coded sub-scores {tilde over (S)}.sub.z noted {tilde over (S)}.sub.z.sup.(out) in FIGS. 6a to 6c are stored in the storage memory corresponding to the m bus (Bus Bank) of the verifiable computation method. Evaluation of function F2, with on input the m values coming from the buses, noted {tilde over (S)}.sub.z.sup.(in) in FIGS. 6a to 6c, produces the coded score S described hereinabove.

(47) As in the case of the circuit in FIGS. 4a and 4b, a first split gate recovers the terms a.sub.i with 1ik corresponding to the terms of the scalar product u.Math.u. The summation of these terms produces the score S which is then compared to the predetermined threshold T.

(48) According to a variant not represented, function F1 can comprise decoding of the coded sub-score {tilde over (S)}.sub.z obtained during its evaluation into a sub-score S.sub.z. Such decoding can be done similarly to the decoding of the coded score {tilde over (S)} presented hereinabove. Function F2 comprises only the summation of the sub-scores S.sub.z to obtain the score S corresponding to the scalar product u.Math.u, according to the formula:

(49) $\begin{array}{c}\underset{z=1}{\overset{m}{.Math.}}{S}_z=\underset{z=1}{\overset{m}{.Math.}}\left(\underset{j=1}{\overset{N/\mathrm{km}}{.Math.}}\left(\underset{i=1}{\overset{k}{.Math.}}{u}_{\left(z-1\right).Math.\left(N/m\right)+\left(j-1\right).Math.k+i}.Math.u_{\left(z-1\right).Math.\left(N/m\right)+\left(j-1\right).Math.k+i}^{}\right)\right)\\ =\underset{z=1}{\overset{N}{.Math.}}{u}_z.Math.u_z^{}\\ =.Math.u,u^{}.Math.\\ =S\end{array}$

(50) In a third mode of operation in which the divider m is greater than or equal to 4, it is possible to decompose function F into a function F.sub.1 and a function F.sub.2, alternatively use and m times the total, which each take on input two vectors of size N/km and a sub-score, and on output return an updated sub-score defined as the sum of the sub-score given on input with the result of the scalar product of the vectors provided on input; and a function F.sub.3 which decodes a coded score {tilde over (S)} into a score S.

(51) As represented in FIGS. 7a and 7b, the circuit comprises at least one first computation sub-circuit of scalar product comprising N/km first multiplication operators connected to the input wires of the circuit, for evaluation of function F1 for z odd, and a first storage memory, and a second computation sub-circuit of scalar product comprising N/km second multiplication operators connected to the input wires of the circuit, for evaluation of function F2 for z even, and a second storage memory, each of said sub-circuit being also connected to an output of the storage memory of the other sub-circuit, and evaluation of the circuit iteratively comprises computation of each of the m scalar products by using alternatively the first or the second sub-circuit to compute the sum of the scalar product of the values of the input wires of this sub-circuit and of the value stored in the storage memory of the other sub-circuit.

(52) With F.sub.1, F.sub.2 and F.sub.3 defined as such, evaluation of the function F then corresponds to m applications alternatively of function F.sub.1 and function F.sub.2 followed by application of function F.sub.3.

(53) The circuit represented in FIGS. 7a and 7b comprises two sets of N/km input multipliers. During the iteration z of the function F1 or F2, the N/km multipliers of the relevant sub-circuit each take on input,

(54) $E_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u\right)$$\mathrm{and}$$E_k^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}\left(u^{}\right)$
with 1jN/km. In FIGS. 7a and 7b these multipliers are noted r.sub.j with respectively 1jN/km and N/km+2j2N/km+1. The input wires are numbered respectively from 1 to 2N/km and from 3N/km+3 to 5N/km+2.

(55) The m applications of functions F.sub.1 and F.sub.2 compute the coded sub-scores {tilde over (S)}.sub.z, for z{1, . . . , m}:

(56) ${\tilde{S}}_z=\underset{=1}{\overset{z}{.Math.}}\underset{j=1}{\overset{N/k.Math.m}{.Math.}}{E}_{u.Math.u^{},k}^{\left(\left(-1\right).Math.\left(N/m\right)+\left(j-1\right).Math.k+1\right)}$

(57) The N/km output wires of the multipliers of a sub-circuit during the iteration z carry the values

(58) $E_{u.Math.u^{},k}^{\left(\frac{\left(z-1\right)N}{m}+\left(j-1\right)k+1\right)}$
whereof the sum, added to the coded sub-score of the preceding iteration {tilde over (S)}.sub.z-1, is equal to the encoded score {tilde over (S)}.sub.z described hereinabove. The sub-score {tilde over (S)}.sub.0 can be also initialized at 0 during the first iteration. The coded score {tilde over (S)} is constructed iteratively, each iteration adding to the sub-score coming from the preceding iteration the result of the current scalar sub-product .sub.j=1.sup.N/k.Math.mE.sub.u.Math.u,k.sup.((z1)(N/m)+(j1).Math.k+1).

(59) The circuit comprises an additional output multiplier for each sub-circuit, numbered r.sub.N/km+1, r.sub.2N/km+2 necessary for conversion of the circuit in the form of QAP. On completion of its evaluation each sub-circuit stores the coded sub-scores {tilde over (S)}.sub.z computed in the storage memory corresponding to its bus (Bus Bank) r2.sub.N/km+3, r.sub.2N/km+219 in terms of the verifiable computation method.

(60) On completion of m iterations of functions F1 and F2, the coded score g is thus stored in one of the two storage memories. In the example of FIGS. 7a and 7b, it is supposed that m is odd. The coded score {tilde over (S)} is stored in the first storage memory. During evaluation of the function F3, with the coded score {tilde over (S)} on input a first split gate recovers the terms a.sub.i with 1ik corresponding to the terms of the scalar product u.Math.u. The summation of these terms produces the score S which is then compared to the predetermined threshold T.

(61) Within the scope of the method described hereinabove the operations to be carried out for generation of the evaluation and verification public keys, and for generation and verification of computation proof can be derived from existing verifiable computation protocols such as Pinocchio, when m=1, and Geppetto, when m>1. The paragraphs hereinbelow describe these operations in more detail as a function of the value of the divider m.

(62) It is to be understood that the embodiment to be described is a particularly advantageous embodiment which is not limiting. The skilled person can use other ways to perform generation of the evaluation and verification public keys, generation and verification of computation proof, and derive said operations from other verifiable existing computation protocols.

(63) Case m=1: In the first mode of operation where m=1, an asymmetric bilinear environment (q, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e) is defined with q a prime number, G.sub.1, G.sub.2 and G.sub.T three groups of order q, g.sub.1 a generator of G.sub.1, g.sub.2 a generator of G.sub.2, and e a non-degenerate bilinear pairing e: G.sub.1G.sub.2.fwdarw.G.sub.T.

(64) The arithmetic circuit can be represented in the form of a polynomial representation of the circuit Q=(t,V,W,Y) of size and degree , with V={vi}, W={wi}, Y={yi}, 0i.

(65) The following are noted hereinbelow:

(66) I.sub.io={1, . . . , } the set of indices corresponding to the input/output wires of the circuit,

(67) I.sub.mid={+1, . . . , } the set of indices of the intermediate wires of the circuit not being input wires of the circuit.

(68) During generation step E3 of a public evaluation key and a public verification key, random variables r.sub.v, r.sub.w, s, .sub.v, .sub.w, .sub.y, , are first generated in .sub.q.

(69) Then the following coefficients are defined: r.sub.y=r.sub.v.Math.r.sub.w, g.sub.v1=g.sub.1.sup.r.sup.v, g.sub.w1=g.sub.1.sup.r.sup.w, g.sub.w2=g.sub.2.sup.r.sup.w, g.sub.y1=g.sub.1.sup.r.sup.y and g.sub.y2=g.sub.2.sup.r.sup.y.

(70) The public evaluation key EK.sub.F is then generated as equal to (EK.sub.F1, EK.sub.F2) where

(71) ${\mathrm{EK}}_{F1}=\left(\begin{array}{c}{\left\{g_{v1}^{v_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{w1}^{w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{y1}^{y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},\\ {\left\{g_{v1}^{{}_v.Math.v_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{w1}^{{}_w.Math.w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},{\left\{g_{y1}^{{}_y.Math.y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}},\\ {\left\{g_1^{s^i}\right\}}_{i\left[1,\right]},{\left\{g_{v1}^{.Math.v_i\left(s\right)}.Math.g_{w1}^{.Math.w_i\left(s\right)}.Math.g_{y1}^{.Math.y_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}}\end{array}\right)$${\mathrm{EK}}_{F2}=\left({\left\{g_{w2}^{w_i\left(s\right)}\right\}}_{i{I}_{\mathrm{mid}}}\right)$

(72) The public verification key VK.sub.F is also generated as equal to (VK.sub.F1, VK.sub.F2) where:
VK.sub.F1=(g.sub.1,{g.sub.v1.sup.v.sup.i.sup.(s)}.sub.i[1,],{g.sub.y1.sup.y.sup.i.sup.(s)}.sub.i[1,])
VK.sub.F2=(g.sub.2,g.sub.2.sup..sup.v;g.sub.2.sup..sup.w,g.sub.2.sup..sup.y,g.sub.2.sup..Math.,g.sub.y2.sup.t(s),{g.sub.w2.sup.w.sup.i.sup.(s)}.sub.i[1,]).

(73) The remote computation device then obtains E4 the arithmetic circuit and the public evaluation key.

(74) For each biometric datum of the entity, at least one matching value between the biometric datum of the entity and at least one reference biometric datum can then be determined E5 by the remote computation device by evaluating the arithmetic circuit received from the biometric data of the entity and the reference biometric data. The set of values of the circuit {c.sub.i}.sub.i[1,] can then be obtained.

(75) Generation E6 by the remote computation device, for each determined matching value, of a proof of correction of the computation execution of the matching value, so-called generated proof =(.sub.1,.sub.2) can then comprise:

(76) determination of a polynomial h(x) such that p(x)=h(x).Math.t(x) with p(x)=(v.sub.0(x)+.sub.i=1.sup.c.sub.i.Math.v.sub.i(x)).Math.(w.sub.0(x)+.sub.i=1.sup.c.sub.i.Math.w.sub.i(x))(x)+.sub.i=1.sup.c.sub.i.Math.y.sub.i(x)),

(77) computation of:

(78) ${}_1=\left(\begin{array}{c}{g}_{v1}^{v_{\mathrm{mid}}\left(s\right)},g_{w1}^{w_{\mathrm{mid}}\left(s\right)},g_{y1}^{y_{\mathrm{mid}}\left(s\right)},g_1^{h\left(s\right)},\\ g_{v1}^{{}_v.Math.v_{\mathrm{mid}}\left(s\right)},g_{w1}^{{}_w.Math.w_{\mathrm{mid}}\left(s\right)},g_{y1}^{{}_y.Math.y_{\mathrm{mid}}\left(s\right)},\\ g_{v1}^{.Math.v_{\mathrm{mid}}\left(s\right)}.Math.g_{w1}^{.Math.w_{\mathrm{mid}}\left(s\right)}.Math.g_{y1}^{.Math.y_{\mathrm{mid}}\left(s\right)},\end{array}\right)$
and .sub.2=(g.sub.w2.sup.W.sup.mid.sup.(s))
where: v.sub.mid(x)=.sub.iI.sub.mid c.sub.i.Math.v.sub.i(x), w.sub.mid(x)=.sub.iI.sub.mid c.sub.i.Math.w.sub.i(x) and y.sub.mid=.sub.iI.sub.mid c.sub.i.Math.y.sub.i(x).
The remote computation device then transmits E7 the matching values and said generated proofs to the client device.

(79) The proofs received by the client device are of the form (.sub.r1, .sub.r12) with: .sub.r1 in the form of: (g.sub.v1.sup.V.sup.mid, g.sub.w1.sup.W.sup.mid, g.sub.y1.sup.Y.sup.mid, g.sub.1.sup.H, g.sub.v1.sup.V.sup.mid, g.sub.w1.sup.W.sup.mid, g.sub.y1.sup.Y.sup.mid, g.sub.1.sup.Z) and .sub.r2 in the form g.sub.w2.sup.w.sup.mid.

(80) The client device then verifies E8 each received proof (.sub.r1, .sub.r2) by performing the following equality tests:
e(g.sub.v1.sup.v.sup.o.sup.(s).Math.g.sub.v1.sup.v.sup.io.sup.(s).Math.g.sub.v1.sup.V.sup.mid,g.sub.w2.sup.w.sup.o.sup.(s).Math.g.sub.w2.sup.w.sup.io.sup.(s).Math.g.sub.w2.sup.W.sup.mid)=e(g.sub.1.sup.H,g.sub.y2.sup.t(s)).Math.e(g.sub.y1.sup.y.sup.o.sup.(s).Math.g.sub.y1.sup.y.sup.io.sup.(s).Math.g.sub.y1.sup.Y.sup.mid,g.sub.2),
e((g.sub.v1.sup.V.sup.mid).sup.d.sup.1.Math.(g.sub.w1.sup.W.sup.mid).sup.d.sup.2.Math.(g.sub.y1.sup.Y.sup.mid).sup.d.sup.3,g.sub.2)=e((g.sub.v1.sup.V.sup.mid).sup.d.sup.1,g.sub.2.sup..sup.v).Math.e((g.sub.w1.sup.W.sup.mid).sup.d.sup.2,g.sub.2.sup..sup.w).Math.e((g.sub.y1.sup.Y.sup.mid).sup.d.sup.3,g.sub.2.sup..sup.y),
e((g.sub.1.sup.Z,g.sub.2.sup.)=e(g.sub.v1.sup.V.sup.mid.Math.g.sub.w1.sup.W.sup.mid.Math.g.sub.y1.sup.Y.sup.mid,g.sub.2.sup..Math.) where g.sub.v1.sup.v.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.v1.sup.v.sup.i.sup.(s)).sup.c.sup.i, g.sub.w1.sup.w.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.w1.sup.w.sup.i.sup.(s)).sup.c.sup.i, and g.sub.y1.sup.y.sup.io.sup.(s)=.sub.i=1.sup.(g.sub.y1.sup.y.sup.i.sup.(s)).sup.c.sup.i and (d.sub.1, d.sub.2, d.sub.3) elements of .sub.q on bits with a security parameter. In this mode of operation the verification step of said received proofs therefore comprises batch verification of pairings.

(81) Case m>1:

(82) Bank B is called a sub-set of indices [1, ] (in other words a sub-set of the circuit wires) and an instance of a bank B is a set of values for these indices (for example noted {c.sub.j}.sub.jB).

(83) The function F is divided into sub-functions F.sub.1, . . . , F.sub.. For example in the case of FIGS. 6 and 7 selection can be made respectively =2 and =3 as described hereinabove.

(84) =((f.sub.l, (T.sub.l1, . . . , T.sub.ll))).sub.l[1,L] is defined as a scheduling of length L with f.sub.l{1, . . . , } the index of the function to be computed.

(85) By way of example, in the case m=2 or m=3 described hereinabove in reference to FIGS. 6a to 6c, L=m+1 and the function F is split into two functions F.sub.1, F.sub.2.

(86) The banks used are: (B.sub.io, B.sub.L.sub.1, B.sub.L.sub.2, B.sub.B.sub.1, . . . , B.sub.B.sub.m) where:

(87) B.sub.io: banks of input/output type. Number of instances: m+1 B.sub.L.sub.1: bank of local type for F1. Number of instances: m B.sub.L.sub.2: bank of local type for F2. Number of instances: 1 B.sub.B.sub.1, . . . , B.sub.B.sub.m: banks of bus type. An instance of each.
The scheduling of proofs, of length m+1, is:
=((1,(1,1,0,1,0, . . . 0)), . . . ,(1,(m,m,0, . . . ,1)),(2,(m+1,0,1, . . . ,1)))
In other words, the scheduling of proofs is: For l{1, . . . , m}: digest of B.sub.L.sub.1.sup.(l), pledging of B.sub.B.sub.l, proof with B.sub.L.sub.1.sup.(l), inputs B.sub.io.sup.(l), and bus B.sub.B.sub.l. For l=m+1: digest of B.sub.L.sub.2, proof with B.sub.L.sub.2, inputs B.sub.io.sup.(l), and all buses B.sub.B.sub.1, . . . , B.sub.B.sub.m.
By way of example, in the case m4 described hereinabove in reference to FIGS. 7a and 7b, the function F is split into three functions F.sub.1, F.sub.2, F.sub.3. The banks used are: (B.sub.io, B.sub.L1, B.sub.L2, B.sub.L2, B.sub.B1, B.sub.B2) where: B.sub.io: banks of input/output type. Number of instances: m+1 B.sub.L.sub.1: bank of local type for F.sub.1. Number of instances: m/2 B.sub.L.sub.2: bank of local type for F.sub.2. Number of instances: m/2 B.sub.L.sub.3: bank of local type for F.sub.3. Number of instances: 1 B.sub.B.sub.1, B.sub.B.sub.2: banks of bus type. m/2 instances of the first m/2 instances of the second.
The scheduling of proofs, of length m+1, is:
=(.sub.1,.sub.2, . . . .sub.m,.sub.m+1)
where: For l {1, . . . , m}: If l odd: digest of B.sub.L.sub.1.sup.(l/2), pledging of B.sub.B.sub.1, proof with B.sub.L.sub.1.sup.(l/2), inputs B.sub.io.sup.(l), and bus B.sub.B.sub.1.
.sub.l=(1,(l,l/2,0,0,l/2,l/21)) If l even: digest of B.sub.L.sub.2.sup.(l/2), pledging of B.sub.B.sub.2, proof with B.sub.L.sub.2.sup.(l/2), inputs B.sub.io.sup.(l), and bus B.sub.B.sub.2 . . .
.sub.l=(2,(l,0,l/2,0,l/21,l/2)) For l=m+1: digest of B.sub.L.sub.3, proof with B.sub.L.sub.3, inputs B.sub.io.sup.(l), and the bus bank B.sub.B.sub.1 (if m is odd) or B.sub.B.sub.2 (if not).
.sub.l=(3,(m+1,0,0,1,l,0)) or .sub.l=(3,+1,0,0,1,0,l)).
For a number x the notation x/2 (respectively x/2) designates the natural integer greater than or equal (respectively less then or equal) to the rational value x/2. For more information on the use of banks and such scheduling, the paragraphs hereinbelow can be viewed in the light of the publication referenced hereinabove describing the Geppetto protocol from which the protocol presented hereinbelow is derived.

(88) In these second and third modes of operation, an asymmetric bilinear environment (q, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e) is defined with q a prime number, G.sub.1, G.sub.2 and G.sub.T three groups of order q, g.sub.1 a generator of G.sub.1, g.sub.2 a generator of G.sub.2, and e a non-degenerate bilinear pairing e: G.sub.1G.sub.2.fwdarw.G.sub.T.

(89) The arithmetic circuit can be represented in the form of a multi-QAP Q=({B.sub.b}.sub.b[1,l], t, V, W, Y) of size and degree , with {B.sub.b}.sub.b[1,l] a set of l banks B.sub.b of Q used in computing the function F, and V={vi}, W={wi}, Y={yi} with 0i.

(90) During the generation step E3 by the client device of a public evaluation key and a public verification key, random variables s,{(.sub.bv, .sub.bw, .sub.by, .sub.b, .sub.b)}.sub.b[1,l], r.sub.v, r.sub.w are generated in .sub.q.

(91) Next, the following coefficients are defined: r.sub.y=r.sub.v.Math.r.sub.w, g.sub.v1=g.sub.1.sup.r.sup.v, g.sub.v2=g.sub.2.sup.r.sup.v, g.sub.w1=g.sub.1.sup.r.sup.w, g.sub.w2=g.sub.2.sup.r.sup.w, g.sub.y1=g.sub.1.sup.r.sup.y and g.sub.y2=g.sub.2.sup.r.sup.y.

(92) The public evaluation key EK.sub.F is generated as equal to:
({EK.sub.Fb}.sub.b[1,l],{g.sub.1.sup.s.sup.i}.sub.i[1,],g.sub.v1.sup.t(s),g.sub.w1.sup.t(s),g.sub.y1.sup.t(s),g.sub.v2.sup.t(s),g.sub.w2.sup.t(s),g.sub.y2.sup.t(s))
Each public bank key EK.sub.Fb is equal to (EK.sub.Fb1, EK.sub.Fb2) and generated by computing:

(93) ${\mathrm{EK}}_{\mathrm{Fb}1}=\left(\begin{array}{c}{\left\{\begin{array}{c}{g}_{v1}^{v_i\left(s\right)},g_{w1}^{w_i\left(s\right)},g_{y1}^{y_i\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v_i\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w_i\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y_i\left(s\right)},\\ g_{v1}^{{}_b.Math.v_i\left(s\right)}.Math.g_{w1}^{{}_b.Math.w_i\left(s\right)}.Math.g_{y1}^{{}_b.Math.y_i\left(s\right)}\end{array}\right\}}_{i{B}_b},\\ g_{v1}^{{}_{\mathrm{bv}}.Math.t\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.t\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.t\left(s\right)},g_{v1}^{{}_b.Math.t\left(s\right)},g_{w1}^{{}_b.Math.t\left(s\right)},g_{y1}^{{}_b.Math.t\left(s\right)}\end{array}\right)$${\mathrm{EK}}_{\mathrm{Fb}2}=\left({\left\{g_{w2}^{w_i\left(s\right)}\right\}}_{i{B}_b},g_{w2}^{{}_{\mathrm{bw}}.Math.t\left(s\right)}\right).$

(94) The public verification key VK.sub.F is also generated as equal to: ({VK.sub.Fb}.sub.b[1,l], g.sub.1, g.sub.2, g.sub.y2.sup.t(s)). Each public bank key VK.sub.Fb is equal to (g.sub.2.sup..sup.bv, g.sub.2.sup..sup.bw, g.sub.2.sup..sup.by, g.sub.2.sup..sup.b, g.sub.2.sup..sup.b.sup..Math..sup.b).

(95) The remote computation device obtains E4 the arithmetic circuit and the public evaluation key.

(96) For each biometric datum of the entity, at least one matching value between said biometric datum and at least one reference biometric datum can then be determined E5 by the remote computation device by evaluating the arithmetic circuit received from the biometric data of the entity and the reference biometric data. The remote computation device evaluates each sub-function F.sub. from the biometric data of the entity and the reference biometric data for obtaining the matching value and the values of the circuit.

(97) Generation E6 by the remote computation device, for each determined matching value, of a proof of correction of the computation execution of the matching value can comprise for each l={1, . . . , L} a list of digests and proofs obtained as described hereinbelow.

(98) Let .Math.[1,l] be the set of indices b[1,l] such that T.sub.lb0 in the scheduling =((f.sub.l, (T.sub.l1, . . . , T.sub.ll))).sub.l[1,L].

(99) Hereinbelow the following: =U.sub.bB.sub.b, {c.sub.j}.sub.jB.sub.b an instance of the bank B.sub.b and ={c.sub.i}.sub.i the set of values of .

(100) For each bank B.sub.b such as b,

(101) the remote computation device generates pledging random variables o.sub.b=(o.sub.bv, o.sub.bw, o.sub.by) in .sub.q.

(102) it then computes the digest D.sub.b equal to (D.sub.b1, D.sub.b2) from the instance of the bank of variables B.sub.b: B.sub.b.sup.(T.sup.lb.sup.)={c.sub.i}.sub.iB.sub.b and pledging random variables o.sub.b. Such digests are such that: if the bank B.sub.b is an input/output bank: D.sub.b1=(g.sub.v1.sup.v.sup.(b).sup.(s), g.sub.y1.sup.y.sup.(b).sup.(s)) and D.sub.b2=(g.sub.w1.sup.w.sup.(b).sup.(s)), if the bank B.sub.b is not an input/output bank:

(103) $D_{b1}=\left(\begin{array}{c}{g}_{v1}^{v^{\left(b\right)}\left(s\right)},g_{w1}^{w^{\left(b\right)}\left(s\right)},g_{y1}^{y^{\left(b\right)}\left(s\right)},g_{v1}^{{}_{\mathrm{bv}}.Math.v^{\left(b\right)}\left(s\right)},g_{w1}^{{}_{\mathrm{bw}}.Math.w^{\left(b\right)}\left(s\right)},g_{y1}^{{}_{\mathrm{by}}.Math.y^{\left(b\right)}\left(s\right)},\\ g_{v1}^{{}_b.Math.v^{\left(b\right)}\left(s\right)}.Math.g_{w1}^{{}_b.Math.w^{\left(b\right)}\left(s\right)}.Math.g_{y1}^{{}_b.Math.y^{\left(b\right)}\left(s\right)}\end{array}\right)$$D_{b2}=\left(g_{w2}^{w^{\left(b\right)}\left(s\right)}\right)$ with:
v.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.v.sub.i(s)+o.sub.bv.Math.t(s),
w.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.w.sub.i(s)+o.sub.bw.Math.t(s),
y.sup.(b)(s)=.sub.iB.sub.bc.sub.i.Math.y.sub.i(s)+o.sub.by.Math.t(s),
The remote computation device then determines a polynomial h.sup.(l)(x) such that p.sup.(l)(x)=h.sup.(l)(x).Math.t(x)
with p.sup.(l)(x)=(v.sub.0(x)+.sub.ic.sub.i.Math.v.sub.j(x)+.sub.bo.sub.bv.Math.t(x)).Math.(w.sub.0(x)+.sub.ic.sub.i.Math.w.sub.j(x)+.sub.bo.sub.bw.Math.t(x))(y.sub.0(x)+.sub.ic.sub.i.Math.y.sub.j(x)+.sub.bo.sub.by.Math.t(x))
Finally, it computes a proof element .sup.(l) equal to g.sub.1.sup.h.sup.(l).sup.(s).

(104) The remote computation device then transmits E7 the matching values and said generated proofs comprising the list of computed digests and proof elements to the client device.

(105) The proofs received by the client device are of the form of: D.sub.1.sup.(1), . . . , D.sub.l.sup.(1), .sup.(1), . . . , D.sub.1.sup.(L), . . . , D.sub.l.sup.(L), .sup.(L) where for all l{1, . . . , L} and {1, . . . ,l}:

(106) 0$D_b^{\left(l\right)}=\left(\left(g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_{v1}^{V_b^{\left(l\right)}},g_{w1}^{W_b^{\left(l\right)}},g_{y1}^{Y_b^{\left(l\right)}},g_1^{Z_b^{\left(l\right)}}\right),\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)$
and .sup.(l)=g.sub.1.sup.H.sup.(l).

(107) Two verification implementation variants of the received proof E8 are specified hereinbelow.

(108) In a first implementation variant, the client device then verifies each received proof by performing: verification of L.Math.e digests, for l{1, . . . , L} and b{1, . . . , l} comprising the following equality tests:

(109) $e\left(g_{v1}^{V_b^{\left(l\right)}},g_2^{{}_{\mathrm{bv}}}\right)=e\left(g_{v1}^{V_b^{\left(l\right)}},g_2\right)$$e\left(g_{w1}^{W_b^{\left(l\right)}},g_2^{{}_{\mathrm{bw}}}\right)=e\left(g_{w1}^{W_b^{\left(l\right)}},g_2\right)$$e\left(g_{y1}^{Y_b^{\left(l\right)}},g_2^{{}_{\mathrm{by}}}\right)=e\left(g_{y1}^{Y_b^{\left(l\right)}},g_2\right)$$e\left(g_1^{Z_b^{\left(l\right)}},g_2^{{}_b}\right)=e\left(g_{v1}^{V_b^{\left(l\right)}}.Math.g_{w1}^{W_b^{\left(l\right)}}.Math.g_{y1}^{Y_b^{\left(l\right)}},g_2^{{}_b.Math.{}_b}\right)$ verification of L proofs comprising for l{1, . . . , L} the following equality test:

(110) $e\left(\underset{b=1}{\overset{}{.Math.}}\left(g_{v1}^{V_b^{\left(l\right)}}\right),\underset{b=1}{\overset{}{.Math.}}\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)=e\left(g_1^{H^{\left(l\right)}},g_{y2}^{t\left(s\right)}\right).Math.e\left(\underset{b=1}{\overset{}{.Math.}}\left(g_{y1}^{Y_b^{\left(l\right)}}\right),g_2\right)$

(111) In a second implementation variant, the client device then verifies each received proof by executing batch verification comprising, given a correction parameter : selection of a random vector (d.sub.1, . . . , d.sub.3.Math.l) of elements of size , batch verification of the L.Math.l digests, in l times by executing the following equality tests, for b{1, . . . , l}:

(112) $e\left(\underset{i=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l},g_2^{{}_{\mathrm{bv}}}\right).Math.e\left(\underset{i=1}{\overset{L}{.Math.}}{\left(g_{w1}^{W_b^{\left(l\right)}}\right)}^{d_{L+l}},g_2^{{}_{\mathrm{bw}}}\right).Math.e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_2.Math.L+l},g_2^{{}_{\mathrm{by}}}\right)=e\left(\underset{i=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l}.Math.\underset{l=1}{\overset{L}{.Math.}}{\left(g_{w1}^{W_b^{\left(l\right)}}\right)}^{d_{L+l}}.Math.\underset{l=1}{\overset{L}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_{2.Math.L+l}},g_2\right)$$e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_1^{Z_b^{\left(l\right)}}\right)}^{d_l},g_e^{{}_b}\right)=e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}.Math.g_{w1}^{W_b^{\left(l\right)}}.Math.g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_l},g_2^{{}_b.Math.{}_b}\right)$ batch verification the L proofs by executing the following equality test:

(113) $\underset{l=1}{\overset{L}{.Math.}}e\left(\underset{b=1}{\overset{}{.Math.}}{\left(g_{v1}^{V_b^{\left(l\right)}}\right)}^{d_l},\underset{b=1}{\overset{}{.Math.}}\left(g_{w2}^{W_b^{\left(l\right)}}\right)\right)=e\left(\underset{l=1}{\overset{L}{.Math.}}{\left(g_1^{H^{\left(l\right)}}\right)}^{d_l},g_{y2}^{t\left(s\right)}\right).Math.e\left(\underset{l=1}{\overset{L}{.Math.}}\underset{b=1}{\overset{}{.Math.}}{\left(g_{y1}^{Y_b^{\left(l\right)}}\right)}^{d_l},g_2\right),$ and as a verification option of the belonging of elements on which the pairings is applied to their respective groups.