ヨハン・ホーラッド

1960年生まれのホーラッドは、1986年にMITでシャフィ・ゴールドワッサーの下で博士号を取った。この時期に生まれたのが、彼の名を冠する攻撃だ。小さな指数のRSAで同じメッセージを十分な数の受信者に送ると、鍵なしで平文が求まってしまう。小さな論理回路が計算できることに厳しい限界を与えたスイッチング補題は1994年のゲーデル賞を受け、ある種の最適化問題は近似すら難しいことを示した成果は2011年に二度目の受賞をもたらした。

暗号にとって最大の仕事は、インパリアッツォ、レヴィン、ルビーとの共著で1999年に発表されたHILL構成である。一方向性関数が一つでもあれば擬似乱数生成器が存在することを証明し、理論が置ける最も弱い仮定に到達した。構成は遅すぎて実用にならないが、もともと目的はそこではなかった。