Lower bound framework for differentially private and oblivious data structures

DOI10.1007/978-3-031-30545-0_17MaRDI QIDQ6138099zbMATH OpenFDO

Authors Giuseppe Persiano, Kevin Yeo

Publication date 16 January 2024

Published in Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-30545-0_17

Mathematics Subject Classification ID

Cryptography (94A60) Data structures (68P05) Privacy of data (68P27)

Recommendations

• Lower bounds for differentially private RAMs
• Lower bounds for oblivious data structures
• Foundations of differentially oblivious algorithms
• Foundations of Differentially Oblivious Algorithms
• A logarithmic lower bound for oblivious RAM (for all Parameters)

Cites work

• A logarithmic lower bound for oblivious RAM (for all Parameters)
• A lower bound for one-round oblivious RAM
• Distributed Oblivious RAM for Secure Two-Party Computation
• Foundations of differentially oblivious algorithms
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound?
• Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs
• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower Bounds for Oblivious Near-Neighbor Search
• Lower bounds for differentially private RAMs
• Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
• Lower bounds for multi-server oblivious RAMs
• Lower bounds for oblivious data structures
• Oblivious parallel RAM and applications
• Oblivious parallel RAM: improved efficiency and generic constructions
• On dynamic bit-probe complexity
• On the (in)security of hash-based oblivious RAM and a new balancing scheme
• Onion ORAM: a constant bandwidth blowup oblivious RAM
• OptORAMa: optimal oblivious RAM
• Preserving order in a forest in less than logarithmic time and linear space
• Privacy-preserving group data access via stateless oblivious RAM simulation
• Private information retrieval with sublinear online time
• Reducing the servers' computation in private information retrieval: PIR with preprocessing
• Simple and efficient two-server ORAM
• Single-server private information retrieval with sublinear amortized time
• Software protection and simulation on oblivious RAMs
• Statistically-secure ORAM with \(\tilde{O}(\log^2 n)\) overhead
• Stronger lower bounds for online ORAM
• The cell probe complexity of dynamic range counting
• Worst-case Analysis of Set Union Algorithms
• Yes, there is an oblivious RAM lower bound!

Cited in

(2)

• A logarithmic lower bound for oblivious RAM (for all parameters)
• Advanced composition theorems for differential obliviousness

This page was built for publication: Lower bound framework for differentially private and oblivious data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138099)