Thesis Defense: Cryptographic Error Correction
Speaker: Chris Peikert , CSAIL, MIT
Date: June 2 2006
Time: 10:00AM to 11:30AM
Location: 32-G449 Patil-Kiva
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL:
It has been said that "cryptography is about hiding information, and coding theory is about revealing it." Despite these apparently conflicting goals, the two fields have common origins and many interesting relationships.
In this thesis, we establish new connections between cryptography and coding theory in two complementary ways: first, by applying cryptographic tools to solve classical problems from the theory of error correction; second, by studying special kinds of codes whose properties are useful in cryptographic applications.
In the first direction, we consider a model of error correction in which the source of errors is adversarial, but limited to _feasible_ computation. In this model, we construct appealingly simple, general, and efficient cryptographic coding schemes which can recover from much larger error rates than are possible in classical models of malicious noise.
In the complementary direction, we study a primitive called "collusion-secure fingerprinting codes," which are of fundamental importance in data watermarking and traitor tracing. We show tight lower bounds on the lengths of such codes by devising a general
collusive attack that works for any code. Bringing our results full-circle, we then show that by limiting coalitions to _feasible_ computation, we can design secure fingerprinting codes that are
significantly shorter than all prior constructions.
Thesis Committee: Silvio Micali, Ron Rivest, Shafi Goldwasser
See other events that are part of
See other events happening in June 2006
