Time-lock puzzles in the quantum random oracle model

Classically they are impossible from a random oracle alone. Quantumly the question splits in three, and one cell is left.

Motivation

A time-lock puzzle hides a solution so that recovering it takes a long sequential time, even with unbounded parallelism. Whether one can be built from symmetric-key primitives alone is naturally asked in the random oracle model, where “time” has a clean information-theoretic proxy: the number of rounds of oracle queries an algorithm needs, with arbitrarily many queries inside a round.

Classically the answer is no. Mahmoody, Moran and Vadhan showed that if the generator asks \(n\) queries and the honest solver \(m\), an attacker always recovers the solution in \(O(n)\) rounds and \(\mathrm{poly}(n,m)\) queries, however sequential the honest solver is — and that \(n\) rounds is optimal, via a pseudo-chain puzzle that genuinely needs them.

Once oracles can be queried in superposition the question splits by which party is quantum: the generator, the solver, or both. Two of the three cells are settled. The third — both quantum — is the statement here, and it is guarded by a barrier: any attack asking only classical queries would prove a simulation conjecture in the Aaronson–Ambainis line.

Provenance and history

One source paper: Afshar, Chung, Hsieh, Lin and Mahmoody, On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model, ePrint 2023/932. Verified against ePrint on 18 August 2026, where it is posted as a preprint; a version appears at ASIACRYPT 2023 under a closely related title.

The statement was drafted by scripts/harvest_conjectures.py from that PDF and is AI-written and unreviewed, as its status badge says. One scope point the draft’s own provenance file raised has been carried onto the page rather than smoothed over: the transcription follows the paper’s Definition 2.6 in taking the puzzle itself to be classical, which is a restriction relative to the paper’s remark that “one can imagine the puzzle itself to be a quantum object”.

Parameter lattice

Three cells, by which party is quantum. Query counts are the generator’s \(n\) and the honest solver’s \(m\).

generator solver status
classical classical impossible — MMV11, \(O(n)\) rounds
classical quantum settled by the source paper, for arbitrary completeness error; round-optimal under perfect completeness
quantum classical settled by the source paper, under perfect completeness
quantum quantum open — c/0028

The open cell is the one where both the generator and the solver exploit superposition queries. The paper offers no attack there and proves a conditional barrier instead: an attacker restricted to classical queries would settle the paper’s Conjecture 6.1, a weakening of the folklore Aaronson–Ambainis simulation conjecture. So an attack must itself be quantum, which is exactly what the statement asks for.

Statements in this hub