A Dichotomy for Local Small-Bias Generators

作者：Applebaum, Benny^*; Bogdanov, Andrej^*; Rosen, Alon^*

来源：Journal of Cryptology, 2016, 29(3): 577-596.

DOI：10.1007/s00145-015-9202-8

• Small-bias generator
• Dichotomy
• Local functions
• NC0

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen (MFCS'01) and by Mossel et al (STOC'03), we ask: which graphs and predicates yield "small-bias" generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, , with output length for some constant . Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear . Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.

• 出版日期2016-7
• 单位香港中文大学