GSW Homomorphic Encryption

Question

In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $Z_q$ (that is $\{0,1,..., q-1\}$) is used or balanced representation ($\{\lceil - q / 2 \rceil, ..., \lfloor(q - 1) / 2 \rfloor\}$). However, usually in lattice based cryptography a balanced representation is used since random numbers are sampled from truncated discrete Gaussian distribution. My question is, if negative numbers are used (which is the case in the balanced representation) how to perform the Bitdecompose procedure which performs the following: Let $a \in Z_q$ and $l=\lfloor \log_2^q \rfloor+1$, $Bitdecompose(a)=(a_0, a_1, ..., a_{l-1})$, where $a_i$ is the $i$-th bit of the binary representation of $a$.

Answer 1

However, usually in lattice based cryptography a balanced representation is used [...]

Is this true? I'd be interested in seeing some instances in the literature (or implementations) which actually use this representation. In my experience, the literature (such as the paper you linked) assume the ordinary representation of $\mathbb{Z}_q$.

I don't see a practical benefit to using the balanced representation. Random numbers are indeed sampled from a truncated discrete Gaussian centered around 0, and a negative number can easily be added to the value in $\mathbb{Z}_q$. Sometimes this result may be negative, so a $\mod q$ operation needs to be done. But this operation is necessary for whichever representation you use. In the balanced representation, if you add a positive error to $(q-1)/2$ you will need a $\mod q$ operation as well to keep the result in $\mathbb{Z}_q$.

To answer your question, the Bitdecompose procedure can be done by simply adding $\lceil-q/2\rceil$ to $a$ first, which shifts the representation back to normal. Then Bitdecompose is nearly free in practice.

Answer 2

The actual schemes are using $\mathbb Z_q$, but the implementations of those schemes in practice need to be mapped into 0/1 bits.

In the implementation, you need to map the field into 0 and 1. In most cases, this is easily achieved by dividing the field into "positive" and "negative" field, by choosing the first bit of the integer representation, a way to map the field.

If the most significant bit (MSB) equals $1$ then you have the "negative" field, if MSB equals $0$ then you have the "positive" field. This is an easy way to do the mapping in the actual implementations of those schemes.