PaperlayerView exact revision on arXiv

Source-linked AI summary

Riposte: An Anonymous Messaging System Handling Millions of Users

Henry Corrigan-Gibbs, Dan Boneh, David Mazières

arXiv:1503.06115v7cs.CR

TL;DR

Anonymous broadcast messaging must resist traffic analysis and malicious-client disruption while scaling to large anonymity sets. Riposte uses private information retrieval and secure multiparty computation techniques in a write-private database scheme, and a three-server cluster constructed an anonymity set of 2,895,216 clients in 32 hours.

  • Problem

    Anonymous messaging systems must protect whistleblowers from traffic-analysis attacks while preventing malicious clients from anonymously disrupting the system.

  • Method

    Riposte implements an anonymous bulletin board using a write-private database scheme maintained by a small set of servers, drawing on private information retrieval and secure multiparty computation.

  • Results

    2,895,216 clients: Riposte constructed this anonymity set in 32 hours using a three-server cluster for a read-heavy, latency-tolerant microblogging workload.

  • Takeaways & Limitations

    Riposte simultaneously thwarts traffic-analysis attacks, prevents malicious-client disruption, and enables million-client anonymity set sizes.

  • Takeaways & Limitations

    Intersection attacks remain an orthogonal problem, although larger anonymity sets typically make them more difficult to mount.

Abstract

from arXiv · show

This paper presents Riposte, a new system for anonymous broadcast messaging. Riposte is the first such system, to our knowledge, that simultaneously protects against traffic-analysis attacks, prevents anonymous denial-of-service by malicious clients, and scales to million-user anonymity sets. To achieve these properties, Riposte makes novel use of techniques used in systems for private information retrieval and secure multi-party computation. For latency-tolerant workloads with many more readers than writers (e.g. Twitter, Wikileaks), we demonstrate that a three-server Riposte cluster can build an anonymity set of 2,895,216 users in 32 hours.

1 Introduction

Riposte is an anonymous broadcast-messaging system designed to resist traffic analysis and malicious-client disruption while scaling to millions of users for latency-tolerant workloads. It combines secret sharing, secure multi-party computation, and reverse private information retrieval to provide these properties with practical bandwidth and computation.

  • Motivation: Riposte targets anonymous messaging that protects against traffic analysis while supporting anonymity sets far larger than prior systems’ tens of thousands of users.The system is motivated by applications such as anonymous whistleblowing and microblogging.
  • Security and scalability: Riposte simultaneously protects against traffic analysis, prevents anonymous denial-of-service by malicious clients, and scales to millions of users for certain latency-tolerant applications.These properties are achieved through fixed-length secret-shared writes, malformed-request detection, and distributed point functions.
  • Bandwidth efficiency: Riposte runs private information retrieval in reverse, enabling clients to write privately into a server-maintained database while reducing upload costs to O(L) bytes for a table of size L.Writing into a 377 MB table requires less than 1 MB of client upload, versus more than 750 MB for a two-server DC-net system.
  • System architecture: Clients cryptographically split each write into shares sent to multiple servers, which aggregate requests per epoch so posts are recoverable without linking messages to clients.A coalition below the security threshold learns neither the message nor its write location, while epoch duration must permit many honest clients to participate.
  • Protocol variants: The three-server variant uses inexpensive multi-party checking for malformed requests, while the s-server variant uses client-produced zero-knowledge proofs and tolerates all but one malicious server.Both variants retain security against actively adversarial links and clients, subject to the stated server non-collusion requirements.

2 Goals and Problem Statement

Riposte defines an anonymous bulletin-board system in which clients write privately to a shared database while resisting malicious-client disruption. Its security depends on epoch participation, server thresholds, and formally defined write-privacy and disruption-resistance properties.

  • System Goals: Riposte lets clients write messages and row locations into a shared server-maintained database without revealing either to sufficiently small server coalitions.Clients secret-share write requests among servers; the threshold t determines how many malicious servers the scheme tolerates.
  • System Goals: An epoch’s honest writers form the anonymity set, so epoch length or termination conditions directly constrain anonymity.Epochs may be time-, request-, or condition-based, and security depends on enough honest clients participating together.
  • Security Goals: Riposte requires write privacy and disruption resistance for anonymous bulletin-board use.Write privacy protects client-message linkage, while disruption resistance limits an adversary controlling n clients to at most n written rows per epoch.
  • Security Goals: The system’s privacy remains robust when adversaries choose honest clients’ messages and submit malicious messages dependent on them.The adversary still cannot successfully identify which client uploaded which message.
  • Security Definitions: Disruption resistance is formalized by requiring that an adversary’s probability of producing more than n non-zero rows from n requests is negligible.Correctness separately requires faithful servers to reveal the database state obtained by applying valid writes to an empty database.
  • Security Goals: Riposte hides client-message linkage within an epoch but does not itself prevent intersection attacks across epochs.Changing online-client sets can enable statistical inference, although larger anonymity sets generally make such attacks more difficult.

