Johan Håstad
KTH-professorn som visade att man kan bygga pseudoslump av vilken envägsfunktion som helst — och som fått Gödelpriset två gånger.
Håstad, född 1960, doktorerade vid MIT 1986 med Shafi Goldwasser som handledare. Redan där publicerade han attacken som bär hans namn: skickas samma meddelande RSA-krypterat med litet exponent till tillräckligt många mottagare går det att räkna fram klartexten utan någon nyckel. Hans switching lemma om gränser för små logiska kretsar gav Gödelpriset 1994, och resultaten om att vissa optimeringsproblem inte ens går att approximera gav ett andra 2011.
För kryptografin väger HILL-konstruktionen tyngst, skriven med Impagliazzo, Levin och Luby och publicerad 1999. Den bevisar att en pseudoslumpgenerator finns så snart någon envägsfunktion finns — det minsta antagande teorin kan klara sig på. Konstruktionen är för långsam att använda, vilket aldrig var poängen.