Skip to main content
SpringerLink
Log in

BETA: Biometric-Enabled Threshold Authentication

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2021 (PKC 2021)

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

Included in the following conference series:

Abstract

In the past decades, user authentication has been dominated by server-side password-based solutions that rely on “what users know”. This approach is susceptible to breaches and phishing attacks, and poses usability challenges. As a result, the industry is gradually moving to biometric-based client-side solutions that do not store any secret information on servers. This shift necessitates the safe storage of biometric templates and private keys, which are used to generate tokens, on user devices.

We propose a new generic framework called Biometric Enabled Threshold Authentication (BETA) to protect sensitive client-side information like biometric templates and cryptographic keys. Towards this, we formally introduce the notion of Fuzzy Threshold Tokenizer (\(\text {FTT}\)) where an initiator can use a “close” biometric measurement to generate an authentication token if at least t (the threshold) devices participate. We require that the devices only talk to the initiator, and not to each other, to capture the way user devices are connected in the real world. We use the universal composability (UC) framework to model the security properties of \(\text {FTT}\), including the unforgeability of tokens and the privacy of the biometric values (template and measurement), under a malicious adversary. We construct three protocols that meet our definition.

Our first two protocols are general feasibility results that work for any distance function, any threshold t and tolerate the maximal (i.e. \(t-1\)) amount of corruption. They are based on any two round UC-secure multi-party computation protocol in the standard model (with a CRS) and threshold fully homomorphic encryption, respectively. We show how to effectively use these primitives to build protocols in a constrained communication model with just four rounds of communication.

For the third protocol, we consider inner-product based distance metrics (cosine similarity, Euclidean distance, etc.) specifically, motivated by the recent interest in its use for face recognition. We use Paillier encryption, efficient NIZKs for specific languages, and a simple garbled circuit to build an efficient protocol for the common case of \(n=3\) devices with one compromised.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Note that corrupt parties can of course freely interact amongst themselves.

  2. 2.

    Recall that by one communication round, we mean a unidirectional/non-simultaneous message exchange channel over a peer-to-peer network. That is, in each round either the initiator sends messages to some subset of the other participating devices or vice versa. In contrast, one round of communication over a broadcast channel means that messages are being sent simultaneously by multiple (potentially all) parties connected to the channel and all of them receive all the messages sent in that round. All our \(\text {FTT}\) protocols use peer-to-peer channels which is the default communication model in this paper.

  3. 3.

    Note that the creation and broadcasting of these ciphertexts can happen in parallel within a single round of communication between \({P}^*\) and the other parties in the set \(S\).

  4. 4.

    Our construction can also be extended to work for the related Euclidean Distance function but we focus on Cosine Similarity in this section.

  5. 5.

    However, we allow the attacker to decide on the corrupt set adaptively after receiving the public values.

  6. 6.

    The arrowhead denotes that in this round messages are outgoing from party \(\mathcal {P}^*\).

  7. 7.

    The arrowhead denotes that in this round messages are outgoing from party \(\mathcal {P}^*\).

  8. 8.

    The arrowhead denotes that in this round messages are outgoing from party \(\mathcal {P}_i\).