3 System Architecture

Riposte combines secret-shared database updates with collision handling and bandwidth improvements to build an anonymous messaging database. The construction supports forward security, while its practical limits include bandwidth, malicious disruption in the straw-man protocol, and server computation.

  • 3.1 A First-Attempt Construction: Toy Protocol: Clients secret-share write requests to multiple servers, which independently update database shares and later combine them to reveal plaintext messages.The basic construction uses XOR-shared vectors, authenticated encrypted channels, and epoch-bound nonces.
  • 3.1 A First-Attempt Construction: Toy Protocol: The two-server toy protocol provides write privacy when the servers do not collude.Each server can simulate its view from aggregate write information without learning individual write locations.
  • 3.1 A First-Attempt Construction: Toy Protocol: The toy protocol is not bandwidth-efficient: a client must send a full database-length request, which can require millions of bits.This limitation arises when the database must contain millions of bits to support millions of clients per epoch.
  • 3.1 A First-Attempt Construction: Toy Protocol: A malformed request can corrupt the entire toy-protocol database, allowing one malicious client to deny service anonymously.Bandwidth efficiency and disruption resistance are identified as the work’s two core contributions.
  • 3.2 Collisions: Collision sizing models write requests as balls thrown uniformly into database rows and estimates the number of singleton rows.The expected success rate is obtained by dividing the expected singleton count by the number of writes.
  • 3.2 Collisions: 95% expected success requires n ≈19.5m cells without collision recovery, versus n ≈2.7m cells with two-way collision coding.Collision coding doubles cell size but shrinks the overall cell count by more than half, reducing server storage and computation.
  • 3.3 Forward Security: Forward security prevents later compromise of all server state and keys from linking n honest clients to their n messages within an unfinished epoch.This assumes client-server channels provide forward secrecy; the full Riposte protocol maintains the property.

4 Improving Bandwidth Efficiency with Distributed Point Functions

Riposte applies distributed point functions, adapted from private information retrieval, to make anonymous database writes bandwidth-efficient while supporting different server-collusion thresholds. The constructions preserve write privacy and correctness, but stronger malicious-server protection requires more expensive computation.

  • Bandwidth efficiency: PIR-inspired reverse writing lets clients efficiently write into a replicated database without revealing the row they modify.The approach reduces the O(L)-bit vector overhead of directly flipping one database bit.
  • Distributed point functions: Distributed point functions split a point function across server keys so up to t colluding servers learn nothing about the written index or value.Correctness requires the summed evaluations to equal the original point function.
  • Write-private database: DPF keys of length |k| yield an s-server write-private database scheme with request length s|k|, while preserving anonymity against t malicious servers.The final database contains the sum of the point functions represented by all write requests.
  • Security variants: The two-server construction tolerates one malicious server using symmetric-key primitives, whereas the s-server construction tolerates s−1 malicious servers with more expensive public-key operations.The stronger construction is novel as far as the authors know, while a symmetric-key alternative has key size exponential in the number of servers.
  • Efficiency trade-offs: The stronger DPF construction trades computational efficiency for security: elliptic-curve scalar multiplications make evaluation orders of magnitude slower than the two-server construction.At large table sizes, AES-NI throughput limits processing rate, so capacity scales with available CPU cores.

5 Preventing Disruptors

Riposte prevents malicious clients from disrupting the database by validating that submitted DPF keys are well formed without exposing their private contents. It offers an inexpensive three-server check or a more costly zero-knowledge approach for stronger server-adversary settings.

  • Motivation: The first-attempt scheme allowed malicious clients to corrupt database state with malformed write requests, motivating distributed validation of DPF keys.The servers jointly decide whether each collection of keys is a valid DPF output without revealing the keys themselves.
  • Validation protocols: Riposte constructs two validity-checking protocols: one computationally inexpensive protocol requiring a third non-colluding server, and one using costly zero-knowledge proofs.Both protocols target soundness, completeness, and zero-knowledge.
  • Three-server protocol: AlmostEqual enables three servers to confirm that two vectors differ at exactly one index while hiding that index from any single malicious server.The protocol uses hashing, pseudorandom values, client-provided digests, and an audit-server decision.
  • DPF-key validation: The two-server DPF checker tests both the b,s vectors and the v vector through AlmostEqual before accepting a write request.Correct key pairs differ at one index in b and s, and v combines the message point with pseudorandom terms.
  • Implementation boundary: The three-server checker leaks whether the message is zero, so clients must encode zero specially or pad requests to ensure m≠0.Security holds only when the checked vectors differ at exactly one index.
  • Zero-knowledge techniques: The zero-knowledge construction maintains write privacy when all but one of s servers are dishonest and is proven sound, complete, and zero-knowledge.It uses collections of Pedersen commitments for the client’s proofs.

