Correctness Proof of GLWE-based Encryption26 Jul 2016
While reading a GLWE-based encryption described in section 3.1 of BGV12. The paper says that correctness is obvious and it only became obvious to me after a bit. This should cover most of the proof outline.
Proof: We have to show that the dot product of and reduces to the message. Let , , and be the th element in , , and respectively. We will zoom in the construction of as a start. Remember that it’s defined as . I will notate to be the element of the matrix .
We have . + =
Now performing the dot product we get: Note that in we can neglect to compute our message since it’s . For any we have the term to be equal to the inner summation module 2. Thus, we will be left with .