Fuzzy Labeled Private Set Intersection with Applications to Private Real-Time Biometric Search

The explosive growth of biometrics use (e.g., in surveillance) poses a persistent challenge to keep biometric data private without sacrificing the apps' functionality.

We consider private querying of a real-life biometric scan (e.g., a person's face) against a private biometric database. The querier learns only the label(s) of a matching scan(s) (e.g. a person's name), and the database server learns nothing.

We formally define Fuzzy Labeled Private Set Intersection (FLPSI), a primitive computing the intersection of noisy input sets by considering closeness/similarity instead of equality.

Our FLPSI protocol's communication is sublinear in database size and is concretely efficient. We implement it and apply it to facial search by integrating with our fine-tuned toolchain that maps face images into Hamming space.

We have implemented and extensively tested our system, achieving high performance with concretely small network usage: for a 10K-row database, the query response time over WAN (resp. fast LAN) is 146ms (resp. 47ms), transferring 12.1MB; offline precomputation (with no communication) time is 0.94s. FLPSI scales well: for a 1M-row database, online time is 1.66s (WAN) and 1.46s (fast LAN) with 40.8MB of data transfer in online phase and 37.5s in offline precomputation. This improves the state-of-the-art work (SANNS) by 9 -25× (on WAN) and 1.2 -4× (on fast LAN).

Our false non-matching rate is 0.75% for at most 10 false matches over 1M-row DB, which is comparable to underlying plaintext matching algorithm.

We follow a much more scalable approach that reduces our fuzzy matching problem to an easier exact-matching subproblems that could be solved with communication cost sublinear in DB size, by leveraging optimizations of the state-of-theart (L)PSI techniques [16,17]. The crux of our solution is twofold. First, we translate the closeness (e.g., in Euclidean space) of two biometrics into a t-out-of-T set-based matching without sacrificing accuracy. That is, we encode a given biometric input into a set of T items, s.t. the two sets will likely have at least t exactly common items iff the biometrics are of the same person. Second, we build an efficient threshold set-matching protocol from fully homomorphic encryption (FHE), garbled circuits (GC) and t-out-of-T secret sharing, and solve several challenges in definitional approach.

• We describe and formally define the functionality and security of Fuzzy Labeled Private Set Intersection (FLPSI). We build a FLPSI protocol using the AES blockcipher, homomorphic encryption, garbled circuits and t-out-of-T secret sharing. We prove the security in the semi-honest model.

• We show how to interpret closeness (e.g., in Euclidean space) between biometric inputs as t-out-of-T exact set-item matchings without sacrificing the accuracy.

• We give simulation-based FLPSI security definition (prior definitions of fuzzy primitives are game-based).

• We introduce a number of optimizations, in addition to the prior (L)PSI techniques we use.

• We extensively evaluate our protocol in different settings.

We achieve 1.66s online running time over WAN with 40.8MB transfer per query over a million-row database.

• We systematically compare our design with prior art, and outperform all of them in their best settings, often by several orders of magnitude both in run time and communication.

For example, on the largest dataset (of 10M records), we speed up by a factor of 3-33× and decrease the overall data communication by a factor of up to 48-452× compared to the two protocols of the state-of-the-art, SANNS [15].

• We highlight sublinear and concretely very small network use of our solution. In contrast with most other related work, our solution will scale on very small-bandwidth networks.