ECCC-Report TR05-076https://eccc.weizmann.ac.il/report/2005/076Comments and Revisions published for TR05-076en-usFri, 15 Jul 2005 18:29:24 +0300
Paper TR05-076
| Time hierarchies for cryptographic function inversion with advice |
Dima Grigoriev,
Edward Hirsch,
Konstantin Pervyshev
https://eccc.weizmann.ac.il/report/2005/076We 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
at least 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!=NP, then for every l>k>=1
(DTime{n^k} \cap NTime{n})/1 \subsetneq (DTime{n^l} \cap NTime{n})/1.
Fri, 15 Jul 2005 18:29:24 +0300https://eccc.weizmann.ac.il/report/2005/076