Date Added: Feb 2011
The authors present an efficient matching protocol that can be used in many privacy-preserving biometric identification systems in the semi-honest setting. The most general technical contribution is a new backtracking protocol that uses the byproduct of evaluating a garbled circuit to enable efficient oblivious information retrieval. They also present a more efficient 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. They evaluate the protocols by implementing a practical privacy-preserving fingerprint matching system.