2
$\begingroup$

Let $n, q, \sigma$ be the polynomial degree($x^n+1$), coefficient modulo, and the standard derivation, respectively. I often see some parameters such as enter image description here

For RLWE, we can use the CRT to decompose the $\text{RLWE}_{q}$ to some $\text{RLWE}_{q_i}$ for $1\leq i\leq l$, where $q = q_1 q_2\cdots q_l$, then when we consider the security of RLWE, we should take $\log q$ or $\log q_i$ to be considered?

$\endgroup$
1
$\begingroup$

You should consider $\log q$.

Considering that all the other parameters are fixed, the smaller $q$ is, the higher is the security. Even the table in your question is showing this (the table probably supposes that $\sigma$ is a small fixed value).

The hardness of the LWE and RLWE problems increases as the ratio $q / || \text{noise}||$ decreases, i.e., larger noise for the same $q$ makes the (R)LWE harder. You can think about the two extreme cases: if the noise is zero, then you can find the secret $s$ with Gaussian elimination; if the noise is as big as $q$, then it is essentially impossible to find $s$ because everything will be (very close to) uniform.

So if you take your (R)LWE samples $(a, b)$ defined mod $q$ and reduce mod a smaller $q'$ (that divides $q$), your new samples have the same noise terms, but with respect to a smaller modulus, so the ratio $q' / || \text{noise}||$ is smaller and the (R)LWE instance that you get is harder.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.