On the Power of Correlated Randomness in Secure Computation

We investigate the extent to which correlated secret randomness can help in secure computation with no honest majority. It is known that correlated randomness can be used to evaluate any circuit of size

s

with perfect security against semi-honest parties or statistical security against malicious parties, where the communication complexity grows linearly with

s

. This leaves open two natural questions: (1) Can the communication complexity be made independent of the circuit size? (2) Is it possible to obtain

perfect

security against malicious parties?

We settle the above questions, obtaining both positive and negative results on unconditionally secure computation with correlated randomness. Concretely, we obtain the following results.

Minimizing communication.

Any multiparty functionality can be realized, with perfect security against semi-honest parties or statistical security against malicious parties, by a protocol in which the number of bits communicated by each party is linear in its input length. Our protocol uses an exponential number of correlated random bits. We give evidence that super-polynomial randomness complexity may be inherent.

Perfect security against malicious parties.

Any finite “sender-receiver” functionality, which takes inputs from a sender and a receiver and delivers an output only to the receiver, can be

perfectly

realized given correlated randomness. In contrast, perfect security is generally impossible for functionalities which deliver outputs to both parties. We also show useful functionalities (such as string equality) for which there are

efficient

perfectly secure protocols in the correlated randomness model.

Perfect correctness in the plain model.

We present a general approach for transforming perfectly secure protocols for sender-receiver functionalities in the correlated randomness model into secure protocols in the plain model which offer

perfect correctness

against a malicious sender. This should be contrasted with the impossibility of perfectly sound zero-knowledge proofs.