2
$\begingroup$

I'd like to know if LWE (and its variants: RLWE and MLWE) can cipher messages bigger than 1 bit. Is it possible? I didn't find any reference yet. Could you explain it to me or give some good references about it?

Thanks in advance.

UPDATE: I read some papers and maybe my question should be a bit different: Are there schemes using LWE and variants that are not FHE (ciphering more than 1 bit each time)? Considering the NIST proposals for example, I didn't get if they are FHE or not. I noticed that cipher texts are much bigger than plain texts when I use Crystals-Kyber, for example. So I'm supposing it is FHE or it is ciphering 1 bit each time.

$\endgroup$

2 Answers 2

2
$\begingroup$

The answer is "yes", and the modifications are relatively straightforward for experts to make (which is why you may not see it often). There are roughly three classes of modifications, I'll try to briefly mention all of them.

Throughout, I will be referring to the standard "Regev-type" encryption scheme

$$\mathsf{Enc}_s(m) = (A, As + e + (q/2)m),\qquad \mathsf{Dec}(A, b) = \lfloor b - As\rceil_2$$

where the function $\lfloor x\rceil_p = p\lfloor x/p\rceil$ rounds $x$ to the nearest integer multiple of $p$ (and $\lfloor x\rceil$ is the standard "round to the nearest integer" function).

First, there is a standard way to go from a message space of $\mathbb{Z}/2\mathbb{Z}$ to $(\mathbb{Z}/2\mathbb{Z})^n$, namely via a "matrix encryption scheme". The idea is to have $n$ independent keys $s_1, s_2,\dots, s_n$. You can collect these into a matrix $\mathbf{S} = [s_1,\dots,s_n]$, and then encryption with

$$\mathsf{Enc}_{\mathbf{S}}(\vec m) = (A, A\mathbf{S} + \vec e + (q/2)\vec m)$$

Practically, we are "reusing" $A$ across $n$ different encryptions. As $A$ is the largest (size wise) part of the scheme, this is a decent savings. Keys increase by a multiplicative factor $n$ though. I believe this optimization is mentioned in PVW08 ("Lossy Trapdoor Functions and their Applications" maybe?), but don't know if this was the first occurrence of it.

Another way to go from a message space of $\mathbb{Z}/2\mathbb{Z}$ to $(\mathbb{Z}/2\mathbb{Z})^n$ is to use more general rings, i.e. use RLWE. This is somewhat mathematically non-trivial, so I'll give a high-level overview. Ciphertexts are now of the form $(a, as + e + (q/2)m)$, where now $a, s, e, m$ are all polynomials of degree $n$. In particular, one gets encryption for bit vectors in $(\mathbb{Z}/2\mathbb{Z})^n$ "for free", in particular without having to increase the size of the secret key. This is one of the more performant ways to go above bit encryption, and is incredibly popular in practice (for example, every NIST solution uses some version of this, i.e. either RLWE, MLWE, or non-integer NTRU stuff, with the exception of FrodoKEM, which intentionally doesn't for security reasons).

What if you don't like the appearance of $\mathbb{Z}/2\mathbb{Z}$ everywhere? The stories above can all be generalized to have message space $\mathbb{Z}p/\mathbb{Z}$ (rather than the specific case of $p = 2$) by switching the term $(q/2)m$ to $(q/p)m$ (where in the first case, we choose $q$ such that $2\mid q$. After generalizing, we want $p\mid q$). This yields encryption with message space $\mathbb{Z}/p\mathbb{Z}$, or after the two optimizations I mentioned $(\mathbb{Z}/p\mathbb{Z})^n$.

Note that this doesn't come for free --- very roughly speaking, the term $(q/2)m$ is used to ensure correct decryption holds, and works in the presence of error $|e| < q/4$ in each coordinate. For general $p$, this bound tightens, and one must have error $|e| < q/2p$ in each coordinate. This smaller error leads to less secure schemes. One can get around this via reparametrizing things, but the point is that switching from $\mathbb{Z}/2\mathbb{Z}\mapsto \mathbb{Z}/p\mathbb{Z}$ doesn't come "for free".


For your updated question, it is worth mentioning that there are LWE-based encryption schemes (even FHE!!) with ciphertext expansion factor (asymptotically optimal), see

$\endgroup$
1
  • $\begingroup$ Excellent explanation, @Mark. This is what I was looking for. Thx! $\endgroup$
    – r4mpz0
    Dec 21, 2021 at 13:38
0
$\begingroup$

Yes, it's possible since, for example multi-bit uses this approach, for example, if our message is bigger than 1 bit, you can just convert the values you want to encrypt using a secret key S which keeps our private key K, and we can create also a public key P which is based on aleatory numbers and generate a set of numbers N, and also aleatory errors E, with the function, for example, $N_{i}=A_{i}S+E_{i} \text{ (mod q)}$. d With many bits, we take our value and convert into bits, and after we cipher each one.

As a reference with a code, you can read in https://medium.com/asecuritysite-when-bob-met-alice/multi-bit-public-key-encryption-with-learning-with-errors-lwe-e6c7cad02758

and a paper can be https://cims.nyu.edu/~regev/papers/lwesurvey.pdf

$\endgroup$
2
  • 1
    $\begingroup$ I think, the OP doesn't ask about representing the message by 4-bit then encrypting, rather they consider the message space of the LWE-Enc is larger than $\mathbb F_2$. The medium article fails on that!. $\endgroup$
    – kelalaka
    Dec 6, 2021 at 21:04
  • $\begingroup$ Hi, guys. Thanks for yours replies. As @kelalaka said, my first idea was cipher more than 1 bit each time, but I don't know if it's possible, considering that I only found references using samples of the PK to cipher 1 bit per sample. I didn't get yet how the samples are definied and why it is not possible using a block instead. $\endgroup$
    – r4mpz0
    Dec 7, 2021 at 12:44

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.