Source-linked AI summary
Eavesdropper-Blind Remote State Preparation and Applications to Quantum Public-Key Encryption
Kaniuar Bacho, Alexandru Cojocaru
TL;DR
Remote state preparation typically requires trapdoor-based assumptions, motivating weaker notions that may support applications under different assumptions. This paper introduces EB-RSP, proves that two-message EB-RSP yields QPKE with classical public keys and quantum ciphertexts, and constructs it from specific one-way group actions without trapdoors. The work also gives a modular connection to TCF-based constructions while identifying boundaries in the current construction.
Problem
Existing RSP constructions typically rely on trapdoor primitives, motivating whether weaker RSP security can support useful applications and be built from weaker, trapdoor-free assumptions.
Method
The paper introduces EB-RSP, requiring blindness against transcript-observing external eavesdroppers rather than the quantum prover, and studies two-message constructions from one-way group actions.
Results
Two-message EB-RSP suffices for QPKE with classical public keys and quantum ciphertexts, and can be instantiated from specific one-way group actions and plain TCFs.
Takeaways & Limitations
EB-RSP provides an intermediate state-preparation primitive linking algebraic one-way group actions and TCFs to quantum public-key encryption.
Takeaways & Limitations
Extending the construction to powers of primes remains unclear because verifier correctness can fail when an unknown group-action parameter affects the phase modulo p^m.
Abstract
from arXiv · showhide
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.
1 Introduction
This work introduces eavesdropper-blind remote state preparation (EB-RSP), a weaker RSP notion that still supports quantum public-key encryption and can be built from specific one-way group actions without trapdoors.
- Existing RSP constructions typically rely on trapdoor cryptographic primitives, while reducing the required assumptions remains an open problem.
- The work combines these results to obtain QPKE constructions from certain one-way group actions and from TCFs.It also presents EB-RSP as a modular route separating state preparation from encryption.
- EB-RSP hides the prepared state from transcript-observing quantum polynomial-time eavesdroppers but does not require hiding it from the prover.The protocol therefore weakens standard blindness by changing the adversary from the prover to an external observer.
- Any two-message EB-RSP protocol implies quantum public-key encryption with classical public keys and quantum ciphertexts.The result identifies EB-RSP as an intermediate primitive for constructing QPKE.
- Two-message EB-RSP protocols can be constructed from specific one-way group actions, providing an RSP-type primitive without trapdoor assumptions.The construction exploits algebraic properties of the group action to eliminate verifier-unknown parameters from the output-state description.
- The protocol’s correctness uses freeness and group-action algebra to cancel unknown parameters and leave a state description that the verifier can compute efficiently.After a Fourier-basis measurement, the remaining phase is θ := ⟨s, z · r + g⟩.
2 Preliminaries
The preliminaries establish notation for rotated quantum states, group actions, effective and one-way group actions, finite Abelian groups, and the quantum Goldreich–Levin theorem used later for security arguments.
- Notation: The paper defines the rotated |+⟩ state using roots of unity and introduces z-axis rotation operators, with states identified up to global phase.It denotes the n-th root of unity by ω_n = e2πi/n and allows any real rotation angle θ.
- Group actions: A group action maps pairs from a group G and set X to X while satisfying identity and compatibility with group multiplication.The action obeys g ⋆(h ⋆x) = (gh) ⋆x, and the paper introduces stabilizers and free actions.
- Effective and one-way group actions: An effective group action requires finite G and X, efficient classical group and action operations, efficient sampling, and a QPT uniform-superposition algorithm.These properties provide the computational framework for the cryptographic group actions used in the paper.
- Effective and one-way group actions: A one-way group action adds a cryptographic hardness condition, while the paper focuses on finite Abelian groups represented as products of cyclic groups.For free actions, an adversary must recover the acting group element itself; later constructions specialize components to prime-order groups.
- Fourier analysis: The paper introduces the quantum Fourier transform over finite Abelian groups and notes that its decomposition enables efficient implementation.Auxiliary maps and bilinear notation are defined to simplify later expressions involving these groups.
- Quantum Goldreich–Levin theorem: The quantum Goldreich–Levin theorem converts a quantum distinguisher for a large-field inner-product predicate into a quantum extractor, supporting later security proofs.In the paper’s setting, a negligible distinguishing advantage means the hardcore predicate appears uniformly random from the adversary’s view.
3 Eavesdropper-Blind Remote State Preparation
EB-RSP weakens RSP blindness to transcript-only protection against an external eavesdropper, while retaining enough structure for QPKE. The section constructs two-message protocols from specific one-way group actions and establishes correctness and eavesdropper blindness.
- Definition: EB-RSP protects the prepared state against a malicious eavesdropper who sees the honest verifier–prover transcript but not the prover’s internal state.This is strictly weaker than blindness against the quantum prover itself.
- Definition: The protocol prepares root-of-unity states, a family of N equidistant Bloch-sphere states that includes BB84 and generalized BB84 states as special cases.The verifier learns the classical angle θ describing the state held by the prover.
- Definition: The security definition uses indistinguishability for θ, which is necessary for QPKE when the state space can be exponential in the security parameter.For polynomial-size search spaces, search and indistinguishability formulations are equivalent; for exponential spaces, search security may reveal bits of θ.
- Two-message constructions: A plain TCF implies a two-message EB-RSP, and existing RSP protocols may likewise be adaptable to this weaker primitive.The section explicitly identifies a TCF-based transformation and suggests broader applicability of the approach.
- Construction from One-Way Group Actions: A free OWGA over G = Z_p for a polynomial-size prime p implies a two-message EB-RSP preparing N = p root-of-unity states.The construction avoids a verifier trapdoor by exploiting algebraic properties of the group action to cancel unknown parameters.
- Construction from One-Way Group Actions: The OWGA protocol terminates with probability 1, produces |+θ⟩ for verifier-known θ, and satisfies eavesdropper blindness.Blindness follows by reducing any distinguisher for the relevant inner product against uniform to an extractor contradicting one-wayness.
- Limitations: The construction’s prime-modulus extension does not currently generalize to prime powers because the verifier cannot determine an unknown-dependent phase modulo p^m.The m = 1 case works because both possible values are congruent modulo p.
- Limitations: Constructing EB-RSP from general abelian one-way group actions remains open because the proof relies on a large-field Goldreich–Levin theorem.The paper also leaves open whether this EB-RSP notion has applications beyond QPKE.
4 Quantum Public-Key Encryption with Classical Public Keys
The section constructs IND-CPA-secure QPKE with classical public keys and quantum ciphertexts from two-message EB-RSP, then gives instantiations from specific OWGAs and plain TCFs. Correctness is perfect in even cases and negligible-error in the odd-message case through repetition and majority voting.
- QPKE definition: The scheme defines classical KeyGen outputs, quantum ciphertexts from Enc, and QPT decryption using the secret key.KeyGen outputs (pk, sk); Enc takes a bit and outputs a quantum ciphertext; Dec outputs the recovered bit or ⊥.
- Two-message EB-RSP implies an IND-CPA-secure QPKE scheme with classical public keys and quantum ciphertexts.
- QPKE construction: Encryption runs EB-RSP.QComp repeatedly, applies a message-controlled Rz rotation to the prepared states, and transmits the rotated qubits with prover messages.Decryption recovers the angles through EB-RSP.Dec, removes them with inverse rotations, measures in the Hadamard basis, and uses majority vote.
- Correctness: At least 75% single-measurement correctness for the remaining odd-N, b = 1 case yields decryption probability 1 − negl(λ) by a Chernoff bound.
- Security: The construction is IND-CPA secure because the independent instances hide the encrypted bit from adversaries with no non-negligible advantage.The resulting implication is explicitly stated as two-message EB-RSP yielding IND-CPA-secure QPKE.
- Instantiations: A free OWGA over G = Z_p with polynomial-size G implies IND-CPA-secure QPKE, and plain TCFs provide another instantiation.
- Security interpretation: For IND-CPA security, hiding the most significant bit of the encoded angle suffices, unlike existing RSPs that hide all but that bit.For general N, the relevant hidden information is whether the angle lies in the upper or lower half of the unit circle.
A Eavesdropper-Blind Remote State Preparation from Trapdoor Claw-Free Functions
This section describes a concrete TCF-based RSP protocol that can be adapted into two-message EB-RSP. The protocol uses repeated subroutines to transform a prover’s input state while the verifier reconstructs a classical bit-angle description.
- The described RSP relies solely on a plain trapdoor claw-free function and can be modified into two-message EB-RSP.
- Security and output: The resulting states have the form Z^b|+θ⟩, while the protocol’s stated security guarantee applies only to θ.
- TCF assumptions: A TCF supplies a generated function pair and trapdoor, with inversion recovering two preimages for an image.The construction also assumes correctness, efficient superposition, claw-freeness, and an embedding of X into polynomial-length bitstrings.
- Subroutine: The subroutine takes a prover state α|0⟩ + β|1⟩ and outputs a verifier pair (b, θ) while applying a phase transformation to the prover’s state.The verifier’s angle is θ = z0 + z1, where z0 and z1 are inner products involving the recovered preimages and random strings.
- Subroutine: The verifier sends function descriptions, checks a measured image, samples random strings, and receives a prover message containing a Hadamard-basis measurement result.The prover coherently evaluates the functions, measures to obtain y, computes inner products over Z2, applies QFTn, and conditionally returns d.
- Subroutine: After the QFT and postselection steps, the prover’s state becomes α|0⟩ + β(−1)^(d·(x0⊕x1))ω_n^(z0+z1)|1⟩.The protocol aborts if the QFT measurement does not produce d′ = 1; otherwise it measures the second register and sends d to the verifier.
- The section refers to the original work for the full correctness and security analysis of the concrete RSP protocol.