Abstract
We study the role of polynomials over the finite field $GF(2^n)$ in constructing and attacking various weak notions of pseudorandomness.
First, we consider the construction of weak pseudorandom generators using $GF(2^n)$-polynomials. We study the generator of [Nisan, STOC'90], that fools space-bounded nonuniform distinguishers, whose standard instantiation can be seen as a $GF(2^n)$-polynomial map. Among other results, we show that its resilience to (nonuniform) space-bounded machines is sensitive to the order of its output bits, and rule out some natural generalizations of the generator. We also consider $GF(2^n)$-polynomial-based generators that have small bias, meaning that they fool all (bit-)linear tests. We present a simple construction of a small-bias generator (called the geometric generator), which is similar (but not identical) to the powering construction presented by [Alon et al., RS&A'92]. A variant of this generator has shorter seed than the classical constructions of Alon et al., if the reciprocal of the bias required is polylogarithmic in the output length. We also use a variant of the geometric generator to construct a separation between small-bias and fooling small space that has good parameters, giving an exponential-stretch generator with exponentially small bias that is $O(1)$-space distinguishable (by a nonuniform machine).
Second, we study how $GF(2^n)$-polynomials can be used to distinguish various distributions from random ones. We provide a full picture of how various notions of $GF(2^n)$-linear distinguishers relate to standard linear (that is, $GF(2)$-linear) tests, and derive a reduction from having small-bias to fooling $GF(2^n)$-linear tests. In fact, this reduction is used to prove the small bias of the geometric generator mentioned above. We also conduct a study of $GF(2^n)$-bilinear and $GF(2^n)$-quadratic forms, and in specific characterize the sets of $GF(2)$-bilinear forms that can be computed exactly, or approximated to various rates, by $GF(2^n)$-bilinear forms. Higher-degree polynomials are also studied, and specifically we consider a recent result of [Viola, CCC'08] that showed that the sum of $d$ independent instances of a small-bias generator fools polynomials of degree at most $d$. We show the tightness of this result with respect to the number of instances required, showing an explicit degree-$d+1$ polynomial that distinguishes this construction from random with constant gap.
Table of Contents
1 Introduction 1.1 Background 1.1.1 Pseudorandomness 1.1.2 Weak pseudorandomness 1.1.3 Using $GF(2^n)$-polynomials 1.2 Overview and organization of the thesis 1.3 Highlights 1.3.1 Separating small-bias from fooling small-space 1.3.2 Order-sensitivity of Nisan's generator 1.3.3 Disqualifying a variant of Nisan's generator 1.3.4 Using $GF(2^n)$ to construct small-bias generators 1.3.5 An explicit lower bound for fooling polynomials by the sum of small-bias generators 1.3.6 Approximating $GF(2)$-bilinear forms from $GF(2^n)$-bilinear forms 2 Preliminaries 2.1 Weak notions of pseudorandomness 2.2 Representation of $GF(2^n)$ 2.2.1 Basic Notations 2.2.2 Basic Properties 2.3 Block-generators and $GF(2^n)$-generators 2.4 Using a larger prime field 3 $GF(2^n)$-Polynomials as Weak Pseudorandom Generators 3.1 Introduction 3.1.1 Motivation 3.1.2 Overview 3.2 A bound on the stretch of $GF(2^n)$-polynomial small-bias generators 3.2.1 A linear dependency over $GF(2^n)$ 3.2.2 A linear dependency over bits 3.3 The Nisan generator 3.3.1 Definitions of the distinguisher classes 3.3.2 Overview of the analysis of Nisan's generator 3.3.3 A $GF(2^n)$-polynomial generator 3.3.4 The permutations variant 3.3.5 Seed-and-hash variants 3.4 The geometric generator 3.4.1 Small bias 3.4.2 Distinguishable by a nonuniform block-automaton 3.4.3 Using more variables 3.4.4 Using a larger prime field 3.5 A small-bias generator of large stretch that is $O(1)$-space distinguishable 3.5.1 Bilinear dependencies 3.5.2 The first bit of Mab 3.5.3 Bilinear dependencies in known generators 4 $GF(2^n)$-Polynomials vs. $GF(2)$-Polynomials: as Distinguishers 4.1 Introduction 4.1.1 Motivation 4.1.2 Overview 4.2 The general picture 4.2.1 Formal definitions 4.2.2 Relations between the different notions of $GF(2^n)$-polynomial tests, and their relation to $GF(2)$-polynomials 4.3 Degree 1: linear tests 4.3.1 Motivating the definitions 4.3.2 Proof of Theorem 4.5 4.3.3 A constructive proof of Lemma 2.11 4.4 Higher degrees: a reduction to approximators 4.4.1 Inapproximability on the uniform distribution suffices for unbiased tests 4.4.2 Inapproximability of bilinear tests 4.5 A sum of d small-bias generators that is distinguishable by a degree-$d+1$ polynomial 4.5.1 Background 4.5.2 Our result 4.5.3 Distinguishing over $GF(2^n)$ 4.5.4 Distinguishing over bits 4.5.5 Using larger prime fields 5 $GF(2^n)$-Polynomials vs. $GF(2)$-Polynomials: as Approximators 5.1 Introduction 5.1.1 Motivation 5.1.2 The general picture 5.1.3 Overview 5.2 Computing exactly 5.2.1 Counting arguments 5.2.2 Bilinear forms 5.3 Approximating bilinear forms 5.3.1 Very good approximations 5.3.2 Somewhat good approximations 5.3.3 Arbitrary Approximations 5.3.4 Quadratic forms 5.4 Multi-$GF(2)$-bilinear functions vs. $GF(2)$-quadratic functions 5.4.1 Definition of the model 5.4.2 Computing block-symmetric $GF(2)$-quadratic functions from n + 1 bilinear functions 5.4.3 Losing one $p_i$ 5.4.4 Different linear combinations of the blocks A Small parameter improvements A.1 A better stretch bound for Section 3.2 A.2 A better approximation rate for Subsection 5.3.3 B Agreement with affine functions
Number of Pages: 87
