TR05-108 Authors: Ariel Gabizon, Ran Raz

Publication: 29th September 2005 19:19

Downloads: 2513

Keywords:

An $(n,k)$-affine source over a finite field $F$ is a random

variable $X=(X_1,...,X_n) \in F^n$, which is uniformly

distributed over an (unknown) $k$-dimensional affine subspace of $

F^n$. We show how to (deterministically) extract practically all

the randomness from affine sources, for any field of size larger

than $n^c$ (where $c$ is a large enough constant). Our main

results are as follows:

(For arbitrary $k$):

For any $n,k$ and any $F$ of size larger than $n^{20}$, we give an

explicit construction for a function $D: F^n \rightarrow {\mathbb

F}^{k-1}$, such that for any $(n,k)$-affine source $X$ over $F$,

the distribution of $D(X)$ is $\epsilon$-close to uniform, where

$\epsilon$ is polynomially small in $|F|$.

(For $k=1$): For any

$n$ and any $F$ of size larger than $n^{c}$, we give an explicit

construction for a function $D: {\mathbb F}^n \rightarrow

\{0,1\}^{(1-\delta) \log_2 |F|}$, such that for any $(n,1)$-affine

source $X$ over $F$, the distribution of $D(X)$ is

$\epsilon$-close to uniform, where $\epsilon$ is polynomially

small in $|F|$. Here, $\delta

> 0$ is an arbitrary small constant, and $c$ is a constant

depending on $\delta$.