Cryptology ePrint Archive: Report 2020/1174

Proximity Searchable Encryption for Biometrics

Chloe Cachet and Luke Demarest and Benjamin Fuller and Ariel Hamlin

Abstract: Biometric databases collect entire countries worth of citizens' sensitive information with few cryptographic protections. The critical required functionality is proximity search, the ability to search for all records close to a queried value, that is within a bounded distance. Biometrics usually operate in high dimensional space where an exponential number (in the dimension) of values are close.

This work builds searchable encryption that supports proximity queries for the Hamming metric. The Hamming metric is frequently used for the iris biometric. Searchable encryption schemes have leakage, which is information revealed to the database server such as identifiers of records returned which is known as access pattern leakage.

Prior work on proximity searchable encryption falls into two classes: 1) Li et al. (INFOCOM 2010) and Boldyreva and Chenette (FSE 2014) support only a polynomial number of close values, 2) Kim et al. (SCN 2018) leak the distance between the query and all stored records. The first class is not feasible due to the exponential number of close values. The second class allows the server to compute geometry of the space, enabling attacks akin to those on nearest neighbor schemes (Kornaropoulos et al. IEEE S&P 2019, 2020).

We build proximity search out of a new variant of inner product encryption called multi-point inner product encryption (MPIPE). MPIPE is built from function-hiding, secret-key, inner product predicate encryption (Shen, Shi, and Waters, TCC 2009). Our construction leaks access pattern and when two database records are the same distance from the queried point.

In most applications of searchable encryption the data distribution is not known a priori, making it prudent to consider leakage in a variety of settings. However, biometrics' statistics are well studied and static. Frequently in biometric search at most one record is returned. In this setting, access pattern leakage and the additional leakage of distance equality is unlikely to be harmful.

We also introduce a technique for reducing key size of a class of inner product encryption schemes based on dual pairing vector spaces. Our technique splits these vector spaces into multiple, smaller components, yielding keys that are a linear number of group elements instead of quadratic. We instantiate this technique on the scheme of Okamoto and Takashima (Eurocrypt, 2012) and show security under the same assumption (decisional linear).

Category / Keywords: cryptographic protocols / Searchable encryption, biometrics, proximity search, inner product encryption

Date: received 25 Sep 2020

Contact author: chloe cachet at uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20200925:185209 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]