Parano1d соответствует NIST PQC Category 1

Аннотация

Штатный профиль доказательств Parano1d анализируется в модели квантового случайного оракула относительно ресурсного эталона NIST Category 1 для полного перебора ключей AES-128. Доказательство начинается с точных отношений кошелька и HistoryStep, объединяет все представленные корневые объекты в одно событие принятия недопустимого состояния, переводит типизированные параллельные запросы к оракулу в число логических квантовых вентилей и глубину схемы и учитывает поправки конечного размера для извлечения и коллизий. На ресурсной границе NIST полная верхняя оценка вероятности успеха в идеальной модели равна 0.053364140323608411. Нижняя граница произведения числа вентилей на глубину при вероятности успеха одна вторая равна 173.273866314232 бит, что на 3.273866314232 бит выше эталона 2^170.

NIST Category 1 сравнивает ресурсы, необходимые для атаки, с полным перебором ключей AES-128. Модель учитывает число логических квантовых вентилей, ограничивает глубину схемы и определяет, может ли атака достичь заданной вероятности успеха в пределах этого бюджета.

Для Parano1d событием успеха противника служит принятие итогового состояния вне множества состояний, получаемых допустимым выполнением от генезиса. Штатный профиль доказательств достигает ресурсного уровня NIST Post-Quantum Cryptography Category 1. На полной ресурсной границе NIST верхняя оценка в идеальной модели квантового случайного оракула равна $0.053364140323608411$ . Нижняя граница произведения числа вентилей на глубину схемы при вероятности успеха одна вторая составляет $2^{173.273866314232}$ . Это на $3.273866314232$ бит выше эталона NIST $2^{170}$ .

Утверждение о стойкости	Штатный результат
Цель противника	Принятие недопустимого итогового состояния
Эталонная задача	Полный перебор ключей AES-128
Эталон NIST для произведения числа вентилей на глубину	$GD=2^{170}$
Проверенные значения NIST MAXDEPTH	$2^{40}$ , $2^{64}$ и $2^{96}$
Нижняя граница произведения при вероятности успеха одна вторая	$2^{173.273866314232}$
Запас относительно эталона NIST	3.273866314232 бит
Полная верхняя оценка вероятности успеха в идеальной модели	$0.053364140323608411$
Достаточное условие для фиксированной перестановки Poseidon2b	$\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}} \lt 0.446635859676391589$
Категория NIST Post-Quantum Cryptography	Category 1

Игра безопасности

Каждый принятый блок Parano1d несёт рекурсивное доказательство HistoryStep. Оно подтверждает выполнение отношения корректности блока, точный переход от аутентифицированного родительского состояния к дочернему и корректность предыдущего доказательства HistoryStep. Доказательства авторизации кошельков и используемые блоком вспомогательные отношения sidecar входят в то же утверждение.

Публичным экземпляром игры служит конечное состояние HistoryStep. Единый квантовый противник, сохраняющий состояние между запросами, выигрывает, если штатный верификатор принимает состояние вне множества, достижимого допустимым выполнением от генезиса. Ошибка в авторизации кошелька, отношении корректности блока, родительской связи, переходе состояния, рекурсивной проверке или заявленной цепочке доказательств приводит к победе в этой же игре.

Все обращения к оракулу, использованные для построения итогового доказательства и всех предшествующих доказательств противника, входят в единый ресурсный бюджет. После измерения базы данных сжатого оракула извлечение свидетелей и обход графа доказательств выполняются детерминированно и больше не обращаются к оракулу. Теорема охватывает всё принятое состояние, включая каждое открытие FRI и каждую рекурсивную зависимость.

Последовательные запросы и ресурсы Category 1

Штатные параметры допускают два дополняющих друг друга способа оценки. Последовательная теорема для идеальной QROM даёт границу $64.707407428576$ бит по бюджету запросов. Она считает каждое обращение к оракулу одним запросом и охватывает бюджеты, для которых явная верхняя оценка остаётся ниже одной второй.

Теорема Category 1 добавляет обратимую схему, необходимую для ответа на каждый запрос. Когерентный запрос к штатному транскрипту Fiat–Shamir на Poseidon2b требует большого числа умножений в двоичном поле. Параллелизм уменьшает глубину схемы, но не исключает суммарное число вентилей из учёта ресурсов. Расчёт использует обе величины и непосредственно выводит нижнюю границу для их произведения.

Штатные параметры

