IP Library › Granted Patent US 12,438,696
Granted Patent B2
US 12,438,696 · App. 18/114,682 · Granted Oct 7, 2025

Copy-and-recurse operations for fully homomorphic encrypted database query processing

Inventors: Hayim Shaul (Kfar Saba, IL); Guy Moshkowich (Nes Ziyona, IL); Eyal Kushnir (Kfar Vradim, IL)
Assignee: International Business Machines Corporation
H04L9/008G06F16/24564
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,438,696
App. No.
18/114,682
Granted
Oct 7, 2025
Kind
B2
Abstract

Mechanisms are provided for performing a fully homomorphic encryption operation. The mechanisms generate, for a data set in a backend data store, a tree data structure comprising a hierarchy of nodes and edges connecting the nodes in a parent-child relationship. In response to receiving an encrypted query from a client computing device, a search operation is executed using the tree data structure at least by executing a copy-and-recurse computing tool to identify a portion of the tree data structure to which to apply a fully homomorphic encryption (FHE) operation. The copy-and-recurse computing tool copies a subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes. The FHE operation is executed on a portion of the data set, corresponding to the identified portion of the tree data structure, to generate results of the FHE operation which are then output.

Claims (45)

1. A computer-implemented method comprising:

generating, for a data set in a backend data store, a tree data structure comprising a hierarchy of nodes and edges connecting the nodes in a parent-child relationship;

in response to receiving an encrypted query from a client computing device, executing a search operation using the tree data structure at least by executing a copy-and-recurse computing tool to identify a portion of the tree data structure to which to apply a fully homomorphic encryption (FHE) operation, wherein the copy-and-recurse computing tool copies a subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes;

executing the FHE operation on a portion of the data set, corresponding to the identified portion of the tree data structure, to generate results of the FHE operation; and

outputting the results as an encrypted output to the client computing device,

wherein the subset of nodes of the tree data structure are child nodes that cross a specified range of the search operation, and wherein the copy-and-recurse computing tool copies the subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes at least by generating a copy-and-recurse matrix and multiplying a vector representing the child nodes of the tree data structure, that cross the specified range of the search operation, by the copy-and-recurse matrix.

2. The method of claim 1 , wherein the copy-and-recurse computing tool, during traversal of the tree data structure, for a given node in the tree data structure, copies a predetermined number of child nodes and their subtrees to a buffer, and recurses the range search operation only into the copied child nodes.

3. The method of claim 2 , wherein the predetermined number of child nodes is a bound value limiting a number of nodes recursed into to be less than a total number of child nodes of the given node.

4. The method of claim 1 , wherein generating the tree data structure further comprises:

executing a fill-tree operation on an initial tree data structure, wherein the fill-tree operation comprises:

identifying a first set of nodes having less than a predetermined number of child nodes;

identifying a second set of nodes that are leaf nodes whose distance from a root node of the tree data structure are less than a predetermined distance;

for the first set of nodes, adding an empty child node to an inner node that has less than the predetermined number of child nodes; and

for the second set of nodes, adding the predetermined number of child nodes to the second node.

5. The method of claim 1 , wherein the tree data structure is one of a partition tree data structure, a decision tree data structure, or a search tree data structure.

6. The method of claim 1 , wherein the search operation is a range search operation, and wherein executing the search operation comprises executing a first algorithm that identifies a first subset of nodes in the tree data structure that are contained in a range of the range search operation, and a second algorithm that identifies a second subset of nodes in the tree data structure that are not contained in the range, but that cross the range, and wherein the copy-and-recurse computing tool executes on the second subset of nodes.

7. The method of claim 1 , wherein the computer-implemented method is performed as part of a cloud computing service, and wherein the encrypted query is part of a request for performance of the cloud computing service.

8. The method of claim 7 , wherein the encrypted query comprises a query that is represented as a range search operation that is one of a counting operation, a reporting operation, an averaging operation, or a k-means clustering operation.

9. The method of claim 7 , wherein the cloud computing service is a location service for locating a physical location of one or more entities.

10. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

generate, for a data set in a backend data store, a tree data structure comprising a hierarchy of nodes and edges connecting the nodes in a parent-child relationship;

in response to receiving an encrypted query from a client computing device, execute a search operation using the tree data structure at least by executing a copy-and-recurse computing tool to identify a portion of the tree data structure to which to apply a fully homomorphic encryption (FHE) operation, wherein the copy-and-recurse computing tool copies a subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes;

execute the FHE operation on a portion of the data set, corresponding to the identified portion of the tree data structure, to generate results of the FHE operation; and

output the results as an encrypted output to the client computing device,

wherein the subset of nodes of the tree data structure are child nodes that cross a specified range of the search operation, and wherein the copy-and-recurse computing tool copies the subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes at least by generating a copy-and-recurse matrix and multiplying a vector representing the child nodes of the tree data structure, that cross the specified range of the search operation, by the copy-and-recurse matrix.

11. The computer program product of claim 10 , wherein the copy-and-recurse computing tool, during traversal of the tree data structure, for a given node in the tree data structure, copies a predetermined number of child nodes and their subtrees to a buffer, and recurses the range search operation only into the copied child nodes.

12. The computer program product of claim 11 , wherein the predetermined number of child nodes is a bound value limiting a number of nodes recursed into to be less than a total number of child nodes of the given node.

13. The computer program product of claim 10 , wherein generating the tree data structure further comprises:

executing a fill-tree operation on an initial tree data structure, wherein the fill-tree operation comprises:

identifying a first set of nodes having less than a predetermined number of child nodes;

identifying a second set of nodes that are leaf nodes whose distance from a root node of the tree data structure are less than a predetermined distance;

for the first set of nodes, adding an empty child node to an inner node that has less than the predetermined number of child nodes; and

for the second set of nodes, adding the predetermined number of child nodes to the second node.

14. The computer program product of claim 10 , wherein the tree data structure is one of a partition tree data structure, a decision tree data structure, or a search tree data structure.

15. The computer program product of claim 10 , wherein the search operation is a range search operation, and wherein executing the search operation comprises executing a first algorithm that identifies a first subset of nodes in the tree data structure that are contained in a range of the range search operation, and a second algorithm that identifies a second subset of nodes in the tree data structure that are not contained in the range, but that cross the range, and wherein the copy-and-recurse computing tool executes on the second subset of nodes.

16. The computer program product of claim 10 , wherein the computer-implemented method is performed as part of a cloud computing service, and wherein the encrypted query is part of a request for performance of the cloud computing service.

17. The computer program product of claim 16 , wherein the encrypted query comprises a query that is represented as a range search operation that is one of a counting operation, a reporting operation, an averaging operation, or a k-means clustering operation.

18. An apparatus comprising:

at least one processor; and

at least one memory coupled to the at least one processor, wherein the at least one memory comprises instructions which, when executed by the at least one processor, cause the at least one processor to:

generate, for a data set in a backend data store, a tree data structure comprising a hierarchy of nodes and edges connecting the nodes in a parent-child relationship;

in response to receiving an encrypted query from a client computing device, execute a search operation using the tree data structure at least by executing a copy-and-recurse computing tool to identify a portion of the tree data structure to which to apply a fully homomorphic encryption (FHE) operation, wherein the copy-and-recurse computing tool copies a subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes;

execute the FHE operation on a portion of the data set, corresponding to the identified portion of the tree data structure, to generate results of the FHE operation; and

output the results as an encrypted output to the client computing device,

