I'm trying to understand the GGH graded encoding scheme, but something there leaves me very confused and I can not figure out how to explain it:

Let $R := \mathbb{Z}[X]/(X^n+1)$, where $n$ is a power of $2$ (hence $X^n+1$ is irreducible in $\mathbb{Z}[X]$); $q := 2^a$ for a large enough $a$; $R_q := R/qR$, i.e. $R_q = \mathbb{Z}_q[X]/(X^n+1)$.

In the scheme, we choose $z$ uniformly at random in $R_q$. Then the scheme uses this $z$ to divide other elements in $R_q$, like $[c/z]_q$. But is it correct? I believe $R_q$ is not field (it is not even integral domain) and so not every element there has it's multiplicative inverse.

Or maybe I misunderstood the notation?

Thank you for any advice.


1 Answer 1


I believe $R_q$ is not field

Yes, it is not a field in general. $R_q$ is a field if, and only if, $q$ is a prime and $X^n+1$ is irreducible over $\mathbb{Z}_q[X]$.

However, you are not forced to pick $q$ as a power of two. As section 4.2 of the original paper explains, the only restriction over $q$ is

$$q \ge 2^{8\kappa \lambda}n^{o(\kappa)}$$

In particular, you can let $q$ to be prime (as it is supposed to be in Lemma 5).

And even if you don't select $q$ as a prime, you just have to check that $z$ has an inverse in $R_q$ and that the order of $z^{-1}$ is bigger than $\kappa$. If this is the case, then you are fine, if not, then sample another $z$.


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.