We study the problem of "privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve's point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.).
We study the problem of "privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve's point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.).
We study the problem of “privacy amplification”: key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve’s point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.). 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. The best previous results have entropy loss of Θ(κ 2), where κ is the security parameter, thus requiring the password to be very long even for small values of κ. In this work, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. The result is optimal up
We study the problem of “privacy amplification”: key agreement between two parties who both know a weak secret w , such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w , so we assume only that w has some entropy from Eve’s point of view. Thus, the goal of the protocol is to convert this nonuniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.). 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. The best previous results have entropy loss of Θ( κ 2 ), where κ is the security parameter, thus requiring the password to be very long even for small values of κ . In this work, 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 achieve our improvement through a somewhat surprising application of error-correcting codes for the edit distance. The protocol can be extended to provide also “information reconciliation,” that is, to work even when the two parties have slightly different versions of w (e.g., when biometrics are involved).
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.
We study the problem of privacy amplification with an active adversary in the information theoretic setting. In this setting, two parties Alice and Bob start out with a shared n-bit weak random string W, and try to agree on a secret random key R over a public channel fully controlled by an active and unbounded adversary. Typical assumptions are that these two parties have access to local private uniform random bits. In this paper we seek to minimize the requirements on the local randomness used by the two parties. We make two improvements over previous results. First, we reduce the number of random bits needed for each party to Θ(ℓ+logn), where ℓ is the security parameter, as long as W has min-entropy nΩ(1). Previously, the best known result needs to use Θ((ℓ+logn)logn) bits. Our result is also asymptotically optimal. Second, we generalize the problem to the case where the two parties only have local weak random sources instead of truly uniform random bits. We show that when each party has a local weak random source with min-entropy >n/2, there is an efficient privacy amplification protocol that works nearly as good as if the two parties have access to local uniform random bits. Next, in the case where each party only has a weak random source with arbitrarily linear min-entropy, we give an efficient privacy amplification protocol where we can achieve security parameter up to Ω(logk). Our results give the first protocols that achieve privacy amplification when each party only has access to a local weak random source.
We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing “optimal ” efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k−m (it is known that the optimal value for L = O(λ), where ε = 2−λ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some “useful information ” about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys.
In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly random x and a uniformly random seed y, and outputs a string which appears uniform, even given y. For a nonmalleable extractor nmExt, the output nmExt(x,y) should appear uniform given y as well as nmExt(x,A(y)), where A is an arbitrary function with A(y)=y. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is 1/2+α for any α>0. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for “privacy amplification": key agreement between two parties who share a weakly random secret. Our protocols work in the presence of an active adversary with unlimited computational power and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate δ for any constant δ>0, our new protocol takes a constant (polynomial in 1/δ) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.