Identification method of an entity

A computer program product comprising a non-transitory computer readable storage medium having computer readable program code instructions embodied therewith that when executed by a processor of a computer causes the computer to perform an identification method of an entity comprising:

• 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:
• an initialisation step comprising:
• determining a list of data to be processed, said list of data to be processed comprising said indexed distance data,
• determining a remaining number of indexed distance data to be set aside I, 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 of indexed distance data comprised in said list of 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:
• comparing 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 I,
• 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,
• searching 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 I:
• removing from said list of data to be processed, data wherein the indices belong to the first group and,
• determining a new remaining number of indexed data to be set aside I by subtracting from the remaining number of indexed data to be set aside I the number of indices of the first group (p);
• else:
• removing from said list of data to be processed, indexed distance data wherein 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, and
• adding 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, said execution step being carried out securely between the control server and the management server by a secure multi party computation protocol for secure evaluation of said Boolean circuit,
• said identification method further comprising:
• 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 belonging 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 I of length equal to the number of indexed distance data (n), the value of the ith bit of said marker indicating belonging or not belonging 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 comprising:
• determining 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 dij 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 I, 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 d1j) AND bi.

An identification system of an entity comprising a management server connected to a storage device storing indexed reference biometric data (Y1, . . . , Yn) corresponding to reference entities and a control server acquiring a biometric datum of the entity to be identified (X), said management server and said control server sharing indexed distance data (d1, . . . , dn), such that none of said distance data is known to the management server or the control server, 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,

• wherein:
• said control server and said management server comprise a processor configured to execute the phases and steps of an identification method comprising:
• 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:
• an initialisation step comprising:
• determining a list of data to be processed, said list of data to be processed comprising said indexed distance data,
• determining a remaining number of indexed distance data to be set aside I, 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 of indexed distance data comprised in said list of 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:
• comparing 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 I,
• 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,
• searching 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 I:
• removing from said list of data to be processed, data wherein the indices belong to the first group and,
• determining a new remaining number of indexed data to be set aside I by subtracting from the remaining number of indexed data to be set aside I the number of indices of the first group (p);
• else:
• removing from said list of data to be processed, indexed distance data wherein 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, and
• adding 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, said execution step being carried out securely between the control server and the management server by a secure multi party computation protocol for secure evaluation of said Boolean circuit,
• said identification method further comprising:
• 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 belonging 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 I of length equal to the number of indexed distance data (n), the value of the ith bit of said marker indicating belonging or not belonging 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 comprising:
• determining 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 dij 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 I, 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 [(d1j 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 d1j) AND bi.