后量子方案是否与QROM无关？

Question

有许多“后量子”方案已经被提出。

它们的安全性仅在随机甲骨文模型下或使用分叉引理来证明。

如Boneh等人所述。(量子世界中的随机预言)，后量子方案应进一步考虑“量子可访问”随机预言(QROM)。

然而，许多不考虑QROM的方案声称它们具有量子抵抗力，因为它们的安全性是基于某些假设，如LWE或SIS。

此外，根据哈希查询的时间，这些方案只能在ROM和安全性降低项下得到验证。

那么，这些方案真的是量子抵抗吗？

我知道在某些情况下，ROM安全方案可以应用于QROM安全方案(量子ROM的安全性研究综述)。

Answer 1

我想你有点困惑，所以我试着简单地描述一下最先进的状态，看看它是否有帮助。

后量子KEM的一般设计范式分为两个步骤：

1. 建立一个IND安全的PKE，通常只基于1的一些计算问题的硬度.
2. 应用一般变换(通常是藤崎-冈本变换的一些变体)将IND-CPA安全的PKE转换为IND安全的KEM。

哈希(或任何ROM类型的东西)严格需要进入图片的唯一部分是在第二步。这个步骤是仅在ROM中完成的，还是QROM中的？这是相对简单的检查--许多作者依赖于藤崎-冈本变换的模分析，其中有一节是关于QROM中的转换的。

作者们用这个吗？你可以检查他们的设计规格- 这是KYBER的规范，NIST第3轮决赛。第四节讨论了它们的安全性分析，其中包括QROM中的分析。这是典型的“严重”结构。

请注意，KYBER正在构建的基础IND安全PKE没有提到QROM (或ROM )分析，因为在从IND安全性到IND安全性的转换过程中，只需要它(以及散列的安全性建模)。

还要注意的是，一般来说，QROM的结果往往比ROM的结果要弱--如果不做一些稍微不那么标准的假设，减少的幅度通常不会很大。这当然是一个非常不同的声明，但没有QROM分析。

1 --严格地说，这不是真的，通常从业者为了提高效率而使用其他原语(例如PRGs /可扩展的输出函数)，但如果一个人的效率略低一些，则并不严格要求这样做。