Adventures in Making Arbitrary Computation with Fully Homomorphic Encryption a Practical Reality
A core privacy preserving technology for computing on data while it is encrypted is Homomorphic Encryption (HE). This is a form of encrypting data that allows users to share their sensitive data in encrypted form, perform computation on the data (for example, within the cloud on an unsecure system) without ever decrypting it, finally allowing decryption and distribution of the computation results to only selected participants. OpenFHE is the next generation open-source library for building systems based on homomorphic encryption. Duality uses OpenFHE as the core cryptography library for its privacy preserving data collaboration platform. Users of the Duality platform can perform various forms of analysis (data base queries, statistics, training of machine learning models) on sensitive data that would not otherwise be made available for shared processing due to various legal limitations (such as being held in different countries, each with its own various data privacy laws). Encrypting the data and processing it while encrypted, allows the information to cross borders, and be processed in the cloud (even on unsecured systems) and satisfies all the various privacy laws simultaneously. This ability comes at a cost though. Computation on, and storage of homomorphically encrypted data is typically at least an order of magnitude larger than computation or storage in the clear.
HE is implemented as one of several co-existing “schemes”, all labeled with the initials of the researchers that first published the approach. One fundamental restriction that currently exists, is that in all HE schemes, one needs to identify the base data type to use for all math. We’ll do a quick summary of the schemes supported in OpenFHE based on the underlying data types supported.
The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes use modulo integer encoding, where all plaintext numbers are limited to the range of unsigned numbers [ 0 .. q-1] or signed numbers [-q/2 .. q/2-1], where q is an integer chosen sufficiently large by the user so that all operations in their application are performed without having any intermediate value or final output exceed the bounds of the above range.
The Cheon-Kim-Kim-Song (CKKS) is a scheme where floating-point data is mapped to an approximate representation that is not bounded, but rather is restricted in accuracy (# bits of accuracy).
TFHE and FHEW are two similar schemes where encrypted data is typically a single bit (or as a new feature in OpenFHE, a very small integer). We collectively call these schemes BinFHE (short for “Binary FHE”) in OpenFHE. Where BGV, BFV and CKKS all allow us to encrypt a vector of data into a single ciphertext, TFHE/FHEW deals with single bit ciphertexts.
BGV, BFV and CKKS are all vectorized schemes, meaning that they allow us to encrypt an entire vector of data into a single ciphertext, and perform math operations on these encrypted vectors with one function call. The operations include vector addition, element wise (Hadamard) vector multiplication, and rotation of the vector (i.e., circular shifting the entries of the vector). In general, the encrypted vector is of a length that is typically a power of two related to the parameters used when the scheme is set up. Arbitrary-length vectors are zero padded before encryption.
One more twist: The number of multiplication operations that can be performed on a ciphertext is limited based on parameters specified at run time. The more sequential multiplications that a particular data path has (referred to as multiplicative “depth”), the larger the ciphertext, and longer the computation time must be. Eventually, a limit is reached, and one must execute a “bootstrapping” function. Ciphertexts all contain some encryption “noise”, and this noise will increase in the result of each multiplication operation. The depth is the limit after which the noise becomes too large for us to successfully decrypt the ciphertext. Bootstrapping basically resets the encryption noise accumulated in a ciphertext after multiple encrypted computations. Bootstrapping is very computationally intensive and is only used in systems with very large computational depth requirements.
Note that there are operations that are missing from those we would expect from a general-purpose computer. There is no division, no nonlinear functions, and no user-level comparison operations. To get around this, researchers have implemented missing functions using polynomial and other numerical approximation techniques. Computing comparison using the polynomial approach has several challenges, e.g., the input range must be known in advance, and a high multiplicative depth (large-degree polynomial) is needed. Simply determining if x is greater than y when both are encrypted has only recently been accomplished by converting vector ciphertexts into vectors of Boolean ciphertexts and performing the comparison in that scheme.
The BinFHE schemes allow us to perform most two-input-one-output Boolean gate operations in encrypted form. Since their input and output ciphertext encrypts a single bit, they can perform bootstrapping in a way that is much more efficient than the vector schemes – to the point where most implementations perform bootstrapping after every gate computation. A sufficient set of Boolean operations are supported in OpenFHE that enable us to implement any arbitrary combinatorial circuit, limited only by the size of the system memory, and the patience of the user running the code.
With BinFHE, the computation of a comparison is achieved in a straightforward manner.
Figure 1 shows the digital logic circuit that performs the three comparison operations: greater than, less than, and equal for two four-bit inputs. It can be easily extended to larger integers. However, implementing this circuit directly into a Boolean scheme is not easy. There are three approaches we could use:
I would design the circuit, break it down into gates and nodes (i.e., wires), each node being a one-bit ciphertext and each gate being the appropriate OpenFHE call for the particular gate. Then systematically lay out the code (going left to right, top to bottom) that will execute the circuit using OpenFHE calls. Trust me, this is both tedious and error-prone, and is not practical for circuits of any significant size.
I could write code that reads in a circuit description from a file (consisting of labeled nodes and gates) and automagically generates and executes the OpenFHE calls for each gate in the correct order. This is a non-trivial piece of code, but if you want to kick the tires, fortunately I have already written it. It is available as an example application in the PALISADE repository at will soon be available for OpenFHE. While there are some big circuits in the repo, the data I/O is still basically limited to a small number of simple integers of fixed bit-width (i.e., one or two inputs, and one or two outputs).
The Google Transpiler is a new open-source tool written by our collaborators at Google that will translate C++ code into hardware design language (HDL) code that describes the functionality of the original code as a digital circuit. It can then execute the circuit in encrypted form using one of multiple cryptographic libraries, but I will focus on our experiences with OpenFHE.
The Google Transpiler is a new system that converts a subset of C++ into a Boolean circuit and integrates OpenFHE’s Boolean schemes as a computational backend to evaluate the circuits with encrypted inputs and outputs. Generally, you write your application using a specific subset of C++ (the limitation is that not all C++ code can be converted to a static combinatorial digital circuit). You specifically encode/encrypt your sensitive input data and specify functions that will be converted to encrypted operations.
The system can be compiled into a “cleartext” form where all variables are encoded into bits, and the resulting circuits executed in the clear. This runs fast, and lets you confirm the correctness of your system. With a small number of changes, this code can be converted to an encrypted form. Running in encrypted form encodes and encrypts the C++ variables as vectors of encrypted bits and executes the functions using OpenFHE calls to the various gates. The conversion of C++ into gates happens under the hood, and you can easily generate very large circuits with little effort. Furthermore, Google has incorporated the Yosys open-source HDL tool chain to generate efficient circuits for execution and included an “interpreted mode” that executes the encrypted gates in parallel across all available cores in your system.
The transpiler supports signed and unsigned integers, shorts, and chars, as well as bool. These are represented internally as vectors of ciphertexts (each encrypting one bit). Floating point is not currently supported, nor is pointer arithmetic. The power of the transpiler becomes apparent when you look at larger, more complex data structures that are supported. You can specify fixed-length multi-dimensional vectors and arbitrary structures. The transpiler takes care of all the bookkeeping that keeps all the underlying ciphertexts straight.
I built a graph processing application that computes a shortest path. In this application we take two data structures which contained an unsigned integer field called “cost” and a vector of unsigned integers representing a path through a series of nodes in a graph. The goal is to select the struct with the smallest cost. This can be applied sequentially across multiple input paths, allowing us to select a path with the smallest associated cost, solving a shortest path problem.
The structure is defined with conventional C++ code in Figure 2. Some observations: Since the data is going to be encrypted, we must define the vector as a fixed-length array and store the actual length of the array that contains valid data. Otherwise, if the array was allowed to be dynamic, the length of the vector (based on the number of encoded ciphertexts) would be visible. Internally, an encrypted PathStruct is stored as a vector of 1000 Ciphertexts (one unsigned int is 32 bits, so the entire structure is 32 + 8 + 30 * 32 = 1000 bits). One of the beauties of the Google Transpiler is that it takes care of the underlying ciphertext management. Doing this by hand-coding would be very cumbersome (and error-prone).
The encrypted function is listed in Figure 3. It takes two encrypted input Path Structs and returns a copy of the one that has the smallest cost.
Some more observations: the result of the cost comparison is captured in the bool chooseNew. We need to copy every element of the lowest cost struct, one by one into an output copy using the conditional ternary operator a?b:c. The first #pragma statement tells the Google Transpiler that this is the entry point of the transpiled code, The transpiled function can consist of several function modules specified in the same files, but the entry point needs to be explicitly called out. The second #pragma statement indicates that the loop must be unrolled before it is converted to logic gates (generated circuits are always combinatorial, not sequential). A word of caution, unrolled loops generate duplicate code for every instance, so double unrolled loops can lead to extremely large circuits!
The top-level code for cleartext execution mode is shown in Figure 4. Instead of encrypting ciphertext, we make encoded versions of PathStruct, encode our data as plaintext bits, and execute the transpiled function in the clear.
The transpiled circuit execution is the select_path() function call, wrapped with the XLS_CHECK() function in order to provide some error checking in case the execution fails. Notice the return value is added as a final parameter in the function call. Running code in this mode quickly verifies that the functionality is correct.
The top-level code for OpenFHE mode (encrypted) is shown in Figure 5 and is very similar to the Cleartext version with the following additions. An OpenFHE Crypto-context and the generation of keys are required at the beginning of the program. The secret key is used to encrypt and decrypt the data (OpenFHE currently only supports symmetric key operation for Boolean schemes, with public/private key operation slated for the next major release). In a real-world application, one program would use the secret key to encrypt and decrypt ciphertexts, transmitting them to a different application which performs the computation (without knowledge of the secret key). The “encoding” and “decoding” operations in the code are replaced with “encrypt” and “decrypt” operations that require the secret key sk. The circuit execution of the function select_path() is identical except for the addition of the crypto context as a parameter).
The operation counts of the circuit generated by the transpiler for select_path() is summarized in Table 1. It consists of 2214 internal nodes (wires) which correspond to individual one-bit ciphertexts. The I/O (three copies of PathStruct) consists of 3000 ciphertexts. Internally there are 3159 encrypted gates calls to OpenFHE bingate calls. Imagine generating this code by hand!
The OpenFHE team is working closely with Google to improve both OpenFHE’s BinFHE implementation and the transpiler itself. Our eventual goal is to work towards enabling a wider array of data types, such as mixing Boolean integer and approximate floating-point schemes under the hood to support more efficient operations. The OpenFHE team is currently working on being able to convert between CKKS and FHEW ciphertexts, allowing users to compute on floating point data, and perform comparison operations as well. This will enable implementation of valuable applications such as decision trees. We are also working to increase the number of Boolean gate components supported by OpenFHE, which will lead to even more efficient circuit implementations.
Meanwhile we are using the Google Transpiler to explore encrypting other algorithms for new application domains. Stay tuned for future blog posts on this subject – or, join the OpenFHE community here.
