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

AI summary

Overview

Research area: Quantum cryptography, specifically quantum-computation classical-communication (QCCC) protocols, remote state preparation (RSP), and quantum public-key encryption (QPKE).

Technical level: Advanced. The paper assumes familiarity with quantum computation, group actions, quantum Fourier transform over finite abelian groups, and standard cryptographic security games (IND-CPA, QPT/PPT adversaries, negligible functions).

Scope: The paper introduces a relaxed notion of remote state preparation—eavesdropper-blind RSP (EB-RSP)—proves that its two-message form suffices to build quantum public-key encryption with classical public keys and quantum ciphertexts, and constructs such protocols from free one-way group actions (OWGAs) and from plain trapdoor claw-free functions (TCFs), notably without any trapdoor in the group-action case.

What This Paper Is About

Remote state preparation lets a purely classical client instruct a quantum server to hold a specific quantum state while the client knows a classical description of that state. Every known RSP construction relies on strong, trapdoor-based assumptions, typically variants of trapdoor claw-free functions, because the client needs a secret trapdoor to recover the description of the prepared state. The authors ask whether a much weaker security requirement—hiding the prepared state only from an outside eavesdropper who sees the protocol transcript, rather than from the quantum server itself—is still strong enough to be cryptographically useful, and whether it can be achieved without trapdoors.

Key Contributions

1. A new primitive, eavesdropper-blind RSP (EB-RSP). The definition requires only that no quantum polynomial-time eavesdropper holding the transcript of an honest verifier and honest prover can distinguish the real angle θ from a uniformly random sample of Θ_N. The authors stress this differs from honest-but-curious blindness: the eavesdropper never sees the honest prover's internal state, so the notion is strictly weaker.

2. A trapdoor-free construction from one-way group actions. Theorem 1.3 shows that a free OWGA ⋆: G × X → X with G = ℤ_p^λ for a prime p implies a two-message EB-RSP. The construction replaces the trapdoor with algebraic structure: properties of the group action cancel out parameters unknown to the verifier, so only verifier-known quantities remain in the phase.

3. A black-box transformation from EB-RSP to QPKE. Theorem 1.5 shows that any two-message EB-RSP yields a QPKE scheme with classical public keys and quantum ciphertexts. Combined with the above, this gives QPKE from specific OWGAs (Corollary 1.6) and from plain TCFs (Corollary 1.7).

