1
$\begingroup$

Generally, we instantiate Ring-LWE with the polynomial ring $R = \mathbb{F}_q\ /\ (X^N+1)$ for prime $q$ and some power-of-two $N$.

Can we instead do Ring-LWE over the ring $R = \mathbb{F}_q\ /\ (X^N+1)$, where $q$ can be any prime power? Basically, this would mean the coefficients of ciphertexts are elements of $GF(q)$.

(Also, is this an unusual choice, or covered by existing literature that I'm not aware of?)

Improve this question
$\endgroup$
2
  • $\begingroup$ I think that the first sentence is to be read: Generally, we instantiate Ring-LWE with the polynomial ring $R=\mathbb F_q[X]\,/\,(X^N+1)$ for prime $q$ and some power-of-two $N$. $\endgroup$
    – fgrieu ♦
    Jul 28 at 10:24
  • $\begingroup$ Yes, I edited it, thank you! $\endgroup$
    – S. M.
    Jul 28 at 16:29

1 Answer 1

Reset to default
1
$\begingroup$

Yes, it is possible to instantiate Ring-LWE with the polynomial ring R=F_q/ (X_N+1), where q is a prime power and N is a power-of-two. in this case, Ring-LWE is known as "Finite Field Ring-LWE" or "FF-Ring-LWE".

In FF-Ring-LWE, the coefficients of the ciphertexts are elements of the finite field GF(q), which is the field of order q. The arithmetic operations in GF(q) are similar to those in Zq, but with some differences due to the fact that GF(q) is a field rather than a ring.

However, the choice of q can have an impact on the security of the scheme. In particular, if q is too small, then the scheme may be vulnerable to certain attacks, such as lattice reduction algorithms. On the other hand, if q is too large, then the scheme may be less efficient and require larger key sizes.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I can't find any references to 'FF-Ring-LWE' or 'Finite Field Ring-LWE' on Google Scholar... $\endgroup$
    – S. M.
    Jul 28 at 16:33
  • $\begingroup$ It's not called that, because the choice of $q$ doesn't impact the security of schemes except via the quantity $\log q$. $\endgroup$
    – Mark
    Jul 28 at 16:39
  • $\begingroup$ But these schemes use $\mathbb{Z}_q$, not $\mathbb{F}_q$ for prime-power q. These are different things (the first isn't even a field!) $\endgroup$
    – S. M.
    Jul 28 at 16:45
  • $\begingroup$ In that case, don't you have that $\mathbb{F}_q\cong \mathbb{Z}_p[x](f(x))$ for $f = \deg e$, and $\mathbb{Z}_q[y]/(g(y))\cong \mathbb{Z}_p[x,y]/(f(x),g(y))$? I.e. it appears you are asking about the security of a bivariate form of RLWE with small modulus. $\endgroup$
    – Mark
    Jul 28 at 17:13
  • $\begingroup$ Note that if this interpretation is correct, you should be careful. Bivariate RLWE has some known security issues. In particular, you might hope that its security corresponds to univariate RLWE of degree $\deg f\cdot \deg g$. This is not always the case, see On the security of multivariate RLWE. The net effect is you might have to choose $p$ large enough that RLWE in $\mathbb{Z}_p[y]/(g(y))$ is still hard, i.e. negating the benefit of choosing the larger modulus $q = p^e$. $\endgroup$
    – Mark
    Jul 28 at 17:20

Your Answer

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

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