References

  1. About Face ID advanced technology. https://support.apple.com/en-us/HT208108. Accessed 07 Apr 2021

  2. Advantages and disadvantages of biometrics. https://www.ukessays.com/dissertation/examples/information-systems/advantages-and-disadvantages-of-biometrics.php?vref=1. Accessed 07 Apr 2021

  3. FIDO Alliance. https://fidoalliance.org/. Accessed 07 Apr 2021

  4. Google Pixel Fingerprint. https://support.google.com/pixelphone/answer/6285273?hl=en. Accessed 07 Apr 2021

  5. iOS Security – iOS 12, p. 8. https://www.apple.com/business/site/docs/iOS_Security_Guide.pdf. Accessed 07 Apr 2021

  6. List of data breaches. https://en.wikipedia.org/wiki/List_of_data_breaches. Accessed 07 Apr 2021

  7. NISTIR Draft on Ongoing Face Recognition Vendor Test Part 1: Verification. https://pages.nist.gov/frvt/reports/11/frvt_report_2020_01_21.pdf. Accessed 07 Apr 2021

  8. Privacy Rights Clearinghouse - Data Breaches. https://www.privacyrights.org/data-breaches. Accessed 07 Apr 2021

  9. Samsung Galaxy: Iris Scans for Security. https://www.samsung.com/global/galaxy/galaxy-s8/security/. Accessed 07 Apr 2021

  10. Web Authentication: W3 Standard. https://www.w3.org/TR/2018/CR-webauthn-20180320/. Accessed 07 Apr 2021

  11. White-Box Competition. https://whibox-contest.github.io/. Accessed 07 Apr 2021

  12. Agrawal, S., Badrinarayanan, S., Mohassel, P., Mukherjee, P., Patranabis, S.: BETA: biometric enabled threshold authentication. IACR Cryptol. ePrint Arch. 2020, 679 (2020)

    Google Scholar 

  13. Barak, B., et al.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1

    Chapter  Google Scholar 

  14. Beimel, A., Ishai, Y., Kushilevitz, E.: Ad hoc PSM protocols: secure computation without coordination. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 580–608. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_20

    Chapter  Google Scholar 

  15. Benhamouda, F., Lin, H.: k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 500–532. Springer, Heidelberg (Apr / May (2018)

    Google Scholar 

  16. Blazy, O., Chevalier, C., Vergnaud, D.: Mitigating server breaches in password-based authentication: Secure and efficient solutions. In: CT-RSA (2016)

    Google Scholar 

  17. Blundo, C., De Cristofaro, E., Gasti, P.: EsPRESSo: efficient privacy-preserving evaluation of sample set similarity. In: Di Pietro, R., Herranz, J., Damiani, E., State, R. (eds.) DPM/SETOP -2012. LNCS, vol. 7731, pp. 89–103. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35890-6_7

    Chapter  Google Scholar 

  18. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-Group signature scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_3

    Chapter  Google Scholar 

  19. Bonawitz, K., et al.: Practical secure aggregation for privacy-preserving machine learning. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1175–1191. ACM Press, October/November 2017

    Google Scholar 

  20. Boneh, D., Gennaro, R., Goldfeder, S., Jain, A., Kim, S., Rasmussen, P.M.R., Sahai, A.: Threshold cryptosystems from threshold fully homomorphic encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 565–596. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_19

    Chapter  Google Scholar 

  21. Boyen, X.: Reusable cryptographic fuzzy extractors. In: Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 2004, pp. 82–91. ACM Press, October 2004

    Google Scholar 

  22. Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337–367. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_12

    Chapter  Google Scholar 

  23. Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: Karlin, A.R. (ed.) ITCS 2018, vol. 94, pp. 21:1–21:21. LIPIcs, January 2018

    Google Scholar 

  24. Brakerski, Z., Perlman, R.: Lattice-based fully dynamic multi-key FHE with short ciphertexts. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 190–213. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_8

    Chapter  Google Scholar 

  25. Bringer, J., Chabanne, H., Patey, A.: SHADE: secure HAmming DistancE computation from oblivious transfer. In: Adams, A.A., Brenner, M., Smith, M. (eds.) FC 2013. LNCS, vol. 7862, pp. 164–176. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41320-9_11

    Chapter  Google Scholar 

  26. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001

    Google Scholar 

  27. Canetti, R.: Universally Composable Signature, Certification, and Authentication. In: CSFW (2004)

    Google Scholar 

  28. Canetti, R., Cohen, A., Lindell, Y.: A simpler variant of universally composable security for standard multiparty computation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 3–22. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_1

    Chapter  Google Scholar 

  29. Chan, T.-H.H., Shi, E., Song, D.: Privacy-preserving stream aggregation with fault tolerance. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 200–214. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32946-3_15

    Chapter  Google Scholar 

  30. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_18

    Chapter  Google Scholar 

  31. Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_9

    Chapter  MATH  Google Scholar 

  32. Dinh, T., Steinfeld, R., Bhattacharjee, N.: A lattice-based approach to privacy-preserving biometric authentication without relying on trusted third parties. In: Liu, J.K., Samarati, P. (eds.) ISPEC 2017. LNCS, vol. 10701, pp. 297–319. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72359-4_17

    Chapter  Google Scholar 

  33. 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). https://doi.org/10.1007/978-3-540-24676-3_31

    Chapter  Google Scholar 

  34. Dupont, P.-A., Hesse, J., Pointcheval, D., Reyzin, L., Yakoubov, S.: Fuzzy password-authenticated key exchange. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 393–424. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_13

    Chapter  Google Scholar 

  35. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_2

    Chapter  Google Scholar 

  36. Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: 26th ACM STOC, pp. 554–563. ACM Press, May 1994

    Google Scholar 

  37. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS (2013)

    Google Scholar 

  38. Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_16

    Chapter  Google Scholar 

  39. Grassi, P.A., et al.: Nist special publication 800–63b: Digital identity guidelines: authentication and lifecycle management, June 2017. https://pages.nist.gov/800-63-3/sp800-63b.html

  40. Halevi, S., Kalai, Y.T.: Smooth projective hashing and two-message oblivious transfer. J. Cryptol. 25(1), 158–193 (2012)

    Article  MathSciNet  Google Scholar 

  41. Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS 1997. Washington, DC, USA (1997)

    Google Scholar 

  42. Joye, M., Libert, B.: A scalable scheme for privacy-preserving aggregation of time-series data. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 111–125. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_10

    Chapter  MATH  Google Scholar 

  43. Liu, W., Wen, Y., Yu, Z., Li, M., Raj, B., Song, L.: Sphereface: deep hypersphere embedding for face recognition. In: CVPR (2017)

    Google Scholar 

  44. Mohassel, P., Rosulek, M., Zhang, Y.: Fast and secure three-party computation: the garbled circuit approach. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015. pp. 591–602. ACM Press, October 2015

    Google Scholar 

  45. Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 735–763. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_26

    Chapter  Google Scholar 

  46. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM, January 2001

    Google Scholar 

  47. 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). https://doi.org/10.1007/3-540-48910-X_16

    Chapter  Google Scholar 

  48. Peikert, C., Shiehian, S.: Multi-key FHE from lwe, revisited. In: TCC (2016)

    Google Scholar 

  49. Peikert, C., Shiehian, S.: Multi-key FHE from LWE, revisited. In: Hirt, M., Smith, A.D. (eds.) TCC 2016-B, Part II. LNCS, vol. 9986, pp. 217–238. Springer, Heidelberg (Oct / Nov (2016)

    Google Scholar 

  50. Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4

    Chapter  Google Scholar 

  51. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_31

    Chapter  Google Scholar 

  52. Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27

    Chapter  Google Scholar 

  53. Schroff, F., Kalenichenko, D., Philbin, J.: FaceNet: a unified embedding for face recognition and clustering. In: CVPR (2015)

    Google Scholar 

  54. Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207–220. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_15

    Chapter  Google Scholar 

  55. Wang, H., et al.: Cosface: Large margin cosine loss for deep face recognition. In: CVPR (2018)

    Google Scholar 

  56. Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Western Digital, Milpitas, CA, USA

    Shashank Agrawal

  2. Visa Research, Palo Alto, CA, USA

    Saikrishna Badrinarayanan, Pratyay Mukherjee & Sikhar Patranabis

  3. Facebook, San Francisco, CA, USA

    Payman Mohassel

Authors
  1. Shashank Agrawal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Saikrishna Badrinarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Payman Mohassel
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pratyay Mukherjee
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sikhar Patranabis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saikrishna Badrinarayanan .

Editor information

Editors and Affiliations

  1. Texas A&M University, College Station, TX, USA

    Juan A. Garay

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Agrawal, S., Badrinarayanan, S., Mohassel, P., Mukherjee, P., Patranabis, S. (2021). BETA: Biometric-Enabled Threshold Authentication. In: Garay, J.A. (eds) Public-Key Cryptography – PKC 2021. PKC 2021. Lecture Notes in Computer Science(), vol 12711. Springer, Cham. https://doi.org/10.1007/978-3-030-75248-4_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75248-4_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75247-7

  • Online ISBN: 978-3-030-75248-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation