The post-quantum migration path: lattice commitments, STARK wrapping, isogeny credentials

The whole F_RP framework, as written today, is completely broken by Shor’s algorithm. Every elliptic-curve assumption the construction rests on — DLOG on Curve25519, q-PKE on BN254, q-DLOG on the Pasta cycle — falls in polynomial time on a sufficiently large fault-tolerant quantum computer. Pedersen commitments lose binding. Groth16 loses soundness. Ed25519 signatures lose unforgeability. The entire stack is a pre-quantum house.

Today this is fine. NIST estimates a cryptographically-relevant quantum computer is still 10-20 years away. But “we’ll fix it later” is exactly how we got into the SHA-1 / RSA-1024 / DES situation. The right time to design the migration path is before there’s a deadline.

This is post 11 of 11 in the relayerless-privacy series — the finale.

What Shor breaks, in one paragraph

Shor’s algorithm gives a quantum polynomial-time reduction from integer factoring and discrete log to period-finding. RSA, classical Diffie-Hellman, DSA, ECDSA, Ed25519, Schnorr signatures, BLS signatures, Pedersen commitments, Pairings — every cryptographic primitive that relies on the hardness of DLOG or factoring is compromised.

For F_RP specifically, the four broken pieces:

1. Groth16 over BN254. q-PKE / q-DLOG → polynomial-time forgery.
2. Pedersen commitments over BN254. DLOG → binding broken; commitments become equivocable.
3. Ed25519 signatures. DLOG → forgery, including FROST threshold variants.
4. CSIDH and other classical isogeny constructions. Kuperberg’s quantum sub-exponential algorithm threatens them more aggressively than classical attacks.

Hash-based primitives survive: SHA-2, SHA-3, Keccak, Poseidon (modulo round-by-round cryptanalysis). FRI / STARK proofs survive because they only depend on hash collision resistance, not on any algebraic structure. Lattice-based primitives (Module-LWE, Module-SIS) survive under best-known quantum attacks.

The replacement stack

Post-quantum F_RP is 5-20 KB per proof instead of 128 bytes, ~300K CU on-chain instead of ~150K, and ~5 KB per signature instead of 64 bytes. The framework still works; the costs grow ~50-100× on every dimension.

Lattice-based polynomial commitments

The replacement for KZG is a polynomial commitment based on Module-LWE / Module-SIS. Two leading candidates:

Brakedown (Golovnev, Lee, Setty, Thaler, Wahby — CRYPTO 2023)

Linear-time SNARK based on linear-code polynomial commitments. The prover commits to multilinear polynomials using a linear-time encodable error-correcting code, combined with the Spartan polynomial IOP.

• Prover: O(N) field operations for N-sized R1CS.
• Proof size: ~1.5 MB for 2^20 multiplication gates (before code-switching compression).
• Verification: linear in proof size.
• No trusted setup.
• Plausibly post-quantum secure (security from collision-resistant hashing + linear-code distance).

The O(√N) base proof size is the killer for Solana — even the 4,096-byte SIMD-0296 limit isn’t enough for a raw Brakedown proof on a meaningful circuit.

Orion (Xie, Zhang, Song — CRYPTO 2022)

O(N) prover time with O(log²N) proof size via code-switching composition. The code-switching mechanism reduces proof size from O(√N) to polylogarithmic by proving that the witness of a secondary zero-knowledge argument coincides with the message in a linear code.

Numbers are still rough — ~10 KB proof for 2^20 constraints — but the trajectory is right. Orion is the most promising candidate for direct on-chain verification on Solana under SIMD-0296.

Open problem 7.1 — lattice commitment size

Current lattice-based commitments produce opening proofs of size O(k · d · log q) bits, yielding 4-50 KB concretely. Determine tight lower bounds for 128-bit post-quantum security; characterise the feasibility space within Solana’s tx limit.

Hash-based STARKs as universal backend

STARKs are already post-quantum (security from collision-resistant hashing only). The migration is simpler in shape but more expensive in proof size:

