⚛️ quantum physics

Information-Theoretic Solutions for Seedless QRNG Bootstrapping and Hybrid PQC-QKD Key Combination

This paper proposes a unified information-theoretic framework using universal hash functions and the Quantum Leftover Hash Lemma to resolve the seedless bootstrapping of Quantum Random Number Generators and to securely combine Post-Quantum Cryptography and Quantum Key Distribution keys, ensuring resilience against quantum adversaries while preserving min-entropy even if partial key material is compromised.

Original authors: Juan Antonio Vieira Giestinhas, Timothy Spiller

Published 2026-03-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Juan Antonio Vieira Giestinhas, Timothy Spiller

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 build a fortress that is completely immune to any attack, even from a super-smart hacker with a time machine (a "quantum adversary"). To do this, you need two things:

Perfectly random numbers to build your locks.
A way to mix different types of locks together so that if one breaks, the whole fortress still stands.

This paper, written by researchers from the University of York, solves two major headaches in building this "quantum-safe" fortress using a mathematical tool called a Strong Seeded Extractor. Think of this tool as a high-tech "magic blender" that turns messy, imperfect ingredients into a perfectly smooth, pure smoothie.

Here is the breakdown of their two main solutions, explained with everyday analogies.

Challenge 1: The "Chicken and Egg" Problem of Randomness

The Problem:
To generate perfect random numbers (like for a lottery or a secret code), you usually need a "seed" (a starting number) to kick things off. But where do you get that first seed?

If you use a computer to make the seed, it's not truly random (it's just a pattern).
If you use a Quantum Random Number Generator (QRNG) to make the seed, it needs a seed to start processing its own data.
The Loop: You need a seed to make a seed. It's like trying to start a campfire without matches, but the only way to get matches is to have a fire.

