Johan Håstad
Le professeur du KTH qui a prouvé qu'on peut fabriquer du pseudo-aléa à partir de n'importe quelle fonction à sens unique — et qui a remporté deux fois le prix Gödel.
Né en 1960, Håstad a fait son doctorat au MIT sous la direction de Shafi Goldwasser, achevé en 1986. Cette période a produit l'attaque qui porte son nom : envoyez le même message en RSA avec un petit exposant à suffisamment de destinataires, et le texte clair tombe sans aucune clé. Son lemme de commutation, qui fixait des limites strictes à ce que de petits circuits logiques peuvent calculer, lui a valu le prix Gödel en 1994 ; ses résultats montrant que certains problèmes d'optimisation ne sont même pas approximables lui en ont valu un second en 2011.
Pour la cryptographie, le poids lourd est la construction HILL, écrite avec Impagliazzo, Levin et Luby et publiée en 1999. Elle prouve qu'un générateur pseudo-aléatoire existe dès qu'existe une fonction à sens unique — l'hypothèse la plus faible dont la théorie puisse se contenter. La construction est bien trop lente pour servir, ce qui n'a jamais été le but.