Thesis Defense: Learning Characters with Noise, Multiplication Codes and Cryptographic Hard-Core Predicates
Speaker: Adi Akavia , MIT
Date: August 15 2007
Time: 1:00PM to 2:30PM
Location: 32-G449 Kiva
Host: Shafi Goldwasser, MIT
Contact: Joanne Hanley, 3-6054, joanne@csail.mit.edu
Abstract
Fourier analysis has proved to be of great value in complexity and cryptography, employed in achieving seminal results such as the Goldreich-Levin cryptographic hard-core predicates, the Linial-Mansour-Nisan lower bounds on AC0 circuits and Hastad's tight inapproximability results. Computing the Fourier transform of a function f can be done in time O(N log N) using the FFT algorithm (for N the size of f's domain). This time bound clearly cannot be improved below O(N) as the output length itself is of length N. Nevertheless, it turns out that it often suffices to find the /significant/ Fourier coefficients of f, that is, say, those occupying 1% of its energy. This raises the computational task of /finding /these significant coefficients. We explore this task in general settings: (1) We address (complex) functions f over /any /finite abelian group. (2) We consider
various models by which the input function f is given. (3) We consider various distance measures by which the "significant" Fourier coefficients are defined. We name this the /Learning Characters with Noise/ problem. (Where characters are the Fourier basis functions.)
Special cases of the problem of Learning Characters with Noise have been studied before. One example is the /Learning Parity with Noise/ problem in which the input is restricted to functions over the Boolean cube
{0,1}^n and access to f is given via random samples. Other example studied in the context of approximation theory is the task of finding /sparse Fourier representations,/ where functions f over the Boolean cube {0,1}^n and over the group of integers modulo N were considered in the query access model.
We study the complexity of Learning Characters with Noise problem presenting algorithms solving several of the variants and conjecturing intractability of others variants. We explore applications of our algorithms and conjectures to cryptography and coding theory.
- In coding theory, we introduce new families of error correcting codes exhibiting a variety of combinatorial and algorithmic properties. For example, we show a family of codes with efficient list decoding algorithm, efficient local decoding algorithm (with O(1) running time and query complexity), constant distance and exponentially small rate. Other codes families we present have polynomial (and even constant) rate with weaker decoding algorithms.
- In cryptography, we explore cryptographic hard-core predicates -- a fundamental cryptographic primitive central for many applications such as pseudo-randomness and semantically secure encryption. We introduce a unifying framework for proving that a predicate is hard-core for a one-way function, and apply it to a broad family of functions and predicates showing new hardcore predicates for well known one-way function candidates as well as reproving old results in an entirely
different way. Our framework extends the list decoding method of Goldreich and Levin for proving hard-core predicates.
See other events that are part of
See other events happening in August 2007
