Breaking Fully Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Classically, a random oracle cannot support a time-lock puzzle: an attacker always recovers the solution in a number of rounds proportional to the generator’s query count, no matter how sequential the honest solver is. The source paper carries that impossibility into the quantum random oracle model in two of the three cases — classical generator with quantum solver, and quantum generator with classical solver. The conjecture is that the last case falls too: when both parties are quantum, a quantum attacker still breaks the puzzle in \(\lceil n/\varepsilon\rceil\) rounds.

View PDF · Download LaTeX source

A fully quantum time-lock puzzle in the QROM is a pair \(\Pi = (\mathsf{Gen}, \mathsf{Sol})\) of quantum oracle algorithms: \(\mathsf{Gen}^{H}\) makes \(n\) queries and outputs a puzzle and its solution, \(\mathsf{Sol}^{H}\) makes \(m\) queries and recovers the solution with completeness error \(\rho\). Rounds are counted as in the paper: arbitrarily many queries may be issued in parallel within one round.

Conjecture. There is a fixed polynomial \(p\), independent of everything below, such that for every such \(\Pi\) and every \(\varepsilon, \delta \in (0,1]\) there is a quantum oracle algorithm \(\mathsf{Ext}\) — allowed to depend on \(\Pi\), \(\varepsilon\) and \(\delta\), and not required to be efficient — with

at most \(p(n, m, 1/\varepsilon, 1/\delta)\) quantum queries to \(H\);
those queries arranged in at most \(\lceil n/\varepsilon \rceil\) rounds; and
\(\Pr[\mathsf{sol}' = \mathsf{sol}] \ge 1 - \rho - \varepsilon - \delta\), over \((\mathsf{puz}, \mathsf{sol}) \gets \mathsf{Gen}^{H}(r_G)\) and \(\mathsf{sol}' \gets \mathsf{Ext}^{H}(\mathsf{puz})\).

A restriction that must not be lost. The transcription follows the paper’s Definition 2.6 in taking the puzzle \(\mathsf{puz}\) to be classical. The paper itself observes that in a fully quantum setting “one can imagine the puzzle itself to be a quantum object”, so this statement covers quantum algorithms producing a classical puzzle, not the most general reading of “fully quantum”. That is a deliberate scope choice, matching the paper’s own definition and construction, and it should be declared rather than assumed.

Open in the fully quantum case. The other two cells are settled and the obstruction here is conditional rather than speculative.

What is settled. For a classical generator with a quantum solver the paper gives an attack for arbitrary completeness error, and a round-optimal one under perfect completeness. For a quantum generator with a classical solver it gives an attack under perfect completeness.

The barrier. If the paper’s Conjecture 6.1 — a weakening of the folklore Aaronson–Ambainis simulation conjecture — is false, then the paper builds a fully quantum puzzle that no attacker asking only classical queries can break. So any attack settling this statement must itself make quantum queries; a classical-query attack would prove Conjecture 6.1 and thereby a statement about quantum speedups that has been open for a decade.

Why the existing attacks do not extend. They proceed by learning the generator’s heavy queries and simulating the rest, which requires a classical record on one side of the protocol. With both parties quantum there is no such record, and the compressed-oracle machinery that replaces it does not obviously respect the round bound the statement demands.

This is the cell where the quantum question genuinely differs from the classical one. The classical impossibility is unconditional; two of the three quantum cells inherit it; and the fourth is protected by a barrier that says the shape of any proof is constrained — it cannot be a classical-query attack. That is a rare and useful thing to know about an open problem in advance.

The scope restriction on the puzzle is worth taking seriously rather than treating as a technicality. If the puzzle may itself be a quantum state, even the syntax of “the attacker is given the puzzle” changes — the attacker may not be able to copy it — and it is not clear the statement above is the right generalization.

Prove or refute the conjecture for a classical puzzle produced by quantum algorithms.
State and settle the version in which the puzzle itself is a quantum object, which the paper flags and this statement does not cover.
Determine whether the round bound \(\lceil n/\varepsilon \rceil\) is the right target in the fully quantum case, or whether some larger bound is forced.
Settle the quantum-generator classical-solver cell beyond perfect completeness, which the source paper leaves at that hypothesis.
Formalize the statement in Lean. The QROM, round-depth accounting and the puzzle syntax all need writing first.

Afshar, Chung, Hsieh, Lin, and Mahmoody. On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model. Cryptology ePrint Archive, Report 2023/932. Definition 2.6, the two settled cells, Section 6’s barrier and its Conjecture 6.1, and the openness statement this transcribes.
Mahmoody, Moran, and Vadhan. Time-lock puzzles in the random oracle model. CRYPTO 2011, pp. 39–50. The classical impossibility and the pseudo-chain lower bound on rounds.
Boneh, Dagdelen, Fischlin, Lehmann, Schaffner, and Zhandry. Random oracles in a quantum world. ASIACRYPT 2011, pp. 41–69. Where superposition access to the oracle is introduced.
Rivest, Shamir, and Wagner. Time-lock puzzles and timed-release crypto. Technical memo, MIT Laboratory for Computer Science, 1996. The primitive itself; cited as the unpublished memo it is.