QRNG vs. PRNG

QRNG vs. PRNG#

Quantum random number generation vs. pseudorandom number generation. Entropy quality, statistical testing, and why the source of randomness matters for cryptographic key generation.

Randomness is the foundation of all cryptography. Every key, nonce, initialization vector, and salt depends on unpredictable random numbers. The quality of that randomness directly determines the security of the system. This chapter compares two fundamentally different sources: pseudorandom number generators (PRNGs) that produce deterministic output from a seed, and quantum random number generators (QRNGs) that derive randomness from quantum mechanical phenomena.

The Randomness Hierarchy#

                    Theoretical Strength
                           ↑
    ┌──────────────────────┼──────────────────────┐
    │                      │                      │
    │   Quantum RNG        │   True RNG           │
    │   (QRNG)             │   (hardware)         │
    │   Provably random    │   Based on physical  │
    │   from QM postulates │   processes           │
    │                      │                      │
    ├──────────────────────┼──────────────────────┤
    │                      │                      │
    │   CSPRNG             │   OS Entropy          │
    │   Cryptographically  │   /dev/urandom,      │
    │   secure PRNG        │   getrandom()        │
    │                      │                      │
    ├──────────────────────┼──────────────────────┤
    │                      │                      │
    │   PRNG               │   Mersenne Twister,  │
    │   Deterministic,     │   LCG, xorshift      │
    │   NOT for crypto     │                      │
    │                      │                      │
    └──────────────────────┴──────────────────────┘

Pseudorandom Number Generators (PRNGs)#

A PRNG is a deterministic algorithm that expands a short seed into a long sequence of numbers that appear random but are entirely determined by the seed.

Cryptographically Secure PRNGs (CSPRNGs)#

For cryptographic use, PRNGs must satisfy additional properties:

  1. Forward security: Given the current state, you cannot predict past outputs

  2. Backward security: Given past outputs, you cannot predict future outputs

  3. Computational indistinguishability: No efficient algorithm can distinguish CSPRNG output from truly random bits

Common CSPRNGs:

CSPRNG

Standard

Used By

AES-256-CTR-DRBG

NIST SP 800-90A

OpenSSL, Linux kernel

ChaCha20

RFC 7539

/dev/urandom (Linux 4.8+)

HMAC-DRBG

NIST SP 800-90A

Java, .NET

SHAKE-256

FIPS 202

ML-KEM key generation

The Seed Problem#

A CSPRNG is only as strong as its seed. If an attacker can predict or influence the seed, all generated keys are compromised. Operating systems collect entropy from:

  • Timing jitter in hardware interrupts

  • Mouse/keyboard input timing

  • Disk I/O timing

  • CPU instruction timing (RDRAND/RDSEED on x86)

  • Thermal noise in ADCs

The Dual_EC_DRBG Backdoor

In 2013, Edward Snowden’s documents revealed that the NSA had influenced NIST to include Dual_EC_DRBG in SP 800-90A. This PRNG contained a suspected backdoor: the NSA could potentially predict outputs if they knew the relationship between two elliptic curve points in the algorithm. Dual_EC_DRBG was withdrawn from the standard in 2014. This incident demonstrates the risk of trusting PRNGs whose internal constants could be chosen adversarially.

Quantum Random Number Generation (QRNG)#

A QRNG derives randomness from fundamentally unpredictable quantum mechanical processes. Unlike PRNGs, which are deterministic, and classical TRNGs, which rely on complex-but-deterministic physical processes, QRNGs produce randomness guaranteed by the laws of quantum mechanics.

Quantum Sources of Randomness#

Method

Principle

Bit Rate

Device Requirement

Photon path

Beam splitter 50/50

~1 Gbps

Photon source + detectors

Vacuum fluctuations

Homodyne detection

~10 Gbps

Laser + balanced detector

Photon arrival time

Timing jitter

~100 Mbps

Single-photon detector

Hadamard measurement

\(|0\rangle \xrightarrow{H}\) measure

~kbps

Quantum computer

Bell test

Violation of CHSH

~bps

Entangled photon pairs

Why QRNG is Different#

The randomness in a QRNG is not due to ignorance (as in a coin flip, where randomness reflects our lack of information about initial conditions). It is intrinsic to quantum mechanics:

\[\begin{split}|0\rangle \xrightarrow{H} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \xrightarrow{\text{measure}} \begin{cases} 0 & \text{with probability } 1/2 \\ 1 & \text{with probability } 1/2 \end{cases}\end{split}\]

