随机预言:重播

Question

我对随机神谕游戏的理解是：

对手可以使用相同的密钥(秘密但未知)多次查询甲骨文多项式。从甲骨文返回的输出中，对手必须判断甲骨文是随机选择还是密码(概率大于.5)。

那么，如何阻止对手重播攻击呢？比方说，对手已经告诉先知两次保持相同的钥匙。这两次对手都用相同的消息查询。现在，如果甲骨文选择随机，这两个输出将是不同的，非常高的概率。然而，如果oracle选择了密码，则来自oracle的两个输出都将匹配。

安全保卫是如何从琐碎的攻击中得到的？

我想到了一个想法:甲骨文有着无限大的记忆。每次查询oracle时，它都会检查先前是否提供了相同的输入。如果是这样的话，它只在内存中找不到输入时才返回错误/返回有效的输出。这个想法有意义吗？

Answer 1

据我所知，“随机甲骨文游戏”并不存在。你所说的(我想)是关于伪随机函数的.根据先前的查询，当挑战者(而不是先知)处于“随机”模式时，他可以将这对输入/输出保存在内存中。然后它不需要输出"error"，他可以返回与上一次查询相同的输出。

参考资料：

en.wikipedia.org/wiki/Pseudorandom_function_family

https://crypto.stanford.edu/pbc/notes/crypto/prf.html