Impossibility of Efficient Information-Theoretic Fuzzy Extraction

Benjamin Fuller

Paper 2023/172

Impossibility of Efficient Information-Theoretic Fuzzy Extraction

Benjamin Fuller

, University of Connecticut

Abstract

Fuzzy extractors convert noisy signals from the physical world into reliable cryptographic keys. Fuzzy min-entropy is an important measure of the ability of a fuzzy extractor to distill keys from a distribution: in particular, it bounds the length of the key that can be derived (Fuller, Reyzin, and Smith, IEEE Transactions on Information Theory 2020). In general, fuzzy min-entropy that is superlogarithmic in the security parameter is required for a noisy distribution to be suitable for key derivation. There is a wide gap between what is possible with respect to computational and information-theoretic adversaries. Under the assumption of general-purpose obfuscation, keys can be securely derived from all distributions with superlogarithmic entropy. Against information-theoretic adversaries, however, it is impossible to build a single fuzzy extractor that works for all distributions (Fuller, Reyzin, and Smith, IEEE Transactions on Information Theory 2020). A weaker information-theoretic goal is to build a fuzzy extractor for each particular probability distribution. This is the approach taken by Woodage et al. (Crypto 2017). Prior approaches use the full description of the probability mass function and are inefficient. We show this is inherent: for a quarter of distributions with fuzzy min-entropy and $2^k$ points there is no secure fuzzy extractor that uses less $2^{\Theta(k)}$ bits of information about the distribution.} This result rules out the possibility of efficient, information-theoretic fuzzy extractors for many distributions with fuzzy min-entropy. We show an analogous result with stronger parameters for information-theoretic secure sketches. Secure sketches are frequently used to construct fuzzy extractors.

Note: Major technical and notational rework. Change in authorship.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. Designs, Codes and Cryptography
DOI: https://doi.org/10.1007/s10623-024-01376-z
Keywords: fuzzy extractors information-reconciliation secure sketches impossibility
Contact author(s): benjamin fuller @ uconn edu
History: 2024-03-14: last of 4 revisions; 2023-02-11: received; See all versions
Short URL: https://ia.cr/2023/172
License: CC BY

BibTeX

@misc{cryptoeprint:2023/172,
      author = {Benjamin Fuller},
      title = {Impossibility of Efficient Information-Theoretic Fuzzy Extraction},
      howpublished = {Cryptology ePrint Archive, Paper 2023/172},
      year = {2023},
      doi = {https://doi.org/10.1007/s10623-024-01376-z},
      note = {\url{https://eprint.iacr.org/2023/172}},
      url = {https://eprint.iacr.org/2023/172}
}