Monday, January 28, 2008
4:00 PM
5130 Upson Hall
  Theory Seminar
Spring 2008

CS 789

Hoeteck Wee
Columbia University


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.