Quantum One-Way Functions and Related Cryptographic Primitives

AI summary

Overview

• Research area: Quantum cryptography / quantum information science, specifically cryptographic primitives whose security relies on quantum states rather than only on classical computational hardness.
• Technical level: Intermediate. The author deliberately minimizes complexity-theoretic formalism and targets readers with a physics background who are not familiar with standard computational-complexity conventions.
• Type of work: Topical Review (arXiv:2608.05754v1 [quant-ph], 06 Aug 2026, CC BY 4.0), single author (Georgios M. Nikolopoulos, IESL/FORTH and FORTH-QuTech, Heraklion, Greece).
• Scope (one sentence): A structured, comparative review of quantum one-way functions and closely related quantum-state primitives — one-way state generators, pseudorandom quantum state generators, and efficiently indistinguishable (EFI) pairs — organized around their security assumptions, physical realizability, and open problems.

Note on completeness: the supplied text is truncated partway through Section 3.2. Sections 4–10 (indistinguishability, EFI pairs, PRSGs, beyond-classical-to-quantum constructions, physical unclonable functions, post-quantum context, conclusions) are known here only from the abstract, the introduction's roadmap, and the keywords. No numerical benchmarks, dataset sizes, or experimental results appear in the supplied content, and none are reported below.

What This Paper Is About

Quantum cryptography has so far been dominated by quantum key distribution, which remains the most mature and widely deployed application of quantum information science. Classical cryptography, by contrast, rests almost entirely on one-way functions — efficiently computable but hard-to-invert maps — so the natural question is whether meaningful quantum analogues exist and what physical or computational mechanisms could enforce their one-wayness. This review organizes and compares the quantum primitives that have been proposed as foundational building blocks for cryptography beyond key distribution, and clarifies how they relate to one another and where they fall short of classical one-way functions.

Key Contributions

1. A unified comparative map of four primitive families. The review brings together quantum one-way functions (QOWFs), one-way state generators (OWSGs), pseudorandom quantum state generators (PRSGs), and efficiently indistinguishable (EFI) pairs, which originated independently in the quantum-information and theoretical-cryptography communities under different terminology and security frameworks, and summarizes their relationships and distinguishing features in a table.
2. A terminology clarification. The author notes that "QOWF" is used inconsistently — sometimes for a post-quantum one-way function with classical output, sometimes for a mapping involving quantum states — and explicitly adopts the latter convention throughout, citing this inconsistency as a motivation for the review.
3. A formal separation of adversarial models. Two definitions are given for classical-to-quantum mappings: computational one-wayness against uniform quantum polynomial-time (QPT) adversaries, and bounded-copy information-theoretic one-wayness against arbitrary physically allowed (completely positive trace-preserving) operations.
4. A careful distinction between two notions of "inversion." The review separates exact-label recovery (outputting the original classical label, x′ = x) from approximate inversion (outputting any label whose state is sufficiently close, using a Uhlmann-fidelity threshold), and argues that exact-label hardness is not by itself an analogue of classical preimage resistance.

Main Findings

• Quantum one-wayness has physical as well as computational sources. The review identifies four principles that can enforce one-wayness independently of computational assumptions: the impossibility of perfectly discriminating non-orthogonal states; information gain implies disturbance (so an adversary cannot repeatedly and independently measure the same unknown state, unlike a classical OWF output that can be copied); Holevo's theorem, which bounds extractable classical information from a single d-dimensional system by I_acc ≤ log₂(d); and the no-cloning theorem.

• Copy number is a structural parameter, not a detail. In the inversion game, the challenger prepares c ≥ 1 independent copies of ρ_x and hands the adversary ρ_x^⊗c together with the security parameter n. Security against polynomially many copies implies security against fewer, and c = 1 is the single-copy challenge.

• A simple information-theoretic counting constraint. An adversary can extract at most c·log₂(d) bits from c copies of a d-dimensional state, while specifying the index x requires n bits. If n ≫ c·log₂(d), the adversary is information-theoretically unable to extract enough information to identify x uniquely — so n, c, and d cannot be chosen arbitrarily, and information-theoretic one-wayness can hold only up to a limited number of copies.

• Computational versus information-theoretic one-wayness are fundamentally different adversarial models. The computational notion can remain meaningful even when polynomially many copies are available, which the review stresses is crucial for OWSGs, PRSGs, and EFI pairs; the information-theoretic notion is typically accompanied by a bound on copies. The author notes the boundary between the two is not always sharp and practical protocols may combine both.

• Injectivity does not imply a unique operationally acceptable inverse. Even when the labeling x ↦ ρ_x is injective, distinct output states need not be orthogonal and may have substantial overlap, so an incorrect label may still pass an operational verification test. Conversely, for a non-injective mapping — the review's example is a constant mapping x ↦ ρ — exact-label recovery may succeed only with probability 2⁻ⁿ while inversion is trivial. Exact-label recovery is therefore characterized as a separate label-identification problem.

• A fidelity-threshold criterion defines acceptance in approximate inversion. Success is declared when F(ρ_x, ρ_x′) ≥ τ with τ ∈ (1/2, 1) a fixed, known constant; the review notes trace distance could also be used. The threshold is purely a verification condition in the inversion game and does not define a canonical preimage set.

