3
$\begingroup$

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.

$\endgroup$
  • $\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 Oct 14 '16 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 Oct 14 '16 at 7:13
5
$\begingroup$

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

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

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.