wherein the subset of nodes of the tree data structure are child nodes that cross a specified range of the search operation, and wherein the copy-and-recurse computing tool copies the subset of nodes of the tree data structure and recurses the search operation into the copied subset of nodes at least by generating a copy-and-recurse matrix and multiplying a vector representing the child nodes of the tree data structure, that cross the specified range of the search operation, by the copy-and-recurse matrix.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 27, 2023
From: SHAUL, HAYIM; MOSHKOWICH, GUY; KUSHNIR, EYAL
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 062814/0783 →
Continuity (1)
Related Publication 20240297777A1 · Sep 5, 2024
References Cited (50)
US 8370394B2 · Atta · 2013 [cited by examiner]
US 8527920B1 · Choudhury · 2013 [cited by examiner]
US 9418088B1 · Noll · 2016 [cited by examiner]
US 9646166B2 · Cash · 2017 [cited by applicant]
US 9798528B2 · Gao · 2017 [cited by examiner]
US 11281747B2 · Kawahara · 2022 [cited by examiner]
US 20030177449A1 · Rose · 2003 [cited by examiner]
US 20100058265A1 · Finkler · 2010 [cited by examiner]
US 20100076940A1 · Bordawekar · 2010 [cited by examiner]
US 20130036473A1 · Myles · 2013 [cited by examiner]
US 20140331044A1 · Fujii · 2014 [cited by examiner]
US 20150067400A1 · Ishii · 2015 [cited by examiner]
US 20150379032A1 · Kaplan · 2015 [cited by examiner]
US 20170063525A1 · Bacon · 2017 [cited by examiner]
US 20200358610A1 · Yeo · 2020 [cited by examiner]
US 20220173886A1 · Sardesai · 2022 [cited by examiner]
US 20230146149A1 · Moon · 2023 [cited by examiner]
US 20250037186A1 · Wang · 2025 [cited by examiner]
Agarwal, P.K. et al., “On range searching with semialgebraic sets”, Discrete Comput Geom 11, Apr. 1, 1994, 26 pages. [cited by applicant]
Agarwal, P.K. et al., “On Range Searching with Semialgebraic Sets II”, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, Oct. 2012, 10 pages. [cited by applicant]
Aharoni, Ehud et al., “HeLayers: A Tile Tensors Framework for Large Neural Networks on Encrypted Data”, arXiv:2011.01805v3 [cs.CR] Jan. 1, 2023, 18 pages. [cited by applicant]
Akavia, Adi et al., “Privacy-Preserving Decision Trees Training and Prediction”, ACM Transactions on Privacy and Security, vol. 25, No. 3, Article 24. Publication date: May 2022, 30 pages. [cited by applicant]
Akavia, Adi et al., “Secure Data Retrieval on the Cloud: Homomorphic Encryption meets Coresets”, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(2):Feb. 2019, 26 pages. [cited by applicant]
Akavia, Adi et al., “Secure Search via Multi-Ring Fully Homomorphic Encryption”, Cryptology ePrint Archive, May 2018, 29 pages. [cited by applicant]
Azogagh, Sofiane et al., “Probonite : Private one-branch-only non-interactive decision tree evaluation.”, WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Nov. 2022, 1… [cited by applicant]
Beaver, Donald et al., “Efficient Multiparty Protocols Using Circuit Randomization”, Advances in Cryptology—CRYPTO '91, 11th Annual International Cryptology Conference, Aug. 11-15, 1991, 13 pages. [cited by applicant]
Beimel, Amos et al., “Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing”, Advances in Cryptology—CRYPTO 2000 20th Annual International Cryptology Conference, Aug. 20-24, 2000, 19 … [cited by applicant]
Brakerski, Zvika et al., “Fully Homomorphic Encryption without Bootstrapping”, ITCS '12: Innovations in Theoretical Computer Science, Jan. 8-10, 2012, 27 pages. [cited by applicant]
Cheon, Jung Hee et al., “Efficient Homomorphic Comparison Methods with Optimal Complexity”, Advances in Cryptology—ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information… [cited by applicant]
Cheon, Jung Hee et al., “Homomorphic Encryption for Arithmetic of Approximate Numbers”, Asiacrypt 2017, the 23rd Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec.… [cited by applicant]
Cheon, Jung Hee et al., “Search-and-compute on Encrypted Data”, Financial Cryptography and Data Security (FC15) 19th International Conference, Jan. 26-30, 2015, 27 pages. [cited by applicant]
Cong, Kelong et al., “SortingHat: Efficient Private Decision Tree Evaluation via Homomorphic Encryption and Transciphering”, CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security… [cited by applicant]
Corrigan-Gibbs, Henry et al., “Private information retrieval with sublinear online time”, 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 10-14, 2020, Proceedings, Pa… [cited by applicant]
De Berg, Mark et al., “Computational Geometry: Algorithms and Applications”, Springer-Verlag TELOS, Santa Clara, CA, USA, 2nd ed. edition, Jun. 2000, 367 pages. [cited by applicant]
Demertzis, Ioannis et al., “Practical Private Range Search In Depth”, ACM Transactions on Database Systems, vol. 9, No. 4, Article 39. Publication date: Mar. 2018, 50 pages. [cited by applicant]
Demertzis, Ioannis et al., “Practical Private Range Search Revisited”, SIGMOD/PODS'16: International Conference on Management of Data, Jun. 2016, 14 pages. [cited by applicant]
Drucker, Nir et al., “Bleach: Cleaning Errors in Discrete Computations over CKKS”, Cryptology ePrint Archive, Paper, 2022/1298, Apr. 2022. https://eprint.iacr.org/2022/1298, 39 pages. [cited by applicant]
Ducas, Leo et al., “Sanitization of FHE Ciphertexts”, Advances in Cryptology—Eurocrypt 2016 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 8-12, 2016, 19 pages. [cited by applicant]
Falzon, Francesca et al., “Range Search over Encrypted Multi-Attribute Data”, Proceedings of the VLDB Endowment vol. 16 Issue 4, 16 pages. [cited by applicant]
Geary, Richard F. et al., “A simple optimal representation for balanced parentheses”, Theoretical Computer Science vol. 368, Issue 3, Dec. 10, 2006, 16 pages. [cited by applicant]
Halevi, Shai et al., “Algorithms in HElib”, Advances in Cryptology—CRYPTO 2014,34th Annual Cryptology Conference, Aug. 17-21, 2014, Proceedings, Part I, 20 pages. [cited by applicant]
Hasan, Mohammad Z. et al., “Secure count query on encrypted genomic data”, Journal of Biomedical Informatics vol. 81, May 2018, pp. 41-52. [cited by applicant]
Iliashenko, Ilia et al., “Homomorphically counting elements with the same property”, The 22nd Privacy Enhancing Technologies Symposium Jul. 11-15, 2022, 20 pages. [cited by applicant]
Kim, Myungsun et al., “Private Compound Wildcard Queries Using Fully Homomorphic Encryption”, IEEE Transactions on Dependable and Secure Computing, vol. 16, No. 5, pp., Sep. 1-Oct. 2019, 14 pages. [cited by applicant]
Lee, Eunsang et al., “Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison”, IEEE Transactions on Dependable and Secure Computing, vol. 19, No. 6, Nov.-Dec. 2022, 22 pages. [cited by applicant]
Matousek, Jiri, “Efficient partition trees”, In Proceedings of the seventh annual symposium on Computational geometry (SCG '91). Association for Computing Machinery, 9 pages. [cited by applicant]
Saha, Tushar K. et al., “Efficient Private Conjunctive Query Protocol Over Encrypted Data”, Cryptography 5, No. 1: 2, Jan. 18, 2021, 22 pages. [cited by applicant]
Tueno, Anselme et al., “Non-Interactive Private Decision Tree Evaluation”, arXiv:1909.08362v1 [cs.CR] Sep. 18, 2019, 16 pages. [cited by applicant]
Tueno, Anselme et al., “Private Evaluation of Decision Trees using Sublinear Cost”, PETS 2019 The 19th Privacy Enhancing Technologies Symposium Jul. 16-20, 2019, 21 pages. [cited by applicant]
Vo-Huu, Triet D. et al., “EPiC: efficient privacy-preserving counting for MapReduce”, Computing vol. 101, Jun. 18, 2018, 22 pages. [cited by applicant]