Mitigating PQC Signature Size Overhead via Identity-Bound ZK Authorization

[Jason Wang]

Dear PQC Forum members,

I would like to share an architecture I have been exploring for post-quantum authorization in distributed systems, with blockchain transactions as the primary motivating case.

The problem with direct PQC deployment

Direct deployment of ML-DSA or SLH-DSA in blockchain transactions introduces kilobyte-scale on-chain artifacts. ML-DSA signatures at NIST security level 2 are approximately 2.4 KB, compared to 64 bytes for Ed25519 — a roughly 30–40× increase per transaction. A natural response is to verify these signatures inside zero-knowledge circuits. However, this does not remove the core cost: lattice-based signature verification requires arithmetic over high-dimensional algebraic structures (NTTs over degree-256 polynomial rings, high-bit-width modular reductions), which translates to millions of R1CS constraints even with optimized non-native arithmetic. The scalability burden is relocated, not eliminated.

A different framing: authorization as a semantic property

At the consensus layer, blockchains do not inherently require verification of a specific cryptographic signature object. What consensus requires is assurance that a given transaction was authorized by the correct entity. Treating the signature object as the primary unit of verification couples consensus security to the concrete properties of a particular signature scheme. ZK-ACE takes a different approach: authorization is modeled as a semantic property — that a specific identity has approved a specific transaction — independent of the artifact traditionally used to express that approval.

The construction

ZK-ACE assumes a deterministic identity derivation primitive (DIDP) as a black-box building block. A DIDP provides a stable, deterministic mapping from a 256-bit Root Entropy Value (REV) — the identity root — to context-specific cryptographic keys across classical and post-quantum algorithms. The REV exists only ephemerally in memory; it is never persistently stored or exposed. ACE-GF is one concrete instantiation of this interface; any framework satisfying the DIDP interface may be used.

On-chain, each identity stores a compact commitment:

        ID_com = H(REV ‖ salt ‖ domain)

To authorize a transaction, the prover demonstrates in zero knowledge:

There exists a REV and associated derivation context such that: (i) the identity commitment derived from REV matches the on-chain commitment ID_com, and (ii) the identity anchored by REV has authorized the transaction with hash TxHash under the prescribed derivation context and replay-prevention rules.

The circuit encodes five constraints (commitment consistency, deterministic derivation correctness, authorization binding to TxHash, anti-replay, and domain separation). It contains no post-quantum signature verification logic and no lattice arithmetic.

To be precise about scope: ZK-ACE does not verify ML-DSA or any other post-quantum signature object, does not compress post-quantum signatures, and does not embed lattice-based operations inside the circuit. It represents a shift in authorization semantics — explicit signature verification is replaced by zero-knowledge proofs of deterministic authorization.

Formal security properties

The paper provides game-based definitions and reduction-based proofs for four security properties under knowledge soundness, collision resistance, and DIDP identity-root recovery hardness:

• Authorization soundness: an adversary without REV cannot produce a valid authorization proof for a committed identity.
• Replay resistance: a previously accepted authorization cannot be resubmitted (under nonce-registry or nullifier-set enforcement).
• Substitution resistance: a valid proof cannot be rebound to a different transaction hash, since the proof is cryptographically bound to TxHash via constraint (C3).
• Cross-domain separation: a proof valid in one domain cannot be replayed in another, enforced by including domain in all commitment and binding computations (C1–C5).

Implementation and benchmarks

The reference implementation provides two pluggable backends:

• Circle STARK (Stwo, post-quantum-oriented): 341 active rows / 361 AIR constraint expressions, 14.5 ms prove, 1.1 ms verify, transparent setup. Post-quantum security is conditional on the instantiated Poseidon2 hash parameters providing adequate quantum collision-resistance margins; this is not taken as established and requires dedicated parameter analysis.
• Groth16/BN254 (classical only): 2,155 R1CS constraints, 37.3 ms prove, 1.6 ms verify, 128-byte compressed proofs. This backend relies on discrete logarithm hardness on BN254, broken by Shor's algorithm. It must not be deployed in post-quantum threat models. It is provided for EVM compatibility and circuit feasibility demonstration only.

Both backends are roughly 500–2,300× smaller than in-circuit post-quantum signature verification by constraint count. Under per-block STARK aggregation, per-transaction consensus-visible data is ≈ 160 bytes (public inputs only), with aggregated proof overhead amortized across the block.

The system is post-quantum-ready by design: identity commitments and the circuit statement are proof-system-agnostic, so migration from the Groth16 backend to a transparent hash-based backend requires no identity rotation or circuit redesign.

References

ZK-ACE paper: https://arxiv.org/abs/2603.07974
ACE-GF paper: https://arxiv.org/abs/2511.20505
ACE-GF IETF Internet-Draft: https://datatracker.ietf.org/doc/draft-wang-acegf-protocol/

I would welcome feedback on:

1. Whether identity-bound ZK authorization is a useful direction for PQC systems, or whether authorization should remain signature-centric.
2. Concrete quantum-security margins for STARK-friendly hash parameters (specifically Poseidon2 over Mersenne-31) used in long-lived commitments — the BHT collision bound of 2^(n/3) queries makes the collision margin more demanding than the preimage margin, and the adequate output-length requirement is not yet established.
3. The soundness of treating deterministic identity derivation as a black-box interface with explicit context separation (the DIDP abstraction), and whether the minimal assumption of identity-root recovery hardness is sufficient or whether a stronger notion is needed in practice.
4. What practical barriers exist to instantiating the DIDP interface with constructions other than ACE-GF — particularly for interoperability with existing key management infrastructure (hardware security modules, BIP-32-style hierarchical derivation, or PKCS#11 environments).

Criticism, alternative constructions, and independent experiments would be very welcome.

Best regards,
Jason Wang