TY - GEN
T1 - ALITHEIA
T2 - 21st ACM Conference on Computer and Communications Security, CCS 2014
AU - Zhang, Yupeng
AU - Papamanthou, Charalampos
AU - Katz, Jonathan
PY - 2014/11/3
Y1 - 2014/11/3
N2 - 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.
AB - 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.
KW - Cloud computing
KW - Graph processing
KW - Verifiable computation
UR - http://www.scopus.com/inward/record.url?scp=84910662329&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84910662329&partnerID=8YFLogxK
U2 - 10.1145/2660267.2660354
DO - 10.1145/2660267.2660354
M3 - Conference contribution
AN - SCOPUS:84910662329
SN - 9781450329576
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 856
EP - 867
BT - Proceedings of the ACM Conference on Computer and Communications Security
PB - Association for Computing Machinery
Y2 - 3 November 2014 through 7 November 2014
ER -