Одед Регев (ивр. עודד רגב‎; род. 1978) — израильско-американский учёный, теоретик информатики и математик. Лауреат премии Гёделя. Профессор информатики в Курантовском институте при Нью-Йоркском университете^[2]. Наиболее известен своими работами в области решётчатой криптографии, в частности постановкой задачи обучения с ошибками (LWE), криптоанализом схем GGH^[англ.] и NTRUSign, а также разработкой нового квантового алгоритма по факторизации чисел, превосходящего по эффективности алгоритм Шора➤.

В 1995 году Одед Регев получил степень бакалавра наук. В 1997 году получил степень магистра наук и доктора философии. В 2001 году защитил докторскую диссертацию в Тель-Авивском университете на тему «Планирование и балансировка нагрузки», его научным руководителем был Йоси Азар^{[нем.][3][4][5]}. До перехода в Курантовский институт, в котором он работает сейчас, Одед преподавал в Тель-Авивском университете и Высшей нормальной школе Парижа^[6].

Регев проделал обширную работу в теории решёток и криптографии. Стал известен после постановки задачи обучения с ошибками (англ. Learning with errors, LWE), за которую получил премию Гёделя^[7].

Работа Регева положила начало революции в криптографии, как в теории, так и на практике. С теоретической точки зрения LWE послужил простой и в то же время универсальной основой практически для любого типа криптографических объектов, которые только можно вообразить, а также для многих из них, которые до недавнего времени были немыслимы и которые до сих пор не имеют известных конструкций без LWE. С практической точки зрения LWE и его прямые потомки лежат в основе нескольких эффективных реальных криптосистем.

Другими влиятельными работами Регева являются криптоанализ схем GGH^[англ.] и NTRUSign в совместной работе с Фонгом К. Нгуеном, за которые они получили награду на Eurocrypt в 2006 году, а также постановка проблемы кольцевого обучения с ошибками^[англ.] для постквантовой криптографии в совместной работе с Крисом Пейкертом и Вадимом Любашевским и доказательство обратной теоремы Минковского о выпуклом теле и исследование её приложений в совместных работах со своим учеником Ноем Стивенсом-Давидовицем и его бывшим постдоком Дэниелом Дадушем^{[8][9][10][11][12]}.

Помимо работ по криптографии, Регев также внёс вклад во многие другие области теоретической информатики и математики, такие как квантовые вычисления, коммуникационная сложность, сложность аппроксимации, онлайн-алгоритмы^[англ.], комбинаторика, теория вероятностей и снижение размерности. Недавно он также заинтересовался вопросами биологии, в частности сплайсингом РНК^[13][14].

Регев — заместитель главного редактора журнала «Теория вычислений», а также соучредитель и организатор серии онлайн-семинаров TCS+^[15][16].

В августе 2023 года Регев опубликовал новый квантовый алгоритм по факторизации чисел, превосходящий по эффективности алгоритм Шора^[17][18][19].

Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией. Ему удалось обобщить алгоритм на произвольное количество измерений, а не только на два, в результате чего для факторизации чисел квантовому компьютеру требуется гораздо меньше логических шагов. Специалисты по квантовыми вычислениями отмечают, что удивительно и неожиданно, что спустя 30 лет кто-то смог качественно улучшить алгоритм Шора^[17][18][19].

Алгоритм Регева использует ${\displaystyle \sim O(n^{3/2})}$ квантовых вентилей, что более эффективно, чем в алгоритме Шора, в котором используется ${\displaystyle \sim O(n^{2})}$ квантовых вентилей, хотя для реализации алгоритма Регева требуется потребуется больше кубитов квантовой памяти ${\displaystyle \sim O(n^{3/2})}$, в то время как а алгоритме Шора их используется ${\displaystyle \sim O(n)\ }$.

Позже был предложен вариант оптимизации алгоритма Регева, в котором было показано, что можно уменьшить пространство используемой квантовой памяти примерно до того же уровня, что и в алгоритме Шора^[20].

• Премия Криля (2005)^[21]
• Премия Eurocrypt (2006)
• Премия Гёделя (2018)^[22]
• Simons Investigator^[англ.] (2019)^[23]
• Серебряный профессор (2022)^[24]

• Сайт Регева
• Computer Science - 2023's Biggest Breakthroughs (англ.) на YouTube.