Paper 2020/1174

Multi Random Projection Inner Product Encryption, Applications to Proximity Searchable Encryption for the Iris Biometric

Chloe Cachet
Sohaib Ahmad
Luke Demarest
Serena Riback
Ariel Hamlin
Benjamin Fuller
Abstract

Biometric databases collect people’s information and allow users to perform proximity searches (finding all records within a bounded distance of the query point) with few cryptographic protections. This work studies proximity searchable encryption applied to the iris biometric. Prior work proposed inner product functional encryption as a technique to build proximity biometric databases (Kim et al., SCN 2018). This is because binary Hamming distance is computable using an inner product. This work identifies and closes two gaps in using inner product encryption for biometric search: 1. Biometrics naturally use long vectors often with thousands of bits. Many inner product encryption schemes generate a random matrix whose dimension scales with vector size and have to invert this matrix. As a result, setup is not feasible on commodity hardware unless we reduce the dimension of the vectors. We explore state-of-the-art techniques to reduce the dimension of the iris biometric and show that all known techniques harm the accuracy of the resulting system. That is, for small vector sizes multiple unrelated biometrics are returned in the search. For length 64 vectors, at a 90% probability of the searched biometric being returned, 10% of stored records are erroneously returned on average. Rather than changing the feature extractor, we introduce a new cryptographic technique that allows one to generate several smaller matrices. For vectors of length 1024 this reduces the time to run setup from 23 days to 4 minutes. At this vector length, for the same 90% probability of the searched biometric being returned, .02% of stored records are erroneously returned on average. 2. Prior inner product approaches leak distance between the query and all stored records. We refer to these as distance-revealing. We show a natural construction from function hiding, secret-key, predicate, inner product encryption (Shen, Shi, and Waters, TCC 2009). Our construction only leaks access patterns and which returned records are the same distance from the query. We refer to this scheme as distance-hiding. We implement and benchmark one distance-revealing and one distance-hiding scheme. The distance-revealing scheme can search a small (hundreds) database in 4 minutes while the distance-hiding scheme is not yet practical, requiring 3.5 hours. As a technical contribution of independent interest, we show that our scheme can be instantiated using symmetric pairing groups reducing the cost of search by roughly a factor of three. We believe this analysis extends to other schemes based on projections to a random linear map and its inverse analyzed in the generic group model.

Note: The previous versions of this work were title "Proximity Searchable Encryption for the Iris Biometric." The title is changed to stress the new developments in inner product encryption.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM ASIACCS 2022
DOI
10.1145/3488932.3497754
Keywords
Searchable encryptionbiometricsproximity searchinner product encryption
Contact author(s)
chloe cachet @ uconn edu
History
2023-03-20: last of 7 revisions
2020-09-25: received
See all versions
Short URL
https://ia.cr/2020/1174
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1174,
      author = {Chloe Cachet and Sohaib Ahmad and Luke Demarest and Serena Riback and Ariel Hamlin and Benjamin Fuller},
      title = {Multi Random Projection Inner Product Encryption, Applications to Proximity Searchable Encryption for the Iris Biometric},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1174},
      year = {2020},
      doi = {10.1145/3488932.3497754},
      url = {https://eprint.iacr.org/2020/1174}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.