International Business Machines Corporation

Guy Moshkowich

Hayim Shaul

Eyal Kushnir

Nir Drucker

Allon Adir

Ehud Aharoni

Omri Soceanu

Ramy Masalha

Tomer Pelleg

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.

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

A computer-implemented method for identifying a leaf in a tree is provided. A processor set receives a first point representing one or more values within a d-dimensional space for identifying the leaf in the tree. The processor set generates a parameter for identifying the leaf in the tree. The processor set identifies a node at highest depth of the tree. The processor set determines a first value of the parameter for generating a range. The processor set selects a subset of child nodes from the number of child nodes associated with the node at the highest depth of the tree based on the range. The processor sets the subset of child nodes as the node at the highest depth of the tree. The processor set traverses the tree by repeating the identifying step, the determining step, the selecting step, and setting steps until the leaf in the tree is identified.

Parametric searching under fully homomorphic encryption

A computer-implemented method comprising: receiving, as input, a ciphertext x representing a computational result of an approximated fully-homomorphic encryption (FHE) scheme, wherein ciphertext x comprises an underlying number m and an accumulated computational error e; iteratively, (i) performing a bit extraction operation to extract a current most significant bit (MSB) x' of ciphertext x, (ii) calculating accuracy parameters α, β associated with x′; (iii) applying a step function to the extracted MSB x′, based, at least in part, on the calculated accuracy parameters α, β, to reduce or remove the accumulated computational error e and to return a clean MSB b, and (iv) repeating steps (i)-(iii) for all bits included in the underlying number m; and reconstructing and outputting, from all of the returned clean MSBs b, the number m.

Fully homomorphic encryption for fixed-point elements

Mechanisms are provided for fully homomorphic encryption enabled graph embedding. An encrypted graph data structure, having encrypted entities and predicates, is received and, for each encrypted entity, a corresponding set of entity ciphertexts is generated based on an initial embedding of entity features. For each encrypted predicate, a corresponding predicate ciphertext is generated based on an initial embedding of predicate features. A machine learning process is iteratively executed, on the sets of entity ciphertexts and the predicate ciphertexts, to update embeddings of the entity features of the encrypted entities and update embeddings of predicate features of the encrypted predicates, to generate a computer model for embedding entities and predicates. A final embedding is output based on the updated embeddings of the entity features and predicate features of the computer model.

Graph based embedding under fully homomorphic encryption

A computer-implemented method including: receiving a list of ciphertexts, wherein a majority of ciphertexts in the list homomorphically-encrypt zero values and a minority of ciphertexts in the list homomorphically-encrypt non-zero values; and compressing the list of ciphertexts to remove the ciphertexts which homomorphically-encrypt zero values, wherein: the compression is performed without knowledge on what each of the ciphertexts in the list encrypts, and the compression is based on homomorphic comparison of each of the ciphertexts in the list with a homomorphically-encrypted zero value, to determine which of the ciphertexts in the list to remove.

Growing community of inventors

Nes Ziyona, Israel

Guy Moshkowich