PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Prabhanjan Ananth, Yao-Ting Lin

arXiv:2609.38894v1quant-phcs.CR

TL;DR

In the classical random oracle model, time-lock puzzles cannot achieve the required gap between puzzle generation and sequential solving, while the quantum-honest-party case remained open. The construction makes the puzzle a quantum state and measures QROM delay in parallel oracle-query rounds. Generation takes poly(λ, log T), solving uses at most T oracle rounds, and adversaries using r=o(T) rounds have success probability o(1).

  • Problem

    In the classical random oracle model, time-lock puzzles cannot achieve the required gap between puzzle generation and sequential solving, while the quantum-honest-party case remained open.

    Source: §1 · p. 2

  • Method

    The construction makes the puzzle a quantum state and measures QROM delay in parallel oracle-query rounds.

    Source: §1 · p. 2

  • Results

    Generation takes poly(λ, log T), solving uses at most T oracle rounds, and adversaries using r=o(T) rounds have success probability o(1).

    Source: §1.2 · pp. 7–8

  • Takeaways & Limitations

    The puzzle is generated in time poly(λ, log T), solved honestly in at most T oracle rounds, and has success probability o(1) against adversaries using r=o(T) rounds.

    Source: §1.2 · pp. 7–8

    The guarantee is round-based in the QROM, for polynomially bounded T and adversaries making r=o(T) parallel-query rounds.

    Source: §1 · p. 2

Abstract

from arXiv · show

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(\lambda)$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).

1 Introduction

This section introduces quantum time-lock puzzles as a response to classical random-oracle impossibility and presents a QROM construction with correctness and security intuition. It outlines how one-wayness across independent quantum-token instances supports indistinguishability security for the solution bit, with poly(λ, log T) generation time and at most T oracle rounds for honest solving.

1 Introduction

  • Classical random-oracle TLPs cannot provide the required generation–solving gap, leaving open whether the impossibility extends to quantum honest parties.TLPs support applications including timed-release encryption, fair contract signing, electronic voting, coin flipping, auctions, and Byzantine consensus.Source: §1 · pp. 1–2

1.1 Our Results

  • The QROM scheme generates puzzles in poly(λ, log T) time with λ+1 classical queries in one round, solves in at most T oracle rounds, and targets security against r=o(T) polynomial-parallel queries.The simple instantiation contains O(λ^2 log T) single-qubit BB84 states and λ^2+1 classical bits; solving has negligible correctness error.Source: §1.1 · p. 3
  • Quantum puzzles address attacks that rely on rerunning a solver on the same classical puzzle: the adversary receives one quantum-puzzle copy, while generation uses only classical oracle queries.The construction uses a product of single-qubit BB84 states and random oracles.Source: §1.1 · pp. 2–3

1.2 Technical Overview

  • In the classical approach, publishing G(a) for random a∈[T] enables sequential search, but a polynomial-width adversary can copy the puzzle and test all candidates in one round.The overview motivates a puzzle whose use in one search cannot be replicated across many independent searches.Source: §1.2 · p. 3
  • The quantum solver searches over candidate bases, using a hash tag to verify candidates and exact Grover search to recover the hidden pair (a, x) with negligible error.Verification approximately restores the puzzle after incorrect candidates, and the exact-search variant avoids inverse-polynomial success error; the solver uses O(T) rounds.Source: §1.2 · pp. 4–5
  • Security combines a list-one-wayness bound from incompatible quantum bases with round-by-round oracle reprogramming to require Ω(T) rounds for constant-probability recovery.The overview applies the list bound to polynomially many parallel queries and uses hybrids differing at the hidden pair’s oracle input.Source: §1.2 · pp. 6–7
  • For r = o(T), the single-instance success probability is o(1), and interactive parallel repetition makes recovery of the full λ-instance tuple negligible.For N ≥ 4, the individual success bound is at most 1/2 for sufficiently large λ; the product bound follows from Gutoski’s interactive repetition theorem [Gut09, Theorem 4.9].Source: §1.2 · p. 7
  • The one-wayness bound yields indistinguishability security: an adversary distinguishing the oracle-derived mask must query the hidden tuple enough to recover it, contradicting amplified one-wayness.The construction uses an independent random oracle F for the solution-bit mask; the parallel-query formulation uses the same oracle-hybrid argument.Source: §1.2 · p. 8
  • The puzzle uses λ tokens, has λn = O(λ^2 log T) qubits and λ^2 + 1 classical bits, and supports generation in poly(λ, log T) time and honest solving in poly(λ, T) time using at most T oracle rounds.The T-round count includes the final mask query.Source: §1.2 · p. 8
  • Codeword-indexed BB84 product states meet the overlap condition: distinct codewords differ in at least λ positions, giving cross-basis overlaps at most 2^(-λ/2), while same-basis states with different x-labels are orthogonal.The token length is n = λk = O(λ log T). Code-selected BB84 bases also appear in [FS17, Section 4.1].Source: §1.2 · p. 8
  • The overview situates the construction against classical random-oracle impossibility and QROM impossibility when either generator or solver is classical.Hidden-basis encodings were studied for quantum key uncertainty, and binary linear codes with BB84 states were used for quantum authentication and key recycling [FS17, Section 4.1].Source: §1.2 · p. 8

2 Preliminaries

The preliminaries fix the notation and delay range, define quantum time-lock puzzles and their QROM query-round model, and introduce binary-code BB84 encodings and exact Grover search.

2 Preliminaries

  • The notation sets λ as the security parameter and [m]={1,…,m}.Throughout, delays T are polynomially bounded integers satisfying T=ω(1).Source: §2 · p. 9, §2.2 · p. 9

