Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs

Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs

Speakers: Mayank Rathee; Yuwen Zhang; Henry Corrigan-Gibbs; Raluca Ada Popa

Conference: IEEE S&P

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

Overview

This talk introduces Whisper, a novel system designed to significantly enhance the efficiency of private analytics, particularly for scenarios involving a large number of users and sensitive data. The core problem Whisper addresses is how to compute aggregate statistics (like histograms or heavy hitters) over user data without compromising individual user privacy, even if some servers are compromised by an adversary. While existing solutions leverage secret sharing and zero-knowledge proofs (ZKPs) to achieve privacy and correctness, they suffer from substantial communication and storage overheads that scale linearly with the number of clients, making them impractical for large-scale deployments.

Whisper tackles these fundamental limitations by introducing silently verifiable proofs (SVPs), a new type of zero-knowledge proof that enables batched verification, dramatically reducing server-to-server communication. For the challenging problem of Heavy Hitters, Whisper integrates linear sketching data structures to allow servers to maintain running aggregates, thereby achieving sublinear storage growth. The system demonstrates a significant improvement in server-side efficiency, offering up to a 50x reduction in server-to-server communication and a 2x reduction in overall deployment costs compared to prior state-of-the-art systems, albeit with a slight increase in client-side computation and communication.

Presented by Mayank Rathee and his collaborators Yuwen Zhang, Henry Corrigan-Gibbs, and Raluca Ada Popa, this research is crucial for developers and organizations building privacy-preserving applications, particularly those handling large datasets from numerous users. By making private analytics more scalable and cost-effective, Whisper paves the way for broader adoption of privacy-enhancing technologies in areas such as application optimization, trend analysis, and public health statistics, where data privacy is paramount.

Background

▶ Watch: Introduction to private analytics and privacy challenge (0:00)

The utility of aggregate statistics in various applications is undeniable. For instance, a developer optimizing a photo application might want to understand the distribution of picture types (e.g., apples, bridges, cats) across their user base to inform feature development. However, directly collecting this raw data from users poses a significant privacy risk: if the collecting server is compromised, an adversary could learn sensitive information about individual users' data.

