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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.