PQC NIST round3提交的测试

Question

我是这个领域的新手，对PQC有一些关注；

NIST如何比较一个特定的算法是有效的，并且它的安全性不能被未来的量子攻击破坏？我很想了解这些准则。

NIST曾试图利用IBM的量子计算机应用Shor的算法来破解加密算法吗？

NIST检查PQC算法提交的标准是什么？

Answer 1

NIST如何比较一个特定的算法是有效的，并且它的安全性不能被未来的量子攻击破坏？

实现一个算法的效率是很容易的--这些算法运行在经典的计算机上，因此人们已经实现了这些算法，并且直接测量其性能。

安全性是用我们对非量子算法使用的方法来衡量的--人们设计出他们能想到的最好的密码分析算法来打破它们，估计这些密码分析算法的运行时间，这样我们就可以选择安全参数，从而使所有这些已知的密码分析算法花费不可行的时间运行。

PQC算法和非PQC算法的唯一区别是，对于PQC算法，我们还考虑了在量子计算机上运行的密码分析算法。这有点棘手，因为我们没有可以运行非平凡密码分析算法的任何东西( IBM量子计算机和类似的计算机太小，无法执行所需的错误校正)，而量子模拟器(在经典计算机上运行)所能处理的量子位数也受到限制。另一方面，我们确实对量子计算机可以做什么操作有很好的理解，所以我们可以设计能够在量子计算机上运行的算法。NIST并没有完成所有这些设计工作--绝大多数工作都是由NIST以外的学者和密码专家完成的-- NIST密切关注这项工作，并考虑到了这一点。

Answer 2

值得一提的是，具体估算各种问题的量子硬度仍是一个非常新的研究领域，有些问题仍未解决。这方面的一个很好的例子是Piekert的论文他用CSIDH给了C筛。除了是一个伟大的双关语之外，本文还使用了一种叫做排序筛子(2013年由开发)的方法来攻击CSIDH假设。请注意，这一假设在所有后量子假设中都有区别，因为它直接产生了非交互式密钥交换，这是事实。

• 很容易从经典问题(离散日志变体)中得到，但是
• 从LWE这样的东西中获取信息要么需要非常大的参数，要么需要高级原语( FHE或函数加密)--无论是哪种情况，结果的方案都是低效的。

本文的主要观点是指出，排序筛不需要直接访问大量(\approx 2^{30})的量子内存，而是可以使用“量子可访问的经典内存”(最终估计是更多的\approx 2^{40})。我记得在twitter/ nist谷歌小组上也有一些争论(我猜丹·伯恩斯坦( debate )和克里斯( Chris )之间存在争议，但不太记得)。

粗略地说，我们可以用打破原语所需的一对(时间、内存)来描述经典的安全性。量子安全性则与四元组(经典时间、经典记忆、量子时间、量子记忆)有关.如何准确地从这样一个四元组中提取出一个单一的安全评估仍然是一个争论的问题，甚至两位后量子密码学的专家也可能有他们的分歧。