⚛️ quantum physics

Eavesdropper-Blind Remote State Preparation and Applications to Quantum Public-Key Encryption

This paper introduces eavesdropper-blind remote state preparation (EB-RSP), a weaker variant of remote state preparation that ensures security only against external observers rather than the quantum server, and demonstrates its sufficiency for constructing quantum public-key encryption with classical public keys while providing new constructions based on one-way group actions and showing the adaptability of existing trapdoor-based schemes.

Original authors: Kaniuar Bacho, Alexandru Cojocaru

Published 2026-08-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kaniuar Bacho, Alexandru Cojocaru

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 authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the emerging field of quantum cryptography, researchers are trying to solve a fundamental mismatch: how can a person using a standard, classical computer talk to a powerful quantum machine without sending it a quantum signal? This is the central challenge of a model known as quantum computation with classical communication. The goal is to let a classical user, who has no quantum hardware, instruct a remote quantum server to prepare a specific quantum state—a delicate configuration of information that exists in a superposition of possibilities. To do this, the user must send only ordinary digital messages, yet the server must end up holding a quantum state that the user knows exactly what it is, while the server itself learns nothing about it. This concept, called remote state preparation, has been a cornerstone for many advanced protocols, including ways to verify that a computer is truly quantum or to encrypt data in new ways. However, building these systems has historically required very strong and complex mathematical assumptions, often relying on secret "trapdoors" that allow the user to reverse-engineer the process.

A team of researchers has now proposed a new, slightly weaker version of this process that still works for important tasks but relies on much simpler mathematical foundations. They call this new method "eavesdropper-blind" remote state preparation. The shift in thinking is subtle but significant. In the traditional, stricter version of the protocol, the system had to remain secret even from the quantum server itself, which was acting as a potentially dishonest participant. The new approach relaxes this requirement. It only demands that the protocol remains secret from an outside observer who is listening in on the conversation between the user and the server. The server is allowed to know the final state, but a third party listening to the exchange must learn nothing. The researchers found that this relaxed security model is actually strong enough to build a secure way of sending encrypted messages using a public key that is purely classical, even though the encrypted message itself is a quantum object.

To achieve this, the researchers moved away from the complex "trapdoor" functions that previous methods depended on. Instead, they utilized the mathematical properties of group actions, which are ways of transforming objects within a set according to specific rules. Imagine a lock where the key is not a secret mechanism hidden inside, but rather the shape of the keyhole itself; the researchers used the inherent structure of these mathematical transformations to cancel out unknown variables. In their protocol, the classical user sends a few digital messages to the quantum server. The server performs a series of quantum operations, measures parts of its system, and sends the results back. Through the algebraic nature of the group actions, the server ends up with a specific quantum state, and the user can calculate exactly what that state is, all without the user needing a secret key to reverse a difficult mathematical problem. Crucially, the server learns the state, but an eavesdropper listening to the messages cannot distinguish the state from random noise.

The paper demonstrates that this new method can be built from "one-way group actions," a type of mathematical assumption that is distinct from the trapdoor functions used in most current quantum cryptography. This is a significant step because it suggests that the building blocks for quantum security might be more diverse than previously thought. The researchers showed that their two-message protocol is sufficient to construct a quantum public-key encryption scheme. In this scheme, a user can generate a public key that is just a string of classical numbers, share it with anyone, and allow them to encrypt a message into a quantum state. Only the holder of the corresponding secret key can decrypt it. While previous work had shown how to do this with quantum public keys or required stronger assumptions, this work proves that classical public keys are possible using these simpler, trapdoor-free foundations.

The researchers also noted that their findings might apply to existing systems. They observed that several known protocols, which were originally designed with the stricter security requirements in mind, could likely be adapted to fit this new, weaker definition without losing their security. This implies that the ability to build these encryption systems might already exist within current cryptographic frameworks, just waiting to be viewed through this new lens. By proving that a less demanding form of remote state preparation is sufficient for real-world applications like encryption, the work opens a path toward quantum cryptographic tools that are built on a wider variety of mathematical assumptions, potentially making them more robust and easier to implement in the future. The study does not claim to have solved every problem in the field, nor does it suggest that the stricter, server-blind versions are unnecessary for all tasks. Instead, it establishes a clear, practical middle ground where simpler mathematics can still power complex quantum security.

