Digital signatures control who can spend funds, issue commands and authorize requests. Widely used schemes rely on factoring or discrete logarithms, assumptions threatened by Shor’s quantum algorithm. The post-quantum transition therefore reaches the mechanism used to establish authority itself.
Post-quantum signatures provide replacements with different security assumptions, key sizes, signature sizes and verification costs. Applications that also prove execution must express that verification in their proof arithmetic.
Signatureless authorization takes a direct proof-of-knowledge approach. An authority publishes a commitment to a reusable secret. Each action is authorized by a freshly randomized zero-knowledge proof of knowledge of that secret, bound to the requested action. The central security problem is safe reuse: an adversary can collect valid proofs, adapt later requests to earlier responses and attempt to authorize a fresh request.
The linked paper develops this construction and proves a quantum chosen-request security reduction in an explicit address-compatible random-completion model. It also establishes the bindings for recursive verification. Parano1d supplies the implementation and measurements. The interface supports both standalone requests and authorization composed with proofs of execution.
Post-Quantum Signatureless Authorization: paper and reproducibility artifact
Statement and request binding
Let s be the authority secret, a its public commitment, and I a canonical intent:
The prover establishes knowledge of s satisfying \operatorname{Addr}(s)=a. Both m and a enter the transcript before its proof challenges, binding the capsule to the requested action and authority.
The application defines the intent’s domain, operation, context, action data and execution constraints. Its adapter derives the required authority from that checked intent and policy. Execution enforces freshness by consuming a nonce, counter or resource reference.
The same secret supports repeated authorizations. Each attempt samples independent fresh prover randomness, including attempts that are later abandoned.
Binary-field construction
The construction uses \mathbb{F}_{2^{128}} embedded in \mathbb{F}_{2^{256}}:
- A width-four Poseidon2b authority circuit defines the secret-to-commitment relation.
- A masked degree-ten reduction turns the authority trace into eleven linear claims over a 2,048-cell source bank.
- Paired terminal pads, a separable Libra mask and dedicated source coins give explicit masking ranks. An independently randomized companion bank supports the linked evaluation proof.
- An affine Reed–Solomon code argument authenticates those evaluations using 65 code queries. The transcript fixes each message before the challenge that constrains it.
The subfield and extension serve different roles. Subfield cells carry the trace and independent randomness. Extension-field challenges support the masking maps and a challenge space of size 2^{255}. The recursive verifier checks these relations in compatible binary-field arithmetic.
The paper proves the masking ranks, adaptive simulation, finite-list source restoration and extraction. The public-coin extraction error is bounded by
Quantum authorization result
The security game allows an adversary to request authorizations for adaptively chosen intents. A forgery is an accepted capsule for a fresh intent under the same authority.
The quantum result uses the following primitive model:
- A fixed public circuit P_0 defines the authority relation and its address input slice.
- The native permutation agrees with P_0 on that slice and is sampled as a uniform permutation completion elsewhere.
- One native permutation supplies the transcript and commitment operations. The adversary has coherent forward and inverse access. Authorization requests, responses and the final forgery are classical.
- The fixed address slice satisfies the finite orbit-profile conditions in Appendix K. At authentication height ten, these are \Lambda_{10}\le 2^{15}, R_{10}<2^{25} and D_{10}<2^{24}. They bound inverse orbit fibers, short returns and shifted orbit intersections.
Under these conditions and independently fresh prover randomness, the paper establishes
The terms account for authority-preimage recovery, simulation error, extraction error and intent-binding failure. The simulator answers adaptive requests without the authority witness. The source extractor works in the same programmed quantum experiment and recovers a secret satisfying the authority relation from a successful fresh forgery, subject to the stated extraction loss.
For S\le T, the numerical certificates give:
| Charged native-call budget T | Combined simulation and extraction loss |
|---|---|
| T\le 2^{24} | below 2^{-67} |
| T\le 2^{32} | below 2^{-41} |
Here S counts authorization attempts. The call budget accounts for constructors, inverse calls, verification, recording rechecks and nonce-search work. In the sampled ideal-slice setup, the profile setup-failure term is included once. Total forgery probability also includes the authority-preimage and intent-binding terms in the displayed reduction.
Recursive verification and execution
For fixed intent and authority, capsule verification is independent of public execution state. A block prover can update the public execution witness within the intent’s constraints while retaining the same authorization capsule. The wallet supplies the authority proof, and the enclosing execution relation checks the permitted state transition.
The recursive composition result enforces the selected capsules’ native equations under exact binary-field arithmetic, complete tile coverage, authenticated transcript and hash regions, and canonical statement bindings. The enclosing recursive proof system supplies its soundness, and execution predicates enforce the intent’s state and policy constraints.
The implemented verifier tile contributes 16,536 incremental rows, including 1,852 rows for the authority reduction, post-claim relation and Phase A. Shared hash regions and execution predicates are accounted for in the enclosing relation.
Implementation costs
Measurements use an Intel Core i7-1365U, Linux x86-64, Rust 1.96.0 and four CPU threads. Each fixture has one warmup and five fresh proofs, with three verification runs per proof.
| Request fixture | Median proving | Median verification | Observed capsule bytes |
|---|---|---|---|
| Payment, 1 input and 1 output | 893.8 ms | 25.59 ms | 88,760–90,168 |
| Consolidation, 8 inputs and 2 outputs | 814.1 ms | 25.60 ms | 88,888–90,104 |
The maximum canonical capsule size is 92,696 bytes. Proving includes the address trace, entropy, commitments, proof generation, nonce search and self-verification. The separate verification timer begins after serialization and decoding.
The accompanying archive provides the source, raw measurements and reproduction programs. Its mathematical checks cover masking, finite extraction examples, compressed-query identities and the numerical security bounds.
Applications and discussion
The interface separates authority from application-specific execution. The same statement structure can authorize service requests, device commands and artifact approvals. Each adapter supplies its audience, operation, policy and freshness rules.
For Ethereum, an interesting integration question is where this authority and execution boundary fits best: rollups, proof-verified accounts or other recursive execution systems.
A useful comparison would measure direct authority proofs and post-quantum signature verification inside the same proof system, with matched security conditions and hardware. I would also welcome discussion of the fixed-slice quantum model and concrete cryptanalysis of the authority-preimage and finite orbit-profile conditions.