A Universal Problem in Secure and Verifiable Distributed Computation

A notion of reduction among multi-party distributed computing problems is introduced and formally defined. Here the reduction from one multi-party distributed computing problem to another means, roughly speaking, a secure and verifiable protocol for the first problem can be constructed solely from a secure and verifiable protocol of the second. A universal or complete multi-party distributed computing problem is defined to be one to which the whole class of multiparty problems is reducible. One is interested in finding a simple and natural multi-party problem which is universal. The distributed sum problcm, of summing secret inputs from N parties, is shown to be such a universal problem. The reduction yields an efficient systematic method for the automatic generation of secure and verifiable protocols for all multi-party distributed computing problems. Incorporating the result from [l4], it also yields an alternative proof to the completeness theorem of [9] that assuming honest majority and the existence of a trap-door function, for all multi-party problems, there is a secure and verifiable protocol.