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

E. A. Hirsch, D. M. Itsykson

Research output

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)459-468
Number of pages10
JournalSt. Petersburg Mathematical Journal
Volume21
Issue number3
DOIs
Publication statusPublished - 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