Randomness that has to be earned

The previous rung breaks every linear generator with three outputs and a division. The obvious next question is what a generator would have to be like to resist that, and the answer turns out to be a statement about complexity rather than about arithmetic.

A rule that can be fitted from its outputs is not a generator anybody should rely on, and fitting is what linear algebra does. So the rule must be non-linear in a way that makes the fitting problem itself hard — and “hard” then has to mean something precise.

Squaring, and what it defeats #

Take two primes $p$ and $q$, both $3 \bmod 4$, set $m = pq$, and iterate

$$x \mapsto x^2 \bmod m.$$

Output one bit of each state — its parity.

Two things have changed from a linear generator and only the first is obvious.

The relation between consecutive states is quadratic, so the outputs impose quadratic rather than linear equations on the unknowns, and solving a system of quadratic congruences modulo a composite is not something anybody knows how to do quickly.

The choice of primes congruent to three modulo four is not cosmetic. It makes $-1$ a non-square modulo each of them, which makes squaring a permutation of the squares modulo $m$ — so the iteration is reversible on its own orbit and has no short cycles or absorbing states. Without that condition the map would collapse states together and the period would be unpredictable, which is a different defect from the one the construction is about and would have to be dealt with separately. It is the first supplement of quadratic reciprocity doing engineering work.

And the parity of the square root is exactly as hard as the whole problem. That is the substantial theorem. Predicting the output bit better than chance would give an algorithm for deciding whether a number is a square modulo $m$, which would give an algorithm for factoring $m$. So the generator is strong if factoring is hard, and the conditional is the theorem’s content.

What “provably secure” promises #

The phrase is used loosely and the precise statement is worth having.

A generator is provably secure under an assumption when there is a reduction: an efficient procedure that, given any efficient predictor for the generator, produces an efficient algorithm for the assumed-hard problem. So if the problem is hard, no predictor exists.

Three features of that shape deserve attention.

It is a contrapositive. Nothing is proved about the generator directly; what is proved is that breaking it is at least as difficult as something else. The security is inherited.

The reduction’s efficiency matters quantitatively. A reduction is a transformation of algorithms, and a transformation costs something. One that turns a predictor running in time $T$ into a factoring algorithm running in time $T^6$ gives a much weaker guarantee than one giving $2T$, because the parameters have to be chosen so that $T^6$ is still infeasible. Reductions are compared by tightness, and a loose reduction is a real cost.

And the assumption is not a theorem. Factoring is believed hard, on the evidence of several centuries of attempts and no proof. If it turned out to be easy, the reduction would still be correct and the generator would be broken. That is not hypothetical for this particular assumption: a quantum computer of sufficient size factors in polynomial time by Shor’s algorithm, so the conditional here is known to fail against an adversary nobody currently has — which is why the constructions being standardised now rest on different assumptions.

The hard-core bit, which is the real theorem #

The step deserving most attention is the one that says the parity of the state is as hard as the whole state, because it is not obvious and it is the pattern the whole subject uses. Every construction of a strong generator, from any assumption whatever, has this shape somewhere in it.

A one-way function is easy to compute and hard to invert. That does not immediately give a generator: knowing that $x$ is hard to recover from $f(x)$ says nothing about whether some bit of $x$ is easy to guess, and a generator outputs bits.

A hard-core bit of a one-way function is a bit of the input that is as hard to guess as the whole input is to compute. Goldreich and Levin proved that every one-way function has one — take the parity of a random subset of the input’s bits — so the gap between “hard to invert” and “usable as a generator” closes in general, not only for squaring.

For squaring modulo a composite the hard-core bit is the parity of the square root, and the proof is a reduction: an algorithm guessing that parity with any advantage can be turned, by a binary search over the modulus, into an algorithm computing square roots, hence into one factoring $m$.

That reduction is the whole construction. Everything else — the choice of primes congruent to three modulo four, the fact that squaring is a permutation on the squares — is bookkeeping to make the reduction go through cleanly.

Why an assumption is unavoidable #

