IP Library › Granted Patent US 12,511,421
Granted Patent B2
US 12,511,421 · App. 18/328,867 · Granted Dec 30, 2025

Systems and methods for end-to end-encryption with encrypted multi-maps

Inventors: Seny Kamara (New York, NY); Tarik Moataz (Brooklyn, NY); Mark Porter (Seattle, WA)
Assignee: MongoDB, Inc.
G06F21/6227G06F16/213
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,511,421
App. No.
18/328,867
Granted
Dec 30, 2025
Kind
B2
Abstract

According to some aspects, provided are systems and methods that implement end-to-end encryption, and provide implementation configured to secure information during execution of queries on an encrypted data source. Various embodiments include multiple encrypted multi-map data structures and associated encryption schemes configured to securely read, write, and delete information while supporting any one or more of the following features: snapshot security, multiple client support, efficient execution under concurrent operation, and resilience to client failures. In various embodiments, addressable multi-map data structures enable concurrent access, and allow correct operation under polynomial time constraints.

Claims (51)

1 . A database system comprising:

at least one processor operatively connected to a memory, the at least one processor when executing configured to:

enable end-to-end encryption of plaintext data via an emulation of a database implementation;

accept and process queries against the emulation of the database implementation, such that the queries operate on and retrieve encrypted data from the emulation;

instantiate the emulation of the database implementation, the emulation including:

at least a first encrypted data structure configured to:

store encrypted representations of the plaintext data;

link multi-dimension labels to respective encrypted representations in the first encrypted data structure;

receive and execute database operations against the encrypted representations using the multi-dimension labels; and

at least a second encrypted data structure configured to:

store encrypted metadata associated with the first encrypted data structure; and

prevent overwrite conditions from occurring on the first encrypted data structure using the encrypted metadata.

2 . The system of claim 1 , wherein the at least one processor is further configured to receive and execute concurrent database operations against the first encrypted data structure.

3 . The system of claim 1 , wherein the at least one processor is further configured to receive and execute concurrent database operations against the second encrypted data structure.

4 . The system of claim 1 , wherein the at least one processor is further configured to receive and execute stateless database operations against the first encrypted data structure.

5 . The system of claim 1 , wherein the at least one processor is further configured to receive and execute stateless database operations against the second encrypted data structure.

6 . The system of claim 1 , wherein the emulation further comprises a third encrypted data structure configured to store gap information for the multi-dimension labels and respective encrypted representations.

7 . The system of claim 6 , wherein the third encrypted data structure is configured to limit reads executed on the first encrypted data structure to occur on locations in the first encrypted data structure having existing data.

8 . The system of claim 6 , wherein the at least one processor is further configured to receive and execute concurrent and/or stateless database operations against the third encrypted data structure.

9 . The system of claim 6 , wherein the emulation further comprises an encrypted set structure configured to:

store operation tokens generated for database operations on the second and third encrypted data structures; and

enable compaction of the second and/or third encrypted data structures.

10 . A computer implemented method for database encryption, the method comprising:

accepting and processing queries, by the at least one processor, against an emulation of a database implementation, such that the queries operate on and retrieve encrypted data from the emulation;

instantiating, by the at least one processor, the emulation of the database implementation, the emulation including at least a first encrypted data structure;

storing, by the at least one processor, encrypted representations of the plaintext data in the first encrypted data structure;

linking, by the at least one processor, multi-dimension labels to respective encrypted representations in the first encrypted data structure;

receiving and executing, by the at least one processor, database operations against the encrypted representations using the multi-dimension labels;

instantiating, by the at least one processor, at least a second encrypted data structure;

storing, by the at least one processor, encrypted metadata associated with the first encrypted data structure; and

preventing, by the at least one processor, overwrite conditions from occurring on the first encrypted data structure using the encrypted metadata.

11 . The method of claim 10 , wherein the method comprises receiving and executing concurrent database operations against the first encrypted data structure.

12 . The method of claim 10 , wherein the method comprises receiving and executing concurrent database operations against the second encrypted data structure.

13 . The method of claim 10 , wherein the method comprises receiving and executing stateless database operations against the first encrypted data structure.

