1990 | OriginalPaper | Buchkapitel
On the Power of 1-way Functions
(Abstract)
verfasst von : Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer
Erschienen in: Advances in Cryptology — CRYPTO’ 88
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The earliest definition of 1-way function is due to Berman [Ber77], who considered polynomial-time computable, length-increasing, 1–1 functions that do not have a polynomial-time computable inverses. Recently, more powerful notions are considered, e.g., polynomial-time computable, length-increasing, 1–1 functions f such that the probability that a BPP algorithm can compute z from f(x) for a randomly selected x is superpolynomidly small [CYa82]. Whatever definition is used, these functions are necessarily easy invert on some inputs:Proposition 1If f is a polynomial-time computable, length-increasing, 1-1 function, and if p is a polynomial, then there is a polynomial time algorithm that for sufficiently large n inverts f on at least p(n) strings of length less than n. Therefore, the range of every such function must contain a polynomial-time computable subset of arbitrarily large polynomial census.