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

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 f 1 , such that for any source X ∈ {0, 1}n with linear minentropy, 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(nlogn) 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.