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