TL;DR
This paper introduces "Cross&Clean," a novel protocol for secure two-party computation that achieves active security with only a constant overhead, even when evaluating the same circuit multiple times. This is a significant improvement over previous methods that required overhead that grew with the security parameter.
What Problem Does This Paper Address?
Secure two-party computation (2PC) allows two parties to jointly compute a function on their private inputs without revealing those inputs to each other. Garbled circuits (GCs) are a cornerstone of 2PC, but the basic version only offers security against passive adversaries (who follow the protocol but try to glean information). Malicious adversaries, however, can tamper with the garbled circuit itself, leading to incorrect computations and broken security.
Achieving active security (protection against malicious adversaries) in GCs typically relies on the "cut-and-choose" approach. This involves creating multiple copies of the garbled circuit, checking a subset for correctness, and then evaluating the rest. While effective, existing cut-and-choose protocols often require a number of garbled circuits that scales with the security parameter (e.g., linearly with k for k-bit security). This can be computationally expensive, especially in the amortized setting, where the same circuit is evaluated many times on different inputs. The core question this paper addresses is: can we achieve active security in the amortized setting with only a constant overhead over the passive GC protocol?
Methods
The authors propose a new protocol called "Cross&Clean" that achieves active security with constant overhead in the amortized setting. The protocol is broken down into five stages:
- Providing Inputs: Parties commit to their inputs using a secure protocol, ensuring they are well-defined from the start.
- Cut-and-Choose: Parties garble multiple copies of the circuit and use a cut-and-choose mechanism to verify a subset. This stage is enhanced with "token generation" for input verification, ensuring that if an input passes verification, the resulting output will be correct.
- Run Computation: The remaining circuits are evaluated. This stage uses a dual-execution approach and is designed to handle potential incorrect outputs from the cut-and-choose phase.
- Actively Secure Filling-in: This stage addresses the possibility that some outputs might still be incorrect. Parties can request re-computations for a limited number of positions using an actively secure protocol, with commitments and MACs to ensure integrity.
- Forge-and-Lose: The final stage identifies the first differing output between parties. If a discrepancy is found, the protocol determines who cheated and, if one party is malicious, reveals their secret key, allowing the honest party to recompute everything in the clear.
The protocol leverages several cryptographic primitives, including commitments, symmetric encryption, MACs, oblivious transfer (OT), and a generalized garbled circuit scheme with input verifiability. The key innovation lies in how these primitives are combined to bound the overhead to a constant, particularly in the amortized setting.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Constant Overhead is Achievable: The most significant insight is that active security in the amortized setting for GCs doesn't inherently require overhead that grows with the security parameter. This challenges previous assumptions and opens the door for more efficient secure computation.
- Input Verifiability is Crucial: The introduction of "tokens" for input verification in the cut-and-choose stage is a key enabler. It ensures that if an input passes verification, the subsequent computation will be correct, simplifying later stages.
- Synergy of Primitives: The protocol cleverly combines multiple cryptographic tools (commitments, MACs, OT, GCs) in a way that their individual overheads don't compound linearly with the security parameter in the amortized setting.
- Amortization is Key: The constant overhead is achieved specifically in the amortized setting, meaning it applies when the same circuit is evaluated many times. The per-evaluation cost is constant, but the total cost for l evaluations is still proportional to l.
Key Results
The paper presents a protocol that achieves active security for two-party computation with an amortized complexity bounded by $O(1) \cdot |f| \cdot p(\kappa) + A(\kappa)$, where $|f|$ is the circuit size, $p(\kappa)$ is the cost per gate in the passive protocol, and $A(\kappa)$ is an additive factor independent of $|f|$. This means the overhead over Yao's passive protocol is constant in the amortized setting. The authors provide a concrete analysis showing that the concrete overhead over Yao's passive protocol is between 2.5 and 2.8 for common garbling schemes when using a specific parameter choice.
Limitations and Future Work
- Theoretical Nature: The authors explicitly state that the work is theoretical, and they have not focused on optimizing the concrete efficiency of the protocol's stages. They suggest that investigating practical efficiency is an interesting direction for future work.
- Complexity of Implementation: The protocol is described as "quite complex" due to its multiple stages and reliance on various cryptographic primitives. This complexity might pose challenges for practical implementation.
- Long Inputs/Outputs: The paper discusses how to handle long inputs and outputs, but the proposed solutions (e.g., using a naive PIR for long inputs) are noted as potentially improvable. The authors suggest more clever PIR schemes could be used.
- Open Questions: The paper leaves open the question of whether the proposed approach can lead to practically efficient solutions.
Summary updated