Assume I am using the SIMD encryption of homomorphic encryption. Performing plaintext-ciphertext multiplication between two vectors $\mathbf{a}$ and $\mathbf{x}$ means $Dec(\mathbf{a} \times Enc(\mathbf{x})) = \mathbf{a} \times \mathbf{x}$, where $\times$ means point-wise (or say element-wise) multiplication. I am wondering if all elements of $\mathbf{a}$ is the same. Is there any cheaper way to do this multiplication?

A possible way I have known is to use the square and multiply algorithm, adding $\mathbf{x}$ to itself to multiply its plaintext by two, which allows to multiply in times $O(\log_2a)$.

  • 2
    $\begingroup$ What does $\vec a\times \vec x$ mean to you? Point-wise multiplication of vectors, or what? $\endgroup$
    – Mark
    Sep 25 at 2:30
  • $\begingroup$ Yes, point-wise multiplication. $\endgroup$
    – Zhengyi Li
    Sep 25 at 2:53
  • $\begingroup$ Which FHE scheme are we talking about? $\endgroup$
    – kelalaka
    Sep 25 at 6:47
  • $\begingroup$ Like CKKS? I do not want to limit the discussion to a specific scheme. $\endgroup$
    – Zhengyi Li
    Sep 25 at 8:30

1 Answer 1


Is there any cheaper way to do this multiplication?

This word has two natural interpretations

  1. Cheaper computation, and
  2. Cheaper noise growth.

For 1, the answer is "no". Additionally, your square-and-multiply algorithm is not necessary. To efficiently (from the perspective of computation) compute your desired quantity, you format ciphertexts as

$$\mathsf{Enc}(\mathsf{iNTT}_p(\vec x)).$$

Here, $\mathsf{iNTT}_p(\vec x)$ is the inverse $\mathsf{NTT}$ modulo $p$, your plaintext modulus. This maps $\vec x\in(\mathbb{Z}_p^n, +, \circ)$ (where $\circ$ is the Hadamard product, what you notate as $\times$) to a polynomial $f_{\vec x}(X)\in \mathbb{Z}_p[x]/(X^n+1)$. There are some conditions for this map to exist ($p$ needs to be "NTT friendly"), but they are common in practice.

When formatted this way, we can compute

$$\mathsf{iNTT}_p(\vec a), \mathsf{Enc}(\mathsf{iNTT}_p(\vec x))\mapsto \mathsf{iNTT}_p(\vec a)\ast \mathsf{Enc}(\mathsf{iNTT}_p(\vec x)) = \mathsf{Enc}(\mathsf{iNTT}_p(\vec a\circ \vec x)).$$

Here, $\ast$ is polynomial multiplication. Often in practice you work in the "NTT domain". Then, this would instead look like

$$\vec a, \mathsf{NTT}_p(\mathsf{Enc}(\mathsf{iNTT}_p(\vec x)))\mapsto \vec a\circ \mathsf{NTT}_p(\mathsf{Enc}(\mathsf{iNTT}_p(\vec x))) = \mathsf{NTT}_p(\mathsf{Enc}(\mathsf{iNTT}_p(\vec a\circ \vec x))).$$

This all being said, the noise growth for this operation will be large. Even if $\vec a$ is small, $\mathsf{iNTT}_p(\vec x)$ may be large (it probably has $\ell_\infty$-norm bounded by $p$). Perhaps your setting can handle this, but if it can't then even though this is "cheap" from the perspective of computational efficiency (something like $O(n)$ operations in $\mathbb{Z}_p$ if you are already in the NTT domain, otherwise $O(n\log n)$), it is "expensive" from the perspective of noise growth.

For 2, the answer is (sort of) also "no". One typically uses a variant of square-and-multiply, though different from how you are imagining.

The issue we ran into before is that we are polynomial-multiplying by $\mathsf{iNTT}_p(\vec a)$, which may be large. We can polynomial=multiply by a smaller quantity as follows. Scalar $y$, write

$$y = \sum_{i = 0}^{\ell - 1} g^{-1}(y) g_i$$