6 Experimental Evaluation

Riposte’s experiments evaluate two protocol variants, showing practical throughput, bandwidth savings, scalability across table sizes and servers, and million-user anonymity sets. The evaluation also identifies computational limits and an implementation caveat for the stronger s-server variant.

  • Corrected implementation: The corrected AlmostEqual protocol fixes an active attack that could let a malicious database server de-anonymize a client.The evaluation reflects the original DPF-checking protocol because the updated protocol has almost identical complexity.
  • Protocol variants: The three-server variant uses symmetric-key primitives and includes the cost of identifying and excluding malicious clients.It requires that no two of the three servers collude.
  • Three-server performance: 32.8 requests per second are processed with 65,536 rows, while throughput falls to 2.86 requests per second at 1,048,576 rows.With 64 rows, throughput is 751.5 write requests per second.
  • Bandwidth efficiency: 768× speed-up comes from bandwidth-efficient DPFs over the naïve construction at fixed 10 MB table size.The optimal table size achieves 38.4 requests per second, versus 0.05 requests per second for the naïve construction.
  • Bandwidth efficiency: 1.23 MB of server transfer is required for a write request with a 2.5 GB database table, demonstrating sub-linear data transfer.The comparison baseline is the database-table-sized transfer required without bandwidth-efficient DPFs.
  • Protocol variants: The s-server variant’s performance figures are upper bounds because the required zero-knowledge proofs for preventing database corruption were not implemented.Its DDH-based PRG is costly: one million rows would take nearly one hour, compared with 0.3 seconds for the AES-based three-server protocol.
  • Large anonymity sets: 2,895,216 write requests formed an anonymity set in 32 hours at an average rate of 25.19 requests per second.A 65,536-row table could support roughly 1,000,000 users with epochs of at least 11 hours under the stated collision assumptions.
  • Deployment limits: The AES-based system is CPU-bound at large table sizes, while the reported Twitter-scale comparison would require roughly 5,250 servers.The estimate assumes throughput scales linearly with the number of machines.

7 Related Work

Related systems either provide low-latency anonymity or stronger traffic-analysis resistance, but often face scalability, trust, bandwidth, or performance trade-offs. Riposte combines a single large anonymity set with reverse PIR and bandwidth-efficient DPFs, while remaining preferable only in particular workload regimes.

  • Anonymity-system categories: Anonymity systems generally prioritize either low-latency communication or protection against traffic analysis by a global adversary.Low-latency proxies do not provide the same protection against powerful network adversaries.
  • Composed systems: Tor and Riposte can be combined so that even colluding Riposte servers would also need to break Tor to link a user to a message.The combined design aims to provide low-latency access alongside Riposte’s messaging protections.
  • Verifiable shuffles: Compared with verifiable shuffles, Riposte uses O(L) AES operations and O(L) data transfer, while Bayer–Groth requires 16N group exponentiations per server and O(N) transfer.Messages in the Bayer–Groth comparison must fit within a few hundred bytes.
  • Workload trade-offs: Bayer–Groth may be faster for short messages and high writer-to-reader ratios, whereas Riposte is faster for long messages when L ≪ O(N).The comparison depends on message length and the writer/reader ratio.
  • DC-net systems: DC-nets provide strong anonymity but require every user to participate in every protocol run, becoming impractical as the user population grows.Dissent makes DC-nets more practical with partially trusted servers but requires O(L) client communication per epoch.
  • Anonymity-set structure: Riposte creates one large anonymity set, unlike Herbivore’s many small sets, allowing clients to be anonymous among all honest clients.This distinction is presented as a scalability and anonymity-set property.
  • PIR-based designs: Riposte adapts private information retrieval by running it in reverse, enabling clients to write without revealing the destination row.Distributed point functions reduce the client bandwidth needed for these writes.
  • Composed systems: Riposte can replace mix-nets in a private messaging design, with Riposte handling anonymous writes and PIR handling private reads.This combination is described for point-to-point messaging rather than only broadcast messaging.

8 Conclusion and Open Questions

Riposte demonstrates that cryptographic techniques can support traffic-analysis-resistant anonymous messaging at Internet scale while resisting malicious-client disruption. The conclusion identifies several open questions about more efficient DPFs and disruption resistance.

  • Riposte simultaneously thwarts traffic-analysis attacks, prevents malicious clients from anonymously disrupting the system, and enables anonymity sets of millions of clients.
  • The system applies private information retrieval and secure multiparty computation techniques to anonymous messaging.
  • An implementation evaluated Riposte with anonymity sets exceeding two million nodes.
  • Open Questions: Open questions concern symmetric-key (s,s−1)-DPFs, disruption resistance without a non-colluding audit server, and DPF write processing below amortized o(L) time.
  • The design and implementation make traffic-analysis-resistant anonymous microblogging and whistleblowing more practical at Internet scale.

