Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 17 min ago
PreprintCC BY 4.0arXiv

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

  • Prabhanjan Ananth
  • Yao-Ting Lin
Open at sourcePDFDOICite

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).

Related

  1. Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity
    Morteza Saberikamarposhti
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Succinct Arguments for QMA in the Quantum Random Oracle Model
    Alessandro Chiesa, Zihan Hu
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
    Boyang Chen, Tianren Liu, Luojian Wei
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. One Gate at a Time: Complexity Growth in Random Quantum Circuits
    Zhi Li
    arXivPreprintarXiv licenceFull textMathematical physicsQuantum physics & quantum informationarXiv
  5. EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
    Atul Mantri
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{ananth2026quantum,
  title = {{Quantum Time-Lock Puzzles in the Quantum Random Oracle Model}},
  author = {Prabhanjan Ananth and Yao-Ting Lin},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38894},
  eprint = {2609.38894},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38894},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
AU  - Prabhanjan Ananth
AU  - Yao-Ting Lin
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38894
UR  - https://arxiv.org/abs/2609.38894
AB  - 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).
ER  -