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.

Ring-GSW

This post is about a ring variant of the GSW FHE scheme, which has been dubbed SHIELD by its authors. The original paper SHIELD is available here.   What is interesting about the SHIELD scheme is that noise increases less than in other schemes if you multiply a number of fresh ciphertexts together in sequence. In addition there is no $p$ and $q$, but only a single modulus $q$. The plaintext space is the ring $R_q={\mathbb F}_q[X]/\Phi_m(X)$ for some cyclotomic polynomial $\Phi_m(X)$.

However, there are a number of drawbacks which include the fact that the ciphertext consists of many elements of $R_q$ and that whilst messages from the whole of $R_q$ maybe encrypted operating on such messages can be a problem. For example scalar multiplying a ciphertext by an element in $R_q$ will make it undecryptable, or homomorphicallhy operating on encryptions of "non-small" elements of $R_q$ will result in decryption not working due to excessive noise growth. These problems do not occur in systems which have a plaintext modulus $p$ which is much smaller than $q$, such as BGV or YASHE.

As usual we define a secret key as a small element $t$ in the ring $R_q$, and the public key is given by a Ring-LWE tuple with respect to this secret, i.e. a pair $(a,b)$ where $a$ is chosen uniformly at random from $R_q$ and $b=a \cdot t+e$ for some small element $e$ in $R_q$. 

To encrypt we form an $N \times 2$ matrix where $N=2\cdot \log_2 q =2 \cdot \ell$. We pick two matrices consisting of small elements in $R_q$, one $R$ is of dimension $N \times 1$ whilst the other $E$ is of size $N \times 2$. A plaintext $m \in R_q$ is then encrypted via the equation

$$ C =m \cdot B + R \cdot (b,a) + E$$

where $B$ is the $N \times 2$ matrix which is zero everywhere, but has the element $2^i$ in location $(i,1)$ and $(i+\ell,2)$ for $i=0,\ldots,\ell-1$.

To decrypt we multiply $C$ by the vector $(1,-t)^T$ so as to obtain an $N$ dimensional column vector which has $m \cdot 2^i + \mathsf{error}$ in position $i$ and $m \cdot 2^i \cdot t + \mathsf{error}$ in position $i+\ell$. The message $m$  can then be recovered by solving this `trivial' variant of the hidden number problem (an exercise for the reader).

To homomorphically add two ciphertexts we simply add the associated matrices together. To homomorphically multiply ciphertexts $C_1$ and $C_2$ we take $C_1$ and apply a bit-decomposition method to it, the resulting matrix is then multiplied into $C_2$ on the left.  We need to keyswitching etc, so multiplicaton is involved but relatively simple. 

The noise growth for homomorphic addition behaves additively. But the noise growth for homomorphic multiplication behaves as $B_1 \cdot || m_2||_1 + B_2 \cdot n \cdot \log q$ where $B_i$ is a noise bound for ciphertext $C_i$ and $m_2$ is the plaintext underlying $C_2$.  This gives very good noise growth if the messages which are encrypted are very small, e.g.bits, but it is less useful when the messages are from all of $R_q$. Thus whilst we can encrypt messages in the whole of $R_q$, we are unable to perform homomorphic operations on such ciphertexts. Making the benefit of Ring-GSW less than one would immediately expect.