About multiply by constant of LWE

I am new to lattice-based cryptography

May I ask that for a lattice-based encryption

$$enc(m) = A^{T}R+m \bmod q$$

If I set the $$q$$ to be able to decrypt to $$m$$ (and suppose the bound of $$q$$ is tight over the bound of error and secret chosen from LWE)

But if I need an operation that takes a constant $$p$$, and multiply $$p\cdot enc(m)$$

Does it mean that all I need to do is to have a new bound of $$q$$ equals $$p\cdot q$$?

I find that this situation becomes easier to understand if you make the various parts of lattice-based encryption more explicit.

An LWE encryption

$$[A, \vec b := A\vec s + \vec m + \vec e]$$

may be approximately decrypted to $$\vec m+ \vec e$$ by computing $$\vec b - A\vec s$$. To isolate $$\vec m$$, we require a separate error-tolerant encoding, e.g. we instead have our ciphertext be of the form

$$[A, \vec b' := A\vec s + \mathsf{encode}(\vec m)+\vec e]$$

where $$\mathsf{encode}(\vec m)$$ is such that we can efficiently compute

$$\vec m':=\mathsf{encode}(\vec m)+\vec e\mapsto \vec m$$

A common way to do this is to write (when $$p\mid q$$)

$$\mathsf{encode}(\vec m) = (q/p)\vec m,$$ where we can decode

$$\vec m'\mapsto \lfloor \vec m'/(q/p)\rceil = \lfloor \vec m + \frac{\vec e}{q/p}\rceil$$

provided $$\lVert e / (q/p)\rVert_\infty < 1/2$$ one can then show that this is equal to $$\vec m$$, e.g. we have correctly decrypted.

If we naively multiply by some scalar $$c$$, then the error $$\vec e$$ becomes the (potentially larger) value $$c\vec e$$, and the condition

$$\lVert e/(q/p)\rVert_\infty < 1/2\iff \lVert \vec e\rVert_\infty < \frac{q}{2p}$$

becomes the condition

$$\lVert c\vec e\rVert_\infty < \frac{q}{2p}\iff \lVert e\rVert_\infty < \frac{q}{2pc}.$$

As you say, setting $$q' := cq$$ is one way to compensate for this.

It is worth mentioning there is another way to multiply by large constants with low noise growth in LWE-based encryption, namely using gadgets. See this for a formal introduction. The main idea is as follows. Write

$$\mathsf{Enc}(\vec m;\vec e) = [A, A\vec s + \mathsf{encode}(\vec m) + \vec e]$$

One can prove that this is linearly homomorphic, in the sense that

$$\mathsf{Enc}(\vec m_0;\vec e_0) + \mathsf{Enc}(\vec m_1;\vec e_1) = \mathsf{Enc}(\vec m_0+\vec m_1;\vec e_0+\vec e_1)$$ and $$c\cdot \mathsf{Enc}(\vec m;\vec e) = \mathsf{Enc}(c\cdot\vec m;c\cdot \vec e).$$

So we can multiply by $$c$$, but grow errors by $$c$$ as well. Instead, if we "encrypt $$\vec m$$ using a gadget", meaning create the collection of ciphertexts

$$\{\mathsf{Enc}(2^i\vec m; \vec e_i)\}_{i},$$

then we can rewrite (for $$c = \sum_i c_i2^i$$ the binary decomposition of $$c$$)

$$c\cdot m = \sum_{i}c_i2^im = c_i\sum_i m2^i$$

It follows that we can compute

$$\sum_i c_i\cdot \mathsf{Enc}(2^im;\vec e_i) = \mathsf{Enc}(c\cdot\vec m; \sum_i c_i\cdot\vec e_i)$$

E.g. we can multiply by an arbitrary $$c\in\mathbb{Z}_q$$ while increasing errors by a factor $$\approx \log_2 q$$. More generally, if we decompose $$c$$ modulo $$B$$, the noise growth becomes $$\approx (B/2)\log_B q$$, e.g. we can achieve noise growth $$\ll q$$ by increasing the size of our ciphertexts by a small amount.

• Maybe this answer needs to include the meaning of $\lceil x \rfloor$ as the nearest integer. Oct 20, 2023 at 7:51

If you consider $$q$$ as the ciphertext modulus, then you would want the new ciphertext $$p \cdot Enc(m)$$ to also lie in $$\mathbb{Z}_q$$, which means the result will still be obtained mod $$q$$. Multiplication of the ciphertext with a constant is a case of homomorphic multiplication usually considered in homomorphic encryption schemes.