通过丢弃可数可加性，你能对可数消息/密钥空间有完全的保密吗？

Question

Chor和Kushilevitz的这篇经典论文证明了如果密钥空间和消息空间都是可数无限的，那么就不可能有一个完全安全的私钥加密方案。它们的证明依赖于自然数集上不存在一致概率测度的事实，而这又依赖于概率测度是可数可加的事实。

但是有一个广义的测度概念，它只需要有限可加性，而不需要可数可加性。特别地，本论文讨论了一组自然数的渐近密度如何构成平移不变性意义下的“一致”有限加性概率测度。

我想知道这是否可以用来恢复一些完美安全的概念。因此，让消息空间、密钥空间和密文空间都相等\mathbb{N}，让可测集族是具有定义的渐近密度的\mathbb{N}的所有子集的族F，让密钥使用渐近密度测度来选择，并让对手在消息空间上有一些有限加性的概率测度P。那么我的问题是，是否存在这样一个加密方案，对于所有的X,Y\in F ( P(C\in Y)\neq 0 )，我们都有P(M\in X | C\in Y) = P(M\in X)？(请注意，我使用相同的字母P来处理消息空间上的概率测度和密文的概率度量。)

当然，降低可数可加性可能会使这一切变得不现实，但我只是在问一个理论问题。

Answer 1

"…允许使用渐近密度测度…选择密钥“

嗯，就实用性而言，这是你的第一个问题。根据定义，任何有界整数集的渐近密度为零。

那么，你的钥匙短于1G的概率？零。

你拥有足够的磁盘空间来存储密钥的可能性？零。

在可观测的宇宙中存在足够多的原子来存储密钥的概率(假设每个原子存储的位数有限)？再来一次，零。

就纯数学而言，确实有趣的是，人们可以(显然)利用这些疯狂的度量来使概率论的一些非平凡子集发挥作用。人们甚至可能会想，这些度量是否可以被以某种方式重新解释(例如，通过将它们映射到一个有界的reals子集上的度量)，从而将它们转化为一个可以近似抽样的方法，或者它们根本不可能用常规的概率度量来近似。但就实际情况而言，嗯，他们似乎并没有。

(哦，那论文中讨论的“两个信封悖论”呢？通过注意两个随机变量的比率的期望值不等于它们的期望值的比率来更直接地解决，决定切换是否有利的是后者，而不是前者。(不需要奇怪的伪概率度量。)

Answer 2

我不认为这个问题很有意义。

让我们再仔细看一看这一措施：

• 首先，测量的是密度的极限。这意味着，这是自然数的无限子集。它不以任何方式测量单个元素。所有有限集都有测度0。
• 加法性质仅适用于自然数的析取子集。它没有给你一个建设性的方法来创建这些子集。
• 这不是一个统一的分布。翻译不变性是必要的，但不是充分的。
• 我根本不称它为概率分布:如果被测集是自然数所有子集上的变量，那么所有P(X)上的和是无限的。

现在让我们看看你的想法：

我想知道这是否可以用来恢复一些完美安全的概念。所以让消息空间、密钥空间和密文空间都等于N，

因此，消息、密钥和密码文本是\mathbb{N}的单个元素。在这里，你不能用任何有意义的方法来使用这个方法。定义不匹配。完善的安全性要求对一条特定的消息或密码文本采取某种措施。

设可测集族是具有良好渐近密度的N个子集的族F，用渐近密度测度选择密钥，

那该怎么做？这个度量没有给你一个建设性的方法来使用它来随意地绘制元素。

并让对手在消息空间上有有限的加性概率测度P。

因为这个措施是一般定义的，所以只给对手看是没有意义的。

那么，我的问题是，是否存在这样的加密方案，对于所有的X，Y∈F，其中P(C∈Y)≠0，我们有P(M∈X C∈Y)=P(M∈X)？(请注意，我使用相同的字母P表示消息空间上的概率测度和密文的概率测度。)

这一定义没有任何意义。通过添加单个元素，度量值不会改变。您尝试测量某种差异，无论单个元素是否存在于这些子集中。所以这个问题是无法回答的。但是，即使你使用无限集作为消息，密码文本和密钥，这个定义也没有意义--只有当集合是分离的时候，有限加性属性才能起作用。我看不出对整个消息或密码文本空间有任何有意义的定义。