Learning noisy characters, multiplication codes, and cryptographic hardcore predicates

We present results in cryptography, coding theory and sublinear algorithms. In cryptography, we introduce a unifying framework for proving that a Boolean predicate is hardcore 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 such as RSA and discrete-log as well as reproving old results in an entirely different way. Our proof framework extends the list-decoding method of Goldreich and Levin [38] for showing hardcore predicates, by introducing a new class of error correcting codes and new list-decoding algorithm we develop for these codes. In coding theory, we introduce a novel class of error correcting codes that we name: Multiplication codes (MPC). We develop decoding algorithms for MPC codes, showing they achieve desirable combinatorial and algorithmic properties, including: (1) binary MPC of constant distance and exponential encoding length for which we provide efficient local list decoding and local self correcting algorithms; (2) binary MPC of constant distance and polynomial encoding length for which we provide efficient decoding algorithm in random noise model; (3) binary MPC of constant rate and distance. MPC codes are unique in particular in achieving properties as above while having a large group as their underlying algebraic structure. In sublinear algorithms, we present the SFT algorithm for finding the sparse Fourier approximation of complex multi-dimensional signals in time logarithmic in the signal length. We also present additional algorithms for related settings, differing in the model by which the input signal is given, in the considered approximation measure, and in the class of addressed signals. The sublinear algorithms we present are central components in achieving our results in cryptography and coding theory.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Akavia, Adi

Advisor dc:contributor.advisor

• Shafi Goldwasser.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/43032

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/43032