⚛️ quantum physics

Quantum Key Exchange from Public Quantum Money

This paper establishes the first complete characterization of two-message quantum key exchange (2QKE) by proving its equivalence to efficiently-verifiable state puzzles and one-time secure digital signatures, thereby demonstrating that 2QKE can potentially be constructed from assumptions weaker than one-way functions while also providing new lower bounds for public-key unclonable primitives and enabling quantum public-key encryption with a novel "certified freeze" functionality.

Original author: Eli Goldin, Tomoyuki Morimae

Published 2026-11-05

📖 4 min read🧠 Deep dive

CC BY 4.0

Original author: Eli Goldin, Tomoyuki Morimae

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of secure communication, two people who have never met before often need to agree on a secret code to protect their messages. For decades, the most reliable way to do this relied on mathematical problems that are easy to solve in one direction but incredibly hard to reverse, like multiplying two massive prime numbers together. This approach, known as public-key cryptography, has protected the internet for years. However, the rise of quantum computers threatens to break these mathematical locks, forcing scientists to look for new foundations. One promising alternative relies on the laws of physics themselves, specifically the fact that quantum information cannot be perfectly copied. This principle allows for the creation of "quantum money," where a banknote is a unique quantum state that anyone can verify but no one can duplicate. While researchers have long known how to build secure communication using these physical laws, they have struggled to do so efficiently. The most efficient methods, which require only two messages to be exchanged, have traditionally depended on the same hard mathematical problems that quantum computers might eventually defeat.

A team of researchers has now mapped out the entire landscape of these two-message quantum exchanges, revealing a surprising connection between them and a different kind of cryptographic tool. They discovered that the ability to exchange a secret key in just two messages is mathematically equivalent to the ability to create a specific type of puzzle. In this puzzle, a sender creates a classical description of a problem and a corresponding quantum state that solves it. The receiver can easily check if a given quantum state is the correct answer, but a hacker who only sees the problem description cannot generate a valid answer. The researchers proved that if you can build one of these systems, you can build the other, and vice versa. This equivalence is a major breakthrough because it shows that the two-message quantum key exchange does not necessarily require the heavy mathematical assumptions that were previously thought to be essential. Instead, it can be built from these quantum puzzles, which might exist even if the hard mathematical problems do not.

The implications of this finding are profound for the future of secure communication. The researchers showed that if these quantum puzzles exist, then a two-message key exchange is possible, and it comes with a powerful bonus: it remains secure even against an attacker who has unlimited computing power and time, provided the attacker was limited to standard quantum capabilities during the actual exchange. This "everlasting security" means that even if a hacker records the encrypted conversation today and waits decades for a supercomputer to arrive, they still cannot crack the code. Furthermore, the team demonstrated that these puzzles can be constructed from other quantum tools, such as digital signatures that work only once. This creates a new, lower threshold for what is needed to build secure systems, suggesting that the requirements for quantum key exchange are weaker than previously believed.

The paper also addresses a practical limitation in previous designs. Earlier attempts at two-message exchanges often required the sender to keep a quantum memory to store delicate states, which is technologically difficult to maintain. The new construction allows the sender to keep only classical information between steps, making the system much more feasible for real-world implementation. Additionally, the researchers extended this work to show how to build a quantum public-key encryption system that includes a "certified freeze" feature. This allows a user to publish a certificate proving they have stopped generating new keys, ensuring that no one can create more than a specific number of distinct valid ciphertexts under that key. This adds a layer of accountability and control that was previously missing from such systems.

By establishing these equivalences, the researchers have clarified the fundamental limits of quantum cryptography. They have shown that the ability to exchange keys in two messages is not an isolated miracle but is deeply tied to the existence of quantum puzzles and one-time signatures. This work suggests that the path to ultra-secure, efficient communication might be shorter than expected, relying on assumptions that are potentially weaker than those currently used to protect the global economy. The findings do not just offer a new protocol; they provide a complete characterization of what is possible, proving that the security of these systems is robust and that the most stringent security guarantees come naturally, without extra cost.

Technical Summary: Quantum Key Exchange from Public Quantum Money

1. Problem Statement

