🔢 mathematics

Quantum One-Way Functions and Related Cryptographic Primitives

This paper reviews the landscape of quantum one-way functions and related cryptographic primitives, clarifying their conceptual relationships, security assumptions, and physical realizability while outlining future directions for building a broader quantum-cryptographic ecosystem beyond key distribution.

Original authors: Georgios M. Nikolopoulos

Published 2026-08-07

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Georgios M. Nikolopoulos

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

Imagine you are trying to send a secret message to a friend. In the world of classical computers, we rely on "one-way functions." Think of these like a giant, complex smoothie machine. You can easily throw in fruit, ice, and sugar (the input) and press a button to get a delicious smoothie (the output). But if someone hands you the smoothie, it is practically impossible to figure out exactly which specific fruits went into it or to rebuild the original fruit bowl from the liquid. This "easy to make, hard to unmake" trick is the backbone of almost all modern digital security, from your bank passwords to encrypted messages.

However, there is a catch. Scientists have discovered that super-powerful quantum computers might one day be able to reverse-engineer these smoothies much faster than we thought, potentially breaking our current locks. This has sparked a race to find new, quantum-proof locks. But what if we could build locks that don't just rely on math being hard, but on the very laws of physics being impossible to break? This is where the paper steps in. It explores a wild new corner of science where the "smoothie" isn't a liquid, but a fragile, invisible quantum state. In this realm, the rules change: you can't copy the smoothie, and trying to taste it changes its flavor. The paper asks: Can we use these weird quantum rules to build unbreakable codes that stay secure even against super-computers?

The Quantum Smoothie Machine

This paper is a guidebook for a team of scientists trying to build a new kind of digital security based on the strange rules of the quantum world. The author, Georgios M. Nikolopoulos and colleagues, is reviewing a collection of ideas that attempt to create "Quantum One-Way Functions" (QOWFs). If a classical one-way function is a smoothie machine, a quantum one-way function is a machine that turns a secret code into a specific, delicate pattern of light or atoms.

The core idea is simple but mind-bending: You can easily prepare a specific quantum state (the "smoothie") if you know the secret code. But if an enemy tries to look at that state to figure out the code, the laws of physics get in the way. Quantum mechanics has a few famous "no-no" rules that make this possible. First, the No-Cloning Theorem says you cannot make a perfect photocopy of an unknown quantum state. Second, Measurement Disturbance means that if you try to peek at the state to learn its secrets, you inevitably mess it up, changing the very thing you are trying to measure. Third, Holevo's Theorem puts a hard limit on how much information you can squeeze out of a quantum system, no matter how smart you are.

The paper reviews several different "machines" (constructions) that try to use these rules to create unbreakable codes. Some of these machines use simple single-qubit rotations (like spinning a tiny magnet), while others use complex patterns of light called "coherent states" or "quantum fingerprints." The author explains that some of these machines are secure because of pure math (computational hardness), while others are secure because of pure physics (information-theoretic security). The latter is the holy grail: it means that even if the enemy has a super-computer and infinite time, they still can't break the code because the universe itself won't let them.

The Copy Problem and the "Shadow" Attack

One of the biggest challenges the paper highlights is the issue of "copies." In the classical world, if you send a password to a friend, you can send it a million times, and it's still just one password. But in the quantum world, sending multiple copies of a state is like sending multiple copies of a fragile glass sculpture. If you send too many, the enemy might be able to piece them together to figure out the secret, even if they can't break the laws of physics.

The paper discusses a concept called "One-Way State Generators" (OWSGs). These are generators that create a quantum state that is easy to make but hard to reverse. However, the author points out a tricky limitation: if an enemy is allowed to have a huge number of copies (polynomially many), they might be able to use a technique called "shadow tomography" to learn the state's secrets without breaking the laws of physics. This suggests that for some of these quantum locks to work, we must strictly limit how many copies of the "key" are ever in circulation. It's like saying, "This lock is unbreakable, but only if you promise never to make more than three copies of the key."

The "Pseudorandom" Illusion

