CS Paper Radar

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Prabhanjan Ananth, Yao-Ting Lin

cs.CR quant-ph ·submitted 2026-09-30 03:41 UTC · v1
hot direction

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

Comment
23 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model

cs.CR quant-ph ·2026-09-26 ·Boyang Chen, Tianren Liu, Luojian Wei
similarity 0.73
Abstract

Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a $λ$-bit message and integer-valued parameters $n=n(λ)$ and $\ell=\ell(λ)$, the construction uses $n\ell$ qubits and $(n+2)λ$ classical bits, and for any quantum adversary with at most $2^{\ell/2-1}-1$ classical queries to the random oracle, its simulation advantage is at most $(n+3)\left(\frac{3}{4}\right)^n.$ Hence exponentially small simulation advantage in $n$.

0.08

EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

cs.CR quant-ph ·2026-09-10 ·Atul Mantri
similarity 0.70
Abstract

EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end. The oracle answers every question about the output probabilities of quantum samplers, which removes the puzzles, and hides a Haar-random half-dimensional subspace. To prove security we reduce it to communication complexity. An adversary whose knowledge of the subspace arrives as classical query answers can be simulated inside a two-party protocol against the party holding it, so it does no better than the best classical protocol for Vector-in-Subspace (Klartag and Regev, STOC 2011), whatever the oracle computes. That argument does not cover the superposition query, which we bound instead using tools from random matrix theory. The same attack gives a classical simulation of any quantum party in a classical-message protocol with no entanglement shared in advance, so relative to the oracle there is no proof of quantumness either. Quantum polynomial time therefore offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable. We state conjectures on removing the restriction on superposition queries.

0.41

Certified Randomness without Structure Against Shallow-Query Adversaries

cs.CR quant-ph ·2026-08-25 ·Dakshita Khurana, Bhaskar Roberts, Avishay Tal
top venuetheory similarity 0.69
Abstract · To be published at FOCS 2026

In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.

0.42

Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM

cs.CR quant-ph ·2026-08-18 ·Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, Takashi Yamakawa
hot direction similarity 0.68
Abstract · 75 pages, 2 figures, 2 tables

We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes $poly(λ)$ queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most $poly(λ)$ and the valid agreement probability is inverse-polynomial. As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.

0.29

Need for Coherent Access in Constructing Quantum Cryptography

cs.CR quant-ph ·2026-09-30 ·Minki Hhan, Changhun Oh, Vaughn Sohn
hot direction similarity 0.68
Abstract

We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.

0.21

Quantum Key Exchange from Public Quantum Money

cs.CR quant-ph ·2026-11-04 ·Eli Goldin, Tomoyuki Morimae
theory similarity 0.67
Abstract · 43 pages, 1 figure

Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs). Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys. [Kitagawa, Morimae,Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.

0.31

Optimal and Verifiable Quantum Advantages in Communication Complexity

cs.CC quant-ph ·2026-10-04 ·Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
hot direction similarity 0.66
Abstract · 65 pages

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

0.47

On The Simplest Quantum-Secure Block Cipher

cs.CR quant-ph ·2026-09-30 ·Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat
similarity 0.66
Abstract

Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.

0.23