How do you store infinity in 256 bits? You don’t. But you can fake it well enough that no bounded observer can tell the difference. This paper is about that deception, why it works, and what it tells us about randomness.

The impossible oracle

A random oracle maps any input to an infinite sequence of perfectly random bits. Try to implement one and you fail immediately:

1. Memory unboundedness: each new query exhausts memory
2. Non-serializability: can’t save/restore state
3. Non-reproducibility: each instance generates different values
4. Non-distributability: can’t share across systems

This isn’t a limitation of current hardware. It’s a constructive proof that true random oracles can’t exist in our computational universe.

The lie that works

From this impossibility comes something useful:

class LazyDigest:
    def __init__(self, seed):
        self.seed = seed

    def __getitem__(self, index):
        return hash(seed || index)[0]

256 bits of entropy generating what appears to be an infinite random sequence.

The deception:

• Appears: infinite random sequence
• Actually: deterministic function with 256 bits of state
• Information content: K(LazyDigest) = 256 bits + constant
• Apparent information: infinite

We’re achieving a compression ratio of infinity, representing unbounded data with bounded information.

Why it works

Computational indistinguishability. If h is a secure PRF, no polynomial-time algorithm can tell LazyDigest apart from truly random output. We’re not random. We’re computationally hard to distinguish from random. This weaker guarantee is sufficient for all of cryptography.

Since LazyDigest has finite state, it must eventually cycle. After at most 2^256 queries, it repeats. But the expected cycle length is 2^128, roughly 10^38. At a billion queries per second, cycling takes about 10^21 years. The universe is roughly 10^10 years old.

Advanced constructions

Hierarchical seeding extends the effective period:

epoch_seed = h(master_seed || "epoch" || epoch)
chunk_seed = h(epoch_seed || "chunk" || chunk)
value = h(chunk_seed || position)[0]

XOR multi-hash hedges against individual algorithm failures:

result = sha256(seed||index)[0] ^ sha512(seed||index)[0] ^
         sha3_256(seed||index)[0] ^ blake2b(seed||index)[0]

The system stays secure if at least one hash function holds. This hedges against future cryptanalysis, quantum vulnerabilities, and implementation bugs.

Sponge construction reserves capacity bits that never leave the system, providing tunable security with 2^(capacity/2) collision resistance.

Random oracles and uncomputable reals

Most real numbers are uncomputable. They require infinite information to specify. A true random oracle is the cryptographic analog:

• Computable reals (like pi, e): measure zero, finite programs
• Uncomputable reals: measure one, infinite information
• LazyDigest: computable, appears random
• Random oracle: uncomputable, truly random

We’re using computable functions to approximate uncomputable ones.