Johan Håstad
De KTH-hoogleraar die bewees dat pseudowillekeurigheid te bouwen is uit welke eenrichtingsfunctie dan ook, en die de Gödelprijs tweemaal won.
Håstad, geboren in 1960, promoveerde in 1986 aan MIT bij Shafi Goldwasser. Uit die periode stamt de aanval die zijn naam draagt: wie hetzelfde bericht met RSA en een kleine exponent naar genoeg ontvangers stuurt, geeft de klare tekst prijs zonder dat er een sleutel nodig is. Zijn switching lemma, dat harde grenzen stelde aan wat kleine logische circuits kunnen berekenen, leverde in 1994 de Gödelprijs op; zijn resultaten dat sommige optimalisatieproblemen zelfs niet te benaderen zijn, brachten in 2011 een tweede.
Voor de cryptografie is de HILL-constructie het zwaargewicht, geschreven met Impagliazzo, Levin en Luby en gepubliceerd in 1999. Zij bewijst dat een pseudowillekeurige generator bestaat zodra er één eenrichtingsfunctie bestaat — de zwakste aanname die de theorie zich kan permitteren. De constructie is veel te traag voor gebruik, maar dat was ook nooit de bedoeling.