×

Computational fuzzy extractors. (English) Zbl 1492.94108

Summary: Fuzzy extractors derive strong keys from noisy sources. Their security is usually defined information-theoretically, with gaps between known negative results, existential constructions, and polynomial-time constructions. We ask whether using computational security can close these gaps. We show the following:

i) Negative result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a secure sketch. We show that secure sketches defined using pseudoentropy instead of information-theoretic security are still subject to upper bounds from coding theory.
ii) Positive result: We show that our negative result can be avoided by constructing and analyzing a computational fuzzy extractor directly. We modify the code-offset construction to use random linear codes. Security is based on the Learning with Errors problem and holds when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed).

MSC:

94A60 Cryptography
94B99 Theory of error-correcting codes and error-detecting codes

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fuller, Benjamin; Meng, Xianrui; Reyzin, Leonid, Computational fuzzy extractors, (Advances in Cryptology - ASIACRYPT (2013), Springer), 174-193 · Zbl 1327.94045
[2] Daugman, John, How iris recognition works, IEEE Trans. Circuits Syst. Video Technol., 14, 1, 21-30 (January 2004)
[3] Tuyls, Pim; Schrijen, Geert-Jan; Skoric, Boris; Geloven, Jan; Verhaegh, Nynke; Wolters, Rob, Read-proof hardware from protective coatings, (Goubin, Louis; Matsui, Mitsuru, Cryptographic Hardware and Embedded Systems - CHES 2006. Cryptographic Hardware and Embedded Systems - CHES 2006, Lecture Notes in Computer Science, vol. 4249 (2006), Springer: Springer Berlin, Heidelberg), 369-383
[4] Suh, G. Edward; Devadas, Srinivas, Physical unclonable functions for device authentication and secret key generation, (Proceedings of the 44th Annual Design Automation Conference (2007), ACM), 9-14
[5] Castelluccia, Claude; Mutaf, Pars, Shake them up!: a movement-based pairing protocol for CPU-constrained devices, (Proceedings of the 3rd International Conference on Mobile Systems, Applications, and Services (2005), ACM), 51-64
[6] Bennett, Charles H.; Brassard, Gilles; Robert, Jean-Marc, Privacy amplification by public discussion, SIAM J. Comput., 17, 2, 210-229 (1988) · Zbl 0644.94010
[7] Dodis, Yevgeniy; Ostrovsky, Rafail; Reyzin, Leonid; Smith, Adam, Fuzzy extractors: how to generate strong keys from biometrics and other noisy data, SIAM J. Comput., 38, 1, 97-139 (2008) · Zbl 1165.94326
[8] Boyen, Xavier; Dodis, Yevgeniy; Katz, Jonathan; Ostrovsky, Rafail; Smith, Adam, Secure remote authentication using biometric data, (EUROCRYPT (2005), Springer), 147-163 · Zbl 1137.94365
[9] Dodis, Yevgeniy; Wichs, Daniel, Non-malleable extractors and symmetric key cryptography from weak secrets, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009), ACM: ACM New York, NY, USA), 601-610 · Zbl 1304.94048
[10] Chandran, Nishanth; Kanukurthi, Bhavana; Ostrovsky, Rafail; Reyzin, Leonid, Privacy amplification with asymptotically optimal entropy loss, (Proceedings of the 42nd ACM Symposium on Theory of Computing (2010), ACM: ACM New York, NY, USA), 785-794 · Zbl 1293.94101
[11] Chandran, Nishanth; Kanukurthi, Bhavana; Ostrovsky, Rafail; Reyzin, Leonid, Privacy amplification with asymptotically optimal entropy loss, J. ACM, 61, 5, 1-28 (2014) · Zbl 1321.94103
[12] Dupont, Pierre-Alain; Hesse, Julia; Pointcheval, David; Reyzin, Leonid; Yakoubov, Sophia, Fuzzy password-authenticated key exchange, (Advances in Cryptology - EUROCRYPT (2018), Springer), 393-424 · Zbl 1415.94425
[13] Nisan, Noam; Zuckerman, David, Randomness is linear in space, J. Comput. Syst. Sci., 43-52 (1993) · Zbl 0846.68041
[14] Shaltiel, Ronen, Recent developments in explicit constructions of extractors, Bull. Eur. Assoc. Theor. Comput. Sci., 77, 67-95, 10 (2002) · Zbl 1051.68070
[15] Fuller, Benjamin; Reyzin, Leonid; Smith, Adam, When are fuzzy extractors possible?, (Advances in Cryptology - ASIACRYPT (2016), Springer), 277-306 · Zbl 1404.94072
[16] Fuller, Benjamin; Reyzin, Leonid; Smith, Adam, When are fuzzy extractors possible?, IEEE Trans. Inf. Theory (2020) · Zbl 1446.94130
[17] Woodage, Joanne; Chatterjee, Rahul; Dodis, Yevgeniy; Juels, Ari; Ristenpart, Thomas, A new distribution-sensitive secure sketch and popularity-proportional hashing, (Advances in Cryptology-CRYPTO (2017), Springer), 682-710 · Zbl 1418.94064
[18] Fuller, Benjamin; Peng, Lowen, Continuous-source fuzzy extractors: source uncertainty and insecurity, (2019 IEEE International Symposium on Information Theory (ISIT) (2019), IEEE), 2952-2956
[19] Krawczyk, Hugo, Cryptographic extraction and key derivation: the HKDF scheme, (Advances in Cryptology-CRYPTO 2010 (2010), Springer), 631-648 · Zbl 1283.94072
[20] Barak, Boaz; Dodis, Yevgeniy; Krawczyk, Hugo; Pereira, Olivier; Pietrzak, Krzysztof; Standaert, François-Xavier; Yu, Yu, Leftover hash lemma, revisited, (Advances in Cryptology-CRYPTO 2011 (2011), Springer), 1-20 · Zbl 1287.94047
[21] Dachman-Soled, Dana; Gennaro, Rosario; Krawczyk, Hugo; Malkin, Tal, Computational extractors and pseudorandomness, (Theory of Cryptography (2012), Springer), 383-403 · Zbl 1304.68136
[22] Håstad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael, A pseudorandom generator from any one-way function, SIAM J. Comput., 28, 4, 1364-1396 (1999) · Zbl 0940.68048
[23] Hsiao, Chun-Yuan; Lu, Chi-Jen; Reyzin, Leonid, Conditional computational entropy, or toward separating pseudoentropy from compressibility, (EUROCRYPT (2007)), 169-186 · Zbl 1141.94357
[24] Barak, Boaz; Shaltiel, Ronen; Wigderson, Avi, Computational analogues of entropy, (11th International Conference on Random Structures and Algorithms (2003)), 200-215 · Zbl 1279.68074
[25] Goldreich, Oded; Levin, Leonid A., A hard-core predicate for all one-way functions, (Proceedings of the 21st Annual ACM Symposium on Theory of Computing (1989)), 25-32
[26] Haitner, Iftach; Reingold, Omer; Vadhan, Salil; Wee, Hoeteck, Inaccessible entropy, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009), ACM), 611-620 · Zbl 1304.94014
[27] Haitner, Iftach; Holenstein, Thomas; Reingold, Omer; Vadhan, Salil; Wee, Hoeteck, Universal one-way hash functions via inaccessible entropy, (Advances in Cryptology - EUROCRYPT (2010), Springer), 616-637 · Zbl 1280.94065
[28] Vadhan, Salil; Zheng, Colin Jia, Characterizing pseudoentropy and simplifying pseudorandom generator constructions, (Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), ACM), 817-836 · Zbl 1286.65008
[29] Haitner, Iftach; Reingold, Omer; Vadhan, Salil, Efficiency improvements in constructing pseudorandom generators from one-way functions, SIAM J. Comput., 42, 3, 1405-1430 (2013) · Zbl 1343.94060
[30] Juels, Ari; Sudan, Madhu, A fuzzy vault scheme, Des. Codes Cryptogr., 38, 237-257 (2006) · Zbl 1172.94578
[31] Juels, Ari; Wattenberg, Martin, A fuzzy commitment scheme, (Sixth ACM Conference on Computer and Communication Security (November 1999), ACM), 28-36
[32] Regev, Oded, On lattices, learning with errors, random linear codes, and cryptography, (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005), ACM: ACM New York, NY, USA), 84-93 · Zbl 1192.94106
[33] Regev, Oded, The learning with errors problem (invited survey), (Annual IEEE Conference on Computational Complexity (2010)), 191-204
[34] Regev, Oded, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56, 6, 1-40 (2009) · Zbl 1325.68101
[35] Döttling, Nico; Müller-Quade, Jörn, Lossy codes and a new variant of the learning-with-errors problem, (Johansson, Thomas; Nguyen, Phong Q., Advances in Cryptology - EUROCRYPT. Advances in Cryptology - EUROCRYPT, Lecture Notes in Computer Science, vol. 7881 (2013), Springer), 18-34 · Zbl 1300.94052
[36] Bogdanov, Andrej; Guo, Siyao; Masny, Daniel; Richelson, Silas; Rosen, Alon, On the hardness of learning with rounding over small modulus, (Theory of Cryptography Conference (2016), Springer), 209-224 · Zbl 1388.94035
[37] Bai, Shi; Lepoint, Tancrède; Roux-Langlois, Adeline; Sakzad, Amin; Stehlé, Damien; Steinfeld, Ron, Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance, J. Cryptol., 31, 2, 610-640 (2018) · Zbl 1444.94043
[38] Akavia, Adi; Goldwasser, Shafi; Vaikuntanathan, Vinod, Simultaneous hardcore bits and cryptography against memory attacks, (Omer, Reingold, Theory of Cryptography. Theory of Cryptography, Lecture Notes in Computer Science, vol. 5444 (2009), Springer: Springer Berlin, Heidelberg), 474-495 · Zbl 1213.94075
[39] Berlekamp, Elwyn; McEliece, Robert; van Tilborg, Henk, On the inherent intractability of certain coding problems, IEEE Trans. Inf. Theory, 24, 3, 384-386 (May 1978) · Zbl 0377.94018
[40] Kamp, Jesse; Zuckerman, David, Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, SIAM J. Comput., 36, 5, 1231-1247 (2007) · Zbl 1124.68036
[41] Canetti, Ran; Fuller, Benjamin; Paneth, Omer; Reyzin, Leonid; Smith, Adam, Reusable fuzzy extractors for low-entropy distributions, (Advances in Cryptology - EUROCRYPT (2016), Springer), 117-146 · Zbl 1347.94022
[42] Bitansky, Nir; Canetti, Ran; Tauman Kalai, Yael; Paneth, Omer, On virtual grey box obfuscation for general circuits, Algorithmica, 79, 4, 1014-1051 (2017) · Zbl 1397.94050
[43] Boyen, Xavier, Reusable cryptographic fuzzy extractors, (Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS ’04 (2004), ACM: ACM New York, NY, USA), 82-91
[44] Apon, Daniel; Cho, Chongwon; Eldefrawy, Karim; Katz, Jonathan, Efficient, reusable fuzzy extractors from LWE, (International Conference on Cyber Security Cryptography and Machine Learning (2017), Springer), 1-18 · Zbl 1492.94056
[45] Wen, Yunhua; Liu, Shengli; Han, Shuai, Reusable fuzzy extractor from the decisional Diffie-Hellman assumption, Des. Codes Cryptogr., 1-18 (2018) · Zbl 1437.94077
[46] Alamélou, Quentin; Berthier, Paul-Edmond; Cachet, Chloé; Cauchie, Stéphane; Fuller, Benjamin; Gaborit, Philippe; Simhadri, Sailesh, Pseudoentropic isometries: a new framework for fuzzy extractor reusability, (AsiaCCS 2018 (2018))
[47] Wen, Yunhua; Liu, Shengli, Reusable fuzzy extractor from LWE, (Australasian Conference on Information Security and Privacy (2018), Springer), 13-27 · Zbl 1444.94107
[48] Herder, Charles; Ren, Ling; van Dijk, Marten; Yu, Meng-Day; Devadas, Srinivas, Trapdoor computational fuzzy extractors and stateless cryptographically-secure physical unclonable functions, IEEE Trans. Dependable Secure Comput., 14, 1, 65-82 (2017)
[49] Blum, Avrim; Furst, Merrick; Kearns, Michael; Lipton, Richard J., Cryptographic primitives based on hard learning problems, (Advances in Cryptology - CRYPTO (1993), Springer), 278-291 · Zbl 0870.94021
[50] Huth, Christopher; Becker, Daniela; Guajardo, Jorge; Duplys, Paul; Güneysu, Tim, LWE-based lossless computational fuzzy extractor for the Internet of things, (Hardware Oriented Security and Trust (HOST), 2017 IEEE International Symposium on (2017), IEEE), 154
[51] Christopher Huth, Daniela Becker, Jorge Guajardo, Paul Duplys, Tim Güneysu, Securing systems with scarce entropy: LWE-based lossless computational fuzzy extractor for the IoT, IACR Cryptology ePrint Archive 2016/982, 2016.
[52] Huth, Christopher; Becker, Daniela; Guajardo Merchan, Jorge; Duplys, Paul; Güneysu, Tim, Securing systems with indispensable entropy: LWE-based lossless computational fuzzy extractor for the Internet of things, IEEE Access, 5, 11909-11926 (2017)
[53] Yasunaga, Kenji; Yuzawa, Kosuke, On the possibilities and limitations of computational fuzzy extractors (2014), Cryptology ePrint Archive, Report 2014/605
[54] Simhadri, Sailesh; Steel, James; Fuller, Benjamin, Reusable authentication from the iris, (Information Security Conference (2019)), 465-485
[55] Jin, Chenglu; Herder Ling Ren, Charles; Nguyen, Phuong; Fuller, Benjamin; Devadas, Srinivas; van Dijk, Marten, FPGA implementation of a cryptographically-secure puf based on learning parity with noise, Cryptography, 1, 3, 23 (2017)
[56] Vadhan, Salil, Pseudorandomness. Foundations and Trends in Theoretical Computer Science (2012), NOW Publishers
[57] Gentry, Craig; Wichs, Daniel, Separating succinct non-interactive arguments from all falsifiable assumptions, (Proceedings in the 43rd Annual ACM Symposium on the Theory of Computation (2011)), 99-108 · Zbl 1288.94063
[58] Reyzin, Leonid, Some notions of entropy for cryptography, (Information Theoretic Security (2011), Springer), 138-142 · Zbl 1295.94136
[59] Shannon, Claude E.; Weaver, Warren; Blahut, Richard E.; Hajek, Bruce, The Mathematical Theory of Communication, vol. 117 (1949), University of Illinois Press: University of Illinois Press Urbana · Zbl 0041.25804
[60] Cover, Thomas M.; Thomas, Joy A., Elements of Information Theory (2006), Wiley-InterScience · Zbl 1140.94001
[61] Kanukurthi, Bhavana; Reyzin, Leonid, Key agreement from close secrets over unsecured channels, (Advances in Cryptology - EUROCRYPT (2009)), 206-223 · Zbl 1239.94076
[62] Venkatesan Guruswami, Introduction to coding theory - lecture 2: Gilbert-Varshamov bound, University Lecture, 2010.
[63] Cooper, Colin, On the rank of random matrices, Random Struct. Algorithms, 16, 2, 209-232 (2000) · Zbl 0953.15025
[64] Peikert, Chris, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009), ACM: ACM New York, NY, USA), 333-342 · Zbl 1304.94079
[65] Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien, Classical hardness of learning with errors, (Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing (2013), ACM), 575-584 · Zbl 1293.68159
[66] Daniele, Micciancio; Peikert, Chris, Hardness of SIS and LWE with small parameters, (Advances in Cryptology - CRYPTO 2013. Advances in Cryptology - CRYPTO 2013, Lecture Notes in Computer Science (2013)) · Zbl 1310.94161
[67] Lee, Pil Joong; Brickell, Ernest F., An observation on the security of Mceliece’s public-key cryptosystem, (Workshop on the Theory and Application of Cryptographic Techniques (1988), Springer), 275-280 · Zbl 0655.94006
[68] Berman, Piotr; Karpinski, Marek, Approximating minimum unsatisfiability of linear equations, (Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2002), Society for Industrial and Applied Mathematics), 514-516 · Zbl 1254.68348
[69] Peters, Christiane, Information-set decoding for linear codes over Fq, (International Workshop on Post-Quantum Cryptography (2010), Springer), 81-94 · Zbl 1284.94101
[70] Canetti, Ran; Goldwasser, Shafi, An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack, (Advances in Cryptology - EUROCRYPT (1999), Springer), 90-106 · Zbl 0948.94008
[71] Peikert, Chris, On error correction in the exponent, (Theory of Cryptography Conference (2006), Springer), 167-183 · Zbl 1112.94019
[72] Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal, On pseudorandom generators with linear stretch in NC 0, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2006)), 260-271 · Zbl 1155.94363
[73] Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal, On pseudorandom generators with linear stretch in nc 0, Comput. Complex., 17, 1, 38-69 (2008) · Zbl 1242.94016
[74] Blanton, Marina; Hudelson, William MP, Biometric-based non-transferable anonymous credentials, (International Conference on Information and Communications Security (2009), Springer), 165-180
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.