A pseudorandom generator from any one-way function

被引：900

作者：

Hästad, J

Impagliazzo, R

Levin, LA

Luby, M

机构：

[1] Royal Inst Technol, Dept Numer Anal & Comp Sci, S-10044 Stockholm, Sweden

[2] Univ Calif San Diego, Dept Comp Sci, La Jolla, CA 92093 USA

[3] Boston Univ, Dept Comp Sci, Boston, MA 02215 USA

[4] Univ Calif Berkeley, Int Comp Sci Inst, Berkeley, CA 94704 USA

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 04期

关键词：

one-way function; pseudorandom generator; cryptography; complexity theory;

D O I：

10.1137/S0097539793244708

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

引用

页码：1364 / 1396

页数：33

共 47 条

[1] RSA AND RABIN FUNCTIONS - CERTAIN PARTS ARE AS HARD AS THE WHOLE [J].