IDENTIFICATION METHOD OF AN ENTITY

摘要

The present invention relates to identification method of an entity executed by an identification system from indexed distance data (d1, . . . , dn) corresponding to reference entities and comprising:
a determination phase of a set (I) of indices of minima (index1, . . . , indexk) from said indexed distance binary data of length q′ comprising an execution step comprising,for each set of jth bits of indexed distance data contained in a list of data to be processed, j being an integer varying from q′−1 to 0, starting by the set of most significant bits of the data to be processed and finishing by the set of least significant bits of the data to be processed,the search of indices of minima comprising, if a number of indices of a first group of indices of indexed distance data (p) is greater than a remaining number of indexed data to be set aside (r), addition of said indices of a second group to the set of indices of minima;an identification phase of the entity to be identified from the reference entities corresponding to the stored reference biometric data determined associated with the indices of minimal distance data (index1, . . . , indexk), the operations on binary integers for conducting at least said execution step, being translated in the form of at least one Boolean circuit used to execute at least said execution step securely between the control server and the management server by means of a secure multi party computation protocol enabling secure evaluation of said Boolean circuit.

主权项

1. An identification method of an entity,
executed by an identification system comprising a management server likely to be connected to a storage device storing indexed reference biometric data (Y1, . . . , Yn) corresponding to reference entities and a control server likely to acquire a biometric datum of the entity to be identified (X), said management server and said control server being likely to be connected together, from indexed distance data (d1, . . . , dn), said indexed distance data being distances calculated from the stored indexed reference biometric data and the acquired biometric datum of the entity to be identified, said indexed distance data being shared between said control server and said management server such that none of said distance data is known to the management server or the control server, said indexed distance data being binary integers of length q′, said identification method being characterized in that it comprises:
a determination phase of a set of indices of minima (index1, . . . , indexk), said set of indices of minima comprising at most a predetermined number of indices of minimal distance data from said indexed distance data, said determination phase comprising: previously, an initialisation step during which:
a list of data to be processed is determined, said list of data to be processed comprising said indexed distance data,a remaining number of indexed distance data to be set aside (r) is determined, said remaining number of indexed distance data to be set aside being equal to the difference between the number of indexed distance data (n) and the predetermined number of indices (k),an execution step comprising,for each set of jth bits, so-called current bits, of indexed distance data comprised in said list of data to be processed, so-called data to be processed, j being an integer varying from q′−1 to 0,performing the following steps,starting by the set of most significant bits of the data to be processed and finishing by the set of least significant bits of the data to be processed:
comparison of a number of indices of a first group of indices of indexed distance data (p) to the remaining number of indexed data to be set aside (r),said first group of indices comprising the indices of the indexed distance data from said list of data to be processed for which said current bit is equal to 1,search of indices of minima comprising:
if the number of indices of the first group (p) is less than the remaining number of indexed data to be set aside (r):removal, from said list of data to be processed, of data whereof the indices belong to the first group and,determination of a new remaining number of indexed data to be set aside (r) by subtracting from the remaining number of indexed data to be set aside (r) the number of indices of the first group (p);else:removal, from said list of data to be processed, of indexed distance data whereof the indices form part of a second group of indices of indexed distance data,said second group comprising the indices of the indexed distance data from said list of data to be processed for which said current bit is equal to 0, andaddition of said indices of the second group to the set of indices of minima;an identification phase of the entity to be identified from the reference entities corresponding to the stored reference biometric data associated with the indices of minimal distance data (index1, . . . , indexk) determined during the determination phase, the operations on binary integers for implementing at least said execution step of said identification method, being translated in the form of at least one Boolean circuit, said Boolean circuit being then used to execute at least said execution step of said method, this execution being carried out securely between the control server and the management server by means of a secure multi party computation protocol for secure evaluation of said Boolean circuit, said identification method further being characterized in that:
belonging of the indexed distance data to said list of data to be processed is stored in the form of a marker of data to be processed, said marker of data to be processed being a binary integer (b) of length equal to the number of indexed distance data (n) and the value of the ith bit of said marker indicating belonging or not of the ith indexed distance datum to said list of data to be processed, belonging of indices of indexed distance data to the set of indices of minima is stored in the form of a minima marker, said minima marker being a binary integer (c) of length equal to the number of indexed distance data (n), the value of the ith bit of said marker indicating belonging or not of the index i to the set of indices of minima, the number of indexed distance data d1, . . . , dn being equal to n:
the initialisation step further comprises initialisation of all the bits of the marker of data to be processed b and of the minima marker c at the value 1,the comparison step comprises steps of:
determination of the number (p) of indices of the first group by counting the number of elements equal to the value 1 from the set (d1j AND b1, . . . , dnj AND bn), the notation d representing the value of the jth bit of the indexed index distance datum i,if the number (p) of indices of the first group is less than the remaining number of indexed data to be set aside (r), setting of a comparison bit e at the value 1,else, setting of said comparison bit e at the value 0,the search step is conducted by:
updating of the remaining number of indexed data to be set aside r, the remaining number of indexed data to be set aside r being replaced by the value [((r−p) XOR r) AND e]XOR r,updating of each bit of the minima marker c, each ith bit ci of the minima marker c being replaced by the value [(dij OR e) OR (bi XOR 1)]AND ci,updating of each bit of the marker of data to be processed b, each ith bit bi of the marker of data to be processed b being replaced by the value (e XOR dij) AND bi.