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

Биография

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Ссылки

• на YouTube .