基于SHA-256的随机预言

Question

我有以下问题。

将SHA-256看作是一个实际应用中的随机预言。构造基于SHA-256的(几乎)随机甲骨文\{0,1\}^*→\{0,1\}^{3000}。

这是否意味着输入是任意长度的零和一，也就是说，应该散列到一个值，是3000位数的零和1？如果是，我可以只应用SHA-256 12次，将输入分成12部分，删除72位，然后我将得到3000位？还是我误会了？

Answer 1

这是否意味着输入是任意长度的零和一，也就是说，应该散列到一个值，是3000位数的零和1？

是的，这就是\{0,1\}^*→\{0,1\}^{3000}的意思。最好用常用的快捷方式来重新定义“零和1的数字”：位。另外，\{0,1\}^*是所有位字符串的集合。

我可以只应用SHA-256 12次，将输入分成12部分，删除72位，然后得到3000位吗？

256\times12-72=3000，因此您拥有域的权限。但是，这是否与随意的先知没有区别呢？不是的。找出你会如何区分。那就改进这个结构。理想情况下，证明如果一种方法可以区分精细的构造和随机的甲骨文，那么它就可以变成对SHA-256进行这种区分的方法。

带有k-bit输出的随机预言是一个假设的设备，它接受位字符串作为输入，以及

• 如果该位字符串以前没有提交，则在\{0,1\}^k中绘制并输出一个随机位字符串。
• 否则，就会输出与以前提交的输入位串相同的位串。

既无法计算SHA-256，也可能忽略了SHA-256的长度扩展属性及其输入长度限制；这些问题中的一部分或全部可能是“(几乎)”的含义。