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

quant-pharXiv:2609.38894Oct 1, 20260 citations

Quantum permutation puzzles with indistinguishable particles

Noah Lordi, Maedée Trank-Greene, Akira Kyle +1 more

Permutation puzzles, such as the Rubik's Cube and the 15 puzzle, are enjoyed by the general public and mathematicians alike. Here we introduce quantum versions of permutation puzzles where the pieces of the puzzles are replaced with indistinguishable quantum particles. The moves in the puzzle are achieved by swapping or permuting the particles. We show that simply permuting the particles can be mapped to a classical permutation puzzle, even though the identical particles are entangled. However, we obtain a genuine quantum puzzle by adding a quantum move: the square root of swap. The resulting puzzle cannot be mapped to a classical permutation puzzle. We focus predominately on the quantization of the $2\ifmmode\times\else\texttimes\fi{}2$ slide puzzle and briefly treat the $2\ifmmode\times\else\texttimes\fi{}2\ifmmode\times\else\texttimes\fi{}1$ Rubik's Cube.Permutation puzzles, such as the Rubik's Cube and the 15 puzzle, are enjoyed by the general public and mathematicians alike. Here we introduce quantum versions of permutation puzzles where the pieces of the puzzles are replaced with indistinguishable quantum particles. The moves in the puzzle are achieved by swapping or permuting the particles. We show that simply permuting the particles can be mapped to a classical permutation puzzle, even though the identical particles are entangled. However, we obtain a genuine quantum puzzle by adding a quantum move: the square root of swap. The resulting puzzle cannot be mapped to a classical permutation puzzle. We focus predominately on the quantization of the $2\ifmmode\times\else\texttimes\fi{}2$ slide puzzle and briefly treat the $2\ifmmode\times\else\texttimes\fi{}2\ifmmode\times\else\texttimes\fi{}1$ Rubik's Cube.

arXiv:2410.22287Physical Review AApr 14, 20252 citations

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