Outsourced Biometric Identification with Privacy

Biometric identification typically scans a large-scale database of biometric records for finding a close enough match of an individual. This paper investigates how to outsource this computationally expensive scanning while protecting the privacy of both the database and the computation. Exploiting the inherent structures of biometric data and the properties of identification operations, we first present a privacy-preserving biometric identification scheme which uses a single server. We then consider its extensions in the two-server model. It achieves a higher level of privacy than our single-server solution assuming two servers are not colluding. Apart from somewhat homomorphic encryption, our second scheme uses batched protocols for secure shuffling and minimum selection. Our experiments on both synthetic and real data sets show that our solutions outperform existing schemes while preserving privacy.