是否因为没有人想出量子算法来解决哈希函数而被认为是安全的？还是可以解决任何众所周知的难题？请说明减少量。
#1 楼
断言散列函数“不是基于任何困难的问题”有点可疑：反转标准散列函数或查找冲突本身是一个非常困难的问题。减少是将密码分析工作集中在较少数量的假设上。在RSA假设下RSA-OAEP是CCA安全的事实并不能证明它是安全的，仅仅是表明研究其安全性足以研究RSA问题的安全性。由于可以将许多其他密码原语简化为RSA假设，因此节省了相当多的密码分析工作。
现在，此类归约通常依赖于数学假设的某些代数性质，利用组结构，自可随机化性， 等等。这些属性在非对称密码术中很常见，因为这种附加结构在它涉及的原语中已经是必需的。但是另一方面，在对称加密中，通常避免这种结构。这样做的结果是，您需要较小的基元（就位大小而言）和较少的计算开销的操作即可达到（推测的）给定的安全级别，但是您却失去了将许多对称基元简化为少量假设的可能性。
但是，对于部署最广泛的分组密码和哈希函数，投入在研究其安全性上的密码分析工作很容易与投资在“一般假设”上的工作（例如离散对数或因式分解）相匹配，因为它们在实践中被广泛使用。 。因此，没有理由相信，由于缺乏减少，反转SHA256应该比破坏RSA更容易。实际上，由于RSA具有如此多的结构，与破坏RSA的攻击相比，使SHA256反转的攻击使大多数专家可能会更加惊讶。因此，ElGamal和这类人享受“减少”的事实绝对不能使它们更加安全-它只能在不同图元的硬度之间建立联系。我们不能肯定地说什么我们可以解决或不能解决这些问题-就我们所知，可能是$ P = NP $，并且可以使用经典计算机来破坏所有密码。但是，根据我们目前的知识，我们可以直观地了解它们为传统计算机提供的其他功能。而且，这种直觉可以总结为：它似乎具有一些额外的功能，但仍不足以在合理的时间内解决非常困难的问题（例如NP完全问题）。
一些问题具有特殊结构（因式分解，离散对数）的问题通常属于量子计算机将提供非常强的加速的问题类别，因为量子计算机可以简化为寻找某些函数的周期的任务，这似乎很难做到。经典计算机，但没有量子计算机。对于非结构化问题，量子计算机似乎通过使用Grover算法提供了一些非平凡的二次加速。但是二次加速不会带来攻击，它只是表明密钥的大小应增加两倍，以补偿这种加速。
散列函数是相当非结构化的，因此我们目前看不到如何在经典计算机上获得超过二次加速的攻击。因此，我们目前推测，具有256位经典安全性的哈希函数仍将具有128位量子安全性。对于抗碰撞性，量子计算机提供了甚至更令人印象深刻的加速：生日攻击给出了$ O（\ sqrt {n}）$攻击，而量子版本似乎仅使这种攻击达到$ O（n ^ {1/3} ）$。
评论
$ \ begingroup $
实际上，碰撞发现的量子加速是一个广泛的错误神话。
$ \ endgroup $
– SEJPM♦
17 Mar 3 '17 at 14:23
$ \ begingroup $
我不了解这篇文章，谢谢分享：）如果我理解正确的话，那么关键是，使用量子计算机不会像使用大规模并行经典计算机进行冲突查找那样具有成本效益。我并不是真正在研究速度或成本，而是在古典世界和量子世界中研究问题的理论复杂性。无论如何，它加强了我的观点，并且学习一些东西总是很高兴的:)
$ \ endgroup $
– Geoffroy Couteau
17 Mar 3 '17 at 14:37
$ \ begingroup $
实际上，迭代哈希函数的安全属性通常可以简化为所用压缩函数的安全属性。 （或者在使用海绵功能时，要使用所使用排列的属性。）
$ \ endgroup $
–PaŭloEbermann
17 Mar 4 '17 at 10:54
$ \ begingroup $
当然，它确实是对称密码学中非常活跃的研究领域-证明了不可区分性，对随机预言的不可区分性或建立在“较小”基元之上的对称基元的抗碰撞性。但是我认为这不是OP的问题所在，而是关注基本固定大小输入基元的情况。
$ \ endgroup $
– Geoffroy Couteau
17年4月4日在11:17
$ \ begingroup $
@SEJPM我不理解这篇文章，如果他说RSA不受量子计算的威胁，Rivest先生在与数字爱好者的访谈中说的是什么？
$ \ endgroup $
–丹尼尔
17年5月15日在9:58
#2 楼
常见的哈希函数基于组合问题。粗略地说，（未来的）量子计算机据称能够以未知的$ k $费力（最坏的情况）$ O（2 ^ {k / 2}）$解决组合问题，而$ O（2 ^ k） $用于经典计算机。因此，量子计算机并不意味着所有哈希的安全性注定要失败。更糟糕的是，这意味着将某些安全参数加倍。我对各种计算机信任SHA-512，而不是我对传统计算机信任SHA-256。
#3 楼
哈希只是循环中运行的对称密码，也使用来自同一输入的密钥对输入进行加密，并且经常随处散布额外的内容（例如SHA-2中的质数）。我不是专家，但是任何哈希是否具有量子抗性都归结为
是否完全取决于为哈希选择的对称密码。
SHA-2密码是秘密的（分类的），因此只有NSA（发明SHA的人）才知道它是否具有量子抗性。
评论
$ \ begingroup $
嗯，如果整个算法都知道，那么密码怎么能保密？哈希为什么要依赖对称密码？是的，有一些哈希并且对称密码和哈希有很多共同点，但这是否意味着哈希必须依赖于基础块密码？
$ \ endgroup $
–马腾·博德威斯♦
17年12月15日在16:07
$ \ begingroup $
马尔滕，你好。请参阅Merkle–Damgård，以了解如何构建所有现代哈希机制。一旦弄清了它们如何以及为什么使用对称密码，就可以研究一下SHA中使用的对称密码，或者如果您擅长反向工程，也许您可以查看SHA代码并找出其中的哪一个。是吗（尽管我怀疑-这是NSA设计的-几乎可以肯定他们使用的实际密码是保密的）
$ \ endgroup $
–安农·科沃德（Anon Coward）
17年12月16日在22:48
$ \ begingroup $
Merkle–Damgård并不是生成现代哈希的唯一方法；例如Keccak / SHA-3不是Merkle–Damgård哈希。
$ \ endgroup $
–马腾·博德威斯♦
17年12月16日在23:04
$ \ begingroup $
这太错了，我什至不知道从哪里开始。因此，我将限制自己传递友好的建议以阅读SHA-2及其使用的Merkle-Damgård构造。相关论文可以广泛地向公众公开-与您的主张相反-绝不是秘密的或以任何方式分类的。在进行研究时，您很快就会注意到，密码（又名加密算法）与Merkle-Damgård构造之间存在巨大差异。 TL; DR：我完全同意@MaartenBodewes的评论。
$ \ endgroup $
– e-sushi
18年5月20日19:00
$ \ begingroup $
@AnonCoward由于该密码仅在SHA-2内部使用，因此没有名称。但是，提取它时，会有一个称为SHACAL-2的密码，该密码是公共的。使用的密码可能基于已分类的密码，但是SHA-2中的分组密码是公开的。
$ \ endgroup $
–森林
18年7月15日在3:23
评论
哈希函数具有极少的数学结构（与非对称密码相反），因此通常假定哈希函数没有专门的量子算法（与其他对称算法相同）。请记住，哈希函数是根本不同的野兽。将书放在保险箱中与将每页的第一个字母作为您拥有该书的证据进行复制然后进行刻录相比。第一种方法可以将书取回，第二种方法则不管您拥有多少资源。有损算法很难逆转，而不仅仅是数学上的困难，逆转它的实际数据已永久消失。
我认为反相的难度与损耗无关，因为反相器只需要找到任何有效的原像即可。丢失只会添加更多有效的原像，真正重要的是缺少（易于识别/可用）的结构。
我不是专家，但是在此站点上有一个非常好的答案，它讨论了由于扇出而难以解决有效输入的问题（这有助于将哈希显示为一系列逻辑门）。有了这些，以及布尔可满足性问题，我想说它们是基于困难的问题？
您可以链接到此答案吗？关于您的发言，重要的不是基于难题，而是将多项式时间缩减为我们未能解决的问题。 Merkle-Hellman密码系统基于NP困难问题（背包问题），但是仍然被破解，并且其不安全性对其所基于问题的NP困难性没有任何影响。