Расчёт привязан к ревизии Parano1d afdce21b6125ae0487c71a9093ab089cb8e88d5a. Отдельный снимок штатных параметров содержит все исходные параметры анализа стойкости, а карта происхождения параметров связывает каждое значение с его определением в Rust.

Параметр	Штатное значение
Число запросов кошелька	65
Число запросов History	133
Размер пространства алгебраических вызовов	$2^{255}$
Разрядность хеша	256 бит
Кодовая скорость History	1/4
Начальное кодовое слово History	$2^{20}$ или $2^{21}$
Группы совместных отношений sidecar	9
Poseidon2b	$t=4$ , скорость 2, $x^7$ , 8 полных раундов, 58 частичных раундов

Две длины начального кодового слова соответствуют двум штатным размерам трассы History. B64 используется до 64 пользовательских страниц транзакций включительно, B255 используется от 65 до 255 страниц. Оба класса доказывают одно отношение HistoryStep с одинаковой скоростью кода, числом запросов, распределением проверочных вызовов и локальной теоремой. Различается только длина трассы.

Алгебраические вызовы принадлежат аффинному подмножеству GF(2²⁵⁶) со следом 1, содержащему ровно $2^{255}$ элементов. Разрядность 256-битного хеша является отдельным параметром. Для алгебраических исключительных множеств используется знаменатель $2^{255}$ , а для глобальных коллизий связывания используется $2^{256}$ .

Локальная теорема корректности

Сначала в анализе каждый вызов Fiat–Shamir заменяется соответствующим случайным вызовом проверяющей стороны, а аутентифицированные массивы рассматриваются как идеальные оракулы. Так получается IOP с публичными случайными монетами, для которого доказывается обобщённая пораундовая ошибка знания (RBR). Локальная теорема допускает более широкое множество принимаемых транскриптов, поскольку условие proof of work на значение nonce удалено. Поэтому сложность майнинга не учитывается как дополнительный запас корректности.

Авторизация кошелька

Для кошелька учитываются член, соответствующий пропуску изменённой позиции всеми запросами, и объединение неблагоприятных алгебраических вызовов:

\kappa_{W,q}=\left(\frac{15}{64}\right)^{65}, \qquad \kappa_{W,f}=\frac{29\,163\,918\,888}{2^{255}}.

Эти события относятся к разным ходам проверяющей стороны. Обобщённая пораундовая ошибка знания (RBR) равна наибольшей условной вероятности уклонения:

\kappa_W=\max\{\kappa_{W,q},\kappa_{W,f}\}.

HistoryStep

Для целого параметра кратности Джонсона $m\ge3$ определим

h=m+\frac12, \qquad \gamma=\frac{m-1}{2m}, \qquad s_N=\frac{N-4}{2N}.

Для слоя кода Рида–Соломона длины $N$ и скорости 1/4 конечная оценка близости и строгая верхняя граница размера начального списка равны

A_N(m)=\left\lfloor N\frac{2h^5+3h\gamma s_N^2}{3s_N^3}+\frac{h}{s_N} \right\rfloor,

L_N(m)=\left\lceil\frac{h}{s_N}\right\rceil-1, \qquad L_{\max}(m)=\max\{L_{2^{20}}(m),L_{2^{21}}(m)\}.

Теорема о списочной корреляции для кодов Рида–Соломона даёт $A_N(m)$ . Анализ BaseFold переносит эту оценку на штатную последовательность свёрток. Для 133 независимых позиций запросов остаточный член равен

E_q(m)=\left(\frac{m+1}{2m}\right)^{133}.

Начальные 32 перемеженные строки упаковываются в одно кодовое слово Рида–Соломона над полем расширения и используют общий конечный начальный список. Каждая свёртка вне исключительного множества связывает кандидата на позднем этапе с коррелированными кандидатами-предшественниками из того же списка. Последующие алгебраические тождества берут объединение по всему списку, поэтому переключение кандидатов остаётся внутри границы.

Наибольшее обычное алгебраическое тождество имеет 127 корней на кандидата. Совместное sidecar-тождество для девяти групп имеет 36 корней. Объединение уклонения от запросов, всех штатных слоёв свёртки и переключения кандидатов даёт

\begin{aligned} \kappa_H(m)=\max\{&E_q(m), \max_N A_N(m)/2^{255},\\ &127L_{\max}(m)/2^{255}, 36L_{\max}(m)/2^{255}\}. \end{aligned}

Максимум оценки близости берётся по $N\in\{2^8,\ldots,2^{20}\}\cup\{2^9,\ldots,2^{21}\}$ и охватывает каждый слой свёртки обоих штатных размеров трассы.

