Structured Encryption for Indirect Addressing

Ruth Ng; Alexander Hoover; David Cash; Eileen Ee

doi:10.62056/ay4fe0zn4

Structured Encryption for Indirect Addressing

Authors

Ruth Ng, Alexander Hoover, David Cash, Eileen Ee

Ruth Ng

DSO National Laboratories, Singapore
thisemailisnotruthless at gmail dot com

Alexander Hoover

University of Chicago, Chicago, United States
alexhoover at uchicago dot edu

David Cash

University of Chicago, Chicago, United States
davidcash at uchicago dot edu

Eileen Ee

DSO National Laboratories, Singapore

Keywords: structured encryption encrypted search searchable encryption indirect addressing

Abstract

The Structured Encryption (StE) framework can be used to capture the encryption and querying of complex data structures on an honest-but-curious server. In this work, we introduce a new type of StE called indirectly addressed multimap encryption (IA-MME). We propose two IA-MME schemes: the layered multimaps approach" which extends and generalizes the existing "multimap chaining" approach, and a novel technique called the single multimap approach which has comparable efficiency and strictly better security. We demonstrate that our formalisms simplify and modularize StE solutions for real-world use cases in searchable encryption and SQL databases, and provide simulations demonstrating that our IA-MME constructions lead to tangible efficiency and security gains on realistic data. As a part of our techniques, we identify and correct a technical error in prior constructions — providing greater insight into issues that can arise when composing StE schemes.

References

[AKM19]

Ghous Amjad, Seny Kamara, and Tarik Moataz. Breach-Resistant Structured Encryption. PoPETs, 2019(1):245–265, January 2019. DOI: 10.2478/popets-2019-0014

Google Scholar ePrint

[ANSS16]

Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf. Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1101–1114. June 2016. ACM Press. DOI: 10.1145/2897518.2897562

Google Scholar ePrint

[ASS18]

Gilad Asharov, Gil Segev, and Ido Shahaf. Tight Tradeoffs in Searchable Symmetric Encryption. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 407–436. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96884-1_14

Google Scholar ePrint

[Aut22]

Anonymous Authors. IA-MME Simulations. https://github.com/IA-MME-StE/IA-MME-Simulations. 2022.

Google Scholar ePrint

[BBO07]

Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill. Deterministic and Efficiently Searchable Encryption. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 535–552. August 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-74143-5_30

Google Scholar ePrint

[BMO17]

Raphaël Bost, Brice Minaud, and Olga Ohrimenko. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 1465–1482. 2017. ACM Press. DOI: 10.1145/3133956.3133980

Google Scholar ePrint

[Bos16]

Raphael Bost. $\Sigma o \phi o \varsigma$: Forward Secure Searchable Encryption. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1143–1154. October 2016. ACM Press. DOI: 10.1145/2976749.2978303

Google Scholar ePrint

[BR06]

Mihir Bellare and Phillip Rogaway. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 409–426. 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11761679_25

Google Scholar ePrint

[CGKO06]

Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 79–88. 2006. ACM Press. DOI: 10.1145/1180405.1180417

Google Scholar ePrint

[CGPR15]

David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-Abuse Attacks Against Searchable Encryption. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015, pages 668–679. October 2015. ACM Press. DOI: 10.1145/2810103.2813700

Google Scholar ePrint

[CJJ⁺13]

David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 353–373. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_20

Google Scholar ePrint

[CJJ⁺14]

David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In NDSS 2014. February 2014. The Internet Society. DOI: 10.14722/ndss.2014.23264

Google Scholar ePrint

[CK10]

Melissa Chase and Seny Kamara. Structured Encryption and Controlled Disclosure. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 577–594. December 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-17373-8_33

Google Scholar ePrint

[CNR21]

David Cash, Ruth Ng, and Adam Rivkin. Improved Structured Encryption for SQL Databases via Hybrid Indexing. In Kazue Sako and Nils Ole Tippenhauer, editors, ACNS 21International Conference on Applied Cryptography and Network Security, Part II, volume 12727 of LNCS, pages 480–510. June 2021. Springer, Cham. DOI: 10.1007/978-3-030-78375-4_19

Google Scholar ePrint

[CT14]

David Cash and Stefano Tessaro. The Locality of Searchable Symmetric Encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 351–368. May 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-55220-5_20

Google Scholar ePrint

[DPP⁺16]

Ioannis Demertzis, Stavros Papadopoulos, Odysseas Papapetrou, Antonios Deligiannakis, and Minos Garofalakis. Practical private range search revisited. In Proceedings of the 2016 International Conference on Management of Data, pages 185–198. 2016. DOI: 10.1145/2882903.2882911

Google Scholar ePrint

[DPP18]

Ioannis Demertzis, Dimitrios Papadopoulos, and Charalampos Papamanthou. Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 371–406. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96884-1_13

Google Scholar ePrint

[fCR22]

International Association for Cryptologic Research. Cryptology ePrint Archive. https://eprint.iacr.org/. 2022.

Google Scholar ePrint

[FJK⁺15]

Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel-Catalin Rosu, and Michael Steiner. Rich Queries on Encrypted Data: Beyond Exact Matches. In Günther Pernul, Peter Y. A. Ryan, and Edgar R. Weippl, editors, ESORICS 2015, Part II, volume 9327 of LNCS, pages 123–145. September 2015. Springer, Cham. DOI: 10.1007/978-3-319-24177-7_7

