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$?

| improve this question | | | | |
  • $\begingroup$ Have you read it on BGV paper? $\endgroup$ – Hilder Vitor Lima Pereira 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

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)

| improve this answer | | | | |
  • $\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$ – Daniel Apon 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$ – Tal-Botvinnik 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.