Score:2

Parameters in RLWE

cn flag
Bob

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?

Score:1
us flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.