### Abstract

We assume the existence of a function f that is computable in polynomial time but cannot be inverted by a randomized average-case polynomial algorithm. The cryptographic setting is, however, different: even for a weak one-way function, a successful adversary should fail on a polynomial fraction of inputs. Nevertheless, we show how to construct an infinitely-often one-way function based on f.

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

Pages (from-to) | 459-468 |

Number of pages | 10 |

Journal | St. Petersburg Mathematical Journal |

Volume | 21 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Dec 2010 |

### Scopus subject areas

- Analysis
- Algebra and Number Theory
- Applied Mathematics

## Fingerprint Dive into the research topics of 'An infinitely-often one-way function based on an average-case assumption'. Together they form a unique fingerprint.

## Cite this

Hirsch, E. A., & Itsykson, D. M. (2010). An infinitely-often one-way function based on an average-case assumption.

*St. Petersburg Mathematical Journal*,*21*(3), 459-468. https://doi.org/10.1090/S1061-0022-10-01103-9