Efficient privacy-preserving biometric identification

We present an efficient matching protocol that can be usedin many privacy-preserving biometric identification systems
in the semi-honest setting. Our most general technical con-
tribution is a new backtracking protocol that uses the by-
product of evaluating a garbled circuit to enable efficient
oblivious information retrieval. We also present a more ef-
ficient protocol for computing the Euclidean distances of
vectors, and optimized circuits for finding the closest match
between a point held by one party and a set of points held
by another. We evaluate our protocols by implementing a
practical privacy-preserving fingerprint matching system.