Technical Summary: Eavesdropper-Blind Remote State Preparation and Applications to Quantum Public-Key Encryption

1. Problem Statement

Remote State Preparation (RSP) is a fundamental primitive in quantum cryptography, enabling a classical client to instruct a quantum server to prepare a specific quantum state using only classical communication. Existing RSP constructions are central to the Quantum-Computation Classical-Communication (QCCC) model, supporting applications such as delegated computation, proofs of quantumness, and quantum public-key encryption (QPKE).

However, current RSP protocols face two significant limitations:

Strong Assumptions: All known constructions rely on "trapdoor" cryptographic primitives, most notably Trapdoor Claw-Free Functions (TCFs). This reliance on trapdoors is a major open problem, as reducing cryptographic assumptions (e.g., to one-way functions or algebraic structures) remains a primary goal in cryptography.
Security Overhead: Standard RSP definitions require "malicious-server blindness," ensuring the server learns nothing about the state even if it deviates arbitrarily from the protocol. This strong security notion often necessitates complex protocols and specific assumptions.

The paper investigates whether a weaker form of RSP can still support meaningful cryptographic applications while admitting constructions from weaker, trapdoor-free assumptions. Specifically, the authors ask:

Can useful applications be derived from RSP protocols with relaxed security guarantees?
Can such weaker RSPs be constructed without trapdoors?

2. Methodology and Definitions

Eavesdropper-Blind Remote State Preparation (EB-RSP)

The authors introduce a new primitive called Eavesdropper-Blind Remote State Preparation (EB-RSP). This relaxes the standard blindness requirement:

Standard Blindness: The quantum prover (server) must learn nothing about the prepared state, even if malicious.
EB-RSP Blindness: The protocol is blind only against an external eavesdropper who observes the classical transcript of an honest interaction between the verifier and the prover. The honest prover itself is allowed to know the state it prepares.

Formal Definition: An EB-RSP protocol involves a classical verifier $V$ and a quantum prover $P$ .

Correctness: $P$ holds a state $|+\theta\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta}|1\rangle)$ where $\theta \in \Theta_N = \{k \cdot \frac{2\pi}{N} \mid 0 \le k \le N-1\}$ , and $V$ holds the classical description $\theta$ .
Eavesdropper Blindness: Given the transcript of the honest execution, no quantum polynomial-time (QPT) eavesdropper can distinguish the true $\theta$ from a uniformly random sample from $\Theta_N$ .

The authors focus specifically on two-message EB-RSP protocols (one message from $V$ , one from $P$ ), as this structure is sufficient for their primary application.

Cryptographic Assumptions

The paper constructs EB-RSP from One-Way Group Actions (OWGAs).

Group Action: A map $\star: G \times X \to X$ satisfying group action axioms.
Free (Semiregular): The action is free if $g \star x = x$ implies $g = 1$ .
One-Wayness: Given $(x, s \star x)$ , it is computationally hard for a QPT adversary to find $s'$ such that $s' \star x = s \star x$ .
Key Distinction: Unlike TCFs, OWGAs do not inherently provide a trapdoor for the verifier to invert the function. The construction relies on the algebraic properties of the group action to cancel unknown parameters.

3. Key Contributions and Results

A. Construction of Two-Message EB-RSP from OWGAs

The authors present a concrete two-message EB-RSP protocol based on free OWGAs where $G = \mathbb{Z}_p^\lambda$ for a prime $p$ .

Protocol Overview:

Verifier ( $V$ ): Samples $x_0 \in X$ and $r, s \in G$ . Computes $x_1 = (-s) \star x_0$ . Sends $(x_0, x_1, r)$ to $P$ .
Prover ( $P$ ):
- Prepares a superposition over $b \in \{0,1\}$ and $g \in G$ .
- Computes $g \star x_b$ in superposition.
- Measures the output register, collapsing the state to a "claw" state $|0, g_0\rangle + |1, g_0 + s\rangle$ (due to the freeness of the action).
- Computes inner products with $r$ and applies Quantum Fourier Transforms (QFT) to the registers.
- Measures to obtain outcomes $g$ and $z$ , sending them to $V$ .
- Outputs the state $|+\theta\rangle$ where $\theta = \langle s, z \cdot r + g \rangle \cdot \frac{2\pi}{p}$ .
Verifier ( $V$ ): Computes $\theta$ using its secret $s$ and the received $g, z$ .

