格的陷門：CCA 安全加密
在Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller中，Miccincio 和 Peikert 提出了一種 CCA 安全加密。
但是，我對解密算法中的步驟感到困惑（第 36 頁引理 6.2。）。
那是， $ \mathbf{v}^t \begin{bmatrix} R \I \end{bmatrix} = 2(\mathbf{s}^th(u)\mathbf{G} $ 反對 $ q $ ) + 編碼(m) 模組 $ 2q $ .
以及為什麼 $ 2(\mathbf{s}^th(u)\mathbf{G} $ 反對 $ q) = 0 $ 反對 $ 2q $ ，這樣解碼（ $ \mathbf{v}^t \begin{bmatrix} R \I \end{bmatrix}) $ =解碼（編碼（m））。
您誤解了“解碼”的作用。正如論文前面提到的：
系統有消息空間 $ {0,1}^{nk} $ ，我們將其雙射映射到 $ \Lambda/2\Lambda $ 為了 $ \Lambda = \Lambda(G^t) $ 通過一些可以有效評估和反轉的函式編碼。具體來說，讓 $ S \in\mathbb{Z}^{nk×nk} $ 是任何基礎 $ \Lambda $ ，我們可以映射 $ m \in{0,1}^{nk} $ 至 $ encode(m) = Sm \in\mathbb{Z}^{nk} $ .
這就是說 encode 是一個函式 $ {0,1}^{nk}\to \Lambda/2\Lambda $ , 因此 decode 是一個函式 $ \Lambda/2\Lambda\to{0,1}^{nk} $ . 請注意，您的表達式是以下形式：
$$ \underbrace{2(\overbrace{s^th(u)G\bmod q}^{\in\Lambda})}_{\in 2\Lambda} + \overbrace{encode(m)\bmod 2q}^{\in \Lambda/2\Lambda} $$ 注意 $ \Lambda/2\Lambda $ 是（通過構造）在元素翻譯下不變 $ 2\Lambda $ . 該構造只是添加了一個元素 $ 2\Lambda $ 至 $ encode(m) $ ，通過上述不變性不會影響解碼。請注意，這可能會映射您選擇的特定代表 $ \Lambda/2\Lambda $ 給不同的代表，但所有這些代表在 $ \Lambda/2\Lambda $ .
具體來說，考慮是否有 $ \Lambda = \mathbb{Z} $ . 說 $ encode(m) = b\in\mathbb{Z}/2\mathbb{Z} $ . 如果你添加一個元素 $ 2\mathbb{Z} $ 對此，你會得到一些形式的東西 $ b + 2k $ 為了 $ k\in\mathbb{Z} $ （簡稱 $ b + 2\mathbb{Z} $ ）。但 $ decode(b + 2\mathbb{Z}) $ 是一個函式 $ \mathbb{Z}/2\mathbb{Z} $ 到消息空間 — 對於元素的任何特定代表，它應該是相同的 $ \mathbb{Z}/2\mathbb{Z} $ 你給它，所以你應該自由地添加任何元素 $ 2\mathbb{Z} $ 在不影響解碼的正確性的情況下。
更具體地說，在這種情況下 $ decode $ 是一個功能，它說“我只關心我的輸入是偶數還是奇數，其他細節無關緊要”。由於將偶數添加到任何其他數字不會影響其奇偶性，因此您有： $$ decode(encode(m) + 2\mathbb{Z}) = m $$ 同樣，在協議中我們有： $$ decode(encode(m) + 2\Lambda) = m $$