更正損壞的共享密鑰
假設我們有一個幾乎共享的秘密。例如，如果我們與一個共享的隨機秘密源有一個嘈雜的連接。所以愛麗絲有 $ k_1 $ 鮑勃有 $ k_2 $ 相似但不一定相同 $ k_1 $ . 一種形式化可能是：
$ \operatorname{hammingDistance}(k_1,k_2) << \operatorname{length}(k_1)=\operatorname{length(k_2)} $
如果密鑰在絕對意義上是相似的，我們可以讓 Alice 向 Mac 發送一條消息，Bob 暴力破解他的密鑰的微小變化。
我們能做得更好嗎？也許以更短的共享密鑰結束。顯然我不想依賴其他密鑰交換或非對稱原語。
如果最大漢明距離 $ d $ 鍵之間足夠小（如果鍵大小較小，則程度較小 $ n $ 位是否足夠小），一種明顯的技術是 Alice 計算 $ H(k_1)=h $ 為了 $ H $ 一些加密雜湊，例如 SHA-256；並發送 $ h $ 給鮑勃。他探索 $ x $ 小漢明權重直到 $ H(k_2\oplus x)=h $ ，當他發現這樣的 $ x $ ， 他知道 $ k_1=k_2\oplus x $ . 有 $ \displaystyle\sum_{i=0}^d{{n}\choose i} $ 要嘗試的值。那是 $ 2^{\approx40.5} $ a 的雜湊值 $ n=128 $ -bit 密鑰最多 $ d=8 $ 亂碼，這對於 Bob 來說已經很慢/很昂貴，因此對於相當大的數據根本不起作用 $ d\log_2(n) $ .
如果密鑰具有足夠的熵，因此無法列舉（例如，它有 $ n\ge128 $ 均勻隨機且獨立的位）並用於加密一些與無關的快速密碼算法 $ H $ （例如 AES 時 $ H $ 是 SHA-256），這表明密鑰沒有任何用處。但是，請注意互動！作為一個極端的例子，如果密鑰被用作 HMAC-SHA-256 密鑰，並且 $ H $ 是 SHA-256，並且 $ n>512 $ ， 然後 $ k_1 $ 完全妥協，因為根據長密鑰的 HMAC 定義， $ \forall M,,\text{HMAC-SHA-256}(k_1,M)=\text{HMAC-SHA-256}(H,M) $ .
注意：這本質上是問題的蠻力方法，除了通過獨立於密鑰的正常使用的雜湊處理密鑰，我們避免以以後可能的預期方式使用密鑰。更正式的方法總是可以使用 $ k_1 $ 作為Key Derivation Function的key，保留一個派生參數用於修復 $ k_1 $ .
如果密鑰很大且熵很大（例如 256 位或更多），則無法應用上述內容，因為 $ d\log_2(n) $ 太大，或者我們不想讓 Bob 猜測，另一種選擇是使用前向糾錯：Alice 計算並揭示 $ C=\text{FEC}(k_1) $ 的 $ c $ 位，與 $ c $ 大到足以糾正預期的錯誤知道 $ k_2 $ , 但仍然是一小部分 $ n $ .
它必須使用 FEC 系統，其中消息通常用於有效負載 $ M $ 是 $ M\mathbin|C $ 和 $ C=\text{FEC}(M) $ ，這是常見的，並且包括一些Turbocode（用於 3G/4G 移動通信）。FEC 在糾正後應該很少或沒有額外的錯誤檢測能力。
Alice 計算並發送 $ C\gets\text{FEC}(k_1) $ ， 和 $ h\gets H(k_1) $ 和以前一樣。
鮑勃收到 $ C $ 和 $ h $ ，將 FEC 恢復應用於 $ C $ 和 $ k_2 $ 試探性的 $ \widetilde{k_1} $ ， 而如果 $ H(\widetilde{k_1})=h $ 得出結論 $ k_1=\widetilde{k_1} $ .
與之前的方案相比，最多 $ c $ 一些熵已經洩露 $ k_1 $ , 對於全熵 $ k_1 $ , 只要我們是安全的 $ n-c $ 仍然足夠大 $ k_1 $ 無法猜測的；和 FEC， $ H $ ，以及用於的算法 $ k_1 $ 不要干擾。
如果我們再次允許 Bob 進行一些猜測，我們可以減少關於密鑰的披露，如下所示。
愛麗絲
- 計算 $ C\gets\text{FEC}(k_1) $ 如上
- 可選地應用一些公共偽隨機排列 $ P $ 至 $ C $ , 產生 $ C’ $ （要不就 $ C’=C $ )
- 分裂 $ C’ $ 進入 $ C_1|C_2=C’ $ ， 和 $ C_2 $ 的 $ r $ -位，例如 $ r=32 $ （或更小，可能 $ 1 $ );
- 計算 $ h\gets H(C_2\mathbin|k_1) $
- 發送 $ C_1 $ 和 $ h $
鮑勃
- 恢復 $ C_1 $ 和 $ h $
- 最多 $ 2^r $ 的值 $ \widetilde{C_2} $
- 推導出相應的 $ \widetilde{C}=P^{-1}(C_1\mathbin|\widetilde{C_2}) $ （要不就 $ \widetilde{C}=C_1\mathbin|\widetilde{C_2} $ 對於沒有可選的偽隨機排列）
- 將 FEC 恢復應用於 $ \widetilde{C} $ 和 $ k_2 $ 試探性的 $ \widetilde{k_1} $
- 如果 $ H(\widetilde{C_2}\mathbin|\widetilde{k_1}) $ 火柴 $ h $
- 得出結論 $ k_1=\widetilde{k_1} $ ，然後繼續使用 Alice。
- 如果未找到匹配項，則以失敗告終。
$ C_1 $ 曾是 $ c-r $ -bit，因此最多直接洩漏了那麼多熵。偽隨機排列允許一個簡單的安全論點，即攻擊者的最佳策略有成本 $ O(2^{n-c+r}) $ 全熵運算 $ k_1 $ 即使對於病理性 FEC，但在實踐中可能沒有必要。
如果 $ k_1 $ 不是全熵，那麼 $ O(2^{\text{Entropy}(K_1)-c+r}) $ 如果我們想要一個簡單的安全論據（包括如果 $ k_1 $ 僅部分使用），我們可以通過 $ k_1 $ 在應用整個方案之前通過另一個公共 PRP，最後通過逆排列。
如果需要，可以像在OAEP中那樣從 MGF 建構 PRP 。