Parano1d meets NIST PQC Category 1

NIST Category 1 compares the resources required by an attack with exhaustive key search against AES-128. Its depth-aware model counts logical quantum gates, limits circuit depth and asks whether an attack can reach its target success probability inside that envelope.

For Parano1d, the target event is acceptance of a terminal State outside the set produced by valid executions from genesis. The production proof profile meets the NIST Post-Quantum Cryptography Category 1 resource target. At the complete NIST envelope, the ideal quantum-random-oracle bound is $0.049330348213215253$. The dominant half-success gate-depth floor is $2^{173.391078499301}$, which is $3.391078499301$ bits above the NIST $2^{170}$ reference.

The security game

Every accepted Parano1d block carries a recursive proof called HistoryStep. It proves the block relation, the exact transition from the authenticated parent State to the child State and verification of the preceding HistoryStep proof. Wallet authorization proofs and the sidecar relations consumed by the block are part of the same statement.

The public instance in the soundness game is the terminal HistoryStep State. One stateful quantum adversary wins when the production verifier accepts a State outside the set reached by valid executions from genesis. A failure in wallet authorization, the block relation, the parent link, the State transition, recursive verification or the claimed proof chain is therefore a win in the same game.

All oracle interactions used to build the terminal proof and every adversarial ancestor share one resource budget. After the compressed-oracle database is measured, extraction and traversal of the proof graph are deterministic and make no further oracle queries. The theorem covers the complete accepted State, including every FRI opening and recursive dependency.

Sequential queries and Category 1 resources

The production parameters support two complementary measurements. The sequential ideal-QROM theorem gives a boundary of $64.707407428576$ query bits. It counts each oracle call as one query and covers the budgets for which the explicit upper bound remains below one half.

The Category 1 theorem adds the reversible circuit required to answer each query. A coherent query to the production Poseidon2b transcript contains many binary-field multiplications. Parallelism reduces elapsed depth while total gate work remains in the resource ledger. The calculation keeps both quantities and derives a gate-depth lower floor directly.

The production instance

The certificate is integrated into Parano1d. ProductionParameters::load imports the wallet ledger and geometry, both History PCS profiles, the BaseFold query count, the wide-challenge support and the fixed Poseidon2b profile directly from the crates used by the production prover and verifier. The pinned analysis revision contains this source-linked certificate.

The two initial codeword lengths are the two production History geometries. B25 covers up to 25 effective page positions and B255 covers 26 through 255. They prove the same HistoryStep relation with the same rate, query count, challenge distribution and local theorem. Only the trace length changes.

Algebraic challenges lie in a trace-one affine subset of GF(2²⁵⁶) with exactly $2^{255}$ elements. The 256-bit digest width is a separate input. Keeping them separate is essential: algebraic exceptional sets use denominator $2^{255}$, while global binding collisions use $2^{256}$.

The local soundness theorem

The analysis first replaces each Fiat–Shamir squeeze by its corresponding verifier coin and exposes authenticated arrays as ideal oracles. This gives the public-coin IOP on which local generalized round-by-round knowledge error is proved. The local theorem grants the prover the larger acceptance set obtained by omitting the proof-of-work nonce predicate, so mining difficulty contributes zero soundness credit.

Wallet authorization

The September 5, 2026 refinement uses distance radius $4/5$ at the unchanged wallet rate $1/32$. Multiplicity-three Guruswami–Sudan interpolation bounds each list by 17 candidates. The correlated-agreement argument uses proximity multiplicity eight and preserves the common agreement set through the grouped additive folds. The complete wallet derivation gives every finite interpolation margin and exceptional-set count.

The eight proximity envelopes sum to $701201954824$. Adding $17^2(156+7)=47107$ algebraic roots covers fixed-origin candidate switching and the upper-link multilinear across the 3+4 fold groups. This improves the local query exponent to $150.925326167679$ bits without changing queries, matrices or proof formats. It does not change the Category 1 classification, classical FS-FRI result or sequential ideal-QROM boundary.

The wallet has one query-position escape term and one union of algebraic bad coins:

These belong to different verifier moves. Generalized round-by-round error takes the largest conditional escape probability:

HistoryStep

For an integer Johnson multiplicity $m\ge3$, define

At a rate-one-quarter Reed–Solomon layer of length $N$, the finite proximity envelope and strict initial-list bound are

The list-correlated Reed–Solomon theorem supplies $A_N(m)$. The BaseFold analysis carries it through the production fold schedule. With 133 independent query positions, the remaining escape term is

The 32 interleaved initial rows are packed into one extension-field Reed–Solomon word and share one finite initial list. Every nonexceptional fold restores a later candidate to correlated candidates in that same list. The later algebraic identities then take a union over the entire list, so candidate switching remains inside the bound.

