是否有一族密码散列函数可以用较小的深度量子电路来实现？

Question

某些数论密码散列函数，如x^2\bmod N，已知被量子计算机破坏。例如，可以使用Shor的算法将N分解到两个素数(p_1,p_2)的乘积中，并使用这些素数任意查找碰撞。找到一个满足西蒙的承诺版本的散列也是一个长期存在的问题；如果可以找到这样的散列，那么它也同样容易用量子计算机进行反演算。

其他常见的哈希函数(如SHA256 )的结构要小得多，而量子计算机可能只能通过格罗弗算法提供“适度”的多项式加速比。即便如此，对于一个量子电路的深度的估计，即使是一个调用Grover的预言的函数(比如SHA256 )，也有几万到几十万个门。在f(x)是n-bit字符串的SHA256输出的情况下，x；即使要实现SHA256，用量子计算机准备\frac{1}{\sqrt{2^n}}|x\rangle|f(x)\rangle也可能需要显着的纠错。我不确定细节，但我认为像CCNOT门或CSWAP门这样好的量子门很难实现s 256‘S扰码的本质。

这是我感兴趣的最后一点。我正在寻找一组很好的密码散列函数f on n位(量子位)，它们很可能是针对量子计算机的secure，仍然需要一个蛮力的Grover/生日式攻击才能找到冲突，但仍然需要<#>easy与量子计算机进行叠加，即有一个浅(Ish)深度的CCNOT/CSWAP/CNOT门的量子电路。

例如，我想看看用量子计算机来准备\frac{1}{\sqrt{2^n}}|x\rangle|f(x)\rangle，为一个足够好的加密函数f，它仍然是用一个小深度的量子电路设计的。是否有任何这样的散列函数被普遍使用，或者修改现有的散列函数是否简单？

Answer 1

我不确定我是否完全理解这个问题的前提。构建Simon承诺的函数相对简单，尽管这些函数在传统上是弱的，如散列函数。我们只需选择一个由\mathbf s生成的一维空空间的线性函数D1，并在\mathbf F_2^n上选择我们最喜欢的伪随机排列，比如\pi(x)，并定义我们的哈希函数为\pi\circ\ell(x)。

此外，与Shor算法中模块指数所需的电路相比，SHA256在量子计算机上的实现并不太繁重。李等人在高效SHA-256量子电路构造的t深度约简方法中引用的大约一万二千托福里深度确实是相当温和的。Grover的痛苦在于所需的迭代次数以及这些迭代高度不可并行的事实。

如果这仍然是令人不快的，你可以看看最近的NIST轻量级密码学竞赛决赛的功能。Lee等人最近在他们的论文面向物联网应用的GPU和量子计算机上轻量级哈希函数的高效实现中的工作发现，来自获胜的ASCON家族的哈希函数可以用35,136个量子位和2,487个T深度来实现。如果一个人准备过去的哈希函数批准标准化，同一篇文章指出，来自同一竞争对手的Xoodyak散列函数(据我所知，没有特别的弱点)可以用14,464个量子位和760个T深度来实现。