Score:2

LWE - Encrypting/Decrypting messages bigger than 1 bit

in flag

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.

Score:1
ng flag

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

Felipe Rampazzo avatar
in flag
Excellent explanation, @Mark. This is what I was looking for. Thx!
Score:0
au flag

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

kelalaka avatar
in flag
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!.
Felipe Rampazzo avatar
in flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.