It is natural to ask for a generator that is strong outright, with no assumption. There is a short argument that nobody can have one, at least not without settling the central open problem of the subject.

A generator with a state of $n$ bits and output much longer than $n$ has outputs that form a tiny subset of all possible strings. Deciding membership of that subset is a question with a short certificate — the seed — so it belongs to the class of problems whose answers are checkable quickly. If every such problem were also solvable quickly, the subset would be recognisable and the generator distinguishable.

So the existence of a strong generator implies that checkable and solvable are different, which is the famous open question. Proving a generator strong unconditionally would settle it, and nobody expects that to happen by way of a generator.

The argument is worth restating as an accounting, since it is easy to lose. The generator maps $n$ bits of seed to $N \gg n$ bits of output, so at most $2^n$ of the $2^N$ possible strings arise — a fraction of $2^{n-N}$, which is astronomically small. A string that arises has a short proof that it does: exhibit the seed. So the set of outputs is exactly the kind of set whose membership is easy to verify and, by assumption, hard to decide, and a generator is a witness that those two are different. It is the same shape of argument that makes an impossibility a statement about what a method can reach rather than about what anybody has tried.

That is a useful thing to know because it converts an apparent gap in the subject into a theorem about the shape of the subject. The conditionality is not a temporary state of the art; it is forced.

The two families, and the trade #

In practice there are two kinds of strong generator and they sit at opposite ends of a trade-off.

Number-theoretic constructions — squaring modulo a composite, exponentiating modulo a prime, and their relatives — come with reductions to problems that have been studied for a very long time. They are slow: each output bit costs a modular multiplication on numbers of thousands of bits.

Symmetric constructions — a block cipher run in counter mode, a hash function iterated — come with no reduction to anything, because there is nothing underneath them to reduce to. Their security rests on the primitive resisting attack, which is evidence of a different kind: decades of concentrated public attempts by people rewarded for succeeding. They are fast, by a factor of several thousand, and the reason is arithmetic: a block cipher does a few dozen bit operations per output bit and a modular squaring does thousands.

Almost every deployed system uses the second, and the choice is deliberate rather than ignorant. A guarantee conditional on factoring is worth less than it sounds if it costs a thousandfold slowdown that forces the system to generate less randomness than it needs.

Putting the two figures beside each other is the clearest statement of the design. The linear generator’s attacker solves a system; the squaring generator’s attacker would have to solve a harder one, and the entire security is that “harder” has a precise meaning and has been tested for a long time. Nothing about the squaring generator is cleverer in construction; it is simply built on an operation whose inverse nobody can compute.

What a strong generator still does not give #

Three limits, and the first two are where real systems fail.

The seed has to come from somewhere. Every generator above turns a short secret into a long stream, and the stream is only as unpredictable as the secret. A generator seeded from a clock has as many possible outputs as the clock has readings, whatever its internal construction, and searching a day’s worth of milliseconds is a hundred million tries. Most famous failures of “cryptographic” generators are seeding failures rather than failures of the generator, and the reduction says nothing about them because it assumes the seed is uniform.

The state has to stay secret. Reading the state predicts everything afterwards, and — for a generator without extra machinery — everything before it as well. Modern designs add forward secrecy by ratcheting the state, which is a repair for a threat the definition does not mention.

Randomness is consumed and has to be replaced. A long-running system draws from its generator continuously, and the guarantees are stated per instantiation. Practical designs reseed periodically from fresh entropy, which changes the object from a generator into a protocol and puts most of the real difficulty into the reseeding schedule rather than into the arithmetic.

And the definition is about efficient adversaries. An adversary with unlimited time enumerates the seeds. That is not a practical concern and it is a reminder that the whole subject is about resource bounds rather than about information: the output of a strong generator carries no more information than its seed, and the security is that nobody can extract it in time.

The other kind of guarantee #

There is a second thing a generator can be measured against, and it is exact rather than conditional.

Equidistribution asks that every pattern of a given length occur equally often over the generator’s full period. That is a combinatorial property of the sequence, provable by counting, with no assumptions in it at all.

