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.

  • $\begingroup$ we can assume $a$ to be multi-bit if that helps. $\endgroup$ – chelsea 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.

  • $\begingroup$ Thanks, I understood. Can you look at (crypto.stackexchange.com/questions/61544/…) and share your thoughts. $\endgroup$ – chelsea Aug 24 '18 at 7:54
  • $\begingroup$ @chelsea Unfortunately, I don't have time now. But at night I will try to give it a look. It seems an interesting question at first glance. $\endgroup$ – Hilder Vitor Lima Pereira Aug 24 '18 at 8:30
  • $\begingroup$ Yeah sure........ $\endgroup$ – chelsea Aug 24 '18 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.