您可以通過放棄可數可加性來對可數消息/密鑰空間進行完美保密嗎？
Chor 和 Kushilevitz 的這篇經典論文表明，如果密鑰空間和消息空間都是可數無限的，那麼就不可能有一個完全安全的私鑰加密方案。他們的證明依賴於這樣一個事實，即在自然數集上不存在統一的機率測度，而這又依賴於機率測度是可數相加的事實。
但是有一個廣義的測度概念，它只需要有限可加性而不需要可數可加性。特別是，本文討論了一組自然數的漸近密度如何構成一個在平移不變性意義上是“均勻”的有限加性機率測度。
我想知道這是否可以用來恢復一些完美安全的概念。所以讓消息空間、密鑰空間和密文空間都相等 $ \mathbb{N} $ , 讓可測集的族為族 $ F $ 的所有子集 $ \mathbb{N} $ 具有明確定義的漸近密度，使用漸近密度度量選擇密鑰，並讓對手有一些有限加性機率度量 $ P $ 在消息空間之上。那麼我的問題是，是否存在一種加密方案，使得所有人 $ X,Y\in F $ 為此 $ P(C\in Y)\neq 0 $ ， 我們有 $ P(M\in X | C\in Y) = P(M\in X) $ ? （注意我用的是同一個字母 $ P $ 為了打擾他對消息空間的機率測量和密文的機率測量。）
當然，放棄可數可加性可能會使這一切變得不切實際，但我只是在問一個理論問題。
讓密鑰、消息和密文空間都是 $ \mathbb{Z} $ , 它與 $ \mathbb N $ . 我將通過將非負整數映射到偶數並將負整數映射到賠率來選擇特定的雙射，然後讓 $ \mu $ 是應用於的漸近密度測度 $ \mathbb{Z} $ 使用這個雙射。然後我們可以通過設置來構造一個一次性墊 $ c = m + k $ . 對於任何（可能是有限相加的）機率測度 $ \mu_M $ 由對手選擇 $ m $ , 和任何集合 $ Y \in F $ , $ (\mu_M \times \mu)({(m, k) \in \mathbb Z^2 \mid m + k \in Y}) = \mu(Y) $ . 也就是說，無論採用什麼度量，密文上的結果度量都是一致的 $ m $ 來自。我這樣說是為了避免內在的分裂 $ P(m \in X | c \in Y) $ 在你的問題中表達。
細節：首先，我們需要證明 $ \mu $ 是平移不變的 $ \mathbb Z $ . $ \mu(A) $ 可以等效地定義為 $ \lim_{n \to \infty} \frac{A \cap [-n, n]}{2n + 1} $ . 要看到平移不變性成立，請注意 $ |[-n, n] \cap A| $ 和 $ |[-n, n] \cap (A - x)| $ 最多只相差 $ 2 x $ ， 自從 $ [-n, n] $ 和 $ [-n + x, n + x] $ 到處重疊，除了 $ x $ 兩端的點。這在限制中變得無關緊要，因為 $ n \to \infty $ .
接下來，我們需要評估產品度量。不幸的是，對於有限加法測量，產品測量似乎沒有很好地定義。我會選擇一種產品衡量標準，但總的來說它並不是唯一的。 $$ \begin{align*} (\mu_M \times \mu)({(m, k) \in \mathbb Z^2 \mid m + k \in Y}) &= \int_{\mathbb Z} \mu({k \in \mathbb Z \mid m + k \in Y}) d\mu_M(m) \ &= \int_{\mathbb Z} \mu(Y - m) d\mu_M(m) \ &= \int_{\mathbb Z} \mu(Y) d\mu_M(m) \ &= \mu(Y) \ \end{align*} $$
在這裡，我們使用了 $ \mu $ 是平移不變的 $ \mathbb Z $ 然後 $ \mu_M $ 是一個機率測度，所以一個常數的積分（即期望值）就是那個常數。
然而，這一切在物理上都無法實現，至少使用數字電腦是這樣。任何生成隨機密鑰的方法都會給出一個具有可加性的分佈，因為它總是可以分解為離散的選擇，每個結果都有通往它的路徑，只有有限數量的選擇。我認為一般來說這在物理上是不可能的，但我對此的理由較少。