research-article

Efficiency improvements in constructing pseudorandom generators from one-way functions

Authors:

Iftach Haitner,

Salil VadhanAuthors Info & Claims

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Pages 437 - 446

https://doi.org/10.1145/1806689.1806750

Published: 05 June 2010 Publication History

Abstract

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 [SICOMP '99]. 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 [Haitner, Reingold, Vadhan, Wee, STOC '09]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Ishai, Kushilevitz, SICOMP '06], this implies the existence of pseudorandom generators in NC^0 based on the existence of one-way functions in NC^1.

References

[1]

B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography in NC0. SIAM Journal on Computing, 36, 2006.

Digital Library

[2]

B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17 (2): 230--261, Apr. 1988.

Digital Library

[3]

U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1 (2): 77--94, 1988.

Digital Library

[4]

O. Goldreich and L. A. Levin. A hard--core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 25--32, 1989.

Digital Library

[5]

O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33 (4): 792--807, 1986.

Digital Library

[6]

O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38 (1): 691--729, 1991. Preliminary version in FOCS'86.

Digital Library

[7]

O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators. SIAM Journal on Computing, 22 (6): 1163--1175, 1993.

Digital Library

[8]

I. Haitner, O. Reingold, S. Vadhan, and H. Wee. Inaccessible entropy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC).

Digital Library

[9]

Haitner, Harnik, and Reingold}HaitnerHR06aI. Haitner, D. Harnik, and O. Reingold. On the power of the randomized iterate. In Advances in Cryptology -- CRYPTO 2006, 2006.

Digital Library

[10]

Haitner, Harnik, and Reingold}HaitnerHR06bI. Haitner, D. Harnik, and O. Reingold. Efficient pseudorandom generators from exponentially hard one-way functions. In Automata, Languages and Programming, 24th International Colloquium, ICALP, 2006.

Digital Library

[11]

I. Haitner, M. Nguyen, S. J. Ong, O. Reingold, and S. Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing, 39 (3): 1153--1218, 2009.

Digital Library

[12]

I. Haitner, O. Reingold, S. Vadhan, and H. Wee. Inaccessible entropy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC '09), pages 611--620, 31 May-2 June 2009.

Digital Library

[13]

J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28 (4): 1364--1396, 1999. Preliminary versions in STOC'89 and STOC'90.

Digital Library

[14]

T. Holenstein. Key agreement from weak bit agreement. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 664--673, 2005.

Digital Library

[15]

T. Holenstein. Pseudorandom generators from one-way functions: A simple construction for any hardness. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, 2006.

Digital Library

[16]

T. Holenstein. Strengthening key agreement using hard-core sets -- PhD thesis, 2006.

[17]

R. Impagliazzo. A personal view of average-case complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134--147. IEEE Computer Society, 1995.

Digital Library

[18]

R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 248--253, 1989.

Digital Library

[19]

R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 12--24. ACM Press, 1989.

Digital Library

[20]

M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17 (2): 373--386, 1988.

Digital Library

[21]

M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4 (2): 151--158, 1991. Preliminary version in CRYPTO'89.

Digital Library

[22]

A. A. Razborov and S. Rudich. Natural proofs. Journal of Computer and System Sciences, 55 (1): 24--35, Aug. 1997.

Digital Library

[23]

M. Sudan. Decoding of Reed--Solomon codes beyond the error correction bound. J. of Complexity, 13: 180--193, 1997.

Digital Library

[24]

M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences, 62: 236--266, 2001.

Digital Library

[25]

S. P. Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. Journal of Cryptology, 17 (1): 43--77, January 2004.

Digital Library

[26]

L. G. Valiant. A theory of the learnable. Communications of the ACM, 27 (11): 1134--1142, 1984.

Digital Library

[27]

A. C. Yao. Protocols for secure computations. pages 160--164, 1982.

[28]

D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16 (4/5): 367--391, Oct./Nov. 1996.

Cited By

Chung KGoldin EGray M(2024)On Central Primitives for Quantum Cryptography with Classical CommunicationAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68394-7_8(215-248)Online publication date: 18-Aug-2024
https://doi.org/10.1007/978-3-031-68394-7_8
Liu YPass R(2024)A Direct PRF Construction from Kolmogorov ComplexityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_14(375-406)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_14
Brzuska CCouteau GKaranko PRohrbach F(2021)On Derandomizing Yao’s Weak-to-Strong OWF ConstructionTheory of Cryptography10.1007/978-3-030-90453-1_15(429-456)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90453-1_15
Show More Cited By

Recommendations

On lattices, learning with errors, random linear codes, and cryptography

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed ...
Limits on the provable consequences of one-way permutations
STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show ...
How to construct random functions

A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented. This generator is a deterministic polynomial-time algorithm that transforms pairs (g, r), where g is ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

June 2010

812 pages

ISBN:9781450300506

DOI:10.1145/1806689

General Chair:
Michael Mitzenmacher
Harvard
,
Program Chair:
Leonard J. Schulman
Caltech

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'10

Sponsor:

SIGACT

STOC'10: Symposium on Theory of Computing

June 5 - 8, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
279
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chung KGoldin EGray M(2024)On Central Primitives for Quantum Cryptography with Classical CommunicationAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68394-7_8(215-248)Online publication date: 18-Aug-2024
https://doi.org/10.1007/978-3-031-68394-7_8
Liu YPass R(2024)A Direct PRF Construction from Kolmogorov ComplexityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_14(375-406)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_14
Brzuska CCouteau GKaranko PRohrbach F(2021)On Derandomizing Yao’s Weak-to-Strong OWF ConstructionTheory of Cryptography10.1007/978-3-030-90453-1_15(429-456)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90453-1_15
Liu YPass R(2020)On One-way Functions and Kolmogorov Complexity2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00118(1243-1254)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00118
Agrawal RChen YHorel TVadhan S(2019)Unifying Computational Entropies via Kullback–Leibler DivergenceAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26951-7_28(831-858)Online publication date: 1-Aug-2019
https://doi.org/10.1007/978-3-030-26951-7_28
Chen YGöös MVadhan SZhang JServedio R(2018)A tight lower bound for entropy flatteningProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235609(1-28)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235609
Agrawal MChakraborty DDas DNandakumar S(2017)Dimension, pseudorandomness and extraction of pseudorandomness1Computability10.3233/COM-1600666:3(277-305)Online publication date: 7-Aug-2017
https://doi.org/10.3233/COM-160066
Artemenko SShaltiel R(2017)Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size CircuitsACM Transactions on Computation Theory10.1145/30180579:2(1-26)Online publication date: 27-Apr-2017
https://dl.acm.org/doi/10.1145/3018057
Zhang WLiu SWang SYi BWu L(2017)An Efficient Lightweight RFID Authentication Protocol with Strong Trajectory Privacy ProtectionWireless Personal Communications: An International Journal10.1007/s11277-017-4232-196:1(1215-1228)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11277-017-4232-1
Yu YSteinberger J(2016)Pseudorandom Functions in Almost Constant Depth from Low-Noise LPNProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081744(154-183)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081744
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents