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, 2016 at 13:44

2 Answers 2


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, 2016 at 4:07

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.

  • $\begingroup$ Welcome to Cryptography.se We have $\LaTeX$/MathJax enabled in our site. $\endgroup$
    – kelalaka
    Nov 18 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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