Paper 2023/842
Advanced Composition Theorems for Differential Obliviousness
Abstract
Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious
algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO.
In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ITCS 2024
- Keywords
- Differential Obliviousness
- Contact author(s)
-
mingxunz @ andrew cmu edu
zmsxsl @ connect hku hk
hubert @ cs hku hk
runting @ gmail com - History
- 2023-11-09: last of 4 revisions
- 2023-06-06: received
- See all versions
- Short URL
- https://ia.cr/2023/842
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/842, author = {Mingxun Zhou and Mengshi Zhao and T-H. Hubert Chan and Elaine Shi}, title = {Advanced Composition Theorems for Differential Obliviousness}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/842}, year = {2023}, url = {https://eprint.iacr.org/2023/842} }