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.