Paper 2026/603

Oblivious SpaceSaving: Heavy-Hitter Detection over Fully Homomorphic Encryption

Divyakant Agrawal, University of California, Santa Barbara

Amr El Abbadi, University of California, Santa Barbara

Abstract

Heavy-hitter detection is a fundamental primitive in stream analytics, with applications in network monitoring, telemetry, and large-scale data systems. In many practical deployments, this computation must be maintained continuously on remote infrastructure that offers higher availability and centralized operational control, even when the underlying streams contain sensitive identifiers or proprietary activity patterns. Existing privacy-preserving approaches either incur substantial statistical noise or rely on multi-server trust assumptions. Fully Homomorphic Encryption (FHE) offers an attractive alternative by enabling exact computation over encrypted data on a single untrusted server, but the high cost of encrypted comparisons has historically made stateful stream processing impractical. We present Oblivious SpaceSaving, a privacy-preserving reformulation of the classical Space-Saving algorithm for fully encrypted execution. Our central idea is the Moving Floor abstraction, which exploits a monotonicity invariant in the summary state to replace repeated magnitude comparisons with equality-based selection against a tracked encrypted floor. We further combine this with parallel victim selection and a hierarchical asynchronous ingestion pipeline, yielding an end-to-end encrypted heavy-hitter architecture that preserves the deterministic accuracy guarantees of the original algorithm. Our design reduces the cost of encrypted updates by up to $2.74\times$ over a naive oblivious baseline and sustains end-to-end encrypted ingestion throughputs of up to 4.30 items/s with sub-second amortized latency. These results show that, with the right algorithmic reformulation, classical streaming summaries can be made practically viable under fully encrypted execution, bringing privacy-preserving stream analytics significantly closer to deployment.

@misc{cryptoeprint:2026/603,
      author = {Sohaib .. and Divyakant Agrawal and Amr El Abbadi},
      title = {Oblivious {SpaceSaving}: Heavy-Hitter Detection over Fully Homomorphic Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/603},
      year = {2026},
      url = {https://eprint.iacr.org/2026/603}
}