Штатный профиль доказательств Parano1d анализируется в модели квантового случайного оракула относительно ресурсного эталона NIST Category 1 для полного перебора ключей AES-128. Доказательство начинается с точных отношений кошелька и HistoryStep, объединяет все представленные корневые объекты в одно событие принятия недопустимого состояния, переводит типизированные параллельные запросы к оракулу в число логических квантовых вентилей и глубину схемы и учитывает поправки конечного размера для извлечения и коллизий. На ресурсной границе NIST полная верхняя оценка вероятности успеха в идеальной модели равна 0.049330348213215253. Нижняя граница произведения числа вентилей на глубину при вероятности успеха одна вторая равна 173.391078499301 бит, что на 3.391078499301 бит выше эталона 2^170.
NIST Category 1 сравнивает ресурсы, необходимые для атаки, с полным перебором ключей AES-128. Модель учитывает число логических квантовых вентилей, ограничивает глубину схемы и определяет, может ли атака достичь заданной вероятности успеха в пределах этого бюджета.
Для Parano1d событием успеха противника служит принятие итогового состояния вне множества состояний, получаемых допустимым выполнением от генезиса. Штатный профиль доказательств достигает ресурсного уровня NIST Post-Quantum Cryptography Category 1. На полной ресурсной границе NIST верхняя оценка в идеальной модели квантового случайного оракула равна . Нижняя граница произведения числа вентилей на глубину схемы при вероятности успеха одна вторая составляет . Это на бит выше эталона NIST .
| Утверждение о стойкости | Штатный результат |
|---|---|
| Цель противника | Принятие недопустимого итогового состояния |
| Эталонная задача | Полный перебор ключей AES-128 |
| Эталон NIST для произведения числа вентилей на глубину | |
| Проверенные значения NIST MAXDEPTH | , и |
| Нижняя граница произведения при вероятности успеха одна вторая | |
| Запас относительно эталона NIST | 3.391078499301 бит |
| Полная верхняя оценка вероятности успеха в идеальной модели | |
| Достаточное условие для фиксированной перестановки Poseidon2b | |
| Категория NIST Post-Quantum Cryptography | Category 1 |
Игра безопасности
Каждый принятый блок Parano1d несёт рекурсивное доказательство HistoryStep. Оно подтверждает выполнение отношения корректности блока, точный переход от аутентифицированного родительского состояния к дочернему и корректность предыдущего доказательства HistoryStep. Доказательства авторизации кошельков и используемые блоком вспомогательные отношения sidecar входят в то же утверждение.
Публичным экземпляром игры служит конечное состояние HistoryStep. Единый квантовый противник, сохраняющий состояние между запросами, выигрывает, если штатный верификатор принимает состояние вне множества, достижимого допустимым выполнением от генезиса. Ошибка в авторизации кошелька, отношении корректности блока, родительской связи, переходе состояния, рекурсивной проверке или заявленной цепочке доказательств приводит к победе в этой же игре.
Все обращения к оракулу, использованные для построения итогового доказательства и всех предшествующих доказательств противника, входят в единый ресурсный бюджет. После измерения базы данных сжатого оракула извлечение свидетелей и обход графа доказательств выполняются детерминированно и больше не обращаются к оракулу. Теорема охватывает всё принятое состояние, включая каждое открытие FRI и каждую рекурсивную зависимость.
Последовательные запросы и ресурсы Category 1
Штатные параметры допускают два дополняющих друг друга способа оценки. Последовательная теорема для идеальной QROM даёт границу бит по бюджету запросов. Она считает каждое обращение к оракулу одним запросом и охватывает бюджеты, для которых явная верхняя оценка остаётся ниже одной второй.
Теорема Category 1 добавляет обратимую схему, необходимую для ответа на каждый запрос. Когерентный запрос к штатному транскрипту Fiat–Shamir на Poseidon2b требует большого числа умножений в двоичном поле. Параллелизм уменьшает глубину схемы, но не исключает суммарное число вентилей из учёта ресурсов. Расчёт использует обе величины и непосредственно выводит нижнюю границу для их произведения.
Штатные параметры
Сертификат встроен в Parano1d. ProductionParameters::load напрямую импортирует реестр и геометрию кошелька, оба PCS-профиля History, число запросов BaseFold, пространство широких вызовов и фиксированный профиль Poseidon2b из тех же crates, которые использует штатная реализация prover и verifier. Зафиксированная ревизия анализа содержит этот напрямую связанный с исходным кодом сертификат.
| Параметр | Штатное значение |
|---|---|
| Число запросов кошелька | 65 |
| Число запросов History | 133 |
| Размер пространства алгебраических вызовов | |
| Разрядность хеша | 256 бит |
| Кодовая скорость History | 1/4 |
| Начальное кодовое слово History | или |
| Группы совместных отношений sidecar | 9 |
| Poseidon2b | , скорость 2, , 8 полных раундов, 58 частичных раундов |
Две длины начального кодового слова соответствуют двум штатным размерам трассы History. B25 охватывает до 25 эффективных позиций страниц, а B255 охватывает от 26 до 255. Оба класса доказывают одно отношение HistoryStep с одинаковой скоростью кода, числом запросов, распределением проверочных вызовов и локальной теоремой. Различается только длина трассы.
Алгебраические вызовы принадлежат аффинному подмножеству GF(2256) со следом 1, содержащему ровно элементов. Разрядность 256-битного хеша является отдельным параметром. Для алгебраических исключительных множеств используется знаменатель , а для глобальных коллизий связывания используется .
Локальная теорема корректности
Сначала в анализе каждый вызов Fiat–Shamir заменяется соответствующим случайным вызовом проверяющей стороны, а аутентифицированные массивы рассматриваются как идеальные оракулы. Так получается IOP с публичными случайными монетами, для которого доказывается обобщённая пораундовая ошибка знания (RBR). Локальная теорема допускает более широкое множество принимаемых транскриптов, поскольку условие proof of work на значение nonce удалено. Поэтому сложность майнинга не учитывается как дополнительный запас корректности.
Авторизация кошелька
Уточнение от 5 сентября 2026 года использует радиус при неизменной скорости кода кошелька . Интерполяция Гурусвами–Судана с кратностью три ограничивает каждый список 17 кандидатами. Аргумент коррелированного согласия использует кратность восемь для оценки близости и сохраняет общее множество согласия через сгруппированные аддитивные свёртки. Полный вывод для кошелька содержит все конечные запасы интерполяции и мощности исключительных множеств.
Восемь оценок исключительных множеств дают в сумме . Добавление алгебраических корней учитывает переключение кандидатов с фиксированными исходными списками и верхний связывающий мультилинейный полином в группах свёрток 3+4. Локальный показатель запросного члена увеличивается до бита без изменения числа запросов, матриц или форматов доказательств. Классификация Category 1, классический результат FS-FRI и граница последовательной идеальной QROM остаются прежними.
Для кошелька учитываются член, соответствующий пропуску изменённой позиции всеми запросами, и объединение неблагоприятных алгебраических вызовов:
Эти события относятся к разным ходам проверяющей стороны. Обобщённая пораундовая ошибка знания (RBR) равна наибольшей условной вероятности уклонения:
HistoryStep
Для целого параметра кратности Джонсона определим
Для слоя кода Рида–Соломона длины и скорости 1/4 конечная оценка близости и строгая верхняя граница размера начального списка равны
Теорема о списочной корреляции для кодов Рида–Соломона даёт . Анализ BaseFold переносит эту оценку на штатную последовательность свёрток. Для 133 независимых позиций запросов остаточный член равен
Начальные 32 перемеженные строки упаковываются в одно кодовое слово Рида–Соломона над полем расширения и используют общий конечный начальный список. Каждая свёртка вне исключительного множества связывает кандидата на позднем этапе с коррелированными кандидатами-предшественниками из того же списка. Последующие алгебраические тождества берут объединение по всему списку, поэтому переключение кандидатов остаётся внутри границы.
Наибольшее обычное алгебраическое тождество имеет 127 корней на кандидата. Совместное sidecar-тождество для девяти групп имеет 36 корней. Объединение уклонения от запросов, всех штатных слоёв свёртки и переключения кандидатов даёт
Максимум оценки близости берётся по и охватывает каждый слой свёртки обоих штатных размеров трассы.
Алгоритм извлечения без перемотки выполняет списочное декодирование упакованного слова, восстанавливает 32 строки основного поля, обращает аддитивное NTT-преобразование и оставляет кандидатов, удовлетворяющих точному отношению History. Обратная индукция по последовательности ходов проверяющей стороны показывает, что принимаемый транскрипт без свидетеля должен попасть в одно из четырёх событий в . Эта локальная теорема извлечения знания используется и в последовательном анализе, и в анализе с учётом ресурсов.
Для последовательной теоремы точный оптимум равен . Для Category 1 точный оптимум с учётом ресурсов равен , поскольку один ответ на запрос History требует двенадцати последовательных перестановок Poseidon2b.
От локальных доказательств к одному событию принятия недопустимого состояния
Типизированные пространства имён оракулов, разделённые по утверждениям, объединяют все семейства транскриптов и адаптивно выбранные утверждения в одно событие. После измерения единой базы данных сжатого оракула событие означает существование представленного и принятого корневого объекта кошелька или History, для которого детерминированное извлечение завершается неудачей.
Остаются два граничных события. Необходимый дочерний объект может отсутствовать в базе данных, либо коллизия, неоднозначное кодирование или смешение доменов может изменить типизированный семантический граф. Поэтому
В замкнутом типизированном идеальном компиляторе канонические вложенные объекты представлены в той же базе данных, поэтому событие невозможно. Связывание транскриптов и обязательств учитывают два приведённых ниже слагаемых: поправка за конечный размер и вероятность коллизии. При замене идеального интерфейса фиксированной Poseidon2b в самом конце добавляется один член отклонения штатной конструкции.
После измерения база данных становится классической. Детерминированный обход начинается с принятого конечного состояния, проверяет каждое локальное отношение, переходит к единственному родителю History меньшей высоты и добавляет необходимые доказательства авторизации кошельков и проверки вспомогательных отношений sidecar. Ранг уменьшается на каждом рекурсивном ребре, поэтому обход завершается на генезисе. Допустимые извлечённые свидетели затем в обратном топологическом порядке влекут точные переходы состояния, определённые протоколом.
Конструкция для всех корней сводит рекурсию к одному вероятностному событию. Высота цепочки влияет на детерминированную работу извлечения, а больший граф доказательств требует от противника больше ресурсов. Все представленные корни остаются внутри одного неблагоприятного события и одного общего бюджета.
Контрольная последовательная оценка в QROM
Положим
Специализация аргумента переноса через сжатый оракул из работы Chiesa, Manohar и Spooner вместе с адаптивной композицией с разделением по утверждениям из FRACTAL даёт полную последовательную границу в идеальной QROM:
Точный целочисленный поиск находит последнее , для которого выражение меньше одной второй:
| Последовательная граница | Точное значение |
|---|---|
| Наибольший сертифицированный бюджет запросов | 30 121 082 641 781 720 121 |
| Первый бюджет за доказанной границей | 30 121 082 641 781 720 122 |
| Двоичный логарифм для представления результата | 64.707407428576 бит |
| Верхняя оценка при |
Первый бюджет за доказанной границей точно отмечает точку, в которой эта верхняя оценка достигает одной второй. В расчёте Category 1 запросы единичной стоимости заменяются логическими ресурсами, необходимыми для реализации когерентных ответов.
Ресурсный эталон NIST Category 1
Раздел 4.A.5 NIST определяет Category 1 через атаки, требующие ресурсов, сопоставимых с полным перебором ключей AES-128 или превышающих их. При учёте ограничения на глубину схемы NIST задаёт для AES-128 следующий эталон:
где обозначает число логических квантовых вентилей, а обозначает максимальную глубину схемы. NIST указывает , и . Сертификат проверяет все три значения.
Ресурсы типизированного параллельного QROM
Для каждого типизированного неблагоприятного события ответа обозначим через его локальную плотность, через число логических квантовых вентилей одного когерентного ответа и через его логическую глубину. Оценка перехода для параллельного сжатого оракула из работы Chung, Fehr, Huang и Liao после специализации на событии для всех корней даёт
Эта ресурсная оценка также охватывает параллельный раунд с несколькими типами ответов. Если обозначает число запросов типа в раунде , а , то
Взвешенное неравенство Коши–Буняковского для амплитуды перехода сжатого оракула даёт
Адаптивно выбранные утверждения и рекурсивные корни входят в общее событие и учитываются в его едином ресурсном бюджете.
Стоимость когерентного ответа Poseidon2b
В ресурсном расчёте используется обратимая схема умножителя Карацубы над GF(2128) со следующими логическими затратами:
| Ресурс | Число |
|---|---|
| CNOT | 29 340 |
| Однокубитные вентили Клиффорда | 4 374 |
| T | 15 309 |
| Всего логических квантовых вентилей | 49 023 |
| Логическая глубина | 43 |
Штатная перестановка Poseidon2b содержит
S-блоков. Для нужны два последовательных умножения в поле, а когерентное вычисление вместе с обратным вычислением использует четыре. S-блоки полного раунда исполняются параллельно. Поэтому один когерентный ответ перестановки имеет
Для ответа на запрос кошелька дуплекс со скоростью два должен выдать семь 128-битных элементов. Для этого выполняются четыре последовательные перестановки. Ответ на запрос History требует двенадцати перестановок, а ответ из одного элемента требует одной.
Вывод Category 1 включает явную предпосылку, что получение соответствующего когерентного ответа штатного оракула требует от противника как минимум указанного числа логических вентилей и указанной глубины. Схема не учитывает дополнительные затраты на маршрутизацию, линейные и управляющие операции, поэтому оценка консервативна для этой конструкции. Теорема формулирует минимальную стоимость как предпосылку. Универсальная нижняя граница для всех обратимых схем потребовала бы отдельного результата.
Расчёт Category 1
Ресурсная теорема одновременно рассматривает события запросов и алгебраических вызовов кошелька, а также события запросов, близости, переключения кандидатов и совместного sidecar-тождества для History. При точном оптимуме с учётом ресурсов наибольшее отношение даёт событие запроса History.
Приравнивая главный член к вероятности успеха одна вторая, получаем
Двоичный логарифм его точного рационального значения равен
На ресурсной границе NIST главный член не превышает . К нему необходимо добавить два поправочных члена конечного размера.
Для каждого значения глубины NIST калькулятор получает максимальное число самых дешёвых когерентных ответов и последовательных раундов из
Типизированный поправочный член конечного размера учитывает нестабильность извлечения и транскрипта. Глобальный член коллизии использует полную амплитуду коллизии параллельного сжатого оракула и возводит в квадрат всё положительное выражение вместе с перекрёстным членом. Наибольшая конечная поправка достигается при .
| Член Category 1 | Верхняя граница |
|---|---|
| Типизированный главный член | |
| Поправка конечного размера для извлечения и транскрипта | |
| Глобальный член 256-битной коллизии | |
| Полная верхняя граница в идеальной модели |
Граница для фиксированной Poseidon2b
В идеальной теореме типизированный интерфейс транскрипта моделируется случайными оракулами, допускающими квантовые запросы. В штатной системе используется фиксированная публичная перестановка Poseidon2b с точным форматированием и разделением доменов. Пусть ограничивает увеличение вероятности полного неблагоприятного события компилятора при замене идеального интерфейса штатной конструкцией. Тогда
Оставшийся запас до вероятности одна вторая даёт следующее достаточное условие для штатной системы:
Величина описывает отклонение для этого события при использовании точной публичной перестановки Poseidon2b, форматирования транскрипта и разделения доменов. Статья о Poseidon2b задаёт параметры фиксированной перестановки и содержит анализ её криптографической стойкости. Неравенство выше формулирует дополнительное условие реализации случайного оракула в квантовой модели, используемое сквозной теоремой.
Текущий криптоанализ Poseidon2b
Merz и Rodríguez García представили улучшенные алгебраические атаки на Poseidon2 и Poseidon2b в ePrint 2026/306. Их wide tensor round skips применимы к ширинам 12, 16, 20 и 24. Parano1d использует ширину 4, где внешний слой является самой бинарной MDS-матрицей M4, поэтому это семейство атак и таблицы wide instances из статьи к штатной перестановке не относятся.
Приложение A применимо к feed-forward сжатию два-в-один, которое используется в штатных деревьях Merkle. Подстановка GF(2^128), , , и даёт пропуск раундов и описательную классическую оценку специализированной атаки примерно . Эта оценка не заменяет предпосылку о фиксированной Poseidon2b в QROM, сформулированную выше. Она фиксирует ту атаку из текущей статьи, которая применима к точному штатному режиму.
Исполняемый сертификат, напрямую связанный с исходным кодом
Полный вывод и калькулятор опубликованы в crate noid_soundness внутри репозитория Parano1d. Сертификат читает штатные параметры из тех же Rust crates, что prover и verifier. Загрузка параметров отклоняет несоответствие между параметрами кошелька и их реестром, числом запросов History и BaseFold, пространством алгебраических вызовов, кодовой скоростью обоих классов History, разрядностью хеша или фиксированным профилем Poseidon2b.
Все вероятности и пороги оптимизации, от которых зависит вывод, вычисляются с помощью целых чисел произвольной разрядности и несократимых рациональных чисел. Верхние границы округляются вверх. Достаточный запас для фиксированной перестановки округляется вниз. Логарифмы с плавающей точкой используются только для представления результата и не влияют на итоговое сравнение.
Склонируйте текущий mainnet-релиз и воспроизведите штатный отчёт:
git clone https://git.parano1d.org/ignotusnemo/parano1d.git
cd parano1d
git checkout 7f65daaae414128aa4377ca0ac1e96fd6dbc31a5
cargo run --release --locked -p noid_soundness
Выведите все несократимые рациональные значения и точные пороги оптимизации:
cargo run --release --locked -p noid_soundness -- --exact
Запустите проверки соответствия исходному коду, точной арифметики и пороговых значений:
cargo test --release --locked -p noid_soundness
Документ с доказательством, загрузчик связанных с исходным кодом параметров, точный калькулятор и тесты образуют единый воспроизводимый сертификат. Вывод о 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.
- Simon-Philipp Merz и Àlex Rodríguez García, Skipping Class: Algebraic Attacks exploiting weak matrices and operation modes of Poseidon2(b), в особенности Раздел 3.4, Теорема 5.1 и Приложение A.
- 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, обратимая схема умножителя в двоичном поле.
