IP Library › Granted Patent US 12,675,594
Granted Patent B2
US 12,675,594 · App. 17/563,425 · Granted Jul 7, 2026

Systems and methods using emulation for end to end encryption

Inventor: Tarik Moataz (North Providence, RI)
Assignee: MongoDB, Inc.
G06F21/6227G06F16/24573G06F16/248G06F21/53G06F21/602
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,675,594
App. No.
17/563,425
Granted
Jul 7, 2026
Kind
B2
Abstract

Methods and system implement solutions for integrating encryption and emulation into native database formats and/or architectures. “Native” database is used to describe a database that has not been designed for end to end encryption, an off the shelf database deployment, and/or a commercially available database. According to some embodiments, various encryption systems and methods employ emulation operations to enable a native database and native database functions to leverage full encryption primitives. Various aspects integrate emulation operations into standard database implementations, where the emulation enables native database functions to operate on entirely encrypted data.

Claims (40)

1 . An emulation system comprising:

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

integrate an emulation layer into a dynamic schema database deployment;

maintain the dynamic schema database architecture;

accept and respond to database queries made on the standard dynamic schema database through the emulation layer;

wherein the emulation layer is configured to:

maintain data stored on the dynamic schema database so that designated data is in an encrypted format when stored, queried, and output, the encrypted format encoding at least a portion of document units of data from dynamic schema source data comprising at least documents, and the encrypted format further comprising at least an encrypted multi-map data structure of label and tuple pairs;

execute queries against the designated data in the encrypted format stored in the encrypted multi-map data structure; and

return the output to any query on the designated data to a requesting client in the encrypted format used in the encrypted multi-map data structure.

2 . The system of claim 1 , wherein the system is further configured to maintain any output from any query response in the encrypted format.

3 . The system of claim 1 , wherein the at least one processor is configured to transform plaintext data into an encrypted multi-map data structure.

4 . The system of claim 3 , wherein the at least one processor is configured to construct an index on the encrypted values in the encrypted multi-map.

5 . The system of claim 1 , wherein the at least one processor is configured to construct at least one search token for accessing the multi-map data structure as part of the query on the designated data.

6 . The system of claim 5 , wherein the at least one processor is configured to construct the at least one search token comprising at least a cyphertext value and index value.

7 . The system of claim 5 , wherein the at least one processor is configured to construct the at least one search token comprising a sub token including at least a cyphertext value and index value for each counter in a state dictionary associated with the cyphertext value being queried.

8 . The system of claim 1 , wherein the at least one processor is configured to construct a range search token comprising vectors of sub tokens.

9 . The system of claim 8 , wherein the at least one processor is configured to generate the sub tokens for the range search token based on counter information in a cover of the range to be searched.

10 . The system of claim 1 , wherein the at least one processor is configured to transform textual values of a plaintext database into numeric values for transformation into an encrypted multimap representation to enable end to end encryption of text search.

11 . The system of claim 1 , wherein the at least one processor is configured to:

transform textual values of a plaintext database into a tree representation;

transform the tree representation into an encrypted multimap and hypergraph representation to enable end to end encryption of pattern search.

12 . A computer implemented method for end to end encryption, the method comprising:

integrating, by at least one processor, an emulation layer into a dynamic schema database deployment;

maintaining, by the at least one processor the dynamic schema database architecture;

accepting and responding, by the at least one processor, to database queries made on the dynamic schema database through the emulation layer;

maintaining, by the at least one processor, data stored on the dynamic schema database so that designated data is in an encrypted format when stored, queried, and output, the encrypted format encoding at least a portion of document units of data from dynamic schema source data comprising at least documents, and the encrypted format further comprising at least an encrypted multi-map data structure of label and tuple pairs;

executing, by the at least one processor, queries against the designated data in the encrypted format stored in the encrypted multi-map data structure; and

returning, by the at least one processor, the output to any query on the designated data to a requesting client in the encrypted format stored in the encrypted multi-map data structure.

13 . The method of claim 12 , wherein the method further comprises maintaining, by the at least one processor, any output from any query response in the encrypted format.

14 . The method of claim 12 , wherein the method further comprises transforming plaintext data into an encrypted multi-map.

