STAP use-cases: Fully Homomorphic Encryption

Homomorphic Encryption (HE) is an advanced cryptographic technique that allows users to evaluate any circuit on encrypted data without decrypting it.

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.

Applications

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.

STAP Lounge

The STAP Wiki currently collects information about the following list of STAP primitives used in FHE:

                            ◊ LowMC

  • Designers: Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner.
  • Article: Ciphers for MPC and FHE, EUROCRYPT 2015.

LowMC is a family of flexible block ciphers based on an SPN structure defined over F_2. It is designed to be used in the context of an MPC protocol, ZK or HE scheme.

To reduce its multiplicative complexity, LowMC leaves part of the substitution layer as the identity mapping; reducing the number of Sboxes applied in parallel. It then introduces a high degree of diffusion by using pseudorandomly generated binary matrices in the linear layer in order to reach the claimed security.

The authors propose a wide range of different instantiations corresponding to 80, 128, and 256-bit security.

Cryptanalysis

Recent cryptanalysis proposes an algebraic meet-in-the-middle attack on LowMC, reducing the memory and time complexities over previous attacks that retrieve the full key from a differential trail. As a consequence, some LowMC instances could be broken for the first time.

Implementation

The authors report on experiments when evaluating LowMC with MPC protocols and with FHE.

In the case of MPC, they provide GMW benchmarking results in the semi-honest setting for a single block and for multiple blocks in parallel to encrypt 12.8 Mbit of data. The security parameters are set to 80-bit for lightweight security and to 128-bit for long-term security. The experiments are run on two desktop PCs, each equipped with an Intel Haswell i7-4770K CPU with 3.5 GHz and 16GB of RAM, that are connected by Gigabit LAN.

For FHE, they implement LowMC using the holomorphic encryption library HELib.

  • Designers: 
  • Article: 

Description, relations, special features

Sbox, round function, pics

keyboard_arrow_up