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

arXiv:1011.2551

On the Problem of Local Randomness in Privacy Amplification with an Active Adversary

Xin Li

Published Nov 11, 2010• 1 citation
arXivHTMLPDF

Abstract

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 $Θ(\ell+\log n)$, where $\ell$ is the security parameter, as long as $W$ has min-entropy $n^{Ω(1)}$. Previously, the best known result needs to use $Θ((\ell+\log n)\log n)$ 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 $Ω(\log k)$. Our results give the first protocols that achieve privacy amplification when each party only has access to a local weak random source.

DOI
10.48550/arxiv.1011.2551

Related papers

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

•Jan 1, 2012•0 citations

Amplifying Privacy in Privacy Amplification.

Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi +2 more

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.

•Jan 1, 2013•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 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 ACM•Sep 8, 2014•3 citations

Privacy Amplification With Tamperable Memory via Non-Malleable Two-Source Extractors

Divesh Aggarwal, Maciej Obremski, João Ribeiro +2 more

We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed tofully corruptthe internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: 1) we give a privacy amplification protocol via low-error non-malleable two-source extractors with one source having low min-entropy. In particular, this implies the existence of such (non-efficient) protocols; 2) we show that even slight improvements to the state-of-the-art explicit non-malleable two-source extractors would lead to explicit low-error, low min-entropy two-source extractors, thereby resolving a long-standing open question. This suggests that obtaining (information-theoretically secure)explicitnon-malleable two-source extractors for (1) might be hard; 3) we present explicit constructions of low-error, low min-entropy non-malleable two-source extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasi-polynomial hardness of DDH or the existence of nearly-optimal collision-resistant hash functions; 4) we instantiate our privacy amplification protocol with the above mentioned non-malleable two-source extractors in the CRS model, leading to explicit, computationally-secure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasi-polynomial hardness of DDH to sub-exponential hardness of DDH.We emphasize that each of the first three results can be read independently.

IEEE Transactions on Information Theory•Apr 14, 2022•2 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

Non-malleable extractors and symmetric key cryptography from weak secrets

Yevgeniy Dodis, Daniel Wichs

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.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•142 citations
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 nnn-bit weak random string WWW, and try to agree on a secret random key RRR 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 Θ(ℓ+log⁡n)Θ(\ell+\log n)Θ(ℓ+logn), where ℓ\ellℓ is the security parameter, as long as WWW has min-entropy nΩ(1)n^{Ω(1)}nΩ(1). Previously, the best known result needs to use Θ((ℓ+log⁡n)log⁡n)Θ((\ell+\log n)\log n)Θ((ℓ+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> n/2>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 Ω(log⁡k)Ω(\log k)Ω(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 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 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.
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 extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed tofully corruptthe internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: 1) we give a privacy amplification protocol via low-error non-malleable two-source extractors with one source having low min-entropy. In particular, this implies the existence of such (non-efficient) protocols; 2) we show that even slight improvements to the state-of-the-art explicit non-malleable two-source extractors would lead to explicit low-error, low min-entropy two-source extractors, thereby resolving a long-standing open question. This suggests that obtaining (information-theoretically secure)explicitnon-malleable two-source extractors for (1) might be hard; 3) we present explicit constructions of low-error, low min-entropy non-malleable two-source extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasi-polynomial hardness of DDH or the existence of nearly-optimal collision-resistant hash functions; 4) we instantiate our privacy amplification protocol with the above mentioned non-malleable two-source extractors in the CRS model, leading to explicit, computationally-secure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasi-polynomial hardness of DDH to sub-exponential hardness of DDH.We emphasize that each of the first three results can be read independently.
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 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.