Quantum puzzles unlock time delays impossible classically
Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
Cryptography and Security
Summary
Some puzzles hide messages so you can only solve them after a certain amount of time and computing effort, no matter how many computers you use. Classical versions can’t guarantee this kind of time delay securely. The authors create a new kind of puzzle using quantum information that does guarantee a set time to solve, even for powerful quantum computers. This solves a long-standing problem by showing how to securely delay access to information using quantum puzzles.
What this means in practice
- •For cryptography engineers: Protect messages to be securely revealed only after a fixed delay even against quantum attacks.
- •For blockchain developers: Design fair time-dependent protocols like auctions or contract signing resilient to quantum adversaries.
A theory result. No direct application yet.
Authors
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).