可以用伪随机发生器对HE密码进行采样吗？

Question

我试着取样他的密文，作为加密文件，对一些随机值进行加密。我用Microsoft实现了一个示例程序，实现了BFV方案的一个变体。不幸的是，这些均匀分布的密文的“噪声预算”为零，因此它们不能支持任何进一步的同态评估。然而，当我从离散的Guassian分布(平均值= 0)中提取这些密文时，它们具有非零的“噪声预算”，并且工作得很好。

我对这个结果很困惑。由于BFV方案是IND安全的，其有效的新密文不应与格式错误的密文(即从均匀分布中提取)区别开来。然而，实验结果表明，均匀分布的密文并不能以压倒性概率形成BFV方案的有效密文。

有什么问题吗？非常感谢。

Answer 1

由于BFV方案是IND安全的，其有效的新密文不应与格式错误的密文(即从均匀分布中提取)区别开来。

IND说，不知道秘密密钥的人无法区分这两个发行版。

然而，实验结果表明，均匀分布的密文并不构成BFV格式的有效密文。

只有当您拥有密钥时，才能检查密文是否“有效”。所以没有矛盾。

一个类比是一个长度加倍的PRG G: \{0,1\}^n \to \{0,1\}^{2n}.PRG的输出与\{0,1\}^{2n}上的均匀分布是无法区分的。这并不意味着\{0,1\}^{2n}中的大多数字符串都是PRG的“有效输出”。事实上，它们中只有一个可以忽略不计的部分(从2^n到2^{2n})。