14 . The method of claim 10 , wherein the method comprises receiving and executing stateless database operations against the second encrypted data structure.

15 . The method of claim 10 , wherein the method comprises generating a third encrypted data structure configured to store gap information for the multi-dimension labels and respective encrypted representations.

16 . The method of claim 15 , wherein the method comprises limiting reads executed on the reads executed on the first encrypted data structure to occur on locations in the first encrypted data structure having existing data, based at least in part on data stored in the third encrypted data structure.

17 . The method of claim 15 , wherein the method comprises receiving and executing concurrent and/or stateless database operations against the third encrypted data structure.

18 . The method of claim 15 , wherein the method comprises:

storing operation tokens generated for database operations on the second and third encrypted data structures in an encrypted set structure; and

enabling compaction of the second and/or third encrypted data structures based at least in part on the encrypted set structure.

19 . A non-transitory computer readable medium containing instructions that when executed cause at least one processor to perform a method for for database encryption, the method comprising:

accepting and processing queries against an emulation of a database implementation, such that the queries operate on and retrieve encrypted data from the emulation;

instantiating the emulation of the database implementation, the emulation including at least a first encrypted data structure;

storing encrypted representations of the plaintext data in the first encrypted data structure;

linking multi-dimension labels to respective encrypted representations in the first encrypted data structure;

receiving and executing database operations against the encrypted representations using the multi-dimension labels;

instantiating at least a second encrypted data structure;

storing encrypted metadata associated with the first encrypted data structure; and

preventing overwrite conditions from occurring on the first encrypted data structure using the encrypted metadata.

