In this paper (A simple provably secure key exchange by Ding et al.), I am trying to understand the correctness (which is given on page number 8) of the key exchange technique based on LWE.

To understand the correctness of the scheme, there is a very important lemma (on page number 6). The lemma is as follows:

Lemma 2. Let $q>8$ be an odd integer, the function $E$ defined above is a robust extractor with respect to $S$ with error tolerance $\frac{q}{4}-2$.

I'm confused by the proof of Lemma 2:

  1. How does the author derive the condition that Lemma 2 is true for $q\gt 8$?
  2. How does $|y+ \sigma$ $\frac{(q-1)}{2} \mod q| \le \frac{q}{4}+1$?
  3. At the end of the proof of Lemma 2, the author writes that

Our robust extractor enjoys a very nice property which says that for uniformly random $x\in$$ \mathbb{Z} _q$, $E(x, \sigma$) is uniform in $\{0,1\}$ even conditioned on $\sigma$, where $\sigma \leftarrow S(x)$.

This property becomes Lemma 3 of this paper.

Can anyone answer the above three questions and thus the proof of Lemma 2 and Lemma 3? Thanks!


1 Answer 1


Lemma 3 in this paper gives a better explanation regarding to your question 1 and 2.

For a simple answer for question 3, because we have equally divided region, this gives us even change on $k_i$ and $k_j$ be even or odd number, thus the output of function $E$ is uniform random.

  • $\begingroup$ $\mathbb{Z} _q$ used in the above paper is not the mathematical $\mathbb{Z} _q$ whose range is [-(q-1), (q-1)]. But it is a $\mathbb{Z} _q$, whose range is [$\frac{-(q-1)}{2}$, $\frac{q-1}{2}$] $\endgroup$
    – vivek
    Jun 13, 2017 at 4:58
  • $\begingroup$ Also, v+Cha(v)*$\frac{q-1}{2}$ mod q $\le$ $\lfloor$$\frac{q}{4}$$\rfloor$. But in the above paper(paper link given by me), |y+$\sigma$ $\frac{q-1}{2}$ mod q| $\le \frac{q}{4}$+1. The v+Cha(v)*$\frac{q-1}{2}$ mod q $\le$ $\lfloor$$\frac{q}{4}$$\rfloor$ seems correct but i am not able to understand |y+$\sigma$ $\frac{q-1}{2}$ mod q| $\le \frac{q}{4}$+1. $\endgroup$
    – vivek
    Jun 13, 2017 at 5:16
  • $\begingroup$ I think $\sigma_0$(x)=0, x$\in$ [-$\lfloor$$\frac{q}{4}$$\rfloor$, $\lfloor$$\frac{q}{4}$$\rfloor$] is rather $\sigma_0$(x)=0, x$\in$ [-$\lfloor$$\frac{q}{4}$$\rfloor$, $\lfloor$$\frac{q}{4}$$\rceil$] in the above paper(paper given by me). Please comment. Thanks! $\endgroup$
    – vivek
    Jun 13, 2017 at 5:24
  • $\begingroup$ @vivek output of Cha() is either output of function $\sigma_0$ or $\sigma_1$. I think the paper is clear. $\endgroup$
    – 9f241e21
    Jun 15, 2017 at 2:52
  • $\begingroup$ @ 9f241e21 I am saying that closed interval should be [-$\lfloor$$\frac{q}{4}$$\rfloor$, $\lfloor$$\frac{q}{4}$$\rceil$] rather than [-$\lfloor$$\frac{q}{4}$$\rfloor$, $\lfloor$$\frac{q}{4}$$\rfloor$]. I verified this but substituting different values. Thanks $\endgroup$
    – vivek
    Jun 15, 2017 at 8:39

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.