Optimizing the communication cost when using homomorphic encryption

Scenario

In typical applications of homomorphic encryption, one of the first steps consists for a user, let's call her Alice, to encrypt her data $m$ under a public key $\textsf{pk}$ and send the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ to someone else, e.g. to the Cloud (see Fig. 1).

Fig. 1. Alice sends her data $m$ encrypted to the Cloud, which publicly performs an operation $f$ on it.

The Cloud then performs publicly a function $f$ on the data, and sends back the result to Alice. Unfortunately, even the most recent homomorphic encryption schemes (e.g. BGV or GSW) are such that the size of the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ is much larger than the size of $m$. Typically, to encrypt a 4MB image, the ciphertext will end up being at least 1 GB long!

Using an Hybrid Approach

In 2012, Michael Naehrig, Kristin Lauter and Vinod Vaikuntanathan suggested to use the following hybrid approach: encrypt the message $m$ under a scheme with no ciphertext expansion (i.e. the ciphertext will have the same size as $m$), e.g. under the Advanced Encryption Standard $\hat c = \textsf{AES}_k(m)$ for a key $k$, and send to the Cloud $(\textsf{Enc}(\textsf{pk}, k), \hat c)$. Now, the communication cost becomes the cost of sending $\hat c$ (same size as $m$) and sending only once $\textsf{Enc}(\textsf{pk}, k)$, which is independent of the data $m$, i.e. is quasi-optimal.

The Cloud has now to perform the $f\circ \textsf{AES}^{-1}_k$ instead of $f$ to publicly compute the expected result as in Fig. 1.

This solution was first implemented by Craig Gentry, Shai Halevi and Nigel Smart in 2012 (Nigel Smart is a member of the HEAT project). Recent timings (from early 2015) demonstrates the possibility to evaluate only $\textsf{AES}^{-1}_k$ (i.e. taking parameters to evaluate the latter function but nothing else) in less than 7 minutes on a classical laptop.

However, this approach has several drawbacks. First, AES was not at all designed in a context of homomorphic cryptography: the operations are not easily parallelizable, the multiplicative depth is large: AES does not appear to be particularly well suited for homomorphic evaluations. Second drawback, the latency of the homomorphic evaluation of $\textsf{AES}^{-1}_k$ is added to the latency of the homomorphic evaluation of $f$: in other words, the data will be homomorphically processed upon after being homomorphically decrypted (i.e. 7 minutes later!).

Block Ciphers for Homomorphic Evaluations

The first drawback has been investigated in a series of work (LN14, DSES14...), trying to replace AES by lighter primitives such as SIMON or PRINCE: the resulting homomorphic evaluations have a much smaller latency. Au EUROCRYPT 2015, Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner presented a new family of block cipher especially designed for homomorphic encryption called LowMC (see also our blog article about EUROCRYPT). Designed to have a shallow decryption circuit (multiplicative depth of 11), they performed much better than previous approaches. Unfortunately, LowMC was broken soon after its publication because of weaknesses inherent in its low multiplicative complexity.

Revisiting the Whole Hybrid System

In 2015, partly founded by the HEAT project, Tancrède Lepoint and Pascal Paillier from CryptoExperts together with Anne Canteaut, Sergiu Carpov, Caroline Fontaine, María Naya-Plasencia and Renaud Sirdey proposed to revisit the hybrid system entirely to tackle both drawbacks mentioned earlier in an article available on the Eprint archive. The key idea is to identify that the homomorphic "decompression" phase is subject to an offline phase and an online phase. The offline phase is plaintext-independent and therefore can be performed in advance, whereas the online phase completes decompression upon reception of the plaintext-dependent part of the compressed ciphertext. 

Using the notation of above, the offline phase consists in sending $\textsf{Enc}(\textsf{pk}, k)$ because this value does not depend on the data. And the online phase consists in sending the data $m$ encrypted under the key $k$.

The second drawback presented earlier is that the online phase has a long latency. Making the online phase as quick as technically doable leads us to choose an additive IV-based stream cipher instead of AES. Therefore the system performs as in Fig. 2.

Fig. 2. When receiving the encryption $\textsf{Enc}(\textsf{pk}, k)$ of the symmetric key $k$, the Cloud can perform during the offline phase (i.e. before getting any data $m$) the generation of the keystream using a stream cipher adapted to current homomorphic encryption constraints. Therefore the latency of the online phase is minimal: when receiving the one-time padded message $m\oplus\textsf{keystream}$, the Cloud can homomorphically and very efficiently evaluate the XOR to obtain $\textsf{Enc}(\textsf{pk}, m)$.

To accelerate the offline phase (and tackle the first drawback), we propose our own stream cipher candidates adapted to homomophic encryption : the keystream generator Trivium, which belongs to the eSTREAM portfolio of recommended stream ciphers, and a new proposal called Kreyvium, which shares the same internal structure. The main advantage of Kreyvium over Trivium is that it provides 128-bit security (instead of 80-bit) with the same multiplicative depth, and inherits the same security arguments. 

Finally, we show that the promising performances obtained by LowMC can also be achieved with Trivium, a well-known primitive whose security has been thoroughly analyzed, and by Kreyvium. The 10-year analysis effort from the whole community, initiated by the eSTREAM competition, enables us to gain confidence in its security. Also our variant Kreyvium, with a 128-bit security, benefits from the same analysis since the core of the cipher is essentially the same. Also the Cloud can also exploits the highly parallel structure of Trivium and Kreyvium to speed up the homomorphic evaluation.