Paper 2023/932
On the (Im)possibility of TimeLock Puzzles in the Quantum Random Oracle Model
Abstract
Timelock puzzles wrap a solution $\mathrm{s}$ inside a puzzle $\mathrm{P}$ in such a way that ``solving'' $\mathrm{P}$ to find $\mathrm{s}$ requires significantly more time than generating the pair $(\mathrm{s},\mathrm{P})$, even if the adversary has access to parallel computing; hence it can be thought of as sending a message $\mathrm{s}$ to the future. It is known [Mahmoody, Moran, Vadhan, Crypto'11] that when the source of hardness is only a random oracle, then any puzzle generator with $n$ queries can be (efficiently) broken by an adversary in $O(n)$ rounds of queries to the oracle. In this work, we revisit timelock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of timelock puzzles solely from quantum (accessible) random oracles. In particular, for any $n$query classical puzzle generator, our attack only asks $O(n)$ (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing. Assuming perfect completeness, we also show how to make the above attack run in exactly $n$ rounds while asking a total of $m\cdot n$ queries where $m$ is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask $n1$ rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from $\Omega(mn \log n)$ to $mn$. Finally, assuming perfect completeness, we present an attack in the ``dual'' setting in which the puzzle generator is quantum while the solver is classical. We then ask whether one can extend our classicalquery attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv'2009] is false, then there is indeed a timelock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto'22] about key agreements (that can have interactions in both directions) to timelock puzzles (that only include unidirectional communication).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 timelock puzzlequantum cryptographyblackbox separations
 Contact author(s)

na6xg @ virginia edu
kmchung @ iis sinica edu tw
ychsieh @ cs washington edu
yaoting_lin @ ucsb edu
mohammad @ virginia edu  History
 20230615: approved
 20230614: received
 See all versions
 Short URL
 https://ia.cr/2023/932
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/932, author = {Abtin Afshar and KaiMin Chung and YaoChing Hsieh and YaoTing Lin and Mohammad Mahmoody}, title = {On the (Im)possibility of TimeLock Puzzles in the Quantum Random Oracle Model}, howpublished = {Cryptology ePrint Archive, Paper 2023/932}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/932}}, url = {https://eprint.iacr.org/2023/932} }