Monday, January
28, 2008 4:00 PM 5130 Upson Hall |
Theory Seminar Spring 2008 CS 789 |
|
---|---|---|
Hoeteck
Wee |
||
Black-Box Complexity of Non-Malleable Encryption |
||
A non-malleable encryption scheme is one
wherein given an encryption of a message, it is infeasible to generate
an encryption of a related message. We show how to transform any
semantically secure encryption scheme into a non-malleable one, with a
black-box construction that achieves a quasi-linear blow-up in the size
of the ciphertext. This improves upon the previous non-black-box
construction of Pass, Shelat and Vaikuntanathan (Crypto ’06).
Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions in zero-knowledge. Instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. In this talk, I will focus on how we exploit properties of low-degree polynomials to compute such an encoding. This is joint work with Seung Geol Choi, Dana Dachman-Soled and Tal Malkin.
|