To address this, the field of private analytics has extensively explored solutions that ensure both correctness (the server computes the desired statistic) and privacy (individual user data remains confidential). A prominent approach involves secret sharing, where users split their sensitive data into multiple "shares" and send these shares to different, non-colluding servers. Typically, two servers are used: a primary server and a secondary helper server. A notable real-world deployment of this model is by ISRG (the entity behind Let's Encrypt), which acts as a helper server in some private analytics setups. In this scheme, each share appears random on its own, but when combined by the servers, they reconstruct the aggregate statistic. Privacy is maintained as long as at least one of the servers remains honest and uncompromised, as an adversary compromising only one server would only see random shares and the final aggregate, not individual user contributions.

While secret sharing effectively resolves the core privacy-correctness dilemma, it introduces new challenges, particularly concerning scalability. The talk highlights two critical issues with prior systems:

1. Server-to-Server Communication: To ensure the integrity of user submissions—that clients send "well-formed" inputs and do not cheat—prior systems rely on zero-knowledge proofs (ZKPs). Each client generates a ZKP alongside their secret shares. The servers then engage in a communication protocol to verify these proofs. The fundamental problem is that this verification process typically requires server-to-server communication for each individual client. Consequently, in systems with many clients (N), the server-to-server communication scales linearly with N, leading to high monetary costs when deployed on major cloud providers.
2. Storage for Heavy Hitters: When the desired aggregate statistic is a list of Heavy Hitters (the most popular items in a large dataset, where the full dataset might be too large to materialize), prior secret-sharing schemes face an additional storage challenge. Servers cannot easily maintain a running aggregate of the data. Instead, they often need to store individual client contributions or intermediate states, which also causes storage requirements to grow linearly with the number of clients. This issue is specific to Heavy Hitters and not present for simpler statistics like sums, means, or basic histograms.

These two challenges represent significant bottlenecks for deploying private analytics at scale, limiting their applicability despite their strong privacy guarantees. Whisper directly targets these inefficiencies to enable more practical and widespread use of private data aggregation.

Key Findings

▶ Watch: Challenges: Communication and storage scaling in prior work (2:20)

Whisper's primary contribution lies in addressing the fundamental scalability limitations of prior private analytics systems. The key findings and advancements are:

1. Sublinear Server-to-Server Communication: For both basic statistics (like histograms) and Heavy Hitters, Whisper achieves server-to-server communication that grows sublinearly in the number of clients, N. This is a significant departure from prior work, where communication scaled linearly with N. The sublinear growth is achieved by dividing clients into batches of size B. The communication scales with the number of batches and a term representing communication per batch. In an optimal configuration, by setting the batch size B equal to N (i.e., processing all clients in a single batch), Whisper can achieve communication that asymptotically matches the information lower bound, meaning it's as efficient as theoretically possible.
2. Sublinear Storage for Heavy Hitters: For the problem of identifying Heavy Hitters, Whisper dramatically reduces server storage requirements. Unlike prior schemes where storage grew linearly with N, Whisper's storage scales only with the batch size B. This allows servers to maintain a running aggregate, eliminating the need to store individual client data or large intermediate states.
3. Introduction of Silently Verifiable Proofs (SVPs): The core enabler for sublinear server-to-server communication is the invention of SVPs. These are new zero-knowledge proofs specifically designed for batched verification. Instead of exchanging messages for each client's proof, servers using SVPs only need to exchange a small, fixed-size message (e.g., 128 bits) to verify an arbitrary number of proofs within a batch. This "silent" verification property is central to Whisper's efficiency gains.
4. Approximate Heavy Hitters with Strong Guarantees: To achieve sublinear storage for Heavy Hitters, Whisper embraces an approximate solution. While this introduces a small, controllable error, the system provides new analysis demonstrating that it can reliably recover Heavy Hitters that appear more frequently than the number of malicious clients in the system. This ensures practical utility even with the approximation.
5. Cost-Effective Deployment: The combined improvements translate into tangible cost savings. Evaluations show that Whisper can achieve an estimated 2x improvement in deployment cost on cloud platforms (e.g., Google Cloud) compared to the prior best system, PR3, primarily due to the drastically reduced server-to-server communication.
6. Trade-offs: While Whisper offers substantial server-side efficiency gains, it incurs a slight overhead in client communication and computation. This trade-off is often acceptable in scenarios where server infrastructure costs and communication latency are dominant concerns compared to individual client resource usage.

In essence, Whisper's key findings revolve around re-architecting the proof verification and data aggregation mechanisms in private analytics to break free from linear scaling bottlenecks, making large-scale, privacy-preserving data analysis economically and practically feasible.

Technical Deep Dive

▶ Watch: Introducing Whisper: Sublinear communication and storage improvements (4:00)

The inefficiencies in prior private analytics schemes, specifically the linear scaling of server-to-server communication, stem directly from the necessity of verifying each client's zero-knowledge proof individually. When a client submits its secret shares and a proof of their well-formedness, the two servers must interact to validate that proof. If there are N clients, this interaction effectively happens N times, leading to O(N) communication overhead between servers.

Whisper’s solution to this problem is the introduction of silently verifiable proofs (SVPs). The fundamental idea behind SVPs is to enable batched proof verification. Instead of verifying proofs one-by-one, SVPs allow servers to verify an entire batch of proofs (from many clients) by exchanging a minimal, fixed-size message. The talk states that servers might only need to exchange 128 bits to verify an arbitrary number of proofs within a batch. This low communication overhead is why they are termed "silently verifiable."

The core mechanism enabling batch verification for SVPs is a simple equality check. Here's how it works:

1. Local Tag Derivation: When servers receive SVPs from multiple clients in a batch, each server can locally derive a unique "tag" from each proof. For instance, Server 1 derives T1, T2, T3 from Client 1, 2, and 3's proofs, respectively. Similarly, Server 2 derives T1', T2', T3' from its received proofs.
2. Consistency Condition: The design of SVPs ensures that if a client's proof is valid, then Ti (derived by Server 1) must be equal to Ti' (derived by Server 2).
3. Batched Equality Check: Instead of communicating to check each Ti == Ti' pair individually, the servers compute a cryptographic hash over all the tags they derived locally. Server 1 computes Hash(T1, T2, T3, ...), and Server 2 computes Hash(T1', T2', T3', ...). They then only exchange these two aggregate hashes. If the hashes match, then with high probability, all individual Ti and Ti' pairs matched, implying that all proofs in the batch were valid. This effectively compresses the verification of N proofs into a single, fixed-size communication.

Constructing Silently Verifiable Proofs

The construction of SVPs from existing (non-batch-verifiable) zero-knowledge proofs is a key technical contribution. Whisper leverages the MPC-in-the-head framework and a multi-party variant of the Fiat-Shamir heuristic.

