# Encoding of the message in Regev encryption

In public key encryption from LWE, we do the following steps

1. $\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \leftarrow \chi^m$, and outputs a key-pair $(pk,sk)$ where $sk = s \in \mathbb{Z}^n_q$ and $pk = (A,s^T\cdot A + \textbf{e}^T)$.

2. $\textbf{PKE.Enc($pk = (A,b^T),b$)}$ takes as input a public key $(A,b^T)$ and a message $a \in {\{0,1}\}$, samples a short vector $r \leftarrow {\{0,1}\}^m$, and outputs a ciphertext $(A\cdot r,b^T\cdot r + a \cdot \lfloor\frac{q}{2}\rfloor)$.

If we now assume that the secret $s$ is a matrix instead of a vector, how can we deterministically encode the message $a$ so that we can recover it during decryption? The error term will also be a matrix in this case where each column is chosen independently of the other from some error distribution.

• we can assume $a$ to be multi-bit if that helps. Aug 23 '18 at 13:38

I think there are are several ways to do that. For instance, the "BGV-like" way is to embed the bit $a$ in a vector $\vec{a} = (a, 0, 0, ..., 0)$.
Then, the encryption is quite the same: $a \mapsto (Ar, Br + \vec{a}\lfloor \frac{q}{2} \rfloor)$. And to decrypt, you can subtract $SAr$ from the second component to get $v := Er + \vec{a}\lfloor \frac{q}{2} \rfloor$. Then, notice that $v$ is a vector whose the first entry is $er + a\lfloor \frac{q}{2} \rfloor$ where $e$ is the first row of $E$. Therefore, if you take the first entry of $v$, you get the same that you have in the original scheme and you can proceed as before.