×

Robustly reusable fuzzy extractor from standard assumptions. (English) Zbl 1447.94058

Peyrin, Thomas (ed.) et al., Advances in cryptology – ASIACRYPT 2018. 24th international conference on the theory and application of cryptology and information security, Brisbane, QLD, Australia, December 2–6, 2018. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 11274, 459-489 (2018).
Summary: A fuzzy extractor (FE) aims at deriving and reproducing (almost) uniform cryptographic keys from noisy non-uniform sources. To reproduce an identical key \(R\) from subsequent readings of a noisy source, it is necessary to eliminate the noises from those readings. To this end, a public helper string \(P\), together with the key \(R\), is produced from the first reading of the source during the initial enrollment phase.{ }In this paper, we consider computational fuzzy extractor. We formalize robustly reusable fuzzy extractor (rrFE) which considers reusability and robustness simultaneously in the common reference string (CRS) model. Reusability of rrFE deals with source reuse. It guarantees that the key \(R\) output by fuzzy extractor is pseudo-random even if the initial enrollment is applied to the same source several times, generating multiple public helper strings and keys \((P_i,R_i)\). Robustness of rrFE deals with active probabilistic polynomial-time adversaries, who may manipulate the public helper string \(P_i\) to affect the reproduction of \(R_i\). Any modification of \({P}_i\) by the adversary will be detected by the robustness of rrFE.{ }We show how to construct an rrFE from a symmetric key encapsulation mechanism (SKEM), a secure sketch (SS), an extractor (Ext), and a lossy algebraic filter (LAF). We characterize the key-shift security notion of SKEM and the homomorphic properties of SS, Ext and LAF, which enable our construction of rrFE to achieve both reusability and robustness.{ }We present an instantiation of SKEM from the DDH assumption. Combined with the LAF by D. Hofheinz [Eurocrypt 2013, Lect. Notes Comput. Sci. 7881, 520–536 (2013; Zbl 1312.94056)], homomorphic SS and Ext, we obtain the first rrFE based on standard assumptions.
For the entire collection see [Zbl 1402.94010].

MSC:

94A60 Cryptography

Citations:

