Multiparty Protocols Tolerating Half Faulty Processors

We show that a complete broadcast network of n processors can evaluate any function fx₁,...,x_n) at private inputs supplied by each processor, revealing no information other than the result of the function, while tolerating up to t maliciously faulty parties for 2t < n. This improves the previous bound of 3t < n on the tolerable number of faults [BGW88, CCD88]. We demonstrate a resilient method to multiply secretly shared values without using unproven cryptographic assumptions. The crux of our method is a new, non-cryptographic zero-knowledge technique which extends verifiable secret sharing to allow proofs based on secretly shared values. Under this method, a single party can secretly share values v₁,...,v_m along with another secret w = P(v₁,...,v_m), where P is any polynomial size circuit; and she can prove to all other parties that w = P(v₁,...,v_m), without revealing w or any other information. Our protocols allow an exponentially small chance of error, but are provably optimal in their resilience against Byzantine faults. Furthermore, our solutions use operations over exponentially large fields, greatly reducing the amount of interaction necessary for computing natural functions.