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

Annual Symposium on Foundations of Computer Science

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness

Yael Tauman Kalai, Xin Li, Anup Rao

Published Oct 1, 2009• 44 citations
Publisher

Abstract

We show how to efficiently extract truly random bits from two independent sources of linear min-entropy, under a computational assumption. The assumption we rely on is the existence of an efficiently computable permutation f1, such that for any source X ¿ {0, 1}nwith linear min-entropy, any circuit of size poly(n) cannot invert f(X) with non-negligible probability. Under the stronger assumption that f(X) cannot be inverted even by circuits of size poly(nlog n) with nonnegligible probability, we design a lossless computational network extractor protocol. Namely, we design a protocol for a set of players, each with access to an independent source of linear min-entropy, with the guarantee that at the end of the protocol, each honest player is left with bits that are computationally indistinguishable from being uniform and private. Our protocol succeeds as long as there are at least two honest players. Our results imply that if such one-way permutations exist, and enhanced trapdoor permutations exist, then secure multiparty computation with imperfect randomness is possible for any number of players, as long as at least two of them are honest. We also construct a network extractor protocol for the case where each source has only polynomially-small min-entropy (n¿for some constant ¿ > 0). For this we need at least a constant u(¿) (which depends on ¿) number of honest players, and we need that the one-way permutation is hard to invert even on polynomially small min-entropy sources.

DOI
10.1109/focs.2009.61

Related papers

Network Extractor Protocols

Yael Tauman Kalai, Xin Li, Anup Rao +1 more

We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•38 citations

Extractors: Low Entropy Requirements Colliding With Non-Malleability

Divesh Aggarwal, Eldon Chung, Maciej Obremski

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

arXiv:2111.04157•Electronic colloquium on computational complexity•Nov 7, 2021•3 citations

Extracting Correlations

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky +1 more

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

Annual Symposium on Foundations of Computer Science•Oct 1, 2009•47 citations

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function $\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$ that takes two inputs---a weak source $W$ and a uniform (independent) seed $S$---and outputs a string $\mathsf{nmExt}(W,S)$ that is nearly uniform given the seed $S$ as well as the value $\mathsf{nmExt}(W,S')$ for any seed $S'\neq S$ that may be determined as an arbitrary function of $S$. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01\cdot\log n\leq d\leq n$, we present an explicit construction of a nonmalleable extractor $\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$, with $m=\Omega(d)$ and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output $\mathsf{nmExt}(W,S)$ is nearly uniform given the seed $S$ as well as the values $\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)$ for several seeds $S_1,\dots,S_t$ that may be determined as an arbitrary function of $S$, as long as $S\notin\{S_1,\dots,S_t\}$. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2+\delta$ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.

SIAM Journal on Computing•Jan 1, 2014•22 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

Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.

arXiv:1603.05226•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•26 citations
We show how to efficiently extract truly random bits from two independent sources of linear min-entropy, under a computational assumption. The assumption we rely on is the existence of an efficiently computable permutation f1, such that for any source X ¿ {0, 1}nwith linear min-entropy, any circuit of size poly(n) cannot invert f(X) with non-negligible probability. Under the stronger assumption that f(X) cannot be inverted even by circuits of size poly(nlog n) with nonnegligible probability, we design a lossless computational network extractor protocol. Namely, we design a protocol for a set of players, each with access to an independent source of linear min-entropy, with the guarantee that at the end of the protocol, each honest player is left with bits that are computationally indistinguishable from being uniform and private. Our protocol succeeds as long as there are at least two honest players. Our results imply that if such one-way permutations exist, and enhanced trapdoor permutations exist, then secure multiparty computation with imperfect randomness is possible for any number of players, as long as at least two of them are honest. We also construct a network extractor protocol for the case where each source has only polynomially-small min-entropy (n¿for some constant ¿ > 0). For this we need at least a constant u(¿) (which depends on ¿) number of honest players, and we need that the one-way permutation is hard to invert even on polynomially small min-entropy sources.
We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about 1/21/21/2, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to 111 and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have 0.80.80.8 entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate 12\frac 1 221​, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.
Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.
Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function nmExt:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m that takes two inputs---a weak source WWW and a uniform (independent) seed SSS---and outputs a string nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) that is nearly uniform given the seed SSS as well as the value nmExt(W,S′)\mathsf{nmExt}(W,S')nmExt(W,S′) for any seed S′≠SS'\neq SS′=S that may be determined as an arbitrary function of SSS. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers nnn and ddd such that 2.01⋅log⁡n≤d≤n2.01\cdot\log n\leq d\leq n2.01⋅logn≤d≤n, we present an explicit construction of a nonmalleable extractor nmExt ⁣:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m, with m=Ω(d)m=\Omega(d)m=Ω(d) and error exponentially small in mmm. The extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) is nearly uniform given the seed SSS as well as the values nmExt(W,S1),…,nmExt(W,St)\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)nmExt(W,S1​),…,nmExt(W,St​) for several seeds S1,…,StS_1,\dots,S_tS1​,…,St​ that may be determined as an arbitrary function of SSS, as long as S∉{S1,…,St}S\notin\{S_1,\dots,S_t\}S∈/{S1​,…,St​}. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2+δ1/2+\delta1/2+δ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.
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 make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.