A Definition of Write Privacy

Write privacy is defined through a security game in which an adversary controls limited servers and potentially malicious clients, while the challenger processes and reveals the database. Privacy requires that the adversary cannot identify which honest client produced which write.

  • An (s,t)-write-private database scheme uses Write, Update, and Reveal algorithms to generate requests, update server states, and recover the plaintext database.
  • Security Game: The adversary may corrupt at most t servers and selects a set of at least two honest clients with message-location pairs.
  • Security Game: The challenger generates honest-client write requests, randomly permutes them, and processes all client requests through the honest servers’ Update functionality.
  • Security Game: The challenger gives the adversary either the actual honest-client permutation or a fresh random permutation together with honest-server states.
  • Security Definition: Write privacy holds when no efficient adversary can distinguish the two permutation cases with non-negligible advantage.

B Correctness Proof for (2,1)-DPF

The correctness proof analyzes cases for the distributed point function and shows that the reconstructed value equals the intended message at the target location while canceling elsewhere.

  • The proof establishes correctness for keys generated by Gen(ℓ,m) at every database location ℓ′ in Z_L.
  • A case analysis compares the represented locations ℓ and ℓ′ to evaluate the construction’s left-hand side.
  • When the relevant terms coincide, the reconstructed value B is identical to the intermediate message m′.
  • Over a binary field, adding a value to itself yields zero, causing the reconstructed value B to be zero in the non-target case.

C Proof Sketches for the AlmostEqual Protocol

The AlmostEqual proof sketches establish completeness, soundness, and zero knowledge for checking whether two vectors differ at exactly one position. The protocol relies on hash consistency and shared check values, with hash collisions creating only negligible error.

  • Completeness: Completeness requires the audit server to output “1” with overwhelming probability when vectors differ at exactly one position.
  • Completeness: The audit server checks single-position difference, equality of check values, and consistency between submitted vectors and their hash digests.
  • Completeness: Hash collisions can make the first test fail, but the probability of this incorrect result is negligible in the security parameter λ.
  • Soundness: Soundness requires that a cheating client cannot make honest servers accept vectors that differ at more than one position.
  • Soundness: A successful soundness violation would yield a collision in H, which is infeasible with non-negligible probability.
  • Zero Knowledge: The zero-knowledge proof requires simulators to reproduce each database server’s and the audit server’s view using public parameters and private inputs.
  • Zero Knowledge: For server A, the simulator samples a random PRG seed, derives the vector and digest, and reproduces the audit response from stored state.
  • Zero Knowledge: The simulation is statistically close to a real execution because discrepancies require a hash-consistent but different vector.

D Security Proof Sketches for the Three-Server Protocol

The three-server protocol uses AlmostEqual checks to verify well-formed client keys and reject malformed requests. Completeness follows from the prescribed vector structure, while soundness relies on the checks detecting deviations except with negligible probability.

  • The protocol’s first AlmostEqual check verifies that the b and s vectors differ at exactly one index for well-formed keys.At the differing index, bA and bB differ, so the test vectors remain distinct even if the random seeds coincide.
  • If v is well formed, the second check produces test vectors uA and uB that differ only at index ℓy.
  • Malformed b and s vectors cause the first AlmostEqual check to return 0 with overwhelming probability.This follows from the soundness of the underlying AlmostEqual protocol.
  • Conditioned on the s vectors differing at one index, passing the second check implies that v is well formed.The soundness argument reduces any successful malformed construction to a constrained tuple whose relevant coordinates differ at exactly one index.
  • The audit server can simulate a successful protocol execution by invoking the AlmostEqual simulator twice.

E Security Proof Sketches for the Zero-Knowledge Protocol

The zero-knowledge protocol proves that accepted write requests have the required vector structure while revealing no underlying values. Completeness follows from the constructed vectors, and soundness makes accepting invalid requests negligible.

  • The first protocol half is complete because the B and S vectors are constructed in the required form.
  • Completeness of the second half requires Gsum to be zero at every index except one.
  • The first-half proof guarantees that the B vectors sum to eℓx and the s vectors sum to s∗·eℓx.
  • 20The soundness proof makes accepting an invalid write request negligible by forcing Gsum to contain commitments to zero at all but one index.Any violating client would require v = m·eℓy −G(s∗), which contradicts the first-half relation.
  • The servers can simulate every received message because they see statistically hiding Pedersen commitments and simulatable non-interactive zero-knowledge proofs.
Loading 1503.06115v7…