Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-117 | 8th November 2007 00:00

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

RSS-Feed




TR07-117
Authors: Edward Hirsch, Dmitry Itsykson
Publication: 19th November 2007 15:55
Downloads: 3792
Keywords: 


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.



ISSN 1433-8092 | Imprint