Google Scholar ePrint

[Goh03]

Eu-Jin Goh. Secure Indexes. Cryptology ePrint Archive, Report 2003/216. 2003.

Google Scholar ePrint

[IKK12]

Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In NDSS 2012. February 2012. The Internet Society.

Google Scholar ePrint

[JT20]

Joseph Jaeger and Nirvan Tyagi. Handling Adaptive Compromise for Practical Encryption Schemes. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 3–32. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56784-2_1

Google Scholar ePrint

[KM17]

Seny Kamara and Tarik Moataz. Boolean Searchable Symmetric Encryption with Worst-Case Sub-linear Complexity. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 94–124. 2017. Springer, Cham. DOI: 10.1007/978-3-319-56617-7_4

Google Scholar ePrint

[KM18]

Seny Kamara and Tarik Moataz. SQL on Structurally-Encrypted Databases. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part I, volume 11272 of LNCS, pages 149–180. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03326-2_6

Google Scholar ePrint

[KM19]

Seny Kamara and Tarik Moataz. Computationally Volume-Hiding Structured Encryption. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 183–213. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17656-3_7

Google Scholar ePrint

[KMO18]

Seny Kamara, Tarik Moataz, and Olga Ohrimenko. Structured Encryption and Leakage Suppression. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 339–370. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96884-1_12

Google Scholar ePrint

[KMZZ20]

Seny Kamara, Tarik Moataz, Stan Zdonik, and Zheguang Zhao. An Optimal Relational Database Encryption Scheme. Cryptology ePrint Archive, Report 2020/274. 2020.

Google Scholar ePrint

[KP13]

Seny Kamara and Charalampos Papamanthou. Parallel and Dynamic Searchable Symmetric Encryption. In Ahmad-Reza Sadeghi, editor, FC 2013, volume 7859 of LNCS, pages 258–274. April 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-39884-1_22

Google Scholar ePrint

[KPR12]

Seny Kamara, Charalampos Papamanthou, and Tom Roeder. Dynamic searchable symmetric encryption. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, ACM CCS 2012, pages 965–976. October 2012. ACM Press. DOI: 10.1145/2382196.2382298

Google Scholar ePrint

[Lab20]

Encrypted Systems Lab. The Clusion Library. https://github.com/encryptedsystems/Clusion. 2020.

Google Scholar ePrint

[NKW15]

Muhammad Naveed, Seny Kamara, and Charles V. Wright. Inference Attacks on Property-Preserving Encrypted Databases. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015, pages 644–655. October 2015. ACM Press. DOI: 10.1145/2810103.2813651

Google Scholar ePrint

[NPG14]

Muhammad Naveed, Manoj Prabhakaran, and Carl A. Gunter. Dynamic Searchable Encryption via Blind Storage. In 2014 IEEE Symposium on Security and Privacy, pages 639–654. May 2014. IEEE Computer Society Press. DOI: 10.1109/SP.2014.47

Google Scholar ePrint

[PPY18]

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. Private Stateful Information Retrieval. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 1002–1019. October 2018. ACM Press. DOI: 10.1145/3243734.3243821

Google Scholar ePrint

[PPY20]

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Model. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 433–463. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56784-2_15

Google Scholar ePrint

[PW16]

David Pouliot and Charles V. Wright. The Shadow Nemesis: Inference Attacks on Efficiently Deployable, Efficiently Searchable Encryption. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1341–1352. October 2016. ACM Press. DOI: 10.1145/2976749.2978401

Google Scholar ePrint

[SPS14]

Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. Practical Dynamic Searchable Encryption with Small Leakage. In NDSS 2014. February 2014. The Internet Society. DOI: 10.14722/ndss.2014.23298

Google Scholar ePrint

[SWP00]

Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Practical Techniques for Searches on Encrypted Data. In 2000 IEEE Symposium on Security and Privacy, pages 44–55. May 2000. IEEE Computer Society Press. DOI: 10.1109/SECPRI.2000.848445

Google Scholar ePrint

[{Tra}22]

Transaction Processing Performance Council. TPC BENCHMARKTM H (Decision Support) Standard Specification Revision 3.0.1. https://www.tpc.org/tpc_documents_current_versions/pdf/tpc-h_v3.0.1.pdf. 2022.

Google Scholar ePrint

[{Tra}23]

Transaction Processing Performance Council. TPC Download Current Specs/Source. https://www.tpc.org/tpc_documents_current_versions/current_specifications5.asp. 2023.

Google Scholar ePrint

[WCL⁺10]

Cong Wang, Ning Cao, Jin Li, Kui Ren, and Wenjing Lou. Secure ranked keyword search over encrypted cloud data. In 2010 IEEE 30th international conference on distributed computing systems, pages 253–262. 2010. IEEE. DOI: 10.1109/ICDCS.2010.34

Google Scholar ePrint

[ZKP16]

Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016, pages 707–720. August 2016. USENIX Association.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ay4fe0zn4

History

Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Ruth Ng, Alexander Hoover, David Cash, and Eileen Ee, Structured Encryption for Indirect Addressing. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ay4fe0zn4.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.