Lowen and I just received word of acceptance of our recent work to ISIT. This papers asks whether you can build a universal fuzzy extractor for all high fuzzy min-entropy distributions. That is, can we have one construction that always just works. Unfortunately, the answer is negative. It is possible to artificially construct families of distributions that are impossible to simultaneously secure. This paper shares a lot of techniques with prior work of myself, Reyzin, and Smith. Excited to talk about these techniques more with the information theory community!
information theory
Presentation at Asiacrypt 2016
I just presented our paper “When are Fuzzy Extractors Possible?” with Leonid Reyzin and Adam Smith at Asiacrypt 2016. The talk video is available here: https://youtu.be/eiKqok3pNIs?t=13906 and the slides are here: fuzzy-extractors-when-possible-asiacrypt
When are Fuzzy Extractors Possible?
Benjamin Fuller, Leonid Reyzin, and Adam Smith. When are Fuzzy Extractors Possible? Asiacrypt 2016.
Abstract
Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.
We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the \emph{ideal} security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor.
We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy min-entropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy.
In this paper, we show that fuzzy min-entropy is also sufficient for information-theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor.
Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. We show that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This result emphasizes the importance of accurate models of high entropy sources.
Unifying Leakage Classes
Benjamin Fuller and Ariel Hamlin. Unifying Leakage Classes: Simulatable Leakage and Pseudoentropy. ICITS 2015.
Abstract
Leakage-resilient cryptography builds systems that withstand partial adversary knowledge of secret state. Ideally, leakage-resilient systems withstand current and future attacks; restoring confidence in the security of implemented cryptographic systems. Understanding the relation between classes of leakage functions is an important aspect.
In this work, we consider the memory leakage model, where the leakage class contains functions over the system’s entire secret state. Standard classes include functions with bounded output length, functions that retain (pseudo)~entropy in the secret, and functions that leave the secret computationally unpredictable.
Standaert, Pereira, and Yu (Crypto, 2013) introduced a new class of leakage functions they call simulatable leakage. A leakage function is simulatable if a simulator can produce indistinguishable leakage without access to the true secret state. We extend their notion to general applications and consider two versions. For weak simulatability: the simulated leakage must be indistinguishable from the true leakage in the presence of public information. For strong simulatability, this requirement must also hold when the distinguisher has access to the true secret state. We show the following: * Weakly simulatable functions retain computational unpredictability. * Strongly simulatability functions retain pseudoentropy. * There are bounded length functions that are not weakly simulatable. * There are weakly simulatable functions that remove pseudoentropy. * There are leakage functions that retain computational unpredictability are not weakly simulatable.
Strong Key Derivation from Noisy Sources
My Ph.D. has been completed and defended. It is titled Strong Key Derivation from Noisy Sources. It is largely drawn from three papers Computational Fuzzy Extractors, Reusable Fuzzy Extractors for Low-Entropy Distributions, and When are Fuzzy Extractors Possible? Those papers are more up-to-date than my Ph.D. My Ph.D does contain a cohesive summary of the results that can be useful as an introduction.
A Unified Approach to Deterministic Encryption
Benjamin Fuller, Adam O’Neill, and Leonid Reyzin. A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy. Theory of Cryptography 2012.
Abstract
This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include:
- The first construction from any trapdoor function that has sufficiently many hardcore bits.
- The first construction that provides “bounded” multi-message security (assuming lossy trapdoor functions).
The security proofs for these schemes are enabled by three tools that are of broader interest:
- A weaker and more precise sufficient condition for semantic security on a high-entropy message distribution. Namely, we show that to establish semantic security on a distribution M of messages, it suffices to establish indistinguishability for all conditional distribution M|E, where E is an event of probability at least 1/4. (Prior work required indistinguishability on all distributions of a given entropy.)
- A result about computational entropy of conditional distributions. Namely, we show that conditioning on an event E of probability p reduces the quality of computational entropy by a factor of p and its quantity by log_2 1/p.
- A generalization of leftover hash lemma to correlated distributions.
We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking \lambda bits of information reduces the quality of computational entropy by a factor of 2^\lambda and its quantity by \lambda.