# US 10,375,066 B2 · Authentication method and system by garbled circuit

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,375,066 B2
- Document ID: US10375066B2
- Status: Granted
- Kind: B2
- Application number: 15/648,300
- Filed: 2017-07-12
- Published: 2018-01-18
- Granted: 2019-08-06
- Earliest claimed: 2016-07-13
- Assignees: Idemia Identity & Security
- Applicants: Safran Identity & Security
- Inventors: Herve Chabanne; Constance Morel
- Web page: https://patentgrep.com/patent/US10375066B2

## CPC

- H04L 63/0861: {using biometrical features, e.g. fingerprint, retina-scan (cryptographic mechanisms or cryptographic arrangements for entity authentication using biological data H04L9/3231)}
- H04L 9/3231: {Biological data, e.g. fingerprint, voice or retina (network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861)}
- H04L 63/061: {for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838)}
- H04L 2209/16: Obfuscation or hiding, e.g. involving white box
- H04L 2209/50: Oblivious transfer
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

the invention proposes a method and an associated system for authenticating a user, by means of the redundancy present between several images of a video, the method using garbled circuits, named variant garbled circuits, associated with the alternative bits between the images of the video and a garbled circuit named invariant garbled circuit, associated with the invariant bits between the images of the video, so that the invariant garbled circuit only needs to be evaluated a single time.

## Claims

### Claim 1

A method for authenticating a user comprising:
a first client unit comprising a memory in which is stored a reference biometric datum (b),
a second client unit acquiring at least one test biometric datum (b′), and
a server, generating garbled circuits (GC) for evaluating functions, each garbled circuit (GC) having as inputs a set of encryption keys of input data bits of the function to be evaluated and as an output the encryption keys corresponding to the bits of the result of the evaluated function, and wherein the steps for calculating the function are broken down into the form of elementary logical operations, each garbled circuit further comprising a set of encoding keys of each of the possible inputs and outputs of each elementary logic operation,
the method comprising the comparison of a number C of test data (b′1, . . . , b′C) acquired on the user by the second client unit with the reference datum, said comparison comprising the calculation, by means of garbled circuits, of a distance between the reference datum (b) and each test datum (b′1, . . . , b′C),
wherein the comparison comprises the application of the following steps:
(E3, F3) from a set S comprising indices of the test data (b′1, . . . , b′C), such that the value of the bit of each test datum associated with an index of the set S is invariant on the whole of the C test data (b′1, . . . , b′C), the server breaks down the function to be evaluated into:
a sub-function ƒS which comprises all the logical operations for which the output exclusively depends on input bits for which the index belongs to said set S and generates for the evaluation of this sub-function ƒS a single garbled circuit (GCS) a garbled circuit, named invariant garbled circuit,
a sub-function ƒS which comprises all the logical operations of the function f non-evaluated by the sub-function ƒS and generates, for each of the C test data (b′1, . . . , b′C), a garbled circuit, named variant garble circuit (GC1S, . . . , GCCS), for evaluation of the sub-function ƒS,
(E4, F4) the server randomly generates encoding keys (kS, k1S, . . . , kCS) for the single invariant garbled circuit (GCS) and for the C variant garbled circuits (GC1S, . . . , GCCS),
(E5, F5) the server sends the garbled circuits (GCS,GC1S, . . . ,GCCS,) to one of the client units,
(E6, F6) both client units recover from the server by oblivious transfer (OT):
encoding keys (kb, kb′) corresponding to the values of the input bits of the function (f) to be evaluated depending on the reference data (b) and on the C test data (b′) respectively at their disposal, the first client unit recovering a set of keys (kb) relative to the reference biometric datum (b) and the second client unit recovering a set of keys (kb′) comprising a key for each bit associated with an index belonging to the set S and C keys for each bit associated with an index not belonging to S, and
(E7, F7) the client unit having received the garbled circuits recovers the encoding keys (kb, kb′) from the other client unit, and (E8, F8) evaluates the function (f) for each of the C test data, with as inputs the recovered keys, by executing the garbled circuits (GCS, GC1S, . . . , GCCS)
(E9, F9) depending on said evaluations of f, either authentication or not of the user or of the object.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the set (S) of indices is determined in a preliminary step (E1) by the second client unit by analysis of the invariant bits between the C test data (b′1, . . . , b′C).

### Claim 3 (depends on 1)