Алгоритм извлечения без перемотки выполняет списочное декодирование упакованного слова, восстанавливает 32 строки основного поля, обращает аддитивное NTT-преобразование и оставляет кандидатов, удовлетворяющих точному отношению History. Обратная индукция по последовательности ходов проверяющей стороны показывает, что принимаемый транскрипт без свидетеля должен попасть в одно из четырёх событий в $\kappa_H(m)$ . Эта локальная теорема извлечения знания используется и в последовательном анализе, и в анализе с учётом ресурсов.

Для последовательной теоремы точный оптимум равен $m=861824$ . Для Category 1 точный оптимум с учётом ресурсов равен $m=318983$ , поскольку один ответ на запрос History требует двенадцати последовательных перестановок Poseidon2b.

От локальных доказательств к одному событию принятия недопустимого состояния

Типизированные пространства имён оракулов, разделённые по утверждениям, объединяют все семейства транскриптов и адаптивно выбранные утверждения в одно событие. После измерения единой базы данных сжатого оракула $D$ событие $\mathsf{BadAll}(D)$ означает существование представленного и принятого корневого объекта кошелька или History, для которого детерминированное извлечение завершается неудачей.

Остаются два граничных события. Необходимый дочерний объект может отсутствовать в базе данных, либо коллизия, неоднозначное кодирование или смешение доменов может изменить типизированный семантический граф. Поэтому

\mathsf{BadState} \subseteq \mathsf{BadAll}\cup\mathsf{MissRep}\cup\mathsf{BadTypedBind}.

В замкнутом типизированном идеальном компиляторе канонические вложенные объекты представлены в той же базе данных, поэтому событие $\mathsf{MissRep}$ невозможно. Связывание транскриптов и обязательств учитывают два приведённых ниже слагаемых: поправка за конечный размер и вероятность коллизии. При замене идеального интерфейса фиксированной Poseidon2b в самом конце добавляется один член отклонения штатной конструкции.

После измерения база данных становится классической. Детерминированный обход начинается с принятого конечного состояния, проверяет каждое локальное отношение, переходит к единственному родителю History меньшей высоты и добавляет необходимые доказательства авторизации кошельков и проверки вспомогательных отношений sidecar. Ранг уменьшается на каждом рекурсивном ребре, поэтому обход завершается на генезисе. Допустимые извлечённые свидетели затем в обратном топологическом порядке влекут точные переходы состояния, определённые протоколом.

Конструкция для всех корней сводит рекурсию к одному вероятностному событию. Высота цепочки влияет на детерминированную работу извлечения, а больший граф доказательств требует от противника больше ресурсов. Все представленные корни остаются внутри одного неблагоприятного события и одного общего бюджета.

Контрольная последовательная оценка в QROM

Положим

\kappa_*=\max\{\kappa_W,\kappa_H(861824)\}.

Специализация аргумента переноса через сжатый оракул из работы Chiesa, Manohar и Spooner вместе с адаптивной композицией с разделением по утверждениям из FRACTAL даёт полную последовательную границу в идеальной QROM:

\varepsilon_{\mathrm{ideal}}(T)=\min\left\{1, 6T^2\left(\kappa_*+\frac{2T+1}{2^{255}}\right) +\frac{6T^3}{2^{256}} \right\}.

Точный целочисленный поиск находит последнее $T$ , для которого выражение меньше одной второй:

Последовательная граница	Точное значение
Наибольший сертифицированный бюджет запросов	30 121 082 641 781 720 121
Первый бюджет за доказанной границей	30 121 082 641 781 720 122
Двоичный логарифм для представления результата	64.707407428576 бит
Верхняя оценка при $T=2^{64}$	$0.187528937938435742$

Первый бюджет за доказанной границей точно отмечает точку, в которой эта верхняя оценка достигает одной второй. В расчёте Category 1 запросы единичной стоимости заменяются логическими ресурсами, необходимыми для реализации когерентных ответов.

Ресурсный эталон NIST Category 1

Раздел 4.A.5 NIST определяет Category 1 через атаки, требующие ресурсов, сопоставимых с полным перебором ключей AES-128 или превышающих их. При учёте ограничения на глубину схемы NIST задаёт для AES-128 следующий эталон:

G=\frac{2^{170}}{D}, \qquad GD=2^{170},

где $G$ обозначает число логических квантовых вентилей, а $D$ обозначает максимальную глубину схемы. NIST указывает $D=2^{40}$ , $2^{64}$ и $2^{96}$ . Сертификат проверяет все три значения.

