Одед Регев (Oded Regev)
Подробнее
- Известен
- Learning With Errors (LWE), квантовый алгоритм факторизации Регева
- Место работы
- Нью-Йоркский университет
Израильский учёный, чья задача Learning With Errors легла в основу большей части постквантовой криптографии.
В статье 2005 года Регев сформулировал LWE: дана система линейных уравнений по некоторому модулю, в каждом из которых к значению добавлена малая случайная ошибка, — найти решение. Без ошибок это школьная алгебра; с ними, как он показал, задача не легче хорошо изученных задач о решётках в худшем случае, для которых у квантовых компьютеров тоже нет известного трюка. Там же он построил на её основе схему шифрования.
LWE и её структурированные варианты лежат в основе ML-KEM и ML-DSA, стандартов NIST 2024 года, а также полностью гомоморфного шифрования. В 2018 году Регев получил премию Гёделя. В 2023-м он опубликовал и квантовый алгоритм факторизации с меньшим числом вентилей, чем у Шора, — редкий вклад в обе стороны одной гонки вооружений.