{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T17:17:54Z","timestamp":1787937474285,"version":"build-2784847793"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2023-03448"],"award-info":[{"award-number":["2023-03448"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["05849"],"award-info":[{"award-number":["05849"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"IRC","award":["537591"],"award-info":[{"award-number":["537591"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>We present Waffle, a datastore that protects an application's data access patterns from a passive persistent adversary. Waffle achieves this without prior knowledge of the input data access distribution, making it the first of its kind to adaptively handle input sequences under a passive persistent adversary. Waffle maintains a constant bandwidth and client-side storage overhead, which can be adjusted to suit the application owner's preferences. This flexibility allows the owner to fine-tune system parameters and strike a balance between security and performance. Our evaluation, utilizing the Yahoo! Cloud Serving Benchmark (YCSB) benchmark and Redis as the backend storage, demonstrates promising results. The insecure baseline outperforms Waffle by a mere 5-6x, whereas Waffle outperforms Pancake-a state-of-the-art oblivious datastore under passive persistent adversaries-by 45-57%, and a concurrent ORAM system, TaoStore, by 102x.<\/jats:p>","DOI":"10.1145\/3626760","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-25","source":"Crossref","is-referenced-by-count":10,"title":["Waffle: An Online Oblivious Datastore for Protecting Data Access Patterns"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-1341-0252","authenticated-orcid":false,"given":"Sujaya","family":"Maiyya","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1762-7253","authenticated-orcid":false,"given":"Sharath Chandra","family":"Vemula","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0215-9539","authenticated-orcid":false,"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4692-3268","authenticated-orcid":false,"given":"Amr","family":"El Abbadi","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4288-2286","authenticated-orcid":false,"given":"Florian","family":"Kerschbaum","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813649"},{"key":"e_1_2_1_3_1","volume-title":"Revisiting leakage abuse attacks. Cryptology ePrint Archive","author":"Blackstone L.","year":"2019","unstructured":"Blackstone, L., Kamara, S., and Moataz, T. Revisiting leakage abuse attacks. Cryptology ePrint Archive (2019)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840761"},{"key":"e_1_2_1_5_1","first-page":"49","volume-title":"2013 USENIX Annual Technical Conference (USENIXATC 13)","author":"Bronson N.","year":"2013","unstructured":"Bronson, N., Amsden, Z., Cabrera, G., Chakka, P., Dimov, P., Ding, H., Ferris, J., Giardullo, A., Kulkarni, S., Li, H., et al. Tao: Facebook's distributed data store for the social graph. In 2013 USENIX Annual Technical Conference (USENIXATC 13) (2013), pp. 49--60."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64375-1_16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813700"},{"key":"e_1_2_1_8_1","volume-title":"Concuroram: High-throughput stateless parallel multi-client oram. arXiv preprint arXiv:1811.04366","author":"Chakraborti A.","year":"2018","unstructured":"Chakraborti, A., and Sion, R. Concuroram: High-throughput stateless parallel multi-client oram. arXiv preprint arXiv:1811.04366 (2018)."},{"key":"e_1_2_1_9_1","volume-title":"https:\/\/bit.ly\/3ZdCzpt. Accessed","author":"Cloud Adoption Statistics","year":"2023","unstructured":"Cloud Adoption Statistics. https:\/\/bit.ly\/3ZdCzpt. Accessed Feb 10, 2023."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_11_1","first-page":"727","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Crooks N.","year":"2018","unstructured":"Crooks, N., Burke, M., Cecchetti, E., Harel, S., Agarwal, R., and Alvisi, L. Obladi: Oblivious serializable transactions in the cloud. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18) (2018), pp. 727--743."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483562"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_14_1","first-page":"2433","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Demertzis I.","year":"2020","unstructured":"Demertzis, I., Papadopoulos, D., Papamanthou, C., and Shintre, S. Seal: Attack mitigation for encrypted databases via adjustable leakage. In 29th USENIX Security Symposium (USENIX Security 20) (2020), pp. 2433--2450."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_17_1","first-page":"2451","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Grubbs P.","year":"2020","unstructured":"Grubbs, P., Khandelwal, A., Lacharit\u00e9, M.-S., Brown, L., Li, L., Agarwal, R., and Ristenpart, T. Pancake: Frequency smoothing for encrypted data stores. In 29th USENIX Security Symposium (USENIX Security 20) (2020), pp. 2451--2468."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243864"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00030"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3363210"},{"key":"e_1_2_1_21_1","volume-title":"https:\/\/bit.ly\/3ZyCWdI. Accessed","author":"Health Care Cloud Computing","year":"2023","unstructured":"Health Care Cloud Computing Trends. https:\/\/bit.ly\/3ZyCWdI. Accessed Feb 10, 2023."},{"key":"e_1_2_1_22_1","volume-title":"Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3","author":"Herlihy M. P.","year":"1990","unstructured":"Herlihy, M. P., and Wing, J. M. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463--492."},{"key":"e_1_2_1_23_1","first-page":"12","volume-title":"Ndss","volume":"20","author":"Islam M. S.","year":"2012","unstructured":"Islam, M. S., Kuzu, M., and Kantarcioglu, M. Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In Ndss (2012), vol. 20, Citeseer, p. 12."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00015"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_2_1_27_1","volume-title":"A note on the optimality of frequency analysis vs. lp-optimization. Cryptology ePrint Archive","author":"Lacharit\u00e9 M.-S.","year":"2015","unstructured":"Lacharit\u00e9, M.-S., and Paterson, K. G. A note on the optimality of frequency analysis vs. lp-optimization. Cryptology ePrint Archive (2015)."},{"key":"e_1_2_1_28_1","volume-title":"Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data. Cryptology ePrint Archive","author":"Lacharit\u00e9 M.-S.","year":"2017","unstructured":"Lacharit\u00e9, M.-S., and Paterson, K. G. Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data. Cryptology ePrint Archive (2017)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.68"},{"key":"e_1_2_1_31_1","first-page":"523","volume-title":"Yes, there is an oblivious ram lower bound! In Annual International Cryptology Conference","author":"Larsen K. G.","year":"2018","unstructured":"Larsen, K. G., and Nielsen, J. B. Yes, there is an oblivious ram lower bound! In Annual International Cryptology Conference (2018), Springer, pp. 523--542."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2017.28"},{"key":"e_1_2_1_33_1","volume-title":"Grid search, random search, genetic algorithm: a big comparison for nas. arXiv preprint arXiv:1912.06059","author":"Liashchynskyi P.","year":"2019","unstructured":"Liashchynskyi, P., and Liashchynskyi, P. Grid search, random search, genetic algorithm: a big comparison for nas. arXiv preprint arXiv:1912.06059 (2019)."},{"key":"e_1_2_1_34_1","first-page":"3665","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Maiyya S.","year":"2022","unstructured":"Maiyya, S., Ibrahim, S., Scarberry, C., Agrawal, D., Abbadi, A. E., Lin, H., Tessaro, S., and Zakhary, V. QuORAM: A Quorum-Replicated fault tolerant ORAM datastore. In 31st USENIX Security Symposium (USENIX Security 22) (Boston, MA, Aug. 2022), USENIX Association, pp. 3665--3682."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749455"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813651"},{"key":"e_1_2_1_37_1","first-page":"127","volume-title":"USENIX Security Symposium","author":"Oya S.","year":"2021","unstructured":"Oya, S., and Kerschbaum, F. Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption. In USENIX Security Symposium (2021), pp. 127--142."},{"key":"e_1_2_1_38_1","first-page":"2407","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Oya S.","year":"2022","unstructured":"Oya, S., and Kerschbaum, F. Ihop: Improved statistical query recovery against searchable symmetric encryption through quadratic optimization. In 31st USENIX Security Symposium (USENIX Security 22) (2022), pp. 2407--2424."},{"key":"e_1_2_1_39_1","first-page":"587","volume-title":"OSDI","volume":"16","author":"Papadimitriou A.","year":"2016","unstructured":"Papadimitriou, A., Bhagwan, R., Chandran, N., Ramjee, R., Haeberlen, A., Singh, H., Modi, A., and Badrinarayanan, S. Big data analytics over encrypted datasets with seabed. In OSDI (2016), vol. 16, pp. 587--602."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319695"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_14"},{"key":"e_1_2_1_42_1","volume-title":"Power law distributions in information retrieval. ACM Transactions on Information Systems (TOIS) 34, 2","author":"Petersen C.","year":"2016","unstructured":"Petersen, C., Simonsen, J. G., and Lioma, C. Power law distributions in information retrieval. ACM Transactions on Information Systems (TOIS) 34, 2 (2016), 1--37."},{"key":"e_1_2_1_43_1","volume-title":"Arx: an encrypted database using semantically secure encryption. Cryptology ePrint Archive","author":"Poddar R.","year":"2016","unstructured":"Poddar, R., Boelter, T., and Popa, R. A. Arx: an encrypted database using semantically secure encryption. Cryptology ePrint Archive (2016)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP48549.2020.00030"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_46_1","volume-title":"https:\/\/redis.io\/. Accessed","author":"Redis","year":"2023","unstructured":"Redis. https:\/\/redis.io\/. Accessed Feb 10, 2023."},{"key":"e_1_2_1_47_1","first-page":"415","volume-title":"24th USENIX Security Symposium (USENIX Security 15)","author":"Ren L.","year":"2015","unstructured":"Ren, L., Fletcher, C., Kwon, A., Stefanov, E., Shi, E., Van Dijk, M., and Devadas, S. Constants count: Practical improvements to oblivious ram. In 24th USENIX Security Symposium (USENIX Security 15) (2015), pp. 415--430."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.20"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3433210.3453103"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.25"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_2_1_52_1","volume-title":"Accessed","author":"The Infrastructure Behind Twitter","year":"2023","unstructured":"The Infrastructure Behind Twitter: Scale. https:\/\/bit.ly\/3KJR7J1. Accessed Feb 10, 2023."},{"key":"e_1_2_1_53_1","volume-title":"https:\/\/datatracker.ietf.org\/doc\/html\/rfc5246. Accessed","author":"TLS.","year":"2023","unstructured":"TLS. https:\/\/datatracker.ietf.org\/doc\/html\/rfc5246. Accessed July 14, 2023."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-021-09392-1"},{"key":"e_1_2_1_55_1","volume-title":"https:\/\/dumps.wikimedia.org\/other\/clickstream\/. Accessed","author":"Wikipedia ClickStream Dataset","year":"2023","unstructured":"Wikipedia ClickStream Dataset. https:\/\/dumps.wikimedia.org\/other\/clickstream\/. Accessed July 14, 2023."},{"key":"e_1_2_1_56_1","first-page":"707","volume-title":"USENIX Security Symposium","volume":"2016","author":"Zhang Y.","year":"2016","unstructured":"Zhang, Y., Katz, J., and Papamanthou, C. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In USENIX Security Symposium (2016), vol. 2016, pp. 707--720."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:01:36Z","timestamp":1755867696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626760"],"URL":"https:\/\/doi.org\/10.1145\/3626760","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}