I think until public key $\mathsf{pk}=(b=-[as + e]_q,a) $ is broken, Ring-LWE is secure where $a$ is uniformaly random polynomial, $e$ is an error sampled from gaussian distribution with std=$\sigma$ and mean $\mu$=0, and $s$ is a secret key of hamming weight $h$.

$\mathbf{Question }$

Why is error needed for encryption?

A some Ring-LWE based homomorphic encryption schemes encrypts a message $m$ as $\mathsf{ct}=([m+e_0+bv]_q,[av+e_1]_q)$ where

$q$: ciphertext space

$v$: uniformly random small polynomial

I wonder why $m+e_0+bv$ part needs $e_0$. I think m+$bv$ is already uniform because $bv$ looks uniform. So gaussian elimination cannot work here, isnt't it correct?

  • $\begingroup$ Is $p$ randomly chosen at each encryption? Do you have any link pointing to the paper that presents this scheme? $\endgroup$ – Hilder Vitor Lima Pereira Aug 30 '17 at 7:41
  • $\begingroup$ No. $p$ is fixed. $e_0$ and $e_1$ are randomly chosen every encryption time $\endgroup$ – mallea Aug 30 '17 at 16:41
  • $\begingroup$ Of course I understood the security of public key which encrypts the secret key by generating a ring-lwe instance, i.e., since $as$ is a constant, we need to add noise term. But as for the public-key-encryption part, because of unknown $bv$ with uniformly random $v$, $m+bv$ already looks uniform. Why is it to be $m+bv+e_0$ with additional noise term? $\endgroup$ – mallea Sep 2 '17 at 21:34
  • 1
    $\begingroup$ But if no error term $e_0$ were added, what would you get if you calculated $ct[0] \pmod b$? $\endgroup$ – Hilder Vitor Lima Pereira Sep 3 '17 at 12:16

Your Answer

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

Browse other questions tagged or ask your own question.