{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:19:15Z","timestamp":1783009155202,"version":"3.54.5"},"reference-count":0,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T00:00:00Z","timestamp":1696118400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["PoPETs"],"abstract":"<jats:p>In this work, we present the first database reconstruction attacks against response-hiding private range search schemes on encrypted databases of arbitrary dimensions. Falzon et al. (VLDB 2022) present a number of range-supporting schemes on arbitrary dimensions exhibiting different security and efficiency trade-offs. Additionally, they characterize a form of leakage, structure pattern leakage, also present in many one-dimensional schemes e.g., Demertzis et al. (SIGMOD 2016) and Faber et al. (ESORICS 2015). We present the first systematic study of this leakage and attack a broad collection of schemes, including schemes that allow the responses to contain false-positives (often considered the gold standard in security). We characterize the information theoretic limitations of a passive persistent adversary.  Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.<\/jats:p>","DOI":"10.56553\/popets-2023-0106","type":"journal-article","created":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T20:41:11Z","timestamp":1691095271000},"page":"204-223","source":"Crossref","is-referenced-by-count":10,"title":["Attacks on Encrypted Response-Hiding Range Search Schemes in Multiple Dimensions"],"prefix":"10.56553","volume":"2023","author":[{"given":"Evangelia Anna","family":"Markatou","sequence":"first","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesca","family":"Falzon","sequence":"additional","affiliation":[{"name":"Brown University, University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zachary","family":"Espiritu","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"35752","published-online":{"date-parts":[[2023,10]]},"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"deposited":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T20:41:44Z","timestamp":1691095304000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2023\/popets-2023-0106.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["10.56553\/popets-2023-0106"],"URL":"https:\/\/doi.org\/10.56553\/popets-2023-0106","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10]]}}}