CS Paper Radar

Quantum Key Exchange from Public Quantum Money

Eli Goldin, Tomoyuki Morimae

cs.CR quant-ph ·submitted 2026-11-04 05:32 UTC · v1
theory

Abstract

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.

Comment
43 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

cs.CR quant-ph ·2026-09-30 ·Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu
similarity 0.72
Abstract

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.

0.26

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

cs.CR quant-ph ·2026-09-10 ·Atul Mantri
similarity 0.72
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.42

Succinct Arguments for QMA from Collapsing Hash Functions

cs.CR quant-ph ·2026-09-28 ·James Bartusek, Giulio Malavolta
theoryhot direction similarity 0.71
Abstract

We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.

0.24

Anchoring the Security of Invariant Quantum Money

cs.CR ·2026-09-30 ·Hans Schmiedel, Jiangshan Yu
hot direction similarity 0.71
Abstract

Prior studies on quantum money from knots, and the invariant money framework that generalizes it, anchor their security on the hardness of path-finding. However, we show that the hardness of path-finding is proven to be necessary for security under certain conditions. In other conditions, this assumption is not a direct anchoring hardness problem such that breaking it allows an adversary to forge a banknote directly. In particular, for quantum money from knots, even when the path-finding assumption does not hold, an adversary still cannot directly forge a banknote. The adversary needs to additionally prepare the uniform superposition over the paths it finds, which we show is as hard as the original problem. Existing security proofs supplement path-finding hardness with knowledge-of-path assumptions. While this combination is sufficient, it may not be necessary. We identify an assumption pair, preparation assumption and transfer assumption, that is both necessary and sufficient for the security of every invariant money scheme. Breaking either assumption directly enables a forgery. The preparation assumption says that no efficient algorithm, given the serial number of a banknote and one object measured from it, prepares a state that verification accepts. While quantum money security gives a forger one quantum state and asks for two that pass, our assumption concerns a problem that takes only classical inputs and asks for one quantum state that passes. This assumption is equivalent to security against forgers that measure their banknote first. Given that its inputs are classical, it is falsifiable and can be attacked and bounded like other computational problems. The transfer assumption covers forgers that keep the banknote coherent, stating that every such forger only has an advantage over the measure-first adversary by at most a polynomial factor.

0.35

On the Construction of Trapdoor Claw-Free Functions with Certifiable Key

cs.CR quant-ph ·2026-09-22 ·Charles Lim, Yao Ma
similarity 0.70
Abstract

Trapdoor claw-free functions (TCFs) underpin much of classical-quantum cryptographic interaction, yet every TCF-based protocol states its guarantees relative to an honestly generated key. We give a family-agnostic abstraction of key certification for (noisy) TCF constructions, built on two notions: a certifiable key relation, an NP relation capturing a family's honest keys with witnesses recoverable from the trapdoor; and certified key generation, which emits with each key a certificate of membership satisfying completeness, certificate soundness with extractability, and key privacy. We instantiate certifiable key relations for different constructions, each met generically by a zero-knowledge argument of knowledge for the relation. As our main application, a generic compiler turns any TCF-based proof of quantumness into a zero-knowledge one, with each security property following from its counterpart in the certification scheme. Finally, we delimit the primitive's reach: for protocols resting on injective invariance, an accepting certificate is itself a family distinguisher, leaking exactly the bit such protocols must hide.

0.24

PQ-Vault: Provably Quantum-Safe Asset Custody for Unmodified Ethereum

cs.CR quant-phcs.DCcs.IT ·2026-10-21 ·Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng
theory similarity 0.69
Abstract · 14 pages + 11 pages of appendices

A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules unchanged can protect such accounts: their funds must move into a contract whose release condition relies only on quantum-safe primitives. We design \emph{PQ-Vault}, a custody system for unmodified Ethereum combining this vault, a quantum-safe proof-of-stake sidechain whose checkpoints carry compact certificates, and an optimistic dispute protocol. We give the first security proof of compact certificates against quantum attackers and a matching attack: with classically chosen parameters, the guarantee falls from 128 to about 60 bits, and a simple rule restores it. We show that a common seed-update rule in hash-chain proof of stake lets an attacker steer chosen slots and profit from splitting its stake, and give an election whose steering gain and inclusion delay are provably bounded against quantum attackers. Since compressing certificates with a pairing-based SNARK breaks quantum security, we use fraud proofs that need a single signature check. For 65,536 validators, a certificate is 0.8 MB, 260 times smaller than all signatures, and verifies in about 20 ms; the vault accepts a checkpoint for about 420,000 gas.

0.17

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

Statistically-Secure Bit Commitment and Coin Flipping Protocols Based on Quantum Hardware Assumptions

cs.CR quant-ph ·2026-08-11 ·Roo Dunnill, Mina Doosti
theory similarity 0.69
Abstract · 21 pages, 0 figures

Bit commitment is impossible to achieve with unconditional security, even in quantum cryptogra- phy. We show that statistically secure bit commitment, satisfying both hiding and binding, can be constructed from hybrid locked physical unclonable functions (HLPUFs), a hardware primitive that combines classical hardware tokens and quantum communication. Our protocol uses these hardware assumptions in a novel and non-trivial way to achieve the first mistrustful two-party cryptographic protocol based on hybrid hardware modules. We prove statistical hiding and binding under natu- ral assumptions on the HLPUF and using a carefully designed challenge generation algorithm as a subroutine of our bit-commitment protocol. The construction also yields the first hardware-based coin-flipping protocol. Our results suggest a new paradigm for secure two-party cryptography in quantum networks, combining rigorous security guarantees with a concrete route toward practical implementation.

0.10