{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:12Z","timestamp":1750221252489,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1514261, 1652259"],"award-info":[{"award-number":["1514261, 1652259"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            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\n            <jats:italic>verifiability<\/jats:italic>\n            of the returned results. Applying generic verifiable computation\u00a0(VC) would involve compiling each graph computation to a circuit or a RAM program and would incur large overhead, especially in the proof-computation time.\n          <\/jats:p>\n          <jats:p>\n            In this work, we address the above by designing, building, and evaluating A\n            <jats:sc>litheia<\/jats:sc>\n            , a VC system tailored for graph queries such as computing shortest paths, longest paths, and maximum flows. The underlying principle of A\n            <jats:sc>litheia<\/jats:sc>\n            \u00a0is to minimize the use of generic VC techniques by leveraging various algorithmic approaches 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, our system achieves significant performance improvements over current state-of-the-art VC systems (up to a 10-orders-of-magnitude improvement in proof-computation time, and a 99.9% reduction in server storage), while scaling to 200,000-node graphs.\n          <\/jats:p>","DOI":"10.1145\/3233181","type":"journal-article","created":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T12:15:55Z","timestamp":1538396155000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Verifiable Graph Processing"],"prefix":"10.1145","volume":"21","author":[{"given":"Yupeng","family":"Zhang","sequence":"first","affiliation":[{"name":"ECE Department, University of Maryland, USA"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[{"name":"ECE Department, University of Maryland, USA"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016. openSSL library. Retrieved from https:\/\/www.openssl.org\/.  2016. openSSL library. Retrieved from https:\/\/www.openssl.org\/."},{"key":"e_1_2_1_2_1","unstructured":"2017. Ate pairing. Retrievved from https:\/\/github.com\/herumi\/ate-pairing.  2017. Ate pairing. Retrievved from https:\/\/github.com\/herumi\/ate-pairing."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134104"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/648025.744371"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56617-7_19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the USENIX Security Symposium. 781--796","author":"Ben-Sasson Eli","year":"2014","unstructured":"Eli Ben-Sasson , Alessandro Chiesa , Eran Tromer , and Madars Virza . 2014 . Succinct non-interactive zero knowledge for a von Neumann architecture . In Proceedings of the USENIX Security Symposium. 781--796 . Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct non-interactive zero knowledge for a von Neumann architecture. In Proceedings of the USENIX Security Symposium. 781--796."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0221-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591859"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_10"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522733"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Dario Catalano and Dario Fiore. 2013. Vector commitments and their applications. In Public Key Cryptography. 55--72.  Dario Catalano and Dario Fiore. 2013. Vector commitments and their applications. In Public Key Cryptography. 55--72.","DOI":"10.1007\/978-3-642-36362-7_5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_13"},{"volume-title":"Proceedings of the Annual Conference on Advances in Cryptology (CRYPTO\u201910)","author":"Chung Kai-Min","key":"e_1_2_1_17_1","unstructured":"Kai-Min Chung , Yael Tauman Kalai , and Salil P. Vadhan . 2010. Improved delegation of computation using fully homomorphic encryption . In Proceedings of the Annual Conference on Advances in Cryptology (CRYPTO\u201910) . 483--501. Kai-Min Chung, Yael Tauman Kalai, and Salil P. Vadhan. 2010. Improved delegation of computation using fully homomorphic encryption. In Proceedings of the Annual Conference on Advances in Cryptology (CRYPTO\u201910). 483--501."},{"key":"e_1_2_1_18_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.23"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45611-8_28"},{"volume-title":"9th DIMACS Implementation Challenge\u2014Shortest Paths.","author":"DIMACS.","key":"e_1_2_1_21_1","unstructured":"DIMACS. 2006. 9th DIMACS Implementation Challenge\u2014Shortest Paths. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/. DIMACS. 2006. 9th DIMACS Implementation Challenge\u2014Shortest Paths. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978368"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2957318"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118748.3118939"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the USENIX Security Symposium","author":"Kosba Ahmed E.","year":"2014","unstructured":"Ahmed E. Kosba , Dimitrios Papadopoulos , Charalampos Papamanthou , Mahmoud F. Sayed , Elaine Shi , and Nikos Triandopoulos . 2014 . TRUESET: Faster verifiable set computations . In Proceedings of the USENIX Security Symposium 2014. 765--780. Ahmed E. Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, Mahmoud F. Sayed, Elaine Shi, and Nikos Triandopoulos. 2014. TRUESET: Faster verifiable set computations. In Proceedings of the USENIX Security Symposium 2014. 765--780."},{"key":"e_1_2_1_30_1","unstructured":"LEDA. 2017. LEDA library. Retrieved from http:\/\/www.algorithmic-solutions.com\/leda\/index.htm.  LEDA. 2017. LEDA library. Retrieved from http:\/\/www.algorithmic-solutions.com\/leda\/index.htm."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42033-7_3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.09.009"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_22"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1785001.1785003"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033045"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.47"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465359"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Network and Distributed System Security Symposium","volume":"1","author":"Setty Srinath T. V.","year":"2012","unstructured":"Srinath T. V. Setty , Richard McPherson , Andrew J. Blumberg , and Michael Walfish . 2012 . Making argument systems for outsourced computation practical (sometimes) . In Proceedings of the Network and Distributed System Security Symposium , Vol. 1 . 17. Srinath T. V. Setty, Richard McPherson, Andrew J. Blumberg, and Michael Walfish. 2012. Making argument systems for outsourced computation practical (sometimes). In Proceedings of the Network and Distributed System Security Symposium, Vol. 1. 17."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_2"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management.","author":"Tamassia Roberto","year":"2010","unstructured":"Roberto Tamassia and Nikos Triandopoulos . 2010 . Certification and authentication of data structures . In Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management. Roberto Tamassia and Nikos Triandopoulos. 2010. Certification and authentication of data structures. In Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.48"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2015.23097"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447914"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.43"},{"volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (S8P\u201918)","author":"Zhang Y.","key":"e_1_2_1_47_1","unstructured":"Y. Zhang , D. Genkin , J. Katz , D. Papadopoulos , and C. Papamanthou . 2018. vRAM: Faster verifiable RAM with program-independent preprocessing . In Proceedings of the IEEE Symposium on Security and Privacy (S8P\u201918) . 203--220. Y. Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou. 2018. vRAM: Faster verifiable RAM with program-independent preprocessing. In Proceedings of the IEEE Symposium on Security and Privacy (S8P\u201918). 203--220."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP.2017.35"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660354"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233181","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3233181","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3233181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:55Z","timestamp":1750212475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3233181"],"URL":"https:\/\/doi.org\/10.1145\/3233181","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"type":"print","value":"2471-2566"},{"type":"electronic","value":"2471-2574"}],"subject":[],"published":{"date-parts":[[2018,10]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}