20 . The non-transitory computer readable medium of claim 19 , wherein the method further comprises receiving and executing concurrent database operations against the first encrypted data structure.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 2, 2024
From: KAMARA, SENY; MOATAZ, TARIK; PORTER, MARK
To: MONGODB, INC.
Reel/Frame 066980/0675 →
Continuity (9)
Continuation In Part 17570730 · Jan 7, 2022
Continuation In Part 17563425 · Dec 28, 2021
Continuation In Part 17514681 · Oct 29, 2021
Continuation In Part 17514681 · Oct 29, 2021
Provisional Application 63349208 · Jun 6, 2022
Provisional Application 63135053 · Jan 8, 2021
Provisional Application 63132063 · Dec 30, 2020
Provisional Application 63131487 · Dec 29, 2020
Related Publication 20230325524A1 · Oct 12, 2023
References Cited (45)
US 11269824B1 · Waas et al. · 2022 [cited by applicant]
US 12039073B2 · Moataz · 2024 [cited by applicant]
US 20150188949A1 · Mahaffey · 2015 [cited by applicant]
US 20160314212A1 · Menday · 2016 [cited by applicant]
US 20170235969A1 · Kamara · 2017 [cited by examiner]
US 20200285777A1 · Heller et al. · 2020 [cited by applicant]
US 20220207171A1 · Moataz · 2022 [cited by applicant]
US 20220215115A1 · Moataz · 2022 [cited by applicant]
US 20220222184A1 · Irwin · 2022 [cited by applicant]
US 20230055992A1 · Vinayagamurthy · 2023 [cited by applicant]
US 20230067981A1 · Varbedian · 2023 [cited by examiner]
US 20230177177A1 · George et al. · 2023 [cited by applicant]
US 20230315896A1 · Kamara et al. · 2023 [cited by applicant]
US 20230315897A1 · Karama et al. · 2023 [cited by applicant]
US 20240289485A1 · Moataz · 2024 [cited by applicant]
Amjad et al., Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption. Google. Jun. 10, 2021. 31 pages. [cited by applicant]
Kamara et al., Computationally Volume-Hiding Structure Encryption. International Conference on the Theory and Application of Cryptographic Techniques. May 19, 2019. 30 pages. [cited by applicant]
Patel et al., Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing. ACM SIGSAC Conference. Nov. 2019. 26 pages. [cited by applicant]
Wang et al., Simple Storage-Saving Structure for Volume-Hiding Encrypted Multi-Maps (A Slot in Need is a Slot Indeed). International Federation for Information Processing. Jul. 2021. pp. 63-83. [cited by applicant]
Wang et al., Practical Volume-Hiding Encrypted Multi-Maps with Optimal Overhead and Beyond. Association for Computing Machinery. Nov. 7, 2022. 2825-2839. [cited by applicant]
Wong et al., Secure query processing with data interoperability in a cloud database environment. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 1395-1406. [cited by applicant]
Amjad et al., Breach-Resistant Structured Encryption. Proceedings on Privacy Enhancing Technologies. Sep. 16, 2018(1):245-65. doi 10.2478/popets-2019-0014. [cited by applicant]
Boelter et al., A Secure One-Roundtrip Index for Range Queries. Technical Report 2016/568, IACR ePrint Cryptography Archive, 2016. [cited by applicant]
Boldyreva et al., Order-Preserving Symmetric Encryption. Order-preserving symmetric encryption. 2009. Advances in Cryptology EUROCRYPT. pp. 224-41. [cited by applicant]
Boneh et al., Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption Without Obfuscation. EUROCRYPT. 2015. pp. 563-94. [cited by applicant]
Bost et al., Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives, 2017. [cited by applicant]
Bost., Sophos—forward Secure Searchable Encryption*. 23rd ACM Conference on Computer and Communications Security. 2016. Doi:10.1145/2976749.2978303. 19 Pages. [cited by applicant]
Cash et al., Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. Network and Distributed System Security Symposium. Feb. 23-26, 2014. ISBN: 1-891562-35-5. 16 Pages. [cited by applicant]
Chase et al., Structured encryption and controlled disclosure. Advances in Cryptology.2010.6477:577-94. [cited by applicant]
Demertzis et al. Practical Private Range Search Revisited. Proceedings of the 2016 International Conference on Management of Data. 2016. pp. 185-198. Doi.org/10.1145/2882903.2882911. [cited by applicant]
Faber et al. Rich Queries on Encrypted Data: Beyond Exact Matches*. European Symposium on research in computer security. 2015.pp. 123-145. [cited by applicant]
Goldreich et al., Software Protection and Simulation on Oblivious RAMs. Journal of the ACM.1996.43(3):431-473. [cited by applicant]
Grubbs et al. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. 2019 IEEE Symposium on Security and Privacy (SP), pp. 1067-1083. [cited by applicant]
Grubbs et al., Pump up the vol. Practical Database Reconstruction from Volume Leakage on Range Queries. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 315-331, 2018. [cited by applicant]
Ishai et al., Private Large-Scale Databases with Distributed Searchable Symmetric Encryption. Cryptographers' Track at the RSA Conference. 2016. pp. 90-107. [cited by applicant]
Kamara et al., An optimal relational database encryption scheme.IACR Cryptol. ePrint Arch., 2020:274. [cited by applicant]
Kamara et al., Cryptographic Cloud Storage. Workshop on Real-Life Cryptographic Protocols and Standardization. 2010. pp. 136-149. [cited by applicant]
Kamara et al., SQL on Structurally-Encrypted Databases. Technical Report 2016/453, IACR ePrint Cryptography Archive. 58 Pages. [cited by applicant]
Kellaris et al., Generic Attacks on Secure Outsourced Databases. In ACM Conference on Computer and Communications Security. 2016. 12 Pages. [cited by applicant]
Lacharite' et al., Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. 2018. IEEE Symposium on Security and Privacy (SP), pp. 297-314. [cited by applicant]
Moataz et al., Oblivious substring search with updates. IACR Cryptol. ePrint Arch., 2015:722. [cited by applicant]
Naveed et al., Inference Attacks on Property-Preserving Encrypted Databases. ACM Conference on Computer and Communications Security (CCS), 2015. pp. 644-655. [cited by applicant]
Pappas et al., Blind Seer: A Scalable Private DBMS. Security and Privacy (SP), 2014 IEEE Symposium. pp. 359-374. [cited by applicant]
Song et al., Practical Techniques for Searches on Encrypted Data*. IEEE Symposium on Research in Security and Privacy. 2000. pp. 44-55. [cited by applicant]
Zhao et al., Encrypted databases: From theory to systems. Conference on Innovative Data Systems Research. 2021. 7 Pages. [cited by applicant]
Cited By (1)
US 12,675,594