Home

Семинар 7 октября 2005 года

  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-1 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-2 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-3 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-4 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-5 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-6 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-7 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-8 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-9 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-10 has been created.
  • The directory /tmp/drutex-794692ab8c404245f52e53abca5c55be-11 has been created.

Пятница, 7 октября, комната 106. Начало в 17:30.

Докладчик: К. В. Первышев.

Тема: Иерархии по времени для инвертирования функций с подсказкой.

Abstract

(Совместная работа с Э.А.Гиршем и Д.Ю.Григорьевым.)

Существование односторонних функций (т.е., таких, для которых никакой полиномиальный по времени ``соперник'' не может вычислить обратную со значительной вероятностью успеха) является необходимым для существования криптографии с открытым ключом. Статья посвящена следующему естественному вопросу: даже если мы и не можем доказать наличие или отсутствие односторонних функций, верно ли, что с увеличением времени работы соперника он сможет инвертировать больше функций?

Abstract статьи: We prove a time hierarchy theorem for inverting functions computable in polynomial time with one bit of advice. In particular, we prove that if there is a strongly one-way function then for any TeX Embedding failed! and for any polynomial TeX Embedding failed!, there is a function TeX Embedding failed! computable in linear time with one bit of advice such that there is a polynomial-time probabilistic adversary that inverts TeX Embedding failed! with probability TeX Embedding failed! on infinitely many lengths of input while all probabilistic TeX Embedding failed!-time adversaries with logarithmic advice invert TeX Embedding failed! with probability less than TeX Embedding failed! on almost all lengths of input.

We also prove a similar theorem in the worst-case setting, i.e., if PTeX Embedding failed!NP, then for every TeX Embedding failed!

TeX Embedding failed!