ECCC-Report TR07-117https://eccc.weizmann.ac.il/report/2007/117Comments and Revisions published for TR07-117en-usMon, 19 Nov 2007 15:55:28 +0200
Paper TR07-117
| An infinitely-often one-way function based on an average-case assumption |
Edward Hirsch,
Dmitry Itsykson
https://eccc.weizmann.ac.il/report/2007/117We 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.
Mon, 19 Nov 2007 15:55:28 +0200https://eccc.weizmann.ac.il/report/2007/117