為什麼我們總是可以假設GenGenGen算法統一選擇密鑰？
免責聲明：這是 Katz-Lindell 書中的練習 2.1。
給定一個（對稱）加密方案 $ \Pi=(Gen,Enc,Dec) $ 在哪裡 $ Gen $ 接受安全參數 $ 1^n $ 作為輸入並生成一個密鑰 $ k $ 長度 $ n $ .
通常我們簡單地假設 $ Gen $ 從中統一選擇密鑰 $ {0,1}^n $ 但情況並非總是如此。
給定 $ Gen $ ，你將如何構造一個新的生成算法 $ Gen’ $ 確實輸出 $ k $ 均勻隨機？
您是否試圖為特定的加密方案或任何方案證明這一點？
如果您有特定的方案，可以考慮使用拒絕抽樣。在您的情況下，使用起來非常簡單：
讓我們說每個鍵 $ k\in {0,1}^n $ 由輸出 $ Gen $ 有機率 $ p(k) $ ， 和 $ p_{min} \overset{def}{=} \min\limits_{k} p(k) $ . 然後你可以定義 $ GenU(1^n) $ 每個例子是這樣的：
$ GenU(1^n): $
$ k \leftarrow Gen(1^n) $
有機率 $ p_{min}/p(k) $ ， 輸出 $ k $ , 否則重啟
你可以看到一個迭代 $ GenU $ 輸出每個 $ k $ 有機率 $ p_{min} $ , 並終止 ( $ ie $ 不重新啟動）有機率 $ \sum_{k} p_{min} = 2^n\cdot p_{min} $ .
現在，該算法假設您可以有效地計算每個 $ p(k) $ . 此外，如果 $ p_{min} $ 遠小於其他值 $ p(k) $ ， 然後 $ GenU $ 終止可能需要不切實際的時間（ $ eg $ 如果 $ p_{min} = 2^{-2n} $ , 然後迭代 $ GenU $ 將有可能終止 $ 2^{-n} $ ).
由於這些原因，如果你想在一般情況下證明你的命題，你不能照原樣應用這個算法。希望它有所幫助。