{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:19:14Z","timestamp":1783009154853,"version":"3.54.5"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>This work addresses expressive queries over encrypted data by presenting the first systematic study of multi-attribute range search on a symmetrically encrypted database outsourced to an honest-but-curious server. Prior work includes a thorough analysis of single-attribute range search schemes (e.g. Demertzis et al. 2016) and a proposed high-level approach for multi-attribute schemes (De Capitani di Vimercati et al. 2021). We first introduce a flexible framework for building secure range search schemes over multiple attributes (dimensions) by adapting a broad class of geometric search data structures to operate on encrypted data. Our framework encompasses widely used data structures such as multi-dimensional range trees and quadtrees, and has strong security properties that we formally prove. We then develop six concrete highly parallelizable range search schemes within our framework that offer a sliding scale of efficiency and security tradeoffs to suit the needs of the application. We evaluate our schemes with a formal complexity and security analysis, a prototype implementation, and an experimental evaluation on real-world datasets.<\/jats:p>","DOI":"10.14778\/3574245.3574247","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"587-600","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Range Search over Encrypted Multi-Attribute Data"],"prefix":"10.14778","volume":"16","author":[{"given":"Francesca","family":"Falzon","sequence":"first","affiliation":[{"name":"Brown University and University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Evangelia Anna","family":"Markatou","sequence":"additional","affiliation":[{"name":"Brown University"}],"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":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 12 pages.","author":"Agrawal R.","unstructured":"R. Agrawal , J. Kiernan , R. Srikant , and Y. Xu . 2004. Order Preserving Encryption for Numeric Data . In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 12 pages. R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. 2004. Order Preserving Encryption for Numeric Data. In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 12 pages."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007608"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236217"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2262--2276","author":"Bogatov Dmytro","year":"2021","unstructured":"Dmytro Bogatov , Georgios Kellaris , George Kollios , Kobbi Nissim , and Adam O'Neill . 2021 . \u03f5psolute: Efficiently Querying Databases While Providing Differential Privacy . In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2262--2276 . Dmytro Bogatov, Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2021. \u03f5psolute: Efficiently Querying Databases While Providing Differential Privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2262--2276."},{"key":"e_1_2_1_7_1","first-page":"8","article-title":"A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols","volume":"12","author":"Bogatov Dmytro","year":"2019","unstructured":"Dmytro Bogatov , George Kollios , and Leonid Reyzin . 2019 . A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols . Proc. VLDB Endow. 12 , 8 (apr 2019), 933--947. Dmytro Bogatov, George Kollios, and Leonid Reyzin. 2019. A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols. Proc. VLDB Endow. 12, 8 (apr 2019), 933--947.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9_13"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978303"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133980"},{"key":"e_1_2_1_11_1","volume-title":"Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In 21st Annual Network and Distributed System Security Symposium, NDSS","author":"Cash D.","year":"2014","unstructured":"D. Cash , J. Jaeger , S. Jarecki , C. S. Jutla , H. Krawczyk , M.C. Rosu , and M. Steiner . 2014 . Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In 21st Annual Network and Distributed System Security Symposium, NDSS 2014 . D. Cash, J. Jaeger, S. Jarecki, C. S. Jutla, H. Krawczyk, M.C. Rosu, and M. Steiner. 2014. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In 21st Annual Network and Distributed System Security Symposium, NDSS 2014."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"D. Cash S. Jarecki C. Jutla H. Krawczyk M.C. Ro\u015fu and M. Steiner. 2013. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In Advances in Cryptology - CRYPTO 2013. Berlin Heidelberg.  D. Cash S. Jarecki C. Jutla H. Krawczyk M.C. Ro\u015fu and M. Steiner. 2013. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In Advances in Cryptology - CRYPTO 2013. Berlin Heidelberg.","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"e_1_2_1_13_1","first-page":"2425","volume-title":"Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions. In 31st USENIX Security Symposium","author":"Chamani Javad Ghareh","year":"2022","unstructured":"Javad Ghareh Chamani , Dimitrios Papadopoulos , Mohammadamin Karbasforushan , and Ioannis Demertzis . [n.d.]. Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions. In 31st USENIX Security Symposium , pages = 2425 -- 2442 , publisher = USENIX Association, year = 2022 ,, Kevin R. B. Butler and Kurt Thomas (Eds.). Javad Ghareh Chamani, Dimitrios Papadopoulos, Mohammadamin Karbasforushan, and Ioannis Demertzis. [n.d.]. Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions. In 31st USENIX Security Symposium, pages = 2425--2442, publisher = USENIX Association, year = 2022,, Kevin R. B. Butler and Kurt Thomas (Eds.)."},{"key":"e_1_2_1_14_1","volume-title":"Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security (Lecture Notes in Computer Science","author":"Chase Melissa","unstructured":"Melissa Chase and Seny Kamara . 2010. Structured Encryption and Controlled Disclosure . In Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security (Lecture Notes in Computer Science , Vol. 6477). Melissa Chase and Seny Kamara. 2010. Structured Encryption and Controlled Disclosure. In Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security (Lecture Notes in Computer Science, Vol. 6477)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_16_1","volume-title":"Proc. ACM Conf. on Computer and Communications Security.","author":"Curtmola R.","unstructured":"R. Curtmola , J. Garay , S. Kamara , and R. Ostrovsky . 2006. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions . In Proc. ACM Conf. on Computer and Communications Security. R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. 2006. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In Proc. ACM Conf. on Computer and Communications Security."},{"key":"e_1_2_1_17_1","volume-title":"USENIX Security Symposium. 2433--2450","author":"Demertzis Ioannis","year":"2020","unstructured":"Ioannis Demertzis , Dimitrios Papadopoulos , Charalampos Papamanthou , and Saurabh Shintre . 2020 . SEAL: Attack Mitigation for Encrypted Databases via Adjustable Leakage . In USENIX Security Symposium. 2433--2450 . Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Saurabh Shintre. 2020. SEAL: Attack Mitigation for Encrypted Databases via Adjustable Leakage. In USENIX Security Symposium. 2433--2450."},{"key":"e_1_2_1_18_1","volume-title":"Practical Private Range Search Revisited (SIGMOD '16)","author":"Demertzis Ioannis","unstructured":"Ioannis Demertzis , Stavros Papadopoulos , Odysseas Papapetrou , Antonios Deligiannakis , and Minos Garofalakis . 2016. Practical Private Range Search Revisited (SIGMOD '16) . Association for Computing Machinery , New York, NY, USA , 185--198. Ioannis Demertzis, Stavros Papadopoulos, Odysseas Papapetrou, Antonios Deligiannakis, and Minos Garofalakis. 2016. Practical Private Range Search Revisited (SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 185--198."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167971"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the GLOBECOM","author":"Capitani di Vimercati Sabrina De","year":"2021","unstructured":"Sabrina De Capitani di Vimercati , Dario Facchinetti , Sara Foresti , Gianluca Oldani , Stefano Paraboschi , Matthew Rossi , and Pierangela Samarati . 2021 . Multi-dimensional indexes for point and range queries on outsourced encrypted data . Proceedings of the GLOBECOM (2021). Sabrina De Capitani di Vimercati, Dario Facchinetti, Sara Foresti, Gianluca Oldani, Stefano Paraboschi, Matthew Rossi, and Pierangela Samarati. 2021. Multi-dimensional indexes for point and range queries on outsourced encrypted data. Proceedings of the GLOBECOM (2021)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978379"},{"key":"e_1_2_1_22_1","volume-title":"Francesca Falzon, Roberto Tamassia, and William Schor.","author":"Espiritu Zachary","year":"2022","unstructured":"Zachary Espiritu , Evangelia Anna Markatou , Francesca Falzon, Roberto Tamassia, and William Schor. 2022 . ERS. https:\/\/github.com\/cloudsecuritygroup\/ers Accessed : 2022-12-14. Zachary Espiritu, Evangelia Anna Markatou, Francesca Falzon, Roberto Tamassia, and William Schor. 2022. ERS. https:\/\/github.com\/cloudsecuritygroup\/ers Accessed: 2022-12-14."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.56553\/popets-2022-0128"},{"key":"e_1_2_1_24_1","volume-title":"Encrypted Data: Beyond Exact Matches. In Computer Security - ESORICS","author":"Faber S.","year":"2015","unstructured":"S. Faber , S. Jarecki , H. Krawczyk , Q. Nguyen , M. Rosu , and M. Steiner . 2015 . Rich Queries on Encrypted Data: Beyond Exact Matches. In Computer Security - ESORICS 2015. S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M. Rosu, and M. Steiner. 2015. Rich Queries on Encrypted Data: Beyond Exact Matches. In Computer Security - ESORICS 2015."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417275"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"R. A. Finkel and J. L. Bentley. 1974. Quad Trees a Data Structure for Retrieval on Composite Keys. 4 1 (mar 1974) 1--9.  R. A. Finkel and J. L. Bentley. 1974. Quad Trees a Data Structure for Retrieval on Composite Keys. 4 1 (mar 1974) 1--9.","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_28_1","volume-title":"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 . 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_29_1","doi-asserted-by":"crossref","unstructured":"J. Ghareh Chamani D. Papadopoulos C. Papamanthou and R. Jalili. 2018. New Constructions for Forward and Backward Private Symmetric Searchable Encryption (CCS '18). 18 pages.  J. Ghareh Chamani D. Papadopoulos C. Papamanthou and R. Jalili. 2018. New Constructions for Forward and Backward Private Symmetric Searchable Encryption (CCS '18). 18 pages.","DOI":"10.1145\/3243734.3243833"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_31_1","volume-title":"Pancake: Frequency Smoothing for Encrypted Data Stores. In USENIX Security Symposium. 2451--2468","author":"Grubbs Paul","year":"2020","unstructured":"Paul Grubbs , Anurag Khandelwal , Marie-Sarah Lacharit\u00e9 , Lloyd Brown , Lucy Li , Rachit Agarwal , and Thomas Ristenpart . 2020 . Pancake: Frequency Smoothing for Encrypted Data Stores. In USENIX Security Symposium. 2451--2468 . Paul Grubbs, Anurag Khandelwal, Marie-Sarah Lacharit\u00e9, Lloyd Brown, Lucy Li, Rachit Agarwal, and Thomas Ristenpart. 2020. Pancake: Frequency Smoothing for Encrypted Data Stores. In USENIX Security Symposium. 2451--2468."},{"key":"e_1_2_1_32_1","volume-title":"Proc. ACM Conf. on Computer and Communications Security (CCS).","author":"Grubbs P.","unstructured":"P. Grubbs , M.S. Lacharit\u00e9 , B. Minaud , and K.G. Paterson . 2018. Pump Up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries . In Proc. ACM Conf. on Computer and Communications Security (CCS). P. Grubbs, M.S. Lacharit\u00e9, B. Minaud, and K.G. Paterson. 2018. Pump Up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. In Proc. ACM Conf. on Computer and Communications Security (CCS)."},{"key":"e_1_2_1_33_1","volume-title":"Proc. IEEE Symp. on Security and Privacy (S&P).","author":"Grubbs P.","unstructured":"P. Grubbs , M. Lacharit\u00e9 , B. Minaud , and K. G. Paterson . 2019. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks . In Proc. IEEE Symp. on Security and Privacy (S&P). P. Grubbs, M. Lacharit\u00e9, B. Minaud, and K. G. Paterson. 2019. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. In Proc. IEEE Symp. on Security and Privacy (S&P)."},{"key":"e_1_2_1_34_1","volume-title":"Why Your Encrypted Database Is Not Secure (HotOS '17)","author":"Grubbs Paul","year":"2017","unstructured":"Paul Grubbs , Thomas Ristenpart , and Vitaly Shmatikov . 2017 . Why Your Encrypted Database Is Not Secure (HotOS '17) . 162--168. Paul Grubbs, Thomas Ristenpart, and Vitaly Shmatikov. 2017. Why Your Encrypted Database Is Not Secure (HotOS '17). 162--168."},{"key":"e_1_2_1_35_1","volume-title":"2017 IEEE Symposium on Security and Privacy (SP).","author":"Grubbs P.","unstructured":"P. Grubbs , K. Sekniqi , V. Bindschaedler , M. Naveed , and T. Ristenpart . 2017. Leakage-Abuse Attacks against Order-Revealing Encryption . In 2017 IEEE Symposium on Security and Privacy (SP). P. Grubbs, K. Sekniqi, V. Bindschaedler, M. Naveed, and T. Ristenpart. 2017. Leakage-Abuse Attacks against Order-Revealing Encryption. In 2017 IEEE Symposium on Security and Privacy (SP)."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security.","author":"Gui Z.","unstructured":"Z. Gui , O. Johnson , and B. Warinschi . 2019. Encrypted Databases: New Volume Attacks against Range Queries . In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Z. Gui, O. Johnson, and B. Warinschi. 2019. Encrypted Databases: New Volume Attacks against Range Queries. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 2016 ACM on Cloud Computing Security Workshop. 12 pages.","author":"Hahn F.","unstructured":"F. Hahn and F. Kerschbaum . 2016. Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage . In Proceedings of the 2016 ACM on Cloud Computing Security Workshop. 12 pages. F. Hahn and F. Kerschbaum. 2016. Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage. In Proceedings of the 2016 ACM on Cloud Computing Security Workshop. 12 pages."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1061"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0245-7"},{"key":"e_1_2_1_41_1","volume-title":"2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). 90--108","author":"Kamara Seny","year":"2022","unstructured":"Seny Kamara , Abdelkarim Kati , Tarik Moataz , Thomas Schneider , Amos Treiber , and Michael Yonli . 2022 . SoK: Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data . In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). 90--108 . Seny Kamara, Abdelkarim Kati, Tarik Moataz, Thomas Schneider, Amos Treiber, and Michael Yonli. 2022. SoK: Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data. In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). 90--108."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"S. Kamara and T. Moataz. 2018. SQL on Structurally-Encrypted Databases. In Advances in Cryptology - ASIACRYPT 2018.  S. Kamara and T. Moataz. 2018. SQL on Structurally-Encrypted Databases. In Advances in Cryptology - ASIACRYPT 2018.","DOI":"10.1007\/978-3-030-03326-2_6"},{"key":"e_1_2_1_43_1","volume-title":"Darmstadt","volume":"213","author":"Kamara Seny","year":"2019","unstructured":"Seny Kamara and Tarik Moataz . 2019 . Computationally Volume-Hiding Structured Encryption. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques , Darmstadt , Germany, May 19-23, 2019, Proceedings, Part II (Lecture Notes in Computer Science , Vol. 11477). Springer, 183-- 213 . Seny Kamara and Tarik Moataz. 2019. Computationally Volume-Hiding Structured Encryption. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 11477). Springer, 183--213."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"S. Kamara and C. Papamanthou. 2013. Parallel and Dynamic Searchable Symmetric Encryption. In Financial Cryptography and Data Security. Berlin Heidelberg.  S. Kamara and C. Papamanthou. 2013. Parallel and Dynamic Searchable Symmetric Encryption. In Financial Cryptography and Data Security. Berlin Heidelberg.","DOI":"10.1007\/978-3-642-39884-1_22"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 2012 ACM Conference on Computer and Communications Security. 12 pages.","author":"Kamara S.","unstructured":"S. Kamara , C. Papamanthou , and T. Roeder . 2012. Dynamic Searchable Symmetric Encryption . In Proceedings of the 2012 ACM Conference on Computer and Communications Security. 12 pages. S. Kamara, C. Papamanthou, and T. Roeder. 2012. Dynamic Searchable Symmetric Encryption. In Proceedings of the 2012 ACM Conference on Computer and Communications Security. 12 pages."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130315"},{"key":"e_1_2_1_47_1","volume-title":"Proc. ACM Conf. on Computer and Communications Security.","author":"Kellaris G.","year":"2016","unstructured":"G. Kellaris , G. Kollios , K. Nissim , and A. O'Neill . 2016 . Generic Attacks on Secure Outsourced Databases . In Proc. ACM Conf. on Computer and Communications Security. G. Kellaris, G. Kollios, K. Nissim, and A. O'Neill. 2016. Generic Attacks on Secure Outsourced Databases. In Proc. ACM Conf. on Computer and Communications Security."},{"key":"e_1_2_1_48_1","volume-title":"Wang Fat Lau, and Man Au","author":"Kermanshahi Shabnam Kasra","year":"2020","unstructured":"Shabnam Kasra Kermanshahi , Shi-Feng Sun , Joseph K. Liu , Ron Steinfeld , Surya Nepal , Wang Fat Lau, and Man Au . 2020 . Geometric range search on encrypted data with Forward\/Backward security. IEEE Transactions on Dependable and Secure Computing ( 2020). Shabnam Kasra Kermanshahi, Shi-Feng Sun, Joseph K. Liu, Ron Steinfeld, Surya Nepal, Wang Fat Lau, and Man Au. 2020. Geometric range search on encrypted data with Forward\/Backward security. IEEE Transactions on Dependable and Secure Computing (2020)."},{"key":"e_1_2_1_49_1","volume-title":"Computer Security - ESORICS","author":"Kerschbaum Florian","year":"2019","unstructured":"Florian Kerschbaum and Anselme Tueno . 2019. An Efficiently Searchable Encrypted Data Structure for Range Queries . In Computer Security - ESORICS 2019 , Kazue Sako, Steve Schneider , and Peter Y. A. Ryan (Eds.). Springer International Publishing , Cham, 344--364. Florian Kerschbaum and Anselme Tueno. 2019. An Efficiently Searchable Encrypted Data Structure for Range Queries. In Computer Security - ESORICS 2019, Kazue Sako, Steve Schneider, and Peter Y. A. Ryan (Eds.). Springer International Publishing, Cham, 344--364."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"A. Kiayias S. Papadopoulos N. Triandopoulos and T. Zacharias. 2013. Delegatable Pseudorandom Functions and Applications (CCS '13). 669--684.  A. Kiayias S. Papadopoulos N. Triandopoulos and T. Zacharias. 2013. Delegatable Pseudorandom Functions and Applications (CCS '13). 669--684.","DOI":"10.1145\/2508859.2516668"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1829--1842","author":"Kornaropoulos Evgenios M.","year":"2022","unstructured":"Evgenios M. Kornaropoulos , Nathaniel Moyer , Charalampos Papamanthou , and Alexandros Psomas . 2022 . Leakage Inversion: Towards Quantifying Privacy in Searchable Encryption . In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1829--1842 . Evgenios M. Kornaropoulos, Nathaniel Moyer, Charalampos Papamanthou, and Alexandros Psomas. 2022. Leakage Inversion: Towards Quantifying Privacy in Searchable Encryption. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1829--1842."},{"key":"e_1_2_1_52_1","volume-title":"Proc. IEEE Symp. on Security and Privacy (S&P).","author":"Kornaropoulos E. M.","unstructured":"E. M. Kornaropoulos , C. Papamanthou , and R. Tamassia . 2020. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution . In Proc. IEEE Symp. on Security and Privacy (S&P). E. M. Kornaropoulos, C. Papamanthou, and R. Tamassia. 2020. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution. In Proc. IEEE Symp. on Security and Privacy (S&P)."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00044"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_55_1","volume-title":"Proc. IEEE Symp. on Security and Privacy 2018 (S&P","author":"Lacharit\u00e9 M.S.","year":"2018","unstructured":"M.S. Lacharit\u00e9 , B. Minaud , and K.G. Paterson . 2018. Improved reconstruction attacks on encrypted data using range query leakage . In Proc. IEEE Symp. on Security and Privacy 2018 (S&P 2018 ). M.S. Lacharit\u00e9, B. Minaud, and K.G. Paterson. 2018. Improved reconstruction attacks on encrypted data using range query leakage. In Proc. IEEE Symp. on Security and Privacy 2018 (S&P 2018)."},{"key":"e_1_2_1_56_1","volume-title":"Proc. ACM Conference on Computer and Communications Security (CCS). 12 pages.","author":"Lewi K.","unstructured":"K. Lewi and D. J. Wu . 2016. Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds . In Proc. ACM Conference on Computer and Communications Security (CCS). 12 pages. K. Lewi and D. J. Wu. 2016. Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds. In Proc. ACM Conference on Computer and Communications Security (CCS). 12 pages."},{"key":"e_1_2_1_57_1","volume-title":"Advances in Spatial and Temporal Databases.","author":"Li Feifei","unstructured":"Feifei Li , Dihan Cheng , Marios Hadjieleftheriou , George Kollios , and Shang-Hua Teng . 2005. On Trip Planning Queries in Spatial Databases . In Advances in Spatial and Temporal Databases. Berlin, Heidelberg , 273--290. Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. 2005. On Trip Planning Queries in Spatial Databases. In Advances in Spatial and Temporal Databases. Berlin, Heidelberg, 273--290."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733100"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2243--2261","author":"Markatou Evangelia Anna","year":"2021","unstructured":"Evangelia Anna Markatou , Francesca Falzon , Roberto Tamassia , and William Schor . 2021 . Reconstructing with Less: Leakage Abuse Attacks in Two Dimensions . In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2243--2261 . Evangelia Anna Markatou, Francesca Falzon, Roberto Tamassia, and William Schor. 2021. Reconstructing with Less: Leakage Abuse Attacks in Two Dimensions. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2243--2261."},{"key":"e_1_2_1_61_1","volume-title":"ISC 2019 (Lecture Notes in Computer Science","author":"Markatou Evangelia Anna","year":"2019","unstructured":"Evangelia Anna Markatou and Roberto Tamassia . 2019 . Full Database Reconstruction with Access and Search Pattern Leakage. In Information Security - 22nd International Conference , ISC 2019 (Lecture Notes in Computer Science , Vol. 11723). Evangelia Anna Markatou and Roberto Tamassia. 2019. Full Database Reconstruction with Access and Search Pattern Leakage. In Information Security - 22nd International Conference, ISC 2019 (Lecture Notes in Computer Science, Vol. 11723)."},{"key":"e_1_2_1_62_1","volume-title":"ISC 2019 (Lecture Notes in Computer Science","author":"Markatou Evangelia Anna","year":"2019","unstructured":"Evangelia Anna Markatou and Roberto Tamassia . 2019 . Mitigation Techniques for Attacks on 1-Dimensional Databases that Support Range Queries. In Information Security - 22nd International Conference , ISC 2019 (Lecture Notes in Computer Science , Vol. 11723). Evangelia Anna Markatou and Roberto Tamassia. 2019. Mitigation Techniques for Attacks on 1-Dimensional Databases that Support Range Queries. In Information Security - 22nd International Conference, ISC 2019 (Lecture Notes in Computer Science, Vol. 11723)."},{"key":"e_1_2_1_63_1","volume-title":"Proc. ACM Conf. on Computer and Communications Security (CCS). 12 pages.","author":"Naveed M.","unstructured":"M. Naveed , S. Kamara , and C. V. Wright . 2015. Inference Attacks on Property-Preserving Encrypted Databases . In Proc. ACM Conf. on Computer and Communications Security (CCS). 12 pages. M. Naveed, S. Kamara, and C. V. Wright. 2015. Inference Attacks on Property-Preserving Encrypted Databases. In Proc. ACM Conf. on Computer and Communications Security (CCS). 12 pages."},{"key":"e_1_2_1_64_1","volume-title":"2014 IEEE Symposium on Security and Privacy.","author":"Naveed M.","unstructured":"M. Naveed , M. Prabhakaran , and C. A. Gunter . 2014. Dynamic Searchable Encryption via Blind Storage . In 2014 IEEE Symposium on Security and Privacy. M. Naveed, M. Prabhakaran, and C. A. Gunter. 2014. Dynamic Searchable Encryption via Blind Storage. In 2014 IEEE Symposium on Security and Privacy."},{"key":"e_1_2_1_65_1","volume-title":"Blind Seer: A Scalable Private DBMS. In 2014 IEEE Symposium on Security and Privacy.","author":"Pappas V.","unstructured":"V. Pappas , F. Krell , B. Vo , V. Kolesnikov , T. Malkin , S.G. Choi , W. George , A. Keromytis , and S. Bellovin . 2014 . Blind Seer: A Scalable Private DBMS. In 2014 IEEE Symposium on Security and Privacy. V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S.G. Choi, W. George, A. Keromytis, and S. Bellovin. 2014. Blind Seer: A Scalable Private DBMS. In 2014 IEEE Symposium on Security and Privacy."},{"key":"e_1_2_1_66_1","volume-title":"Proc. ACM Conf. on Computer and Communications Security. 15 pages.","author":"Patel S.","unstructured":"S. Patel , G. Persiano , K. Yeo , and M. Yung . 2019. Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing . In Proc. ACM Conf. on Computer and Communications Security. 15 pages. S. Patel, G. Persiano, K. Yeo, and M. Yung. 2019. Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing. In Proc. ACM Conf. on Computer and Communications Security. 15 pages."},{"key":"e_1_2_1_67_1","unstructured":"Python Cryptographic Authority. 2018. pyca\/cryptography. https:\/\/cryptography.io\/ Accessed: 2022-12-14 version 3.4.7.  Python Cryptographic Authority. 2018. pyca\/cryptography. https:\/\/cryptography.io\/ Accessed: 2022-12-14 version 3.4.7."},{"key":"e_1_2_1_68_1","first-page":"12","article-title":"Effectively Learning Spatial Indices","volume":"13","author":"Qi Jianzhong","year":"2020","unstructured":"Jianzhong Qi , Guanli Liu , Christian S. Jensen , and Lars Kulik . 2020 . Effectively Learning Spatial Indices . Proc. VLDB Endow. 13 , 12 (jul 2020), 2341--2354. Jianzhong Qi, Guanli Liu, Christian S. Jensen, and Lars Kulik. 2020. Effectively Learning Spatial Indices. Proc. VLDB Endow. 13, 12 (jul 2020), 2341--2354.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_69_1","first-page":"5","article-title":"Theoretically Optimal and Empirically Efficient R-Trees with Strong Parallelizability","volume":"11","author":"Qi Jianzhong","year":"2018","unstructured":"Jianzhong Qi , Yufei Tao , Yanchuan Chang , and Rui Zhang . 2018 . Theoretically Optimal and Empirically Efficient R-Trees with Strong Parallelizability . Proc. VLDB Endow. 11 , 5 (jan 2018), 621--634. Jianzhong Qi, Yufei Tao, Yanchuan Chang, and Rui Zhang. 2018. Theoretically Optimal and Empirically Efficient R-Trees with Strong Parallelizability. Proc. VLDB Endow. 11, 5 (jan 2018), 621--634.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_70_1","volume-title":"REX: A Searchable Symmetric Encryption Scheme Supporting Range Queries (CCSW '17).","author":"Rizomiliotis P.","year":"2017","unstructured":"P. Rizomiliotis , E. Molla , and S. Gritzalis . 2017 . REX: A Searchable Symmetric Encryption Scheme Supporting Range Queries (CCSW '17). P. Rizomiliotis, E. Molla, and S. Gritzalis. 2017. REX: A Searchable Symmetric Encryption Scheme Supporting Range Queries (CCSW '17)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","unstructured":"E. Shi J. Bethencourt T-H. H. Chan D. Song and A. Perrig. 2007. Multi-Dimensional Range Query over Encrypted Data (SP '07). USA 15 pages.  E. Shi J. Bethencourt T-H. H. Chan D. Song and A. Perrig. 2007. Multi-Dimensional Range Query over Encrypted Data (SP '07). USA 15 pages.","DOI":"10.1109\/SP.2007.29"},{"key":"e_1_2_1_72_1","volume-title":"Proceeding IEEE Symposium on Security and Privacy (S&P).","author":"Song D.","unstructured":"D. Song , D. Wagner , and A. Perrig . 2000. Practical techniques for searches on encrypted data . In Proceeding IEEE Symposium on Security and Privacy (S&P). D. Song, D. Wagner, and A. Perrig. 2000. Practical techniques for searches on encrypted data. In Proceeding IEEE Symposium on Security and Privacy (S&P)."},{"key":"e_1_2_1_73_1","unstructured":"Malte Spitz. 2011. CRAWDAD dataset spitz\/cellular (v. 2011-05-04). Downloaded from https:\/\/crawdad.org\/spitz\/cellular\/20110504. Accessed: 2022-12-14.  Malte Spitz. 2011. CRAWDAD dataset spitz\/cellular (v. 2011-05-04). Downloaded from https:\/\/crawdad.org\/spitz\/cellular\/20110504. Accessed: 2022-12-14."},{"key":"e_1_2_1_74_1","unstructured":"United States Geological Survey. [n.d.]. Elevation Products (3DEP). Downloaded from apps.nationalmap.gov. Accessed: 2022-12-14.  United States Geological Survey. [n.d.]. Elevation Products (3DEP). Downloaded from apps.nationalmap.gov. Accessed: 2022-12-14."},{"key":"e_1_2_1_75_1","volume-title":"Proc. of the 9th ACM Symposium on Information, Computer and Communications Security (ASIA CCS '14)","author":"Wang B.","unstructured":"B. Wang , Y. Hou , M. Li , H. Wang , and H. Li . 2014. Maple: Scalable Multi-Dimensional Range Search over Encrypted Cloud Data with Tree-Based Index . In Proc. of the 9th ACM Symposium on Information, Computer and Communications Security (ASIA CCS '14) . B. Wang, Y. Hou, M. Li, H. Wang, and H. Li. 2014. Maple: Scalable Multi-Dimensional Range Search over Encrypted Cloud Data with Tree-Based Index. In Proc. of the 9th ACM Symposium on Information, Computer and Communications Security (ASIA CCS '14)."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2022-0003"},{"key":"e_1_2_1_77_1","volume-title":"European Symposium on Research in Computer Security (ESORICS) (LNCS). Springer, 228--246","author":"Zuo Cong","year":"2018","unstructured":"Cong Zuo , Shi-Feng Sun , Joseph K Liu , Jun Shao , and Josef Pieprzyk . 2018 . Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security . In European Symposium on Research in Computer Security (ESORICS) (LNCS). Springer, 228--246 . Cong Zuo, Shi-Feng Sun, Joseph K Liu, Jun Shao, and Josef Pieprzyk. 2018. Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security. In European Symposium on Research in Computer Security (ESORICS) (LNCS). Springer, 228--246."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:15:57Z","timestamp":1677021357000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":76,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574247"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574247","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}