IT lexicon › Security › Russell Impagliazzo

Russell Impagliazzo

Security På svenska → Updated: 2026-10-15

UC San Diego complexity theorist who sorted every possible universe into five, according to how much cryptography can be built in it.

In A Personal View of Average-Case Complexity (1995), Impagliazzo described five worlds: Algorithmica, where P = NP; Heuristica and Pessiland, where hard problems exist but are of no use; Minicrypt, where one-way functions exist but public-key crypto does not; and Cryptomania, where we believe we live. Nobody yet knows which one is real.

Behind the metaphor are hard results. With Luby he showed in 1989 that cryptography requires one-way functions; with Rudich, that key exchange cannot be derived from them in a black-box way; and with Håstad, Levin and Luby (HILL), that any one-way function yields a pseudorandom generator.

← Back to the lexicon