The measurement outcome is fundamentally unpredictable. No hidden variable, no amount of information about the quantum state, can predict which outcome will occur. This is guaranteed by:

  • The Born rule: Measurement probabilities are given by \(|\langle \psi | \phi \rangle|^2\)

  • The Kochen-Specker theorem: No deterministic hidden variable theory can reproduce all quantum predictions

  • Bell’s theorem: No local hidden variable theory can explain quantum correlations

Device-Independent QRNG

The strongest form of QRNG is device-independent: it certifies randomness through Bell inequality violations, without trusting the internal workings of the device. If the CHSH inequality \(S \leq 2\) is violated (\(S > 2\)), the outputs must be random, regardless of what hardware produces them. This is the gold standard but currently too slow for most practical applications.

Generating Quantum Random Numbers#

Using a Quantum Computer (Hadamard Method)#

The simplest QRNG circuit: apply a Hadamard gate to \(|0\rangle\) and measure.

from qiskit import QuantumCircuit
from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2

def qrng_bits(n_bits: int, backend_name: str = "ibm_brisbane") -> str:
    """Generate n_bits of quantum random bits."""
    service = QiskitRuntimeService()
    backend = service.backend(backend_name)

    qc = QuantumCircuit(n_bits, n_bits)
    qc.h(range(n_bits))          # Hadamard on all qubits
    qc.measure(range(n_bits), range(n_bits))

    sampler = SamplerV2(backend)
    job = sampler.run([qc], shots=1)
    result = job.result()

    # Extract the single measurement outcome
    counts = result[0].data.meas.get_counts()
    bitstring = list(counts.keys())[0]
    return bitstring

# Generate 128 bits of quantum randomness
bits = qrng_bits(128)
print(f"QRNG output: {bits[:32]}... ({len(bits)} bits)")

import cirq

def qrng_bits(n_bits: int) -> str:
    """Generate n_bits of quantum random bits using Cirq."""
    qubits = cirq.LineQubit.range(n_bits)
    circuit = cirq.Circuit([
        cirq.H.on_each(*qubits),
        cirq.measure(*qubits, key='result')
    ])

    # Simulate (replace with hardware sampler for real QRNG)
    simulator = cirq.Simulator()
    result = simulator.run(circuit, repetitions=1)
    bits = result.measurements['result'][0]
    return ''.join(str(b) for b in bits)

bits = qrng_bits(128)
print(f"QRNG output: {bits[:32]}... ({len(bits)} bits)")

import pennylane as qml
import numpy as np

