Chinese Journal of Computers

A Strong Privacy Amplification Protocol by Unconditionally Secure Authentication

Liu Sheng

Published Jan 1, 2000• 0 citations

Abstract

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.

Related papers

Implementation of Privacy Amplification Secure Against Active Adversaries

Sheng Liu

This paper proposes a protocol that enables communication over public channel to be authenticated by the partially secret common information between the two parties,and makes privacy amplification secure against active adversaries with some probability.At last,the relationship between the block size and the success probability of active attack is analyzed and a lower bound on size of bits of the common string needed to implement privacy amplification is given.

Dianzi xuebaoJan 1, 19990 citations

Secret-Key Agreement Over Unauthenticated Public Channels—Part III: Privacy Amplification

I. Motivation, Preliminaries

This is the third part of a three-part paper on se- cret-key agreement secure against active adversaries. Here, we con- sider the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary. The problem of generating a key in this case has been well studied in the passive-adversary model—for instance, in the context of quantum key agreement—under the name of privacy amplification. We consider the same problem with respect to an ac- tive adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy ampli- fication secure against an adversary whose knowledge about the initial partially string is limited to one third of the length of this string. Our results are based on novel techniques for au- thentication secure even against adversaries knowing a substantial amount of the secret key. information about . From Eve's point of view, the length of can in this case be roughly equal to the Renyi entropy of . In this paper, we investigate the same problem under the as- sumption that the communication between Alice and Bob is not authenticated. Note that, in contrast to the model where many independent repetitions of the involved random variables are given (15), the same piece of information must be used here both for authentication and as the input for privacy amplifica- tion. Two problems that arise in this context are authentication with an only partially key, and the fact that this authenti- cation leaks information about , hence potentially also about , to the adversary. We show that for our purpose, a new, inter- active, authentication method is better than one-way authentica- tion by strongly universal hashing, and that so-called extractors, requiring fewer random bits (i.e., shorter messages to be com- municated), are a better technique for privacy amplification than

Jan 1, 20030 citations

A privacy amplification protocol against active attacks in information theoretically secret key agreement

Q.H. Wang, X.J. Wang, Q.Y. Lv & X.Y. Ye

Privacy Amplification, introduced by Bennett et. al in [1] and generalized in [2], is the technique of shrinking a partially secret string to a highly secret one by public discussion. More precisely, in the privacy amplification phase, two legitimate parties, Alice and Bob, who share a partially secret string S about an opponent Eve has partial information to extract, and a shorter but highly-secret string S' by communication through an public channel such that Eve’s information about S' is negligible, i.e., ε= ≥ −S' U uH ( / ) log S2 | '| holds with very high probability for some small ε > 0, where the random variable U summarizes Eve’s complete knowledge about S', and u is the particular value known to Eve [2]. Privacy amplification is an important step in both quantum cryptography and key theoretically secret information agreement [3].

CRC Press eBooksJun 29, 20151 citation

Privacy amplification against active attacks withstrong robustness

Liu, Wang

An improvement is made to a recently proposed protocol by Wolf. Privacy amplification is achieved for communication over an insecure and non-authentic channel for sufficiently large n, the size of string S shared by the two parties, when the adversary's Rényi entropy about S exceeds only n/2 rather than 2n/3.

Electronics LettersApr 29, 19990 citations

Secret-key agreement over unauthenticated public channels-part III: privacy amplification

Ueli M. Maurer, Stefan Wolf

For pt. II see ibid., vol.49, no.4, p.832-38 (2003). Here, we consider the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary. The problem of generating a secret key in this case has been well studied in the passive-adversary model - for instance, in the context of quantum key agreement - under the name of privacy amplification. We consider the same problem with respect to an active adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy amplification secure against an adversary whose knowledge about the initial partially secret string is limited to one third of the length of this string. Our results are based on novel techniques for authentication secure even against adversaries knowing a substantial amount of the "secret" key.

IEEE Transactions on Information TheoryApr 1, 2003158 citations

Privacy amplification with asymptotically optimal entropy loss

Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky +1 more

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).

Journal of the ACMSep 8, 20143 citations