1. Client-Side Emulation: The client, acting as the prover, emulates the entire interaction of the prior proof system (which would involve server-to-server communication) entirely in its own head. This means the client simulates both servers' roles in the ZKP protocol.
2. Transcript Extraction: From this internal emulation, the client extracts the full "transcript" of the simulated server-to-server communication, specifically the messages that would have been exchanged between the servers (e.g., y1 from Server 1 to Server 2, and y2 from Server 2 to Server 1).
3. SVP Formulation: The client then sends its original proof (from the prior system) along with the simulated transcript messages. Specifically, to Server 1, the client sends its proof and y2 (the message Server 1 would expect to receive from Server 2). To Server 2, the client sends its proof and y1 (the message Server 2 would expect to receive from Server 1).

Detecting Cheating with Equality Checks

A crucial aspect is detecting malicious clients who might send incorrect y1 or y2 values to trick the servers. Whisper's design provides a robust mechanism for this using the aforementioned equality checks.

1. Local Verification: With the client providing the "expected" messages, each server locally has all the information needed to perform the accept/reject function of the proof. For example, Server 2 locally derives its y2 from the proof it received. It also received y1 from the client. With y1 and its derived y2, it can compute F(y1, y2) to verify the proof locally.
2. The Cheating Scenario: A malicious client could send an incorrect y2 to Server 1, making Server 1's local verification pass, even if the actual proof is invalid or inconsistent.
3. The Equality Check for Cheating Detection: To prevent this, the servers perform a simple equality check: Server 1 receives Y2_client from the client. Server 2 derives the true Y2_derived from the proof it received. For the proof to be valid and the client honest, Y2_client must equal Y2_derived. The same logic applies to Y1. These equality checks, as previously described, can be batched using hashing, ensuring that the client has consistently provided the correct messages to both servers. This simple yet powerful mechanism ensures integrity without incurring linear communication costs.

Heavy Hitters with Linear Sketching

For the specific challenge of Heavy Hitters, where prior schemes struggled with linear storage growth due to the inability to maintain running aggregates, Whisper introduces an innovative approach:

1. Approximate Heavy Hitters: Whisper accepts that computing Heavy Hitters precisely in a streaming, private context is difficult and instead focuses on the approximate Heavy Hitters problem. This allows for some error in the computation but enables significant efficiency gains.
2. Linear Sketching Data Structures: The core idea is to use linear sketching data structures. These probabilistic data structures are designed to summarize large streams of data in a small, fixed amount of space, allowing for approximate queries. Examples include Count-Min Sketch or Count Sketch.
3. Maintaining Running Aggregates: By integrating these sketches, servers can maintain a running aggregate of the data, updating the sketch with each client's contribution without storing individual client data. This ensures that storage scales only with the size of the sketch (which depends on the desired accuracy and probability of error), not with the number of clients.
4. Malicious Client Robustness: A critical challenge is proving that the accuracy of these sketches is maintained even in the presence of malicious clients. Whisper provides new analytical results demonstrating that it can reliably recover Heavy Hitters that appear more frequently than the number of malicious clients in the system. This ensures that the approximation remains useful and robust against adversarial behavior.

In summary, Whisper's technical advancements, particularly SVPs and the integration of linear sketching with malicious client analysis, provide a robust and highly scalable framework for private analytics that overcomes the major bottlenecks of previous systems.

Demo / Proof of Concept

▶ Watch: Solution: Silently Verifiable Proofs for batch verification (6:40)

While the talk did not feature a live demonstration or a visual proof-of-concept, the speakers presented a comprehensive evaluation of Whisper's performance against the prior state-of-the-art system, PR3. This evaluation serves as the practical validation of Whisper's theoretical efficiency gains.

The evaluation focused on a common private analytics task: computing a histogram with 1,000 bins. The simulated deployment scenario involved:

• Two servers (as required by the secret-sharing model).
• 100,000 clients submitting data.
• A realistic adversarial model where 1% of these clients were malicious, attempting to submit ill-formed inputs or cheat the system.

The comparison highlighted the following key performance metrics:

1. Client Communication and Computation: As anticipated, Whisper incurs a slight overhead for clients. This means individual clients using Whisper will experience a minor increase in the amount of data they send and the computational effort required to generate their secret shares and silently verifiable proofs. The talk acknowledged this as a trade-off for the substantial server-side benefits.
2. Server-to-Server Communication: This is where Whisper demonstrates its most significant advantage. The server-to-server communication in Whisper was measured to be 50 times better (i.e., 50x less data exchanged) than in PR3. This dramatic reduction is a direct consequence of the batched verification enabled by silently verifiable proofs. Instead of exchanging messages for each of the 100,000 clients, servers only need to perform a few fixed-size exchanges per batch.
3. Estimated Deployment Cost: To quantify the real-world impact, the speakers estimated the cost of deploying these systems on a major cloud provider like Google Cloud. By considering both communication and computation as primary cost metrics, Whisper achieved an estimated 2x improvement in overall deployment cost compared to PR3. This demonstrates that the technical innovations directly translate into tangible economic benefits for organizations implementing private analytics.

