arXiv:2609.38894
Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
Prabhanjan Ananth, Yao-Ting Lin
Abstract
A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T=T(λ)$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).
AI Summary
Classical random-oracle time-lock puzzles cannot achieve a substantial gap between generation and sequential solving. This paper asks whether quantum-state puzzles evade that barrier and gives a construction in the quantum random oracle model, addressing the quantum-honest-party question left open in 2011. For every polynomially bounded delay $T=T(\lambda)=\omega(1)$, generation takes $\mathrm{poly}(\lambda,\log T)$ time and $\lambda+1$ classical oracle queries in one parallel round. The puzzle contains $O(\lambda^2\log T)$ single-qubit BB84 states and $\lambda^2+1$ classical bits. Quantum solving uses at most $T$ oracle rounds, with at most $\lambda$ queries per round, and has negligible error. Any computationally unbounded adversary receiving one copy and using polynomial query width and $r=o(T)$ rounds has negligible advantage in guessing the hidden bit. Each component encodes a random string in a hidden, code-selected BB84 basis and publishes a random-oracle verification tag. Exact amplitude amplification searches the basis labels while approximately preserving the token. Security starts from a list-recovery bound: for $N=\Theta(T^2)$ bases with pairwise state overlaps at most $\varepsilon=2^{-\lambda/2}$, a list of $p$ candidate pairs succeeds with probability at most $(1+(p-1)\varepsilon)/N$. Oracle reprogramming yields single-instance recovery probability $1/N+O(r/T)+\mathrm{negl}(\lambda)$. Interactive parallel repetition across $\lambda$ instances and a random-oracle mask give bit-hiding security. The guarantees concern oracle-round delay, not physical execution time, and require a single quantum puzzle copy and quantum solving. The model excludes superposition queries across distinct oracles; the result is not a standard-model construction.
We also used these tools to draft and revise text throughout the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 23 pages