Adaptively Secure Multi-party Computation


Non-Commiting Encryption

Ran Canetti      Uri Feige      Oded Goldreich       Moni Naor


A fundamental problem in the area of secure multi-party computation is how to deal with  adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the computation), in a setting where the channels themselves are not secure and secure communication is achieved by cryptographic primitives, i.e. based on the computational limitations of the adversary.

It turns out that the power of an adaptive adversary is greatly affected by the amount of information gathered upon the corruption of a party. This amount of information is, in turn, intimately related to the extent to which uncorrupted parties carry out instructions that cannot be externally verified, such as erasing records of past configurations. It has been shown that if the parties are trusted to erase such records, then adaptively secure computation can be carried out using known primitives. However, this total trust in parties may be unrealistic in many scenarios.

The main result of the paper is an affirmative resolution of this question, for the case where uncorrupted parties follow their protocols with the exception that all records of past configurations are kept. We first propose a novel property of encryption protocols, called non-committing encryption, and show that if an encryption protocol enjoying this property is used, instead of a standard encryption scheme, then known constructions become adaptively secure. Next we construct, based on the standard RSA assumption, an encryption protocol that enjoys this property.

 Postscript, gzipped Postscript. PDF.

Related On-Line Papers:

Back to: All On-Line Publications , By Topic , Recent

Back Home