非对称CSPRNG，其中公钥只向后工作

Question

是否存在不对称密码安全伪随机数生成器，其中公钥只向后退？例如，我想生成5,000位数字，然后向另一方提供公钥和RNG状态。然后，他们向后生成5,000到1的相同数字。第二方不应该能够计算5,001个数字。

编辑：这是一个工作演示的丹尼牛的RSA方法。

Answer 1

免责声明:我还没有验证我的提案的安全性。

你可以用两种方式实现这一点:一种是前量子，使用类似RSA的方案，另一种是后量子，使用多变量系统。

1. RSA版本。

生成一个RSA密钥对，将私钥(N,d)留给自己，将公钥(N,e)交给第二方。

要生成新的数字，请计算x_{i+1} = x_i^d \pmod N。这样，第二方就可以通过计算x_i从已知的x_{i-1} = x_i^e \pmod N返回。

1. 多元版本。

这个版本比RSA版本要重得多.虽然在NIST PQC“竞赛”中有几个多变量签名方案(使用MV构建安全加密方案似乎很困难)，但其中许多方案使用奇异的方法来压缩公钥，这可能是可选的，这取决于您的用例。

在它的简单形式中，您有一个公共多元系统P，它是私有组件S \circ F \circ T的组合，其中F是一个容易解的二次系统，S和T是线性的。

为了产生新的随机数，

1. 计算u = S^{-1}(x_i)
2. 求解u = F(v)并选择任意v
3. 计算x_{i+1} = T^{-1}(v)

第二方可以使用x_{i-1} = P(x_i)将其逆转。

正如poncho在评论中提到的那样，解决的v可能不是唯一的解决方案，但这不是一个问题，因为任何生成的x_{i+1}都满足x_i = P(x_{i+1})。

编辑

看来你对这些符号不太熟悉。

在x_{i\pm1}中，i\pm1是下标，所以就程序员所熟悉的术语而言，它是x[i+1]或x[i-1]。

x_i是PRNG的当前状态。由于这是一些算术运算的输出，它的位模式不是完全随机的(即可能不通过一些复杂的统计测试)，因此您可能需要截断它和/或散列它，以获得一些高质量的随机比特- TLS协议也是出于同样的原因而进行的。

是的，它是一个迭代生成器，但是我不知道你所说的“代数”是什么意思，以及为什么你认为第二个注释中它是低效的。