# Proving these two distributions are the same for LWE reduction

As part of a reduction I'm trying to construct, I want to show that the two terms described at the bottom are identically distributed, but I'm not sure if this is correct and I cannot seem to prove that it is formally. I was trying to formulate my reduction similarly to MIT's reduction at the top of p.5 of this pdf.

Denoting by $$\in_R$$ a random uniform choice from a set, let:

$$A\in_{R} \mathbb{Z}^{m\times n}_q$$

$$r \in_{R} \{0,1\}^m$$

$$l, s \in_{R} \{0,1\}^n$$

$$k \in_R \{0,1\}$$

Then the following are identically distributed:

$$(r^T A +\frac{q}{2} l, r^T As+r^Te+\frac{q}{2}k)$$ $$(r^T A, r^T As+r^Te)$$

where $$e$$ is the error term used in LWE.

I tried computing, for example, $$\Pr[r^TA+\frac{q}{2}l+r^Te=a]$$ for some value $$a$$ in order to show that it is equal to $$\Pr[r^TA+r^Te=a]$$, but that wasn't fruitful.

I can say that the two decrypt to the same value. Does that help somehow?

## 1 Answer

I'm not fully clear on what you're trying to do here. Usually with LWE constructs, we try and show that things are computationally indistinguishable rather than identically distributed. Also the person attempting to distinguish typically has access to $$A$$ in which case with good probability, there's a very simple distinguisher for your problem. We compute $$A^{-1}$$ (which exists with good probability) and then given a sample $$(x,y)$$ we compute $$xA^{-1}$$. If this consists only of zeros and ones then with overwhelming probability it is sampled from the second set and if not all zeros and ones it is definitely sampled from the first set.