Miklós Ajtai
1996’da bazı kafes problemlerinin en kötü durumda zorsa ortalamada da zor olduğunu kanıtlayan, IBM Almaden’deki Macar matematikçi; modern kafes kriptografisinin temeli.
Kriptografi rastgele seçilmiş örneklerin zor olmasını ister; karmaşıklık kuramı ise neredeyse hep en zor örneklerden söz eder. Ajtai’nin Generating Hard Instances of Lattice Problems (1996) makalesi bu boşluğu kapattı: rastgele bir örneği kırmak, tüm örnekleri çözmek kadar zor olacaktı. Çarpanlara ayırma ya da ayrık logaritma için kimse benzerini başaramamıştı.
Ertesi yıl Cynthia Dwork’le Ajtai–Dwork kriptosistemini kurdu; pratik değildi ama ilke olarak önemliydi. Daha önce Komlós ve Szemerédi’yle yazdığı AKS sıralama ağına (1983) baş harfini vermişti. 2003’te Knuth Ödülü’nü aldı.