Uniform and non-uniform adversaries

A uniform adversary is a single probabilistic polynomial-time machine that plays the game at every security parameter; a non-uniform adversary is a family of polynomial-size circuits, one for each security parameter, equivalently a polynomial-time machine that also receives an advice string of polynomial length depending only on the security parameter — standard.

Uniform adversaries

A uniform adversary is a probabilistic Turing machine together with a polynomial such that, on input and the game’s other inputs, halts within steps: a algorithm.

Non-uniform adversaries

A non-uniform adversary is a family of circuits with for a polynomial , where plays the game at security parameter and reads any random coins from extra input wires. Equivalently, is a polynomial-time machine run on for an advice sequence with , which need not be computable — standard; see poly.

In a game whose admissibility conditions constrain each run of the adversary rather than the distribution of its outputs, coins give a non-uniform adversary nothing. The winning probability of is an average over its coins, so some fixed coin string attains at least the average in a search game, and in a bit-guessing game a winning probability at least as far from ; hard-wiring it gives a deterministic circuit of the same size and at least the same advantage — folklore. Removing the coins of a decision procedure that must be correct on every input takes more: amplify its success probability, then fix one random string that is good for all inputs of length by a union bound, which is the argument for poly — Adl78 for , BG81 for .

Relation between the notions

A circuit of size polynomial in the running time of a uniform adversary simulates it at each , so security against all non-uniform adversaries implies security against all uniform ones — standard; for computational indistinguishability, Gol01.

The converse fails for unkeyed objects if some unkeyed compressing function is collision resistant against uniform adversaries. An unkeyed compressing family has collisions at every , and the circuit that outputs a hard-wired collision of has size and always wins, so no unkeyed function is collision resistant against non-uniform adversaries — Rog06. A uniform adversary is one program for all and cannot hard-wire a collision for each, so this argument says nothing against it — standard.

A uniform black-box reduction, an oracle machine that uses the adversary only as an oracle, proves both readings of a theorem: run with a non-uniform adversary it is a non-uniform adversary against the assumption — standard. A reduction that hard-wires information depending on the adversary — its best coins, the most useful index of a hybrid argument, samples from a distribution it cannot sample efficiently — proves only the non-uniform reading, from non-uniform hardness of the assumption — standard.

Encryption and zero knowledge have a uniform-complexity theory of their own: against uniform adversaries the two definitions of security of GM84, semantic security and indistinguishability of encryptions, remain equivalent, and uniform zero knowledge asks that nothing leak on instances chosen by an efficient algorithm rather than on every instance — Gol93.

Which notion this site uses

Pages write for all efficient without fixing the model, and computational indistinguishability is defined under both readings. A theorem proved by a uniform black-box reduction holds under either; a page that needs one reading states it, as time-lock puzzles do for non-uniform circuit families whose depth measures parallel time.

Auxiliary input and composition

Zero knowledge is defined against verifiers with an auxiliary input : for every efficient there is an efficient such that the ensembles and , indexed by , witness for and , are computationally indistinguishable — GO94. Unlike advice, may depend on . In a sequential composition the verifier’s view of the earlier sessions is part of its input in the later ones; auxiliary-input zero knowledge is preserved under sequential composition — GO94 — and the definition without auxiliary input is not — GK96a.

Composition proofs in general fix the state of the surrounding execution inside a distinguisher or adversary for one component, and so need non-uniform security of that component or a reduction that regenerates the state efficiently — standard. For the same reason, indistinguishability of one sample extends to polynomially many independent samples for non-uniform distinguishers without efficient sampleability — Gol01.

Concrete security and precomputation

Against circuits of a fixed size, advice can hold the result of a precomputation far more expensive than the circuit, and the concrete security conjectured for standard primitives, among them AES and elliptic-curve discrete logarithms, fails against non-uniform adversaries of the conjectured size — BL13a. Idealized models capture the effect by preprocessing, in which an unbounded algorithm computes advice of bounded length from the oracle: in the generic group model with preprocessing, bits of advice and online queries solve discrete logarithms in a group of prime order with probability only if (GGM with preprocessing ⇒ DLOG) — CK18.