• The overlap structure of the state ensemble governs threshold choice. Defining F_max := max_{x ≠ x′} F(ρ_x, ρ_x′) over the ensemble, choosing F_max < τ < 1 guarantees the correct label is always accepted in the ideal noiseless case (since F(ρ_x, ρ_x) = 1) while every incorrect label is rejected. If F_max ≥ τ, at least one pair of distinct labels passes acceptance — which the review notes does not by itself imply insecurity, since that set may be negligibly small.

• Random-guessing baselines differ between the two objectives. For exact-label recovery with uniformly sampled input, guessing succeeds with probability 1/|𝕏|, so |𝕏| typically must grow exponentially with n; for approximate inversion the guessing probability also depends on the number and structure of labels satisfying the acceptance criterion and cannot be inferred from |𝕏| or |𝕊| alone.

• Geometric separation does not guarantee invertibility. Although tensor powers of non-orthogonal states may become nearly orthogonal as copies increase, identifying the correct state among exponentially many candidates still depends on the structure of the whole ensemble, not just pairwise distinguishability.

• Quantum cryptography does not replace the classical world. The author emphasizes that quantum steps supply new guarantees — unclonability and measurement disturbance — while the information ultimately communicated, authenticated, or verified often remains classical, following a classical–quantum–classical workflow.

• Practical obstacles are physical, not only mathematical. Quantum states are fragile and susceptible to decoherence, imperfections, and environmental noise; generating and manipulating complex states remains challenging despite progress in QKD, and reliable long-term storage of quantum states remains an open issue. Comparing two quantum states, unlike comparing two classical OWF outputs, generally requires quantum operations and is subject to nonzero error unless the states are orthogonal.

Methodology in Plain English

This is a literature review, not an experimental or numerical study. The author's approach is to impose a common conceptual vocabulary on a scattered body of work. He first recalls classical one-way functions and their role (including that pseudorandom generators exist if and only if one-way functions do, and that public-key encryption is not known to follow from one-way functions alone but requires trapdoor one-way functions), then recasts quantum one-wayness as an explicit game between a challenger — who samples a random classical input and prepares c copies of the corresponding quantum state — and an adversary who must return a label. By varying two axes (what counts as success: exact label versus fidelity-approximate inversion; and who the adversary is: efficient quantum algorithm versus any physically allowed quantum operation), he obtains a small grid of security notions instead of four near-identical definitions. Concepts are kept intuitive: the relevant physical limits are stated informally, similarity between states is measured with Uhlmann fidelity, and the discussion is restricted to uniform adversaries for accessibility, with the non-uniform (advice-augmented) variant noted as formally stronger. Post-quantum cryptography — entirely classical schemes secure against quantum adversaries, resting on assumptions such as Learning With Errors, other lattice problems, code-based problems, and hash-based constructions — is explicitly set outside the review's scope.

Why This Matters

The review addresses a gap that is partly sociological: primitives with essentially the same goal were invented in separate communities with different language, which hinders comparison, reuse, and assessment of what is actually achievable. By clarifying which assumptions each primitive needs and which are physically realizable, it supports a realistic appraisal of the long-term vision of a quantum internet and of a broader quantum-cryptographic ecosystem beyond key distribution. Impact on research: it gives physicists a low-formalism entry point to a complexity-theoretic literature, and gives cryptographers a physical-feasibility perspective, while flagging that concepts described as "quantum one-way functions" in the physics literature often encode protocol-specific verification rather than preimage resistance.

Real-world applications the paper ties to these primitives (stated as applications arising from this framework, not as demonstrated deployments):

• Quantum money.
• Authentication schemes.
• Quantum public-key constructions.
• Quantum encryption protocols.

Industry relevance: the review is relevant to the mature QKD deployment market and to anyone planning quantum-internet infrastructure, since it foregrounds hardware-level requirements — state generation, manipulation, noise robustness, and the unresolved problem of long-term quantum storage. It also draws the boundary between post-quantum cryptography (classical schemes, such as LWE-based, code-based, and hash-based constructions, secure against quantum adversaries) and genuinely quantum-state primitives, a distinction with direct consequences for where standards and procurement efforts should invest.

Future Directions

• Physical realizability and experimental feasibility. Turning the reviewed constructions into implementable primitives, given decoherence, device imperfections, and the difficulty of preparing and manipulating complex quantum states.
• Noise robustness. Establishing how the security notions behave under realistic noise, and how verification thresholds such as τ should be set when the ideal noiseless assumption F(ρ_x, ρ_x) = 1 no longer holds.
• Long-term quantum storage and measurement practice. Resolving the open issue of reliable storage, and developing optimal measurement strategies — currently known only for certain scenarios, such as distinguishing symmetric pure states — that minimize error or maximize information gain.
• A broader theory of quantum one-wayness. The review closes by outlining open problems and a roadmap toward practical primitives beyond key distribution; specifics of that agenda lie in Section 10, which is beyond the truncated text provided here.
• Clarifying inter-primitive relationships. The comparison of QOWFs, OWSGs, PRSGs, and EFI pairs is presented as conceptual clarification; the abstract flags that these relationships remain an area needing clearer understanding.

Target Audience

Physicists interested in quantum cryptography who lack a background in standard computational-complexity formalism — the stated primary readership — as well as quantum-information researchers entering cryptography and cryptographers who want a physical-feasibility view of quantum-state primitives. Readers seeking a comprehensive survey of the full "Microcrypt" landscape of assumptions, reductions, separations, and applications are directed by the author to resources such as the Microcrypt Zoo instead.

Authors’ abstract

Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.