Katz/Lindell - 2.10：是否允許在完全不可區分的情況下對鍵空間進行詳盡搜尋？
我正在使用“現代密碼學導論（第 2 版）”自學
我試圖了解以下問題的解決方案如何有效：
證明滿足定義 2.5 的方案必須有 $ |K| \geq |M| $ 不使用引理 2.4。具體來說，讓 $ \Pi $ 是一個任意的加密方案 $ |K| < |M| $ 顯示一個 $ A $ 為此 $ Pr[PrivK^{eav}_{A,\Pi} = 1] > \frac{1}{2} $
一些符號：
定義 2.5 是：
加密方案 $ \Pi = (Gen, Enc, Dec) $ 有消息空間 $ M $ 是完美的，如果對於每個 $ A $ 它認為
$$ Pr[Priv^{eav}_{A,\Pi} = 1] = \frac{1}{2} $$
該符號表示對手正確猜測輸入消息的機率必須等於 $ \frac{1}{2} $ 為完美的不可區分性舉行。
但是，該解決方案對我來說沒有意義。
解決方案是：
考慮以下 $ A $ : 輸出統一 $ m_0, m_1 \in M $ . 收到密文後 $ c $ , 通過（窮舉搜尋）檢查是否存在鍵 $ k $ 這樣 $ Dec_k(c) = m_0 $ . 如果是，則輸出 0；否則輸出 1。
這個解決方案似乎有問題，因為它說對手對密鑰空間進行詳盡的搜尋是有效的。但如果是這種情況，對於任何不可區分性實驗，我們可能會有一個對手在密鑰空間上執行詳盡的搜尋以確定密文解密到什麼。
有誰明白髮生了什麼？
這種推理很誘人，但並不合理：“我們可以讓對手在密鑰空間上進行詳盡的搜尋，以確定密文解密到什麼。”
問題在於，在檢查每個密鑰時，可能不清楚哪一個是“正確”的，即密文實際解密為什麼明文。
要具體了解這一點，請考慮一次性墊，這是完全無法區分的。給一個密文，當用密鑰空間中的每個密鑰解密它時，我們得到所有可能的明文（與密文長度相同）。這可能包括許多“無意義的”明文，但也包括所有“合理的”明文（長度合適）。對手無法分辨出這些候選明文中的哪一個是“真實的”。事實上，完美的不可區分性意味著對手在看到密文之後並沒有比在看到密文之前更清楚正確的明文是什麼。
因此，在完全不可區分的情況下，當然允許窮舉鍵搜尋，但即使這樣也無助於對手破壞完全不可區分的系統。