⚛️ quantum physics

Quantum Computational Unpredictability Entropy and Quantum Leakage Resilience

This paper initiates the study of quantum computational entropy by defining quantum computational unpredictability entropy, proving its fundamental properties such as a leakage chain rule under quantum side-information, and demonstrating its utility for pseudo-randomness extraction against computationally bounded quantum adversaries.

Original authors: Noam Avidan, Rotem Arnon

Published 2026-02-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Noam Avidan, Rotem Arnon

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 keep a secret. In the world of classical cryptography (the kind used on your phone today), we have a very good way of measuring how "hard" that secret is to guess. We call this entropy. If your secret has high entropy, it's like a safe with a million random combinations; if it has low entropy, it's like a safe with the combination "1234."

For decades, scientists have studied how this "guessing difficulty" changes when a hacker steals some extra information (like a side note or a partial key). They have powerful mathematical tools to predict exactly how much harder or easier the secret becomes to crack after a leak.

However, the world is moving toward quantum computers. These machines don't just calculate faster; they play by different rules of physics. The problem is, we didn't have a good way to measure "guessing difficulty" in this new quantum world, especially when the hacker is limited by how fast their computer can think (computational power).

This paper, by Noam Avidan and Rotem Arnon, is like building the first reliable ruler for measuring secrets in the quantum age. Here is how they did it, using some everyday analogies:

1. The New Ruler: "Unpredictability Entropy"

In the past, scientists tried to measure quantum secrets using a tool called "HILL entropy," but it was a bit clunky. It was like trying to measure the temperature of a soup with a ruler—it just didn't fit the job.

The authors invented a new tool called Quantum Computational Unpredictability Entropy.

The Analogy: Imagine a master thief (the adversary) trying to guess a password.
- Old Way: We asked, "If the thief had infinite time and a super-computer, could they guess it?" (This is the old "Min-Entropy").
- New Way: We ask, "If the thief has a normal laptop and only a few seconds, can they guess it?"
Why it matters: In the quantum world, a secret might be mathematically "solved" if you wait forever, but it's still perfectly safe if the thief has to guess it now. This new ruler measures that "now" safety. It captures the idea that just because a secret can be broken in theory doesn't mean it will be broken in practice.

2. The "Leakage Chain Rule": The Bucket with a Hole

One of the most important things in cryptography is understanding what happens when a secret leaks. Imagine you have a bucket of water (your secret) and you poke a small hole in it (a leak).

The Problem: In the old quantum models, if the bucket was already wet (had some quantum side-information), and you poked a hole, the math got messy and often broke. It couldn't handle the idea of a "wet bucket" leaking more water.
The Solution: The authors proved a Leakage Chain Rule.
- The Analogy: They showed that even if your bucket is already sitting in a puddle (quantum side-information), and you poke a hole to let a little bit of water out (leakage), you can still calculate exactly how much water is left.
- The Catch: The math shows that quantum leaks are tricky. Because of a quantum phenomenon called "superdense coding" (which is like being able to pack two messages into one quantum coin), the water level drops by a specific, predictable amount (a factor of 2) every time a leak happens. This rule works even if the bucket was already full of "quantum water" before the leak started.

3. Squeezing Randomness from a Wet Sponge

Once you know how much "guessing difficulty" (entropy) you have left, you want to turn that into something useful, like a new random password. This is called Extraction.

The Challenge: You have a "wet sponge" (a source of randomness that has been partially leaked). Can you squeeze out a fresh, dry, random drop?
The Result: The authors showed that you can! They proved that a specific, simple method called the Inner-Product Extractor works like a magic sponge. Even if a quantum thief is watching you, as long as your "unpredictability entropy" is high enough, this method can squeeze out a bit of pure randomness that the thief cannot guess.
The Limit: They found that you can't just keep squeezing the same sponge forever. If you try to use the output of one squeeze as the input for the next (like recycling a seed), the math gets tricky because the "unpredictability" doesn't grow back the way it does in classical math. So, they designed a protocol where you use a fresh seed every time to keep the process secure.

4. The "Only Computation Leaks" Model

Finally, they updated the rules of the game for how hackers steal information.

