TL;DR
This paper tackles the fundamental problem of "broadcast" in secure multi-party computation (MPC), where one party sends a message to all others. They prove that achieving this in a single round is impossible under standard cryptographic assumptions. However, they demonstrate it is possible using stateful trusted hardware, and showcase an application in constructing a novel one-round multi-verifier zero-knowledge protocol.
What Problem Does This Paper Address?
In secure multi-party computation (MPC), parties want to compute a function on their private inputs without revealing those inputs. A crucial primitive for this is "broadcast," where one party (the sender) wants to reliably send a message to all other parties (the receivers). The challenge is to do this securely, even if some parties are malicious. A specific variant, "broadcast with selective abort," allows receivers to abort if they suspect something is wrong, but they must either receive the intended message or a special abort signal.
The authors focus on the round complexity of this broadcast primitive. Specifically, they investigate if it's possible to achieve broadcast in just one round of communication, meaning all messages are exchanged simultaneously without waiting for responses. This is highly desirable for efficiency. Previous work by Goldwasser and Lindell (2002, 2005) established a two-round protocol. The question this paper addresses is: can we do better and achieve one-round broadcast, and under what assumptions?
Methods
The paper's core contribution lies in its theoretical analysis of one-round broadcast. They employ the Universal Composition (UC) framework, a standard and powerful tool for proving security in cryptographic protocols.
- Impossibility Proof: The authors introduce a new concept called a "consistent oracle." This oracle models a wide range of common cryptographic "global setup" assumptions, such as the Random Oracle Model (ROM), Common Reference String (CRS) model, and even stateless trusted hardware. They then prove that no one-round broadcast protocol can UC-realize the broadcast functionality if it relies only on such consistent oracles and secure point-to-point channels. The proof uses a proof-by-contradiction strategy, showing that if such a protocol existed, a malicious adversary could exploit it to cause inconsistent behavior among honest receivers, violating the broadcast guarantee.
- Feasibility Proof: To bypass their own impossibility result, they consider a different, stronger assumption: stateful trusted hardware. They define a new functionality called "Onw" (which seems to be a typo for "OHW" or similar, representing a trusted hardware device) that can maintain state and provide signatures. They then construct a one-round broadcast protocol, denoted $\Pi_{BC-HW}$, that UC-realizes the broadcast functionality in the "Onw-hybrid world" (meaning the protocol can interact with this trusted hardware functionality). This protocol is proven secure against adaptive and malicious adversaries who can corrupt up to $t < n$ parties. Crucially, this stateful trusted hardware does not satisfy the definition of a consistent oracle, which is why their impossibility result doesn't apply here.
- Application: As a practical demonstration of their one-round broadcast protocol, they construct the first one-round Multiple-Verifier Zero-Knowledge (MVZK) protocol that works against a dishonest majority, using only secure point-to-point channels and the stateful trusted hardware assumption. This is significant because previous one-round MVZK protocols required the broadcast hybrid world.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The fundamental barrier: The paper provides a formal proof that one-round broadcast is impossible under a broad class of widely-used cryptographic setups. This is a significant theoretical result, establishing a hard limit on efficiency for this primitive.
- The power of state: The impossibility arises from the "stateless" nature of consistent oracles. By introducing stateful trusted hardware, which can remember past interactions (like a counter for signatures), this barrier can be overcome. This highlights the importance of state in cryptographic primitives.
- Bridging the gap: The paper elegantly connects the impossibility result with a feasibility result, showing that while one-round broadcast is impossible in the "plain" world (with standard setups), it becomes achievable with a more powerful, albeit less common, assumption.
- New building block: The one-round broadcast protocol constructed using stateful trusted hardware serves as a new, efficient building block for other cryptographic tasks, as demonstrated by its application to MVZK.
Key Results
- Impossibility: A formal proof that one-round broadcast is impossible in the UC framework using only "consistent oracles" (modeling ROM, CRS, etc.) against static, malicious, and rushing adversaries corrupting the sender.
- Feasibility: A construction of a one-round broadcast protocol that is UC-secure in the "Onw-hybrid world" (stateful trusted hardware), secure against adaptive and malicious adversaries corrupting up to $t < n$ parties. This protocol is non-interactive in terms of communication between parties after the initial broadcast.
- Application: The first one-round MVZK protocol against a dishonest majority, using only secure P2P channels and stateful trusted hardware.
Limitations and Future Work
- Trusted Hardware Assumption: The feasibility result relies on stateful trusted hardware, which is a strong assumption and not always practical or desirable. Future work could explore achieving one-round broadcast under weaker assumptions, perhaps by combining multiple weaker primitives.
- Application Details: The paper mentions the construction of a one-round MVZK protocol but defers the full details to a longer version due to space constraints. A complete exposition of this application would be valuable.
- Generalization of Impossibility: While the impossibility proof covers a broad class of "consistent oracles," exploring its boundaries and potential extensions to other models could be interesting.
- Efficiency of Feasible Protocol: While the feasible protocol is one-round, its practical efficiency (e.g., communication size, computational overhead) would be a key area for future investigation.
Summary updated