Automatic recognition of human faces is becoming increasingly popular in civilian and law enforcement applications that require
reliable recognition of humans. However, the rapid improvement and widespread deployment of this technology raises strong
concerns regarding the violation of individuals’ privacy. A typical application scenario for privacy-preserving face recognition
concerns a client who privately searches for a specific face image in the face image database of a server.
In this paper we present a privacy-preserving face recognition scheme that substantially improves over previous work in terms
of communication-and computation efficiency: the most recent proposal of Erkin et al. (PETS’09) requires
O(logM)\mathcal{O}(\log M) rounds and computationally expensive operations on homomorphically encrypted data to recognize a face in a database of
M faces. Our improved scheme requires only
O(1)\mathcal{O}(1) rounds and has a substantially smaller online communication complexity (by a factor of 15 for each database entry) and less
computation complexity.
Our solution is based on known cryptographic building blocks combining homomorphic encryption with garbled circuits. Our implementation
results show the practicality of our scheme also for large databases (e.g., for M = 1000 we need less than 13 seconds and less than 4 MByte online communication on two 2.4GHz PCs connected via Gigabit Ethernet).
Keywords Secure Two-Party Computation - Face Recognition - Privacy