Covert Multi-Party Computation

In STOC'05, Aim, Hopper and Longford introduced the notion of covert computation. A covert computation protocol is one in which parties am run a protocol without knowing if other parties ore also participating in the protocol or not. At the end of the protocol, if all parties participated in the protocol and if the function output is favorable to all parties, then the output is revealed. Ahn et al. constructed a protocol for covert two-partv computation in the random oracle model In this paper, we offer a construction for covert multiparty computation. Our construction is in the standard model and does not require random oracles. In order to achieve this goal, we introduce a number of new techniques. Central to our work is the development of "zero-knowledge proofs to garbled circuits, " which we believe could be of independent interest. Along the way, we also develop a definition of covert computation as per the Ideal/Real model simulation paradigm.

Authors

• Nishanth Chandran
• Vipul Goyal
• Rafail Ostrovsky
• Amit Sahai

Keywords

• Protocols
• Computer science
• Computational modeling
• Circuit simulation
• Technological innovation
• Multi-party Computation
• Output Function
• End Of Protocol
• Computational Protocol
• Random Oracle
• Random Oracle Model
• Zero-knowledge Proof
• Computational Model
• End Of Phase
• Input Vector
• Random Values
• Dishonest
• Part Of Protocol
• Types Of Messages
• Security Parameter
• Correct Output
• Turing Machine
• Broadcast Channel
• Protocol Execution
• Share Of Output
• Notions Of Fairness
• Hamiltonian Path
• Probabilistic Polynomial Time
• Steganography
• Protocol Participants