International Business Machines Corporation

Other

Hayim Shaul

Ehud Aharoni

Nir Drucker

Omri Soceanu

Gilad Ezov

Allon Adir

Ramy Masalha

Eyal Kushnir

Guy Moshkowich

Nathalie Baracaldo Angel

Lev Greenberg

Runhua Xu

Heiko Hary Ludwig

Dov Murik

Evgeny Shindin

Michal Lev

Tomer Pelleg

Ron Lev

Ran Balicer

Mechanisms are provided for performing homomorphic cryptographic operations. The mechanisms receive a specification of a homomorphic encryption (HE) operation to be performed on workloads comprising one or more input ciphertexts and generate a circuit of HE computations for performing the HE operation. The circuit comprises authentication tag checking logic at one or more inputs of the circuit, and nullification logic inserted into the circuit. The nullification logic operates to delete one or more HE encrypted ciphertexts received by the circuit. The mechanisms process the workloads by the circuit of HE computations to generate one or more output ciphertexts that are results of the HE operation executed on the one or more input ciphertexts, which are returned to a source computing system. The nullification logic deletes an input ciphertext of the one or more input ciphertexts when the authentication tag is invalid.

Approximate homomorphic cryptographic operations

An embodiment appends, into a concatenated table, a second plurality of records in a second table to a first plurality of records in a first table. An embodiment sorts, according to each identification value in the concatenated table, the concatenated table. An embodiment generates, using an equality mask derived from each identification value in the sorted table, an intersection table, the intersection table comprising a record in the first plurality of records with a first identifier value matching a second identifier value in a record in the second plurality of records. An embodiment generates, using a not-in-intersection mask derived from the equality mask, a not-in-intersection table. An embodiment adds contents of the intersection table and contents of the not-in-intersection table together, resulting in a join table.

Database table joining under fully homomorphic encryption

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 method, apparatus and computer program product for privacy-preserving homomorphic inferencing using one-hot data representations. In this approach, a client interacting with a cloud-based server submits one-hot maps of a Chinese Remainder Theorem (CRT)-based representation of an data element, and the server expands these maps in an online phase to obtain a full one-hot map for the element. After the server obtains the full one-hot map, it performs an operation, e.g., a comparison operation associated with inferencing on a decision tree, on the one-hot map under homomorphic encryption, and in response generates a result. The result is provided back to the client.

Homomorphic encrypted one-hot maps using intermediate chinese remainder theorem (CRT) maps

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

An example system includes a processor to receive a ciphertext including an encrypted packed plaintext. The processor can, in response to detecting that a reshape is to be executed for a data structure including the packed ciphertext, identify a target shape for the data structure and execute the reshape based on the identified target shape. The reshape is executed using multiplication by an identity element. The processor can then execute a homomorphic computation using the reshaped data structure.

Reshaping data structures for homomorphic computations using multiplication by identity elements

An example system includes a processor to compute a tensor of indicators indicating a presence of partial sums in an encrypted vector of indicators. The processor can also securely reorder an encrypted array based on the computed tensor of indicators to generate a reordered encrypted array.

Secure reordering using tensor of indicators

Mechanisms are provided for performing a tournament selection process of a computer function. A request is received to execute the computer function on an input vector data structure, where a result of the computer function is provided by executing the tournament selection process. The input vector data structure is received, comprising a plurality of values where each value corresponds to a vector slot. An index vector data structure is received that comprises indices of the vector slots of the input vector. Iteration(s) of the tournament selection process are executed to identify a value in the input vector satisfying a criterion of the computer function. An operation is performed on the index vector data structure to generate an indicator vector data structure that uniquely identifies a slot in the input vector data structure that is a result of the computer function being executed on the input vector data structure.

Tournament type selection operations on encrypted data

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

An example system includes a processor to partition an arithmetic circuit representing a homomorphically encrypted (HE) code into a number of execution blocks. The processor can generate, for each of the number of execution blocks, manifests describing access patterns for a number of different machine environments. The processor can then dynamically execute the HE code by selecting successive blocks to execute based on an access pattern calculated for the execution block corresponding to a detected current machine environment.

Execution of homomorphically encrypted code using dynamically selected blocks

A second set of data identifiers, comprising identifiers of data usable in federated model training by a second data owner, is received at a first data owner from the second data owner. An intersection set of data identifiers is determined at the first data owner. At the first data owner according to the intersection set of data identifiers, the data usable in federated model training is rearranged by the first data owner to result in a first training dataset. At the first data owner using the intersection set of data identifiers, the first training dataset, and a previous iteration of an aggregated set of model weights, a first partial set of model weights is computed. An updated aggregated set of model weights, comprising the first partial set of model weights and a second partial set of model weights from the second data owner, is received from an aggregator.

Private vertical federated learning

A method, a neural network, and a computer program product are provided that optimize training of neural networks using homomorphic encrypted elements and dropout algorithms for regularization. The method includes receiving, via an input to the neural network, a training dataset containing samples that are encrypted using homomorphic encryption. The method also includes determining a packing formation and selecting a dropout technique during training of the neural network based on the packing technique. The method further includes starting with a first packing formation from the training dataset, inputting the first packing formation in an iterative or recursive manner into the neural network using the selected dropout technique, with a next packing formation from the training dataset acting as an initial input that is applied to the neural network for a next iteration, until a stopping metric is produced by the neural network.

Neural network training with homomorphic encryption

A method comprising: receiving an input tensor having a shape defined by [n, . . . , n], where k is equal to a number of dimensions that characterize the input tensor; receiving tile tensor metadata comprising: a tile tensor shape defined by [t, . . . , t], and information indicative of an interleaving stride to be applied with respect to each dimension of the tile tensor; constructing an output tensor comprising a plurality of the tile tensors, by applying a packing algorithm which maps each element of the input tensor to at least one slot location of one of the plurality of tile tensors, based on the tile tensor shape and the interleaving stride, wherein the interleaving stride results in non-contiguous mapping of the elements of the input tensor, such that each of the tile tensors includes a subset of the elements of the input tensor which are spaced within the input tensor according to the interleaving stride.

Efficient convolution in an environment that enforces tiles

In response to identifying that a Single Instruction, Multiple Data (SIMD) operation has been instructed to be performed or has been performed by a Fully-Homomorphic Encryption (FHE) software on one or more original ciphertexts, performing the following steps: Performing the same operation on one or more original plaintexts, respectively, that are each a decrypted version of one of the one or more original ciphertexts. Decrypting a ciphertext resulting from the operation performed on the one or more original ciphertexts. Comparing the decrypted ciphertext with a plaintext resulting from the same operation performed on the one or more original plaintexts. Based on said comparison, performing at least one of: (a) determining an amount of noise caused by the operation, (b) determining whether unencrypted data underlying the one or more original ciphertexts has become corrupt by the operation, and (c) determining correctness of an algorithm which includes the operation.

Analysis and debugging of fully-homomorphic encryption

An example system includes a processor that can obtain a circuit describing operations of sequential secure computation code. The processor can modify the circuit based on a cost function. The processor can partition the circuit into a number of sub-circuits. The processor can assign the number of the sub-circuits to different processors for execution.

Growing community of inventors

Kfar Saba, Israel

Hayim Shaul