JOINT ENCRYPTION AND MESSAGE-EFFICIENT SECURE COMPUTATION

This paper addresses the message complexity of secure computation in t he (passive adversary) privacy setting. We show that O(nC) encrypted b its of communication suffice for n parties to evaluate any boolean cir cuit of size C privately, under a specific cryptographic assumption. T his work establishes a connection between secure distributed computati on and group-oriented cryptography, i.e., cryptographic methods in whi ch subsets of individuals can act jointly as single agents. Our secure computation protocol relies on a new group-oriented probablistic publ ic-key encryption scheme with useful algebraic properties.