4. Adaptation of existing RSP to the weaker notion. The authors observe that existing RSP constructions are likely adaptable to two-message EB-RSP and demonstrate this explicitly for a concrete TCF-based construction (drawn from the protocol in [5] and described in the paper's Appendix A), yielding Theorem 1.4.

Main Findings

• Protocol shape (OWGA-based EB-RSP). The verifier samples x₀ ← X and r, s ← G, computes x₁ := (−s) ⋆ x₀, and sends (x₀, x₁, r). The prover prepares a superposition over branch and group element, entangles it with the group action applied to x_b, measures the third register, uses r to prepare a state of the form |0, g₀, ⟨g₀,r⟩⟩ + |1, g₀+s, ⟨g₀+s,r⟩⟩, measures the last two registers in the QFT basis to obtain (g, z), sends (g, z) to the verifier, and outputs |+_θ⟩ with θ := ⟨s, z·r + g⟩. The verifier recomputes θ from s, r, z, g.

• Correctness rests on freeness plus algebra. Freeness collapses the state to a claw state |0, g₀⟩ + |1, g₀+s⟩, and the Fourier-basis measurement pushes terms into a relative phase in which unknown parameters such as g₀ cancel.

• Security rests on the quantum Goldreich-Levin theorem for large fields (Theorem 2.6). Because g is uniform and independent of everything under honest behavior, θ consists of a secret s together with a uniformly random quantity z·r + g, which is computationally indistinguishable from uniform.

• The protocol can be simplified. The authors report that after completing a first version of the paper they realized—as also pointed out independently by an anonymous Asiacrypt reviewer—that r and the measurement outcome z can be removed entirely, equivalent to setting r = 0 (the all-zero string). Completeness is unchanged since it holds for every r, and blindness still follows because for any fixed verifier randomness and any inner-product-register outcome, the Fourier outcome g is uniform over G.

• A broad output-state family. The protocol prepares "root of unity states": N states equally spaced on the (X, Y) plane of the Bloch sphere, i.e., |+⟩ states whose relative phases are the N-th roots of unity. Most prior RSP protocols cover only special cases such as BB84 states and generalized BB84 states.

• Parameter range for N. The protocol covers N = p prime and extends to N = p₁⋯p_m for pairwise distinct primes p_i by running the protocol in parallel, giving θ = θ₁ + … + θ_m ∈ Θ_N. The authors state that extending the idea to powers of primes remains unclear.

• No trapdoor is used. The verifier does not invert any function with secret information; the group action's algebraic properties alone remove unknown parameters from the state description. The authors describe this as the first RSP-type primitive with meaningful cryptographic applications that relies on no trapdoor primitive.

• QPKE construction. Key generation sets pk := (x₀, x₁, r) (the verifier's first message) and sk := s. Encryption runs the prover's steps to obtain |+_θ⟩ and (z, g), applies U_b := R_z(b·⌊N/2⌋·2π/N), and outputs ct := (U_b|+_θ⟩, z, g). Decryption uses s to recover θ, applies R_z(−θ) to obtain U_b|+⟩, and measures in the Hadamard basis; the state is exactly |+⟩ for b = 0 and very close to |−⟩ for b = 1, and the success probability is amplified by encrypting many states and taking a majority vote.

• Only one bit of θ must be hidden for IND-CPA. Eavesdropper blindness hides the full angle, i.e., every bit of k when N is a power of 2. For IND-CPA, however, only the most significant bit of k matters—equivalently, whether θ lies on the upper or lower half of the unit circle. The authors note that all other known RSPs do the opposite, hiding all but the most significant bit, because they must also protect against a malicious prover.

• A stated caveat on novelty. Remark 1.8 notes that the assumption-level conclusions of Corollaries 1.6 and 1.7 can also be obtained by specializing the framework of [20]: defining f_b(h) := h ⋆ x_b, freeness makes each f_b injective and hence collapsing, one-wayness makes the pair (f₀, f₁) claw-free, and [20]'s conversion-hardness result then yields IND-CPA-secure QPKE with classical public keys and quantum ciphertexts. The authors therefore present these corollaries as alternative modular derivations rather than new feasibility results relative to [20]. Similarly, a TCF yields a swap-trapdoor function pair.

• Contrast with prior QPKE-from-RSP work. The paper notes that [8] built QPKE with classical public keys and classical ciphertexts from RSPs based on dual-mode TCFs, whereas this work obtains QPKE with classical public keys but quantum ciphertexts from a weaker RSP notion.

• No experimental evaluation. The paper is entirely theoretical; no benchmarks, implementations, dataset sizes, or concrete parameter instantiations are reported.

Methodology in Plain English

The authors work at the level of definitions, theorems, and reductions. They first carve out a deliberately weak security definition: instead of demanding that the quantum server learn nothing about the prepared state (the usual blindness requirement), they demand only that a third party reading the public transcript learn nothing. They then design an interactive protocol in which the verifier sends two group elements derived from a secret shift s, and the prover uses a quantum superposition over the group to entangle a branch bit with the group action. Measuring part of the register leaves a "claw" pair of inputs that map to the same value—possible because the action is free—and a Fourier-basis measurement converts the leftover group information into a relative phase on a single qubit. The trick is that the algebra of the action makes the prover's unknown offset cancel, leaving a phase expressible purely in terms of the verifier's secret and public randomness. For security, they reduce the hidden phase to a Goldreich-Levin style inner product of a secret with a uniform value, which is pseudorandom. Finally, they treat the resulting protocol as a reusable component: they show that any two-message protocol meeting the definition can be turned into an encryption scheme by publishing the verifier's first message as the public key, keeping its secret state as the secret key, and having encryption apply a small rotation that encodes the message bit into the phase.

Why This Matters

The work opens a route to RSP-type primitives that avoids trapdoor claw-free functions, the assumption underlying essentially all prior RSP constructions, and it does so using assumptions rooted in group-based and isogeny-based cryptography—a qualitatively different framework. It also proposes a modular architecture in which the state-preparation primitive is separated from the encryption scheme built on top of it, so improvements to either side can be plugged in. The paper frames this as evidence that algebraic assumptions may provide an alternative path to QCCC primitives beyond the trapdoor paradigm. Prior impossibility evidence suggests one-way functions alone are unlikely to suffice for certain families of RSP protocols, which makes the search for intermediate assumptions relevant.

Potential applications, all drawn from the roles the paper attributes to RSP and QPKE:

• Delegated and verifiable quantum computation, where a classical client drives a remote quantum server.
• Proofs of quantumness, which the paper lists among protocols built on RSP and notes share tools such as coherent claw states and complementary/Fourier-basis measurements.
• Quantum fully homomorphic encryption and unclonable cryptography, both listed as RSP-dependent applications.
• Quantum public-key encryption with classical public keys, which matters because quantum public keys cannot be freely copied, stored, or distributed the way classical ones can.

Industry relevance: the motivating setting is cloud-based quantum computing, where users hold only classical hardware but want cryptographic guarantees from a remote quantum device. Classical public keys are a practical advantage because they fit existing public-key infrastructure; the quantum ciphertext requirement is the tradeoff this work accepts.

Future Directions

• Map the landscape of weaker RSP notions. The authors ask which security properties of RSP are genuinely necessary for which quantum cryptographic tasks, and specifically which additional applications follow from eavesdropper blindness alone in the QCCC model.
• Strengthen the primitive without reintroducing trapdoors. A natural target is blindness against a malicious prover, or verifiable RSP, using the algebraic phase-generation mechanism developed here; a closely related target is proofs of quantumness from group-action-based assumptions.
• Generalize the group-action construction. It remains open whether the OWGA-based protocol extends beyond the classes of groups considered in this work.
• Reach classical ciphertexts. The paper asks whether similar techniques could yield QPKE with classical public keys and classical ciphertexts, as in [8], while still avoiding trapdoor assumptions. Extending the parallel-composition trick from distinct primes to powers of primes is also stated as unresolved.

Target Audience

Quantum cryptography researchers and graduate students working on the QCCC model, remote state preparation, or quantum public-key encryption; cryptographers interested in group actions and isogeny-based assumptions as alternatives to trapdoor claw-free functions; and protocol designers who want to understand exactly how much security a state-preparation primitive needs in order to support encryption. Readers without a background in quantum algorithms and cryptographic reductions will find the technical sections demanding.

Authors’ abstract

Remote state preparation (RSP) is a central primitive in quantum cryptography, enabling classical parties to remotely construct quantum states using only classical communication. As a result, RSP serves as a key building block in numerous protocols involving classical clients and quantum servers, allowing classical parties to leverage the advantages offered by powerful quantum computers. All known constructions of RSP rely on strong cryptographic assumptions, typically variants of trapdoor claw-free functions (TCFs). In this work, we initiate the study of a weaker form of remote state preparation, which we call eavesdropper-blind remote state preparation (EB-RSP). Informally, EB-RSP requires blindness only against external observers who see the transcript of the honest protocol, rather than against the quantum server itself. Despite this relaxed adversarial model, the resulting notion remains sufficient for useful cryptographic applications. In particular, we show that two-message EB-RSP already suffices to construct quantum public-key encryption with classical public keys and quantum ciphertexts. We then construct two-message EB-RSP protocols from specific one-way group actions, yielding a first step toward RSP-type primitives based on assumptions that do not rely on trapdoors. Finally, we observe that existing RSP constructions are likely naturally adaptable to the two-message EB-RSP notion; we demonstrate this explicitly for a concrete TCF-based RSP construction.