International Business Machines Corporation

Nir Drucker

Hayim Shaul

Ehud Aharoni

Allon Adir

Omri Soceanu

Ramy Masalha

Gilad Ezov

Ronen Levy

Eyal Kushnir

Guy Moshkowich

Lev Greenberg

Dov Murik

Akram Bitar

Michael Mirkin

Tomer Pelleg

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

Reducing homomorphic encryption (HE) rotations is provided. Input of a source tensor of HE ciphertexts is received and a mapping of elements from the source tensor to a target tensor. For each ciphertext, a vector of required rotations is computed according to the mapping plus a list of unique rotations. A first and second list of rotations are generated which have a combined number of rotations less than the list of unique rotations. For each rotation in the first list a ciphertext vector is computed that holds selected elements cyclically rotated by that rotation. For each rotation in the second list a subset of elements is selected from the ciphertext which is summed with ciphertext vectors generated according to the first list. A rotated ciphertext is generated from this sum rotated by the rotation in the second list. Rotated ciphertexts are summed, and the target tensor is output.

Reducing homomorphic encryption rotations when reshaping a ciphertext

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

An example system includes a processor to mask a ciphertext using four random elements to generate masked ciphertexts. The processor can send the masked ciphertexts to a server device. The processor can receive masked plaintexts from the server device. The processor can unmask the masked plaintexts using the four random elements to generate unmasked plaintexts.

Masking ciphertexts using random elements for secure decryption

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

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

A computer-implemented method comprising: generating, from a key-seed associated with a user, a set of homomorphic encryption (HE) keys associated with an HE scheme; receiving, from a key management system (KMS) associated with said HE scheme, an encrypted version of said key-seed; storing said encrypted version of said key-seed, and said set of HE keys, in an untrusted storage location; and at a decryption stage, decrypting an encrypted computation result generated using said HE scheme, by: (i) recalling, from said untrusted storage location, said encrypted version of said key-seed, (ii) providing said encrypted version of said key-seed to said KMS, to obtain a decrypted version of said key-seed s associated with said user, (iii) generating, from said received decrypted version of said key-seed, a secret HE key associated with said HE scheme, and (iv) using said secret HE key to decrypt said encrypted computation result.

Homomorphic encryption key management

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

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 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.

Growing community of inventors

Zichron Yaakov, Israel

Nir Drucker