The paper addresses the fundamental question of the minimal computational assumptions required to construct Two-Message Quantum Key Exchange (2QKE).

In the classical setting, 2-message key exchange is impossible without structured public-key assumptions (Cryptomania), as it cannot be built from One-Way Functions (OWFs) alone. In the quantum setting, while the BB84 protocol offers information-theoretic security, it requires more than two messages. It has been established that statistically secure 2QKE is impossible, necessitating computational assumptions.

Prior to this work, the weakest known assumption for 2QKE was the existence of One-Way Functions (OWFs). Malavolta and Walter (2024) and Kitagawa et al. (2024) demonstrated constructions of 2QKE (and Quantum Public-Key Encryption with quantum public keys, QPKE) based solely on OWFs. However, recent developments in quantum cryptography suggest that many primitives (e.g., commitments, oblivious transfer) can be based on assumptions potentially weaker than or incomparable to OWFs (such as Pseudorandom States, One-Way Puzzles, or EFI pairs).

The central open problem is: Can 2QKE be constructed from an assumption weaker than OWFs? Furthermore, can Quantum Public-Key Encryption (QPKE) with quantum public keys be constructed from such weaker assumptions?

2. Methodology and Technical Approach

The authors provide a complete characterization of 2QKE by establishing an existential equivalence between four distinct cryptographic primitives. Their methodology involves constructing a cycle of reductions:

From One-Time Secure Digital Signatures (with Quantum Signatures) to Everlasting-Secure 2QKE:
- The authors adapt the "coherent verification" technique used in previous OWF-based constructions but modify it to handle quantum signatures.
- In standard signature schemes, Alice can generate a superposition of signatures. However, with quantum signatures, the signing algorithm may be non-deterministic or output mixed states.
- Key Innovation: To resolve the issue of generating a superposition of two quantum signatures ( $|0\rangle|\sigma(0)\rangle + |1\rangle|\sigma(1)\rangle$ ) and recovering the key, the authors introduce a protocol where Alice generates two signatures, applies a controlled-SWAP to create a superposition, and masks the state with a random Pauli operator. This allows Alice to recover the key bit after Bob's interaction without needing to know the specific randomization applied by the signing algorithm.
- The security proof relies on the one-time security of the signature scheme. Unlike previous proofs that relied on "strong existential unforgeability" (which is ill-defined for quantum signatures), this proof uses a "cross-term" argument. It shows that if an adversary can distinguish the keys, they must be able to forge a signature for a message they did not query, contradicting the one-time security.
From 2QKE to Efficiently-Verifiable State Puzzles (EV-StatePuzzs):
- The authors show that any 2QKE protocol can be transformed into an EV-StatePuzzle.
- Construction: The puzzle generator ($Samp$) simulates Alice's first phase of the 2QKE, outputting the classical message as the "puzzle" and the quantum state (held by Alice) as the "answer." The verifier ($Ver$) simulates Bob's interaction and Alice's second phase.
- Security: If an adversary can solve the puzzle (make $Ver$ accept), they can effectively break the 2QKE security by acting as a malicious Bob who learns the key.
- This establishes that 2QKE is no harder than EV-StatePuzzs.
From EV-StatePuzzs to One-Time Secure Digital Signatures:
- The authors construct a quantum analogue of Lamport signatures using EV-StatePuzzs.
- Construction: The verification key consists of two puzzles ( $s_0, s_1$ ). The signing key consists of the corresponding answer states ( $\psi_0, \psi_1$ ). To sign a bit $b$ , the sender reveals $\psi_b$ . Verification checks if $\psi_b$ solves $s_b$ .
- Security: A forgery of a signature for the unqueried bit implies solving the corresponding puzzle, which contradicts the security of the EV-StatePuzzle.
From One-Shot Signatures (OSS) to QPKE with Certified Freeze:
- The authors construct a QPKE scheme from One-Shot Signatures (OSS). OSS are signature schemes where a signing key can sign only one message, and the signatures are classical.
- Challenge: Standard QPKE requires many-time signatures to generate multiple public keys. OSS are "one-time."
- Solution: The authors employ a certificate chain technique. The $t$ -th public key generation signs the $(t+1)$ -th verification key. Since the signatures are classical, they can be copied and included in subsequent public keys.
- Certified Freeze: A novel functionality is introduced where the receiver can publish a classical certificate proving they have "frozen" the system, binding them to a specific upper bound on the number of valid ciphertexts. This is achieved by signing a special "stop" message with the final unused signing key.