The Paper's Solution: The "Two-Stranger" Strategy
The authors propose a clever workaround using two independent QRNGs (let's call them Machine A and Machine B).

Machine A generates a bunch of raw, messy randomness (the "Input").
Machine B generates a different bunch of raw, messy randomness (the "Seed").
The Magic Blender: They feed both into their "Strong Seeded Extractor."

The Analogy:
Imagine you have two different people, Alice and Bob, who are both terrible at guessing numbers.

Alice writes down a list of numbers she guessed (Input).
Bob writes down a completely different list of numbers he guessed (Seed).
Even though Alice's list isn't perfect, and Bob's list isn't perfect, if you mix them together using the right mathematical recipe (the Quantum Leftover Hash Lemma), the result is a list of numbers that is perfectly random.
Crucially, because Alice and Bob are independent (they didn't talk to each other), a hacker can't predict the result even if they know how Alice and Bob think.

Result: You can now start your first QRNG without needing a pre-shared secret. You just need two machines running side-by-side.

Challenge 2: Mixing Different Types of Keys (The "Hybrid" Lock)

The Problem:
In the future, we will use two types of security:

QKD (Quantum Key Distribution): Unbreakable, based on the laws of physics. (Like a diamond lock).
PQC (Post-Quantum Cryptography): Very strong, based on complex math, but theoretically breakable if a super-computer finds a shortcut. (Like a steel lock).

We want to mix these two to get the best of both worlds. If the math lock (PQC) gets broken by a future computer, the physics lock (QKD) should still save us.

The Old Way (XORing):
The standard way to mix keys is to use a simple operation called XOR (like flipping switches).

The Flaw: If you mix a Diamond Lock and a Steel Lock, and the hacker steals the Steel Lock and the Final Mixed Key, they can easily reverse-engineer the Diamond Lock. The Diamond Lock is now ruined. It's like mixing a diamond with a piece of paper; if you burn the paper and keep the ash, you can't get the diamond back, but if you have the ash and the final mix, you can figure out the diamond.

The Paper's Solution: The "Entropy Budget" Blender
The authors propose using their "Magic Blender" (the Strong Seeded Extractor) instead of simple XOR.

How it works: You put the Diamond Lock and the Steel Lock into the blender. The blender doesn't just mix them; it compresses them. It takes a huge amount of "randomness" (entropy) from both and squeezes out a smaller, super-strong key.
The Safety Net: Because the blender squeezed out so much "waste" (compression), even if the hacker steals the Steel Lock and the Final Key, there is still so much "randomness" left over in the Diamond Lock that the hacker cannot figure it out.
The Trade-off: You need to start with more raw material (longer keys) to get a short, secure final key. But the security is worth it.

The Analogy:
Imagine you are making a concentrated soup.

XOR Method: You mix a bucket of water (Steel) and a bucket of gold dust (Diamond). If someone steals the water and the final soup, they can figure out exactly how much gold dust was in there.
The Paper's Method: You take a giant vat of water and a giant vat of gold dust. You boil it down until it's a tiny, thick, golden paste. If someone steals the water and the paste, they still can't figure out the original amount of gold dust because the boiling process (compression) threw away so much "information" that the original ingredients are mathematically unrecoverable.

Why This Matters for the Future

Bootstrapping: It solves the "how do we start?" problem for quantum devices. We can now build networks that generate their own security from scratch without needing a secret handshake beforehand.
Resilience: It allows us to mix "unbreakable physics" with "very strong math." Even if the math part is cracked in 20 years, the physics part keeps your data safe.
No Single Point of Failure: Unlike the old methods, if one part of the system is compromised, the rest of the system doesn't automatically collapse.

In a Nutshell

The authors have invented a mathematical "safety blender."

It lets two imperfect random machines create a perfect random seed.
It lets you mix a "perfect" key with a "strong" key so that if the strong key breaks, the perfect key remains safe.

It's a way to ensure that even in a world of super-quantum computers, our digital secrets remain locked tight.

1. Problem Statement

The paper addresses two critical challenges in the deployment of quantum-safe communication infrastructure:

Seedless QRNG Bootstrapping: Quantum Random Number Generators (QRNGs) typically require an initial random seed to perform post-processing (randomness extraction) to ensure the output is statistically uniform. However, generating this initial seed often creates a "chicken-and-egg" problem: a seedless QRNG needs a seed to generate a seed. Existing solutions often rely on pre-shared secrets or assume the existence of a trusted seed, which is impractical for new, isolated nodes.
Resilient Hybrid Key Combination: As networks transition to Post-Quantum Cryptography (PQC), there is a need to combine PQC keys (computationally secure) with Quantum Key Distribution (QKD) keys (information-theoretically secure). Standard methods like XORing keys are vulnerable to implementation errors (e.g., double XORing) and lack robustness: if the combined output and one input key are compromised, the remaining key is fully revealed. Furthermore, standard Key Derivation Functions (KDFs) lack information-theoretic security (ITS) proofs.

2. Methodology

The authors propose a unified framework based on Strong Seeded Extractors and the Quantum Leftover Hash Lemma (QLHL).

Core Mathematical Tool: The paper utilizes the Modified Toeplitz family of hash functions. These are proven to be "1-almost universal²" (and dual universal²), making them valid candidates for strong seeded extractors under the QLHL.
The Quantum Leftover Hash Lemma (QLHL): The authors extend the standard QLHL to account for:
- Weak Seeds: Seeds that do not have perfect uniformity but possess a characterized min-entropy.
- Smoothness Parameters: Accounting for statistical closeness to uniformity in both the input and the seed.
- Conditional Independence: Ensuring the input and seed are conditionally independent given an unbounded quantum adversary.
Security Model: The framework assumes an unbounded adversary capable of performing any quantum attack (including coherent attacks). Security is defined by the smooth min-entropy ( $H_{min}^\epsilon$ ), quantifying the amount of randomness extractable even if the adversary holds quantum side information.

3. Key Contributions

A. Application 1: Bootstrapping Seedless QRNGs

The paper proposes a method to generate a secure seed using two independent seedless QRNGs without any pre-shared secret.

Mechanism: One QRNG generates the "input" raw data, and the other generates the "seed" raw data.
Condition: The two sources must be physically independent (no correlations).
Process: Using the Modified Toeplitz extractor and the QLHL, a statistically uniform random bitstring is extracted if the sum of the min-entropies of the input and seed exceeds the output length plus a security overhead.
Result: This resolves the bootstrapping loop, allowing the first QRNG iteration to be secured purely by physical entropy sources.

B. Application 2: Resilient Hybrid Key Combination (PQC + QKD)

The paper introduces a method to combine PQC and QKD keys that offers superior resilience compared to XOR.

Mechanism: The keys are treated as inputs to a strong seeded extractor. The "seed" for the extractor is constructed from a portion of the keys themselves (private seed scenario) or a public uniform random string (public seed scenario).
Resilience: Unlike XOR, where compromising the output and one key reveals the other, this method ensures that if the output and one key are compromised, the remaining key retains quantifiable min-entropy. The security of the remaining key depends on the compression ratio and the initial entropy budget.
HILL Entropy Integration: The framework extends to PQC keys by modeling them as having HILL entropy (Hastad, Impagliazzo, Levin, and Luby). This allows the QLHL to treat computationally secure PQC keys as sources of entropy, enabling a hybrid security model where the final key's security is a mix of information-theoretic and computational guarantees.

C. Protocol Integration (Muckle Series)

The authors demonstrate how this method can replace Pseudo-Random Functions (PRFs) or KDFs in hybrid protocols (e.g., the Muckle series).

Transcript Binding: The method naturally binds protocol transcripts to the key material within the extractor input, providing a unified approach for entropy distillation and session binding.
Trade-off: The method requires a larger input key space (higher compression ratio) compared to XOR, but this "entropy budget" provides a security buffer against leakage.

4. Results and Analysis

Theoretical Bounds: The paper derives specific inequalities (Lemma 2) determining the maximum output length ($|output|$) based on the min-entropies of the input and seed, the seed length, and the desired security parameter ( $\epsilon'$ $ϵ^{'}$ ).
- Formula: $|output| \leq H_{min}^{input} + H_{min}^{seed} - |seed| - 2\log(1/\epsilon') + 2$ .
Security Scenarios:
- Adversary Controls Generation: If an adversary controls the generation of one key, secure extraction is generally impossible unless the other key has significantly higher entropy.
- Key Revelation: If one key is revealed after generation, the method guarantees the remaining key and the combined output remain secure, provided the compression ratio is high enough.
- Output Revelation: If the output is revealed, the remaining min-entropy of the source keys is reduced by the length of the output, but the security bounds remain quantifiable.
Complexity: The computational complexity is $O(n^2)$ (or $O(n \log n)$ with Fast Fourier Transform) due to matrix multiplication, which is higher than the $O(n)$ complexity of XOR. However, this is accepted as a trade-off for unconditional security and resilience.

5. Significance

Unconditional Security: The proposed framework provides Information-Theoretic Security (ITS) for key combination, a property absent in standard KDFs and vulnerable in XOR implementations.
Quantum-Resilient: The security proofs hold against unbounded quantum adversaries, making the solution "future-proof" for the post-quantum era.
Practical Bootstrapping: It solves a fundamental practical hurdle in deploying QRNGs in isolated environments by eliminating the need for pre-shared seeds.
Hybrid Robustness: It offers a mathematically rigorous way to combine PQC and QKD, ensuring that even if the PQC component is broken (e.g., by a future quantum algorithm), the QKD component preserves the security of the hybrid key, provided the entropy budget is managed correctly.
Architectural Impact: The method provides a drop-in replacement for PRFs in hybrid protocols, enhancing security by binding transcripts and keys in a single, provably secure step.

In conclusion, the paper presents a mathematically rigorous, unified solution for randomness generation and key management in quantum networks, leveraging the QLHL and Modified Toeplitz matrices to achieve resilience against both quantum adversaries and implementation failures.