Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with i.o.-hardness:
TR07-117 | 8th November 2007
Edward Hirsch, Dmitry Itsykson

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

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, ... more >>>

ISSN 1433-8092 | Imprint