Given the ring $R_2=\mathbb{Z}_{2}[x]/(x^8+1)$, initiate a public key encryption based on RLWE $(A,b=As+e)$ where all the parameters are selected as polynomials over the given ring. Under the assumption of brute force attack only and if the vector $s$ is 248-byte long, I have the following questions:

  • is this secure initiation?
  • What should be the dimension of the matrix $A$?
  • Can Gaussian elimination finds $s$ given $A$ and $b$?.

1 Answer 1


It is not clear how to create correct encryption from this, let alone secure encryption.

I'll show the easiest lattice-based scheme to make correct, namely secret key encryption. Here, we have

  1. Key Gen samples $s(x)$ somehow, generally with independent coordinates. The only reasonable choice here seems to be uniform.
  2. $\mathsf{Enc}_{s}(m) = [a(x), a(x)s(x) + e(x) + \mathsf{encode}(m(x))]$
  3. $\mathsf{Dec}_s([a(x), b(x)]) = \mathsf{decode}(b(x) - a(x)s(x))$

Here, $\mathsf{encode}$ and $\mathsf{decode}$ must correct errors, in the sense that

$$\mathsf{decode}(\mathsf{encode}(m(x)) + e(x)) = m(x)$$

Typically this is done by having $\mathsf{encode}(m(x)) = \Delta m(x)$ for some scaling factor $\Delta$, and then $\mathsf{decode}(c(x)) = \lfloor c(x)/\Delta\rceil$. The issue with your scheme is that working over $\mathbb{Z}_2$ leaves no room for any scaling factor $\Delta$, so it's really not clear what you can do to make the scheme correct, let alone secure.

Note that for this scheme, if you assume the coordinates of $e(x)$ are from a Gaussian of standard deviation $\sigma$, then one expects something like $\Pr[\lVert e(x)\rVert_\infty > k\sigma]\leq n\exp(-k^2)$. Under the assumption that $k\approx 10$, $\sigma \approx 3$ (which are common), this means that we really need to be working over $\mathbb{Z}_q$ for $q\geq 30$ just to get a basic notion of correctness for private-key encryption. Public-key encryption would require larger $q$ even though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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