Enhancing Privacy in Graph Algorithms: Data-Oblivious Approaches to DFS and Dijkstra's Algorithm

Koteswararao CH(1), Kunwar Singh(2), Anoop Kumar(3),


(1) VIT-AP University
(2) National Institute of Technology
(3) National Institute of Technology

Abstract


Data obliviousness is characterized by a consistent sequence of operations irrespective of input data and data-independent memory accesses, making it a suitable solution for users utilizing outsourced storage data services who aim to conceal their data access patterns. In ACM SIGSAC 2013, data-oblivious algorithms were introduced for breadth-first search, single-source single-destination (SSSD) algorithms, maximum flow, and minimum spanning tree. In this study, we present novel data-oblivious algorithms designed for depth-first search and single-source shortest path (Dijkstra’s algorithm). Our proposed data-oblivious algorithms demonstrate efficiency comparable to non-data-oblivious counterparts, particularly for graphs containing fewer than 1000 nodes. This research contributes to advancing data privacy in outsourced storage services by providing effective data-oblivious solutions for common graph algorithms.

Keywords


Oblivious execution; Secure computation; Graph algorithms

Full Text:

PDF

References


M. Blanton, A. Steele, and M. Alisagari, “Data-oblivious graph algorithms for secure computation and outsourcing,” Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security. ACM, May 08, 2013. doi: 10.1145/2484313.2484341.

M. Ajtai, “Oblivious RAMs without cryptogrpahic assumptions,” Proceedings of the forty-second ACM symposium on Theory of computing. ACM, Jun. 05, 2010. doi: 10.1145/1806689.1806716.

L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro, “Cache-oblivious priority queue and graph algorithm applications,” Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM, May 19, 2002. doi: 10.1145/509907.509950.

L. Arge, M. A. Bender, E. D. Demaine, B. Holland‐Minkley, and J. Ian Munro, “An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms,” SIAM Journal on Computing, vol. 36, no. 6. Society for Industrial & Applied Mathematics (SIAM), pp. 1672–1695, Jan. 2007. doi: 10.1137/s0097539703428324.

P. Williams, R. Sion, and B. Carbunar, “Building castles out of mud,” Proceedings of the 15th ACM conference on Computer and communications security. ACM, Oct. 27, 2008. doi: 10.1145/1455770.1455790.

B. Pinkas and T. Reinman, “Oblivious RAM Revisited,” Advances in Cryptology – CRYPTO 2010. Springer Berlin Heidelberg, pp. 502–519, 2010. doi: 10.1007/978-3-642-14623-7_27.

I. Damg˚ard, S. Meldgaard, J. B. Nielsen, Perfectly secure oblivious ram without random oracles, in: Theory of Cryptography Conference, Springer, 2011, pp. 144–163.

M. T. Goodrich and M. Mitzenmacher, “Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation,” Automata, Languages and Programming. Springer Berlin Heidelberg, pp. 576–587, 2011. doi: 10.1007/978-3-642-22012-8_46.

E. Kushilevitz, S. Lu, R. Ostrovsky, On the (in) security of hash-based oblivious ram and a new balancing scheme, in: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2012, pp. 143–156. doi: 10.1137/1.9781611973099.13

C. Gentry, Z. Ramzan, Single-database private information retrieval with constant communication rate, in: International Colloquium on Automata, Languages, and Programming, Springer, 2005, pp. 803–815. doi: 10.1007/11523468_65

H. Lipmaa, “An Oblivious Transfer Protocol with Log-Squared Communication,” Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 314–328, 2005. doi: 10.1007/11556992_23.

S. Wang, X. Ding, R. H. Deng, and F. Bao, “Private Information Retrieval Using Trusted Hardware,” Computer Security – ESORICS 2006. Springer Berlin Heidelberg, pp. 49–64, 2006. doi: 10.1007/11863908_4.

D. Eppstein, M. T. Goodrich, and R. Tamassia, “Privacy-preserving data-oblivious geometric algorithms for geographic data,” Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, Nov. 02, 2010. doi: 10.1145/1869790.1869796.

J. Brickell, V. Shmatikov, Privacy-preserving graph algorithms in the semi-honest model, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2005, pp. 236–252. doi: 10.1007/11593447_13

C. H. K. Rao and K. Singh, “Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model,” International Journal of Ad Hoc and Ubiquitous Computing, vol. 34, no. 1. Inderscience Publishers, p. 1, 2020. doi: 10.1504/ijahuc.2020.107501.

M. T. Goodrich, “Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data,” Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures. ACM, Jun. 04, 2011. doi: 10.1145/1989493.1989555.

M. T. Goodrich, O. Ohrimenko, R. Tamassia, Data-oblivious graph drawing model and algorithms, arXiv preprint arXiv:1209.0756 (2012).

G. S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh, “Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths,” Algorithm Theory - SWAT 2004. Springer Berlin Heidelberg, pp. 480–492, 2004. doi: 10.1007/978-3-540-27810-8_41.


Refbacks

  • There are currently no refbacks.


Journal of Computer Science and Engineering (JCSE)
ISSN 2721-0251 (online)
Published by : ICSE (Institute of Computer Sciences and Engineering)
Website : http://icsejournal.com/index.php/JCSE/
Email: jcse@icsejournal.com

Creative Commons License is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.