Lower Bound Framework for Differentially Private and Oblivious Data Structures

ePrint Report: Lower Bound Framework for Differentially Private and Oblivious Data Structures

Giuseppe Persiano, Kevin Yeo

In recent years, there has been significant work in studying data structures that provide privacy for the operations that are executed. These primitives aim to guarantee that observable access patterns to physical memory do not reveal substantial information about the queries and updates executed on the data structure. Multiple recent works, including Larsen and Nielsen [Crypto'18], Persiano and Yeo [Eurocrypt'19], Hubáček et al. [TCC'19] …

data eprint report framework oblivious