We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Time hierarchies for cryptographic function inversion with advice.
- Authors
Grigoriev, D. Yu.; Hirsch, E. A.; Pervyshev, K. V.
- Abstract
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 Bibliography: 21 titles.
- Subjects
CRYPTOGRAPHY; SYMBOLIC inversion; POLYNOMIAL rings; PROBABILITY theory; INFINITE processes
- Publication
Journal of Mathematical Sciences, 2009, Vol 158, Issue 5, p633
- ISSN
1072-3374
- Publication type
Article
- DOI
10.1007/s10958-009-9403-5