MULTIPARTY SECURE CALCULATION METHOD PROTECTED AGAINST A MALEVOLENT PARTY

Abstract

The invention proposes a method comprising the evaluation of a function F obtained by applying to n sub-functions f.sub.i a first operation, the evaluation comprising: the application of a series of calculation steps in which a first unit assumes a role of a client and a second unit assumes a role of a server, and the repetition of the series of calculation steps in which the roles of client and of server are exchanged between the units,
each series of steps comprising: a) randomly generating, by the server, first data, and a second datum, b) for each sub-function f.sub.i, generating by the server a set of elements formed by: a result of f.sub.i evaluated in the data of the client and of the server, masked by a first datum, by applying the first operation between the result and the first datum, and masked by the second datum, by applying between the masked result and the second datum of a second operation different from the first and distributed relatively to the latter, c) recovering by oblivious transfer, by the client, an intermediate datum corresponding to one of the elements generated by the server, d) generating, by the server, a first result portion, by: masking each first datum with the second datum, applying to all the first masked data of the first operation, and e) generating by the client, a second result portion, by applying all the intermediate data of the first operation.

Claims

1. A method for executing a cryptographic calculation applied by two processing units each comprising processing means, and each having a vector comprising a number n of indexed components, the method comprising the secure evaluation of a function F obtained by applying to n sub-functions f.sub.i of several variables of an operation, called first operation with the vectors of each processing unit as inputs of the function, the method being characterized in that it comprises: application of a series of secure calculation steps in which a processing unit assumes a role of a client and the other processing unit assumes a role of a server, and repetition of the series of secure calculation steps in which the roles of client and of server are exchanged between the two processing units, each series of steps comprising: a) randomly generating, by the server, n first masking data, in the set .sub.m with m being a prime number, invertible for the first operation, and a second masking datum in the set .sub.m, invertible for a second operation, different from the first operation, and distributive relatively to the latter, b) for each sub-function f.sub.i, generating by the server a set of elements, each element being formed by: a result of the sub-function f.sub.i evaluated at the vector of the server and a vector which may be held by the client, masked by a first masking datum, the masking being obtained by applying the first operation between the result and the first masking datum, and masked by the second masking datum, the masking being applied by application between the result masked by the first masking datum and the second masking datum of the second operation, c) recovering by oblivious transfer, by the client, for each component of the vector held by the client, an intermediate datum corresponding to one of the elements generated by the server and indexed by the value of said component, d) generating, by the server, a first result portion, by: masking each first masking datum with the second masking datum, and applying to all said first masked data the first operation, and e) generating, by the client, a second result portion, by applying to all the intermediate data of the first operation, said second result portion comprising a masked evaluation of the function F with the vectors of the two processing units as inputs, applying, by two processing units, an equality test on the masked evaluations of the function F obtained at the end of each series of steps, and if the equality test succeeds, calculating, by one of the two processing units, the function evaluated with the data of the two processing units F(A,B) from the first and second result portions, and using the function evaluated with the data of two processing units in at least one application from among the group comprising a cryptographic application, an identification application, and an authentication application.

2. The method according to claim 1, wherein the application of both series of steps is carried out simultaneously.

3. The method according to claim 1, wherein the calculation step by one of two processing units, of F(A,B) comprises obtaining by one party, of the result portion held by the other processing unit, and inference of F(A,B) from both result portions.

4. The method according to claim 1, wherein the function to be evaluated is a fraction of functions, and the steps for applying and repeating the series of steps are carried out once for the numerator of the fraction, and once for the denominator.

5. The method according to claim 1, wherein the first operation is an addition or a multiplication, and the second operation is a multiplication or raising to a power, respectively.

6. The method according to claim 5, wherein the function F is a sum of the n sub-functions f.sub.i, and the application of each series of steps comprises: during step b), each element is formed by the sum of a possible result of the sub-function f.sub.i evaluated at the datum of the client and the datum of the server and of a first masking datum, and multiplied by the second masking datum, during step d), the first party of the result is generated by the server by summing all the first masking data and by multiplying by the second masking datum, and during step e), the second party of the result is generated by the client by summing all the intermediate data.

7. The method according to claim 5, wherein the function to be evaluated is one from among the following group: a Hamming distance between the vectors of the portions, a normalized Hamming distance between the vectors of the portions, a scalar product between the vectors of the portions.

8. The method according to claim 7, wherein the vectors of the processing units are identity data of individuals, and the use of the evaluated function comprises: comparing the value F(X,Y) with a pre-established threshold depending on the nature of the evaluated function, and from a result of said comparison, determining whether the identity data correspond or not to a same individual.

9. The method according to claim 8, wherein the identity data of individuals are data coded on biometric traits of individuals.

10. The method according to claim 7, wherein each sub-function f.sub.i is a function of two variables, the components of the data held by the processing units are integers comprised between 0 and q−1, and: step b) comprises the generation by the server of a set comprising the elements:
(α(r.sub.i+f.sub.i(0,Y), . . . ,α(r.sub.i+f.sub.i(q−1,Y))) wherein Y is the vector held by the server, and the recovered intermediate datum during step c) is:
α(r.sub.i+f.sub.i(x.sub.i,Y))

11. The method according to claim 1, wherein the function to be evaluated is a product of the n sub-functions f.sub.i, and the application of each series of steps comprises: during step b), each element is formed by the product of a possible result of the sub-function f.sub.i evaluated in the datum of the client and the datum of the server and of a first masking datum, and raising to a power of the second masking datum, during step d), the first party of the result is generated by the server by a product of all the first masking data and raising to a power of the second masking datum, and during step e), the second party of the result is generated by the client by a product of all the intermediate data.

