Foundations of Differentially Oblivious Algorithms
Open accessAbstract
It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program's runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “(∊, δ)-differential obliviousness”. We separate the notion of (∊, δ)-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ∊ and δ, not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy “almost for free”). On the other hand, we show that for very demanding choices of ∊ and δ, the same lower bounds for oblivious algorithms would be preserved for (∊, δ)-differential obliviousness.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Previous methods including finetuning, denoising, and fine-pruning have been shown to be insufficient against the latest attacks.
“Other previous methods, including finetuning, denoising, and fine-pruning [153], have been shown to be insufficient against the latest attacks [156], [53].”
From Privacy and Robustness in Federated Learning: Attacks and Defenses (2024) · cites this paper as [153]
Backdoor detection algorithms rely on the statistical difference between latent representations of backdoor-enabled and clean inputs in the poisoned model.
“These algorithms rely on the statistical difference between the latent representations of backdoor-enabled and clean (benign) inputs in the poisoned model.”
From Privacy and Robustness in Federated Learning: Attacks and Defenses (2024) · cites this paper as [153]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 16
- A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? J. Comput. Syst. Sci., 57(1):74-93, Aug. 1998.
- C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.
- C. Dwork, G. N. Rothblum, and S. P. Vadhan. Boosting and differential privacy. In FOCS, pages 51- 60. IEEE Computer Society, 2010.
- D. Eppstein, M. T. Goodrich, and R. Tamassia. Privacy-preserving data-oblivious geometric algorithms for geographic data. In GIS, pages 13-22, 2010.
- O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In ACM Symposium on Theory of Computing (STOC), 1987.
- O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In ACM symposium on Theory of computing (STOC), 1987.
- O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996.
- Y. Han. Deterministic sorting in o(nloglogn) time and linear space. J. Algorithms, 50(1):96-105, 2004.
- G. Kellaris, G. Kollios, K. Nissim, and A. O'Neill. Accessing data while preserving privacy. CoRR, abs/1706.01552, 2017. · arXiv
- D. E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. 1998.
- J. C. Mitchell and J. Zimmerman. Data-oblivious data structures. In STACS, pages 554-565, 2014.
- K. Nayak, X. S. Wang, S. Ioannidis, U. Weinsberg, N. Taft, and E. Shi. GraphSC: Parallel Secure Computation Made Easy. In IEEE S & P, 2015.
- N. Pippenger and L. G. Valiant. Shifting graphs and their applications. J. ACM, 23(3):423-432, July 1976.
- E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li. Oblivious RAM with O((log N ) 3 ) worst-case cost. In ASIACRYPT, pages 197-214, 2011.
- M. Thorup. Randomized sorting in o(nloglogn) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms, 42(2):205-230, 2002.
- S. Wagh, P. Cuff, and P. Mittal. Root ORAM: A tunable differentially private oblivious RAM. CoRR, abs/1601.03378, 2016. · arXiv
Cited by
Sorted by citations
Privacy and Robustness in Federated Learning: Attacks and Defenses
Lyu, L., Yu, H., Ma, X., Chen, C., Sun, L., Zhao, J., Yang, Q., & Yu, P. S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3216981 · Cited by 548 · see citing works
Oblix: An Efficient Oblivious Search Index
Mishra, P., Poddar, R., Chen, J., et al. (2018) · Proceedings - IEEE Symposium on Security and Privacy/Proceedings of the ... IEEE Symposium on Security and Privacy · doi:10.1109/sp.2018.00045 · Cited by 172 · see citing works
Secure Computation with Differentially Private Access Patterns
Mazloom, S., & Gordon, S. (2018) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3243734.3243851 · Cited by 43 · see citing works
Interpreting and Mitigating Leakage-Abuse Attacks in Searchable Symmetric Encryption
Xu, L., Duan, H., Zhou, A., et al. (2021) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2021.3128823 · Cited by 33 · see citing works
Recent advances and future challenges in federated recommender systems
Harasic, M., Keese, F.-S., Mattern, D., & Paschke, A. (2023) · International Journal of Data Science and Analytics · doi:10.1007/s41060-023-00442-4 · Cited by 32 · see citing works
Qin, L., Jayaram, R., Shi, E., et al. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3574245.3574267 · Cited by 20 · see citing works
Self-citationDoquet: Differentially Oblivious Range and Join Queries with Private Data Structures
Qiu, L., Kellaris, G., Mamoulis, N., et al. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3625054.3625055 · Cited by 16 · see citing works
FedKNN: Secure Federated k-Nearest Neighbor Search
Zhang, X., Wang, Q., Xu, C. L., et al. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3639266 · Cited by 15 · see citing works
Lyu, L. (2020) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn48605.2020.9207618 · Cited by 15 · see citing works
εpsolute: Efficiently Querying Databases While Providing Differential Privacy
Bogatov, D., Kellaris, G., Kollios, G., Kobbi Nissim, B., & O’Neill, A. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3484786 · Cited by 18 · see citing works
Dong, W., & Yi, K. (2023) · ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) · doi:10.1145/3584372.3588669 · Cited by 13 · see citing works
A language for probabilistically oblivious computation
Darais, D., Sweet, I., Liu, C., & Hicks, M. (2019) · Proceedings of the ACM on Programming Languages · doi:10.1145/3371118 · Cited by 21 · see citing works
Locality-Preserving Oblivious RAM
Asharov, G., Chan, T.-H. H., Nayak, K., et al. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17656-3_8 · Cited by 12 · see citing works
Self-citationDifferentially Oblivious Data Analysis With Intel SGX: Design, Optimization, and Evaluation
Wu, P., Li, Q. L., Ning, J., Huang, X., & Wu, W. (2021) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2021.3106317 · Cited by 11 · see citing works
What Storage Access Privacy is Achievable with Small Overhead?
Patel, S., Persiano, G., & Yeo, K. (2019) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3294052.3319695 · Cited by 10 · see citing works
The Price of Privacy: A Performance Study of Confidential Virtual Machines for Database Systems
Qiu, L., Taft, R., Shraer, A., & George Kollios, D. (2024) · International Workshop on Data Management on New Hardware (DaMoN) · doi:10.1145/3662010.3663440 · Cited by 9 · see citing works
Lower Bound Framework for Differentially Private and Oblivious Data Structures
Persiano, G., & Yeo, K. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30545-0_17 · Cited by 8 · see citing works
Desfontaines, D., & Pejó, B. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0028 · Cited by 7 · see citing works
Spreading the Privacy Blanket:
Gordon, D., Katz, J. I., Liang, M., & Xu, J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-09234-3_25 · Cited by 5 · see citing works
Differentially Oblivious Two-Party Pattern Matching With Sublinear Round Complexity
Wu, P., Ning, J., Huang, X., et al. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3206758 · Cited by 4 · see citing works
A Theory of Composition for Differential Obliviousness
Zhou, M., Shi, E., Chan, T.-H. H., & Maimon, S. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30620-4_1 · Cited by 4 · see citing works
Self-citationAugmented Shuffle Protocols for Accurate and Robust Frequency Estimation Under Differential Privacy
Murakami, T., Sei, Y., & Eriguchi, R. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00019 · Cited by 4 · see citing works
Locality-Preserving Oblivious RAM
Asharov, G., Chan, T.-H. H., Nayak, K., et al. (2022) · Journal of Cryptology · doi:10.1007/s00145-022-09419-1 · Cited by 2 · see citing works
Self-citationFast ORAM with Server-Aided Preprocessing and Pragmatic Privacy-Efficiency Trade-Off
Kolesnikov, V., Peceny, S., Trieu, N., et al. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-34671-2_31 · Cited by 1 · see citing works
Improving Utility and Security of the Shuffler-based Differential PrivacyPreprint
Wang, T., Ding, B., Xu, M., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.11515 · Cited by 1 · see citing works
What Storage Access Privacy is Achievable with Small Overhead?Preprint
Patel, S., Persiano, G., & Yeo, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.05452
Differentially Private Resource Allocation
Chen, J. Q., Wang, T., Zhang, Z., et al. (2023) · Annual Computer Security Applications Conference · doi:10.1145/3627106.3627181
Pelosi, G. (2024) · Springer eBooks · doi:10.1007/978-3-642-27739-9_1551-1
Pelosi, G. (2025) · Springer eBooks · doi:10.1007/978-3-030-71522-9_1551
On the Privacy of Sublinear-Communication Jaccard Index Estimation via Min-hash
Liang, M., Choi, S. G., Dachman-Soled, D., et al. (2025) · IACR Communications in Cryptology · doi:10.62056/ak2i5w7sf
Differentially Private Access in Encrypted Search: Achieving Privacy at a Small Cost?
Pöllmann, D., & Tang, T. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765038
- Authors
- Chan, T.-H. H., Chung, K.-M., Maggs, B. M., & Shi, E.
- Affiliations
- University of Hong Kong (HK)
- Academia Sinica (TW)
- Akamai (United States) (US)
- Cornell University (US)
- Venue
- Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
- Published
- 2019-01
- Pages
- 2448-2467
- OpenAlex
- W2950330052
- Cited by
- 33
- References
- 0
- Citations by year
- 2025: 4 · 2024: 3 · 2023: 7 · 2022: 5 · 2021: 3 · 2020: 4 · 2019: 5 · 2018: 2
- FWCI
- 1.59
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Society for Industrial and Applied Mathematics eBooks (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Security and Verification in Computing
- Keywords
- oblivious RAM, differential privacy, access pattern leakage, oblivious algorithms, binary search trees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
