Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 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 $k$ and for any polynomial $p$, there is a function $f$ computable in linear time with one bit of advice such that there is a polynomial-time probabilistic adversary that inverts $f$ with probability $ge 1/p(n)$ on infinitely many lengths of input while all probabilistic $O(n^k)$-time adversaries with logarithmic advice invert $f$ with probability less than $1/p(n)$ on almost all lengths of input.

We also prove a similar theorem in the worst-case setting, i.e., if P$neq$NP, then for every $l>kge1$ $$ (DTime[n^k] cap NTime[n])/1 subsetneq (DTime[n^l] cap NTime[n])/1. $$