The largest ordinary algebraic identity has 127 roots per candidate. The joint nine-group sidecar identity has 36. Combining query escape, every production fold layer and candidate switching gives

The proximity maximum ranges over $N\in\{2^7,\ldots,2^{19}\}\cup\{2^9,\ldots,2^{21}\}$, covering every folded layer of both production geometries.

A straight-line extractor list-decodes the packed word, recovers the 32 base-field rows, inverts the additive NTT and retains candidates satisfying the exact History relation. Backward induction over the verifier schedule shows that a witnessless accepting transcript must cross one of the four events in $\kappa_H(m)$. This is the local knowledge theorem used by both the sequential and resource-aware analyses.

The sequential optimum is $m=861824$. For Category 1, the exact resource-aware optimum is $m=318983$ because one History query requires twelve sequential Poseidon2b permutations.

From local proofs to one invalid-State event

Typed, statement-keyed oracle namespaces absorb every transcript family and adaptive statement into one event. After the single compressed-oracle database $D$ is measured, define $\mathsf{BadAll}(D)$ as the existence of any represented accepting wallet or History root for which deterministic extraction fails.

Two boundary events remain: a required child may be missing from the represented database, or a collision, ambiguous encoding or domain confusion may change the typed semantic graph. Therefore

In the closed typed ideal compiler, canonical nested artifacts are represented in the same database, so $\mathsf{MissRep}$ is false. Typed transcript and commitment binding are covered by the finite and collision terms below. Replacing the ideal interface with fixed Poseidon2b adds one production deviation term at the end.

Once the database is classical, a deterministic worklist begins at the accepted terminal, checks every local relation, follows the unique lower-height History parent and appends the required wallet and sidecar obligations. The rank decreases at every recursive edge and terminates at genesis. Valid extracted witnesses then imply the exact native State transitions in reverse topological order.

The all-root construction absorbs recursion into one probability event. Chain height changes deterministic extraction work, and a larger proof graph costs the adversary more resources, while every represented root remains inside one bad event and one total budget.

The sequential QROM cross-check

Let

Specializing the compressed-oracle lifting argument of Chiesa, Manohar and Spooner, together with the statement-keyed adaptive composition used by FRACTAL, gives the complete sequential ideal-QROM bound

Exact integer search finds the last $T$ for which this expression is below one half:

The first uncovered budget marks exactly where this upper bound reaches one half. Category 1 replaces the unit query counter with the logical resources needed to implement those coherent responses.

The NIST Category 1 reference

NIST Section 4.A.5 defines Category 1 by attacks requiring resources comparable to or greater than AES-128 key search. Its depth-aware guidance assigns the AES-128 reference

where $G$ is logical gate count and $D$ is maximum circuit depth. NIST lists $D=2^{40}$, $2^{64}$ and $2^{96}$. The certificate evaluates all three.

Typed parallel-QROM resources

For each typed bad-response event $j$, let $\kappa_j$ be its local density, $g_j$ the logical gates for one coherent response and $d_j$ its logical depth. The parallel compressed-oracle transition bound of Chung, Fehr, Huang and Liao, specialized to the all-root event, gives

The resource step also covers a parallel round containing several response types. If $k_{s,j}$ is the number of type-$j$ queries in round $s$ and $\delta_s=\max\{d_j:k_{s,j}\gt0\}$, then

Weighted Cauchy–Schwarz applied to the compressed-oracle transition amplitude yields

Adaptive statements and recursive roots share the same $\mathsf{BadAll}$ event and its resource accounting.

The coherent Poseidon2b response

The resource calculation uses a reversible GF(2¹²⁸) Karatsuba multiplier schedule with the following logical costs:

The production Poseidon2b permutation contains

S-boxes. The $x^7$ S-box uses two sequential field multiplications; coherent computation and uncomputation use four. Full-round S-boxes run in parallel. One coherent permutation response therefore has

A wallet query squeezes seven 128-bit lanes through a rate-two duplex and needs four sequential permutations. A History query needs twelve. Scalar responses use one.

The Category 1 conclusion includes the explicit premise that an adversary obtaining the corresponding coherent production response pays at least these logical gate and depth costs. The schedule omits positive routing, linear and control work, which is conservative for this construction. The theorem states its use as a minimum-cost premise; a universal lower bound for every reversible circuit would require a separate result.

The Category 1 calculation

The resource theorem evaluates wallet query and field events together with History query, proximity, candidate-switching and joint-sidecar events. At the exact resource-aware optimum $m=318983$, the largest ratio $\kappa_j/(g_jd_j)$ is the History query event.