The method according to claim 1, wherein
the set (S) of indices comprises a set number of indices (L-5|Smax|), the indices being selected in any way,
the second client unit applies an permutation (π) to the invariant bits of each datum (b′i) between the C test data so that said indices of said invariant bits match to the indices of the set of indices (S), and
the encoding keys are recovered for the permuted bits.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the set number of indices of the set of indices (S) is determined beforehand by a database analysis, the set number of indices of the set of indices being selected so as to be less than the actual number of invariant bits between the C test data.

### Claim 5 (depends on 3)

The method according to claim 3, wherein the steps for breaking down the function to be evaluated, for generating the encoding keys and for sending garbled circuits to one of the client units are applied before acquiring the test data or before applying the permutation to said data.

### Claim 6 (depends on 1)

The method according to claim 1, wherein both client units form a single client terminal.

### Claim 7 (depends on 1)

The method according to claim 1, wherein the server and one of the two client units form a single entity, and wherein the other client unit receives the garbled circuits.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the server also sends to the client unit a matching table (T) of the outputs of each garbled circuit (C), so that the client unit which evaluates the function f may determine the value of the output keys of the evaluation (kouti).

### Claim 9 (depends on 1)

The method according to claim 1, further comprising a step during which the client unit having evaluated the function send to the server the output keys of the evaluation (kouti) and the server infers therefrom, from the matching table of the outputs of each garbled circuit, the evaluations of the function f.

### Claim 10 (depends on 1)

The method according to claim 1, wherein the data (b, b′1, . . . , b′C) are iris binary codes.

### Claim 11 (depends on 1)

The method according to claim 1, wherein the function (f) to be evaluated comprises the calculation of the normalized Hamming distance between the reference biometric datum (b) and each of the C biometric test data (b′1, . . . , b′C) and comprises the comparison of this distance with a threshold (t).

### Claim 12 (depends on 1)

The method according to claim 1, wherein the invariant garbled circuit (GCS) is evaluated only once for the C test data.

### Claim 13

A system for authentication of individuals, comprising:
a first client unit comprising a memory,
a second client unit acquiring at least one test datum (b′1, . . . , b′C), and
a server, generating garbled circuits (GC) for evaluating functions (f), each garbled circuit (GC) having as inputs a set of encryption keys for input data bits of the function (f) to be evaluated and as output, the encryption keys corresponding to the bits of the result of the evaluated function (f), and wherein the steps for calculating the function (f) are broken down into the form of elementary logic operations, each garbled circuit further comprising a set of encoding keys (k) of each of the possible inputs and outputs of each elementary logical operation,
wherein the system applies the method comprising the comparison of a number C of test data (b′1, . . . , b′C) acquired on the user by the second client unit with the reference datum, said comparison comprising the calculation, by means of garbled circuits, of a distance between the reference datum (b) and each test datum (b11. . . b′C),
wherein the comparison comprises the application of the following steps:
(E3, F3) from a set S comprising indices of the test data (b′1, . . . , b′C), such that the value of the bit of each test datum associated with an index of the set S is invariant on the whole of the C test data (b′1, . . . , b′C), the server breaks down the function to be evaluated into:
a sub-function ƒS which comprises all the logical operations for which the output exclusively depends on input bits for which the index belongs to said set S and generates for the evaluation of this sub-function ƒS a single garbled circuit (GCS) a garbled circuit, named invariant garbled circuit,
a sub-function ƒS which comprises all the logical operations of the function f non-evaluated by the sub-function ƒS and generates, for each of the C test data (b′1, . . . , b′C), a garbled circuit, named variant garble circuit (GC1S, . . . , GCCS), for evaluation of the sub-function ƒS,
(E4, F4) the server randomly generates encoding keys (kS, K1S, . . . , kCS) for the single invariant garbled circuit (GCS) and for the C variant garbled circuits (GC1S, . . . , GCCS),
(E5, F5) the server sends the garbled circuits (GCS,GC1S,. . .,GCCS,) to one of the client units,
(E6, F6) both client units recover from the server by oblivious transfer (OT):
encoding keys (kb, kb′) corresponding to the values of the input bits of the function (f) to be evaluated depending on the reference data (b) and on the C test data (b′) respectively at their disposal, the first client unit recovering a set of keys (kb) relative to the reference biometric datum (b) and the second client unit recovering a set of keys (kb′) comprising a key for each bit associated with an index belonging to the set S and C keys for each bit associated with an index not belonging to S, and
(E7, F7) the client unit having received the garbled circuits recovers the encoding keys (kb, kb′) from the other client unit, and (E8, F8) evaluates the function (f) for each of the C test data, with as inputs the recovered keys, by executing the garbled circuits (GCS, GC1S, . . . , GCCS)
(E9, F9) depending on said evaluations of f, either authentication or not of the user or of the object.