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 f, such that for any source X in {0,1}^n with linear 
min-entropy, any circuit of size poly(n^{\log n})cannot invert f(X) with 
non-negligible probability.
 
We use our 2-source extractor to design a computational network 
extractor protocol. Namely, we design a protocol
for a set of processors, each with access to an independent source of 
linear min-entropy, with the guarantee that at the end of the protocol, 
each honest processor 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. 
 
This is joint work with Xin Li and Anup Rao.