The Old Rule: Previous models assumed hackers could only steal data if the computer was "thinking" (computing), but they had to assume the hacker's storage was limited.
The New Rule: The authors created a more realistic model. They allow the hacker to have a massive quantum memory (unlimited storage) and to steal data while the computer is working.
The Analogy: Imagine a magician (the computer) performing a trick. The old model said, "The spy can only peek when the magician is moving his hands, and the spy can only hold one card in their pocket." The new model says, "The spy can have a giant vault of cards, and they can peek whenever the magician moves, but they can only steal a tiny, specific card at a time."
The Outcome: Even with this much more powerful spy, the authors proved that their "Leakage Chain Rule" and "Extraction" methods still hold up. The secret remains safe as long as the leakage is small and controlled.

Summary

In short, this paper builds the first solid foundation for measuring how hard it is to guess secrets in a quantum world where the attacker is limited by their computer's speed. They created a new measuring stick (Unpredictability Entropy), proved a rule for how secrets degrade when leaked (Leakage Chain Rule), and showed how to still generate fresh, unguessable randomness from those leaking secrets (Extraction).

This doesn't mean we have quantum computers ready to break the internet tomorrow, but it gives scientists the mathematical tools to design security systems that will be safe when those computers arrive.

Technical Summary: Quantum Computational Unpredictability Entropy and Quantum Leakage Resilience

Problem Statement

In classical cryptography, computational entropies (such as HILL entropy and unpredictability entropy) are fundamental for analyzing and constructing primitives like pseudo-random generators, leakage-resilient schemes, and randomness extractors. These notions quantify uncertainty under computational constraints, distinguishing between information that is theoretically present but computationally hard to access.

However, in the quantum setting, the study of computational analogues of entropy remains largely unexplored. While information-theoretic quantum entropies (e.g., smooth min-entropy) are well-understood and underpin many quantum security proofs, they do not account for the computational limitations of adversaries. Existing attempts to define quantum computational entropy, such as the quantum variant of HILL entropy proposed in prior work [26], suffer from significant limitations: they lack a general leakage chain rule and often require restrictive assumptions, such as bounded quantum storage, which limits their applicability to modern quantum cryptographic scenarios involving unbounded side-information.

This work addresses the gap by initiating the study of quantum computational entropy. Specifically, it seeks to define a notion of entropy that captures the difficulty of guessing a classical secret given quantum side-information, restricted to adversaries with bounded computational power, while maintaining the structural properties necessary for cryptographic applications.

Methodology and Definitions

Quantum Computational Unpredictability Entropy

The authors introduce Quantum Computational Unpredictability Entropy, denoted as $H^{\varepsilon}_{\text{unp}(s)}(X|E)$ , where $X$ is a classical random variable and $E$ is a quantum system.

Operational Definition: The entropy is defined based on the optimal guessing probability of a computationally bounded adversary. Specifically, $H^{\varepsilon}_{\text{unp}(s)}(X|E) \geq k$ if, for any quantum guessing circuit $C$ of size at most $s$ , the probability of correctly guessing $X$ given access to the quantum state $\rho_E$ is at most $2^{-k}$ .
Smoothing: To align with standard quantum information theory practices, the definition employs smoothing. Instead of evaluating the entropy on a specific state $\rho_{XE}$ , the value is optimized over all states $\tilde{\rho}_{XE}$ that are $\varepsilon$ -close to $\rho_{XE}$ .
Distance Measure: Crucially, the authors utilize the purified distance ( $\Delta_P$ ) for smoothing, rather than the trace distance or a computational distance. This choice is motivated by the need for the distance measure to satisfy the data-processing inequality and the Uhlmann extension property (Lemma IV.8), which are essential for proving chain rules in the presence of quantum side-information.

Quantum Leakage Model

The paper proposes a generalized model for quantum leakage, extending the classical "Only Computation Leaks" (OCL) model.