def qrng_bits(n_bits: int) -> str:
    """Generate n_bits of quantum random bits using PennyLane."""
    dev = qml.device("default.qubit", wires=n_bits, shots=1)

    @qml.qnode(dev)
    def circuit():
        for i in range(n_bits):
            qml.Hadamard(wires=i)
        return [qml.sample(qml.PauliZ(i)) for i in range(n_bits)]

    samples = circuit()
    # PennyLane returns +1/-1; convert to 0/1
    bits = [(1 - int(s)) // 2 for s in samples]
    return ''.join(str(b) for b in bits)

bits = qrng_bits(128)
print(f"QRNG output: {bits[:32]}... ({len(bits)} bits)")

from pyquil import Program
from pyquil.gates import H, MEASURE
from pyquil.quilbase import Declare

def qrng_bits(n_bits: int) -> str:
    """Generate n_bits of quantum random bits using PyQuil."""
    p = Program()
    ro = p.declare('ro', 'BIT', n_bits)

    for i in range(n_bits):
        p += H(i)
        p += MEASURE(i, ro[i])

    p.wrap_in_numshots_loop(1)

    # Execute on QVM (replace with QPU for real QRNG)
    from pyquil import get_qc
    qc = get_qc(f"{n_bits}q-qvm")
    executable = qc.compile(p)
    results = qc.run(executable).readout_data.get('ro')

    return ''.join(str(b) for b in results[0])

bits = qrng_bits(128)
print(f"QRNG output: {bits[:32]}... ({len(bits)} bits)")

Bulk QRNG via Multi-Qubit Circuits#

For generating large amounts of entropy, use all available qubits and multiple shots:

def harvest_entropy(n_qubits: int, n_shots: int) -> bytes:
    """Harvest entropy from a quantum computer.

    Total bits = n_qubits * n_shots
    Total bytes = n_qubits * n_shots / 8
    """
    from qiskit import QuantumCircuit

    qc = QuantumCircuit(n_qubits, n_qubits)
    qc.h(range(n_qubits))
    qc.measure(range(n_qubits), range(n_qubits))

    # Execute with many shots
    # Each shot produces n_qubits bits
    # 120 qubits × 100,000 shots = 12 million bits = 1.5 MB
    ...

Statistical Testing#

Both PRNG and QRNG outputs should pass the same statistical tests. Passing tests is necessary but not sufficient for cryptographic quality: a PRNG with a known seed passes all tests despite being completely predictable.

NIST SP 800-22 Test Suite#

The standard battery for randomness testing:

Test

What It Checks

Frequency (monobit)

Equal proportion of 0s and 1s

Block frequency

Uniform distribution within blocks

Runs

Oscillation between 0 and 1

Longest run of ones

Maximum consecutive 1s in a block

Binary matrix rank

Linear dependence between bit subsequences

DFT (spectral)

Periodic features in the sequence

Non-overlapping template

Occurrences of specific patterns

Overlapping template

Sliding window pattern matching

Maurer’s universal

Compressibility (entropy estimate)

Linear complexity

LFSR complexity of subsequences

Serial

Uniformity of \(m\)-bit patterns

Approximate entropy

Regularity of pattern frequencies

Cumulative sums

Maximum deviation of partial sums

Random excursions

Deviation from random walk

Random excursions variant

Frequency of specific states in random walk

Testing in Practice#

# Using the NIST SP 800-22 tests (nistrng package)
from nistrng import run_all_battery, pack_sequence

# Test PRNG output
import os
prng_data = os.urandom(1_000_000)  # 1 MB from OS CSPRNG
results_prng = run_all_battery(pack_sequence(prng_data), test_type='all')

# Test QRNG output (from quantum hardware)
qrng_data = open("quantum_entropy_pool.bin", "rb").read(1_000_000)
results_qrng = run_all_battery(pack_sequence(qrng_data), test_type='all')

# Both should pass all 15 tests
for name, result in results_prng:
    print(f"{name}: {'PASS' if result.passed else 'FAIL'} (p={result.p_value:.4f})")

QRNG vs. PRNG: When Does It Matter?#

Scenario

PRNG Sufficient?

QRNG Recommended?

Why

Web server TLS sessions

Yes

No

Short-lived keys; OS entropy is adequate

Long-term signing keys

Yes

Yes

Key compromise has lasting impact

Root CA certificates

Yes

Yes

Multi-decade validity

Classified/military

Depends on policy

Often required

Regulatory mandate in some jurisdictions

Key generation for PQC

Yes

Yes

Belt-and-suspenders for quantum-resistant keys

Monte Carlo simulation

Yes

No

Statistical quality, not secrecy, matters

Gambling/lottery

Depends on regulation

Sometimes required

Regulatory fairness requirements

The Pragmatic View#

For most applications, a well-seeded CSPRNG (e.g., /dev/urandom on Linux) provides adequate randomness. The OS entropy pool collects from multiple hardware sources and applies cryptographic mixing.

QRNG adds value when:

  1. Regulatory requirements mandate quantum-derived entropy

  2. Defense in depth: if the CSPRNG is ever compromised (backdoor, implementation bug, weak seeding), QRNG provides an independent entropy source

  3. Long-lived keys: keys that must remain secure for decades benefit from the strongest available randomness source

  4. Symbolic value: for a PQC product, using quantum entropy for quantum-resistant key generation is a coherent security story

Hybrid Approach#

The strongest practical approach combines both:

\[\text{seed} = \text{SHAKE-256}(\text{QRNG\_bytes} \| \text{OS\_entropy} \| \text{timestamp})\]

This way, the seed is at least as strong as the strongest input. Even if QRNG hardware malfunctions (producing biased output), the OS entropy provides a floor. Even if the OS CSPRNG has a weakness, the QRNG provides independent randomness.

Entropy Rate and Min-Entropy#

Raw QRNG output may have bias due to hardware imperfections. The key metric is min-entropy, which measures the worst-case unpredictability:

\[H_{\min}(X) = -\log_2 \max_x P(X = x)\]

For a perfect coin, \(H_{\min} = 1\) bit per flip. For a biased coin with \(P(\text{heads}) = 0.6\):

\[H_{\min} = -\log_2(0.6) \approx 0.737 \text{ bits per flip}\]

Entropy Extraction#

To convert raw QRNG output (with potential bias) into uniformly random bits, use a randomness extractor:

  1. Von Neumann extractor: Pairs (0,1) \(\rightarrow\) 0; pairs (1,0) \(\rightarrow\) 1; discard (0,0) and (1,1). Simple but wastes ~75% of input.

  2. Toeplitz hashing: Multiply input by a random Toeplitz matrix. Provably extracts near-uniform bits. Used in QRNG products.

  3. SHAKE-256 conditioning: Hash raw QRNG output through a cryptographic sponge. The NIST-recommended approach for conditioning entropy sources.

Further Reading#