Suppose you have an RLWE of degree 4096: a*s+e+\Delta M and a decryption of m and you extract its 4096 lwe coefficients:
b_1 = a.s+e_1+\Delta m_1\to b_1 -\Delta m_1 = a.s+e_1\\b_2 = a.s+e_2+\Delta m_2\to b_2 -\Delta m_2 = a.s+e_2\\\cdots\\b_{4096} = a.s+e_{4096}+\Delta m_{4096}\to b_{4096} -\Delta m_{4096} = a.s+e_{4096}
since you know m, summing everything in the system, you have to search through 4096(e_1+\cdots+e_{4096}) = 4096e to guess the value of a.s and thus the value of the secret key s. Thus, the smaller the error bits, the fastest we can guess.
On Zama, I believe, the error bits are something like 52, which when multiplied by the 12 of the 4096, is not near 128 bits of security.
What’s wrong?
Hi guerlando,
assuming * refers to polynomial multiplication in the ring R_q = Z_q[X]/(X^N + 1) with N=4096 and . refers to the inner product of vectors over Z_q (where we identify polynomials with their coefficient vectors), the mapping from the RLWE sample to the 4096 LWE samples is incorrect. Each sample should have a different a', where a' is a negacyclic rotation of a. You can see this by viewing a*s = a * (\sum s_i x^i) = \sum s_i( x^i * a). So the j-th sample should have a' with a'_i being the j-th index of x^i * a (which, in R_q corresponds to a negacyclic rotation). Then, indeed, a'.s corresponds to the j-th index of a*s.
Summing all the terms will then not help you, since all it does is creating a new LWE sample (where a = \sum a') with larger noise.
Hope this helps.