Zbl 1312.94056
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alamélou, Q., et al.: Pseudoentropic isometries: a new framework for fuzzy extractor reusability. In: Kim, J., Ahn, G., Kim, S., Kim, Y., López, J., Kim, T. (eds.) AsiaCCS 2018, pp. 673-684. ACM (2018). doi:10.1145/3196494.3196530
[2] Apon, D.; Cho, C.; Eldefrawy, K.; Katz, J.; Dolev, S.; Lodha, S., Efficient, reusable fuzzy extractors from LWE, Cyber Security Cryptography and Machine Learning, 1-18 (2017), Cham: Springer, Cham · Zbl 1492.94056 · doi:10.1007/978-3-319-60080-2_1
[3] Bennett, CH; DiVincenzo, DP, Quantum information and computation, Nature, 404, 6775, 247-255 (2000) · Zbl 1369.81023 · doi:10.1038/35005001
[4] Boyen, X.: Reusable cryptographic fuzzy extractors. In: Atluri, V., Pfitzmann, B., McDaniel, P.D. (eds.) CCS 2004, pp. 82-91. ACM (2004). doi:10.1145/1030083.1030096
[5] Boyen, X.; Dodis, Y.; Katz, J.; Ostrovsky, R.; Smith, A.; Cramer, R., Secure remote authentication using biometric data, Advances in Cryptology - EUROCRYPT 2005, 147-163 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94365 · doi:10.1007/11426639_9
[6] Canetti, R.; Fuller, B.; Paneth, O.; Reyzin, L.; Smith, A.; Fischlin, M.; Coron, J-S, Reusable fuzzy extractors for low-entropy distributions, Advances in Cryptology - EUROCRYPT 2016, 117-146 (2016), Heidelberg: Springer, Heidelberg · Zbl 1347.94022 · doi:10.1007/978-3-662-49890-3_5
[7] Cramer, R.; Dodis, Y.; Fehr, S.; Padró, C.; Wichs, D.; Smart, N., Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors, Advances in Cryptology - EUROCRYPT 2008, 471-488 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94333 · doi:10.1007/978-3-540-78967-3_27
[8] Cramer, R.; Shoup, V., Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. Comput., 33, 1, 167-226 (2003) · Zbl 1045.94013 · doi:10.1137/S0097539702403773
[9] Daugman, J., How iris recognition works, IEEE Trans. Circuits Syst. Video Techn., 14, 1, 21-30 (2004) · doi:10.1109/TCSVT.2003.818350
[10] Dodis, Y.; Katz, J.; Reyzin, L.; Smith, A.; Dwork, C., Robust fuzzy extractors and authenticated key agreement from close secrets, Advances in Cryptology - CRYPTO 2006, 232-250 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.94440 · doi:10.1007/11818175_14
[11] Dodis, Y.; Ostrovsky, R.; Reyzin, L.; Smith, AD, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data, SIAM J. Comput., 38, 1, 97-139 (2008) · Zbl 1165.94326 · doi:10.1137/060651380
[12] Dodis, Y.; Reyzin, L.; Smith, A.; Cachin, C.; Camenisch, JL, Fuzzy extractors: how to generate strong keys from biometrics and other noisy data, Advances in Cryptology - EUROCRYPT 2004, 523-540 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94368 · doi:10.1007/978-3-540-24676-3_31
[13] Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: Mitzenmacher, M. (ed.) STOC 2009, pp. 601-610. ACM (2009). doi:10.1145/1536414.1536496 · Zbl 1304.94048
[14] Fuller, B.; Meng, X.; Reyzin, L.; Sako, K.; Sarkar, P., Computational fuzzy extractors, Advances in Cryptology - ASIACRYPT 2013, 174-193 (2013), Heidelberg: Springer, Heidelberg · Zbl 1327.94045 · doi:10.1007/978-3-642-42033-7_10
[15] Hofheinz, D.; Johansson, T.; Nguyen, PQ, Circular chosen-ciphertext security with compact ciphertexts, Advances in Cryptology - EUROCRYPT 2013, 520-536 (2013), Heidelberg: Springer, Heidelberg · Zbl 1312.94056 · doi:10.1007/978-3-642-38348-9_31
[16] Imamog, A., Quantum information processing using quantum dot spins and cavity QED, Phys. Rev. Lett., 83, 20, 4204 (1999) · doi:10.1103/PhysRevLett.83.4204
[17] Jain, AK; Ross, A.; Prabhakar, S., An introduction to biometric recognition, IEEE Trans. Circuits Syst. Video Techn., 14, 1, 4-20 (2004) · doi:10.1109/TCSVT.2003.818349
[18] Kanukurthi, B.; Reyzin, L.; Ostrovsky, R.; De Prisco, R.; Visconti, I., An improved robust fuzzy extractor, Security and Cryptography for Networks, 156-171 (2008), Heidelberg: Springer, Heidelberg · Zbl 1180.68150 · doi:10.1007/978-3-540-85855-3_11
[19] Li, SZ; Jain, AK, Handbook of Face Recognition (2011), Heidelberg: Springer, Heidelberg · Zbl 1230.68002 · doi:10.1007/978-0-85729-932-1
[20] Marasco, E.; Ross, A., A survey on antispoofing schemes for fingerprint recognition systems, ACM Comput. Surv., 47, 2, 28:1-28:36 (2014) · doi:10.1145/2617756
[21] Rührmair, U., Sehnke, F., Sölter, J., Dror, G., Devadas, S., Schmidhuber, J.: Modeling attacks on physical unclonable functions. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) CCS 2010, pp. 237-249. ACM (2010). doi:10.1145/1866307.1866335
[22] Shoup, V., A Computational Introduction to Number Theory and Algebra (2006), Cambridge: Cambridge University Press, Cambridge · Zbl 1196.11002
[23] Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key generation. In: DAC 2007, pp. 9-14. IEEE (2007). doi:10.1145/1278480.1278484
[24] Wen, Y.; Liu, S.; Susilo, W.; Yang, G., Reusable fuzzy extractor from LWE, Information Security and Privacy, 13-27 (2018), Cham: Springer, Cham · Zbl 1444.94107 · doi:10.1007/978-3-319-93638-3_2
[25] Wen, Y., Liu, S.: Robustly reusable fuzzy extractor from standard assumptions. Cryptology ePrint Archive, Report 2018/818 (2018). https://eprint.iacr.org/2018/818 · Zbl 1447.94058
[26] Wen, Y.; Liu, S.; Han, S., Reusable fuzzy extractor from the decisional Diffie-Hellman assumption, Des. Codes Cryptogr., 86, 2495-2512 (2018) · Zbl 1437.94077 · doi:10.1007/s10623-018-0459-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.