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:
- Memory unboundedness: each new query exhausts memory
- Non-serializability: can't save/restore state
- Non-reproducibility: each instance generates different values
- 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.
The parallel with pi is instructive. We can compute any digit of pi using a finite algorithm (Bailey-Borwein-Plouffe formula). Finite description, infinite output, computed on demand. LazyDigest does the same thing. The difference is semantic: pi encodes geometric relationships, LazyDigest encodes computational hardness. Both achieve the same compression: finite program to infinite sequence.
Two kinds of randomness
There are two incompatible definitions of randomness:
- Information-theoretic: high Kolmogorov complexity
- Computational: indistinguishable from random by efficient algorithms
LazyDigest fails (1) catastrophically. It has tiny Kolmogorov complexity, just 256 bits plus the hash function definition.
LazyDigest passes (2) perfectly, assuming secure hash functions.
The insight: "randomness" in cryptography is actually computational hardness in disguise. We don't generate randomness. We generate a computationally hard problem and bet that nobody can solve it.
Entropy and computational bounds
Consider Laplace's demon, a being with unlimited computational power. To it, LazyDigest is trivially non-random, just compute h(seed||i). No entropy exists, only deterministic evolution.
But we are computationally bounded, and that boundedness creates our entire experience of randomness. The past is fixed (we remember it). The future is uncertain (we can't compute fast enough to predict it). Entropy increases (we can't invert dynamics). Randomness exists (we can't distinguish it from true randomness).
A hash function is a one-way time machine. Forward: h(x) is easy. Backward: finding x given h(x) is computationally infeasible.
The P != NP bet
Every use of LazyDigest implicitly bets that P != NP. If P = NP, we could invert the hash function in polynomial time and distinguish LazyDigest from random output. We're not generating randomness. We're generating a hard problem and hoping nobody solves it.
The constructivist angle
I think the most interesting part is what this says about mathematics. Classical mathematics posits incoherent infinities and uncomputable reals as real objects. LazyDigest represents a constructivist alternative: a finite, computable object that serves all practical purposes of an infinite random sequence.
The deception is honest:
- We don't claim infinite objects. We have finite programs generating unbounded output.
- We don't pretend uncomputable things exist. We work with computable approximations.
- We don't hide behind axioms. We build finite machines and study their behavior.
Cryptography forces you to be a constructivist. The boundary of cryptographic possibility is precisely the boundary of computational constructibility.
In a universe that may itself be computational, LazyDigest isn't approximating some "true" random oracle in a Platonic realm. It may be as real as randomness gets.
Key takeaways
- True random oracles are impossible to implement (proven constructively)
- LazyDigest uses 256 bits to simulate infinity through computational hardness
- "Randomness" in cryptography means computationally indistinguishable from random
- The deception works because we're all computationally bounded observers
- This is a constructivist approach to mathematics and computation