Solving the main term for success probability one half gives

Its exact rational value has descriptive logarithm

At the NIST envelope $GD=2^{170}$, the main term is at most $0.047659958340587260$. Two finite terms still have to be added.

For every NIST depth point, the calculator derives the maximum number of cheapest coherent responses and sequential rounds from

The typed finite term covers extraction and transcript instability. The global collision term uses the complete parallel compressed-oracle collision amplitude and squares the whole positive expression, including its cross term. The worst finite envelope occurs at $D=2^{40}$.

The fixed Poseidon2b boundary

The ideal theorem models the typed transcript interface as quantum-accessible random oracles. Production uses the fixed public Poseidon2b permutation with exact framing and domain separation. Let $\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}$ bound the increase in the complete compiler bad event when the ideal interface is replaced by that production construction. Then

The available half-success headroom gives the sufficient production condition

This is an event-specific compiler deviation for the exact public Poseidon2b permutation, transcript framing and domain separation. The Poseidon2b paper supplies the fixed permutation parameters and their cryptanalysis; the inequality above states the additional quantum-instantiation condition used by the end-to-end theorem.

Current Poseidon2b cryptanalysis

Merz and Rodríguez García give improved algebraic attacks on Poseidon2 and Poseidon2b in ePrint 2026/306. Their wide tensor round skips apply to widths 12, 16, 20 and 24. Parano1d uses width 4, where the external layer is the binary MDS matrix M4 itself, so that attack family and the paper's wide-instance tables do not apply to the production permutation.

Appendix A does apply to the two-to-one feed-forward compression used by production Merkle trees. Specializing it to GF(2^128), $t=4$, $x^7$, $R_F=8$ and $R_P=58$ gives the round skip $(1,[1,7])$ and a descriptive classical dedicated-attack projection of approximately $2^{409.873818620410}$. This projection does not replace the fixed-Poseidon2b QROM premise above; it records the attack from the current paper that applies to the exact production mode.

An executable, source-linked certificate

The complete derivation and calculator are published in the noid_soundness crate inside the Parano1d repository. The certificate reads production parameters from the same Rust crates as the prover and verifier. Parameter loading rejects a mismatch between wallet geometry and its ledger, History and BaseFold query counts, challenge support, both History rates, digest width or the fixed Poseidon2b profile.

All normative probabilities and optimizer boundaries use arbitrary-size integers and reduced rational numbers. Upper bounds are rounded upward. Sufficient fixed-permutation headroom is rounded downward. Floating-point logarithms are descriptive and never decide the result.

Clone the pinned analysis revision and reproduce the production report:

git clone https://git.parano1d.org/ignotusnemo/parano1d.git
cd parano1d
git checkout 7f65daaae414128aa4377ca0ac1e96fd6dbc31a5
cargo run --release --locked -p noid_soundness

Print every reduced rational value and optimizer boundary:

cargo run --release --locked -p noid_soundness -- --exact

Run the source-correspondence, arithmetic and threshold regression suite:

cargo test --release --locked -p noid_soundness

The proof document, source-linked parameter loader, exact calculator and tests form one certificate. The terminal category is the final comparison performed by that chain of evidence.

Primary sources

• NIST Post-Quantum Cryptography Security Evaluation Criteria, Section 4.A.5, for the Category 1 AES-128 reference and MAXDEPTH points.
• Alessandro Chiesa, Peter Manohar and Nicholas Spooner, Succinct Arguments in the Quantum Random Oracle Model, for the sequential compressed-oracle lifting argument.
• Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang and Tai-Ning Liao, On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work, for parallel transition and collision bounds.
• Alessandro Chiesa, Dev Ojha and Nicholas Spooner, FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography, for statement-keyed adaptive composition.
• Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty and Shubhangi Saraf, On Proximity Gaps for Reed–Solomon Codes, for the list-correlated proximity envelope.
• Ulrich Haböck, BaseFold in the List Decoding Regime, for the production fold specialization.
• Lorenzo Grassi, Dmitry Khovratovich, Katharina Koschatko, Christian Rechberger, Markus Schofnegger, Verena Schröppel and Zhuo Wu, Poseidon(2)b: Binary Field Versions of Poseidon/Poseidon2.
• Simon-Philipp Merz and Àlex Rodríguez García, Skipping Class: Algebraic Attacks exploiting weak matrices and operation modes of Poseidon2(b), especially Section 3.4, Theorem 5.1 and Appendix A.
• Kyungbae Jang, Wonwoong Kim, Sejin Lim, Yeajun Kang, Yujin Yang, Hwajeong Seo and Ilsun You, Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion, for the reversible multiplier schedule.