2.1 Quantum Random Oracle Model

  • A QROM query round is one round of parallel oracle queries, with r denoting rounds and p the number of parallel queries per round.When multiple oracles are available, superposition queries across them are not allowed.Source: §2.1 · p. 9

2.2 Quantum Time-Lock Puzzles in the QROM

  • A QTLP is a pair of quantum oracle algorithms: PGen outputs a puzzle state and PSolve returns a solution bit or abort.The model considers polynomially bounded integer delays T=ω(1); efficiency requires solving in at most T query rounds, while security covers possibly unbounded adversaries using r=o(T) rounds of p-parallel queries.Source: §2.2 · p. 9

2.3 BB84 Encodings from Binary Codes

  • For a binary codeword x, Ux applies a Hadamard gate at coordinates whose bits are 1, and code distance d yields overlap bound ε=2^-d/2.The code is introduced as an [n,k,d]-code, a k-dimensional subspace of F^n.Source: §2.3 · p. 10

2.4 Exact Grover Search

  • Exact Grover search rounds up the iteration count and lowers the initial marked amplitude so g iterations recover the marked element with probability 1.Choosing θ=π/(4g+2) ensures (2g+1)θ=π/2.Source: §2.4 · p. 10

3 Construction

The construction prepares independent encoded quantum tokens and oracle-derived tags, then uses exact search to recover candidate inputs. Its stated efficiency bounds give one-round generation and solving within T oracle rounds.

3 Construction

  • The construction sets k=2⌊log2(T+1)⌋−2, n=λk, and code distance d=λ using an efficiently encoded [n,k,d]-code.The repetition encoder yields an [λk,k,λ]-code.Source: §3 · p. 11
  • The generator samples independent (ai,xi) pairs, prepares one token per instance, and computes tags zi=Hi,λ(ai,xi) plus mask msk=F(a1,x1,…,aλ,xλ) in one parallel round.The puzzle holds the λ-bit tags, n-qubit tokens, and masked bit.Source: §3 · p. 11
  • For each instance, the solver reflects on candidate labels whose token matches the tag, interleaving that reflection with reflection about the initial search state.The tag-matching reflection coherently computes Hi(a,x), flips phase on a match, uncomputes the oracle answer, and applies the candidate-controlled unitary.Source: §3 · p. 12
  • After search, the solver measures candidate labels and token registers, then queries F on the recovered pairs to obtain the masked solution.The search aborts if any candidate measurement yields the dummy label ⊥.Source: §3 · p. 12
  • The code choice gives ε=2^-λ/2, making pε negligible for every polynomial query width p, and the λ tokens contain O(λ² log T) qubits.Each token has n=λk qubits.Source: §3 · p. 12
  • Generation takes poly(λ, log T) time with λ+1 classical oracle calls in one round, while solving takes poly(λ,T) time in at most T rounds with at most λ calls per round.Approximating non-oracle gates over a fixed finite universal gate set adds at most 2^-λ to failure probability without changing oracle depth.Source: §3 · p. 12

4 Proof of Correctness

The proof establishes correctness by comparing the implemented solver with an ideal search that recovers each hidden pair exactly. Random-oracle and finite-gate errors leave the actual solver with negligible failure probability for polynomially bounded delays.

4 Proof of Correctness

  • The ideal solver recovers each hidden pair with certainty, so its final query to F recovers the mask and outputs the solution bit.When g = 0, correctness is perfect directly; for g ≥ 1, the ideal search measures the correct label and decoding yields the token’s x value.Source: §4 · pp. 13–14
  • The proof compares the actual reflection-based search with the ideal search through a state-distance bound, then uses that bound to control failure probability.The ideal solver uses the same initialization and final decoding as PSolve, but replaces its implemented reflection with the ideal reflection.Source: §4 · pp. 13, 14, 16
  • For each token, the random-oracle probability of failing to recover its hidden pair is at most (2^k − 1)/2^λ; a union bound covers all λ tokens.Recovering every pair makes the solver query F on the generator’s tuple and recover s.Source: §4 · p. 16
  • The finite-gate solver succeeds with probability at least 1 − negl(λ), counting aborts as failures.The finite-gate implementation adds at most 2^-λ to the failure probability, and correctness holds for every solution bit.Source: §4 · p. 16

5 Proof of Security

The security proof develops bounds for identifying hidden pairs from quantum states and random-oracle tags, then applies them to the puzzle’s distinguishing game. For polynomial query width and r = o(T) rounds, the theorem establishes the stated security bound and the proof shows it is negligible.

5.1 Useful Lemmata

  • The list-one-wayness lemma bounds recovery when an adversary receives one encoded hidden pair and outputs up to p candidate pairs, under a pairwise-overlap condition.The proof represents the output as a set of at most p distinct pairs and bounds the adversary’s winning probability.Source: §5.1 · pp. 17–18
  • The QROM list-recovery argument gradually decouples the tag from the oracle, bounding each hybrid hop by the chance a query addresses the hidden pair.The terminal experiment makes the tag and oracle independent of the hidden pair; the same argument extends to λ copies even for a joint quantum adversary.Source: §5.1 · p. 20
  • Parallel repetition bounds success across λ independent challenge copies by the single-copy bound raised to λ, even when the adversary jointly entangles the copies.The repeated verifier accepts only if every copy accepts.Source: §5.1 · p. 20

5.2 Security Proof

  • For polynomial query width and r = o(T) rounds, the security theorem bounds an adversary’s success, and the proof establishes that the resulting bound is negligible.The proof decouples the mask from the oracle across hybrids; in the final hybrid the masked bit is uniform from the adversary’s perspective, giving winning probability 1/2.Source: §5.2 · pp. 20–21
Loading 2609.38894v1…