{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T23:53:57Z","timestamp":1726444437331},"reference-count":17,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"2","license":[{"start":{"date-parts":[[2017,4,1]],"date-time":"2017-04-01T00:00:00Z","timestamp":1491004800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We present the idea of <jats:italic>externally verifiable<\/jats:italic> oblivious RAM (ORAM). Our goal is to allow a client and server carrying out an ORAM protocol to have disputes adjudicated by a third party, allowing for the enforcement of penalties against an unreliable or malicious server. We give a security definition that guarantees protection not only against a malicious server but also against a client making false accusations. We then give modifications of the Path ORAM [15] and Ring ORAM [9] protocols that meet this security definition. These protocols both have the same asymptotic runtimes as the semi-honest original versions and require the external verifier to be involved only when the client or server deviates from the protocol. Finally, we implement externally verified ORAM, along with an automated cryptocurrency contract to use as the external verifier.<\/jats:p>","DOI":"10.1515\/popets-2017-0021","type":"journal-article","created":{"date-parts":[[2017,4,6]],"date-time":"2017-04-06T10:04:34Z","timestamp":1491473074000},"page":"149-171","source":"Crossref","is-referenced-by-count":3,"title":["Externally Verifiable Oblivious RAM"],"prefix":"10.56553","volume":"2017","author":[{"given":"Joshua","family":"Gancher","sequence":"first","affiliation":[{"name":"Cornell University, work done partly while at Reed College"}]},{"given":"Adam","family":"Groce","sequence":"additional","affiliation":[{"name":"Reed College"}]},{"given":"Alex","family":"Ledger","sequence":"additional","affiliation":[{"name":"MIT Lincoln Laboratory, work done while at Reed College"}]}],"member":"35752","published-online":{"date-parts":[[2017,4,4]]},"reference":[{"key":"2021040621502521162_j_popets-2017-0021_ref_001_w2aab2b8c10b1b7b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"[1] D. Apon, J. Katz, E. Shi, and A. Thiruvengadam. Verifiable oblivious storage. In Public-Key Cryptography\u2013PKC, pages 131\u2013148. Springer, 2014.","DOI":"10.1007\/978-3-642-54631-0_8"},{"key":"2021040621502521162_j_popets-2017-0021_ref_002_w2aab2b8c10b1b7b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"[2] N. Asokan, M. Schunter, and M. Waidner. Optimistic protocols for fair exchange. In Proceedings of the 4th ACM conference on Computer and communications security, pages 7\u201317. ACM, 1997.","DOI":"10.1145\/266420.266426"},{"key":"2021040621502521162_j_popets-2017-0021_ref_003_w2aab2b8c10b1b7b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"[3] N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures, pages 591\u2013606. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998.","DOI":"10.1007\/BFb0054156"},{"key":"2021040621502521162_j_popets-2017-0021_ref_004_w2aab2b8c10b1b7b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"[4] S. Devadas, M. van Dijk, C. W. Fletcher, L. Ren, E. Shi, and D. Wichs. Onion ORAM: A constant bandwidth blowup oblivious RAM. In IACR Theory of Cryptography Conference\u2013TCC, pages 145\u2013174. Springer, 2016.","DOI":"10.1007\/978-3-662-49099-0_6"},{"key":"2021040621502521162_j_popets-2017-0021_ref_005_w2aab2b8c10b1b7b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[5] O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In Symposium on Theory of Computing\u2013STOC, pages 182\u2013194. ACM, 1987.","DOI":"10.1145\/28395.28416"},{"key":"2021040621502521162_j_popets-2017-0021_ref_006_w2aab2b8c10b1b7b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[6] O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 43(3):431\u2013473, May 1996.","DOI":"10.1145\/233551.233553"},{"key":"2021040621502521162_j_popets-2017-0021_ref_007_w2aab2b8c10b1b7b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"[7] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. University of Maryland and Cornell University, 2015.","DOI":"10.1109\/SP.2016.55"},{"key":"2021040621502521162_j_popets-2017-0021_ref_008_w2aab2b8c10b1b7b1ab1ab8Aa","doi-asserted-by":"crossref","unstructured":"[8] R. Ostrovsky. Efficient computation on oblivious RAMs. In Symposium on Theory of Computing\u2013STOC, pages 514\u2013523. ACM, 1990.","DOI":"10.1145\/100216.100289"},{"key":"2021040621502521162_j_popets-2017-0021_ref_009_w2aab2b8c10b1b7b1ab1ab9Aa","unstructured":"[9] L. Ren, C. Fletcher, A. Kwon, E. Stefanov, E. Shi, M. Van Dijk, and S. Devadas. Constants count: practical improvements to oblivious RAM. In USENIX Security Symposium, pages 415\u2013430, 2015."},{"key":"2021040621502521162_j_popets-2017-0021_ref_010_w2aab2b8c10b1b7b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"[10] L. Ren, C. W. Fletcher, X. Yu, M. van Dijk, and S. Devadas. Integrity verification for path oblivious-RAM. In High Performance Extreme Computing Conference\u2013HPEC, pages 1\u20136. IEEE, 2013.","DOI":"10.1109\/HPEC.2013.6670339"},{"key":"2021040621502521162_j_popets-2017-0021_ref_011_w2aab2b8c10b1b7b1ab1ac11Aa","unstructured":"[11] M. A. Shah, R. Swaminathan, and M. Baker. Privacy-preserving audit and extraction of digital contents. Technical report, HP Lab No. HPL-2008-32, 25 April, 2008."},{"key":"2021040621502521162_j_popets-2017-0021_ref_012_w2aab2b8c10b1b7b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"[12] E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li. Oblivious RAM with O((log N)3) worst-case cost. In Advances in Cryptology\u2013ASIACRYPT, pages 197\u2013214. Springer, 2011.","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"2021040621502521162_j_popets-2017-0021_ref_013_w2aab2b8c10b1b7b1ab1ac13Aa","unstructured":"[13] E. G. Sirer. Thoughts on the dao hack. http:\/\/hackingdistributed.com\/2016\/06\/17\/thoughts-on-the-dao-hack\/, 2016."},{"key":"2021040621502521162_j_popets-2017-0021_ref_014_w2aab2b8c10b1b7b1ab1ac14Aa","doi-asserted-by":"crossref","unstructured":"[14] M. Stadler. Publicly verifiable secret sharing. In Advances in Cryptology\u2014EUROCRYPT, pages 190\u2013199. Springer, 1996.","DOI":"10.1007\/3-540-68339-9_17"},{"key":"2021040621502521162_j_popets-2017-0021_ref_015_w2aab2b8c10b1b7b1ab1ac15Aa","doi-asserted-by":"crossref","unstructured":"[15] E. Stefanov, M. Van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas. Path ORAM: An extremely simple oblivious RAM protocol. In Computer & Communications Security\u2013CCS, pages 299\u2013310. ACM, 2013.","DOI":"10.1145\/2508859.2516660"},{"key":"2021040621502521162_j_popets-2017-0021_ref_016_w2aab2b8c10b1b7b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"[16] X. Wang, H. Chan, and E. Shi. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. In Computer & Communications Security\u2013CCS, pages 850\u2013861. ACM, 2015.","DOI":"10.1145\/2810103.2813634"},{"key":"2021040621502521162_j_popets-2017-0021_ref_017_w2aab2b8c10b1b7b1ab1ac17Aa","unstructured":"[17] G. Wood. Ethereum: A secure decentralised generalised transaction ledger. Technical report, Ethereum Project Yellow Paper, 2014."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2017\/2\/article-p149.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2017-0021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:29:42Z","timestamp":1658334582000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2017\/popets-2017-0021.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,1]]},"references-count":17,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,4,4]]},"published-print":{"date-parts":[[2017,4,1]]}},"alternative-id":["10.1515\/popets-2017-0021"],"URL":"https:\/\/doi.org\/10.1515\/popets-2017-0021","relation":{},"ISSN":["2299-0984"],"issn-type":[{"type":"electronic","value":"2299-0984"}],"subject":[],"published":{"date-parts":[[2017,4,1]]}}}