{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T20:31:55Z","timestamp":1771705915157,"version":"3.50.1"},"reference-count":53,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"HPI Research Center in Machine Learning and Data Science at UC Irvine"},{"name":"NSF Grants","award":["2032525, 1545071, 1527536, 1952247, 2008993, 2133391, and 2245372"],"award-info":[{"award-number":["2032525, 1545071, 1527536, 1952247, 2008993, 2133391, and 2245372"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>This paper addresses volume leakage (i.e., leakage of the number of records in the answer set) when processing keyword queries in encrypted key-value (KV) datasets. Volume leakage, coupled with prior knowledge about data distribution and\/or previously executed queries, can reveal both ciphertexts and current user queries. We develop a solution to prevent volume leakage, entitled Veil, that partitions the dataset by randomly mapping keys to a set of equi-sized buckets. Veil provides a tunable mechanism for data owners to explore a trade-off between storage and communication overheads. To make buckets indistinguishable to the adversary, Veil uses a novel padding strategy that allow buckets to overlap, reducing the need to add fake records. Both theoretical and experimental results show Veil to significantly outperform existing state-of-the-art.<\/jats:p>","DOI":"10.1145\/3626759","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-27","source":"Crossref","is-referenced-by-count":6,"title":["Veil: A Storage and Communication Efficient Volume-Hiding Algorithm"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2788-8834","authenticated-orcid":false,"given":"Shanshan","family":"Han","sequence":"first","affiliation":[{"name":"University of California, Irvine, Irvine, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0997-4149","authenticated-orcid":false,"given":"Vishal","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1667-5435","authenticated-orcid":false,"given":"Sharad","family":"Mehrotra","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1339-5481","authenticated-orcid":false,"given":"Shantanu","family":"Sharma","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology, Newark, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ghous Amjad Sarvar Patel Giuseppe Persiano Kevin Yeo and Moti Yung. 2021. Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption. (2021)."},{"key":"e_1_2_1_2_1","volume-title":"SMCQL: secure querying for federated databases. arXiv preprint arXiv:1606.06808","author":"Bater Johes","year":"2016","unstructured":"Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel Kho, and Jennie Rogers. 2016. SMCQL: secure querying for federated databases. arXiv preprint arXiv:1606.06808 (2016)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324309"},{"key":"e_1_2_1_4_1","volume-title":"Marcel-Cua tua lin Rocs u, and Michael Steiner","author":"Cash David","year":"2014","unstructured":"David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cua tua lin Rocs u, and Michael Steiner. 2014. Dynamic searchable encryption in very-large databases: Data structures and implementation. Cryptology ePrint Archive (2014)."},{"key":"e_1_2_1_5_1","volume-title":"Sqoram: Read-optimized sequential write-only oblivious RAM. arXiv preprint arXiv:1707.01211","author":"Chakraborti Anrin","year":"2017","unstructured":"Anrin Chakraborti and Radu Sion. 2017. Sqoram: Read-optimized sequential write-only oblivious RAM. arXiv preprint arXiv:1707.01211 (2017)."},{"key":"e_1_2_1_6_1","volume-title":"ConcurORAM: High-throughput stateless parallel multi-client ORAM. arXiv preprint arXiv:1811.04366","author":"Chakraborti Anrin","year":"2018","unstructured":"Anrin Chakraborti and Radu Sion. 2018. ConcurORAM: High-throughput stateless parallel multi-client ORAM. arXiv preprint arXiv:1811.04366 (2018)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517868"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"e_1_2_1_9_1","volume-title":"Differentially Private Access Patterns for Searchable Symmetric Encryption. IEEE INFOCOM 2018 - IEEE Conference on Computer Communications","author":"Chen Guoxing","year":"2018","unstructured":"Guoxing Chen, Ten-Hwang Lai, Michael K. Reiter, and Yinqian Zhang. 2018. Differentially Private Access Patterns for Searchable Symmetric Encryption. IEEE INFOCOM 2018 - IEEE Conference on Computer Communications (2018), 810--818."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32627-1_10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_12_1","unstructured":"Joan Daemen and Vincent Rijmen. 1999. AES proposal: Rijndael. (1999)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978379"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings, Part II 20","author":"Faber Sky","year":"2015","unstructured":"Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel Rosu, and Michael Steiner. 2015. Rich queries on encrypted data: Beyond exact matches. In Computer Security--ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21--25, 2015, Proceedings, Part II 20. Springer, 123--145."},{"key":"e_1_2_1_15_1","volume-title":"Cryptography and computer privacy. Scientific american","author":"Feistel Horst","year":"1973","unstructured":"Horst Feistel. 1973. Cryptography and computer privacy. Scientific american, Vol. 228, 5 (1973), 15--23."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_20"},{"key":"e_1_2_1_17_1","volume-title":"Structured Encryption and Dynamic Leakage Suppression. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 370--396","author":"George Marilyn","year":"2021","unstructured":"Marilyn George, Seny Kamara, and Tarik Moataz. 2021. Structured Encryption and Dynamic Leakage Suppression. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 370--396."},{"key":"e_1_2_1_18_1","volume-title":"Secure indexes. Cryptology ePrint Archive","author":"Goh Eu-Jin","year":"2003","unstructured":"Eu-Jin Goh. 2003. Secure indexes. Cryptology ePrint Archive (2003)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3363210"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS.2018.8624187"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC40277.2020.9148612"},{"key":"e_1_2_1_25_1","volume-title":"Attack and Mitigation. In Network and Distributed System Security Symposium.","author":"Islam Mohammad Saiful","year":"2012","unstructured":"Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In Network and Distributed System Security Symposium."},{"key":"e_1_2_1_26_1","volume-title":"Near-optimal bin packing algorithms. Ph.,D. Dissertation","author":"Johnson David S","unstructured":"David S Johnson. 1973. Near-optimal bin packing algorithms. Ph.,D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_1_27_1","volume-title":"Jutla and Sikhar Patranabis","author":"Charanjit","year":"2021","unstructured":"Charanjit S. Jutla and Sikhar Patranabis. 2021. Efficient Searchable Symmetric Encryption for Join Queries. In IACR Cryptology ePrint Archive."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17656-3_7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_12"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382298"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978376"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100289"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.30"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354213"},{"key":"e_1_2_1_38_1","volume-title":"On the secure hash algorithm family. Cryptography in context","author":"Penard Wouter","year":"2008","unstructured":"Wouter Penard and Tim van Werkhoven. 2008. On the secure hash algorithm family. Cryptography in context (2008), 1--18."},{"key":"e_1_2_1_39_1","first-page":"591","article-title":"Arx: A Strongly Encrypted Database System","volume":"2016","author":"Poddar Rishabh","year":"2016","unstructured":"Rishabh Poddar, Tobias Boelter, and Raluca Ada Popa. 2016. Arx: A Strongly Encrypted Database System. IACR Cryptol. ePrint Arch., Vol. 2016 (2016), 591.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_2_1_40_1","volume-title":"USENIX Security Symposium. 2129--2146","author":"Poddar Rishabh","year":"2021","unstructured":"Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics.. In USENIX Security Symposium. 2129--2146."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP48549.2020.00030"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS47774.2020.00014"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574248"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.2000.848445"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177872"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559345"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02744-5_9"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00062"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384942.3406869"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3052973.3052977"},{"key":"e_1_2_1_53_1","first-page":"1283","article-title":"Enabling encrypted rich queries in distributed key-value stores","volume":"30","author":"Yuan Xingliang","year":"2018","unstructured":"Xingliang Yuan, Xinyu Wang, Cong Wang, Baochun Li, Xiaohua Jia, et al. 2018. Enabling encrypted rich queries in distributed key-value stores. IEEE Transactions on Parallel and Distributed Systems, Vol. 30, 6 (2018), 1283--1297.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:03:11Z","timestamp":1755867791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626759"],"URL":"https:\/\/doi.org\/10.1145\/3626759","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}