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$?
3
-
$\begingroup$ Have you read it on BGV paper? $\endgroup$– Hilder Vitor Lima PereiraAug 17, 2016 at 19:25
-
$\begingroup$ Yes, I'm currently working through it and this is one the confusions that came up for me. $\endgroup$– sycsAug 17, 2016 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$– Hilder Vitor Lima PereiraApr 9, 2021 at 8:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– sycsAug 17, 2016 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, 2016 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$– sycsAug 23, 2016 at 2:24
-
$\begingroup$ Yes, as stated in the notation of BGV $\endgroup$ Aug 23, 2016 at 12:52