In the implementation of HEAAN, they have implemented the conjugate function. It computes conjugate of a polynomial. Effectively they have reverted the positions of the coefficients and negated their values. Can anyone please explain me how does it work (mathematically).


1 Answer 1


What they have implemented is close to the notion of reciprocal polynomials. For

$$p(x) = p_0 + p_1 x + \dots + p_{n-1} x^{n-1}$$

these are given by

$$p^*(x) = p_{n-1} + p_{n-2}x + \dots + p_0 x^{n-1} = x^{n-1} p(x^{-1}).$$

This is not precisely what is done though, as what HEAAN implements is instead

$$p_*(x) = p_0 - p_{n-1} x - p_{n-2} x^2 - \dots - p_1 x^{n-1}$$

Still, for $x$ such that $x^{n} \equiv -1$ (equivalently, when working in the polynomial ring $\mathbb{Z}[x]/(x^{n}+1)$), one can easily check that

$$p_*(x) = - x p^*(x) = p(x^{-1}) = p(-x^{n-1}).$$

This third expression is probably the easiest way to understand them. They are simply evaluating $p$ at $x^{-1}$, where one is viewing $x$ as an element such that $x^n\equiv -1$, e.g. it is (formally) a root of unity (either in $\mathbb{C}$ or a finite field), and therefore it is sensible for it to have an inverse.

  • $\begingroup$ Thanks, @Mark. Given the link (you provided) and the explanation, I understood it. It totally makes sense. I am grateful for the answer. $\endgroup$
    – kindi
    Commented Dec 14, 2023 at 0:54
  • $\begingroup$ Sorry for the drive-by comment, but I wonder in what case the reciprocal is useful in the context of HEAAN? It seems like it is a means to provide some useful automorphism that is not a rotation, but I wonder what sort of higher-level operations make use of this. $\endgroup$
    – JeremyKun
    Commented Dec 14, 2023 at 17:21
  • $\begingroup$ @JeremyKun It is mostly to shrink ciphertext sizes iirc. The HEAAN authors like to embed $\mathbb{R}^N$ into a certain subspace of $\mathbb{C}^N$, see section 2.3 of the HEANN paper. I believe the condition that $z_j\equiv \overline{z}_{-j}$ can be alternatively written as $p(x) = p_*(x)$. This is perhaps more obvious in their other writings, see for example this. They refer to discarding the later $N/2$ coordinates as these being "conjugates" of the prior coordinates. One can also more easily see that $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 16, 2023 at 1:38
  • $\begingroup$ claimed relationship $p(x) = p_*(x)$ holds (at least, if one knows that $5^i$ generates $\mathbb{Z}_{2^k}^*$). $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 16, 2023 at 1:39
  • $\begingroup$ As for how this may be independently useful, it is one way to embed the Euclidean inner product $\langle \vec x, \vec y\rangle = \sum_i \vec x_i\vec y_i$ into $\mathbb{Z}[x]/(x^n+1)$. In particular, the constant coefficient of $p(x) q_*(x)$ is $\langle \vec p, \vec q\rangle$ (if I remember correctly). I don't think this is a particularly good way to compute $\langle \vec p, \vec q\rangle$ though. In particular it "wastes" many coefficients of the output polynomial, which things like the Diagonally Dominant matrix-vector multiplication algorithm doesn't. $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 16, 2023 at 1:45

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.