Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

I. Motivation, Preliminaries

Published Jan 1, 2003• 0 citations
OpenAlex

Abstract

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

Related papers

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 Theory•Apr 1, 2003•158 citations

Secret-key agreement over unauthenticated public channels-part I: definitions and a completeness result

Ueli M. Maurer, Stefan Wolf

This is the first part of a three-part paper on secret-key agreement secure against active adversaries. In all three parts, we address the question whether two parties, knowing some correlated pieces of information X and Y, respectively, can generate a string S about which an adversary, knowing some information Z and having read and write access to the communication channel used by the legitimate partners, is almost completely ignorant. Whether such key agreement is possible, and if yes at which rate, is an inherent property of the joint probability distribution P/sub XYZ/. In this part, we first prove a number of general impossibility results. We then consider the important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment. In this case, the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature: either a secret key can be generated at the same rate as in the (well-studied) passive-adversary case, or such secret-key agreement is completely impossible. The exact condition characterizing the two cases is presented.

IEEE Transactions on Information Theory•Apr 1, 2003•159 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 eBooks•Jun 29, 2015•1 citation

A Strong Privacy Amplification Protocol by Unconditionally Secure Authentication

Liu Sheng

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.

Chinese Journal of Computers•Jan 1, 2000•0 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 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.).

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•37 citations

A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries

Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin +1 more

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret $X$ in order to establish a shared private key $K$ by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS'12), and is able to extract from source of min-entropy rates larger than $1/2$. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.

arXiv:1710.00557•Oct 2, 2017•2 citations
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
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.
This is the first part of a three-part paper on secret-key agreement secure against active adversaries. In all three parts, we address the question whether two parties, knowing some correlated pieces of information X and Y, respectively, can generate a string S about which an adversary, knowing some information Z and having read and write access to the communication channel used by the legitimate partners, is almost completely ignorant. Whether such key agreement is possible, and if yes at which rate, is an inherent property of the joint probability distribution P/sub XYZ/. In this part, we first prove a number of general impossibility results. We then consider the important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment. In this case, the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature: either a secret key can be generated at the same rate as in the (well-studied) passive-adversary case, or such secret-key agreement is completely impossible. The exact condition characterizing the two cases is presented.
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].
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.
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.).
In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret XXX in order to establish a shared private key KKK by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS'12), and is able to extract from source of min-entropy rates larger than 1/21/21/2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.