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 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/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 21, 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.
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 21, 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.
We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new challenges such as potential entanglement in the side information, it is not a prior clear under what conditions do quantum multi-source extractors exist; the only previous work is [KK12], where the classical inner-product two-source extractors of [CG88] and [DEOR04] are shown to be quantum secure in the restricted Independent Adversary (IA) Model and entangled Bounded Storage (BS) Model. In this paper we propose a new model called General Entangled (GE) Adversary Model, which allows arbitrary entanglement in the side information and subsumes both the IA model and the BS model. We proceed to show how to construct GE-secure quantum multi-source extractors. To that end, we propose another model called One-sided Adversary (OA) Model, which is weaker than all the above models. Somewhat surprisingly, we establish equivalence between strong OA-security and strong GE-security. As a result, all classical multi-source extractors can either directly work, or be modified to work in the GE model at the cost of one extra random source. Thus, our constructions essentially match the best known constructions of classical multi-source extractors. We also apply our techniques to two important problems in cryptography and distributed computing --- privacy amplification and network extractor. We show that as long as the sources have certain amounts of conditional min-entropy in our GE model (even with entangled quantum side information), we can design very efficient privacy amplification protocols and network extractors.
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.
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.