| DOI | Resolve DOI: https://doi.org/10.1145/3714393.3726497 |
|---|
| Author | Search for: Ha, JulieORCID identifier: https://orcid.org/0009-0006-8853-1069; Search for: Cachet, Chloe1ORCID identifier: https://orcid.org/0009-0002-7320-3127; Search for: Demarest, LukeORCID identifier: https://orcid.org/0000-0002-4317-1198; Search for: Ahmad, SohaibORCID identifier: https://orcid.org/0000-0001-6720-0507; Search for: Fuller, BenjaminORCID identifier: https://orcid.org/0000-0001-6450-0088 |
|---|
| Affiliation | - National Research Council of Canada. Digital Technologies
|
|---|
| Funder | Search for: NSF |
|---|
| Format | Text, Article |
|---|
| Conference | CODASPY '25: Fifteenth ACM Conference on Data and Application Security and Privacy, June 4-6, 2025, Pittsburgh, Pennsylvania, United States |
|---|
| Subject | searchable encryption; biometrics; proximity search |
|---|
| Abstract | This work introduces Private Eyes, the first zero-leakage biometric database. The only leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from oblivious symmetric searchable encryption. Approximate proximity queries are used: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric.
Private Eyes combines locality sensitive-hashing or LSHs (Indyk and Motwani, STOC 1998) and oblivious maps which map keywords to values. One computes many LSHs of each record in the database and uses these hashes as keywords in the oblivious map with the matching biometric readings concatenated as the value. At search time with a noisy reading, one computes the LSHs and retrieves the disjunction of the resulting values from the map. The underlying oblivious map needs to answer disjunction queries efficiently.
We focus on the iris biometric which requires a large number of LSHs, approximately 1000. Boldyreva and Tang’s (PoPETS 2021) design yields a suitable map for a small number of LSHs (their application was in zero-leakage 𝑘-nearest-neighbor search).
Our solution is a zero-leakage disjunctive map designed for the setting when most clauses do not match any records. For the iris, on average at most 6% of LSHs match any stored value.
For the largest tested parameters of a 5000 synthetic iris database, a search requires 18 rounds of communication and 25ms of parallel computation. Our scheme is implemented and open-sourced. |
|---|
| Publication date | 2024-06-04 |
|---|
| Publisher | Association for Computing Machinery (ACM) |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | ecb38f02-3340-43d1-8729-cf665a8ab9bb |
|---|
| Record created | 2025-06-23 |
|---|
| Record modified | 2025-06-25 |
|---|
