Abstract
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).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)
Armknecht, F., Sadeghi, A.-R.: A new approach for algebraically homomorphic encryption. Cryptology ePrint Archive, Report 2008/422 (2008), http://eprint.iacr.org/2008/422
Avidan, S., Butman, M.: Efficient methods for privacy preserving face detection. In: Advances in Neural Information Processing Systems (NIPS’06), pp. 57–64. MIT Press, Cambridge (2006)
Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.-R., Schneider, T.: Secure evaluation of private linear branching programs with medical applications. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 424–439. Springer, Heidelberg (2009)
Belhumeur, P.N., Hespanha, J.P., Kriegman, D.J.: Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(7), 711–720 (1997)
Blake, I.F., Kolesnikov, V.: Strong conditional oblivious transfer and computing on intervals. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 515–529. Springer, Heidelberg (2004)
Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
Bowcott, O.: Interpol wants facial recognition database to catch suspects. Guardian (October 20, 2008), http://www.guardian.co.uk/world/2008/oct/20/interpol-facial-recognition
Damgård, I.B., Geisler, M., Krøigård, M.: Efficient and secure comparison for on-line auctions. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 416–430. Springer, Heidelberg (2007)
Damgård, I., Geisler, M., Krøigård, M.: A correction to efficient and secure comparison for on-line auctions. Cryptology ePrint Archive, Report 2008/321 (2008), http://eprint.iacr.org/2008/321
Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, S., Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Goldberg, I., Atallah, M.J. (eds.) Privacy Enhancing Technologies. LNCS, vol. 5672, pp. 235–253. Springer, Heidelberg (2009)
Fischlin, M.: A cost-effective pay-per-multiplication comparison method for millionaires. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 457–472. Springer, Heidelberg (2001)
Garay, J.A., Schoenmakers, B., Villegas, J.: Practical and secure solutions for integer comparison. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 330–342. Springer, Heidelberg (2007)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: ACM Symposium on Theory of Computing (STOC’09), pp. 169–178. ACM, New York (2009)
Giry, D., Quisquater, J.-J.: Cryptographic key length recommendation (March 2009), http://keylength.com
Grose, T.: When surveillance cameras talk. Time Magazine (February 11, 2008), http://www.time.com/time/world/article/0,8599,1711972,00.html
Interational Civil Aviation Organization (ICAO). Machine Readable Travel Documents (MRTD), Doc 9303, Part 1, 5th (edn.) (2003)
Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Improved garbled circuit building blocks and applications to auctions and computing minima. In: Cryptology and Network Security (CANS ’09). LNCS. Springer, Heidelberg (2009), http://www.springerlink.com/content/175204h13h038581
Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008)
Lindell, Y., Pinkas, B.: A proof of Yao’s protocol for secure two-party computation. ECCC Report TR04-063, Electronic Colloquium on Computational Complexity, ECCC (2004)
Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003)
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay a secure two-party computation system. In: USENIX (2004), http://fairplayproject.net
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: ACM-SIAM Symposium On Discrete Algorithms (SODA’01), pp. 448–457. Society for Industrial and Applied Mathematics (2001)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce, pp. 129–139 (1999)
Naumann, I., Hogben, G.: Privacy features of European eID card specifications. Network Security 2008(8), 9–13 (2008); European Network and Information Security Agency (ENISA)
Newton, E.M., Sweeney, L., Malin, B.: Preserving privacy by de-identifying face images. IEEE Transactions on Knowledge and Data Engineering 17(2), 232–243 (2005)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Paus, A., Sadeghi, A.-R., Schneider, T.: Practical secure evaluation of semiprivate functions. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 89–106. Springer, Heidelberg (2009), http://www.trust.rub.de/FairplaySPF
Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Advances in Cryptology ASIACRYPT 2009. LNCS, Springer, Heidelberg (2009), http://www.springerlink.com/content/3p52033869154003
Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: Efficient privacy-preserving face recognition. Cryptology ePrint Archive, Report 2009/507 (2009), http://eprint.iacr.org/2009/507
Turk, M., Pentland, A.: Eigenfaces for recognition. Journal of Cognitive Neu- roscience 3(1), 71–86 (1991)
Turk, M., Pentland, A.: Face recognition using eigenfaces. In: IEEE Computer Vision and Pattern Recognition (CVPR’91), pp. 586–591. IEEE, Los Alamitos (1991)
Yao, A.C.: How to generate and exchange secrets. In: IEEE Symposium on Foundations of Computer Science (FOCS’86), pp. 162–167. IEEE, Los Alamitos (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sadeghi, AR., Schneider, T., Wehrenberg, I. (2010). Efficient Privacy-Preserving Face Recognition. In: Lee, D., Hong, S. (eds) Information, Security and Cryptology – ICISC 2009. ICISC 2009. Lecture Notes in Computer Science, vol 5984. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14423-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-14423-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14422-6
Online ISBN: 978-3-642-14423-3
eBook Packages: Computer ScienceComputer Science (R0)