Limits on the stretch of non-adaptive constructions of pseudo-random generators

Josh Bronson, Ali Juma, Periklis Papakonstantinou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

The standard approach for constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator involves repeatedly composing the given primitive with itself. In this paper, we consider whether this approach is necessary, that is, whether there are constructions that do not involve composition. More formally, we consider black-box constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, where the constructions make only non- adaptive queries to the given object. We consider three classes of such constructions, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions. We first consider constructions that make constantly-many non-adaptive queries to a given pseudo-random generator, where the seed length of the construction is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions cannot achieve stretch that is even a single bit greater than the stretch of the given pseudo-random generator. We then consider constructions with arbitrarily long seeds, but where oracle queries are collectively chosen in a manner that depends only on a portion of the seed whose length is at most O(log n) bits longer than the length n of each query. We show that such constructions making constantly-many non-adaptive queries cannot achieve stretch that is ω(log n) bits greater than the stretch of the given pseudo-random generator. Finally, we consider a class of constructions motivated by streaming computation. Specifically, we consider constructions where the computation of each individual output bit depends only on the seed and on the response to a single query to a one-way permutation. We allow the seed to have a public portion that is arbitrarily long but must always be included in the output, and a non-public portion that is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions whose queries are chosen non-adaptively based only on the non-public portion of the seed cannot achieve linear stretch.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings
Pages504-521
Number of pages18
DOIs
StatePublished - Apr 4 2011
Event8th Theory of Cryptography Conference, TCC 2011 - Providence, RI, United States
Duration: Mar 28 2011Mar 30 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6597 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th Theory of Cryptography Conference, TCC 2011
CountryUnited States
CityProvidence, RI
Period3/28/113/30/11

Fingerprint

Pseudorandom Generator
Stretch
Query
Seed
Black Box
Permutation
Output
Streaming

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Bronson, J., Juma, A., & Papakonstantinou, P. (2011). Limits on the stretch of non-adaptive constructions of pseudo-random generators. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings (pp. 504-521). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6597 LNCS). https://doi.org/10.1007/978-3-642-19571-6_30
Bronson, Josh ; Juma, Ali ; Papakonstantinou, Periklis. / Limits on the stretch of non-adaptive constructions of pseudo-random generators. Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings. 2011. pp. 504-521 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{2c4db1bf50e848d9b2689889bff29578,
title = "Limits on the stretch of non-adaptive constructions of pseudo-random generators",
abstract = "The standard approach for constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator involves repeatedly composing the given primitive with itself. In this paper, we consider whether this approach is necessary, that is, whether there are constructions that do not involve composition. More formally, we consider black-box constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, where the constructions make only non- adaptive queries to the given object. We consider three classes of such constructions, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions. We first consider constructions that make constantly-many non-adaptive queries to a given pseudo-random generator, where the seed length of the construction is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions cannot achieve stretch that is even a single bit greater than the stretch of the given pseudo-random generator. We then consider constructions with arbitrarily long seeds, but where oracle queries are collectively chosen in a manner that depends only on a portion of the seed whose length is at most O(log n) bits longer than the length n of each query. We show that such constructions making constantly-many non-adaptive queries cannot achieve stretch that is ω(log n) bits greater than the stretch of the given pseudo-random generator. Finally, we consider a class of constructions motivated by streaming computation. Specifically, we consider constructions where the computation of each individual output bit depends only on the seed and on the response to a single query to a one-way permutation. We allow the seed to have a public portion that is arbitrarily long but must always be included in the output, and a non-public portion that is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions whose queries are chosen non-adaptively based only on the non-public portion of the seed cannot achieve linear stretch.",
author = "Josh Bronson and Ali Juma and Periklis Papakonstantinou",
year = "2011",
month = "4",
day = "4",
doi = "10.1007/978-3-642-19571-6_30",
language = "English (US)",
isbn = "9783642195709",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "504--521",
booktitle = "Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings",

}

Bronson, J, Juma, A & Papakonstantinou, P 2011, Limits on the stretch of non-adaptive constructions of pseudo-random generators. in Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6597 LNCS, pp. 504-521, 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, United States, 3/28/11. https://doi.org/10.1007/978-3-642-19571-6_30

Limits on the stretch of non-adaptive constructions of pseudo-random generators. / Bronson, Josh; Juma, Ali; Papakonstantinou, Periklis.

Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings. 2011. p. 504-521 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6597 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Limits on the stretch of non-adaptive constructions of pseudo-random generators

AU - Bronson, Josh

AU - Juma, Ali

AU - Papakonstantinou, Periklis

PY - 2011/4/4

Y1 - 2011/4/4

N2 - The standard approach for constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator involves repeatedly composing the given primitive with itself. In this paper, we consider whether this approach is necessary, that is, whether there are constructions that do not involve composition. More formally, we consider black-box constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, where the constructions make only non- adaptive queries to the given object. We consider three classes of such constructions, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions. We first consider constructions that make constantly-many non-adaptive queries to a given pseudo-random generator, where the seed length of the construction is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions cannot achieve stretch that is even a single bit greater than the stretch of the given pseudo-random generator. We then consider constructions with arbitrarily long seeds, but where oracle queries are collectively chosen in a manner that depends only on a portion of the seed whose length is at most O(log n) bits longer than the length n of each query. We show that such constructions making constantly-many non-adaptive queries cannot achieve stretch that is ω(log n) bits greater than the stretch of the given pseudo-random generator. Finally, we consider a class of constructions motivated by streaming computation. Specifically, we consider constructions where the computation of each individual output bit depends only on the seed and on the response to a single query to a one-way permutation. We allow the seed to have a public portion that is arbitrarily long but must always be included in the output, and a non-public portion that is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions whose queries are chosen non-adaptively based only on the non-public portion of the seed cannot achieve linear stretch.

AB - The standard approach for constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator involves repeatedly composing the given primitive with itself. In this paper, we consider whether this approach is necessary, that is, whether there are constructions that do not involve composition. More formally, we consider black-box constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, where the constructions make only non- adaptive queries to the given object. We consider three classes of such constructions, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions. We first consider constructions that make constantly-many non-adaptive queries to a given pseudo-random generator, where the seed length of the construction is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions cannot achieve stretch that is even a single bit greater than the stretch of the given pseudo-random generator. We then consider constructions with arbitrarily long seeds, but where oracle queries are collectively chosen in a manner that depends only on a portion of the seed whose length is at most O(log n) bits longer than the length n of each query. We show that such constructions making constantly-many non-adaptive queries cannot achieve stretch that is ω(log n) bits greater than the stretch of the given pseudo-random generator. Finally, we consider a class of constructions motivated by streaming computation. Specifically, we consider constructions where the computation of each individual output bit depends only on the seed and on the response to a single query to a one-way permutation. We allow the seed to have a public portion that is arbitrarily long but must always be included in the output, and a non-public portion that is at most O(log n) bits longer than the length n of each oracle query. We show that such constructions whose queries are chosen non-adaptively based only on the non-public portion of the seed cannot achieve linear stretch.

UR - http://www.scopus.com/inward/record.url?scp=79953168032&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79953168032&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-19571-6_30

DO - 10.1007/978-3-642-19571-6_30

M3 - Conference contribution

SN - 9783642195709

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 504

EP - 521

BT - Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings

ER -

Bronson J, Juma A, Papakonstantinou P. Limits on the stretch of non-adaptive constructions of pseudo-random generators. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings. 2011. p. 504-521. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-19571-6_30