Significance of Construction:

Trapdoor-Free: The verifier does not need a trapdoor to compute $\theta$ . Instead, the algebraic structure of the group action ensures that unknown parameters (like $g_0$ ) cancel out during the QFT measurement, leaving only terms known to the verifier.
Security: Security relies on the Quantum Goldreich-Levin Theorem. Since $g$ is uniformly random and independent of the adversary's view, the term $\langle s, z \cdot r + g \rangle$ is computationally indistinguishable from uniform, hiding $\theta$ from the eavesdropper.
Generalization: The protocol can be extended to composite $N$ (product of distinct primes) by running parallel subroutines.

B. Construction of QPKE from EB-RSP

The authors demonstrate that two-message EB-RSP is sufficient to construct Quantum Public-Key Encryption (QPKE) with classical public keys and quantum ciphertexts.

Construction (Black-Box):

KeyGen: Run the EB-RSP setup $n$ times. The public key $pk$ consists of the verifier's first messages; the secret key $sk$ consists of the verifier's internal states.
Enc: To encrypt a bit $b$ , the encryptor (acting as the prover) runs the EB-RSP computation for each $pk$ instance to generate states $|+\theta_i\rangle$ . They then apply a unitary $U_b = R_z(b \cdot \lfloor N/2 \rfloor \cdot \frac{2\pi}{N})$ to flip the phase based on $b$ . The ciphertext is the set of transformed states and the prover's messages.
Dec: The decryptor uses $sk$ to recover $\theta_i$ , applies $R_z(-\theta_i)$ to remove the phase, and measures in the Hadamard basis to recover $b$ .

Security:
The IND-CPA security of the QPKE relies directly on the eavesdropper blindness of the underlying EB-RSP. Since the eavesdropper cannot distinguish the random angle $\theta$ from uniform, they cannot distinguish the encrypted state (which depends on $\theta + b \cdot \text{shift}$ ) from a random state.

C. Adaptation of Existing TCF-Based Protocols

The paper observes that existing RSP constructions based on plain TCFs (e.g., [BKM+25]) can be adapted to the two-message EB-RSP model. By merging messages and noting that the "byproduct bit" in TCF-based RSP is independent of the angle in honest executions, these protocols also satisfy eavesdropper blindness. This yields a second construction of QPKE from plain TCFs.

4. Significance and Claims

The paper claims the following significance:

First Trapdoor-Free RSP-Type Primitive: To the best of the authors' knowledge, this is the first RSP-type primitive with useful cryptographic applications that does not rely on any trapdoor primitive. It demonstrates that algebraic assumptions (OWGAs) can replace trapdoor assumptions for specific RSP tasks.
Weaker Security, Same Utility: The work establishes that eavesdropper blindness (a weaker security notion than malicious-server blindness) is sufficient for constructing QPKE with classical public keys. This suggests that the strong security requirements of standard RSP may be unnecessary for certain applications, potentially allowing for simpler protocols and weaker assumptions.
Modular Approach: The authors provide a generic black-box reduction from two-message EB-RSP to QPKE. This separates the construction of the state preparation primitive from its application in encryption, allowing for modular improvements in either component.
Foundational Step: While the construction is limited to specific group actions and does not yet achieve verifiable RSP or RSP against malicious servers without trapdoors, it provides a "first step" toward reducing the cryptographic assumptions underlying quantum cryptographic schemes.

Limitations and Open Questions:

The construction currently works for $N$ being a prime or a product of distinct primes; extending to prime powers remains unclear due to correctness issues with the QFT over prime powers.
The paper does not claim to construct verifiable RSP or malicious-server blind RSP from trapdoor-free assumptions; it explicitly leaves this as an open direction.
The resulting QPKE scheme produces quantum ciphertexts, not classical ones (unlike some TCF-based constructions).

In summary, the paper initiates the study of a weaker RSP notion (EB-RSP), constructs it from one-way group actions without trapdoors, and proves its sufficiency for building QPKE, thereby expanding the landscape of assumptions available for quantum cryptography.