Trong khi tôi đang cố gắng tự triển khai lược đồ BGV, tôi thấy rằng tôi thực sự bối rối về mã hóa và giải mã lược đồ. Đây là sự hiểu biết của tôi:
Để cho $p$ là một mô đun bản rõ và $q$ là một mô đun bản mã (chúng là nguyên tố cùng nhau). Để cho $\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$ là tập cố định của các đại diện modulo $m$ và $[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$ được modulo $m$ bản đồ. Để cho $R = \mathbb{Z}[x] / (x^{n} + 1)$, $R_{m} = \mathbb{Z}_{m}[x]/(x^{n}+1)$ như thường lệ ($n$ là lũy thừa của 2). Tôi sẽ bỏ qua những thứ cấp độ và bootstrapping.
- $a \leftarrow U_{q}$, ở đâu $U_{q}$ là phân bố đều trên $R_{q}$
- $s \leftarrow \{-1, 0, 1\}^{n}$
- $e \leftarrow GD(\sigma)^{n}$, ở đâu $GD(\sigma)$ là một phân phối Gaussian (rời rạc) với độ lệch chuẩn $\sigma$
- $b = [as + pe]_{q} \in R_{q}$ và $pk = (a, b) \in R_{q}^{2}$
- $r \leftarrow \{-1, 0, 1\}^{n}$, với $P(X=0) = 1/2$ và $P(X=-1) = P(X=1) = 1/4$.
- $e_0, e_1 \leftarrow GD(\sigma)^{n}$.
- thông điệp $m \in R_{p}$
- $c_{0} = [br + pe_{0} + m]_{q} \in R_{q}$
- $c_{1} = [ar + pe_{1}]_{q} \in R_{q}$
- mã hóa $m$ như $\mathrm{Enc}(m) = (c_{0}, c_{1}) \in R_{q}^{2}$
- Đối với một bản mã $(c_{0}, c_{1})$, giải mã nó thành $[[c_{0} - c_{1}s]_{q}]_{p}\in R_{p}$.
Tôi hiểu làm thế nào điều này được dự định $\mathrm{Dec}(\mathrm{Enc}(m)) = m$, nhưng khi tôi thử làm một số mẫu đồ chơi bằng tay của chính mình, tôi thấy rằng bây giờ tôi đang thiếu một thứ gì đó.
Điều tôi nghĩ là, có hai mô-đun (bản rõ và bản mã) và việc sử dụng cả hai thực sự khiến việc giải mã không thành công. Điều này là do $[[x]_{q} + [y]_{q}]_{p} \neq [[x+y]_{q}]_{p}$ và $[[x]_{q}[y]_{q}]_{p} \neq [[xy]_{q}]_{p}$ nói chung. Đặc biệt, nếu $x + pe \not\in \mathbb{Z}_{q}$, sau đó giảm modulo $q$ sẽ làm $[[x+pe]_{q}]_{p} \neq [[x]_{q}]_{p}$ dẫn đến việc giải mã không thành công.Tôi nghĩ rằng tôi đang thiếu một cái gì đó thực sự đơn giản nhưng tôi không thể tìm ra.