where $\vec g\in\mathbb{Z}_q^\ell$ is a "Gadget". Explicitly, you can think of $\vec g = (1, 2, 2^2, ..., 2^{\ell-1})$ for $\ell = \lceil \log_2(q)\rceil$. The notation $g^{-1}(y)$ "gadget decomposition". For the aformentioned binary digit decomposition gadget, this maps

$$y \mapsto (\vec y_{0},\dots, y_{\ell-1})$$

where $y_i\in\{0,1\}$ are such that

$$\langle g^{-1}(y), \vec g\rangle = y$$

Note that this defines gadget decomposition for scalars. Extend to vectors by decomposing each scalar in the vector independently.

Anyway, now if you instead format the ciphertexts as

$$\mathsf{Enc}(\vec g\otimes \mathsf{iNTT}_p(\vec x)) :=\mathsf{Enc}(g_0\mathsf{iNTT}_p(\vec x)), \mathsf{Enc}(g_1\mathsf{iNTT}_p(\vec x)),\dots \mathsf{Enc}(g_{\ell-1}\mathsf{iNTT}_p(\vec x)),$$

e.g. you increase the number of ciphertexts you have by a factor $\ell$, then you can "square and multiply" to get a homomorphic operation

$$\mathsf{iNTT}_p(\vec a), \mathsf{Enc}(\vec g\otimes \mathsf{iNTT}_p(\vec x)))\mapsto \sum_{i\in[\ell]} g^{-1}(\mathsf{iNTT}_p(\vec a))\ast\mathsf{Enc}(g_i \mathsf{iNTT}_p(\vec x)).$$

This yields multiplication by $\mathsf{iNTT}_p(\vec a)$ with noise growth that scales with $\approx 2\ell$ (and for digit decomposition with respect to base $B$, it becomes $\approx B\lceil \log_B q\rceil$), which can sometimes be useful.

  • $\begingroup$ Does cheaper computation works in any scheme? What about the cost of converting back and foreword from spectral domain. $\endgroup$
    – kelalaka
    Sep 26 at 6:56
  • $\begingroup$ Thanks for the nice answer! But I am confused about why the NNT and INNT are needed. It seems increases the overhead. Moreover, the answer seems to be a general algorithm for any $a$ while I am wondering a special case where all elements in $a$ are the same. Looking forward to your reply. $\endgroup$
    – Zhengyi Li
    Sep 26 at 7:52
  • $\begingroup$ @kelalaka you need a plaintext modulus such that you have an isomorphism $(\mathbb{Z}_p^n, +, \circ)\cong \mathbb{Z}_p[x]/(x^n+1)$. This requires the plaintext modulus $p\equiv 1\bmod 2n$ to be NTT friendly. It is a common assumption in things like BGV/BFV encryption. And the cost of computing to/from the NTT domain is required here, as otherwise you do not have pointwise multiplication of values, only polynomial multiplication, which is not what the OP wanted. $\endgroup$
    – Mark
    Sep 27 at 3:38
  • 1
    $\begingroup$ @ZhengyiLi Sorry, I didn't see that all elements of $a$ are the same. Then you can do this with polynomial multiplication, e.g. you can just encrypt via $\mathsf{Enc}(\vec x)$ (viewing $\vec x$ as the coefficients of a polynomial), and multiply all coefficients by $a$ by multiplying your two components of your ciphertext $(c_0(x), c_1(x))$ by the constant polynomial $a$. Square and multiply still seems unnecessary here though, solely because multiplication by $a$ likely occurs in a single underlying instruction, so square-and-multiply would only make things slower for no reason. $\endgroup$
    – Mark
    Sep 27 at 3:40
  • $\begingroup$ Square-and-multiply may still be useful to reduce the noise growth via gadgets, but that doesn't sound like your primary concern. Overall, plaintext-ciphertext multiplications are very efficient in FHE, so if they areyour bottleneck for some reason it might make sense to describe your application more. $\endgroup$
    – Mark
    Sep 27 at 3:42

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.