基于格的变分量子算法密码(Kyber1024仅为25k.Qbit)？

Question

我目前正在撰写一篇关于Kyber和其他基于格的方法的研讨会论文。我对基于点阵的方法非常兴奋，所以我现在也搜索量子算法来解决这些方法。

在这个过程中，我遇到了一篇论文：https://www.mdpi.com/1099-4300/24/10/1428/pdf，叫做“使用变分量子算法来解决LWE问题”。作者声明: Lv et.阿尔。在那里，作者声称已经开发了一种算法，只需25.482，QBits就能破解Kyber1024。这比RSA加密要少。

我不是量子计算方面的专家。我所能确定的是，没有类似的论文表明量子算法有如此迅速的进步。

Answer 1

虽然我不是量子计算专家，但RSA/DLOG的典型估计为~2k (逻辑) qbits，因此取决于您是否意味着物理/逻辑您的数字可能为off。不过，他们声称的减少到BDD或uSVP的技术是该领域的标准技术。他们似乎也没有引用关于结构化晶格问题的量子算法的最新进展，即Cramer，Ducas和Wesolowski于2017年首次出版的这项工作。该工作仅限于模块秩1的格问题，而需要模秩\geq 2来打破(R/M)LWE，而Kyber是基于MLWE的(可能需要模块秩3~5来打破它？( idk)

总的来说，我怀疑这篇论文与我上面所链接的工作相比尤其有用，如果你想了解关于结构格问题的量子算法的最新进展。如果它声称对Kyber进行了有效的量子攻击(我没有仔细阅读)，它将需要两个同时的突破。

1. CDW逼近因子的约简(从次指数降为可能的多项式)
2. CDW从模级1到模秩\geq 2的推广。

我个人并不认为这篇论文会包含这两个问题的解决方案(特别是因为它甚至没有引用CDW!)，因为它似乎是在某个特定的量子计算框架中重新分析标准经典算法，并且似乎主要关注表示各种缩减格基的空间复杂性。具体而言，第4.2节界限

qbits = \sum_{i = 1}^{m'} (\lfloor \log_2 d_i\rfloor + 1)

其中，d_i看起来是m'维矩阵B的i第四系数的\ell_\infty界(这不是一个错误--由于某种原因，他们用一个单维参数将矩阵B参数化，这是不标准的)。在古典意义上，这只是对应于一个空间复杂度，它必须用(经典)位来表示B，正如波乔在注释中所暗示的那样，也就是说，与限制时间复杂性本身没有什么真正的关系。

Answer 2

本文的思想(以及之前关于"NISQ"-y量子格算法的其他工作)是将一个硬格问题转化为一个二进制优化问题。为了说明这对于SVP是如何工作的，让B是n-dimensional格L的基向量的矩阵。假设我们想要找到最短向量v。最短等于是最小的v\in L (最小化v^Tv )。我们可以将v=Bx进一步分解为一些整数x，因此我们希望找到最小化x^TB^TBx的x\in \mathbb{Z}^n。更重要的是，我们可以将x=(x_1,\dots, x_n)的每个组件分解为二进制，就像某些m的x_i = x_{i0}+x_{i1}2^1 + x_{i2}2^2 + \dots + x_{im}2^m，其中每个x_{ij}\in \{0,1\}。因此，我们可以重写

v^Tv = x^TB^TBx = \sum_{ijk\ell st} x_{ij}2^jB_{si}B_{tk}x_{k\ell}s^\ell = \sum_{ij k\ell} x_{ij}x_{k\ell} C_{ijk\ell}

在哪里C_{ijk\ell}:= \sum_{st} 2^{j+\ell}B_{si}B_{tK}。

最小化v^Tv对于v\in\ell就相当于在\{x_{ij}\}的所有可能的二进制选择上最小化上面的表达式。

实际上，二进制优化问题也是非常困难的，所以这在古典意义上并没有多大帮助(我们基本上抛弃了所有的几何格结构！)但是这里有用的事实是，在量子计算机上评估这个成本函数实际上是相当简单的。

一旦您可以在量子计算机上评估成本函数，您就可以尝试任意数量的量子优化技术(如链接论文中的asQAOA或变分量子特征求解器)。这些细节并不重要；相关的事实是，在查询方面(因此，大致相当于运行时)，它们的性能不能优于Grover的算法。综上所述，我们有nm二进制变量，所以搜索空间是2^{nm}，这意味着O(2^{nm/2})的运行时。这里 --他们仔细分析并限定了m= O(\log n) (这意味着对于最短向量，系数不需要大于O(n)，如果对基进行预处理的话)。因此，运行时充其量是2^{O(n\log n)}：渐进地与量子枚举相同，比量子筛选更糟糕(尽管没有内存需求)。

那么，如果变分/近似算法不能提供一个渐进改进以前的算法，我们为什么要关心呢？因为这些算法在进行经典测量之前只需要进行较短的量子计算。因此，容错开销可以大大降低，因此算法的量子比特要求也要低得多。因此，构建一个可以运行NISQ量子算法的庞大的量子计算机阵列可能更容易，而不是完全容错的量子枚举或晶格筛选。

更准确地说，你说的是“只要25.482，QBits破解Kyber1024，这比RSA加密要少。”这是不完全正确的。RSA加密只需要几千个逻辑量子位，这是一种高保真的量子比特，具有纠错开销。今天最好的估计是，这将需要几百万个物理量子位元(量子计算机的实际组件)。相反，我们可以直接在物理量子位上运行这些NISQ点阵解算器，或者使用较少的误差校正，使它们使用的物理量子位数少于100万。

但总的来说我很怀疑。对于这些算法，我们没有运行时保证，噪声可能是一个大问题，我们只是希望经典的优化器能够做得足够好，找到正确的解决方案。这是有趣和值得考虑的量子密码分析，但我不认为它对晶格安全估计有任何影响。