The Mersenne twister is designed against exactly this criterion, and achieves it to six hundred and twenty-three dimensions at thirty-two bits — meaning that six hundred and twenty-three consecutive outputs, taken at full precision, hit every possible combination equally often over the period. That is an enormous and exactly proved property — and the generator is not cryptographically strong, being linear over the field of two elements and therefore solvable from about two thousand five hundred outputs by the linear algebra of the previous rung.

So the two guarantees are independent again, in exactly the way the first two rungs of this ladder are. A generator can be provably equidistributed and trivially predictable, or unpredictable under an assumption and mediocre at equidistribution. Which matters depends entirely on the use.

What was believed before #

The construction dates from 1982 — Blum, Blum and Shub — and the shift it represents is worth stating, because it is a change in what the word random was taken to mean.

Before it, a pseudorandom generator was something that passed tests. The tests were chosen by judgement, the list grew whenever somebody found a new failure, and the claim a generator made was always of the form “it passed these”. The spectral test was the strongest instrument of that era and it is a measurement of one specific structure.

Blum and Micali, and then Yao, replaced the list with a quantifier. A generator is good when no efficient procedure whatever can tell it from random, and that definition cannot be gamed by passing more tests because it already quantifies over all of them.

Two consequences followed immediately and are worth separating.

The definition made the subject provable. Once “good” is a statement about all efficient procedures, a reduction can establish it — which is what turned pseudorandomness from an engineering practice into a branch of complexity theory.

And it made most existing generators visibly inadequate, not by finding a new failure but by changing the standard. A linear generator does not fail the new definition on a technicality; it fails by three lines of algebra, and its earlier good standing was a statement about which tests had been thought of.

What the pictures cannot show #

Absence of structure is drawn as absence, which every scatter of noise looks like. The figure of a strong generator is a grey square, and so is a figure of genuinely random points, and so would be a figure of a generator broken by a structure the search does not look for. What the figure establishes is that no relation with small coefficients holds; it cannot establish that no relation of any kind does.

The hardness is nowhere in any picture. Everything about this rung is a statement about what no efficient procedure achieves, which is a quantifier over algorithms. Pictures show one generator’s output; the claim is about every possible attack on it.

The equidistribution table is exact and small. It reports a register of ten bits with a period of a thousand and twenty-three, where every count can be taken. The generators the property is claimed for have periods of $2^{19937}$, where nothing can be counted and the property is established by an algebraic argument about the recurrence’s characteristic polynomial.

And the reduction is a proof, not a construction anybody runs. The theorem says a predictor could be turned into a factoring algorithm. No such predictor is known, so the transformation has never been performed, and the figure of it would be a figure of a procedure with no input.

Where the ladder goes next #

The last rung on this ladder looks at the generators actually shipped, and at the exact property they are designed against rather than the conditional one: the generator with nineteen thousand bits of state.

Named here as a debt: randomness extraction — turning a weak physical source with some unpredictability into uniform bits — which is where a seed comes from and is a subject with its own theorems, none of them above.

Also named as a debt: the ratchet, the standard repair that makes a compromised state not reveal the past, which every deployed generator has and no definition on this rung mentions.

Sideways, the arithmetic modulo a composite is the Chinese remainder theorem’s setting, the linear solve this construction defeats is the previous rung’s, and the lattice quality measure that says nothing about any of this is the rung below that.

What is worth carrying away #

Unpredictability cannot be constructed; it can only be transferred from something already believed hard.

Every strong generator is a machine for converting the difficulty of one specific problem into the difficulty of predicting a stream, and the conversion is a proof while the difficulty is a belief. That is not a weakness of the constructions — it is forced, since an unconditional construction would settle the central open question of complexity — and knowing it is forced changes how the guarantees should be read.

The habit worth taking is to ask what a security claim is conditional on. “Provably secure” always ends in a clause, the clause names a problem, and the whole value of the claim is however much confidence that problem deserves.