Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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).
