A Simple Provably Secure Key Exchange Scheme Based on the LWE 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&gt;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:


How does the author derive the condition that Lemma 2 is true for $q\gt 8$?  
How does $|y+ \sigma$ $\frac{(q-1)}{2} \mod q| \le \frac{q}{4}+1$?    
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!
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.