EFFICIENCY IMPROVEMENTS IN CONSTRUCTING PSEUDORANDOM GENERATORS FROM ONE-WAY FUNCTIONS

被引：22

作者：

Haitner, Iftach ^{[1
]}

Reingold, Omer ^{[2
,3
]}

Vadhan, Salil ^{[4
,5
]}

机构：

[1] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

[2] Microsoft Res, Mountain View, CA 94043 USA

[3] Weizmann Inst Sci, Fac Math & Comp Sci, IL-76100 Rehovot, Israel

[4] Harvard Univ, Sch Engn & Appl Sci, Cambridge, MA 02138 USA

[5] Harvard Univ, Ctr Res Computat & Soc, Cambridge, MA 02138 USA

来源：

SIAM JOURNAL ON COMPUTING | 2013年 / 42卷 / 03期

关键词：

one-way functions; pseudorandom generators; pseudoentropy; RANDOMIZED ITERATE; PROOFS; POWER; BITS;

D O I：

10.1137/100814421

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Hastad, Impagliazzo, Levin, and Luby [SIAM J. Comput., 28 (1999), pp. 1364-1396]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired by the notion of "inaccessible entropy" recently introduced in [I. Haitner, O. Reingold, S. Vadhan, and H. Wee, Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 611-620]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a nonadaptive manner. Using [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845-888], this implies the existence of pseudorandom generators in NC0 based on the existence of one-way functions in NC1.

引用

页码：1405 / 1430

页数：26

共 37 条

[1]

[Anonymous], P IEEE FOCS 1989

[2] Cryptography in NC0 [J].

Applebaum, Benny ;

Ishai, Yuval ;

Kushilevitz, Eyal .

SIAM JOURNAL ON COMPUTING, 2006, 36 (04) :845-888

[3] HOW TO GENERATE CRYPTOGRAPHICALLY STRONG SEQUENCES OF PSEUDO-RANDOM BITS [J].

BLUM, M ;

MICALI, S .

SIAM JOURNAL ON COMPUTING, 1984, 13 (04) :850-864

[4] UNBIASED BITS FROM SOURCES OF WEAK RANDOMNESS AND PROBABILISTIC COMMUNICATION COMPLEXITY [J].

CHOR, B ;

GOLDREICH, O .

SIAM JOURNAL ON COMPUTING, 1988, 17 (02) :230-261

[5]

Feige U., 1988, Journal of Cryptology, V1, P77, DOI 10.1007/BF02351717

[6] Bounds on the efficiency of generic cryptographic constructions [J].

Gennaro, R ;

Gertner, Y ;

Katz, J ;

Trevisan, L .

SIAM JOURNAL ON COMPUTING, 2005, 35 (01) :217-246

[7]

Goldreich O., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P25, DOI 10.1145/73007.73010

[8] HOW TO CONSTRUCT RANDOM FUNCTIONS [J].

GOLDREICH, O ;

GOLDWASSER, S ;

MICALI, S .

JOURNAL OF THE ACM, 1986, 33 (04) :792-807

[9] ON THE EXISTENCE OF PSEUDORANDOM GENERATORS [J].

GOLDREICH, O ;

KRAWCZYK, H ;

LUBY, M .

SIAM JOURNAL ON COMPUTING, 1993, 22 (06) :1163-1175

[10]

GOLDREICH O, 1991, J ACM, V38, P691, DOI 10.1145/116825.116852

← 1 2 3 4 →