Introduction

The proliferation of ubiquitous computing and the recent advances in cloud services have amplified the reliance of millions of users to outsourced computation and storage for their data. Remote servers across the globe are becoming the virtual containers of sensitive data, from banking records and medical information to file storage and search queries. Numerous benefits of outsourcing, however, are often matched with several limitations in security and privacy guarantees offered to the end users.

As with most data confidentiality problems, modern cryptography offers a wide range of primitives that can protect outsourced computation against known, or yet unknown, attacks. In the most common cases, cryptography is leveraged to protect data at rest, such as remote backups, as well as data in transit, such as network communications with remote servers. Nevertheless, the use of cryptography primitives while data are being manipulated inside processor pipelines (i.e., data in use) has been limited so far, since modern computer architectures, such as x86 and ARM, are unable to process encrypted values natively. E3 is developed based on the thesis that cryptography protections need to be retained through the lowest levels of computation stack, since any leakage or privacy violation would be meaningless as long as data remain encrypted.

One compelling solution that allows native manipulation of encrypted values within processor pipelines is the use of a cryptosystem that has homomorphic properties. Indeed, following the breakthrough discovery of fully homomorphic encryption (FHE), if sensitive data are protected using FHE, it is possible to apply any algorithm directly on ciphertext values so that the decrypted final output would be the same as if the original algorithm was applied on the plaintext values. In this case, critical data are never decrypted, even within the processor pipeline, so any data leakage or side-channel attack is meaningless: user privacy is always preserved due to the semantic security of encryption.

Encrypt-Everything-Everywhere (E3) computation paradigm allows non-crypto-savvy developers to effortlessly incorporate data privacy in their programs. Specifically, E3 offers secure cryptographic libraries that define new datatypes to selectively protect critical variables using end-to-end encryption for numerous real-life applications.

+-----------------+                           +------------+
|                 |       send bob.exe        |            |
|      Alice      | +-----------------------> |    Bob     |
|                 |                           |            |
|  My C++ project |          result           |  untrusted |
|  E3 framework   | <-----------------------+ |            |
|                 |                           |            |
+-----------------+                           +------------+

E3 is designed to work in the following scenario: The end user (Alice) employs E3 to compile a C++ program with encrypted data and send it to Bob for execution. Bob runs the executable and sends the result back to Alice. Alice decrypts the result.

  +----------------------------------------------------------+
  |                                                          |
  |                           E3                             |
  |                                                          |
  +------+--------------------+---------------------+--------+
         |                    |                     |
         v                    v                     v
      +--+---+          +-----+------+        +-----+------+
      | make |          | amalgam.sh |        | amalkey.sh |
      +--+---+          +-----+------+        +-----+------+
         |                    |                     |
         v                    |                     v
    +----+----+               |               +-----+------+
    | cgt.exe |               |               | cgtkey.cpp |
    +----+----+               |               +-----+------+
         |                    |                     |
         |                    |                     v
+-----------------------------------------+     +---+-------+
|        |                    |           +---->+ alice.exe |
|        v                    v           |     +-----------+
|  +-----+------+     +-------+-------+   |
|  | secint.cpp |     | cgtshared.cpp |   |
|  +------------+     +---------------+   |
|                                         |
|   +---------+                           |
|   | My C++  |                           |       +---------+
|   | project |                           +------>+ bob.exe |
|   +---------+                           |       +---------+
|                                         |
+-----------------------------------------+

Programming support for the E3 computation paradigm is provided through a set of software libraries and helper tools. E3 works as follows: Given a C++ user program and a configuration file indicating the FHE scheme to be instantiated, the E3 build tool ('cgt.exe') is generated. This tool builds 'secret key' for decryption and 'evaluation key' needed to execute a compiled binary, and generates the 'Framework API.cpp' (secint.cpp) file that gives access to the new secure datatypes. As the diagram shows, it is possible to build two executables: bob.exe and alice.exe. Alice sends bob.exe to Bob. Alice can use alice.exe to run ancillary functions, i.e. custom encryption and decryption, because alice.exe has access to the secret key, while bob.exe does not.

