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).
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).
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 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 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.
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.
Communications over the public channel should be authenticated to make privacy amplification against active adversaries possible. A new method of constructing authentication codes from error correcting codes is proposed and analyzed, and an arbitrary q ary code( q is a prime power) can be transformed into an authentication code according to the method. When the two communicants share n bit partially secret string S , an authentication scheme can be constructed from a ( 2 m,k,2 m-k+1 ) extended Reed Solomon code, where m=[XXZS-ZSX*3Y0]n/k[XXYS-YSX*3Y0] and 2 mk . As long as the two parties share an authentication key of at least 3 m bit, there exists a strong protocol for privacy amplification which ensures that the probability that the adversary successfully implements active attacks is at most k/2 m , and a highly secret string can be distilled of length about the Renyi entropy of S when given Eve's complete knowledge U=u about S . As n is large enough, more than 3 m bits secret string can always be distilled, thus the protocol is practical.