I'm going through the BGV paper and trying to make a toy implementation, but I just want to focus on Ring-LWE. In the paper, they set $N = \lceil{(2n + 1)\log_2(q)\rceil}$, and generate $A'$ uniformly from $R_q^{N\times{n}}$. From what I can tell, they do this because they focus on the GLWE problem. While reading some other papers(such as the standard paper from homomorphicencryption.org), I notice they seem just sample from $R_q$ instead of $R_q^{N\times{n}}$.

Is it necessary to sample from $R_q^{N\times{n}}$, or is it sufficient to just sample from $R_q$? If the latter, why does BGV suggest the former?

BGV Paper


Your Answer


Browse other questions tagged or ask your own question.