Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {Rj} using multiple pairs {(Wj, W ′ j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors. Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t = 0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t> 0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {Rj} using multiple pairs {(Wj, W ′ j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors. Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t = 0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t> 0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.
Consider two parties holding samples from correlated distributionsWandW′, respectively, where these samples are within distancetof each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret keyRby sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret${\ssr SK}_{\ssr Ext}$that they can use to generate a sequence of session keys{Rj}using multiple pairs{(Wj,Wj′)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects.The best prior solution for the keyless case with no errors (i.e.,t=0) requires the min-entropy ofWto exceed2n/3, wherenis the bit length ofW. Our solution applies whenever the min-entropy ofWexceeds the minimal thresholdn/2, and yields a longer key.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetrickey primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n 2, and require poor parameters even when n 2 < k ≪ n. On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [RW03], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing “non-malleable” seeded randomness extractors — if an attacker sees a random seed X and comes up with an arbitrarily related seed X ′, then we bound the relationship between R = Ext(W;X) and R ′ = Ext(W;X ′). We also extend our two-round key agreement protocol to the “fuzzy ” setting, where Alice and Bob share “close ” (but not equal) secrets WA and WB, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.
This paper explores what kinds of information two parties must communicate in order to correct errors which occur in a shared secret string W. Any bits they communicate must leak a significant amount of information about W --- that is, from the adversary's point of view, the entropy of W will drop significantly. Nevertheless, we construct schemes with which Alice and Bob can prevent an adversary from learning any useful information about W. Specifically, if the entropy of W is sufficiently high, then there is no function f(W) which the adversary can learn from the error-correction information with significant probability.This leads to several new results: (a) the design of noise-tolerant "perfectly one-way" hash functions in the sense of Canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets W; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data W, while also insuring that no sensitive information about W is leaked; and (c) noise tolerance and stateless key re-use in the Bounded Storage Model, resolving the main open problem of Ding [10].The heart of our constructions is the design of strong randomness extractors with the property that the source W can be recovered from the extracted randomness and any string W' which is close to W.
We consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers. Our protocol can be seen as an interactive version of robust fuzzy extractors (Boyen et al., Eurocrypt 2005, Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.
Cryptographic protocols, though used in a wide range of everyday tasks, are typically built for certain unrealistic ideal conditions in which the user is assumed to work. For example, one such condition that is implicitly assumed is that the user has perfect randomness that she can use as her cryptographic secret key. Another commonly made assumption is that the user runs her cryptographic tasks (such as encryption) on a device that is perfectly secure; that is, its internals are not tampered with or even observed by an adversary.
In this thesis, we focus on designing cryptographic techniques that are secure under less-than-ideal conditions. In order to remove the assumption that users share perfectly random secret keys, we study the problem of privacy amplification: key agreement between two parties who both know a weak secret w, such as a password. The goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from the adversary. R may then be used as a key for running symmetric cryptographic protocols (such as encryption or authentication). Because we make no computational assumptions, the entropy in R can come only from w. Thus such a protocol must minimize the entropy loss during its execution, so that R is as long as possible. In this thesis, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. The result is optimal up to constant factors. We also extend our results to the case where the users share correlated secrets w and w' . This setting occurs, for example, when the secrets are biometric readings taken at different points of time and is more generally known as information-reconciliation.