Paper 2020/1174

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

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.