Ресурсы типизированного параллельного QROM

Для каждого типизированного неблагоприятного события ответа $j$ обозначим через $\kappa_j$ его локальную плотность, через $g_j$ число логических квантовых вентилей одного когерентного ответа и через $d_j$ его логическую глубину. Оценка перехода для параллельного сжатого оракула из работы Chung, Fehr, Huang и Liao после специализации на событии для всех корней даёт

\Pr[\mathsf{BadState}]_{\mathrm{main}} \le 10GD\max_j\frac{\kappa_j}{g_jd_j}.

Эта ресурсная оценка также охватывает параллельный раунд с несколькими типами ответов. Если $k_{s,j}$ обозначает число запросов типа $j$ в раунде $s$ , а $\delta_s=\max\{d_j:k_{s,j}\gt0\}$ , то

\sum_{s,j}g_jk_{s,j}\le G, \qquad \sum_s\delta_s\le D.

Взвешенное неравенство Коши–Буняковского для амплитуды перехода сжатого оракула даёт

\begin{aligned} \Pr[\mathsf{BadState}]_{\mathrm{main}} &\le10\left(\sum_s\delta_s\right) \left(\sum_s\frac{\sum_j\kappa_jk_{s,j}}{\delta_s}\right)\\ &\le10D\sum_{s,j}\frac{\kappa_jk_{s,j}}{d_j}\\ &\le10GD\max_j\frac{\kappa_j}{g_jd_j}. \end{aligned}

Адаптивно выбранные утверждения и рекурсивные корни входят в общее событие $\mathsf{BadAll}$ и учитываются в его едином ресурсном бюджете.

Стоимость когерентного ответа Poseidon2b

В ресурсном расчёте используется обратимая схема умножителя Карацубы над GF(2¹²⁸) со следующими логическими затратами:

Ресурс	Число
CNOT	29 340
Однокубитные вентили Клиффорда	4 374
T	15 309
Всего логических квантовых вентилей	49 023
Логическая глубина	43

Штатная перестановка Poseidon2b содержит

4\cdot8+58=90

S-блоков. Для $x^7$ нужны два последовательных умножения в поле, а когерентное вычисление вместе с обратным вычислением использует четыре. S-блоки полного раунда исполняются параллельно. Поэтому один когерентный ответ перестановки имеет

g_0=90\cdot4\cdot49\,023=17\,648\,280,

d_0=(8+58)\cdot4\cdot43=11\,352,

g_0d_0=200\,343\,274\,560.

Для ответа на запрос кошелька дуплекс со скоростью два должен выдать семь 128-битных элементов. Для этого выполняются четыре последовательные перестановки. Ответ на запрос History требует двенадцати перестановок, а ответ из одного элемента требует одной.

Вывод Category 1 включает явную предпосылку, что получение соответствующего когерентного ответа штатного оракула требует от противника как минимум указанного числа логических вентилей и указанной глубины. Схема не учитывает дополнительные затраты на маршрутизацию, линейные и управляющие операции, поэтому оценка консервативна для этой конструкции. Теорема формулирует минимальную стоимость как предпосылку. Универсальная нижняя граница для всех обратимых схем потребовала бы отдельного результата.

Расчёт Category 1

Ресурсная теорема одновременно рассматривает события запросов и алгебраических вызовов кошелька, а также события запросов, близости, переключения кандидатов и совместного sidecar-тождества для History. При точном оптимуме с учётом ресурсов $m=318983$ наибольшее отношение $\kappa_j/(g_jd_j)$ даёт событие запроса кошелька.

Приравнивая главный член к вероятности успеха одна вторая, получаем

GD_{1/2}^{\mathrm{main}} =\frac{1}{20\max_j(\kappa_j/(g_jd_j))}.

Двоичный логарифм его точного рационального значения равен

\log_2 GD_{1/2}^{\mathrm{main}} =173.273866314232\ldots

На ресурсной границе NIST $GD=2^{170}$ главный член не превышает $0.051693750450980417$ . К нему необходимо добавить два поправочных члена конечного размера.

Для каждого значения глубины NIST калькулятор получает максимальное число самых дешёвых когерентных ответов и последовательных раундов из

G=2^{170}/D, \qquad N=\left\lfloor\frac{G}{g_0}\right\rfloor, \qquad R=\left\lfloor\frac{D}{d_0}\right\rfloor.

Типизированный поправочный член конечного размера учитывает нестабильность извлечения и транскрипта. Глобальный член коллизии использует полную амплитуду коллизии параллельного сжатого оракула и возводит в квадрат всё положительное выражение вместе с перекрёстным членом. Наибольшая конечная поправка достигается при $D=2^{40}$ .

