Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors
2026-06-08 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors study how to protect users' data privacy when it is shuffled and processed securely. They improve an existing model by using special trusted hardware (TEEs) to make sure the shuffler does not cheat or leak information. To strengthen privacy, they create a new standard called Fully Oblivious Differential Privacy (FODP) that guards against hardware side-channel attacks. They also design practical algorithms and test them on Intel's secure hardware, showing better privacy and performance compared to other methods.
Differential PrivacyShuffle ModelTrusted Execution Environments (TEEs)Side-Channel AttacksFully Oblivious Differential Privacy (FODP)Random SamplingDummy DataCount-Min SketchIntel SGXMemory Obfuscation
Authors
Takao Murakami, Yuichi Sei, Reo Eriguchi
Abstract
In the shuffle model of DP (Differential Privacy), a shuffler randomly permutes users' data to achieve high accuracy and privacy. Recent studies show that most existing shuffle protocols are vulnerable to collusion attacks by the data collector and users. They address this issue by introducing the augmented shuffle model that incorporates random sampling and dummy data addition into the shuffler. However, it remains open how to ensure the shuffler follows the protocol and does not collude with the data collector in this model. We address this trust issue by thoroughly exploring the augmented shuffle model with TEEs (Trusted Execution Environments). We first introduce a new privacy notion, FODP (Fully Oblivious DP), which strengthens DP to prevent various TEE side-channel attacks based on external/internal memory access patterns and control flows. We propose a general framework for FODP algorithms based on memory-size obfuscation and three concrete algorithms within it. We also improve the efficiency of our algorithms by using the count-min sketch and optimizing the number of hashes. We evaluate our algorithms on Intel SGX and demonstrate their effectiveness through comparisons with nine baselines.