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).
Category / Keywords: cryptographic protocols / Secure Two-Party Computation, Face Recognition, Privacy Publication Info: Full version of ICISC 2009 paper. Date: received 20 Oct 2009, last revised 21 Oct 2009 Contact author: thomas schneider at trust rub de Available formats: PDF | BibTeX Citation Version: 20091021:181607 (All versions of this report) Discussion forum: Show discussion | Start new discussion