15 . The method of claim 14 , wherein the method further comprises constructing an index on the encrypted values in the encrypted multi-map.

16 . The method of claim 12 , wherein the method further comprises constructing at least one search token as part of the query on the designated data.

17 . The method of claim 16 , wherein the method further comprises constructing the at least one search token comprising at least a cyphertext value and index value.

18 . The method of claim 16 , wherein the method further comprises constructing the at least one search token comprising a sub token including at least a cyphertext value and index value for each counter in a state dictionary associated with the cyphertext value being queried.

19 . The method of claim 12 , wherein the method further comprises constructing a range search token comprising vectors of sub tokens.

20 . The method of claim 19 , wherein the method further comprises generating the sub-tokens for the range search token based on counter information in a cover of the range to be searched.

21 . The method of claim 12 , wherein the method further comprises transforming textual values of a plaintext database into numeric values for transformation into an encrypted multimap representation to enable end to end encryption of text search.

22 . The method of claim 12 , wherein the method further comprises:

transforming textual values of a plaintext database into a tree representation; and

transforming the tree representation into an encrypted multimap and hypergraph representation to enable end to end encryption of pattern search.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 14, 2022
From: MOATAZ, TARIK
To: MONGODB, INC.
Reel/Frame 059596/0304 →
Continuity (5)
Continuation In Part 17514681 · Oct 29, 2021
Provisional Application 63135053 · Jan 8, 2021
Provisional Application 63132063 · Dec 30, 2020
Provisional Application 63131487 · Dec 29, 2020
Related Publication 20220207171A1 · Jun 30, 2022
References Cited (52)
US 9213867B2 · Ramamurthy · 2015 [cited by examiner]
US 10846411B2 · Horowitz · 2020 [cited by examiner]
US 11269824B1 · Waas · 2022 [cited by examiner]
US 12039073B2 · Moataz · 2024 [cited by applicant]
US 12511421B2 · Kamara et al. · 2025 [cited by applicant]
US 12511422B2 · Kamara et al. · 2025 [cited by applicant]
US 12511423B2 · Kamara et al. · 2025 [cited by applicant]
US 20150188949A1 · Mahaffey et al. · 2015 [cited by applicant]
US 20160314212A1 · Menday · 2016 [cited by examiner]
US 20170235969A1 · Kamara · 2017 [cited by examiner]
US 20200285777A1 · Heller et al. · 2020 [cited by applicant]
US 20220215115A1 · Moataz · 2022 [cited by applicant]
US 20220222184A1 · Irwin et al. · 2022 [cited by applicant]
US 20230055992A1 · Vinayagamurthy et al. · 2023 [cited by applicant]
US 20230067981A1 · Varbedian et al. · 2023 [cited by applicant]
US 20230177177A1 · George et al. · 2023 [cited by applicant]
US 20230315896A1 · Kamara et al. · 2023 [cited by applicant]
US 20230315897A1 · Kamara et al. · 2023 [cited by applicant]
US 20230325524A1 · Kamara et al. · 2023 [cited by applicant]
US 20240289485A1 · Moataz · 2024 [cited by applicant]
“Wong et al., Secure Query Processing with Data Interoperability in a Cloud Database Environment, Jun. 27, 2014, p. 1395-1406” (Year: 2014). [cited by examiner]
Popa, et al., “CryptDB: Processing Queries on an Encrypted Database”, Sep. 2012, Communications of the ACM, vol. 55, No. 9, pp. 103-111 (Year: 2012). [cited by examiner]
Amjad, et al., “Breach-Resistant Structured Encryption”, Proceedings on Privacy Enhancing Technologies, 2018, Sep. 16(1): 245-65, doi 10.2478/popets-2019-0014 (Year: 2018). [cited by examiner]
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]
Amjad et al., Breach-Resistant Structured Encryption. Proceedings on Privacy Enhancing Technologies. Sep. 1, 20186(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. [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-98. 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-45. [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 vol. 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]
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]
Lacharite' et al., Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. 2018. IEEE Symposium on Security and Privacy (SP). 18 Pages. [cited by applicant]