Miklós Ajtai
Ungarischer Mathematiker bei IBM Almaden, der 1996 bewies, dass manche Gitterprobleme im Durchschnitt schwer sind, wenn sie im schlimmsten Fall schwer sind — das Fundament der modernen Gitterkryptografie.
Die Kryptografie braucht zufällig gewählte Instanzen, die schwer sind, während die Komplexitätstheorie fast immer von den schwersten Instanzen spricht. Ajtais Arbeit Generating Hard Instances of Lattice Problems (1996) schlug die Brücke: Eine zufällige Instanz zu brechen wäre so schwer, wie jede Instanz zu lösen. Für Faktorisierung oder diskrete Logarithmen hat bisher niemand etwas Vergleichbares geschafft.
Im Jahr darauf entwarf er mit Cynthia Dwork das Ajtai–Dwork-Kryptosystem — unpraktisch, aber prinzipiell bedeutsam. Zuvor hatte er dem AKS-Sortiernetzwerk (1983) mit Komlós und Szemerédi seinen Anfangsbuchstaben geliehen. 2003 erhielt er den Knuth-Preis.