Paper 2009/507

Efficient Privacy-Preserving Face Recognition

Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg


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 $\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 $\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).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Full version of ICISC 2009 paper.
Secure Two-Party ComputationFace RecognitionPrivacy
Contact author(s)
thomas schneider @ trust rub de
2009-10-21: revised
2009-10-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ahmad-Reza Sadeghi and Thomas Schneider and Immo Wehrenberg},
      title = {Efficient Privacy-Preserving Face Recognition},
      howpublished = {Cryptology ePrint Archive, Paper 2009/507},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.