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.053364140323608411$. The dominant half-success gate-depth floor is $2^{173.273866314232}$, which is $3.273866314232$ 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 calculation is pinned to Parano1d revision afdce21b6125ae0487c71a9093ab089cb8e88d5a. The standalone production snapshot records every security input, and the provenance map points each value back to its Rust definition.

The two initial codeword lengths are the two production History geometries. B64 is used through 64 user-transaction pages and B255 from 65 through 255 pages. 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 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^8,\ldots,2^{20}\}\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 wallet 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.051693750450980417$. 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.

An executable, source-pinned certificate

The complete derivation and calculator are published in the Parano1d soundness repository. The repository embeds its production snapshot and pins the source revision. 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 certificate and reproduce the production report:

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

Print every reduced rational value and optimizer boundary:

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

Run the snapshot, arithmetic and threshold regression suite:

cargo test --release --locked

The proof document, source-symbol map, 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.
• 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.