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 条

[31]

LEVIN LA, 1993, J SYMBOLIC LOGIC, V58, P1102

[32] HOW TO CONSTRUCT PSEUDORANDOM PERMUTATIONS FROM PSEUDORANDOM FUNCTIONS [J].

LUBY, M ;

RACKOFF, C .

SIAM JOURNAL ON COMPUTING, 1988, 17 (02) :373-386

[33]

Luby M., 1996, PRINCETON COMPUTER S

[34]

McEliece Robert J, 1978, PUBLIC KEY CRYPTOSYS

[35]

MCINNES J, 1987, 19487 U TOR

[36]

MOTWANI R., 1995, Randomized Algorithms

[37]

Naor M., 1991, Journal of Cryptology, V4, P151, DOI 10.1007/BF00196774

[38]

Naor M., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P33, DOI 10.1145/73007.73011

[39]

Ostrovsky R., 1993, Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), P3, DOI 10.1109/ISTCS.1993.253489

[40]

Renyi A., 1970, Probability Theory

← 1 2 3 4 5 →