$\lambda$ -Bounded Quantum Leakage Channel: A channel $\phi$ acting on a state $\rho_{XE}$ is defined as a composition $\phi = \Lambda \circ \psi$ . Here, $\psi$ is a pre-processing map acting only on the adversary's side-information $E$ , and $\Lambda$ appends an ancilla register $L$ (of dimension at most $2^\lambda$ ) and modifies only $L$ , leaving the marginal state of $X$ and the original side-information invariant.
This model allows for arbitrary quantum side-information and permits the leakage to be entangled with prior side-information, removing the "bounded storage" assumption found in previous frameworks.

Key Contributions and Results

1. A Fully Quantum Leakage Chain Rule

The primary theoretical contribution is the proof of a leakage chain rule for quantum computational unpredictability entropy.

Theorem II.3 / IV.6: For a state $\rho_{XBC}$ (classical on $X$ ), the entropy satisfies:
$H^{\varepsilon}_{\text{unp}(s)}(X|BC) \geq H^{\varepsilon}_{\text{unp}(s+O(\ell))}(X|B) - 2\ell$
where $\ell = \log \dim(C)$ .
Significance: This result holds even when $B$ and $C$ are quantum registers, allowing for unbounded prior quantum side-information. The factor of $2\ell$ is identified as fundamentally quantum (related to superdense coding) and is tight. This overcomes a key limitation of the quantum HILL-entropy framework [26], which could not support a fully quantum chain rule.

2. Pseudo-Randomness Extraction

The authors demonstrate that high unpredictability entropy enables the extraction of pseudo-randomness against quantum adversaries.

Inner-Product Extractor: They prove that the inner-product (IP) function serves as a secure one-bit extractor for sources with high $H^{\varepsilon}_{\text{unp}(s)}(X|E)$ . The proof leverages the "pretty good measurement" technique but adapts it to the computational setting by showing that if the IP output is distinguishable, an efficient circuit can guess the input $X$ with high probability.
Multi-bit Extraction: By combining the IP extractor with weak designs (following the approach of Trevisan's extractor), the paper constructs multi-bit extractors. The analysis carefully tracks the computational resources required, showing that the leakage chain rule is necessary to bound the entropy reduction caused by the advice string in the construction.

3. Alternating Extraction with Quantum Leakage

The paper applies these tools to alternating extraction protocols, a technique used to derive fresh randomness from weak sources in the presence of leakage.

Protocol Analysis: The authors analyze a protocol where two independent sources are used in alternating rounds, with bounded quantum leakage occurring after each step.
Security Guarantee: Using the newly defined leakage model and the chain rule, they prove that the unpredictability entropy of the sources degrades in a controlled manner across rounds. Consequently, pseudo-random bits can be securely extracted in each round, even when the adversary holds unbounded quantum side-information and the leakage is entangled with previous states.
Distinction from PRGs: The authors explicitly note that their framework does not support leakage-resilient stream ciphers based on Pseudo-Random Generators (PRGs). Unlike HILL entropy, unpredictability entropy does not increase under PRG expansion (since a bounded adversary can efficiently evaluate the PRG), meaning the "entropy amplification" step in stream cipher constructions fails in this model.

Significance and Claims

The paper positions itself as a foundational step toward a theory of quantum computational entropy, analogous to the role such entropies play in classical cryptography.

Foundational Framework: The work establishes that a well-founded notion of quantum computational entropy is essential for analyzing quantum cryptographic primitives against computationally bounded adversaries.
Overcoming Prior Limitations: By defining entropy based on guessing probability (unpredictability) rather than indistinguishability (HILL) and utilizing the purified distance for smoothing, the authors successfully derive a fully quantum leakage chain rule. This resolves structural deficiencies in previous quantum computational entropy proposals.
Broad Applicability: The proposed leakage model is more general than prior work, accommodating arbitrary quantum side-information and entangled leakage, thereby applying to a broader class of leakage scenarios.
Operational Relevance: The results provide the theoretical underpinnings for constructing cryptographic tools, specifically randomness extractors and alternating extraction protocols, that remain secure in the presence of quantum side-information and repeated quantum leakage.

The authors conclude that while their work opens new directions, several challenges remain, particularly in defining a "computational purified distance" that retains the desirable properties of the information-theoretic version while respecting computational limits, and in identifying broader classes of extractors (beyond the inner-product) that work with quantum unpredictability entropy.