Data-oblivious graph algorithms for secure computation and outsourcing

Marina Blanton; Aaron Steele; Mehrdad Alisagari

doi:10.1145/2484313.2484341

Data-oblivious graph algorithms for secure computation and outsourcing

Marina Blanton
, Aaron Steele
, Mehrdad Alisagari

Department of Computer Science and Engineering

University of Notre Dame

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

81 Scopus citations

Abstract

This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.

Original language	English
Title of host publication	ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security
Pages	207-218
Number of pages	12
DOIs	https://doi.org/10.1145/2484313.2484341
State	Published - 2013
Event	8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013 - Hangzhou, China Duration: May 8 2013 → May 10 2013

Publication series

Name	ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security

Conference

Conference	8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013
Country/Territory	China
City	Hangzhou
Period	05/8/13 → 05/10/13

Keywords

graph algorithms
oblivious execution
secure computation

Access to Document

10.1145/2484313.2484341

Cite this

Blanton, M., Steele, A., & Alisagari, M. (2013). Data-oblivious graph algorithms for secure computation and outsourcing. In ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security (pp. 207-218). (ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security). https://doi.org/10.1145/2484313.2484341

Blanton, Marina ; Steele, Aaron ; Alisagari, Mehrdad. / Data-oblivious graph algorithms for secure computation and outsourcing. ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013. pp. 207-218 (ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security).

@inproceedings{996d2ed24ae14f93ab8a0bdb83a66c19,

title = "Data-oblivious graph algorithms for secure computation and outsourcing",

abstract = "This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.",

keywords = "graph algorithms, oblivious execution, secure computation",

author = "Marina Blanton and Aaron Steele and Mehrdad Alisagari",

year = "2013",

doi = "10.1145/2484313.2484341",

language = "English",

isbn = "9781450317672",

series = "ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security",

pages = "207--218",

booktitle = "ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security",

note = "8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013 ; Conference date: 08-05-2013 Through 10-05-2013",

}

Blanton, M, Steele, A & Alisagari, M 2013, Data-oblivious graph algorithms for secure computation and outsourcing. in ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, pp. 207-218, 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013, Hangzhou, China, 05/8/13. https://doi.org/10.1145/2484313.2484341

Data-oblivious graph algorithms for secure computation and outsourcing. / Blanton, Marina; Steele, Aaron; Alisagari, Mehrdad.
ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013. p. 207-218 (ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Data-oblivious graph algorithms for secure computation and outsourcing

AU - Blanton, Marina

AU - Steele, Aaron

AU - Alisagari, Mehrdad

PY - 2013

Y1 - 2013

N2 - This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.

AB - This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.

KW - graph algorithms

KW - oblivious execution

KW - secure computation

UR - https://www.scopus.com/pages/publications/84877998963

U2 - 10.1145/2484313.2484341

DO - 10.1145/2484313.2484341

M3 - Conference contribution

AN - SCOPUS:84877998963

SN - 9781450317672

T3 - ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security

SP - 207

EP - 218

BT - ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security

T2 - 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013

Y2 - 8 May 2013 through 10 May 2013

ER -

Blanton M, Steele A, Alisagari M. Data-oblivious graph algorithms for secure computation and outsourcing. In ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013. p. 207-218. (ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security). doi: 10.1145/2484313.2484341

Data-oblivious graph algorithms for secure computation and outsourcing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this