Регев, Одед

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
В Википедии есть статьи о других людях с фамилией Регев.
Одед Регев
Дата рождения 1978
Место работы
Альма-матер
Научный руководитель Йоси Азар[de]
Награды и премии

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

Биография[править | править код]

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

Научная работа[править | править код]

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

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

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

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

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

Алгоритм Регева[править | править код]

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

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

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

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

Награды и премии[править | править код]

Примечания[править | править код]

  1. ↑ Mathematics Genealogy Project (англ.) — 1997.
  2. ↑ Faculty listing, Courant Institute of Mathematical Sciences, accessed 2019-06-25.
  3. ↑ School of Computer Science Thesis Repository, Tel-Aviv University, accessed 2019-06-25.
  4. ↑ https://www.aftau.org/2013-redesign/pages/tau/spotlights/blavatnik-school-of-computer-science#alumniSay.  (недоступная ссылка)
  5. ↑ http://primage.tau.ac.il/libraries/theses/exeng/free/1509397_abe.pdf. Архивировано 23 июля 2019 года.
  6. ↑ Oded Regev. Simons Foundation (5 октября 2014).
  7. ↑ http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize
  8. ↑ IACR Publication Awards. www.iacr.org.
  9. ↑ Nguyen, Phong Q.; Regev, Oded (2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". Journal of Cryptology. 22 (2): 139—160. doi:10.1007/s00145-008-9031-0. ISSN 0933-2790. S2CID 2164840.
  10. ↑ Lyubashevsky, Vadim. On Ideal Lattices and Learning with Errors over Rings // Advances in Cryptology – EUROCRYPT 2010 / Vadim Lyubashevsky, Chris Peikert, Oded Regev. — 2010. — Vol. 6110. — P. 1–23. — ISBN 978-3-642-13189-9. — doi:10.1007/978-3-642-13190-5_1.
  11. ↑ Regev, Oded; Stephens-Davidowitz, Noah (2017), A reverse Minkowski theorem, Annual ACM SIGACT Symposium on Theory of Computing, Montreal, Quebec, Canada, pp. 941—953, arXiv:1611.05979{{citation}}: Википедия:Обслуживание CS1 (отсутствует издатель) (ссылка)
  12. ↑ Dadush, Daniel. Towards Strong Reverse Minkowski-Type Inequalities for Lattices // 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) / Daniel Dadush, Oded Regev. — 2016. — P. 447–456. — ISBN 978-1-5090-3933-3. — doi:10.1109/FOCS.2016.55.
  13. ↑ Oded Regev.
  14. ↑ Oded Regev. scholar.google.com.
  15. ↑ List of editors, Theory of Computing, accessed 2019-06-25.
  16. ↑ TCS+. sites.google.com.
  17. ↑ 1 2 Regev, Oded (2023). "An Efficient Quantum Factoring Algorithm". arXiv:2308.06572. {{cite journal}}: Cite journal требует |journal= (справка)
  18. ↑ 1 2 'Surprising and super cool.' Quantum algorithm offers faster way to hack internet encryption (Report) (англ.). 2023-09-19. doi:10.1126/science.adk9418.
  19. ↑ 1 2 Brubaker, Ben Thirty Years Later, a Speed Boost for Quantum Factoring (англ.). Quanta Magazine (17 октября 2023). Дата обращения: 18 октября 2023.
  20. ↑ Ragavan, Seyoon; Vaikuntanathan, Vinod (2023). "Optimizing Space in Regev's Factoring Algorithm". arXiv:2310.00899. {{cite journal}}: Cite journal требует |journal= (справка)
  21. ↑ http://www.wolffund.org.il/index.php?dir=site&page=winners&cs=565  (недоступная ссылка)
  22. ↑ 2018 Gödel Prize. Дата обращения: 12 апреля 2018. Архивировано 5 октября 2018 года.
  23. ↑ Simons Investigators. Simons Foundation (10 июля 2018).
  24. ↑ The Silver Professors

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Регев,_Одед&oldid=136856520