# 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>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