基于代码的密码系统上的信息集解码攻击所需的位操作数？

Question

这个问题可能与NIST后量子密码学标准相关，包括基于代码的密码系统，如McEliece、自行车和HQC。

本论文估计执行五月-迈勒-汤姆埃(MMT)信息集解码攻击所需的具体位操作数。它表明，这明显少于任何其他考虑的ISD变体，包括BJMM算法，该算法被广泛认为是对MMT的一种改进。(例如，对于经典的麦克利希的8192128参数集，本文给出了MMT的复杂度为2^{249.74}，而非2^{299.89}。)这个分析正确吗？

如果分析是正确的，这似乎不仅可能威胁到一些McEliece参数，而且威胁到其他基于代码的方案的一些参数。如果不是，准确数字的好来源是什么？

(本文声称MMT的2^{87.95}内存复杂性与BJMM的2^{79.97}相比，与2^{67.64}的Stern算法相比，请参见表5。这似乎不足以弥补内存成本与位操作之间任何看似合理的模型的差异。MMT对于其他参数集和方案来说也同样便宜。)

这个问题是交叉在NIST PQC论坛这里。

Answer 1

我无法从上述论文[1]中重现确切的位复杂度，作者没有提供源代码。我正在发布我对MMT和BJMM攻击这里的估计。

BJMM算法比MMT算法差的结论是错误的，因为MMT是BJMM的特例。简单地说，BJMM是MMT，对于错误向量没有1 = 0+0 \bmod 2 类型的表示。混淆来自于[1]的作者认为BJMM具有一定的搜索树的固定深度(即深度3，正如在最初的论文[2]中所做的那样)。然而，对于给定的稀疏机制，这可能不是最优的，因此，错误的结论是BJMM比MMT差。我在下面给出更多的细节。

MMT算法和BJMM算法的核心思想都是将权值p的误差向量D6分解为e = e_1 + e_2。MMT采用e_1, e_2 \in \{0,1\}^k中的每个权重p/2，从而给出了\binom{p}{p/2}将0-coordinates表示为e中的0+1或1+0的方法。BJMM采用e_1, e_2 \in \{0,1\}^k中的每个权重p/2 + \varepsilon，从而给出\binom{p}{p/2} \cdot \binom{k-p}{\varepsilon}表示(第二个倍数是0 = 1+1类型的表示数)。

结果表明，对于密集情况下的译码问题，即当e的权重为\Theta(n)阶时，BJMM算法在重复该过程时速度更快，它还以一种模糊的方式表示e_1、e_2。因此，最终得到算法的搜索树结构，其中树的最优深度是要优化的参数。从[2]到密集的政权，它恰好是3。

对于经典的McEliece参数来说，做深度-2是最优的.从直觉上看，误差越小，最优树就越浅，因为一个人不能把一个小重量分成两半太多次。

特别是，我得到了以下比特安全性(和内存复杂性)与我的估计。这些可能被低估，因为poly(n)因素被忽略了。您可以通过运行脚本来再现它们。

N=3488k= 2720 w= 64 {‘运行时’：133.610045757394，'mem'：61.4108701659799}

N= 4608 k= 3360 w= 96 {‘运行时’：174.170500202444，'mem'：76.7183814578096}

N=6960k=5413w=119个{‘运行时’：244.706198594600，'mem'：123.451330788046}

N=8192k=6528w=128个{‘运行时’：277.268692835670，'mem'：140.825234863797}

BJMM深度2略优于MMT和BJMM深度3。

N=3488k= 2720 w= 64 {‘运行时’：127.121142192395，'mem'：65.4912086419963，'eps'：4}

N= 4608 k= 3360 w= 96 {‘运行时’：164.510671206084，'mem'：88.1961572319148，'eps'：6}

N=6960k=5413w=119个{‘运行时’：231.228308300186，'mem'：118.193072674123，'eps'：8}

N=8192k=6528w=128个{‘运行时’：262.367185095806，'mem'：134.928413147468，'eps'：8}

N=3488k= 2720 w= 64 {‘运行时’：132.929177320070，'mem'：30.8744409777593，'eps'：}

N= 4608 k= 3360 w= 96 {‘运行时’：167.443669507488，'mem'：45.4015594758618，'eps'：}

N=6960k=5413w=119个{‘运行时’：236.346159271338，'mem'：67.5649403829532，'eps'：}

N=8192k=6528w=128个{‘运行时’：269.431207750362，'mem'：70.1193015124538，'eps'：}

1

2