用PRF构造PRG的几个问题

Question

设F是一个具有128位密钥和256位块长度的安全伪随机函数.下面哪个函数G是安全伪随机发生器？(选择所有适用的。)

A. G(x)=F_x(0...0)，其中x是128-bit输入。

B. G(x)=F_x(0...0)|| F_x(0...0)，其中x是128-bit输入。

C. G(x)=F_x(0...0)||F_x(1...1)，其中x是128-bit输入。

D. G(x)=F_{0...0}(x)|| F_{1...1}(x)，其中x是256-bit输入。

我们老师给出的答案是A,D。但我不明白。为什么C是错的？

Answer 1

我们不直接回答家庭作业问题，但会给出提示。

假定攻击者控制所有非秘密输入。钥匙是秘密的，那块不是。这个答案对PRG有一个很好的定义:简单地说，PRG是一个函数，它接受固定长度的秘密输入种子位串，并输出一个不能与不可忽略的随机位串区分的更长的位串。

A. G(x)=F_{x}(0...0)，其中x是128位输入键.

攻击者是否控制任何输入？攻击者能否以不可忽略的概率区分输出和随机函数的输出(即，在输出中是否有任何可观察的模式)？输出比输入长吗？

唯一的输入变量是一个秘密密钥。没有额外的模式被添加到输出。输出多长时间？

B. G(x)=F_{x}(0...0)||F_{x}(0...0)，其中x是128位输入键.

同样的问题。

唯一的输入变量是一个秘密密钥。输出重复某些序列两次。输出多长时间？

C. G(x)=F_{x}(0...0)||F_{x}(1...1)，其中x是128位输入键.

同样的问题。

唯一的输入变量是一个秘密密钥。输出有额外的模式吗？输出多长时间？

D. G(x)=F_{0...0}(x)||F_{1...1}(x)，其中x是一个256位输入数据块.

同样的问题。

唯一的输入变量是公共数据块。输出有额外的模式吗？输出多长时间？

有一个缺失的选项继续这种模式: E. G(x)=F_{0...0}(x)||F_{0...0}(x)，其中x是一个公共256位数据块。

如果你能回答A-D，E应该是微不足道的。