3. Key Contributions and Results

The paper establishes the following main theorems and corollaries:

Theorem 1.1 (Equivalence): The following four primitives are existentially equivalent:
1. Everlasting-secure 2QKE.
2. Standard 2QKE.
3. Efficiently-verifiable state puzzles (EV-StatePuzzs).
4. One-time secure digital signatures with quantum signatures and signing keys.
Implication for Assumption Strength: Since EV-StatePuzzs (and related primitives like Pseudorandom States) are potentially weaker than OWFs (they can exist even if $P=NP$ relative to a classical oracle), 2QKE is potentially weaker than OWFs. This provides the first complete characterization of 2QKE.
Corollary 1.3 (Free Everlasting Security): If 2QKE exists, then everlasting-secure 2QKE exists. This means that achieving security against computationally unbounded adversaries after the protocol terminates comes "for free" in the 2-message setting; no additional assumptions are needed beyond those required for standard 2QKE.
Corollary 1.4 (No Quantum Memory for Alice): The constructed 2QKE allows Alice to operate with no quantum memory between her first and second phases; her internal state can be entirely classical.
Theorem 1.8 (QPKE from OSS): If One-Shot Signatures exist, then everlasting-secure QPKE with quantum public keys exists.
- Since OSS are believed to be incomparable to OWFs, this suggests QPKE can be built from assumptions weaker than or incomparable to OWFs.
- The construction includes Certified Freeze, allowing the receiver to publicly verify a bound on the number of ciphertexts they can decrypt.
Lower Bounds: The results imply that One-Shot Signatures, Quantum Lightning, and Public-Key Quantum Money mini-schemes imply EV-StatePuzzs, and thus imply everlasting-secure 2QKE. This provides a new, non-trivial lower bound for these unclonable primitives.

4. Significance and Claims

The paper claims to provide the first complete characterization of the computational assumptions required for 2QKE. By linking 2QKE to EV-StatePuzzs and One-Time Signatures with quantum signatures, the authors demonstrate that 2QKE does not necessarily require the full power of OWFs.

Key claims regarding the significance of the work include:

Minicrypt/Microcrypt Descent: The results suggest that 2QKE and QPKE can potentially be moved from "Cryptomania" (requiring OWFs) down to "Minicrypt" or even "Microcrypt" (based on weaker assumptions like EV-StatePuzzs or OSS).
Everlasting Security: The equivalence between standard and everlasting 2QKE is a significant structural result, showing that the stronger security notion is not strictly harder to achieve.
Certified Freeze: The introduction of the "certified freeze" functionality in QPKE is a novel contribution, offering a mechanism for receivers to publicly commit to a limit on their decryption capacity, which has not been previously defined in this context.

The authors remain modest about the tightness of the lower bounds. They explicitly state that showing 2QKE implies Public-Key Quantum Money mini-schemes would be very hard (as it would imply OWFs imply such money), and thus the equivalence between 2QKE and these unclonable primitives is not yet proven to be bidirectional.

5. Limitations and Open Problems

Classical Bob Message: The constructed 2QKE requires Bob to send a quantum state back to Alice. It remains an open problem whether 2QKE with a classical message from Bob can be constructed from assumptions weaker than OWFs.
Security for Alice: In the basic 2QKE construction, Eve can learn Alice's key or force a mismatch between Alice's and Bob's keys. The paper addresses this in Section 7 by adding a short classical tag (using an AMD code), but this requires an additional round of classical communication or specific protocol modifications.
Many-Time Signatures from EV-StatePuzzs: The authors note that they do not know how to construct many-time secure digital signatures from EV-StatePuzzs. Consequently, constructing standard QPKE (where a single public key encrypts many messages) from EV-StatePuzzs remains open. Their QPKE construction relies on OSS and is stateful (the secret key grows or changes with use).