Data-oblivious graph algorithms in outsourced external memory

DOI10.1007/978-3-319-12691-3_19MaRDI QIDQ2942400zbMATH OpenOpenAlexFDO

Authors Joseph A. Simons, Michael T. Goodrich

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.0597

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Mathematical problems of computer architecture (68M07) Nonnumerical algorithms (68W05)

Abstract: Motivated by privacy preservation for outsourced data, data-oblivious external memory is a computational framework where a client performs computations on data stored at a semi-trusted server in a way that does not reveal her data to the server. This approach facilitates collaboration and reliability over traditional frameworks, and it provides privacy protection, even though the server has full access to the data and he can monitor how it is accessed by the client. The challenge is that even if data is encrypted, the server can learn information based on the client data access pattern; hence, access patterns must also be obfuscated. We investigate privacy-preserving algorithms for outsourced external memory that are based on the use of data-oblivious algorithms, that is, algorithms where each possible sequence of data accesses is independent of the data values. We give new efficient data-oblivious algorithms in the outsourced external memory model for a number of fundamental graph problems. Our results include new data-oblivious external-memory methods for constructing minimum spanning trees, performing various traversals on rooted trees, answering least common ancestor queries on trees, computing biconnected components, and forming open ear decompositions. None of our algorithms make use of constant-time random oracles.

Recommendations

• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Data-oblivious data structures
• Privacy-Preserving Graph Algorithms in the Semi-honest Model
• Graph drawing in the cloud: privately visualizing relational data using small working storage
• Efficient, oblivious data structures for MPC

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• Data-oblivious graph algorithms in outsourced external memory
• Graph drawing in the cloud: privately visualizing relational data using small working storage
• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• On efficient parallel strong orientation
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Optimizing ORAM and Using It Efficiently for Secure Computation
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Path ORAM
• Perfectly secure oblivious RAM without random oracles
• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Privacy-preserving group data access via stateless oblivious RAM simulation
• Software protection and simulation on oblivious RAMs
• Two linear time algorithms for MST on minor closed graph classes.

Cited in

(7)

• Data-oblivious graph algorithms in outsourced external memory
• Design and Engineering of External Memory Traversal Algorithms for General Graphs
• Graph drawing in the cloud: privately visualizing relational data using small working storage
• Memory Efficient Anonymous Graph Exploration
• Privacy-Preserving Graph Algorithms in the Semi-honest Model
• scientific article; zbMATH DE number 7650132 (Why is no real title available?)
• Optimal offline ORAM with perfect security via simple oblivious priority queues

This page was built for publication: Data-oblivious graph algorithms in outsourced external memory

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