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$.

  • $\begingroup$ I haven't read the paper but I believe the usual thing to do is to use the regular bit representation of the (unsigned) numbers in $\{0, \ldots, q-1\}$, and then use that for $x \in \{-q/2,\ldots ,-1\}$ you have $x$ reduced modulo $q$ is $q-x$. I.e., in a sense you use the numbers $\{q/2, \ldots, q-1\}$ to represent the negative numbers. $\endgroup$ – Guut Boy Sep 11 '16 at 13:44

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.

  • 1
    $\begingroup$ For more illustration and some instances find this $\endgroup$ – caesar Aug 13 '16 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.