Количество битовых операций, необходимых для атак декодирования набора данных на криптосистемы на основе кода?

Этот вопрос потенциально имеет отношение к стандартам постквантовой криптографии NIST, включая криптосистемы на основе кода, такие как McEliece, BIKE и HQC.

Эта бумага оценивает конкретное количество битовых операций, необходимых для выполнения атаки декодирования информационного набора (ISD) May-Meurer-Thomae (MMT). Это показывает, что это значительно меньше, чем для любого из других рассмотренных вариантов ISD, включая алгоритм BJMM, который широко считается улучшением по сравнению с MMT. (Например, для классического набора параметров МакЭлиса 8192128 в документе сложность MMT указана как $2^{249.74}$ в отличие от $2^{299.89}$ для BJMM.) Верен ли этот анализ?

Если анализ верен, кажется, что это может угрожать не только некоторым параметрам МакЭлиса, но и некоторым параметрам других схем на основе кода. Если нет, то какой хороший источник точных цифр?

(В газете утверждается $2^{87.95}$ сложность памяти для MMT по сравнению с $2^{79.97}$ для BJMM и $2^{67.64}$ для алгоритма Стерна см. Таблицу 5. Это не кажется достаточно большим, чтобы компенсировать несоответствие любой правдоподобной модели стоимости памяти по сравнению с битовыми операциями. Аналогично заявлено, что ММТ дешевле для других наборов параметров и схем.)

Этот вопрос опубликован на форуме NIST PQC. здесь.

Я не смог воспроизвести точные битовые сложности из упомянутой статьи. [1], авторы не предоставили исходный код. Я публикую свои оценки атак MMT и BJMM. здесь.

Вывод о том, что алгоритм BJMM хуже, чем MMT, неверен, поскольку MMT является частным случаем BJMM. Вкратце, BJMM — это MMT без представления типа $1 = 0+0 \bmod 2 $ для вектора ошибки. Путаница возникает из-за того, что авторы [1] рассмотрим BJMM с некоторой фиксированной глубиной дерева поиска (а именно глубиной 3, как это сделано в исходной статье [2]. Однако это может быть неоптимальным для данного режима разреженности, следовательно, неверный вывод, что BJMM хуже, чем MMT. Я даю более подробную информацию ниже.

В основе алгоритмов MMT и BJMM лежит идея двусмысленно расщепление вектора ошибки $e \in \{0,1\}^k$ веса $р$ как $е = е_1 + е_2$. ММТ занимает $e_1, e_2 \in \{0,1\}^k$ каждый по весу $п/2$, тем самым давая $\binom{p}{p/2}$ способы представления $0$-координаты как $0+1$ или же $1+0$ в $е$. BJMM принимает $e_1, e_2 \in \{0,1\}^k$ каждый по весу $p/2 + \varepsilon$, тем самым давая $\binom{p}{p/2} \cdot \binom{kp}{\varepsilon}$ представлений (второе кратное число представлений типа $0 = 1+1$).

Оказывается, для задачи декодирования в плотном режиме, т.е. когда вес $е$ в порядке $\тета(п)$, алгоритм BJMM работает быстрее, если мы повторяем процесс, также представляя $e_1$, $e_2$ неоднозначным образом. Таким образом, получается структура алгоритма в виде дерева поиска, где оптимальная глубина дерева является оптимизируемым параметром. От [2] для плотного режима получается 3.

Для параметров Классического МакЭлиса получается, что оптимально делать depth-2. Интуитивно понятно, что чем реже ошибка, тем мельче будет оптимальное дерево, потому что нельзя разделить небольшой вес пополам слишком много раз.

В частности, я получаю следующие битовые гарантии (и сложности с памятью) с помощью моего оценщика. Скорее всего, это заниженные оценки, поскольку $поли(п)$ факторы игнорируются. Вы можете воспроизвести их, запустив скрипт.

-------------------- ММТ --------------------

n = 3488 k = 2720 w = 64 {'время выполнения': 133.610045757394, 'память': 61.4108701659799}

n = 4608 k = 3360 w = 96 {'время выполнения': 174.170500202444, 'память': 76.7183814578096}

n = 6960 k = 5413 w = 119 {'время выполнения': 244,706198594600, 'память': 123,451330788046}

n = 8192 k = 6528 w = 128 {'время выполнения': 277,268692835670, 'память': 140,825234863797}

Глубина 2 BJMM немного превосходит как глубину MMT, так и глубину 3 BJMM.

----------------BJMM глубина 2 ----------------

n = 3488 k = 2720 w = 64 {'время выполнения': 127.121142192395, 'mem': 65.4912086419963, 'eps': 4}

n = 4608 k = 3360 w = 96 {'runtime': 164.510671206084, 'mem': 88.1961572319148, 'eps': 6}

n = 6960 k = 5413 w = 119 {'runtime': 231.228308300186, 'mem': 118.193072674123, 'eps': 8}

n = 8192 k = 6528 w = 128 {'время выполнения': 262.367185095806, 'mem': 134.928413147468, 'eps': 8}

----------------BJMM глубина 3 ----------------

n = 3488 k = 2720 w = 64 {'время выполнения': 132.929177320070, 'mem': 30.8744409777593, 'eps': [2, 0]}

n = 4608 k = 3360 w = 96 {'runtime': 167.443669507488, 'mem': 45.4015594758618, 'eps': [6, 0]}

n = 6960 k = 5413 w = 119 {'runtime': 236.346159271338, 'mem': 67.5649403829532, 'eps': [6, 0]}

n = 8192 k = 6528 w = 128 {'время выполнения': 269.431207750362, 'mem': 70.1193015124538, 'eps': [6, 0]}

[1] https://www.mdpi.com/1999-4893/12/10/209/pdf

[2] https://eprint.iacr.org/2012/026.pdf