• FRI over Goldilocks field ($p = 2^{64} - 2^{32} + 1$): efficient NTT, native to 64-bit hardware. Plonky3 uses this.
• FRI over M31 (Mersenne-31): SIMD-optimised arithmetic. StarkWare’s Circle STARK construction uses M31.

Proof size scaling: O(λ · log²N). For 2^20 steps at 128-bit security, ~50-200 KB per proof.

A 400×-1600× blowup vs. Groth16’s 128 bytes. Way over Solana’s transaction limit. Three deployment paths:

Path 1: STARK-in-Lattice-SNARK (Open Problem 7.2)

Wrap the STARK verifier circuit inside a lattice-based SNARK to recover succinct on-chain verification. The STARK verifier circuit is O(log²N) hash evaluations + field operations. With Poseidon (~250 R1CS constraints per hash), 2^20-step verification is ~100K constraints.

Recursive composition:

Estimated proof size: ~5-20 KB. Marginal fit for SIMD-0296 (4,096-byte transactions). Open whether the lattice outer is small enough.

Path 2: STARK aggregation (STARKPack)

Aggregate n STARK proofs into a single argument that’s $(1 + 1/n)$× the size of a single proof, with ~2× faster verification.

Doesn’t help individual transactions (still 100 KB per submission) but amortises validator-side cost dramatically.

Path 3: Off-chain STARK with on-chain commitment

The most pragmatic near-term path. Publish the full STARK proof to a data-availability layer (Solana ledger via call-data, or a separate DA chain). On-chain verify only a 32-byte hash commitment. Add a challenge period where any observer can verify the off-chain proof and dispute on-chain if it’s invalid.

^* Requires off-chain proof availability + honest-verifier assumption for retrieval.

Isogeny-based group actions for credentials

For applications needing anonymous identity binding — compliance-compatible privacy, selective disclosure, “prove balance ≥ threshold without revealing balance” — isogeny-based cryptography offers post-quantum group actions that can replace DLOG-based constructions.

CSIDH-based ring signatures

CSIDH defines a commutative group action ★: Cl(O) × E(F_p) → E(F_p) between the ideal class group of an imaginary quadratic order and the set of supersingular elliptic curves over F_p. This group action instantiates Sigma protocols for “knowledge of an isogeny”, which yields ring signatures via Fiat-Shamir.

Current status (cautious): CSIDH at NIST-1 security needs p ≈ 2^512, key sizes ~64 B, computation ~50-100 ms. Quantum security analysis (Bonnetain-Schrottenloher, Peikert) shows Kuperberg’s quantum sub-exponential algorithm threatens CSIDH more aggressively than classical attacks — proposed 128-bit classical / 64-bit quantum parameters can be broken in ~2^35 quantum key-exchange evaluations, not ~2^62.

So CSIDH at the 128-bit level is not secure at the originally advertised parameters. Larger parameters (p ≈ 2^4096+) restore the security but balloon costs.

SQIsign

SQIsign (De Feo, Kohel, Leroux, Petit, Wesolowski — NIST Round 2) offers compact post-quantum signatures (204 bytes) from quaternion isogeny problems. Signing time ~100 ms.

Verification is computationally expensive (~100 ms), which makes it impractical for direct on-chain verification on Solana — a single SQIsign verification would consume the entire 1.4M CU budget.

Open problem 7.3 — isogeny anonymous credentials

Design an anonymous credential scheme based on supersingular isogeny group actions that:

1. Supports selective attribute disclosure.
2. Has verification time < 10 ms (compatible with blockchain block times).
3. Achieves 128-bit post-quantum security with concrete parameter justification.
4. Is compatible with the SPST note model (credentials bound to note commitments).

This is wide open. The most promising shape is a hybrid architecture: isogeny-based credentials for identity binding, composed with STARK proofs for the transactional privacy layer.

What survives without modification

Two pieces of F_RP carry over unchanged into the post-quantum world:

