Katz/Lindell 問題 2.2
2.2 證明，通過重新定義密鑰空間，我們可以假設 $ \text{Enc} $ 是確定性的而不改變 $ \text{Pr}[\text{Enc}_k(m)=c] $ 對於任何 $ m, c $ .
在解決這個問題幾個小時後，老實說，我沒有看到對密鑰空間進行修改以提供所需的結果。對所有人 $ k,m, $ 和 $ c $ 我們有 $ \text{Enc}_k(m)=c $ 以一定的機率 $ p(k,m,c)\geq 0 $ . 我們能用它做什麼？
注意： Katz/Lindell 假設 $ |\mathcal M|<\infty $ ， 和 $ \mathcal C $ 被定義為一組可能的輸出 $ \text{Enc} $ .
我相信你忽略了最重要的部分；加密映射本身可能是機率性的，這意味著我們可能有
$$ c \leftarrow \mathrm{Enc}_k(m), $$代替$$ c =\mathrm{Enc}_k(m), $$這是確定性的。在第一種情況下，使用相同密鑰和消息的第二次加密可能會導致不同的密文。一旦您意識到這一點並考慮到密鑰空間是有限的，請考慮每個固定密鑰消息對 $ (k,m) $ 隨機變數的分佈$$ \mathrm{Enc}_k(m) $$超過 $ \mathcal{C} $ 請注意，每個機率都是實數的這種分佈可以通過具有有理機率的有理分佈任意近似地近似。 讓我們說 $ p_i=a_i/b_i, $ 是密文的有理任意準確的近似機率 $ c_i $ 屬於給定的以非零機率出現的文本集 $ (k,m). $ 用分母將機率重寫為分數 $ \mathrm{LCM}(b_i) $ 我們現在可以替換密鑰 $ k $ 和
$$ \mathrm{LCM}(b_i) a_i/b_i $$所有這些密鑰現在都將確定性地映射到單個密文 $ c_i. $ 以這種方式為每個 $ (k,m) $ 對我們得到一個確定性方案。