Член Category 1	Верхняя граница
Типизированный главный член	$0.051693750450980417$
Поправка конечного размера для извлечения и транскрипта	$0.000199022715317804$
Глобальный член 256-битной коллизии	$0.001471367157310191$
Полная верхняя граница в идеальной модели	$0.053364140323608411$

\boxed{ \varepsilon_{\mathrm{ideal}}^{\mathrm{Cat1}} \le0.053364140323608411\lt\frac12.}

Граница для фиксированной Poseidon2b

В идеальной теореме типизированный интерфейс транскрипта моделируется случайными оракулами, допускающими квантовые запросы. В штатной системе используется фиксированная публичная перестановка Poseidon2b с точным форматированием и разделением доменов. Пусть $\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}$ ограничивает увеличение вероятности полного неблагоприятного события компилятора при замене идеального интерфейса штатной конструкцией. Тогда

\Pr[\mathsf{BadState}]_{\mathrm{production}} \le \varepsilon_{\mathrm{ideal}}^{\mathrm{Cat1}} +\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}.

Оставшийся запас до вероятности одна вторая даёт следующее достаточное условие для штатной системы:

\boxed{ \Delta_{\mathrm{P2b}}^{\mathrm{Cat1}} \lt0.446635859676391589.}

Величина $\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}$ описывает отклонение для этого события при использовании точной публичной перестановки Poseidon2b, форматирования транскрипта и разделения доменов. Статья о Poseidon2b задаёт параметры фиксированной перестановки и содержит анализ её криптографической стойкости. Неравенство выше формулирует дополнительное условие реализации случайного оракула в квантовой модели, используемое сквозной теоремой.

Исполняемый сертификат с привязкой к исходному коду

Полный вывод и калькулятор опубликованы в репозитории анализа корректности Parano1d. Репозиторий содержит снимок штатных параметров и фиксирует ревизию исходного кода. Загрузка параметров отклоняет несоответствие между параметрами кошелька и их реестром, числом запросов History и BaseFold, пространством алгебраических вызовов, кодовой скоростью обоих классов History, разрядностью хеша или фиксированным профилем Poseidon2b.

Все вероятности и пороги оптимизации, от которых зависит вывод, вычисляются с помощью целых чисел произвольной разрядности и несократимых рациональных чисел. Верхние границы округляются вверх. Достаточный запас для фиксированной перестановки округляется вниз. Логарифмы с плавающей точкой используются только для представления результата и не влияют на итоговое сравнение.

Склонируйте репозиторий сертификата и воспроизведите штатный отчёт:

git clone https://github.com/ignotusnemo/parano1d-soundness.git
cd parano1d-soundness
cargo run --release --locked

Выведите все несократимые рациональные значения и точные пороги оптимизации:

cargo run --release --locked -- --exact

Запустите проверки снимка параметров, точной арифметики и пороговых значений:

cargo test --release --locked

Документ с доказательством, карта соответствия исходному коду, точный калькулятор и тесты образуют единый воспроизводимый сертификат. Вывод о Category 1 следует из последнего сравнения ресурсов в этой цепочке доказательств.

Первоисточники

Критерии оценки безопасности NIST Post-Quantum Cryptography, раздел 4.A.5, эталон AES-128 для Category 1 и значения MAXDEPTH.
Alessandro Chiesa, Peter Manohar и Nicholas Spooner, Succinct Arguments in the Quantum Random Oracle Model, последовательный аргумент переноса через сжатый оракул.
Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang и Tai-Ning Liao, On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work, параллельные границы перехода и коллизий.
Alessandro Chiesa, Dev Ojha и Nicholas Spooner, FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography, адаптивная композиция с привязкой к утверждению.
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty и Shubhangi Saraf, On Proximity Gaps for Reed–Solomon Codes, оценка близости с корреляцией по списку.
Ulrich Haböck, BaseFold in the List Decoding Regime, специализация штатной последовательности свёрток.
Lorenzo Grassi, Dmitry Khovratovich, Katharina Koschatko, Christian Rechberger, Markus Schofnegger, Verena Schröppel и Zhuo Wu, Poseidon(2)b: Binary Field Versions of Poseidon/Poseidon2.
Kyungbae Jang, Wonwoong Kim, Sejin Lim, Yeajun Kang, Yujin Yang, Hwajeong Seo и Ilsun You, Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion, обратимая схема умножителя в двоичном поле.