基於 MP12 構造的 CCA1 方案中的解碼如何工作？
在MP12的第 6.3 節中，我們有 $ encode(m) = Sm $ ， 為了 $ S $ 任何依據 $ \Lambda(G^t) $ . 然後我有：
$ S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\ 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 0\ 4 & 8 & 16 & 32 & 64 & 128 & 256 & 0 & 0\ 8 & 16 & 32 & 64 & 128 & 256 & 0 & 0 & 0\ 16 & 32 & 64 & 128 & 256 & 0 & 0 & 0 & 0\ 32 & 64 & 128 & 256 & 0 & 0 & 0 & 0 & 0\ 64 & 128 & 256 & 0 & 0 & 0 & 0 & 0 & 0\ 128 & 256 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 256 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $
我使用了非常簡單的參數： $ q=512 $ , $ k=9 $ , $ n=1 $ , $ m=18 $ . 我設置 $ H $ 和 $ R $ 到單位矩陣。這樣我就有了 $ A_u = [A’ \mid -A’ + G] $ . 因此，我有那個 $ encode([1, 0, 0, 0, 0, 0, 0, 0, 0]) = [1, 2, 4, 8, 16, 32, 64, 128, 256] = G $ . 定影 $ s=1 $ , 我計算了 $ 2s.A_u + e + encode(m) = [2.A’ \mid -2A’ + 2.G] + [0 \mid G] + e = [2.A’ \mid -2A’ + 3.G] + e \pmod{2q} $ .
反轉預言機返回 $ z=3 $ 和一個大錯誤 $ e’ $ （但是這樣 $ e’.[R \mid I]^t = e.[R \mid I]^t \pmod{q} $ ）。解密算法返回 $ m=[1, 1, 0, 0, 0, 0, 0, 0] $ .
一般來說，我有 $ m $ 正在添加到 $ 2s $ , 所以解密算法返回的二進制分解 $ DecimalRepresentation(m)+2s $ , 而不僅僅是 $ m $ .
在引理 6.2 中，我們有 $ v^t.[R \mid I]^t = 2(sG \pmod{q}) + encode(m) \pmod{2q} $ . 因此，我成功地達到了這一點。因此我猜我的解碼算法是錯誤的。為了解碼，我乘以 $ Inverse(S) $ . 然後我將獲得的向量除以 $ q^{k-1} $ .
我究竟做錯了什麼？
一段時間後，我重新審視了這個問題，發現在解碼之前有必要對基本區域進行模減少以找到陪集，然後我們在範例中給出了內部值 $ 2s+m $ 等於 $ [1, 1, \dots] $ , 歸約後結果等價於 $ [1, 0, \dots] $ ，即 $ m $ ， 如所須。