香农完全保密是否意味着确定性加密算法？

Question

考虑一个加密方案(Gen,Enc,Dec)，其中Gen是密钥生成算法，Enc是加密算法，其中c \leftarrow Enc_{k}(m) 意味着使用Gen从某个密钥空间K生成的密钥k加密的消息空间M中的消息m生成密文c，它属于某些密匙空间C，其中Dec_{k}(c) = m是始终具有确定性的解密算法。

在Shannon完全保密理论中，假定|K| = |M| = |C|是完全保密的。这是否意味着Enc是确定性的？

也就是说，不可能存在两种不同的密文c_{1},c_{2} \in C，它们都是通过加密相同的(消息、密钥)对而产生的？看来，一旦限制这三个空间具有相等的基数，加密算法就必须是确定性的，但我似乎无法正式证明这一点。

Answer 1

在Shannon完全保密理论中，假定|K| = |M| = |C|是完全保密的。这是否意味着Enc是确定性的？

实际上，标准的定义并不意味着。|K| \ge |M|和|C| \ge |M|是必要的，但是在这两种情况下，平等都不一定成立。

无论如何，我将继续假设我们有|M| = |C| (密钥的长度对您的问题并不重要)

这是否意味着Enc是确定性的？

是的，鸽子洞的校长是你的朋友。

考虑任何固定的密钥k，以及所有长度为n的明文(其中有2^n )。如果使用密钥对其中任何一个进行加密，则会产生长度为n的密文(而且，还有2^n可能的密文)。

我们假设加密过程是可逆的(即对任何Dec_k(Enc_k(m)) = m )，因此两个不同的明文必然导致不同的密文。

有2^n明文映射到2^n密文，因此每个明文必须精确地映射到一个密文(鸽子洞原则；如果有一个明文可以映射到两个不同的密文，那么必须有一个明文不能映射到任何明文，而且我们假设不会发生这种情况)。

因此，对任何特定密钥的加密都是确定性的；这意味着所有密钥的加密都是确定性的。