Întrebare simplă despre schema BGV

În timp ce încerc să implementez eu schema BGV, am descoperit că sunt foarte confuz în ceea ce privește criptarea și decriptarea schemei. Iată înțelegerea mea:

Lăsa $p$ fie un modul de text simplu și $q$ fie un modul de text cifrat (sunt coprime). Lăsa $\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$ fi mulțimea fixă ​​de reprezentanți modulo $m$ și $[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$ fie modulo $m$ Hartă. Lăsa $R = \mathbb{Z}[x] / (x^{n} + 1)$, $R_{m} = \mathbb{Z}_{m}[x]/(x^{n}+1)$ ca de obicei ($n$ este o putere a lui 2). Aș ignora nivelul și chestiile de bootstrapping.

• Generarea cheilor

1. $a \leftarrow U_{q}$, Unde $U_{q}$ este o distribuție uniformă peste $R_{q}$
2. $s \leftarrow \{-1, 0, 1\}^{n}$
3. $e \leftarrow GD(\sigma)^{n}$, Unde $GD(\sigma)$ este o distribuție Gaussiană (discretă) cu abatere standard $\sigma$
4. $b = [as + pe]_{q} \in R_{q}$ și $pk = (a, b) \in R_{q}^{2}$

• Criptare:

1. $r \leftarrow \{-1, 0, 1\}^{n}$, cu $P(X=0) = 1/2$ și $P(X=-1) = P(X=1) = 1/4$.
2. $e_0, e_1 \leftarrow GD(\sigma)^{n}$.
3. mesaj $m \în R_{p}$
4. $c_{0} = [br + pe_{0} + m]_{q} \in R_{q}$
5. $c_{1} = [ar + pe_{1}]_{q} \in R_{q}$
6. Criptează $m$ la fel de $\mathrm{Enc}(m) = (c_{0}, c_{1}) \in R_{q}^{2}$

• Decriptare

1. Pentru un text cifrat $(c_{0}, c_{1})$, decriptați-l ca $[[c_{0} - c_{1}s]_{q}]_{p}\în R_{p}$.

Înțeleg cum se intenționează să fie asta $\mathrm{Dec}(\mathrm{Enc}(m)) = m$, dar când am încercat să fac câteva exemple de jucării cu propriile mâini, am constatat că acum îmi lipsește ceva. Ceea ce cred este că, există două module (text simplu și text cifrat) și folosirea ambelor face ca decriptarea să eșueze. Asta pentru ca $[[x]_{q} + [y]_{q}]_{p} \neq [[x+y]_{q}]_{p}$ și $[[x]_{q}[y]_{q}]_{p} \neq [[xy]_{q}]_{p}$ în general. Mai ales, dacă $x + pe \not\in \mathbb{Z}_{q}$, apoi reducând modulo $q$ ar face $[[x+pe]_{q}]_{p} \neq [[x]_{q}]_{p}$ ceea ce duce la eșec de decriptare.Cred că îmi scapa ceva foarte simplu, dar nu îmi pot da seama.

Trebuie să alegeți q pentru ca zgomotul din textul cifrat să nu depășească. De exemplu, dacă $p = 2$ și $n = 256$ poți să folosești $q = 7681$ (luat din Kyber). Există multe instanțieri posibile, iar punctul important este că norma $||c_0 - c_1 s||_\infty = ||p (e r + e_2 - e_1 s) + m||_\infty$ e mai puțin decât $q/2$.