security - 安全 PRG 和语义安全之间的区别

Question

我正在斯坦福大学的 coursera 上学习密码学课程。我有以下问题。

我有一个问题，为什么在 G(k) 中附加 0，即 G'(k) = G(k) || 0 被认为是不安全的 PRG，因为消息中的 0 是在未加密的情况下复制的。而在语义安全 E'(k,m) = 0 || E(k,m) 即前置 0 被认为是语义安全的。为什么附加 0 不会破坏语义安全？

请要求澄清。

Answer 1

你在比较两个不同的东西。一个是 PRG（伪随机生成器），另一个是 PRP（伪随机排列）。

PRG 只有一个输入，即密钥，并且输出应该足够随机，以至于与真正的随机块无法区分。这意味着当对手查看字符串时，他无法确定输出是来自 PRG 还是真正的随机块。但是，当您附加 0 时，您可以轻松区分您使用的是真正的随机生成器还是 G'（因为真正的随机仅在一半的情况下以 0 结尾，而 G' 总是以 0 结尾）。

在第二种情况下，对手想要找到一些关于明文 m 的信息。我们假设 E(k,m) 是安全的。现在的问题是：E'(k,m) 安全吗？前面的 0 是否为您提供了有关明文 m 的一些信息？如果是这样，则意味着您拥有“一种工具”，可以从 E'(k,m) 中提取有关 m 的一些信息。如果你有这样的工具，你能用它来打破 E(k,m) 吗？是的你可以。您可以获得 E(k,m) 的输出，在前面加上 0 并将其传递给您的工具。瞧，您刚刚破坏了 E(k,m)，但这意味着我们对 E(k,m) 安全的假设是不正确的。