Теоретико-сложностные основы криптографии, эвристические алгоритмы и сложность в среднем

Теоретико-сложностные основы криптографии, эвристические алгоритмы и сложность в среднем

Современные криптографические задачи разнообразны: шифрование с открытым ключом, цифровые подписи, распределённые вычисления, где участники не узнают ничего о вычислениях других участников и т.д. Существование надёжных протоколов, однако, ничем не гарантировано: используемые конструкции “просто никто не умеет взламывать”.

Сложностная криптография формализует понятия надёжности, показывает, как из надёжных примитивов собираются надёжные протоколы. Это не гарантирует, что протоколы не будут взломаны (ведь надёжность примитивов не доказана - мы даже не умеем доказывать, что P≠NP), но, по крайней мере, позволяет работать с этими задачами с точки зрения теории сложности вычислений. Следует отметить, что существующие определения вовсе не идеальны, и даже в основаниях этой науки есть поле для исследований.

Потенциальный взлом, которого мы хотим избежать в криптографии, не ограничивается взломом “в наихудшем случае”: чаще всего нет необходимости взламывать протокол во всех ситуациях; взлома “в среднем” или “в заметном числе случаев” вполне достаточно, чтобы нарушить работу. Поэтому криптографии близки сложность в среднем, эвристическая сложность - несколько более современные разделы теории сложности вычислений, где изучаются вычисления, которые могут ошибаться или очень долго работать на некоторых входах.

 

Сотрудники кафедры: 

Э.А.ГиршД.М.ИцыксонА.А.КнопД.О.Соколов

 

Публикации сотрудников кафедры

  1. D. Grigoriev, E. A. Hirsch, K. Pervyshev, A Complete Public-Key Cryptosystem. Groups, Complexity, Cryptology 1(2009).
  2. D. Grigoriev, E. A. Hirsch, K. Pervyshev, Time hierarchies for cryptographic function inversion with advice. ECCC Report TR05-076. Русская версия: Записки научных семинаров ПОМИ 358(2008): 54-76.
  3. E. A. Hirsch, D. M. Itsykson, An infinitely-often one-way function based on an average-case assumption. ECCC Report TR07-117. Proceedings of WoLLIC'08, LNCS 5110, Springer, pp.208-217. Русская версия: Алгебра и анализ 21(3):129-143, 2009.
  4. E. A. Hirsch, D. Itsykson, I. Monakhov, A. Smal. On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Theory of Computing Systems 51(2):179-195, 2012; DOI 10.1007/s00224-011-9354-3.
  5. E. A. Hirsch, D. Itsykson, V. Nikolaenko, A. Smal. Optimal heuristic algorithms for the image of an injective function. Записки научных семинаров ПОМИ 399:15-31 (2012).
  6. D. Itsykson, A. Knop, D. Sokolov. Complexity of distributions and average-case hardness. ECCC Report TR15-174.
  7. D. Itsykson, A. Knop and D. Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. ECCC Report TR14-178 Proceedings of ISAAC 2015.
  8. D. Itsykson and D. Sokolov. On fast non-deterministic algorithms and short heuristic proofs. Fundamenta Informaticae, 132(1):113-129, 2014.
  9. D. Itsykson, Structural complexity of AvgBPP. Annals of Pure and Applied Logic, 162(3): 213-223, 2010.
  10. A. Knop, Circuit Lower Bounds for Average-Case MA. Proceedings of CSR 2015.

Квалификационные работы

  1. Д. М. Ицыксон. Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой. Диссертация на соискание степени кандидата физико-математических наук. ПОМИ РАН, 2009.
  2. Ф. А. Парт. Недетерминированные вычисления, полиномиальные в среднем. Магистерская диссертация, СПбАУ РАН, 2011.
  3. В. О. Николаенко. Оптимальный детерминированный эвристический алгоритм для образа инъективной функции. Магистерская диссертация, СПбАУ РАН, 2011.