Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors

arXiv:2606.09402 · cs.CR · Submitted 2026-06-08 · Read on arXiv

cs.CR

Submitted: 2026-06-08

Updated: 2026-08-27

Comments: Full version of the paper accepted at USENIX Security 2026; The current version added an addendum to the runtime (Appendix F)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Accuracy — 43× in this paper · explained in 1 episode
• Robustness — 40× in this paper · explained in 5 episodes
• Differential Privacy — 30× in this paper · explained in 4 episodes
• Trace — 23× in this paper · explained in 2 episodes
• Geometric Distribution — 22× in this paper · explained in 2 episodes
• Uniform Dummies — 16× in this paper
• Differentially Private — 6× in this paper · explained in 3 episodes
• Federated Learning — 4× in this paper · explained in 14 episodes
• Trusted Execution Environment — 4× in this paper
• Analyzer — 1× in this paper · explained in 1 episode
• Communication Overhead — 1× in this paper · explained in 2 episodes
• Differential Obliviousness — 1× in this paper
• Generalization — 1× in this paper · explained in 13 episodes
• Maximal Gain Attack — 1× in this paper
• Mean Squared Error — 1× in this paper
• Multi-Party Computation — 1× in this paper
• Verification — 1× in this paper · explained in 2 episodes

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Estimating the Social Cost of Corporate Data Breaches
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills