文章基本信息

标题：An epsilon-Biased Generator in NC0
本地全文：下载
作者：Luca Trevisan
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; in fact, they show that it is always possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k>3, and conjecture that every NC0 generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, they conjecture that no NC0 generator can sample an epsilon-biased space with negligible epsilon. We refute the conjecture for k>4, and we give a generator that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias exponentially small in n/c^4. We also present a polynomial-time distinguisher for the case k=4, having constant distinguishing probability. We observe that constant distinguishing probability is not achievable in general via linear tests. It remains open whether noticeable distinguishing probability can be achieved with linear tests for the case k=4, and whether there is a polynomial time test that breaks every generator (or even just our proposal) for k>4.
关键词：Bounded-depth Circuits , Correlation Attacks , pseudorandom generators , Small Bias Sample Spaces