Network Extractor Protocols

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 (log n) 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 n Omega(1).

Authors

• Yael Tauman Kalai
• Xin Li 0006
• Anup Rao 0001
• David Zuckerman

Keywords

• Access protocols
• Cryptography
• Distributed computing
• Data mining
• Cryptographic protocols
• Computer networks
• Entropy
• Computational modeling
• Computer science
• Nominations and elections
• Information Theory
• Number Of Parties
• Multi-party Computation
• Leader Election
• Diffie-Hellman Problem
• Row Vector
• Strong Assumptions
• End Of Protocol
• End Of Round
• Synchronization Of Networks
• Private Sources
• Source Of Randomness
• Random Bits
• Small Chunks
• Secure Channel
• Weak Source
• Random String
• Broadcast Channel
• Random Yield
• Zero-knowledge Proof
• Network
• Extractor