Extended Private Information Retrieval and Its Application in Biometrics Authentications | SpringerLink
Skip to main content
Springer Nature Link
Log in

Extended Private Information Retrieval and Its Application in Biometrics Authentications

  • Conference paper
Cryptology and Network Security (CANS 2007)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 4856))

Included in the following conference series:

Abstract

In this paper we generalize the concept of Private Information Retrieval (PIR) by formalizing a new cryptographic primitive, named Extended Private Information Retrieval (EPIR). Instead of enabling a user to retrieve a bit (or a block) from a database as in the case of PIR, an EPIR protocol enables a user to evaluate a function f which takes a string chosen by the user and a block from the database as input. Like PIR, EPIR can also be considered as a special case of the secure two-party computation problem (and more specifically the oblivious function evaluation problem). We propose two EPIR protocols, one for testing equality and the other for computing Hamming distance. As an important application, we show how to construct strong privacy-preserving biometric-based authentication schemes by employing these EPIR protocols.

This work is partially supported by french ANR RNRT project BACH.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Atallah, M.J., Frikken, K.B., Goodrich, M.T., Tamassia, R.: Secure biometric authentication for weak computational devices. Financial Cryptography, 357–371 (2005)

    Google Scholar 

  2. Bolle, R.M., Connell, J.H., Ratha, N.K.: Biometric perils and patches. Pattern Recognition 35(12), 2727–2738 (2002)

    Article  MATH  Google Scholar 

  3. Boneh, D., Goh, E., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)

    Google Scholar 

  4. Boyen, X.: Reusable cryptographic fuzzy extractors. In: Atluri, V., Pfitzmann, B., McDaniel, P.D. (eds.) CCS 2004: Proceedings of the 11th ACM conference on Computer and communications security, pp. 82–91. ACM Press, New York (2004)

    Chapter  Google Scholar 

  5. Boyen, X., Dodis, Y., Katz, J., Ostrovsky, R., Smith, A.: Secure remote authentication using biometric data. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 147–163. Springer, Heidelberg (2005)

    Google Scholar 

  6. Bringer, J., Chabanne, H., Izabachène, M., Pointcheval, D., Tang, Q., Zimmer, S.: An application of the Goldwasser-Micali cryptosystem to biometric authentication. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) Information Security and Privacy, 12th Australasian Conference, ACISP 2007 Proceedings. LNCS, vol. 4586, pp. 96–106. Springer, Heidelberg (2007)

    Google Scholar 

  7. Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)

    Google Scholar 

  8. Canetti, R., Ishai, Y., Kumar, R., Reiter, M.K., Rubinfeld, R., Wright, R.N.: Selective private function evaluation with applications to private statistics. In: PODC 2001: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pp. 293–304. ACM Press, New York (2001)

    Chapter  Google Scholar 

  9. Chor, B., Gilboa, N.: Computationally private information retrieval (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 304–313 (1997)

    Google Scholar 

  10. Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  11. Crepeau, C., Salvail, L.: Oblivious verification of common string. CWI Quarterly, special issue for Crypto Course 10th Anniversary 8(2), 97–109 (1995)

    MATH  Google Scholar 

  12. Crescenzo, G.D., Graveman, R., Ge, R., Arce, G.: Approximate message authentication and biometric entity authentication. In: Patrick, A.S., Yung, M. (eds.) FC 2005. LNCS, vol. 3570, pp. 240–254. Springer, Heidelberg (2005)

    Google Scholar 

  13. Crescenzo, G.D., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 122–138. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  14. Dodis, Y., Katz, J., Reyzin, L., Smith, A.: Robust fuzzy extractors and authenticated key agreement from close secrets. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 232–250. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  15. Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004)

    Google Scholar 

  16. Du, W., Atallah, M.: Privacy-preserving cooperative statistical analysis. In: ACSAC 2001: Proceedings of the 17th Annual Computer Security Applications Conference, pp. 102–110. IEEE Computer Society, Los Alamitos (2001)

    Google Scholar 

  17. Du, W., Atallah, M.J.: Secure multi-party computation problems and their applications: a review and open problems. In: NSPW 2001: Proceedings of the 2001 workshop on New security paradigms, pp. 13–22. ACM Press, New York (2001)

    Chapter  Google Scholar 

  18. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)

    Chapter  Google Scholar 

  19. Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Communications of the ACM 39(5), 77–85 (1996)

    Article  Google Scholar 

  20. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)

    Google Scholar 

  21. Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)

    Google Scholar 

  22. Gasarch, W.: A survey on private information retrieval, http://www.cs.umd.edu/~gasarch/pir/pir.html

  23. Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)

    Google Scholar 

  24. Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp. 151–160 (1998)

    Google Scholar 

  25. Goethals, B., Laur, S., Lipmaa, H., Mielikäinen, T.: On private scalar product computation for privacy-preserving data mining. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 104–120. Springer, Heidelberg (2005)

    Google Scholar 

  26. Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)

    MATH  Google Scholar 

  27. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  28. Hao, F., Anderson, R., Daugman, J.: Combining crypto with biometrics effectively. IEEE Transactions on Computers 55(9), 1081–1088 (2006)

    Article  Google Scholar 

  29. Juels, A., Sudan, M.: A fuzzy vault scheme. Des. Codes Cryptography 38(2), 237–257 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  30. Juels, A., Wattenberg, M.: A fuzzy commitment scheme. In: ACM Conference on Computer and Communications Security, pp. 28–36 (1999)

    Google Scholar 

  31. Kiltz, E., Leander, G., Malone-Lee, J.: Secure computation of the mean and related statistics. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 283–302. Springer, Heidelberg (2005)

    Google Scholar 

  32. Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: Single database, computationally-private information retrieval. In: FOCS 1997. 38th Annual Symposium on Foundations of Computer Science, pp. 364–373 (1997)

    Google Scholar 

  33. Linnartz, J.M.G., Tuyls, P.: New shielding functions to enhance privacy and prevent misuse of biometric templates. In: Kittler, J., Nixon, M.S. (eds.) AVBPA 2003. LNCS, vol. 2688, pp. 393–402. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  34. Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: Zhou, J., Lopez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)

    Google Scholar 

  35. Mishra, S.K., Sarkar, P.: Symmetrically private information retrieval. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 225–236. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  36. Naor, M., Pinkas, B.: Oblivious polynomial evaluation. SIAM J. Comput. 35(5), 1254–1281 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  37. Ostrovsky, R., Skeith III, W.E.: A survey of single database PIR: Techniques and applications. Cryptology ePrint Archive: Report 2007/059 (2007)

    Google Scholar 

  38. Ratha, N., Connell, J., Bolle, R.M., Chikkerur, S.: Cancelable biometrics: A case study in fingerprints. In: ICPR 2006: Proceedings of the 18th International Conference on Pattern Recognition, pp. 370–373. IEEE Computer Society, Los Alamitos (2006)

    Google Scholar 

  39. Ratha, N.K., Connell, J.H., Bolle, R.M.: Enhancing security and privacy in biometrics-based authentication systems. IBM Systems Journal 40(3), 614–634 (2001)

    Article  Google Scholar 

  40. Safavi-Naini, R., Tonien, D.: Fuzzy universal hashing and approximate authentication. Cryptology ePrint Archive: Report 2005/256 (2005)

    Google Scholar 

  41. Schoenmakers, B., Tuyls, P.: Efficient binary conversion for Paillier encrypted values. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 522–537. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  42. Tuyls, P., Akkermans, A.H.M., Kevenaar, T.A.M., Jan Schrijen, G., Bazen, A.M., Veldhuis, R.N.J.: Practical biometric authentication with template protection. In: Kanade, T., Jain, A., Ratha, N.K. (eds.) AVBPA 2005. LNCS, vol. 3546, pp. 436–446. Springer, Heidelberg (2005)

    Google Scholar 

  43. Tuyls, P., Goseling, J.: Capacity and examples of template-protecting biometric authentication systems. In: Pajdla, T., Matas, J(G.) (eds.) ECCV 2004. LNCS, vol. 3021, pp. 158–170. Springer, Heidelberg (2004)

    Google Scholar 

  44. Tuyls, P., Verbitskiy, E., Goseling, J., Denteneer, D.: Privacy protecting biometric authentication systems: an overview. In: EUSIPCO 2004 (2004)

    Google Scholar 

  45. Uludag, U., Pankanti, S., Prabhakar, S., Jain, A.K.: Biometric cryptosystems: Issues and challenges. Proceedings of the IEEE 92(6), 948–960 (2004)

    Article  Google Scholar 

  46. Vaidya, J., Clifton, C.: Privacy preserving association rule mining in vertically partitioned data. In: KDD 2002: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 639–644 (2002)

    Google Scholar 

  47. Verbitskiy, E., Tuyls, P., Denteneer, D., Linnartz, J.P.: Reliable biometric authentication with privacy protection. In: SPIE Biometric Technology for Human Identification Conf. (2004)

    Google Scholar 

  48. Atallah, M.J., Du, W.: Protocols for secure remote database access with approximate matching. Technical report, CERIAS, Purdue University. CERIAS TR (2000)-15 (2000)

    Google Scholar 

  49. Yao, A.: Protocols for secure computations. In: Proceedings of the twenty-third annual IEEE Symposium on Foundations of Computer Science, pp. 160–164 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sagem Sécurité,  

    Julien Bringer & Hervé Chabanne

  2. Departement d’Informatique, École Normale Supérieure, 45 Rue d’Ulm, 75230 Paris Cedex 05, France

    David Pointcheval & Qiang Tang

Authors
  1. Julien Bringer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hervé Chabanne
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Pointcheval
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qiang Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Feng Bao San Ling Tatsuaki Okamoto Huaxiong Wang Chaoping Xing

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bringer, J., Chabanne, H., Pointcheval, D., Tang, Q. (2007). Extended Private Information Retrieval and Its Application in Biometrics Authentications. In: Bao, F., Ling, S., Okamoto, T., Wang, H., Xing, C. (eds) Cryptology and Network Security. CANS 2007. Lecture Notes in Computer Science, vol 4856. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76969-9_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-76969-9_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-76968-2

  • Online ISBN: 978-3-540-76969-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics