A Simple Provably Secure Key Exchange Scheme Based on the LWE

Question

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!

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.