オデド・レゲヴ

2005年の論文でレゲヴはLWEを定式化した。ある数を法とする連立一次方程式に、それぞれ小さなランダムな誤差を加え、解を復元せよ、という問題だ。誤差がなければ中学の代数だが、誤差があると、よく研究された最悪ケースの格子問題と少なくとも同程度に難しいことが示された。量子コンピュータにも有効な手口は知られていない。同じ論文で、それに基づく暗号方式も構築している。

LWEとその構造化版は、NISTが2024年に標準化したML-KEMやML-DSA、そして完全準同型暗号の基盤となっている。2018年にはゲーデル賞を受賞。2023年にはShorのアルゴリズムより少ないゲート数で済む量子素因数分解アルゴリズムも発表しており、同じ軍拡競争の両側に貢献した珍しい例である。