針對具有短密鑰的隨機密鑰加密方案，存在 99% 成功的無界對手
可以證明，如果 $ E $ 是具有長度密鑰的確定性加密 $ n $ 和長度的消息 $ l\geq n + 10 $ 那麼存在兩條消息 $ m_0 $ , $ m_1 $ 和夏娃的策略，以便給定加密 $ c = E_{k}(m_b) $ 對於隨機 $ k $ 和 $ b \in {0, 1} $ , Eve 可以輸出 $ m_b $ 至少有機率 $ 0.99 $ . （Eve 在計算上是無界的）
證明顯示在這裡（在最後一頁）： http: //www.boazbarak.org/cs127/chap01-introduction.pdf
現在，我想為使用 n 個隨機位的隨機加密算法證明完全相同的事情。問題是某個消息的所有可能加密的集合可能要大得多。比方說 $ E $ 的隨機位是 $ r\gets{0,1}^n $ 均勻繪製，然後集合 $ {E(m;r)}_{k,r} $ 可以有大小 $ 2^{2n} $ 可能（遠）大於 $ 2^l $ 在哪裡 $ l $ 是消息的長度。
與確定性證明相比，不難證明，如果我們仍然選擇 $ m_0 $ 任意並使用相同類型的決策規則 $ A $ 對手，存在一個隨機的 $ E $ 還有一些 $ m_0 $ 這樣對於每個 $ m_1 $ 的機率 $ A $ 正確是不好的。所以為了處理隨機化的情況，我們一定不能選擇 $ m_0 $ 任意或想出一個新的決策規則 $ A $ .
我們唯一的假設是 $ D_k(E_{k}(m;r))=m $ 對所有人 $ r,m,k $ . （解密算法不能“錯過”）
我想知道是否有人可以提供有用的觀察或任何提示。
最終，我能夠解決這個問題。對於任何想知道的人，我的問題（主要是）將確定性對手決策規則推廣到隨機案例。
最初，確定性決策規則是
$$ A(ct)=\begin{cases}m_0 & ct\in{E_{sk}(m_0)\mid sk\in{0,1}^n}\m_1 & otherwise\end{cases} $$ 我把它概括為 $$ A(ct)=\begin{cases}m_0 & ct\in{E_{sk}(m_0;r)\mid sk\in{0,1}^n,r\in{0,1}^n}\m_1 & otherwise\end{cases} $$ 但好的概括是 $$ A(ct)=\begin{cases}m_0 & m_0\in{D_{sk}(ct)\mid sk\in{0,1}^n}\m_1 & otherwise\end{cases} $$ 另外，這一次你修復 $ m_1 $ 並隨機檢查 $ m_0 $ 的。好吧，名稱並不重要，但關鍵是決策規則取決於隨機消息，而不是固定消息。