I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 10, 11):

When $q$ is odd, while it is possible to use the above methods to agree on a bit derived by rounding a uniform $v \in \mathbb{Z}_q$, the bit will be biased, and hence not wholly suitable as key material.

I don't understand the biased part and how it is related to $q$ being odd or even. Any help would be appreciated.

  • $\begingroup$ I edited the title of your question to more closely reflect what the question is about. I hope this is fine. $\endgroup$
    – Guut Boy
    Commented Oct 14, 2016 at 7:09
  • $\begingroup$ @GuutBoy It is good. Thank you. Can you please edit the title of my other question as well (my english isn't good): crypto.stackexchange.com/questions/40668/… $\endgroup$
    – Node.JS
    Commented Oct 14, 2016 at 7:13

1 Answer 1


What Peikert is saying here is that you can generate a random bit $b$ by first picking a uniformly random number $v \in \mathbb{Z}_q$, and then setting $b = 0$ if $v \leq q/2$ and $b = 1$ if $v > q/2$.

However, when $q$ is odd there is one more number in $\mathbb{Z}_q$ that is smaller than $q/2$ than there numbers that are larger than $q/2$. I.e., the bit will be slightly biased towards zero.

Put in other words, the probability of $b=1$ will be $\frac{\lfloor q/2 \rfloor}{q}$ and the probability of $b=0$ will be $\frac{\lceil q/2 \rceil}{q} = \frac{\lfloor q/2 \rfloor + 1}{q}$.

Note: Actually, Peikert seems to be using a slightly different "rounding" method. But the same argument applies. You would have more numbers mapping $b$ to $0$ than $1$ (or the other way around).

  • 1
    $\begingroup$ Exactly. (There's a little typo in your "ceiling" case: it should be "floor" plus 1.) $\endgroup$ Commented Oct 13, 2016 at 23:44
  • $\begingroup$ There was actually a typo in both cases but it should be fixed now. $\endgroup$
    – Guut Boy
    Commented Oct 14, 2016 at 2:11

Your Answer

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

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