TY - JOUR

T1 - Time hierarchies for cryptographic function inversion with advice

AU - Grigoriev, D. Yu

AU - Hirsch, E. A.

AU - Pervyshev, K. V.

PY - 2009/5/1

Y1 - 2009/5/1

N2 - We prove a time hierarchy theorem for inverting functions computable in a slightly nonuniform polynomial time. 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 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[nk] ∩Ntime[n]) 1 (Dtime[nl}] ∩ Ntime[n] )1. Bibliography: 21 titles.

AB - We prove a time hierarchy theorem for inverting functions computable in a slightly nonuniform polynomial time. 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 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[nk] ∩Ntime[n]) 1 (Dtime[nl}] ∩ Ntime[n] )1. Bibliography: 21 titles.

UR - http://www.scopus.com/inward/record.url?scp=67349115686&partnerID=8YFLogxK

U2 - 10.1007/s10958-009-9403-5

DO - 10.1007/s10958-009-9403-5

M3 - Article

AN - SCOPUS:67349115686

VL - 158

SP - 633

EP - 644

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 5

ER -