Johan Håstad
O professor do KTH que provou que dá para construir pseudoaleatoriedade a partir de qualquer função unidirecional — e que ganhou o Prêmio Gödel duas vezes.
Nascido em 1960, Håstad fez doutorado no MIT com Shafi Goldwasser, concluído em 1986. Dessa época vem o ataque que leva o seu nome: envie a mesma mensagem com RSA de expoente pequeno a destinatários suficientes e o texto em claro aparece sem chave nenhuma. Seu lema de comutação, que impôs limites rígidos ao que circuitos lógicos pequenos conseguem calcular, rendeu o Prêmio Gödel de 1994; seus resultados mostrando que certos problemas de otimização nem sequer podem ser aproximados renderam um segundo em 2011.
Para a criptografia, o peso-pesado é a construção HILL, escrita com Impagliazzo, Levin e Luby e publicada em 1999. Ela prova que um gerador pseudoaleatório existe assim que existir qualquer função unidirecional — a hipótese mais fraca que a teoria consegue se permitir. A construção é lenta demais para uso prático, o que nunca foi o objetivo.