### 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 (Dtime[nk] ∩Ntime[n]) 1 (Dtime[nl}] ∩ Ntime[n] )1. Bibliography: 21 titles.

Original language | English |
---|---|

Pages (from-to) | 633-644 |

Number of pages | 12 |

Journal | Journal of Mathematical Sciences |

Volume | 158 |

Issue number | 5 |

DOIs | |

Publication status | Published - 1 May 2009 |

### Scopus subject areas

- Statistics and Probability
- Mathematics(all)
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Time hierarchies for cryptographic function inversion with advice'. Together they form a unique fingerprint.

## Cite this

*Journal of Mathematical Sciences*,

*158*(5), 633-644. https://doi.org/10.1007/s10958-009-9403-5