加密的糾錯功能？
這是由這個關於恢復（損壞的）加密文件的問題所激發的，特別是以下語句（在答案中）：
但是，如果我知道算法和密鑰，並且我製作了一個自定義軟體來解密文件的內容，無論如何，我可能會得到一個解密的 JPEG，在某些地方可能部分可見/混亂。
一般來說，像全盤加密這樣的東西如何與隨機翻轉的位互動是我沒有想到的。有兩個明顯的解決方案：
- 將全盤加密包裝在糾錯碼中
- 最小化每個加密數據“塊”的大小，並在出現錯誤時接受數據的完全失去（到那個單個小塊）（儘管我不相信這不是全盤加密）。
這個問題正在詢問其他潛在的解決方案。
對於固定鍵 $ k\in\mathcal{K} $ 和加密隨機性 $ r\in\mathcal{R} $ , 可以查看加密方案 $ m\mapsto \mathsf{Enc}k(m;r) $ 作為具有域的程式碼（在編碼理論的意義上） $ \mathcal{M} $ 和共域 $ \mathcal{C}{k, r}\subseteq \mathcal{X} $ . 加密方案的正確性表明程式碼是唯一可解碼的，可以將其寫為條件： $$ \forall k\in\mathcal{K} : \mathsf{Dec}_k(\mathsf{Enc}_k(m; \mathcal{R})) = m $$ 可以定義一個程式碼 $ \mathcal{M} $ 和 $ \mathcal{X} $ 抽像地通過這對映射 $ \mathsf{encode} $ 和 $ \mathsf{decode} $ . 然後可以通過上述條件擷取幾個編碼理論屬性，例如獨特的可解碼性： $$ \forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m)) = m $$ 一個更有趣的能力是能夠糾正一些有界集合中的錯誤 $ \mathcal{E} $ . 這通常具有“幾何”風味（ $ \mathcal{E} $ 在某些規範中是一個球，所以錯誤是“小”），但我不會強加這個要求。編碼 $ (\mathsf{encode}, \mathsf{decode} $ ) 可以更正 $ \mathcal{E} $ 如果： $$ \forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m) + \mathcal{E}) = m $$
我很好奇關於 IND-CPA 加密方案的糾錯能力可以說些什麼。他們顯然可以有一些，原因很簡單，如果 $ (\mathsf{Enc}_k, \mathsf{Dec}_k) $ 是 IND-CPA，並且 $ (\mathsf{encode}, \mathsf{decode}) $ 可以改正 $ \mathcal{E} $ 錯誤，那麼 $ (\mathsf{encode}\circ \mathsf{Enc}_k, \mathsf{Dec}_k\circ\mathsf{decode}) $ 仍然是 IND-CPA（其密文可從初始方案的密文公開計算），但現在可以更正 $ \mathcal{E} $ 錯誤。
因此，問題是任何常見的方案是否有任何糾錯特性可言。具體來說，如果我採取一些密文 $ c $ 並在其中“翻轉”一點（或添加任何其他潛在的微小錯誤），關於明文與“真正的明文”的關係可以說什麼嗎？是否任何 IND-CPA 安全方案都帶有“嵌入”的糾錯功能，或者它們是否必須像我上面提到的結構中那樣明確地與糾錯程式碼相結合？
請注意，即使這些方案不再正確，但在某種意義上“接近正確”，我也會感興趣。特別是，如果 $ \forall k\in\mathcal{K} $ : $$ \mathsf{Dec}_k(\mathsf{Enc}_k(m;\mathcal{R}) + \mathcal{E}) \in m + \mathcal{E}’ $$ 在哪裡 $ \mathcal{E}’ $ 是一些允許的錯誤，並有望與 $ \mathcal{E} $ （即如果承諾雜訊很小，那麼由此產生的誤差也很小）。
請注意，對上述問題的一個明顯答案（LWE 加密，它已經具有自然的編碼理論解釋）似乎只能部分起作用 — 形式的密文 $ (a, b) $ 正在糾錯“在 $ b $ 插槽”自然，但不是“在 $ a $ 插槽”。然後可以定義一組錯誤 $ \mathcal{E} = {0}^n\times \overline{\mathcal{E}} $ （在哪裡 $ a $ 是 $ n $ -維），和 $ \overline{\mathcal{E}} $ 在精確的意義上是“足夠小”。由於錯誤的“人為”形狀，我發現這有點不滿意 $ \mathcal{E} $ （並且基於 LWE 的加密可以說已經需要選擇一個糾錯碼，因此它具有“嵌入”的糾錯屬性並不令人驚訝）。
評論太長了：
讓 $ {\cal M}={0,1}^n, $ 和 $ {\cal K}={0,1}^k. $ 讓集 $ \cal E, $ 有基數 $ 2^{f}, $ 為簡單起見（順便說一句，如果您只對停止低權重錯誤感興趣，那麼任何漢明球都不會有這個值）。您要求每條消息 $ m\in {\cal M} $ 並且對於每個 $ e\in {\cal E} $ 我們有： $$ E^{-1}_k(E_k(m)+e)=m ,\quad \forall k\in {\cal K} $$ 這會影響效率，因為您不再真正加密消息 $ m $ 一對一但加密消息的等價類，其中消息的等價類 $ m $ 是 $$ [m]={m+e: e \in {\cal E}}. $$ 特別是，您的有效消息空間現在是 $ {\cal M}^\ast={[m]: m \in {\cal E}} $ 有大小 $ 2^{n-f}. $ 事實上，這種設置讓人想起 Gilbert-Sloane 的無保密（密鑰）身份驗證程式碼 (MAC) 設置。
在安全參數方面，如果你願意，我敢說 $ N $ 您可能想要選擇的位安全性 $ n=N+f, $ 和 $ k=N, $ 如果你喜歡 keylength=blocklength 機制，平衡字典和暴力攻擊。據推測，AES-256 可能會以這種方式使用。
然而，一個設計得體的分組密碼，在設計時具有雪崩特性，不太可能有一個集合 $ \cal E $ 它以任何重要的方式與以零為中心的漢明球重疊。
可能有一些特定的案例需要組合操作，但總的來說，我看不到加密然後編碼的好處。主要缺點是，如果該方案不等同於加密後編碼——也就是說，編碼確實是加密的基本部分——那麼如果不使用密鑰進行解密，就不可能糾正錯誤。也就是說，如果這種組合的加密和編碼不能分離成獨立的步驟 $ E_k(m) = Encode(Encrypt(m, k)) $ ，那麼一定是沒有密鑰無關的糾錯或檢測算法。對於長期儲存而言，這將是一個重大問題，否則設備可能會持續監控和糾正“位腐爛”。
一般來說，編碼參數（即糾錯能力）應根據儲存介質或傳輸通道的特性來選擇。一段加密的數據可能會在多個不同的通道上移動，最好是 1) 在每個步驟中糾正任何錯誤（不解密）和 2) 為每個步驟優化編碼數據。像這樣的方案需要在內置的基礎上增加額外的冗餘，這只是低效的。加密和編碼是分開的足夠多的關注點，算法和參數應該獨立選擇。