The evaluation extended beyond just histograms, with the paper discussing results for other statistics as well, further reinforcing Whisper's broad applicability and efficiency across various private analytics tasks. These quantitative results provide compelling evidence for Whisper's practical viability and its superiority over existing methods for large-scale private data aggregation.

Defensive Implications

▶ Watch: Demonstrating the simple equality check verification procedure (7:50)

Whisper presents significant defensive implications for organizations and developers operating or planning to deploy private analytics systems, especially those dealing with large user bases and sensitive data. The core message for defenders is that it is now possible to achieve privacy-preserving data aggregation at scales previously considered impractical or prohibitively expensive.

Here's how defenders should leverage this information:

1. Re-evaluate Private Analytics Deployments: Organizations currently using or considering private analytics solutions (e.g., for telemetry, application usage statistics, or health data aggregation) should re-evaluate their architectures in light of Whisper. Systems that frequently encounter communication bottlenecks or high infrastructure costs due to linearly scaling server-to-server communication are prime candidates for adopting Whisper's approach.
2. Prioritize Server-Side Efficiency for Scale: For large-scale deployments with hundreds of thousands or millions of clients, the 50x improvement in server-to-server communication offered by Whisper is a game-changer. This directly translates to lower cloud costs, reduced network latency, and improved system throughput. Defenders should prioritize solutions like Whisper when server-side operational expenditure is a critical concern.
3. Consider Heavy Hitters with Confidence: For use cases requiring the identification of frequent items (Heavy Hitters), Whisper offers a robust solution that overcomes the linear storage problem. Organizations can now implement privacy-preserving Heavy Hitter detection with sublinear storage, making it feasible for real-time or streaming analytics on vast datasets. The trade-off of "approximate" Heavy Hitters is often acceptable in many practical scenarios, especially given Whisper's guarantees of recovering items appearing more than malicious clients.
4. Manage Client-Side Overhead: While Whisper provides substantial server-side gains, it does introduce a slight increase in client-side computation and communication. Defenders must assess if their client base (e.g., mobile devices, IoT endpoints) can tolerate this marginal overhead. For many applications, a small increase in client-side resource usage is a minor cost compared to the significant reduction in server infrastructure and operational costs.
5. Leverage Robustness to Malicious Clients: Whisper's design explicitly accounts for malicious clients (up to 1% in the evaluation), ensuring that the integrity of aggregate statistics is maintained through silently verifiable proofs and robust cheating detection mechanisms. This built-in resilience simplifies the security posture for defenders, as they don't need to assume all clients are honest.
6. Explore Future Work Directions: The speakers mentioned future work on improving proof efficiency (size and time). Defenders should keep an eye on these developments, as further optimizations could reduce the client-side overhead, making Whisper even more universally applicable.

In essence, Whisper provides a powerful set of tools for building more scalable, cost-effective, and privacy-preserving data analytics systems. Defenders should actively consider integrating these techniques to enhance both the security and operational efficiency of their data collection and analysis pipelines.

Key Takeaways

• Whisper significantly enhances the scalability of private analytics systems by addressing critical bottlenecks in server-to-server communication and storage.
• Silently Verifiable Proofs (SVPs) are a core innovation, enabling batched zero-knowledge proof verification and reducing server-to-server communication by up to 50x compared to prior systems like PR3.
• Sublinear storage for approximate Heavy Hitters is achieved through the integration of linear sketching data structures, allowing servers to maintain running aggregates without linear growth in storage with client count.
• The system offers substantial cost savings, demonstrating an estimated 2x improvement in deployment costs on cloud platforms due to reduced communication and computation.
• Whisper's construction relies on MPC-in-the-head and equality checks to enable efficient, batched verification and robust detection of malicious client behavior.
• A trade-off exists with a slight increase in client-side overhead, which is generally outweighed by the significant server-side efficiency gains, making it suitable for large-scale deployments.

About the Speaker(s)

The talk "Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs" was presented by Mayank Rathee. This work is a collaborative effort, with Mayank Rathee acknowledging his co-authors Yuwen Zhang, Henry Corrigan-Gibbs, and Raluca Ada Popa. The transcript does not provide further biographical details regarding their specific titles or affiliations beyond their names and their collaborative contribution to this research project.