The paper also dives into "Pseudorandom Quantum States" (PRSGs). Imagine trying to create a quantum state that looks so random and chaotic that even a super-computer can't tell the difference between your fake random state and a truly random one generated by nature. The author explains that while we have mathematical ways to create these "fake random" states, they are incredibly fragile. If there is even a tiny bit of noise or error in the real world (like a slight vibration or a temperature change), the "fake" state might become distinguishable from the "real" one, breaking the security. The paper suggests that while these ideas are theoretically powerful, building them in a noisy, imperfect real-world lab is a massive hurdle.

The Reality Check: Theory vs. Practice

Perhaps the most important takeaway from this review is the gap between theory and reality. The author is very clear: while we have many beautiful mathematical theories and "proofs" that these quantum one-way functions exist, actually building them is incredibly hard.

They compare the current state of quantum cryptography to the early days of the internet. We have the blueprints for a quantum internet with unbreakable locks, but we don't have the roads yet. The paper notes that many of these constructions require "quantum memories" (devices that can store quantum states for a long time), which are currently very difficult to build and keep stable. Other methods, like the "quantum fingerprint" states, require manipulating huge numbers of particles at once, which is beyond our current technology.

The author argues that instead of trying to build the most complex, theoretically perfect machine immediately, we should focus on simpler, "robust" designs that can survive the noise and errors of the real world. They suggest that the most promising path forward might be using "bounded-copy" security—designing systems that are secure specifically because we limit how many times a state can be used or copied. This turns a physical limitation (we can't store infinite copies) into a security feature.

The Bottom Line

In short, this paper is a map of the frontier. It tells us that quantum one-way functions are a real and exciting possibility that could revolutionize security. It shows us that the laws of physics can indeed be used to create locks that are fundamentally unbreakable. However, it also warns us that we are not there yet. The "smoothie machines" we have built so far are mostly theoretical; they work on paper but struggle in the messy, noisy real world. The author concludes that the future of this field depends on finding a sweet spot: creating quantum cryptographic tools that are simple enough to build with today's technology but clever enough to stay secure against tomorrow's super-computers. It's a reminder that while the universe offers us magic tricks, learning how to perform them without dropping the props is the real challenge.

Technical Summary: Quantum One-Way Functions and Related Cryptographic Primitives

Problem Statement
While quantum key distribution (QKD) represents the most mature application of quantum information science, the broader landscape of quantum cryptography remains less understood. In classical cryptography, one-way functions (OWFs) serve as the foundational building block for nearly all standard protocols. However, the existence of analogous quantum one-way functions (QOWFs) and the physical mechanisms that enforce one-wayness in the quantum domain are not fully resolved. Unlike classical OWFs, which rely on mathematical hardness assumptions, quantum constructions must contend with fundamental physical constraints such as the no-cloning theorem, measurement disturbance, and the Holevo bound. Furthermore, the field has seen the emergence of various related primitives—one-way state generators (OWSGs), pseudorandom state generators (PRSGs), and efficiently indistinguishable (EFI) pairs—often developed in overlapping but distinct research communities with different terminologies and security frameworks. The central problem addressed is the lack of a unified conceptual framework that clarifies the relationships, security assumptions, and physical realizability of these primitives.

Methodology
The paper adopts a review and comparative analysis approach, synthesizing literature from both the quantum information and theoretical cryptography communities. The methodology involves:

Formal Definition and Categorization: Establishing precise definitions for quantum one-wayness under two primary adversarial models: computational (Quantum Polynomial-Time, QPT) and information-theoretic (unbounded physical operations). The review distinguishes between "exact-label recovery" (identifying the specific classical input) and "approximate inversion" (finding any input producing a sufficiently similar quantum state).
Construction Analysis: Systematically reviewing specific constructions of classical-to-quantum mappings, including conjugate coding, quantum fingerprint states, single-qubit rotations, and phase-encoded coherent states. For each, the paper analyzes the trade-offs between information-theoretic security (based on limited accessible information) and computational security.
Comparative Framework: Contrasting QOWFs with related primitives like OWSGs, EFI pairs, and PRSGs. The analysis focuses on the security basis (computational hardness vs. physical limits), the adversarial model (copy limits vs. polynomial copies), and the nature of the indistinguishability or inversion hardness.
Physical Feasibility Assessment: Evaluating the experimental requirements of these primitives, particularly regarding state preparation, transmission, storage (quantum memory), and robustness to noise and decoherence.

Key Contributions and Results

Conceptual Unification: The paper clarifies the relationships between QOWFs, OWSGs, EFI pairs, and PRSGs. It establishes a conceptual hierarchy where, under suitable conditions on the output length, PRSGs (requiring computational indistinguishability from Haar-random states) imply OWSGs (requiring one-wayness against polynomially many copies), which in turn imply computational QOWFs. The paper explicitly notes that the converse implications do not hold in general. Conversely, bounded-copy information-theoretic QOWFs derive security from fundamental quantum limits rather than computational assumptions.
Analysis of Classical-to-Quantum Constructions:
- Conjugate Coding: Demonstrates information-theoretic hardness of exact-label recovery in single-copy settings due to non-orthogonality, though approximate inversion remains a distinct challenge.
- Quantum Fingerprints: Highlights their ability to embed exponentially many classical strings into polynomial-dimensional Hilbert spaces with small pairwise overlaps. The paper notes they serve as bounded-copy information-theoretic QOWFs but face challenges with constant pairwise overlaps and experimental scalability.
- Single-Qubit and Coherent States: Analyzes mappings based on qubit rotations and weak coherent states. It shows that for coherent states in the weak-photon regime ( $\sqrt{c}\mu \ll 1$ ), the accessible information scales logarithmically with the number of copies $c$ , recovering qubit-like behavior. However, for general coherent states, accessible information scales linearly with $c$ , imposing stricter constraints on security.
Distinction from PUFs: The paper explicitly differentiates QOWFs from Physical Unclonable Functions (PUFs). While QOWFs assume a publicly known mathematical description with a hard inversion problem, PUFs rely on hidden, device-specific physical randomness. Consequently, PUF security collapses if the mapping is characterized, whereas QOWF security does not depend on hiding the function description.
Indistinguishability and Pseudorandomness: The review details how EFI pairs capture the separation between efficient and unbounded distinguishability, while PRSGs aim to emulate Haar-random states. It notes that PRSGs typically rely on classical post-quantum assumptions (e.g., quantum-secure pseudorandom functions) rather than intrinsic quantum complexity.
Physical Realizability and Noise: A significant finding is the sensitivity of advanced primitives like PRSGs to noise. Recent results cited indicate that depolarizing noise not exponentially suppressed can render pseudorandom states efficiently distinguishable from Haar-random counterparts, suggesting that certain forms of quantum pseudorandomness may be beyond the reach of noisy intermediate-scale quantum (NISQ) devices.

Significance and Claims
The paper claims that the primary significance of this review lies in organizing the fragmented landscape of quantum cryptographic primitives to highlight their conceptual links and fundamental differences. It argues that:

Beyond QKD: The development of quantum cryptography beyond key distribution requires primitives that leverage uniquely quantum properties (unclonability, measurement disturbance) rather than merely reproducing classical computational security with quantum resources.
Bounded-Copy Security: The number of copies available to an adversary is a physical resource, not just a technical parameter. Security models that explicitly account for bounded-copy regimes offer a pathway to information-theoretic or "everlasting" security that has no direct classical counterpart.
Implementation Gap: While theoretical definitions (like OWSGs and PRSGs) are powerful, they face substantial physical barriers. The paper emphasizes that practical progress depends on identifying primitives that are robust to loss, noise, and imperfect state preparation, potentially favoring bounded-copy information-theoretic constructions over those requiring long-term quantum memory or high-fidelity pseudorandomness.
Future Directions: The author outlines open problems, including the need for task-specific primitives with realistic security guarantees, the exploration of hardware-rooted approaches (like QR-PUFs), and the integration of noise models into security analyses.

The review concludes that while the theoretical understanding of quantum one-wayness has advanced, the realization of a broader quantum-cryptographic ecosystem depends on bridging the gap between abstract complexity-theoretic definitions and the constraints of physical implementability.

More like this