1. Poseidon Merkle trees. Hash-based, no algebraic structure assumption beyond collision resistance.
2. Indexed Merkle Trees for nullifier non-membership. Same hashes, same structure, same constraints.

So the state layer of F_RP doesn’t need to change. Only the proof and signature layers.

Migration timeline (rough)

This timeline is contingent on (a) NIST shipping PQC standards on schedule, (b) Solana adopting the syscalls within ~2 years of standardisation, and (c) lattice-based polynomial commitments achieving sub-10 KB proof sizes. None of these are certain. All three look likely.

What would have to change in F_RP itself

The protocol design is mostly insulated. Specifically:

1. The note model is unchanged. Notes, commitments, nullifiers, Merkle trees — all hash-based.
2. The five-tuple (Setup, Deploy, Invoke, Verify, Finalize) is unchanged. Just the proof system inside Invoke/Verify swaps out.
3. The simulation-based privacy theorem (3.12) survives. The hybrid argument’s transitions are: ZK of proof system, pseudorandomness of hash, pseudorandomness of PRF, CCA2 of encryption. The ZK / PRF / CCA2 each get a post-quantum-secure replacement; the structure of the proof is the same.
4. The self-sovereignty theorem (3.13) survives unchanged. It only depends on chain liveness and proof system completeness.

What changes: byte sizes, CU costs, prover times. The math survives. That’s a lucky property of having designed F_RP around the abstract Π_hybrid rather than committing to Groth16 in the relations.

Why this isn’t urgent (today)

It’s worth ending the series with the honest answer to “should I be worried right now?”:

No. Not in 2026, not in 2028. A cryptographically-relevant quantum computer is plausibly a decade-plus away. The harvest-now-decrypt-later threat applies to confidentiality (encrypted communications today, decrypted later when QC arrives) — but most F_RP outputs are commitments and nullifiers, not encrypted plaintexts. The information-theoretic content of an old shielded transaction is bounded; an adversary who breaks it in 2040 learns transaction graph structure that’s no longer interesting.

What does need attention: building the migration path now so that when the day comes, F_RP isn’t a 2-year rewrite project. That’s what this post is for.

Closing the series

Eleven posts:

1. Series intro — the F_RP framework and the five games.
2. The fee paradox — why every smart-contract privacy protocol needs a relayer.
3. SPST — self-paying shielded transactions, four security theorems.
4. PPST — private programmable state via R1CS embedding.
5. TAB — submitter anonymity via ring sigs and FROST.
6. Verifiable shuffles — Bayer-Groth network-layer mixing.
7. UPEE — composing the framework, the simulation-based privacy and self-sovereignty theorems.
8. Solana instantiation — concrete numbers: 656 bytes, 235K CU.
9. F_RP vs the rest — comparison with nine deployed privacy systems.
10. MEV resistance — sandwich-proof by construction; Theorem 7.4.
11. Post-quantum migration — the future-proofing plan you just read.

The full preprint will land at /papers/relayerless-privacy/ once typeset. Until then the series is the canonical reference. If you want to discuss any of it, book a call or open an issue on Dax911/zera-sdk.

Thanks for reading.

Bibliography

• Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing.
• Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R. (2023). Brakedown. CRYPTO 2023.
• Xie, T., Zhang, Y., Song, D. (2022). Orion. CRYPTO 2022.
• Ben-Sasson, E. et al. (2018). STARKs. https://eprint.iacr.org/2018/046
• De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B. (2020). SQIsign. ASIACRYPT 2020. https://eprint.iacr.org/2020/1240
• Castryck, W. et al. (2018). CSIDH. ASIACRYPT 2018. https://eprint.iacr.org/2018/383
• Bonnetain, X., Schrottenloher, A. (2018). Quantum Security Analysis of CSIDH.
• Peikert, C. (2020). He gives C-sieves on the CSIDH.
• NIST PQC Round 4 — Post-Quantum Cryptography Standardization.

Previous: MEV resistance ← · Series: back to start