Is there any cheaper way to do this multiplication?
This word has two natural interpretations
- Cheaper computation, and
- 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.
