Regev's Public Key Cryptosystem is defined as follows:

enter image description here

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?


1 Answer 1


This is largely correct though your second case also needs the two-sided bound $$\lfloor\frac p2\rfloor-\frac{\lfloor\frac p2\rfloor} 2<b-\langle\mathbf a,\mathbf s\rangle<\lfloor\frac p2\rfloor+\frac{\lfloor\frac p2\rfloor} 2$$ whereas your argument only covers the left-hand inequality. Instead, if we just note that $$-\frac{\lfloor\frac p2\rfloor} 2<\sum e_i<\frac{\lfloor\frac p2\rfloor} 2$$ with very high probability (whether we can say this with certainty depends on $\chi$) and then note that $\lfloor\frac p2\rfloor+\sum e_i=b-\langle \mathbf a,\mathbf s\rangle$ then everything follows neatly.

  • $\begingroup$ Thanks for your great answer! Unfortunately the absolute value makes it more complicated in the second case. If you omit it and use the inequality of $\sum e_i$, as you also suggest, then the result is really easier to see. It would be interesting to see if one could also derive the other side of the inequality by solving for the absolute value at the top of my calculation. $\endgroup$
    – P_Gate
    Commented Nov 25, 2022 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.