Abstract
Biometric authentication is a protocol which verifies a user’s authority by comparing her biometric with the pre-enrolled biometric template stored in the server. Biometric authentication is convenient and reliable; however, it also brings privacy issues since biometric information is irrevocable when exposed.
In this paper, we propose a new user-centric secure biometric authentication protocol for Hamming distance. The biometric data is always encrypted so that the verification server learns nothing about biometric information beyond the Hamming distance between enrolled and queried templates. To achieve this, we construct a single-key function-hiding inner product functional encryption for binary strings whose security is based on a variant of the Learning with Errors problem. Our protocol consists of a single round, and is almost optimal in the sense that its time and space complexity grow quasi-linearly with the size of biometric templates. On implementation with concrete parameters, for binary strings of size ranging from 579 to 18,229 bytes (according to NIST IREX IX report), our scheme outperforms previous work from the literature.
This research was conducted while the second, third and fourth authors were at Seoul National University and the fifth author was at Samsung Research.
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
Similar content being viewed by others
Notes
- 1.
Iris template size analyzed in NIST IRES IX report (2018) [28] ranges from 579 to 18, 229 bytes.
- 2.
- 3.
- 4.
- 5.
THRIVE [21] insists that their scheme is secure under (static) malicious adversary, but they assume that the end-user (client) performs the encryption honestly.
- 6.
They reported 24 s of running time for biometric of size 16, 384 bits which is roughly \(\times \frac{1}{10}\) of the biometric considered in our parameter II.
- 7.
However, it is not clarified in [14] which OT is used in their experiment.
References
Abdalla, M., Bourse, F., De Caro, A., Pointcheval, D.: Simple functional encryption schemes for inner products. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 733–751. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_33
Abidin, A., Aly, A., Rúa, E.A., Mitrokotsa, A.: Efficient verifiable computation of XOR for biometric authentication. In: Foresti, S., Persiano, G. (eds.) CANS 2016. LNCS, vol. 10052, pp. 284–298. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48965-0_17
Abidin, A., Mitrokotsa, A.: Security aspects of privacy-preserving biometric authentication based on ideal lattices and ring-LWE. In: 2014 IEEE International Workshop on Information Forensics and Security (WIFS), pp. 60–65. IEEE (2014)
Agrawal, S., Libert, B., Maitra, M., Titiu, R.: Adaptive simulation security for inner product functional encryption. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12110, pp. 34–64. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45374-9_2
Agrawal, S., Libert, B., Stehlé, D.: Fully secure functional encryption for inner products, from standard assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 333–362. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_12
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)
Alexander, D.: 5.6 million fingerprints stolen in U.S. personnel data hack: government (2015). https://www.reuters.com/article/us-usa-cybersecurity-fingerprints/5-6-million-fingerprints-stolen-in-u-s-personnel-data-hack-government-idUSKCN0RN1V820150923
Bishop, A., Jain, A., Kowalczyk, L.: Function-hiding inner product encryption. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 470–491. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_20
Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 575–584 (2013)
Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_29
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
Chun, H., Elmehdwi, Y., Li, F., Bhattacharya, P., Jiang, W.: Outsourceable two-party privacy-preserving biometric authentication. In: Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, pp. 401–412. ACM (2014)
Datta, P., Dutta, R., Mukhopadhyay, S.: Functional encryption for inner product with full function privacy. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 164–195. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_7
Gasti, P., Šeděnka, J., Yang, Q., Zhou, G., Balagani, K.S.: Secure, fast, and energy-efficient outsourced authentication for smartphones. IEEE Trans. Inf. Forensics Secur. 11(11), 2556–2571 (2016)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM, New York (2009)
Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Security Symposium, vol. 201, pp. 331–335 (2011)
Information technology - security techniques - biometric information protection, standard, international organization for standardization. ISO/IEC24745:2011 (2011)
Jain, A.K., Nandakumar, K., Nagar, A.: Biometric template security. EURASIP J. Adv. Signal Process. 2008, 113 (2008)
Jain, A.K., Prabhakar, S., Hong, L., Pankanti, S.: FingerCode: a filterbank for fingerprint representation and matching. In: Conference on Computer Vision and Pattern Recognition (CVPR), p. 2187. IEEE Computer Society (1999)
Jarrous, A., Pinkas, B.: Secure hamming distance based computation and its applications. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 107–124. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01957-9_7
Karabat, C., Kiraz, M.S., Erdogan, H., Savas, E.: Thrive: threshold homomorphic encryption based secure and privacy preserving biometric verification system. EURASIP J. Adv. Signal Process. 2015(1), 71 (2015)
Katz, J., Yung, M.: Threshold cryptosystems based on factoring. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 192–205. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_12
Kim, S., Kim, J., Seo, J.H.: A new approach to practical function-private inner product encryption. Theoret. Comput. Sci. 783, 22–40 (2019)
Kim, S., Lewi, K., Mandal, A., Montgomery, H., Roy, A., Wu, D.J.: Function-hiding inner product encryption is practical. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 544–562. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_29
Micciancio, D.: On the hardness of learning with errors with binary secrets. Theory Comput. 14(1), 1–17 (2018)
Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, pp. 113–124. ACM (2011)
Prabhakar, S., Pankanti, S., Jain, A.K.: Biometric recognition: security and privacy concerns. IEEE Secur. Priv. 99(2), 33–42 (2003)
Quinn, G.W., Matey, J.R., Grother, P.J.: IREX IX part one, performance of iris recognition algorithms. NIST Interagency/Internal Report (NISTIR) - 8207 (2018)
Rane, S., Wang, Y., Draper, S.C., Ishwar, P.: Secure biometrics: concepts, authentication architectures, and challenges. IEEE Signal Process. Mag. 30(5), 51–64 (2013)
Regev, O.: The learning with errors problem. In: Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity, pp. 191–204 (2010)
Roberts, C.: Biometric attack vectors and defences. Comput. Secur. 26(1), 14–25 (2007)
Simoens, K., Bringer, J., Chabanne, H., Seys, S.: A framework for analyzing template security and privacy in biometric authentication systems. IEEE Trans. Inf. Forensics Secur. 7(2), 833–841 (2012)
Tomida, J., Abe, M., Okamoto, T.: Efficient functional encryption for inner-product values with full-hiding security. In: Bishop, M., Nascimento, A.C.A. (eds.) ISC 2016. LNCS, vol. 9866, pp. 408–425. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45871-7_24
Tomida, J., Takashima, K.: Unbounded inner product functional encryption from bilinear maps. Jpn. J. Ind. Appl. Math. 37(3), 723–779 (2020). https://doi.org/10.1007/s13160-020-00419-x
Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Packed homomorphic encryption based on ideal lattices and its application to biometrics. In: Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds.) CD-ARES 2013. LNCS, vol. 8128, pp. 55–74. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40588-4_5
Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Practical packing method in somewhat homomorphic encryption. In: Garcia-Alfaro, J., Lioudakis, G., Cuppens-Boulahia, N., Foley, S., Fitzgerald, W.M. (eds.) DPM/SETOP -2013. LNCS, vol. 8247, pp. 34–50. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54568-9_3
Zhou, K., Ren, J.: PassBio: privacy-preserving user-centric biometric authentication. IEEE Trans. Inf. Forensics Secur. 13, 3050–3063 (2018)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Cheon, J.H., Kim, D., Kim, D., Lee, J., Shin, J., Song, Y. (2021). Lattice-Based Secure Biometric Authentication for Hamming Distance. In: Baek, J., Ruj, S. (eds) Information Security and Privacy. ACISP 2021. Lecture Notes in Computer Science(), vol 13083. Springer, Cham. https://doi.org/10.1007/978-3-030-90567-5_33
Download citation
DOI: https://doi.org/10.1007/978-3-030-90567-5_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90566-8
Online ISBN: 978-3-030-90567-5
eBook Packages: Computer ScienceComputer Science (R0)