Standard

An infinitely-often one-way function based on an average-case assumption. / Hirsch, E. A.; Itsykson, D. M.

In: St. Petersburg Mathematical Journal, Vol. 21, No. 3, 01.12.2010, p. 459-468.

Research output: Contribution to journal › Article › peer-review

Harvard

Hirsch, EA & Itsykson, DM 2010, 'An infinitely-often one-way function based on an average-case assumption', St. Petersburg Mathematical Journal, vol. 21, no. 3, pp. 459-468. https://doi.org/10.1090/S1061-0022-10-01103-9

APA

Hirsch, E. A., & Itsykson, D. M. (2010). An infinitely-often one-way function based on an average-case assumption. St. Petersburg Mathematical Journal, 21(3), 459-468. https://doi.org/10.1090/S1061-0022-10-01103-9

Vancouver

Hirsch EA, Itsykson DM. An infinitely-often one-way function based on an average-case assumption. St. Petersburg Mathematical Journal. 2010 Dec 1;21(3):459-468. https://doi.org/10.1090/S1061-0022-10-01103-9

Author

Hirsch, E. A. ; Itsykson, D. M. / An infinitely-often one-way function based on an average-case assumption. In: St. Petersburg Mathematical Journal. 2010 ; Vol. 21, No. 3. pp. 459-468.

BibTeX

@article{24f0ebfe8a034472907ee94408531055,
title = "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 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.",
keywords = "Average-case complexity, One-way function",
author = "Hirsch, {E. A.} and Itsykson, {D. M.}",
year = "2010",
month = dec,
day = "1",
doi = "10.1090/S1061-0022-10-01103-9",
language = "English",
volume = "21",
pages = "459--468",
journal = "St. Petersburg Mathematical Journal",
issn = "1061-0022",
publisher = "American Mathematical Society",
number = "3",

}

RIS

TY - JOUR

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

AU - Hirsch, E. A.

AU - Itsykson, D. M.

PY - 2010/12/1

Y1 - 2010/12/1

N2 - 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.

AB - 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.

KW - Average-case complexity

KW - One-way function

UR - http://www.scopus.com/inward/record.url?scp=84861235113&partnerID=8YFLogxK

U2 - 10.1090/S1061-0022-10-01103-9

DO - 10.1090/S1061-0022-10-01103-9

M3 - Article

AN - SCOPUS:84861235113

VL - 21

SP - 459

EP - 468

JO - St. Petersburg Mathematical Journal

JF - St. Petersburg Mathematical Journal

SN - 1061-0022

IS - 3

ER -

ID: 49786688