Processing math: 100%

Tuesday, June 2, 2015

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.


 

No comments:

Post a Comment