E3 implements four external FHE libraries: TFHE, FHEW, HElib, PALISADE and SEAL. FHEW and HElib are only supported in Linux. The user can decide which library to use and specify their choice in the configuration file. Different libraries can be used simultaneously, and the same source code can be used for any library - users only need to slightly modify the configuration file.

TFHE implements a variant of the GSW scheme and supports evaluation of any Boolean circuit on encrypted values. Unrestricted circuit sizes are possible by incorporating bootstrapping in the evaluation of eachgate; gate-by-gate bootstrapping reduces the noise of FHE ciphertexts after each operation and allows applying an arbitrary function after the data are already encrypted.

FHEW is a predecessor of TFHE and the first FHE library supporting per-gate bootstrapping using a homomorphic accumulator based on a variant of the GSW scheme. The latest version of FHEW implements a functionally-complete set of bitwise operations on the encryptions of bits, and each ciphertext output is refreshed using bootstrapping to reduce its noise to similar levels as the corresponding inputs. Thus, FHEW enables the homomorphic evaluation of any Boolean circuit on encrypted bits.

HElib implements a ring-LWE variant of the BGV scheme (second generation FHE) with the GHS optimizations. It provides bootstrapping operations to reduce ciphertext noise. HElib is used to compose higher-level functions on multi-bit inputs as circuits (specifically, we implement multi-bit adders and multipliers) and to evaluate integer addition and multiplication, directly using multi-inputs as coefficients of polynomials. It supports modular arithmetic.

SEAL implements two different homomorphic encryption schemes: the BFV scheme and the CKKS scheme. The BFV scheme allows modular arithmetic to be performed on encrypted integers, and the CKKS scheme allows addition and multiplication on encrypted real or complex numbers, but yields only approximate results. SEAL supports batching (packing multiple plaintexts into one ciphertext) in both the BFV and CKKS schemes. It does not use bootstrapping.

PALISADE implements different homomorphic schemes, but in E3 (as of May 2021) only BFV/CKKS are supported.

NOTE: FHEW has internal error (sic) forbidding binary operations on the same bits:

ERROR: Please only use independant ciphertexts as inputs.

E3 also implements BDD, an internally-developed encryption scheme. BDD is developed using an external library called CUDD. It supports full gate operations and full programming via circuits. No bootstrapping is necessary for this scheme since it is sufficiently fast (compared to TFHE).

While TFHE and FHEW libraries provide gates for circuits, gates for HElib, SEAL, and BDD are created using arithmetic equations. Hence, arithmetic addition and multiplication are available and encouraged using HElib, SEAL, and BDD. While arithmetic circuits excel in speed, they have limited operations. The goal is to maximize the use of arithmetic circuits by "bridging" boolean-to-arithmetic conversion.

Many encryption schemes supports modular arithmetic, which defines arithmetic addition, subtraction, and multiplication on numeric rings. However, modular arithmetic supports a very limited set of arithmetic operations (it does not support comparison or division), which severely limits the possible applications of FHE. However, if operations were evaluated on the bit level, then the user can have access to a universal set of operations. In other words, if an FHE scheme supports the logic NAND or NOR gate, which is the elementary gate for all other operations, then it can support universal computation. To support a wider range of operations, E3 provides secure data types called integral types which are made of sequences of bits. Computation using these types is called bit-level arithmetic.

The downside of using bit-level arithmetic is that it is much slower compared to the natively provided modular arithmetic, which operates Mdirectly on ciphertexts rather on the bits. To solve this problem, E3 introduces the novel technique of bridging - mixing both modular and Bit-level arithmetic in one program with the ability to convert variables from integral type to modular. Some variables can be declared as protected types that support only Modular arithmetic while others with the other type supporting Bit-level arithmetic. In bridging mode, a type of Bit-level arithmetic declares a conversion function into a type of Modular arithmetic. Obviously, the encryption of the two different C++ types must share the same keys.

Bridging mode can be set in the configuration file (see Configuration File). Note that SEAL is currently the only HE library that supports bridging.