Regev 加密中的消息編碼

在 LWE 的公鑰加密中，我們執行以下步驟

1. $ \textbf{PKE.KeyGen($1^n$)} $ 將安全參數 n 作為輸入，樣本 $ A \leftarrow \mathbb{Z}_p^{n \times m} $ 和 $ \textbf{e} \leftarrow \chi^m $ , 並輸出一個密鑰對 $ (pk,sk) $ 在哪裡 $ sk = s \in \mathbb{Z}^n_q $ 和 $ pk = (A,s^T\cdot A + \textbf{e}^T) $ .
2. $ \textbf{PKE.Enc($pk = (A,b^T),b$)} $ 將公鑰作為輸入 $ (A,b^T) $ 和一條消息 $ a \in {{0,1}} $ , 採樣一個短向量 $ r \leftarrow {{0,1}}^m $ ，並輸出密文 $ (A\cdot r,b^T\cdot r + a \cdot \lfloor\frac{q}{2}\rfloor) $ .

如果我們現在假設秘密 $ s $ 是矩陣而不是向量，我們如何確定性地對消息進行編碼 $ a $ 以便我們可以在解密期間恢復它？在這種情況下，誤差項也將是一個矩陣，其中每一列都是從某個誤差分佈中獨立選擇的。

我認為有幾種方法可以做到這一點。例如，“BGV-like”方式是嵌入位 $ a $ 在向量中 $ \vec{a} = (a, 0, 0, …, 0) $ .

然後，加密是完全一樣的： $ a \mapsto (Ar, Br + \vec{a}\lfloor \frac{q}{2} \rfloor) $ . 而要解密，你可以減去 $ SAr $ 從第二個組件得到 $ v := Er + \vec{a}\lfloor \frac{q}{2} \rfloor $ . 然後，請注意 $ v $ 是一個向量，其第一個條目是 $ er + a\lfloor \frac{q}{2} \rfloor $ 在哪裡 $ e $ 是第一行 $ E $ . 因此，如果你取第一個條目 $ v $ ，你得到的和原來的方案一樣，你可以像以前一樣繼續。

引用自：https://crypto.stackexchange.com/questions/61715