完美隱私的證明意味著密鑰的數量至少是消息的數量
我正在閱讀該聲明的證明：
完美的隱私意味著 $ |K| = |M| $
我很確定 $ K $ 是一組鍵和 $ M $ 是消息的集合。
證明如下，但我不明白（可能是因為符號）。
假設不是，即假設我們的鍵比消息少。給定一個密文 $ c $ , 有消息 $ m $ 和一把鑰匙 $ k $ 這樣：
$ e(k, m) = c $ ， 和 $ p_{k \in K}[e(k, m) = c] > 0 $
讓 $ P_c = { m \in M $ 這樣 $ e(k, m) = c $ 對於一些 $ k } $
由於每 $ k $ 恰好映射一條消息 $ m $ 至 $ c $ ，並且由於我們的鍵比消息少，所以有 $ m’ $ 不在 $ P_c $ 這樣沒有鑰匙 $ k $ 地圖 $ m’ $ 至 $ c $ .
所以 $ P_{k \in K}[e(k, m’) = c] = 0 $ , 這違反了對所有 m 和 $ m’ $ , $ P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m’). = c] $ .
在哪裡 $ k \in K $ 意思是 $ k $ 是集合中的一個鍵 $ K $ .
我不明白的第一件事是以下符號： $ p_{k \in K}[e(k, m) = c] > 0 $ . 這到底是什麼意思？做 $ p $ 參考機率？
我理解了以下聲明：
由於每 $ k $ 恰好映射一條消息 $ m $ 至 $ c $
一個函式應該只為相同的輸入輸出一個結果是有道理的。
所以 $ P_{k \in K}[e(k, m’) = c] = 0 $
這是否意味著我們加密的機率 $ m’ $ 使用 $ k $ 結果是密碼 $ c $ 等於 $ 0 $ 因為，正如之前在證明中所說， $ m’ $ 是沒有密鑰的消息 $ k $ 將其轉換為 $ c $ ? 如果是，我仍然不是 100% 相信的。
這違反了對所有 m 和 $ m’ $ , $ P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m’). = c] $
如果我們一開始就假設 $ p_{k \in K}[e(k, m) = c] > 0 $ , 上面的陳述也是有道理的。
再一次，我沒有得到假設的部分 $ p_{k \in K}[e(k, m) = c] > 0 $ （除了我不確定是否 $ p $ 應該 $ P $ , 即如果它只是一個錯字，如果 $ P $ （或者 $ p $ ）指的是機率，正如我在上面想知道的）。
此外，我認為證明沒有顯示密鑰數量大於消息數量的情況。
讓 $ K $ 是所有可能的密鑰的集合（對於 AES-256，這個集合有 $ 2^{256} $ 元素。）
讓 $ M $ 是所有可能消息的集合（對於 AES，它有 $ 2^{128} $ 元素）。
讓 $ C $ 是所有可能的密文的集合（對於 AES，再次 $ 2^{128} $ 元素）。
我正在閱讀該聲明的證明：
> > 完美的隱私意味著 $ |K|=|M| $ > > >
其實這是 $ |K| \ge |M| $ .
完美的隱私條件是：
為所有人 $ m $ 和 $ m′ $ , $ P_{k \in K}[e(k,m)=c]=P_{k \in K}[e(k,m′).=c] $
密文的機率 $ c $ 被解密為 $ m $ 和被解密一樣 $ m’ $ .
或者換句話說：
你找不到兩者之間的區別 $ m $ 和 $ m’ $ .
為了證明這樣的陳述，你使用reductio ad absurdum。在這裡你假設 $ |M| > |K| $ .
我不明白的第一件事是以下符號： $ p_{k \in K}[e(k,m)=c]>0 $ . 這到底是什麼意思 ？
是的 $ p $ 是一個錯字，應該是 $ P $ . 這意味著存在 $ k $ 和 $ m $ 如 $ e(k,m)=c $ （這很簡單，因為我們需要一個有效的算法……）。因此，給定 a 的機率 $ c $ , $ m $ 是純文字至少是 $ \frac{1}{|M|} $ （假設均勻分佈），因此 $ > 0 $ .
關於這部分：
所以 $ P_{k \in K}[e(k,m′)=c]=0 $
這是否意味著我們加密的機率 $ m′ $ 使用 $ k $ 結果是密碼 $ c $ 等於 $ 0 $ 因為，正如之前在證明中所說， $ m′ $ 是沒有密鑰的消息 $ k $ 將其轉換為 $ c $ ? 如果是，我仍然不是 100% 相信的。
你必須首先想到的是 $ c $ 是固定的。為了加密消息 $ m $ 對此 $ c $ 你需要一把鑰匙 $ k $ . 因為 $ |M| $ 大於 $ |K| $ （認為 $ |M| = 5 $ 和 $ |K| = 3 $ )，存在沒有映射到的消息 $ c $ （在這種情況下 $ 5 - 3 = 2 $ ）。因此存在 $ m’ $ 比如沒有 $ k $ 以便 $ e(k,m) = c $ . 因此 $ P_{k \in K}[e(k,m′)=c]=0 $
因為完全保密的聲明適用於所有人 $ m $ 和 $ m’ $ 你不能同時擁有所有的機率 $ > 0 $ 和 $ = 0 $ . 所以你有矛盾。
據我所知，這種說法是不正確的。完全保密意味著 $ |K|\geq |M| $ （正如您在現代密碼學導論中的定理 2.10 中看到的那樣）並且並不意味著 $ |M|=|K| $ 一定。您提到的證明適用於 $ |K|>|M| $ （是的，我相信 $ p $ 指機率）。
這裡也是這個定理的 Katz 和 Lindell 證明（這個證明與你的證明基本相同，只是不同的符號可能對你有幫助）：
認為 $ |K|<|M| $ , 考慮均勻分佈 $ M $ 然後讓 $ c\in C $ 是非零機率發生的密文。讓 $ M(c) $ 是可能解密c的所有可能消息的集合；那是
$$ M(c)={m|m=Dec_k(c) \text{ for some } k\in K} $$ 清楚地 $ M(c)\leq |K| $ . （回想一下，我們可以假設 Dec 是確定性的）。如果 $ |k|<|M| $ ， 有一些 $ m’\in M $ 這樣 $ m’\notin M(c) $ . 但是之後： $$ Pr[M=m’|C=c]=0\neq Pr[M=m’] $$ 所以這個方案並不完全安全。