Ring of Gyges: Accountable Anonymous Broadcast via Secret-Shared Shuffle

Ring of Gyges: Accountable Anonymous Broadcast via Secret-Shared Shuffle

Speakers: Wentao Dong, City University of Hong Kong

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=Aa8v49nRFJw

Overview

In an increasingly interconnected world, the ability to broadcast messages anonymously has become a critical feature, empowering free expression, supporting whistleblowers, and enabling anti-censorship efforts. However, this very anonymity, while vital for privacy, can also be exploited for malicious purposes such as cyberbullying, terrorist propaganda, or the spread of fake news. The talk "Ring of Gyges: Accountable Anonymous Broadcast via Secret-Shared Shuffle" by Wentao Dong from City University of Hong Kong directly addresses this duality, presenting a novel cryptographic protocol that provides both strong anonymity guarantees and a mechanism for accountability when messages cross ethical or legal boundaries.

The core contribution of this work lies in its innovative use of Multi-Party Computation (MPC), specifically a technique dubbed "silent shuffle," to achieve highly efficient anonymous broadcast. Unlike traditional approaches that often suffer from significant communication overhead or computational intensity, Ring of Gyges focuses on optimizing the online phase of the shuffle operation to be non-interactive. This efficiency is coupled with a robust design that ensures message delivery even in the presence of malicious parties, alongside a unique accountability feature that allows for the tracing of problematic messages under predefined moderation policies, without compromising the anonymity of legitimate communications.

This research is particularly significant for its potential to reshape the landscape of secure and private communication platforms. By offering a practical and scalable solution that balances privacy with the societal need for accountability, Ring of Gyges pushes the boundaries of what's achievable in anonymous broadcast systems. It provides a blueprint for future applications that require both the freedom of expression afforded by anonymity and the safeguards against abuse that accountability provides, making it a compelling advancement in the field of privacy-enhancing technologies.

Background

▶ Watch: Introduction and motivation for anonymous broadcast (0:00)

The concept of broadcast, fundamentally a public bulletin board where messages are posted for wide consumption, underpins many modern communication platforms like Twitter (now X) and Facebook. While open sharing is a foundational principle, there are numerous scenarios where privacy is paramount, leading to a demand for anonymous broadcast services. Users may wish to disseminate information without revealing their identity, a common requirement in whistleblowing, anonymous social media, or reporting under oppressive regimes to circumvent censorship.

Historically, the pursuit of anonymous communication traces back to pioneering work by David Chaum, who proposed paradigms like DCNET and Mix Nets. These systems typically involve a series of sequential servers that perform verifiable shuffles, often relying on public-key cryptography to achieve anonymity. While effective, the cryptographic operations involved can be computationally intensive and heavyweight, leading to suboptimal performance, especially as the number of users or messages increases.

In recent years, researchers have increasingly turned to Multi-Party Computation (MPC) as a promising alternative for anonymous shuffle. MPC-based approaches often follow an offline/online paradigm. In the offline phase, data-independent correlated randomness, referred to as shuffle correlation, is pre-generated. In the online phase, users share their messages, and these shares are combined with the pre-generated shuffle correlation shares to perform a secret-shared shuffle. This approach can significantly improve computational efficiency compared to public-key-based mix nets. However, a persistent challenge in MPC, particularly for large-scale applications, remains the substantial communication burden between parties.

