In HE, one data set is transformed into another while preserving the relationships between the elements in both sets. Consequently, mathematical operations produce equivalent results in a HE scheme, whether the operation is performed on encrypted or decrypted data. Fully homomorphic encryption (FHE) is the strongest notion of HE since it allows the evaluation of arbitrary circuits with infinite additions or multiplications for the ciphertext.

As opposed to traditional ciphers built from linear and non-linear building blocks for applications where these two have roughly similar costs in hardware and software implementations, the situation is radically different for ciphers implemented in a HE scheme. In all somewhat and FHE schemes known so far, XOR (addition) gates are considerably cheaper than AND (multiplication) gates. Moreover, XOR gates do not increase the noise much, whereas AND gates do considerably, which is an essential feature in HE schemes as the result should have low enough noise in order to permit decryption.

Hence, ciphers that find a use-case in HE schemes should desirably minimize their use of non-linear operations, while most cryptographically relevant work is performed as linear operations. This design philosophy is related to the fundamental theoretical question of the minimal multiplicative complexity (MC) of certain tasks, which is simply the number of AND gates in a circuit. A second cost metric of central importance within HE schemes is the multiplicative depth of the circuit, which should be low to ensure the efficiency of the evaluation of the cipher.

FHE can be used, among others, in privacy-preserving applications. In the case where privacy-preserving applications based on FHE outsource computations on sensitive data to the cloud, however, it is beneficial to make use of hybrid encryption: Instead of encrypting the client’s data directly with FHE, the client encrypts its data using symmetric encryption, e.g., with a block cipher, and then sends the encrypted data along with the FHE-encrypted symmetric key to the cloud. The cloud then decrypts the symmetrically encrypted data through HE. Using this method, the network communication is lowered to the data size, which is optimal, plus a one-time setup for sending the FHE-encrypted symmetric key.

Another use case is verifiable computing, which allows to outsource computation to untrusted workers (such as the cloud) and verify that the result was computed correctly.