Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be represented by means of $\ell(N, q) := N\lceil\log_2(q)\rceil$ bits. In lattice-based cryptography the polynomial $f$ is often cyclotomic $\Phi_n$ for some $n \in \mathbb{N}$ (mainly $n$ is a prime or a power of two). In this case, $N = \varphi(n)$, where $\varphi$ is Euler's totient function. Do you know an example of a cryptographic scheme such that for the same security level the number $\ell(N, q)$ can be smaller if $f$ is not a cyclotomic polynomial ? In other words, is not the choice $f = \Phi_n$ optimal if we want to minimize $\ell(N, q)$ in a cryptosystem ? Thank you in advance for your response !


1 Answer 1


As the size of objects is only a function of the degree $N$, it seems that an equivalent way to phrase your question is

For fixed modulus $q$ and degree $N$, is there some particular family of polynomials $\{f_i\}_{i\in\mathbb{N}}$ where $\deg f_i = i$, and RLWE instantiated over $\mathbb{Z}[x]/(q, f)$ is maximally hard?

The answer to that is "mostly no". First, working with $\mathbb{Z}[x]/(q, f)$ for general $f$ is something you should be careful about. While this is typical in lattice-based cryptography for cyclotomic $f$, in general it seems closer to a problem known as the "Polynomial Learning With Errors" problem (PLWE). Roughly, here one works over $\mathbb{Z}[x]/(q,f)$ directly, i.e. "in the coefficient embedding". This leads to all sorts of weirdness, and instances can be atypically weak unexpectedly. For cyclotomics it doesn't matter that much (the two embeddings are isometric up to a scaling factor), but for general $f$ this can fail completely.

This is to say that there are some explicit families of $f$ that are known to be weak, and you can find them from searching on "PLWE" or "Polynomial Learning with Errors". This is the opposite of your question though --- are there explicit families of $f$ that are strong.

The answer to this seems less clear. Roughly speaking, how (theoretical) hardness results work tends to be

If RLWE over this number field is easy, then some worst-case lattice problem over ideal lattices in this number field is easy.

At least this is my understanding of things. Provided it is correct (I am too lazy to check right now), this would only help us determine hard families if $f_i$ if we knew number fields where lattice problems are hard. But this seems difficult to provably establish, and there are some disagreements in the community as to which number fields should heuristically be harder.

Still, there are some results that are vaguely along the lines of what you want. Rather than defining polynomial multiplication $(a(x), b(x))\mapsto a(x)b(x)\bmod (f, q)$, one could impose other multiplication operations onto things. One interesting one for your situation is known as Middle Product Learning With Errors. This is a little technical to define, so I will just give some intuition. If we multiply $a(x)b(x)\bmod q$ (not $\bmod f$), we get a polynomial of degree $\deg a + \deg b$. This will often be larger than $N$ --- reducing $\bmod f$ can be seen as post-processing to ensure the degree is $\leq N$. There are other strategies one could use though --- for example, define a polynomial $c'(x)$ of degree $N$ that are the "middle $N$ coefficients" in the polynomial product $a(x)b(x)$.

Anyway, if one uses this non-standard product, one can prove something of the form

If Middle-Product LWE over a number field is easy, then worst-case lattice problem over ideal lattices in any number field is easy.

This is to say that one can connect a LWE-type assumption with the hardness of ideal lattice problems in any number field of fixed degree.

In this way, theoretically MPLWE is "maximally hard" among RLWE-type things, at least with respect to how strong the worst-case to average-case reductions are. So if you are trying to pick out polynomials that are maximally hard for a certain size of ciphertexts, I would say just use MP-LWE instead.

It's worth mentioning as a caveat there are questions about the practical hardness of RLWE instances as well. But really if you care about practice (vs theory) just use power-of-two cyclotomics. They have attracted the most cryptanalytic interest by quite a bit, and are the biggest target for attacks.


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.