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 1


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.


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.