12. The method according to claim 11, wherein each sub-function f.sub.i is a function of two variables, the components of the data held by the processing units are integers comprised between 0 and q−1, and: step b) comprises the generation by the server of a set comprising the elements:
((r.sub.i.Math.f.sub.i(0,Y)).sup.α, . . . . (r.sub.i.Math.f.sub.i(q−1,Y)).sup.α) wherein Y is the vector held by the server, and the recovered intermediate datum during step c) is:
(r.sub.i.Math.f.sub.i(x.sub.i,Y)).sup.α

13. A computer program product, comprising code instructions for executing, by a processor of a processing unit, a method comprising the application of a series of steps comprising: randomly generating n first data r.sub.i in the set .sub.m with m being a prime number, and invertible for a first operation, and a second datum belonging to the set of the invertible elements of .sub.m for a second operation, different from the first operation and distributive relatively to the latter, for each i from 1 to n, generating a set of elements, each element being formed by: a possible result of a function f.sub.i evaluated at an unknown datum and a known datum, masked by a first masking datum, the masking being obtained by applying the first operation between the first datum and the result, and masked by the second masking datum, the masking being applied by application between the result masked by the first masking datum and the second masking datum of the second operation, participating in an oblivious transfer protocol with a distinct processing unit for communicating, for each i from 1 to n, an element from among the generated elements.

14. A method for authenticating an individual, applied by an authentication system including a first processing unit holding an identity datum of the individual, and a second processing unit holding an identity datum of a reference individual, the method comprising the application of the data processing method according to claim 1 by the processing units from two identity data, the function to be evaluated being selected from among the group comprising: a Hamming distance between the vectors of the portions, a normalized Hamming distance between the vectors of the portions, a scalar product between the vectors of the portions.

15. A system for authenticating an individual, comprising a first processing unit and a second processing unit, each processing unit comprising a processor and a communication interface, the system being characterized in that the first and the second processing unit are adapted for applying the data processing method according to claim 1, the function to be evaluated being selected from the group comprising: a Hamming distance between the vectors of the portions, a normalized Hamming distance between the vectors of the portions, a scalar product between the vectors of the portions.

Description

DESCRIPTION OF THE FIGURES

[0116] Other features, objects and advantages of the present invention will become apparent upon reading the detailed description which follows, with reference to the appended figures, given as non-limiting examples and wherein:

[0117] FIG. 1a illustrates a first exemplary embodiment for executing a series of steps of a method for executing a cryptographic calculation,

[0118] FIG. 1b illustrates a second exemplary repeated embodiment for a series of steps of a method for executing a cryptographic calculation with different masking data,

[0119] FIG. 2a illustrates an exemplary equality test which may be applied to the exemplary embodiment of FIG. 1a,

[0120] FIG. 2b illustrates an exemplary equality test which may be applied to the exemplary embodiment of FIG. 1b,

[0121] FIG. 3a schematically illustrates the main steps of an exemplary method for executing a cryptographic calculation,

[0122] FIG. 3b schematically illustrates the main steps of an exemplary authentication method,

[0123] FIG. 4 schematically illustrates one of the data processing systems adapted for applying the method, in an exemplary application to authentication of an individual.

DETAILED DESCRIPTION OF AT LEAST ONE EMBODIMENT OF THE INVENTION

Data Processing System

[0124] With reference to FIG. 4, two portions P.sub.1 and P.sub.2 respectively having a vector A and B, is illustrated, each vector comprising a same number n of indexed components (a.sub.1, . . . , a.sub.n), (b.sub.1, . . . , b.sub.n).

[0125] Each vector is expressed in a base q, wherein q is an integer strictly greater than 1, i.e. the components a.sub.i and b.sub.i are integers with values comprised between 0 and q−1. The data A and B are not necessarily expressed in the same base so that A may be in a base q and B in a base q′ with q′ being an integer strictly greater than 1 and different from q.

[0126] According to a particular and non-limiting embodiment, each vector is binary, and its components are with values equal to 0 or 1.

[0127] The vectors A and B respectively held by the portions P.sub.1 and P.sub.2 are secrets, i.e. the vector A is only known to P.sub.1 and the vector B is only known to P.sub.2.

[0128] Each party is a processing unit, and has processing means, for example a processor 10.sub.1, 10.sub.2, adapted for applying the calculations, and for executing a program comprising code instructions installed on the processor. Each party also has a memory 11.sub.1, 11.sub.2 and an interface 12.sub.1, 12.sub.2 for communication with the other party.

[0129] Both parties P.sub.1 and P.sub.2 may be engaged into a method for executing a cryptographic calculation comprising the calculation of a function F which is obtained by applying to a set of n sub-functions f.sub.i of a same mathematical operation, called first operation, wherein the sub-functions f.sub.i are with several variables, n is a positive integer corresponding to the number of sub-functions in the function f, and i is a mute index with values from 1 to n.

It may be noted that F=f.sub.1opf.sub.2op . . . opf.sub.n, wherein op is the first operation.

[0130] The first operation is for example a sum or a product, i.e. the function F is respectively written either as a sum, or as a product, of n sub-functions f.sub.i. In particular, each sub-function f.sub.i is a function of two variables X and Y with n components x.sub.i, y.sub.i.

[0131] In the case when F is written as a sum of sub-functions f.sub.i, it is noted that:

