Verification process of authentication or biometric identification
The invention proposes a method for processing biometric data, comprising verification of the result of a calculation of distance between a biometric candidate datum and at least one biometric reference datum, each comprising a number n of indexed components (a i , b i ), said calculation of distance comprising that of a polynomial of the components of the biometric data, the method being executed by a proving entity and a verification entity, the method comprising steps during which: the proving entity communicates to the verification entity the result of calculation of the distance between the candidate and reference biometric data, and said data, the proving entity generates from each datum a function of a number d of variables f a (i 1 , . . . , i d ), f b (i 1 , . . . , i d ) where d=log 2 n, defined for each variable on the set {0,1}, by reformulation of the index i of each component (a i , b i ) in binary format, the proving entity generates from each function a polynomial of d variables ã(x 1 , . . . x d ), {circumflex over (b)} (x 1 , . . . x d ) defined on d where is a finite field, such that each polynomial ã, {circumflex over (b)} coincides with the corresponding function f a ,f b on the set {0,1} d , and generates from the polynomials ã, {circumflex over (b)} a polynomial p(x 1 , . . . , x d ) of d variables of the same expression as that of the distance between the data, and the proving entity and the verification entity engage in a Sumcheck protocol applied to the polynomial p to verify the result of calculation of the distance between the data.
1. A method for processing biometric data, the method being executed by a proving entity (P) and a verification entity (V), each entity being a processing unit comprising processing and communication means with the other entity, the method comprising the following steps:
communicating, by the proving entity (P), to the verification entity (V) the result of a calculation of distance between a biometric candidate datum (a) and at least one biometric reference datum (b), each comprising a number n of indexed components (a i , b i ), and said data, said calculation of distance comprising that of a polynomial of the components of the biometric data,
generating, by the proving entity (P), from each datum a function of a number d of variables f a (i 1 , . . . , i d ), f b (i 1 , . . . , i d ) where d=log 2 n, defined for each variable on the set {0,1}, by reformulation of the index i of each component (a i , b i ) in binary format,
generating, by the proving entity (P), from each function a polynomial of d variables ã(x 1 , . . . x d ), {circumflex over (b)}(x i , . . . x d ) defined on λ d where ∥ is a finite field, such that each polynomial ã, {circumflex over (b)} coincides with the corresponding function f a ,f b on the set {0,1} d , and
generating, by the proving entity (P) from the polynomials ã, {circumflex over (b)} a polynomial p(x 1 , . . . , x d ) of d variables of the same expression as that of the distance between the data,
engaging, by the proving entity (P) and the verification entity (V), in a Sumcheck protocol applied to the polynomial p to verify the result of the calculation of the distance between the data, and
verifying of the result of calculation of distance between the biometric candidate datum and the at least one biometric reference datum.
2. The method as claimed in claim 1 , in which calculation of distance comprises that of a scalar product, and the polynomial p comprises at least one term g equal to a scalar product between the polynomials ã and {circumflex over (b)}:
g ( x 1 , . . . ,x d )=ã( x 1 , . . . ,x d )·{tilde over (b)}( x 1 , . . . ,x d ).
3. The method as claimed in claim 2 , in which the calculated distance is the square of the Euclidian distance, and the polynomial p is written as:
p ( x 1 , . . . ,x d )=ã( x 1 , . . . ,x d )·ã( x 1 ; . . . ,x d )+{tilde over (b)}( x 1 , . . . ,x d )·{tilde over (b)}( x 1 , . . . ,x d )−2 g ( x 1 , . . . ,x d ).
4. The method as claimed in claim 2 , in which the calculated distance is the Hamming distance, and the polynomial p is written as:
p ( x 1 , . . . ,x d )=ã( x 1 , . . . ,x d )+{tilde over (b)}( x 1 , . . . ,x d )−2 g ( x 1 , . . . ,x d ).
5. The method as claimed in claim 1 , in which the biometric candidate datum and the biometric reference datum or the biometric reference data are initially retained by the proving entity (P), and the method comprises a preliminary step of masking, by the proving entity (P), biometric data, said masking comprising the random generation of a circular permutation and a vector of n components, and performing a sum or the operation exclusive or between each datum permutated by the circular permutation and the randomly generated vector.
6. The method as claimed in claim 1 , in which each polynomial ã( x 1 , . . . , x d ) and {circumflex over (b)}( x 1 , . . . , x d ) is of degree a in each variable.
7. The method as claimed in claim 6 , in which the polynomial ã( x 1 , . . . , x d ) is defined by:
∀
x
∈
F
d
,
a
~
(
x
)
=
∑
i
=
(
i
1
,
…
,
i
d
)
∈
{
0
,
1
}
d
a
(
i
)
x
i
(
x
)
with
:
x
υ
(
x
1
,
…
,
x
d
)
=
∏
k
=
1
d
χ
υ
k
(
x
k
)
and where the function Xv k (x k ) is defined, for x k ∈{0,1}, by:
{
χ
υ
k
(
x
k
)
=
1
-
x
k
if
υ
k
=
0
χ
υ
k
(
x
k
)
=
x
k
if
υ
k
=
1
8. The method as claimed in claim 6 wherein calculation of distance comprises that of a scalar product, and the polynomial p comprises at least one term g equal to a scalar product between the polynomials ãand {circumflex over (b)}:
g ( x 1 , . . . ,x d )=ã( x 1 , . . . ,x d )·{tilde over (b)}( x 1 , . . . ,x d )
in which the application of the Sumcheck protocol directly comprise generating by the proving entity (P) j polynomials p j of a single variable from the polynomial p, and transmitting to the verification entity (V) evaluations of each polynomial p j in three points for the verification entity (V) to interpolate the polynomial p j .
9. Method according to claim 8 , wherein for each polynomial p j , for j from 1 to d−1, the proving entity (P) transmits the evaluations of these polynomials in 0, 1, and a third value t.
10. The method as claimed in claim 7 , in which the application the Sumcheck protocol comprises a series of iterations for j from 2 to d−1 during which the verification entity (V) randomly generates and communicates to the proving entity a value r j−1 , and the proving entity (P) generates a polynomial:
p
j
(
X
j
)
n
=
∑
x
j
+
1
∈
{
0
,
1
}
…
x
d
∈
[
0
,
1
]
n
p
(
r
1
,
…
,
r
j
-
1
,
X
j
,
x
j
+
1
,
…
,
x
d
)
and, at each iteration,
the proving entity (P) has for each polynomial ã, {tilde over (b)} a table A (j) , B (j) comprising respectively all the possible values of the functions ã(r 1 , . . . r j−2 , x j−i , . . . x d ) and {tilde over (b)} (r 1 , . . . r j−2 , x j−i , . . . x d ) for (x j−i , . . . x d )∈{0,1} d−j+1 , where each value r k (k=l, . . . j−2) has been generated randomly by the verification entity and sent to the proving entity during the preceding iterations,
evaluation of a polynomial p i in a value t is performed by the proving entity (P) from the values t, r j−1 and the values of the tables A (j) , B (j) , and
the proving entity (P) increments the tables A( j+1 ), B( j+1 ) for the iteration j+1 by replacing their values by all the possible values ã(r 1 , . . . r j−1 , x j , . . . x d ) and t {tilde over (b)}(r 1 , . . . r j−1 , x j , . . . x d ) for (x j , . . . x d )∈{0,1} d−j , the tables being initialised for the polynomial p2 by comprising all the possible values of the polynomials ã, {tilde over (b)} on the set {0,1} d .
11. The method as claimed in claim 2 , comprising verification of the result of calculation of a scalar product between a biometric candidate datum and each of a number m of biometric reference data, in which the biometric reference data are combined into a matrix M of size (n,m) such that the scalar products are obtained by the product of the candidate vector and of the matrix, and the Sumcheck protocol is executed on a polynomial p (r1, . . . , rd) (j 1 , . . . , j d ) such that:
p
(
r
1
,
…
,
r
d
)
(
j
1
,
…
,
j
d
)
=
∑
j
1
,
…
,
j
d
∈
{
0
,
1
}
d
a
~
(
j
1
,
…
,
j
d
)
·
M
(
j
1
,
…
,
j
d
,
r
1
,
…
,
r
d
)
where (r 1 , . . . , r d ) is a vector whereof the components are generated randomly by the verification entity (V).
12. The method of claim 1 , wherein:
the biometric candidate datum (a) is a biometric datum acquired on a biometric trait of an individual.
13. The method claimed in claim 12 , in which the proving entity (P) is an electronic device personal to the individual of telephone type, personal computer or digital tablet comprising a computer, a image sensor, and a module for acquisition of a biometric reference datum contained in an identity document.