Regev's Public Key Cryptosystem is defined as follows:
I want to proof the correctness. For this it must be shown that a 0 is decoded correctly and equally that a 1 is decoded correctly. I would present here once my proof:
Case: Encryption of 0
$$b = \sum_{i \in S} b_i = \sum_{i \in S} ( \langle \mathbf{a_i},\mathbf{s} \rangle + e_i)
= \langle \mathbf{a},\mathbf{s} \rangle + \sum_{i \in S} e_i \Rightarrow b - \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i \in S} e_i$$
We know from the definition that $|e| < \frac{\lfloor \frac{p}{2} \rfloor}{2} $ using this fact we can write:
$$|b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \sum_{i \in S} e_i \right| < \frac{\lfloor \frac{p}{2} \rfloor}{2}$$
This is closer to 0 than to $\lfloor \frac{p}{2} \rfloor$, so the decryption of a 0 is correct.
Case: Encryption of 1
$$b = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} b_i = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} ( \langle \mathbf{a_i},\mathbf{s} \rangle + e_i)
= \lfloor \frac{p}{2} \rfloor +\langle \mathbf{a},\mathbf{s} \rangle + \sum_{i \in S} e_i \Rightarrow b - \langle \mathbf{a},\mathbf{s} \rangle = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i$$
Using the triangle inequality we can write:
$$| b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i \right| \geq -\left| \sum_{i \in S} e_i \right| + \left| \lfloor \frac{p}{2} \rfloor \right|$$
Since $-|e| > -\frac{\lfloor \frac{p}{2} \rfloor}{2} $ we can write:
$$| b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i \right| \geq -\left| \sum_{i \in S} e_i \right| + \left| \lfloor \frac{p}{2} \rfloor \right| > -\frac{\lfloor \frac{p}{2} \rfloor}{2} + \left| \lfloor \frac{p}{2} \rfloor \right|$$
And this is closer to $\lfloor \frac{p}{2} \rfloor$ than to 0, so the decryption of a 1 is correct.
I am not sure about the second case of my proof, so I would appreciate a correction or confirmation. Another question is about the limits of decryption. If I'm not misleading, then everything in the range $-\frac{\lfloor \frac{p}{2} \rfloor}{2} < x < \frac{\lfloor \frac{p}{2} \rfloor}{2}$ is interpreted as 0 and everything in the range $\frac{\lfloor \frac{p}{2} \rfloor}{2} < x < \frac{3 \lfloor \frac{p}{2} \rfloor}{2}$ is interpreted as 1, can you say that?
