LWE - 加密/解密大於 1 位的消息
我想知道 LWE（及其變體：RLWE 和 MLWE）是否可以加密大於 1 位的消息。可能嗎？我還沒有找到任何參考。你能向我解釋一下或提供一些好的參考嗎？
提前致謝。
**更新：**我讀了一些論文，也許我的問題應該有點不同：是否有使用 LWE 的方案和不是 FHE 的變體（每次加密超過 1 位）？例如，考慮到 NIST 的提議，我不知道它們是否是 FHE。例如，當我使用 Crystals-Kyber 時，我注意到密文比純文字大得多。所以我假設它是 FHE 或者它每次都加密 1 位。
答案是“是”，而且對於專家來說，修改相對簡單（這就是為什麼你可能不會經常看到它的原因）。大致有三類修改，我將嘗試簡要提及所有修改。
在整個過程中，我將參考標準的“Regev 類型”加密方案
$$ \mathsf{Enc}_s(m) = (A, As + e + (q/2)m),\qquad \mathsf{Dec}(A, b) = \lfloor b - As\rceil_2 $$
函式在哪裡 $ \lfloor x\rceil_p = p\lfloor x/p\rceil $ 回合 $ x $ 到最接近的整數倍 $ p $ （和 $ \lfloor x\rceil $ 是標準的“四捨五入到最接近的整數”函式）。
首先，有一個標準的方法可以從消息空間 $ \mathbb{Z}/2\mathbb{Z} $ 至 $ (\mathbb{Z}/2\mathbb{Z})^n $ ，即通過“矩陣加密方案”。這個想法是有 $ n $ 獨立鍵 $ s_1, s_2,\dots, s_n $ . 您可以將這些收集到一個矩陣中 $ \mathbf{S} = [s_1,\dots,s_n] $ ，然後用
$$ \mathsf{Enc}_{\mathbf{S}}(\vec m) = (A, A\mathbf{S} + \vec e + (q/2)\vec m) $$
實際上，我們是在“重用” $ A $ 穿過 $ n $ 不同的加密。作為 $ A $ 是該計劃的最大（尺寸明智）部分，這是一個不錯的節省。鍵值增加一個倍數 $ n $ 儘管。我相信 PVW08 中提到了這種優化（可能是“有損陷門函式及其應用程序”？），但不知道這是否是第一次出現。
從消息空間的另一種方式 $ \mathbb{Z}/2\mathbb{Z} $ 至 $ (\mathbb{Z}/2\mathbb{Z})^n $ 就是使用更通用的環，即使用RLWE。這在數學上有點不重要，所以我將給出一個高級概述。密文現在的形式是 $ (a, as + e + (q/2)m) $ , 現在在哪裡 $ a, s, e, m $ 都是次數多項式 $ n $ . 特別是，在 $ (\mathbb{Z}/2\mathbb{Z})^n $ “免費”，特別是無需增加密鑰的大小。這是超越位加密的性能更高的方法之一，並且在實踐中非常流行（例如，每個 NIST 解決方案都使用這種方法的某個版本，即 RLWE、MLWE 或非整數 NTRU 的東西，除了FrodoKEM，出於安全原因故意不這樣做）。
如果你不喜歡它的外觀怎麼辦 $ \mathbb{Z}/2\mathbb{Z} $ 到處？上面的故事都可以概括為有消息空間 $ \mathbb{Z}p/\mathbb{Z} $ （而不是具體情況 $ p = 2 $ ) 通過切換術語 $ (q/2)m $ 至 $ (q/p)m $ （在第一種情況下，我們選擇 $ q $ 這樣 $ 2\mid q $ . 概括後，我們想要 $ p\mid q $ ）。這會產生帶有消息空間的加密 $ \mathbb{Z}/p\mathbb{Z} $ ，或者在我提到的兩個優化之後 $ (\mathbb{Z}/p\mathbb{Z})^n $ .
請注意，這不是免費的——非常粗略地說，這個詞 $ (q/2)m $ 用於確保正確的解密保持，並在存在錯誤的情況下工作 $ |e| < q/4 $ 在每個座標。對於一般 $ p $ ，這個界限變緊了，而且肯定有錯誤 $ |e| < q/2p $ 在每個座標。這個較小的錯誤導致不太安全的方案。可以通過重新參數化來解決這個問題，但關鍵是從 $ \mathbb{Z}/2\mathbb{Z}\mapsto \mathbb{Z}/p\mathbb{Z} $ 不是“免費”來的。
對於您更新的問題，值得一提的是，有基於 LWE 的加密方案（甚至 FHE ！！）具有密文擴展因子（漸近最優），請參閱