Source-linked AI summary
Prochlo: Strong Privacy for Analytics in the Crowd
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Usharsee Kode, Julien Tinnes, Bernhard Seefeld
TL;DR
Large-scale software monitoring offers important operational benefits but can expose highly identifying or sensitive user information, while existing privacy mechanisms often have limited utility or deployment scope. The paper presents ESA and its PROCHLO implementation, combining encoding, shuffling, cryptography, trusted computing, and differential privacy. It reports high utility with strong privacy guarantees across multiple monitoring and machine-learning tasks, while noting scalability limits for the Stash Shuffle at very large problem sizes.
Problem
The paper addresses how to support useful large-scale software monitoring when existing privacy guarantees remain mostly theoretical, narrow in scope, or difficult to deploy.
Method
ESA divides processing among encoders, shufflers, and analyzers, using cryptographic protection, randomized thresholding, anonymity, and independently applicable differential privacy.
Results
PROCHLO achieves high utility and strong privacy guarantees across two monitoring use cases, collaborative filtering, and deep learning.
Takeaways & Limitations
ESA supports privacy-preserving analysis of unique or highly identifying reports while remaining compatible with practical software-monitoring workflows.
Takeaways & Limitations
The Stash Shuffle reaches scalability limits at 200 million items for the stated SGX parameters, requiring higher overhead or altered security parameters for larger problems.
Abstract
from arXiv · showhide
The large-scale monitoring of computer users' software activities has become commonplace, e.g., for application telemetry, error reporting, or demographic profiling. This paper describes a principled systems architecture---Encode, Shuffle, Analyze (ESA)---for performing such monitoring with high utility while also protecting user privacy. The ESA design, and its Prochlo implementation, are informed by our practical experiences with an existing, large deployment of privacy-preserving software monitoring. (cont.; see the paper)
1. Introduction
Software monitoring provides operational benefits but raises serious privacy concerns, while existing privacy-preserving approaches often lack either broad utility or practical deployment. The paper introduces ESA and PROCHLO to combine high-utility monitoring with strong, independently enforceable privacy guarantees.
- Software monitoring supports feature measurement, performance analysis, error reporting, and security updates, but can systematically collect information about users, devices, and software.
- Existing privacy guarantees are often limited to theory, narrow deployments, or nascent mechanisms, leaving automatically collected profiling data insufficiently protected in practice.
- ESA uses encrypted records and explicit trust assumptions to remain compatible with centralized database workflows while restricting processing to permitted analyses.
- PROCHLO hardens ESA with SGX-based Stash Shuffle, secret sharing, blinding, and differential privacy applied independently across processing steps.
- Across representative monitoring, collaborative-filtering, and deep-learning tasks, PROCHLO achieves both high utility and strong privacy guarantees.
2. Motivation and Alternatives
Large-scale software monitoring needs stronger technical privacy protections than conventional access controls and user approval alone provide. ESA addresses this gap by combining data reduction, cryptographic protection, randomized thresholding, anonymity, and privacy-preserving analysis while retaining practical analytics workflows.
- Established monitoring practices reduce, scrub, and coarsen data and require opt-in approval, but rely primarily on users’ declared trust in the collecting party.
- ESA extends these practices into a flexible platform for high-utility monitoring without increasing users’ privacy risk.
- Application identities and API-usage profiles can closely correlate with user activity, making naive collection potentially unique, incriminating, or secret.
- Locally differentially private analysis adds substantial noise, limiting reliable measurement largely to frequent elements in peaky power-law distributions.
- Partitioning reports can improve signal recovery and reduce required data by two orders of magnitude, but can weaken privacy by revealing partition membership.
- ESA’s intermediary manages sufficiently large, uncertain crowds through batching and randomized thresholding, while cryptography supports anonymity and protection for unique reports.
3. The Encode-Shuffle-Analyze Architecture
ESA divides privacy-preserving monitoring into encoders, shufflers, and analyzers, using trust assumptions, encryption, fragmentation, thresholding, and analysis protections to preserve utility while limiting linkability and inference.
- Encoder: Encoders run on client devices, control released data’s scope, granularity, and randomness, and use nested encryption to constrain processing parties and order.They can remove identifiers, fragment data, or add noise for local differential privacy or plausible deniability.
- Shuffler: Shufflers remove metadata, batch and blindly shuffle encrypted records, and threshold sparse crowd IDs so items become less linkable and rare classes can be discarded.Crowd-ID thresholding improves privacy for crowd counts while introducing a slight systematic bias for small counts.
- Analyzer: Analyzers decrypt, store, aggregate, and release shuffled data; their cryptographic keys specify the permitted analysis and associated privacy protection.Analyzer outputs are treated as public in the attack model, motivating further protection against statistical inference.
- End-to-end guarantees: ESA can combine shuffling, secret sharing, blinding, and minimal analyzer noise to support standard analysis while enabling differentially private release with little utility loss.For app/API fragments, the combined data need not be treated as sensitive even without encoding noise.
- Threat model: The architecture composes independently added privacy guarantees across stages and remains structured around users’ trust assumptions and possible compromise or collusion.Under the stated powerful attack model, ESA can still provide differential privacy guarantees, although encoder compromise enables Sybil and pollution attacks that the work does not further consider.
- Encoder: Fragmentation can split unique user data into separate reports, reducing the identifying structure exposed by any single report.The architecture describes this approach for movie-rating sets and other potentially unique data.
4. PROCHLO Implementation and Hardening
PROCHLO hardens ESA with trustworthy hardware, secret sharing, and cryptographic blinding to strengthen privacy under stronger threat models and distribute shuffler trust.
- PROCHLO hardening: PROCHLO introduces the scalable Stash Shuffle, based on Intel SGX, alongside secret sharing and blinding techniques for hardening ESA’s processing steps.These mechanisms target stronger privacy assurances while preserving the pipeline’s functionality.
4.1 Higher Assurance by using Trustworthy Hardware
PROCHLO uses trustworthy hardware, specifically Intel SGX, to harden the ESA shuffler while limiting trusted computing assumptions. Because SGX private memory is small, the design requires oblivious shuffling; existing approaches motivate the Stash Shuffle, whose scalability still has defined limits.
- Trustworthy hardware: Trustworthy hardware allows PROCHLO to collocate the shuffler with the analyzer while reducing reliance on a distinct trusted third party.The hardware prevents the hosting organization from directly accessing protected shuffler state, while limiting secure private memory and system I/O.
- SGX attestation: SGX attestation lets clients verify the shuffler code and legitimate processor certificate chain before encrypting data for its public key.The shuffler places its public key in an attestation quote, enabling clients to derive an ephemeral encryption key for each data item.
- Oblivious shuffling: Oblivious shuffling hides the permutation of large encrypted arrays by processing small batches in private memory through publicly observable operations.A primitive operation reads records under Key1, randomly shuffles them privately, and writes them under Key2; security depends on making the resulting order indistinguishable from random.
- State of the art: Existing oblivious-shuffling approaches impose substantial SGX costs: Batcher’s sort processes 49× the dataset for 10 million records and 100× for 100 million.The corresponding daily-scale parallelization would require 33 machines for 10 million records and 330 for 100 million.
- The Stash Shuffle: These scalability, efficiency, and randomness constraints led PROCHLO to design the Stash Shuffle, which reaches its SGX scalability limit at 200 million items.Larger problems require spilling internal state to untrusted memory, roughly doubling processing overhead, or running the algorithm twice with smaller security parameters.
- Crowd cardinality thresholding: If crowd ID domains do not fit in private memory, ESA must use a more expensive oblivious-sorting-and-scanning approach for thresholding.The paper reports that all applied ESA problems so far had crowd ID domains small enough to count inside private memory.
4.2 Encoding Using Secret-Sharing Cryptography
ESA’s secret-sharing encoding protects sensitive user data by distributing message-derived key material across independently computed shares. The construction permits recovery with enough matching shares while revealing no message information from fewer than the threshold.
- Security: The scheme targets data with unique, hard-to-guess values, including fingerprints or random URLs, and composes with randomized thresholding.Combining it with blinded crowd IDs extends protection to both easy-to-guess limited-domain data and hard-to-guess unique data.
- Construction: Secret-share encoding combines deterministic encryption under km = H(m) with a randomized t-secret share of km, forming (c, aux).Users can compute the shares independently, enabling direct use as an ESA encoding scheme.
- Construction: Any t matching shares for ciphertext c recover m by reconstructing km from the shares and decrypting c.The recovery procedure first derives the message-derived key, then uses it to decrypt the ciphertext.
- Security: At most t −1 matching shares reveal no information about m beyond what an adversary could guess beforehand.The guarantee combines Shamir secret-sharing security with the security of a message-derived key, especially when m is hard to guess.
4.3 Blinded Crowd IDs for Shuffler Thresholding
Prochlo enables private thresholding on sensitive crowd IDs through a split shuffler whose non-colluding parties jointly process blinded identifiers without seeing them in clear. The design preserves equality for comparison and counting while protecting against dictionary attacks and supporting privacy-sensitive collection scenarios.
- Mechanism: Prochlo hashes each crowd ID into a prime-order group and uses a two-party split shuffler to jointly shuffle and threshold without exposing the ID in clear.The encoder computes µ = H(crowd ID), avoiding transmission of the crowd ID encrypted under a single shuffler’s key.
- Mechanism: Three extra group exponentiations let Shuffler 2 process crowd IDs hashed and raised to secret power α while preserving equality for comparison and counting.
- Privacy: As long as the shufflers do not collude, neither can mount a dictionary attack or access the crowd ID in clear.Shuffler 1 lacks Shuffler 2’s private key, while Shuffler 2 lacks Shuffler 1’s secret α.
- Use cases: Private thresholding addresses identifying crowd IDs, low-frequency data points vulnerable to de-anonymization, and easily guessable secret-share encoded data.
- Evaluation: Table 2 reports Stash Shuffle execution by input size, per-phase and total execution time, and maximum private SGX memory.
4.4 Implementation
The PROCHLO framework and its Stash Shuffle implementation are written in C++ with OpenSSL, gRPC, SGX enclaves, and SGX SDK cryptographic libraries. An open-source implementation is being gradually released.
- Implementation: PROCHLO comprises 1100 lines of C++ using OpenSSL and gRPC, plus 1600 lines for cryptographic hardening.
- Implementation: The Stash Shuffle uses 2300 lines of C++ with SGX enclaves and OpenSSL plus Linux SGX SDK cryptographic libraries.
- Release: An open-source implementation is gradually released at the project’s GitHub repository.
5. Evaluation
The evaluation ports ESA to multiple monitoring analyses, testing how different encoding, crowd, shuffling, and thresholding choices balance privacy and utility. Across case studies, PROCHLO preserves useful analytical performance, including for long-tailed data and privacy-sensitive sequences.
- Evaluation design: The four PROCHLO pipelines vary encoders, shufflers, and analyzers to measure how ESA privacy affects analytical utility.Thresholds are set to 20 in the described experiments, with consistent noisy-loss parameters across pipelines.
- 5.2 Vocab: NoCrowd achieves the highest utility but provides no differential privacy, while ∗-Crowd loses little utility from noisy thresholding and recovers a large fraction of unique words.NoCrowd uses no crowd-based thresholding; the ∗-Crowd experiments retain strong utility relative to the non-private baseline.
- 5.2 Vocab: RAPPOR recovers less than 5% of PROCHLO’s utility on the long-tailed Vocab task, while partitioning improves RAPPOR only 1.13× to 3.45×.The partitioning comparison relaxes the guarantee from 2-differential privacy to (2.25, 10^-6)-differential privacy.
- 5.3 Perms: PROCHLO improves Web-page recovery by several orders of magnitude over RAPPOR while providing at least (ε=1.2, δ=10^-7)-differential privacy.The configuration uses threshold 100, Gaussian noise σ = 4, and blinded, secret-shared ⟨page, feature⟩ crowd IDs.
- 5.4 Suggest: A 3-tuple sequence model predicts the next view more than 1 in 8 times, reaches around 90% of non-private accuracy, and matches the quality of a prior best-known YouTube model.The model is trained on about 200 million longitudinal view histories using a small GPU cluster.
- 5.5 MovieLens: For collaborative filtering, PROCHLO’s RMSE is 0.9595 versus 0.9579 without privacy on 200 movies, 90K users, and 1.77M reports.The reported scores show similar utility under the compared private and non-private settings.
6. Conclusions
The paper presents ESA and PROCHLO as a practical way to address software-monitoring privacy concerns while retaining high-utility analysis and compatibility with standard engineering practice. Its flexible architecture combines cryptographic primitives, oblivious shuffling, trusted computing, and differential privacy to balance privacy and utility.
- 6. Conclusions: ESA and PROCHLO address software-monitoring privacy concerns while permitting high-utility analysis, standard engineering practice, and strong privacy guarantees.The conclusion frames these properties as simultaneously achievable in the proposed approach.
- 6. Conclusions: PROCHLO combines new cryptographic primitives and oblivious shuffling with trusted computing and differential privacy to balance privacy and utility.ESA remains flexible enough to support different implementations and techniques for different data-collection and analysis scenarios.
- 6. Conclusions: ESA is flexible enough to permit different implementations and techniques for different data-collection and analysis scenarios.The conclusion describes PROCHLO as a straightforward realization of the ESA architecture.