[00001]$F\left(X,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math.f_i\left(x_i,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math.f_i\left(y_i,X\right)$

with x.sub.i, y.sub.i, being the integer components of the variables X and Y.

[0132] In the case when F is written as a product of sub-functions f.sub.i, it is noted that:

[00002]$F\left(X,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.f_i\left(x_i,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.f_i\left(y_i,X\right)$

with x.sub.i, y.sub.i, being the integer components of the variables X and Y.

[0133] The sub-functions of x.sub.i, Y and of y.sub.i, X may be different so as to be able to have an expression of F such that:

[00003]$F\left(X,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.f_i\left(x_i,Y\right)=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.g_i\left(y_i,X\right)$

Also, the number of components of x.sub.i and y.sub.i, and therefore of sub-functions f.sub.i and g.sub.i may be two different numbers. The method applies in this case in the same way by means of a taking into account of the differences of sub-functions and the number of components.

[0134] However, subsequently, the simplified case when the sub-functions are identical, will be assumed, and the numbers of components of the data are also identical.

[0135] The function F may also be a fraction for which the numerator and the denominator are each obtained by applying the first operation with n sub-functions. In this case, and as this is seen hereafter, the method is applied twice, once for calculating the numerator, and once for calculating the denominator.

[0136] The function F is with values in the set .sub.m of the integers comprised between 0 and m−1, wherein m is a positive integer, and is further prime, for the reasons explained hereafter. Further, the function F is with values in the sub-set of .sub.m of the invertible elements for the first operation.

[0137] This means that, in the case when the function F is written as a product of n sub-functions f.sub.i, this function has values in the set .sub.m* of the integers comprised between 1 and m−1, with m also being a prime number. In other words, the f.sub.i(x.sub.i, Y) and the f.sub.i(y.sub.i,X) are advantageously all different from 0. This gives the possibility of improving the safety of the method for the reasons detailed hereafter.

[0138] The data processing method which will be described hereafter may notably be applied to a context of authentication of individuals, notably biometric authentication, when the function F is written as a sum of the sub-functions f.sub.i. The authentication system of FIG. 4 is illustrated in such a context and as a non-limiting example.

[0139] An authentication method comprises a comparison of an identity datum of a candidate individual with a datum of a reference individual for detecting matching between the data and detecting that the individual is the reference individual.

[0140] In this context, a party P.sub.1 may be a control unit of a candidate individual, for example comprising a means 13 for acquiring an identity datum of the individual. This identity datum is advantageously a biometric datum, i.e. a digital datum coded on a biometric trait of an individual.

The relevant biometric traits may typically comprise fingerprints, iris images, shape of the face, etc.

[0141] In this case, the means for acquiring an identity datum of the control server is advantageously a biometric datum sensor (for example, but not in a limiting way, a fingerprint sensor) or an identity document reader in which a biometric datum has been recorded beforehand, for example by being stored in memory in an electronic chip integrated to the document or printed on the document.

[0142] The other party P.sub.2 may be a unit comprising at least one identity datum of a reference individual, for example stored in its memory 11.sub.2.

[0143] The function F may then be a function for comparing identity data of individuals, and in particular may be selected from the following group: [0144] Hamming distance, defined by F(X, Y)=Σ.sub.i=1.sup.n x.sub.i⊕y.sub.i, [0145] normalized Hamming distance, defined by

[00004]$F\left(X,Y\right)=\frac{\underset{i=1}{\overset{n}{.Math.}}.Math.\left(m_i.Math.m_i^{\prime }\left(x_i\oplus y_i\right)\right)}{\underset{i=1}{\overset{n}{.Math.}}.Math.\left(m_i.Math.m_i^{\prime }\right)},$ [0146] wherein M=(m.sub.1, . . . m.sub.n) and M′(m′.sub.1, . . . , m′.sub.n) are masking vectors respectively associated with the vectors X and Y, the bits of which equal to 1 indicate the bits of the same index of the vectors X and Y to be taken into account for calculating the Hamming distance, and [0147] the scalar product, defined by F(X, Y)=Σ.sub.i=1.sup.nx.sub.i y.sub.i.

[0148] During a method for authenticating an individual, the portions P.sub.1 and P.sub.2 are engaged into the calculation of the function F selected from among this group by following the method described hereafter for evaluating a similarity level between an identity datum of the individual and an identity datum of the reference individual.

[0149] If the similarity level is less than a predetermined threshold, the identity data of the candidate individual and of the reference individual are considered as stemming from the same person and the candidate individual is authenticated.

Data Processing Method With reference to FIGS. 1a to 3α, a method for calculating the function F will be described, which may be applied by a system as shown hereinbefore, and which only allows one of the portions to obtain the evaluation of the function F(A,B) with as inputs, the vectors A and B held by the parties, without any party obtaining information on the vector of the other party, even if it has a malicious behavior.

[0150] To do this, the method comprises a first phase 100, illustrated in FIGS. 1a and 1b, comprising the application of a series of determined steps 100.sub.1 in which the first party P.sub.1 has a role of a client and the second party P.sub.2 a role of a server, and the repetition of this series of steps 100.sub.2 by reverting the roles, i.e. the first party P.sub.1 has a role of a server and the second party P.sub.2 has a role of a client.

[0151] Preferably, but not in a limiting way, the application of both series of steps may be achieved simultaneously by the two parties, this in order to shorten the execution period of the method. Alternatively, the series of steps may be applied in succession.

First Phase of the Method

[0152] Subsequently, and for the purpose of conciseness, the series of steps will be described relatively to the roles of the server and of the client without detailing the first phase and then the second phase, since they are symmetrical.

[0153] The vector held by the party having the role of a client is noted as X and the vector held by the party having the role of a server as Y. It is therefore understood that during the application of the first series of steps 100.sub.1, X=A and Y=B, and during the application of the second series of steps 100.sub.2, X=B and Y=A. It is also noted with the indexes 1 and 2, that the applied steps or the data are respectively generated during the first or second series of steps.

[0154] The implementation of each series of steps with the notations specific to each party and each application of the series of steps is nevertheless detailed in FIGS. 1a and 1b.

[0155] Each series of steps 100.sub.1, 100.sub.2 includes a first step 110.sub.1, 110.sub.2 during which the server randomly generates a set of n first masking data indexed as r.sub.i in the set .sub.m. The data r.sub.i are further selected from among the invertible elements in the set .sub.m, for the first operation.

[0156] In other words, if F is a sum of the sub-functions f.sub.i, the data r.sub.i are then invertible for addition, and they are therefore selected from the set .sub.m.

[0157] It is noted that:

∀iε[1,n],r.sub.iε.sub.R.sub.m

[0158] On the other hand, if the function F is a product of the sub-functions f.sub.i, then the data r.sub.i are invertible for multiplication, and they are therefore selected from the set .sub.m* (i.e. .sub.m without the element 0).

[0159] It is noted that:

∀iε[1,n],r.sub.iε.sub.R.sub.m*

[0160] The server also randomly generates a second masking datum α invertible for a second operation, which is different from the first and distributed relatively to the latter. For example, if the first operation is addition, F is a sum of f.sub.i, and the second operation is advantageously multiplication. If the first operation is multiplication, F is a product of f.sub.i, the second operation is advantageously raising to a power.

[0161] In both of these examples, the second masking datum α should be invertible for multiplication in the set .sub.m (since the same inversion criteria apply for multiplication and for raising to a power). It is noted that αε.sub.R*.sub.m.

[0162] In FIGS. 1a and 1b, the index 1 or 2 has further been added to the data r.sub.i and a for indicating that these data are respectively generated during the first or the second application of the series of steps 100 and are therefore not identical (for example α.sub.1≠α.sub.2 and for each i from 1 to n, r.sub.i1≠r.sub.i2). The indexes 1 and 2 are nevertheless omitted in most of the notations hereafter in order not to burden the text.

[0163] The fact that m is a prime number implies that all the elements of the set *.sub.m are invertible for multiplication. Therefore, when the second datum α is randomly selected, no information may be inferred therefrom on the value of this datum.

[0164] As this has been said, in the case of a function F in the form of a fraction of functions, like this is the case, for example, of the normalized Hamming distance (a case not illustrated in FIG. 1α), then at each implementation of step 100, data r.sub.i and a are generated for the numerator, and data r′.sub.i and α′ (having the same properties as the data r.sub.i and a) for the denominator.

[0165] During a step 120.sub.1, 120.sub.2, the server generates from these data and for each sub-function f.sub.i, i.e. for any i from 1 to n, a set of elements, such that each element is formed by a possible result of the function f.sub.i evaluated at the datum of the client (which is therefore unknown to it) and the datum of the server f.sub.i(x.sub.i,Y), masked by a first masking datum r.sub.i and by the second masking datum α.

[0166] The masking by the first masking datum r.sub.i is applied by applying between this datum and the possible result of the function f.sub.i the first operation, i.e. for example summation or multiplication, if F is respectively obtained by summation or multiplication of the sub-functions f.sub.i.

[0167] In the case when F is a sum of f.sub.i, each possible result of the function f.sub.i evaluated at the datum of the client and the datum of the server is added with a first masking datum r.sub.i.

[0168] In the case when F is a product of f.sub.i, each possible result of the function f.sub.i evaluated at the datum of the client and the datum of the server is multiplied by a first masking datum r.sub.i.

[0169] The masking with the second masking datum α is applied by applying, between the result of the function f.sub.i masked by a first masking datum r.sub.i and the second masking datum α, the second operation.

[0170] In particular, in the case when the first operation is a summation, each element of the set generated by the server is a possible result of the function f.sub.i evaluated at the datum of the client and the datum of the server, added with a first masking datum r.sub.i, and multiplied by the second masking datum α:

α(r+f.sub.i(x.sub.i,Y))

[0171] For example, if the function is a sum of sub-functions f.sub.i with two variables and if the data X and Y are binary, the server therefore generates a doublet as follows:

(α(r.sub.i+f.sub.i(0,Y)),α(r.sub.i+f.sub.i(1,Y)))

[0172] In the case when the first operation is a multiplication, the second operation is raising to the power of the second masking datum α.

[0173] Then, each element of the set generated by the server is a possible result of the function f.sub.i evaluated in the datum of the client and the datum of the server, multiplied by a first masking datum τ.sub.i, and raised to the power α:

(r.sub.i.Math.f.sub.i(x.sub.i,Y)).sup.α

[0174] For example, when the function is a product of sub-functions f.sub.i with two variables, and when the data X and Y are binary, the server generates a doublet as follows:

((r.sub.i.Math.f.sub.i(0,Y)).sup.α,(r.sub.i.Math.f.sub.i(1,Y)).sup.α)

[0175] When the function F is a fraction, a set compliant with the preceding description is generated by the server for the numerator, and another one for the denominator.

[0176] According to a particular example, in the case when the function to be evaluated is the normalized Hamming distance, each portion has, in addition to its respective binary datum A, B, a respective masking datum of size n, also binary, and for which the bits set to 1 respectively indicate the bits of the vectors A and B to be taken into account for the calculation of the Hamming distance. The masking datum held by the unit having the role of a server is noted as M=(m.sub.1, . . . m.sub.n) and the masking datum held by the unit having the role of a client is noted as M′=(m′.sub.1, . . . m′.sub.n).

[0177] In FIG. 4, the masking data respectively corresponding to the vectors A and B are indicated by A.sub.M and B.sub.M. Therefore, during the first application of the series of steps 100.sub.1, A.sub.M=M′ and B.sub.M=M, and during the second application of the series of steps 100.sub.2, A.sub.M=M and B.sub.M=M′.

[0178] In this case, for each portion, it is possible to reduce it to a datum of length 2n by considering that a bit of the datum associated with a corresponding bit of the mask set to 0 is zero.

[0179] Thus a datum obtained from X and M′ with a length of 2n is thus posed as X′ and such that x′.sub.i=x.sub.i for i=1 to n and x′.sub.i=m′.sub.i-n for i comprised between n+1 and 2n. The same thing applies mutatis mutandis in order to obtain Y′ from Y and M.

[0180] During step 120, the server generates, as regards the numerator, for all the from 1 to 2n, a set of doublets:

(α(r.sub.i+f.sub.i.sup.num(0,Y′)),α(r.sub.i+f.sub.i.sup.num(1,Y′)))

[0181] Wherein f.sub.i.sup.num designates the numerator of the normalized Hamming distance, for which the values are detailed in paragraph 4.2 of the publication of J. Bringer et al., “GSHADE: Faster Privacy-Preserving Distance Computation and Biometric Identification”, in Proceedings of the 2.sup.nd ACM workshop on Information hiding and multipedia security, 187-198, 2014.

[0182] The server also generates, for the denominator, for all the i from 1 to n, a set of doublets:

(α′r′.sub.i,α′(r′.sub.i+m.sub.i)).

[0183] During step 120, the server thus generates a combination of the possible results of the function F evaluated in the datum of the server and of the client, by masking the results with the r.sub.i and α.sub.i (and if necessary r′.sub.i and α′.sub.i).

[0184] The series of steps then comprises a step 130.sub.1, 130.sub.2 during which the client and the server engage into an oblivious transfer protocol, wherein the client recovers, for each i from 1 to n, one of the elements of the set generated by the server in step 120, indexed with the value of x.sub.i. The oblivious transfer type which is used for this step is preferably a protocol which is secure against malicious parties. This is the case of the oblivious transfer protocols which are described in both of these publications: [0185] Asharov et al., More efficient oblivious transfer and extensions for faster secure computation, In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS '13, Berlin, Germany, Nov. 4-8 2013, pages 535-548, 2013. [0186] Asharov et al., More efficient oblivious transfer extensions with security for malicious adversaries. In Advances in Cryptology—EUROCRYPT 2015-34.sup.th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, Apr. 26-30 2015, Proceedings, Part I, pages 673-701, 2015
The oblivious transfer is schematized in FIGS. 1a and 1b with the acronym “OT”.
In particular, in the case when the server has generated a doublet for each i, if x.sub.i is equal to 0, the client recovers by an oblivious transfer of type 1 from among 2 the first element of the doublet, and if x.sub.i is equal to 1, it recovers the second element of the doublet.

[0187] In a more general case when the datum of the client is expressed in base q, the server will have generated a q-uplet for each i, and the client recovers by an oblivious transfer of type 1 from q the element of the doublet corresponding to the value of x.sub.i between 0 and q−1.

[0188] Thus, the client may recover a datum t.sub.i called an intermediate datum.

The intermediate datum t.sub.i is written as, in the case when the function F is a sum of sub-functions f.sub.i:

t.sub.i=α(r.sub.i+f(x.sub.i,Y))

In the case when the function F is a product of sub-functions f.sub.i, it is written as:

t.sub.i=(r.sub.i.Math.f.sub.i(x.sub.i,Y)).sup.α

[0189] In the example introduced earlier when the function F is the normalized Hamming distance, the client recovers an intermediate datum t.sub.i for the numerator, depending on the value of x′.sub.i as defined hereinbefore, and an intermediate datum t′.sub.i for the denominator, depending on the value of m′.sub.i.

[0190] In FIGS. 1a and 1b, an index 1 or 2 has also been added to the intermediate data t.sub.i depending on whether they are obtained during the first or the second implementation of the phase 100.

[0191] During a step 140.sub.1, 140.sub.2, the server generates from all the first masking data r.sub.i and from the second masking datum a first result portion noted as R.

[0192] This portion R is obtained by applying the first operation—i.e. for example addition or multiplication—to all the first masking data, and by masking them with the second datum α, i.e. by applying to them the second operation with α, for example respectively by multiplying them by α or by raising them to the power α.

[0193] As a summary, in the case when the function F is a sum of the sub-functions f.sub.i, the server generates a result portion R such that:

[00005]$R=\alpha .Math.\underset{i}{\overset{}{.Math.}}.Math.r_i$

In the case when the function F is a product of sub-functions f.sub.i, the server generates a result portion R such that:

[00006]$R={\left(\underset{i=1}{\overset{n}{.Math.}}.Math..Math.r_i\right)}^{\alpha }$

In the case of the calculation of a function as a fraction, the server carries out this operation for the numerator from the data r.sub.i and α in order to obtain a datum R and for the denominator from the data r′.sub.i and α′ in order to obtain a datum R′.

[0194] The step 140 may be applied at any moment after step 110, but not necessarily after step 130.

[0195] Of course, and as visible in FIGS. 1a and 1b, a result portion R (and if required R′) is calculated during each implementation of the phase 100. The result portion calculated during the first implementation of the phase 100 is noted as R.sub.1 and the result portion calculated during the second implementation of the phase 100 is noted as R.sub.2. R.sub.1 and R.sub.2 are different.

[0196] During a step 150.sub.1, 150.sub.2, the client applies the first operation—i.e. for example addition or multiplication—to all the intermediate data t.sub.i so as to obtain a result portion T such that: [0197] If the function F is a sum of sub-functions f.sub.i:

[00007]$T=\underset{i=1}{\overset{n}{.Math.}}.Math.t_i=\underset{i=1}{\overset{n}{.Math.}}.Math.\alpha \left(r_i+f_i\left(x_i,Y\right)\right)=R+\alpha .Math..Math.F\left(X,Y\right)$ [0198] If the function F is a product of sub-functions f.sub.i:

[00008]$T=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.t_i=\underset{i=1}{\overset{n}{.Math.}}.Math..Math.{\left(r_i.Math.f_i\left(x_i,Y\right)\right)}^{\alpha }=R.Math.{F\left(X,Y\right)}^{\alpha }$

As earlier, a result portion T is calculated during each implementation of the phase 100, and in FIGS. 1a and 1b, the result portions respectively obtained during the first and the second implementation, are noted as T.sub.1 and T.sub.2 respectively, T.sub.1 and T.sub.2 being different.

[0199] In the case when the function f is a fraction, this step is applied for the numerator (obtaining a datum T) and for the denominator (obtaining a datum T′) with the respective intermediate data.

[0200] By again taking the indexes 1 and 2 related to the first or second implementation of the phase 100, at the end of the first application of the series of steps, the party P.sub.1 in the role of the client has a datum T.sub.1 and the party P.sub.2 in the role of the server has a datum R.sub.1 giving the possibility of obtaining together a first evaluation of the function F in the data of the client and of the server, masked by the second masking datum α.sub.1, which was randomly generated by the party P.sub.2 as a server, and is therefore unknown to the party P.sub.1.

[0201] In the case when F is a sum of sub-functions, one has

T.sub.1−R.sub.1=α.sub.1F.sub.1(X,Y)

[0202] In the case when F is a product of sub-functions, one has

T.sub.1.Math.R.sub.1.sup.−1=F.sub.1(X,Y).sup.α.sup.1

[0203] At the end of the second application of the series of steps 100.sub.2, the party P.sub.1 in the role of the server has a datum R.sub.2, and the party P.sub.2 in the role of the client has a datum T.sub.2 giving the possibility of obtaining a second evaluation of the function F in the data of the client and of the server, masked by the second masking datum α.sub.2, which was randomly generated by the party P.sub.1 as a server, and is therefore unknown to the party P.sub.2.

[0204] In the case when F is a sum of sub-functions, one has:

T.sub.2−R.sub.2=α.sub.2F.sub.2(X,Y)

[0205] In the case when F is a product of sub-functions, one has:

T.sub.2.Math.R.sub.2.sup.−1=F.sub.2(X,Y).sup.α.sup.2

[0206] The results F.sub.1(X,Y) and F.sub.2(X,Y) are equal and have the value F(A,B) in the absence of any fraud.

[0207] In the case when one of the parties is malicious, for example P.sub.1, it therefore cannot, by modifying the values of the data which it holds, for example T.sub.1, R.sub.2 and α.sub.2, ensure that:

α.sub.2(T.sub.1−R.sub.1)=α.sub.2α.sub.1F.sub.1(X,Y)=α.sub.1(T.sub.2−R.sub.2)=α.sub.1α.sub.2F.sub.2(X,Y)

or that:

(T.sub.1.Math.R.sub.1.sup.−1).sup.α.sup.2=F.sub.1(X,Y).sup.α.sup.1.sup.α.sup.2=(T.sub.2.Math.R.sub.2.sup.−1).sup.α1=F.sub.2(X,Y).sup.α.sup.2.sup.α1

[0208] Returning to step 150, for the case of the generalized Hamming distance, the client separately sums the intermediate data t.sub.i and t′.sub.i obtained for the numerator and the denominator, in order to obtain (indexes 1 and 2 are omitted):

[00009]$T=\underset{i=1}{\overset{n}{.Math.}}.Math.t_i=R+\alpha .Math..Math.\left(X\oplus Y\right).Math.M.Math.M^{\prime }.Math.$$T^{\prime }=\underset{i=1}{\overset{n}{.Math.}}.Math.{t^{\prime }}_i=R^{\prime }+{\alpha }^{\prime }.Math..Math.M.Math.M^{\prime }.Math.$

Therefore, subsequently to both implementations of the phase 100, the following relationships are obtained:

[00010]${{\alpha }_1\left({\alpha }_1^{\prime }\right)}^{-1}.Math.F_1\left(X,Y\right)=\frac{T_1-R_1}{T_1^{\prime }-R_1^{\prime }}$${{\alpha }_2\left({\alpha }_2^{\prime }\right)}^{-1}.Math.F_2\left(X,Y\right)=\frac{T_2-R_2}{T_2^{\prime }-R_2^{\prime }}$

[0209] As earlier, by means of the multiplication during each series of steps by a value α.sub.1, α′.sub.1, α.sub.2 or α′.sub.2 which is random and specific to a party, a malicious party, for example P.sub.1 cannot modify the elements which it holds, i.e. T.sub.1, T′.sub.1, R.sub.2, R′.sub.2 and α.sub.2 and α′.sub.2, in order to ensure that:

[00011]$\begin{array}{cc}{{\alpha }_1\left({\alpha }_1^{\prime }\right)}^{-1}.Math.{{\alpha }_2\left({\alpha }_2^{\prime }\right)}^{-1}.Math.F_2\left(X,Y\right)=\frac{{\alpha }_1}{{\alpha }_1^{\prime }}.Math.\frac{T_2-R_2}{T_2^{\prime }-R_2^{\prime }}={{\alpha }_1\left({\alpha }_1^{\prime }\right)}^{-1}.Math.{{\alpha }_2\left({\alpha }_2^{\prime }\right)}^{-1}.Math.F_1\left(X,Y\right)=\frac{{\alpha }_2}{{\alpha }_2^{\prime }}.Math.\frac{T_1-R_1}{T_1^{\prime }-R_1^{\prime }}& \end{array}$

Equality Test

[0210] At the end of the phase 100, the method comprises an equality test 200 for the values of F.sub.1(X,Y) and F.sub.2(X,Y) which may be inferred from each series of steps of the phase 100. In order that this equality test 200 does not reveal any information on the value of F (X,Y) before having verified the equality, it comprises the two following steps: [0211] A first step 210 consists of “pledging” or achieving a “commitment” of the whole of the outputs of both series of steps of the phase 100, i.e. T.sub.1, R.sub.1, α.sub.1, and T.sub.2, R.sub.2, α.sub.2.
Pledging is a conventional operation in cryptography consisting of generating from a datum, a ciphering function and a key, a value not providing any information on the initial datum. Further, it guarantees that during the “decommitment” operation, which consists of finding again the initial datum from the value of the key and from a suitable deciphering function, the initial datum obtained at the end of the decommitment has not been altered. Step 210 therefore gives the possibility of ensuring that during the equality test, no output of the series of steps of phase 100 is altered. [0212] A second step 220 is a verification of the equality of the values of F.sub.1(X,Y) and F.sub.2(X,Y) without a party obtaining any information on the result F(X,Y).
As a non-limiting example, an equality test protocol possible for this phase 200 is described hereafter and with reference to FIG. 2.

[0213] During this protocol, the party P.sub.1 has as inputs, the data T.sub.1, R.sub.2 and α.sub.2 and the party P.sub.2 has as inputs, the data R.sub.1, T.sub.2 and α.sub.1 stemming from the first phase 100.

[0214] The protocol comprises a first pledging step 210 during which the party P.sub.1 pledges, by means of random keys K.sub.1, K.sub.2, K.sub.3 its data T.sub.1, R.sub.2 and α.sub.2 respectively in order to obtain three tokens c.sub.1, c.sub.2, c.sub.3 respectively defined by:

c.sub.1=Com(T.sub.1,K.sub.1)

c.sub.2=Com(R.sub.2,K.sub.2)

c.sub.3=Com(α.sub.2,K.sub.3)

[0215] The party P.sub.1 sends the tokens to the party P.sub.2. In the case when the calculated function is the generalized Hamming distance, the data T′.sub.1, R′.sub.2 and α′.sub.2 are pledged with other random keys, and the obtained tokens are also send to the other portion.

[0216] On its side, the party P.sub.2 pledges, by means of random keys K.sub.4, K.sub.5, K.sub.6, its data R.sub.1, T.sub.2 and α.sub.1 respectively in order to obtain three tokens c.sub.4, c.sub.5, c.sub.6 respectively defined by:

c.sub.4=Com(R.sub.1,K.sub.4)

c.sub.5=Com(T.sub.2,K.sub.5)

c.sub.6=Com(α.sub.1,K.sub.6)

[0217] The party P.sub.2 sends the tokens to the party P.sub.1. In the case when the calculated function is the generalized Hamming distance, the data T′.sub.2, R′.sub.1 and α′.sub.1 are pledged with other random keys, and the obtained tokens are also send to the first party P.sub.1.

[0218] The step 220 for verifying the equality of the values of F.sub.1(X,Y) and F.sub.2(X,Y) obtained during the phase 1 may then be applied as follows, according to a non-limiting example.

[0219] The first party P.sub.1 sends to the second party P.sub.2, the datum R.sub.2 and the key K.sub.2. The party P.sub.2 may therefore achieve decommitment of the R.sub.2 datum, Decom(c.sub.2, K.sub.2), and verify that it corresponds to the transmitted datum, and therefore that the party P.sub.1 has not been modified. If there exists a difference between the datum R.sub.2 transmitted by P.sub.1 and its decommitment from K.sub.2, the protocol stops, a fraud is detected.

[0220] Next, the second party P.sub.2 sends to the first party P.sub.1 the datum R.sub.1 and the key K.sub.4. The party P.sub.1 may achieve decommitment of the datum R.sub.1, Decom(c.sub.4, K.sub.4), and verify that it corresponds to the transmitted datum. If there exists a difference between the datum R.sub.1 transmitted by P.sub.2 and its decommitment from K.sub.4, the protocol stops, a fraud is detected.

[0221] In the case of a function F in the form of a fraction of functions, the verification of equality is achieved by separately verifying the equality of the numerators and of the denominators.

[0222] In FIG. 2α, in the case when the function F is a sum of sub-functions f.sub.i, the party P.sub.1 and the party P.sub.2 are then able to respectively calculate the values α.sub.1α.sub.2F.sub.1(X, Y) and α.sub.1α.sub.2F.sub.2(X, Y) (through α.sub.2(T.sub.1−R.sub.1) and α.sub.1(T.sub.2−R.sub.2)).

[0223] The following notations are used H.sub.1=Hash(α.sub.1α.sub.2F.sub.1(X, Y)) and H.sub.2=Hash(α.sub.1α.sub.2F.sub.2(X, Y)) wherein Hash is a hash function.

[0224] A portion first sends one of H.sub.1 or H.sub.2 to the other portion, which compares one of the received H.sub.1 or H.sub.2 with the other one which it held previously. If H1≠H2, the portion having carried out the comparison stops the protocol. Otherwise, as this portion only has hashed data, it cannot infer therefrom the value of the function F evaluated in X and Y.

[0225] Then this portion sends the one which it holds from α.sub.1α.sub.2F.sub.2(X,Y) and α.sub.1α.sub.2F(X, Y) to the other portion. The portion having for example received α.sub.1α.sub.2F.sub.2(X, Y) compares it with α.sub.1α.sub.2F(X, Y) which it already held (or vice-versa) in order to check equality between both terms. If this is not the case, the portion stops the protocol.

[0226] Otherwise, both parties were able to verify whether F.sub.1(X,Y)=F.sub.2(X,Y) while ensuring that the portion has not altered the integrity of the data.

[0227] In FIG. 2b, in the case when the function F is a product of sub-functions f.sub.i, the party P.sub.1 and the party P.sub.2 are able to calculate (F.sub.1(X,Y)).sup.α.sup.1.sup.α.sup.2 and (F.sub.2(X,Y)).sup.α.sup.1.sup.α.sup.2 (through (T.sub.1R.sub.1.sup.−1).sup.α.sup.2 and (T.sub.2R.sub.2.sup.−1).sup.α.sup.1)

[0228] The following notations are used H′.sub.1=Hash((F.sub.1(X,Y)).sup.α.sup.1.sup.α.sup.2) and H′.sub.2=Hash((F.sub.2(X, y)).sup.α.sup.1.sup.α.sup.2) wherein Hash is a hash function.

[0229] A portion sends one of H′.sub.1 or H′.sub.2 to the other portion, which compares H′.sub.1 and H′.sub.2, and stops the protocol if a difference exists.

[0230] Otherwise, it then sends to the other portion one of (F.sub.2(X,Y)).sup.α.sup.1.sup.α.sup.2 and (F.sub.1(X, y)).sup.α.sup.1.sup.α.sup.2.

[0231] The portion having (F.sub.2(X,Y)).sup.α.sup.1.sup.α.sup.2 and (F.sub.1(X,Y)).sup.α.sup.1.sup.α.sup.2 compares them, and if there is a difference, it stops the protocol. Thus, both parties may check whether F.sub.1(X,Y)=F.sub.2(X,Y) while guaranteeing the integrity of the data.

[0232] If a portion ascertains that F.sub.1(X,Y)≠F.sub.2(X,Y), then the protocol stops and a fraud is detected.

At the end of the equality test, if the equality of the values of F.sub.1(X,Y) and F.sub.2(X,Y) was verified and confirmed, then one of the two portions may calculate F(X,Y) during a step 300.

[0233] For example, a portion may either use its datum T.sub.i (T.sub.2 respectively) and recover R.sub.1 (R.sub.2 respectively) and α.sub.1 (α.sub.2 respectively) from the other portion, or use its data R.sub.1 (R.sub.2 respectively) and α.sub.1 (α.sub.2 respectively) and recover the datum T.sub.1 (T.sub.2 respectively) held by the other portion, in order to infer F(A,B) therefrom.

[0234] According to an advantageous alternative in terms of safety, the portion may use a datum of the other portion which it has already received during the method (in this case, R.sub.1 or R.sub.2), and also use the two other parameters T.sub.1, α.sub.1 or T.sub.2, α.sub.2 held by the other party and which it has not recovered.

[0235] Indeed, the portion may also recover the pledging tokens of the corresponding parameters and verify the integrity from the tokens.

Inference of F(A,B) is accomplished, when F is a sum of sub-functions, by the operation:

F(A,B)=α.sub.1.sup.−1(T.sub.1−R.sub.1)

or

F(A,B)=α.sub.2.sup.−1(T.sub.2−R.sub.2)

Inference of F(A,B) is accomplished, when F is a product of sub-functions, by the operation:

[00012]$F\left(A,B\right)={\left(T_1.Math.R_1^{-1}\right)}^{\frac{1}{a_1}}$$\mathrm{or}$$F\left(A,B\right)={\left(T_2.Math.R_2^{-1}\right)}^{\frac{1}{a_2}}$

[0236] In the case when the calculated function is a fraction of functions, the calculation of F(A,B) is accomplished by first calculating the numerator, and then the denominator of the function.

[0237] The result of the function evaluated in A and B is therefore held by one of the parties without any portion having revealed any information to the other portion on the datum which it holds.

[0238] In FIG. 3b, in the case when the calculation of the function F is applied during a method for authenticating an individual, the result F(A,B) may be compared with a predetermined threshold during a step 400. For example, in the case when the function is a Hamming distance, the result may be less than a determined threshold so that the data are considered as stemming from the same person.

[0239] If the result of the comparison indicates that the data A and B stem from the same person, the individual is authenticated as the reference individual during a step 500. Otherwise, warning steps may be applied by one of the parties, for example by means of the display of a message, of the generation of an audio alarm, etc.