1
$\begingroup$

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$?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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.

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

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.

$\endgroup$

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.