__
TR07-117 | 8th November 2007 00:00
__

#### An infinitely-often one-way function based on an average-case assumption

**Abstract:**
We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, we show how to construct an _infinitely-often_ one-way function based on f.