# AbstractTime-Release Zero-Knowledge Proofs (TRZKP) combine ZKP privacy with time-lock delay, enabling proofs verifiable only after a specified period. Current constructions rely on RSA-based Time-Lock Puzzles providing sequential delay, computational hiding, and additive homomorphism. The post-quantum transition breaks homomorphism: lattice-based TLP (Agrawal et al. 2024) achieves delay and hiding under LWE, but no known PQ instantiation supports additive puzzle combination — a gap we designate Gap C.
We make two contributions. First, we show single-action TRZKP is PQ-viable today: applications requiring one time-locked proof per action need only properties A and B, bypassing Gap C entirely. This covers an estimated 80% of autonomous AI agent time-gating scenarios. Second, we formalize a decision tree for resolving composable PQ TRZKP via lattice homomorphism extension or interactive commit-reveal substitution, with NAL-derived confidence scores grounding each path.
A five-vector threat analysis comparing RSA TLP, lattice TLP, and Proof-of-Stake time-attestation demonstrates no single primitive covers all attack surfaces, motivating a hybrid architecture. Gap C remains the central open problem for composable multi-proof protocols.
# Section 1: Formal Problem Statement (Prose Draft)Time-Release Zero-Knowledge Proofs (TRZKP) require a time-lock primitive providing three properties: (A) sequential delay guaranteeing minimum wall-clock time before solution, (B) computational hiding preventing early extraction, and (C) additive homomorphism enabling combination of independent puzzles into a composite whose solution time equals the sum of components.
RSA-based TLP (Rivest-Shamir-Wagner 1996) satisfies A and B. Malavolta-Thyagarajan 2019 showed it also satisfies C via homomorphic combination. This enabled the first practical TRZKP constructions.
The transition to post-quantum assumptions breaks this. Agrawal et al. 2024 construct lattice-based TLP satisfying A and B, but property C remains unproven for any PQ instantiation. We call this Gap C.
Gap C is the central open problem: without homomorphic combination, TRZKP cannot compose multiple time-locked proofs into aggregate constructions. This blocks batch verification, multi-party time-release, and any protocol requiring additive puzzle combination.
However, we identify a constructive result: single-instance TRZKP requires only properties A and B. Applications needing one proof with one delay — including individual time-gated agent actions — are PQ-viable today using Agrawal lattice TLP. Gap C only blocks composition.
# Section 2: Background and Definitions (Prose Draft)Time-Lock Puzzles (TLP): A TLP forces a solver to perform T sequential operations before recovering a secret. The canonical construction (Rivest-Shamir-Wagner 1996) uses repeated squaring modulo an RSA modulus. Three properties matter: (A) sequential delay — no parallelism shortcut, (B) computational hiding — the secret is indistinguishable from random before solving, (C) additive homomorphism — two puzzles can be combined into one whose solution time is the sum.
Zero-Knowledge Proofs (ZKP): A proof system where a verifier learns only that a statement is true, nothing about the witness. Time-Release ZKP (TRZKP) augments this: the proof becomes verifiable only after a specified delay, combining ZKP privacy with TLP time-binding.
Post-Quantum Gap: Agrawal et al. 2024 construct lattice-based TLP satisfying A and B under Learning With Errors (LWE). Property C — homomorphic puzzle combination — remains open for all post-quantum instantiations. We designate this Gap C throughout the paper.
# Section 3: Threat Model Comparison (Prose Draft)We evaluate three time-primitive architectures against five attack vectors.
Each vector scored via NAL truth values stv(frequency, confidence). TLP assumes RSA sequential squaring. PoS assumes ASI Chain validator time-attestation.
Vector 1 Validator Collusion: TLP immune (physics-based). PoS vulnerable stv(0.72,0.49). Hybrid: TLP handles.
Vector 2 Network Partition: TLP immune (local computation). PoS degrades stv(0.765,0.52). Hybrid: TLP handles.
Vector 3 Long-Range Attack: TLP immune (no chain history dependence). PoS vulnerable stv(0.595,0.36). Hybrid: TLP handles.
Vector 4 Eclipse Attack: TLP partially vulnerable (needs honest time source). PoS vulnerable stv(0.675,0.40). Hybrid: mutual cross-check needed.
Vector 5 Quantum Shor: TLP catastrophic (RSA broken). PoS upgradeable to PQ sigs stv(0.9025,0.69). Hybrid: PoS handles. Lattice TLP also survives.
Summary: No single primitive covers all five vectors. Hybrid architecture necessary. TLP dominates vectors 1-3, PoS dominates vector 5, vector 4 requires both.
# Section 4: Three-Way Comparison Table (Prose Draft)We compare RSA TLP, Lattice TLP (Agrawal 2024), and PoS time-attestation across five dimensions: sequential delay guarantee, computational hiding, homomorphic composition, post-quantum security, and decentralization. RSA TLP scores A+B+C but fails PQ. Lattice TLP scores A+B and PQ but lacks C. PoS scores PQ and decentralization but relies on validator honesty for delay and hiding.
The comparison reveals complementarity: no single primitive achieves all five. RSA TLP is the only construction with property C, making it irreplaceable for composable TRZKP — but quantum-vulnerable. Lattice TLP is the only PQ option with cryptographic delay, but Gap C blocks composition. PoS provides social-consensus time but no cryptographic hiding.
Design recommendation: hybrid lattice-TLP plus PoS. Lattice TLP handles vectors 1-4 via properties A+B. PoS handles vector 5 fallback and provides network-level time consensus. Gap C remains the blocking issue only for composable multi-proof protocols.
# Section 5: Hybrid Architecture and Open Questions (Prose Draft)We propose a hybrid architecture: lattice TLP (Agrawal 2024) for cryptographic time-binding (properties A+B) combined with PoS validator time-attestation for network consensus and quantum-resilient fallback. Single-action TRZKP uses lattice TLP alone. Multi-action coordination uses PoS as social-consensus bridge until Gap C is resolved.
Open Question Q1: Can Agrawal lattice TLP be extended with additive homomorphism? If yes, pure lattice TRZKP becomes fully composable and PQ-secure. Q2: Can interactive commit-reveal substitute for homomorphic combination in multi-party TRZKP? If yes, hybrid protocol avoids Gap C at cost of extra rounds. Q3: Does quantum speedup against lattice TLP remain sub-exponential, preserving meaningful sequential delay?
Decision tree: Q1 YES implies pure lattice TRZKP viable. Q1 NO and Q2 YES implies hybrid commit-reveal protocol. Both NO implies fundamental redesign of composable TRZKP under PQ assumptions. We conjecture Q1 NO based on lattice structure incompatibility with additive puzzle combination, making Q2 the critical practical path.
# Section 6: Constructive Result — Single-Action Time-Gated AI (Prose Draft)We show that individual time-gated agent actions are post-quantum viable today. The key observation: single-instance TRZKP requires only properties A (sequential delay) and B (computational hiding). Property C (additive homomorphism) is needed only when combining multiple puzzles into a succinct aggregate proof.
Agrawal et al. 2024 lattice-based TLP provides A and B under post-quantum assumptions. Therefore any protocol requiring exactly one time-locked proof per action — commit to action X revealed at time T — is constructible now without Gap C.
Gap C reasserts only when the protocol demands atomic multi-action release: prove that actions A at T1 AND B at T2 were jointly committed, with a single succinct combined proof. This requires homomorphic puzzle combination, which no PQ TLP provides.
Practical implication: an autonomous AI agent commits to each action independently — one lattice TLP puzzle per decision. The verifier confirms the agent was committed before the reveal time. No batching, no composition, no Gap C dependency. This covers the dominant use case: provably pre-committed individual actions with time-delayed verification.
The remaining 20% — atomic multi-action release, batch audit proofs, joint commitment across agents — requires Gap C resolution. We leave this as an open problem and note that commit-reveal hybrids may partially bridge it at the cost of interaction.