Publicly Auditable Secure Multi-Party Computation

Carsten Baum, Ivan Damgård, Claudio Orlandi

TL;DR

This paper introduces a novel approach to enhance secure multi-party computation (MPC) by enabling public auditability. They achieve this by extending the efficient SPDZ protocol, allowing anyone to verify the correctness of a computation even if all participating parties are corrupted, with only a modest performance overhead.

What Problem Does This Paper Address?

Secure Multi-Party Computation (MPC) allows multiple parties to jointly compute a function on their private inputs without revealing those inputs. While recent advancements have made MPC highly efficient, a critical challenge remains: ensuring the correctness of the computation's output, especially in scenarios where all parties might be malicious or collude. This is particularly important for applications like electronic voting or auctions, where the integrity of the result is paramount. Traditional methods for achieving this, like using non-interactive zero-knowledge proofs, often introduce significant computational overhead, negating the efficiency gains of modern MPC protocols. The paper addresses this gap by proposing a way to make highly efficient MPC protocols, like SPDZ, publicly auditable without sacrificing their speed.

Methods

The core contribution is an enhanced version of the SPDZ protocol that incorporates public auditability. The key idea is to augment the standard SPDZ protocol with a Pedersen commitment scheme applied to shared values. This means that not only are the values shared among parties, but they are also committed to.

Here's a breakdown of the approach:

  • Augmented Representation: Shared values are represented not just by their shares but also by their Pedersen commitments. This representation is designed to be linear, allowing it to be compatible with SPDZ's existing operations.
  • Preprocessing Phase: The offline (preprocessing) phase of SPDZ is modified to generate these augmented representations, including commitments to random values and multiplication triples.
  • Online Phase: During the online computation, parties perform operations on the augmented representations. Crucially, they ignore the commitments during this phase, relying on the linearity of the representation. The actual verification of commitments happens later.
  • Audit Phase: A designated auditor (or anyone with access to the protocol transcript) can then use the commitments and the circuit description to verify the correctness of each step of the computation. This is done by following the computation's logic and checking if the opened values match the commitments.
  • Formal Definition: The paper formalizes the concept of "publicly auditable MPC," requiring correctness and privacy when at least one party is honest, and additionally ensuring that an auditor can verify the output's correctness from the transcript, even if all computing parties are corrupted.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Efficiency and Verifiability: The paper successfully demonstrates that it's possible to achieve both high efficiency (comparable to SPDZ) and robust public auditability, a combination previously difficult to attain.
  • Commitments as Audit Trails: Using Pedersen commitments as an integral part of the MPC protocol transforms the computation into a verifiable process. The commitments act as an immutable audit trail that can be checked post-computation.
  • Decoupling Computation and Audit: The design cleverly separates the computation phase from the audit phase. Parties perform computations efficiently without constant commitment checks, deferring the verification to an auditor who has access to the complete transcript.
  • Extending SPDZ's Power: By building upon the SPDZ protocol, the work leverages its existing efficiency for arithmetic circuits and extends its applicability to scenarios requiring strong accountability.

Key Results

  • Auditable SPDZ Protocol: The paper presents a concrete protocol that enhances SPDZ for public auditability.
  • Performance Overhead: The proposed protocol incurs an online phase complexity that is approximately twice that of the original SPDZ protocol. This is considered a significant achievement given the added auditability feature.
  • Formal Security Guarantees: The paper provides a formal definition of publicly auditable MPC and proves the security of their construction in the UC framework, implying auditable correctness even in the presence of fully malicious adversaries.

Limitations and Future Work

  • Performance for Boolean Circuits: The authors note that their approach would be significantly slower for Boolean circuits due to the need for MACs over extension fields. They suggest designing efficient auditable protocols specifically for Boolean circuits as a future direction.
  • Stronger Notions of Auditability: The paper acknowledges that stronger notions of auditability, such as universal verifiability (where the auditor doesn't need to know the output) and accountability, are not provided. These are identified as open research questions.
  • Implementation: The authors suggest that a working implementation of their scheme would be a valuable future work, building upon the existing SPDZ codebase.

Summary updated

Abstract

In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice. A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly – even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not participating. This is especially relevant in the clients-servers setting, where many clients provide input to a secure computation performed by a few servers. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs during the computation. A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgård et al. Applications such as voting and some auctions are perfect use-case for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information-theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase. In this paper, we show how to achieve efficient MPC with a public audit. We formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without significantly compromising the performance of SPDZ i.e. our online phase has complexity approximately twice that of SPDZ.
BibTeX
@article{baum2014publicly,
  author = {Carsten Baum and Ivan Damgård and Claudio Orlandi},
  title = {{Publicly Auditable Secure Multi-Party Computation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
  doi = {10.1007/978-3-319-10879-7\_11},
}
Figure