2
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 '17 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 '17 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 '17 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 '17 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 '17 at 8:39

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.