Almost Random because randomness is hard

Correctness Proof of GLWE-based Encryption

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 .