Process for obtaining candidate data from a remote storage server for comparison to a data to be identified
The invention presents a process for obtaining candidate reference data to compare to a data to be identified, implemented in a system comprising a client unit and a storage server comprising two databases, in which: —the first database comprises indexed memory blocks each comprising a corresponding encrypted indexed reference data, and —the second database comprises memory blocks indexed by all possible hash values obtained by a plurality of k indexed hash functions, and wherein each block contains a list of the indexes of the reference data which hashing by one of said hash function results in the hash value corresponding to said block, said process comprising the steps during which: —the client unit hashes the data to be identified with each of the plurality of hash functions, and reads the k memory blocks of the second database corresponding to the hash values thus obtained, the client unit identifies indexes contained in at least t out of k read memory blocks, and —the client unit reads the memory blocks of the first database indexed by the identified indexes in order to obtain the corresponding indexed reference data, said data being candidate data to compare to the data to be identified, the steps of reading memory blocks of the databases being carried out by executing a protocol preventing the storage server from learning which memory blocks of the databases are read. Another object of the invention is a system for the secure comparison of data.
1. A process for obtaining candidate reference data to compare to a data to be identified, implemented in a system comprising a client unit and a storage server comprising two databases (DB 1 , DB 2 ), in which:
the first database (DB 1 ) comprises a plurality of indexed memory blocks each comprising a corresponding encrypted indexed reference data (b i ), and
the second database (DB 2 ) comprises memory blocks indexed by all possible hash values obtained by a plurality of k indexed hash functions (H j ), and wherein each block contains a list of the indexes of the reference data (b i ) which hashing (H j (b i )) by one of said hash function (H j ) results in the hash value corresponding to said block,
said process comprising the steps during which:
the client unit hashes the data (b) to be identified with each of the plurality of hash functions (H j ), and reads the k memory blocks of the second database (DB 2 ) corresponding to the hash values thus obtained,
the client unit identifies indexes (i 1 , . . . i 1 ) contained in at least t out of k read memory blocks, and
the client unit reads the memory blocks of the first database (DB 1 ) indexed by the identified indexes (i 1 , . . . i 1 ) in order to obtain the corresponding indexed reference data (b i1 , . . . b i1 ), said data being candidate data to compare to the data to be identified,
the client unit decrypts the candidate reference data and compares each of said reference data (b i1 , . . . b i1 ) to the data (b) to be identified in order to detect a matching between the data (b) and one reference data,
wherein the steps of reading memory blocks of the databases are carried out by executing an oblivious RAM protocol preventing the storage server ( 10 ) from learning which memory blocks of the databases are read.
2. A process according to claim 1 , characterized in that the storage server and the client unit are configured to execute a distinct instance (ORAM 1 , ORAM 2 ) of an oblivious RAM protocol for each database (DB 1 , DB 2 ), and in that the steps of reading memory blocks of the database are carried out using said Oblivious RAM protocol instances.
3. A process according to claim 1 , wherein reference data (b i ) and the data (b) to be identified are biometric data, and a matching between the data (b) and a reference data (b i ) leads to identifying the person to whom belongs the data to be identified to the person to whom belongs the reference data.
4. A process according to claim 3 , wherein the reference data (b i ) and the data (b) to be identified are iris codes, the hash functions are projections of the iris codes on smaller bits sequences, and the comparison between the data to be identified and each reference data is carried out by computing the Hamming distance between said data.
5. A process according to claim 1 , wherein the hash functions (H j ) are of the locality-sensitive type, and all the hash values obtained by the hash functions (H j ) are bits sequences which length m is strictly inferior to the length n of each reference data.
6. A storage server ( 10 ), comprising:
a first database (DB 1 ) that comprises a plurality of indexed memory blocks each comprising a corresponding encrypted indexed reference data (b i ), and
a second database (DB 2 ) that comprises memory blocks indexed by all possible hash values obtained by a plurality of k indexed hash functions (H j ), and wherein each block contains a list of the indexes of the reference data (b 1 ) which hashing (H j (b i )) by one of said hash function (H j ) results in the hash value corresponding to said block,
wherein the storage server is configured to i) execute a distinct instance (ORAM 1 , ORAM 2 ) of an Oblivious RAM protocol (ORAM 1 , ORAM 2 ) for each database (DB 1 , DB 2 ), and ii) communicate with a client unit which hashes the data (b i ) to be identified with each of the plurality of k indexed hash functions (H j ), and reads the k memory blocks of the second database (DB 2 ) corresponding to the hash values thus obtained,
the client unit identifies indexes (i 1 , . . . i 1 ) contained in at least t out of k read memory blocks,
the client unit reads the memory blocks of the first database (DB 1 ) indexed by the identified indexes (i 1 , . . . i 1 ) in order to obtain the corresponding indexed reference data (b i1 , . . . b i1 ), said data being candidate data to compare to the data to be identified, and
the client unit decrypts the candidate reference data and compares each of said reference data (b i1 , . . . b i1 ) to the data (b) to be identified in order to detect a matching between the data (b) and one reference data, and
wherein said oblivious RAM protocol prevents the storage server from learning which memory blocks of the databases are read.
7. A data processing method implemented in a system comprising a client unit ( 20 ) and a storage server comprising two databases (DB 1 , DB 2 ), in which:
the first database (DB 1 ) comprises a plurality of indexed memory blocks each comprising a corresponding encrypted indexed reference data (b i ), and
the second database (DB 2 ) comprises memory blocks indexed by all possible hash values obtained by a plurality of k indexed hash functions (H j ), and wherein each block contains a list of the indexes of the reference data (b i ) which hashing (H j (b i )) by one of said hash function (H j ) results in the hash value corresponding to said block,
the storage server and the client unit are configured to execute a distinct instance (ORAM 1 , ORAM 2 ) of an Oblivious RAM protocol (ORAM 1 , ORAM 2 ) for each database (DB 1 , DB 2 ), said method being implemented by the client unit and comprising steps during which the client unit:
hashes a data (b) to be identified with each of the plurality of hash functions (H j ), and reads the k memory blocks of the second database (DB 2 ) corresponding to the hash values thus obtained,
identifies indexes (i 1 , . . . i 1 ) contained in at least t out of k read memory blocks, and
reads the memory blocks of the first database (DB 1 ) indexed by the identified indexes (i 1 , . . . i 1 ) in order to obtain the corresponding indexed reference data (b i1 , . . . b i1 ), and compares each of the said reference data (b i1 , . . . b i1 ) to the data (b) to be identified in order to detect a matching between the data (b) and one reference data,
wherein the steps of reading memory blocks of the databases are carried out using said Oblivious RAM protocol instances.
8. A system for the secure storage and access to data, comprising a client unit, and a storage server comprising two databases (DB 1 , DB 2 ), wherein:
the first database (DB 1 ) comprises indexed memory blocks each comprising a corresponding encrypted indexed reference data (b i ), and
the second database (DB 2 ) comprises memory blocks indexed by all possible hash values obtained by a plurality of indexed hash functions (H j ), and wherein each block comprises a list of the indexes of the reference data (b 1 ) which hashing (H j (b i )) by one of said hash functions (H j ) results in the hash value corresponding to said block,
said system being characterized in that the client unit and the storage server are configured to execute a distinct instance of an Oblivious RAM (ORAM 1 , ORAM 2 ) protocol for each database (DB 1 , DB 2 ), and in that the system is configured to implement a method for obtaining candidate reference data to compare to a data to be identified, wherein the method comprises the steps during which:
the client unit hashes the data (b) to be identified with each of the plurality of hash functions (H j ), and reads the k memory blocks of the second database (DB 2 ) corresponding to the hash values thus obtained,
the client unit identifies indexes (i 1 , . . . i 1 ) contained in at least t out of k read memory blocks, and
the client unit reads the memory blocks of the first database (DB 1 ) indexed by the identified indexes in order to obtain the corresponding indexed reference data (b i1 , . . . b i1 ), said data being candidate data to compare to the data to be identified,
the client unit decrypts the candidate reference data and compares each of said reference data (b i1 , . . . b i1 ) to the data (b) to be identified in order to detect a matching between the data (b) and one reference data,
wherein the steps of reading memory blocks of the databases are carried out by executing an oblivious RAM protocol preventing the storage server from learning which memory blocks of the databases are read.
9. A system according to claim 8 , wherein the system is further configured to perform an initialization method comprising the steps during which:
the client unit selects a family of locality-sensitive hash functions,
the storage server and the client unit set up two instances of an Oblivious RAM protocol for the databases,
the client unit attributes a memory block index of the second database to each hash value obtained by each hash function.
10. A system according to claim 8 , wherein the system is further configured to perform a method for enrolling an i-th reference data, comprising the steps during which:
the client unit writes in the memory block indexed by i of the first database the i-th reference data (b i ),
the client unit computes, for each hash function, the hashing of the i-th reference data, and writes the index i of the reference data in all the memory block of the second database corresponding to the hash values thus obtained,
wherein all the writing steps are carried out implementing an Oblivious RAM protocol.