Often times $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is referred to as the noise associated to the ciphertext $\textbf{c}$, and that decryption is correct when the norm of the noise is $< q/2$. But shouldn't $\langle \textbf{c}, \textbf{s} \rangle$ be the noise instead of $[\langle \textbf{c}, \textbf{s} \rangle]_q$, since $[\langle \textbf{c}, \textbf{s} \rangle]_q$ means the reduction mod $q$ already happened and so the norm of $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is always $< q/2$?

  • $\begingroup$ Have you read it on BGV paper? $\endgroup$ Aug 17 '16 at 19:25
  • $\begingroup$ Yes, I'm currently working through it and this is one the confusions that came up for me. $\endgroup$
    – sycs
    Aug 17 '16 at 21:39
  • $\begingroup$ $\langle c ,s\rangle$ cannot be defined as the noise, since we have $\langle c,s\rangle= 2e + m + uq$ for some integer $u$. The reduction mod $q$ removes the term $uq$ so that we have access to the noise term, which is $e$, or $2e$, or $2e + m$ depending on the definition. In BGV paper, what they really want is $|2e + m| < q/2$. But it is true that the way they defined everything does not seem good, because the reduction maps to $(-q/2, ..., q/2]$, so what they defined as the noise will always be smaller than $q / 2$ (or exactly equal to $q/2$, which is very very unlikely). $\endgroup$ Apr 9 at 8:01

This is because of the decryption equation: If two ciphertexts differ ($\mathbb{Z}$-component-wise..., not homomorphically) in a multiple of $q$, they both decrypt to the same thing because of the modular reduction. Therefore, upon reception of a 'big' ciphertext, it makes sense to take modular reduction of this ciphertext and then look at its noise. Conversely, to cheat silly attackers one could add 'false noise' in this fashion (severely augmenting ciphertext size, however)

  • $\begingroup$ If I am right, is there a good explanation for why $[\langle \textbf{c}, \textbf{s} \rangle ]_q$ is referred to as the noise and not $\langle \textbf{c}, \textbf{s} \rangle$? $\endgroup$
    – sycs
    Aug 17 '16 at 21:48
  • $\begingroup$ They write $[\langle\vec{c},\vec{s}\rangle]_q$ in order to explicitly distinguish it from the similar-looking-but-distinct $[\langle\vec{c},\vec{s}\rangle]_p$ for $p < q$. In particular, modulus switching was "the new thing" in BGV, and their key idea revolves around these two types of terms (so they really want to keep them separate). $\endgroup$ Aug 21 '16 at 6:28
  • 1
    $\begingroup$ Maybe I'm misinterpreting what $[\langle \textbf{c}, \textbf{s} \rangle]_q$ means. Is my assumption that $[\langle \textbf{c}, \textbf{s} \rangle]_q$ means the reduction mod $q$ already went through so then the norm of $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is always $< q/2$ correct? $\endgroup$
    – sycs
    Aug 23 '16 at 2:24
  • $\begingroup$ Yes, as stated in the notation of BGV $\endgroup$ Aug 23 '16 at 12:52

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.