Регев, Одед

Шаблон:Однофамильцы Шаблон:Учёный Одед Регев (Шаблон:Lang-he; Шаблон:ВД-Преамбула) — израильско-американский учёный, теоретик информатики и математик. Лауреат премии Гёделя. Профессор информатики в Курантовском институте при Нью-Йоркском университете. Наиболее известен своими работами в области решётчатой криптографии, в частности постановкой задачи обучения с ошибками (LWE), криптоанализом схем Шаблон:Нп5 и NTRUSign, а также разработкой нового квантового алгоритма по факторизации чисел, превосходящего по эффективности алгоритм ШораШаблон:Переход.

Биография

В 1995 году Одед Регев получил степень бакалавра наук. В 1997 году получил степень магистра наук и доктора философии. В 2001 году защитил докторскую диссертацию в Тель-Авивском университете на тему «Планирование и балансировка нагрузки», его научным руководителем был Шаблон:Нп5. До перехода в Курантовский институт, в котором он работает сейчас, Одед преподавал в Тель-Авивском университете и Высшей нормальной школе Парижа.

Научная работа

Регев проделал обширную работу в теории решёток и криптографии. Стал известен после постановки задачи обучения с ошибками (Шаблон:Lang-en), за которую получил премию Гёделя.

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

Другими влиятельными работами Регева являются криптоанализ схем Шаблон:Нп5 и NTRUSign в совместной работе с Фонгом К. Нгуеном, за которые они получили награду на Eurocrypt в 2006 году, а также постановка проблемы Шаблон:Нп5 для постквантовой криптографии в совместной работе с Крисом Пейкертом и Вадимом Любашевским и доказательство обратной теоремы Минковского о выпуклом теле и исследование её приложений в совместных работах со своим учеником Ноем Стивенсом-Давидовицем и его бывшим постдоком Дэниелом Дадушем.

Помимо работ по криптографии, Регев также внёс вклад во многие другие области теоретической информатики и математики, такие как квантовые вычисления, коммуникационная сложность, сложность аппроксимации, Шаблон:Нп5, комбинаторика, теория вероятностей и снижение размерности. Недавно он также заинтересовался вопросами биологии, в частности сплайсингом РНК.

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

Алгоритм Регева

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

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

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

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

Награды и премии

• Премия Криля (2005)
• Премия Eurocrypt (2006)
• Премия Гёделя (2018)
• Шаблон:Нп5 (2019)
• Серебряный профессор (2022)

Ссылки

• Сайт Регева
• Шаблон:YouTube.