具有機率解密的加密方案的優點和可能的用途
我們可以定義確定性和機率性加密；
確定性 $ c = E(k,m) $ ， 和
- 範例是教科書 RSA，ECB 模式下的分組密碼。
- 確定性加密無法實現 CPA 安全性。
- 確定性加密是不安全的，我們不想使用/建議使用（有一些不好的例外情況，例如 SIV 模式沒有 CPA 安全性，如果您保持 nonce 固定不要這樣做（（見註 3） )，但是，AES-GCM-SIV 是一種非防誤用方案，可防止 AES-GCM 的 IV 重用問題)
機率的 $ c \stackrel{R}{\leftarrow} E(k,m) $
- Elgamal、RSA-OAEP、Pailler 等公共方案和 CBC、CTR、CGM、SIV 等私人方案。
在確定性的情況下，有一個密文可以解密到消息，而在機率性的情況下，有很多是可以預期的。
從正確性要求，我們想要
- 對於確定性情況 $ m = D(k,E(k,m)) $
- 對於機率情況 $ c \stackrel{R}{\leftarrow} E(k,m) $ , $ m’ = D(k,c) $ 機率為 1。
機率加密是可取的，因為它可以提供語義安全或其等效且易於使用的版本是不可區分的。
現在，如果將機率解密的定義設置為大於：$$ \Pr[D(k,E(k,(m))=m] = 1 - negl(k) $$
相反，使它：
$$ \Pr[D(k,E(k,(m))=m] = p $$
這方面的一個例子是Rabin 密碼系統（見註 2），其中 $ p = 1/4 $ 因為我們最終有四種可能 $ m $ . 建議在明文中添加一些輔助數據來解析。請注意，Rabin 密碼系統不是隨機加密，通常需要 IV/nonce 來實現。解密仍然產生隨機解密。
- 除了半隨機拉賓密碼系統之外，還有其他隨機解密方案的例子嗎？
- 隨機解密方案有什麼優勢或用途嗎？
筆記：
因為在解密時我們總是希望得到正確的資訊，所以我們沒有理由讓這個模棱兩可。它沒有安全優勢（如果對手可以以任何不可忽略的機率猜測，你已經輸了，所以模棱兩可的解密不會變得更難）。因此，與安全所需的機率加密不同，機率解密是一種不受歡迎的屬性，有時在嘗試建構方案時會出現。例如，對於天真的拉賓，它恰好是所用數論的一個屬性。使拉賓成為活板門排列所需的額外工作對於使其有用是必要的。
因此，隨機解密（有錯誤機率）存在的唯一原因是某些結構不幸地給了我們。（這在某種意義上可以被視為一種優勢——如果我們不能允許解密錯誤，我們將無法建構這些方案，其中一些具有優勢。）有一些這樣的例子：NTRU 和基於格的 Ajtai 方案。因此，已經有一些理論上的工作來消除具有錯誤的加密方案中的錯誤。最值得注意的是，我推薦閱讀 Dwork、Naor 和 Reingold 的論文Immunizing Encryption Schemes from Decryption Errors。