ALITHEIA: Towards practical verifiable graph processing

Yupeng Zhang, Charalampos Papamanthou, Jonathan Katz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a scenario in which a data owner outsources storage of a large graph to an untrusted server; the server performs computations on this graph in response to queries from a client (whether the data owner or others), and the goal is to ensure verifiability of the returned results. Existing work on verifiable computation (VC) would compile each graph computation to a circuit or a RAM program and then use generic techniques to produce a cryptographic proof of correctness for the result. Such an approach will incur large overhead, especially in the proof-computation time. In this work we address the above by designing, building, and evaluating ALITHEIA, a nearly practical VC system tailored for graph queries such as computing shortest paths, longest paths, and maximum flow. The underlying principle of ALITHEIA is to minimize the use of generic VC systems by leveraging various algorithmic techniques specific for graphs. This leads to both theoretical and practical improvements. Asymptotically, it improves the complexity of proof computation by at least a logarithmic factor. On the practical side, we show that ALITHEIA achieves significant performance improvements over current state-of-the-art (up to a 108× improvement in proof-computation time, and a 99.9% reduction in server storage), while scaling to 200,000-node graphs.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages856-867
Number of pages12
ISBN (Print)9781450329576
DOIs
StatePublished - Nov 3 2014
Externally publishedYes
Event21st ACM Conference on Computer and Communications Security, CCS 2014 - Scottsdale, United States
Duration: Nov 3 2014Nov 7 2014

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

Other21st ACM Conference on Computer and Communications Security, CCS 2014
Country/TerritoryUnited States
CityScottsdale
Period11/3/1411/7/14

Keywords

  • Cloud computing
  • Graph processing
  • Verifiable computation

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'ALITHEIA: Towards practical verifiable graph processing'. Together they form a unique fingerprint.

Cite this