2006 | OriginalPaper | Buchkapitel
On Pseudorandom Generators with Linear Stretch in NC0
verfasst von : Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC
0
, namely ones in which each bit of the output depends on just a constant number of input bits. Previous constructions of such PRGs were limited to stretching a seed of
n
bits to
n
+
o
(
n
) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC
0
. In this work we study this question and obtain the following main results:
1. We show that the existence of a linear-stretch PRG in NC
0
implies non-trivial hardness of approximation results
without relying on PCP machinery
. In particular, that Max 3SAT is hard to approximate to within some constant.
2. We construct a linear-stretch PRG in NC
0
under a specific intractability assumption related to the hardness of decoding “sparsely generated” linear codes. Such an assumption was previously conjectured by Alekhnovich [1].
We note that Alekhnovich directly obtains hardness of approximation results from the latter assumption. Thus, we do not prove hardness of approximation under new
concrete
assumptions. However, our first result is motivated by the hope to prove hardness of approximation under more general or standard cryptographic assumptions, and the second result is independently motivated by cryptographic applications.