Previous works, such as MixBlender and RPM, leveraged the concept of a random permutation matrix as a form of shuffle correlation. In this paradigm, a secret-shared permutation matrix is used to shuffle secret-shared input messages through a matrix multiplication operation. Traditionally, performing multiplication of secret-shared values in MPC, especially over finite rings, requires interactive protocols or subsequent "resharing" (also known as "degree reduction" in polynomial-based sharing schemes like Shamir's) to maintain the desired sharing properties for subsequent computations. This interaction contributes significantly to the communication overhead, making truly efficient and scalable anonymous broadcast a complex problem.

The starting point for the Ring of Gyges project was to explore the optimal communication boundaries for an honest-majority, small-party MPC setup. The ambitious goal was to make the online phase of the shuffle entirely non-interactive, essentially performing the secret-shared multiplication in a "silent" manner. This necessitated a re-evaluation of the necessity of resharing in the specific context of anonymous broadcast, where the ultimate goal is merely the reconstruction of the shuffled output, rather than further computations on intermediate shared values. By addressing these fundamental challenges, Ring of Gyges aims to overcome the limitations of prior work and deliver a more practical and robust solution for anonymous and accountable broadcasting.

Key Findings

▶ Watch: Multi-Party Computation (MPC) approach for anonymous shuffle (2:30)

The Ring of Gyges protocol introduces several significant advancements that collectively enable efficient, robust, and accountable anonymous broadcast.

A primary contribution is the development of a silent shuffle paradigm. This innovation allows the online phase of the secret-shared shuffle to be entirely non-interactive. Traditionally, multiplication of secret shares requires an interactive step (e.g., using Beaver triples) or a subsequent resharing round to maintain the consistency of the sharing scheme. However, in the context of anonymous broadcast, the speaker observed that only the final reconstructed output matters, not the intermediate shared values or their properties for subsequent operations. By bypassing this resharing round, the protocol achieves local computation for the shuffle, drastically reducing communication overhead and making the online phase exceptionally fast.

To further optimize efficiency, the protocol incorporates sparsity-aware optimizations. Permutation matrices, which are central to the shuffle correlation, are inherently sparse, containing mostly zeros with only a single '1' in each row and column. Instead of sharing these matrices in a full arithmetic domain, Ring of Gyges shares them in a boolean way. This allows for significant compression of communication, as the boolean representation is much more compact. This sharing conversion from arithmetic data (messages) to one-hot vector data (permutation matrix columns) is efficiently handled using techniques like Distributed Point Functions (DPF), and messages themselves are processed in a bit-wise manner, leading to faster and lighter computations.

The work also addresses the critical aspect of scaling anonymous broadcast services. Recognizing that simply increasing the number of servers in a traditional MPC setup often increases total sharing size and thus the workload per server (due to collusion prevention mechanisms), Ring of Gyges proposes horizontal and vertical scaling notions. The non-interactive nature of the silent shuffle in the critical path makes the protocol highly amenable to parallelization, allowing for increased computation throughput without the typical communication bottlenecks.

Private robustness is another key finding. Beyond the standard MPC goal of guaranteed output delivery (GOD) for honest users against malicious servers, Ring of Gyges extends this to ensure that honest parties themselves do not learn who sent which message. This is crucial for anonymity services where even honest participants should not be able to link messages to senders. The protocol achieves this using replicated secret sharing (RSS) and by enforcing well-formedness of data from malicious users through a "weak verifiable signature" concept. Due to the non-interactive online phase, robust shuffling simplifies to a robust reconstruction problem, which can be managed with blame games and conflict reduction.

Finally, the protocol introduces a novel accountability mechanism. While anonymity is a core feature, the "Ring of Gyges" acknowledges that it can be abused. The system enables tracing of improper messages while preserving anonymity for legitimate ones. This is achieved by leveraging the same Boolean Permutation Correlation (BPC) matrix used for shuffling. While shuffling focuses on the columns of the BPC to map inputs to outputs, tracing focuses on the rows to map outputs back to inputs. This allows for lightweight and quick tracing without additional cryptographic overhead. To prevent abuse of accountability, a moderation policy is integrated, ensuring tracing is only triggered under predefined rules. Evaluation results highlight that offline communication is independent of message size due to the boolean representation, making it highly suitable for long messages, and that the silent shuffle achieves optimal communication for data.

Technical Deep Dive

▶ Watch: MPC's communication burden and interaction challenge (3:15)

The technical foundation of Ring of Gyges is built upon a clever re-engineering of secret-shared shuffle within an MPC framework, specifically targeting an honest-majority, small-party setup over finite rings. The central innovation is the silent shuffle paradigm, which bypasses the interactive rounds typically required for secure multiplication.

The shuffle operation is fundamentally a multiplication of a secret-shared permutation matrix [P] with secret-shared input messages [M], resulting in [P M]. In standard MPC protocols, computing [A] [B] where [A] and [B] are secret shares, often requires an interactive protocol like using Beaver triples or a subsequent resharing (or degree reduction) phase. This resharing is critical to ensure that the resulting shares [A * B] maintain the same properties (e.g., degree of the polynomial in Shamir's secret sharing) as the input shares, allowing them to be used in subsequent computations without revealing information.

The key insight in Ring of Gyges is that for anonymous broadcast, the shuffle operation is often the final computation before reconstruction. The system only cares about the reconstructed output, not about using the intermediate secret shares [P M] for further secret-shared computations. Therefore, the traditional resharing round, whose primary purpose is to maintain share semantics for subsequent operations, can be entirely omitted. By removing this interactive step, the online phase of [P M] becomes purely local computation. Each party performs its share of the multiplication locally, and then the resulting shares are directly used for reconstruction. This "silent" approach eliminates a significant communication bottleneck inherent in many MPC protocols.

Further enhancing efficiency, the protocol incorporates sparsity-aware optimizations for the permutation matrix P. A permutation matrix consists almost entirely of zeros, with exactly one '1' in each row and column. Instead of representing and sharing these matrices using full arithmetic shares (which would be inefficient for mostly zero values), Ring of Gyges uses a boolean representation. This significantly compresses the amount of data that needs to be shared and communicated. The conversion from arithmetic shares for messages to bit-wise shares for processing with the boolean permutation matrix is also optimized. To efficiently evaluate the sparse structure of the permutation matrix and generate its one-hot vector columns, Distributed Point Functions (DPF) are utilized. DPFs allow parties to jointly compute a function that evaluates to a specific value at a single "point" (the '1' in the one-hot vector) and zero elsewhere, without revealing the point itself. This specialized technique makes the handling of the sparse permutation matrix highly efficient in a secret-shared context.

For robustness against malicious parties, Ring of Gyges employs replicated secret sharing (RSS), a common choice for honest-majority MPC protocols. The protocol addresses two types of malicious behavior:

1. Malicious Users: If a user submits malformed secret shares (i.e., shares that do not correctly form an RSS share), the system needs to prevent this from disrupting the entire shuffle. Drawing inspiration from the concept of "weak verifiable signatures," the protocol grants honest servers the capability to "enforce" well-formedness. This means that if a user submits malformed data, the servers can deterministically convert it into well-formed (though potentially dummy) shares. This is deemed acceptable because the system does not need to guarantee the integrity of malicious inputs, only that they do not break the protocol.
2. Malicious Servers: Since the online shuffle phase is non-interactive, the problem of robust shuffling against malicious servers simplifies to a robust reconstruction problem. During the reconstruction phase, if servers submit inconsistent shares, mechanisms like blame games and conflict reduction can be employed. This allows the honest parties to identify and disregard the malicious contributions, ensuring that the honest users' messages are still correctly reconstructed and delivered. This approach provides private robustness, meaning not only is output delivery guaranteed for honest users, but their anonymity is also preserved from other honest parties, a critical feature for anonymity services.

The accountability mechanism is ingeniously integrated by leveraging the dual nature of the Boolean Permutation Correlation (BPC) matrix. For the anonymous shuffle, the parties are interested in the columns of the BPC, as these define how input messages are mapped to output positions. For accountability, however, the system needs to trace a specific output message back to its original sender. This requires examining the rows of the BPC, which effectively map output positions back to their original input sources. By having access to this BPC, the system can, when triggered, reveal the sender of a specific message. To prevent the abuse of this tracing capability, a strict moderation policy is enforced. Tracing is not an arbitrary function; it can only be activated under predefined rules and conditions, ensuring that anonymity for legitimate messages remains intact while providing a critical safeguard against malicious content.

Demo / Proof of Concept

▶ Watch: Sparsity-aware optimizations: boolean sharing and DPF (6:20)

While the talk did not feature a live, interactive demonstration of the Ring of Gyges system, the speaker presented comprehensive evaluation results to validate the protocol's performance and scalability. These results were crucial in demonstrating the practical applicability of their theoretical advancements.

The evaluation specifically focused on the system's ability to handle varying user populations, testing scenarios with anonymous sets ranging from 1,000 to 1 million users. The speaker noted that a million users is widely considered an acceptable anonymity set size in many research papers, indicating that their system scales effectively to real-world demands.

A key highlight from the evaluation was the impact of using a boolean representation for the shuffle correlation. This optimization led to the significant finding that the offline communication is independent of the message size. This is a particularly advantageous characteristic for services that handle long messages, such as streaming data or extensive reports, as the communication overhead for setting up the shuffle does not grow with the length of the content being anonymized. This makes Ring of Gyges highly efficient for a broad spectrum of anonymous broadcast applications.

The evaluation also implicitly showcased that the silent shuffle paradigm achieves optimal communication for the data-dependent online phase, as it requires only local computation and no interaction. This efficiency, combined with the robustness and accountability features, positions Ring of Gyges as a practical solution for building next-generation anonymous communication platforms. The system's ability to scale to large user bases while maintaining communication efficiency underscores its potential for real-world deployment, particularly in contexts like anonymous reporting platforms (e.g., an "EPA-like system with accountability" as mentioned in the Q&A) where both privacy and the ability to address harmful content are critical.

Defensive Implications

▶ Watch: Scaling throughput: challenges with increasing anonymity set (8:00)

The Ring of Gyges protocol offers several crucial defensive implications for organizations and platforms seeking to implement anonymous broadcast services. Its dual focus on privacy and accountability provides a robust framework for managing the complexities of free expression online.

1. Balanced Anonymous Communication: For platforms that aim to provide anonymous communication channels (e.g., whistleblowing systems, anonymous feedback mechanisms, anti-censorship tools), Ring of Gyges offers a way to do so responsibly. It allows these platforms to uphold strong privacy guarantees for legitimate users while simultaneously possessing the capability to address and mitigate abuse. This balance is critical for maintaining trust and preventing the degradation of anonymous services into havens for malicious activity.

1. Robustness Against Adversaries: The protocol's private robustness ensures that honest users' messages will be successfully broadcast even in the presence of malicious users or servers. This is a significant defensive posture, as it prevents selective failure attacks where adversaries might attempt to block specific messages or disrupt the service. Furthermore, the private nature of this robustness means that even honest parties cannot link messages to senders, reinforcing the anonymity guarantees. Defenders can deploy this system with confidence that the service will remain available and private for its intended users.

1. Efficient Resource Utilization: The silent shuffle and sparsity-aware optimizations translate into highly efficient resource utilization. The non-interactive online phase drastically reduces communication bandwidth and latency, which are often bottlenecks in MPC-based systems. For platforms operating at scale, this means they can support a larger user base and higher message throughput with fewer computational resources compared to traditional mix-net or interactive MPC solutions. This efficiency is a key defensive advantage against denial-of-service (DoS) attacks that often target resource-intensive cryptographic operations.

1. Controlled Accountability for Abuse: The built-in accountability mechanism is a powerful defensive tool against the misuse of anonymity. Platforms can define clear moderation policies and rules under which tracing can be triggered (e.g., in response to verifiable threats, illegal content, or severe violations of terms of service). This allows platforms to take action against malicious actors without resorting to blanket surveillance or undermining the privacy of all users. Implementing this mechanism requires careful legal and ethical consideration to establish transparent and fair policies for when and how tracing is activated, ensuring it aligns with user expectations and legal frameworks.

1. Scalability for Growth: The protocol's demonstrated ability to scale to 1 million users and its efficient handling of long messages (due to offline communication being independent of message size) means that platforms can grow their user base without facing prohibitive performance degradations. This scalability is a defensive asset, as it allows platforms to serve a wider community and remain resilient under increased demand, ensuring the continued availability of anonymous services.

In essence, Ring of Gyges provides a blueprint for building next-generation anonymous broadcast systems that are not only private and robust but also responsibly equipped to handle the challenges of online abuse. Defenders can leverage this technology to create more secure, ethical, and sustainable communication environments.

Key Takeaways

• Accountable Anonymous Broadcast: Ring of Gyges introduces a novel MPC-based protocol that provides strong anonymity for broadcast messages while simultaneously enabling a mechanism for accountability to trace improper content.
• Non-Interactive "Silent Shuffle": The core innovation is a silent shuffle paradigm that makes the online phase of the secret-shared shuffle entirely non-interactive, significantly reducing communication overhead by bypassing traditional resharing rounds.
• Optimized Efficiency: The protocol employs sparsity-aware optimizations, using boolean representation for permutation matrices and leveraging Distributed Point Functions (DPF) to compress communication and enhance computational speed.
• Private Robustness: It guarantees output delivery for honest users against malicious parties while also ensuring that honest parties cannot link messages to senders, extending traditional MPC robustness to preserve anonymity.
• Integrated Accountability: A built-in accountability mechanism uses the same Boolean Permutation Correlation (BPC) matrix for tracing improper messages (by examining rows) as for shuffling (by examining columns), governed by strict moderation policies to prevent abuse.
• Scalable Performance: Evaluation results demonstrate the system's scalability, supporting up to 1 million users, with offline communication costs independent of message size, making it suitable for high-throughput and long-message scenarios.

About the Speaker(s)

Wentao Dong is a researcher from City University of Hong Kong. He presented the work "Ring of Gyges: Accountable Anonymous Broadcast via Secret-Shared Shuffle" at the NDSS Symposium. The project represents a collaborative effort between City University of Hong Kong and EURISH, focusing on advancing privacy-enhancing technologies with practical applications in secure communication.