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


Hoeteck
Wee 

BlackBox Complexity of NonMalleable Encryption 

A nonmalleable 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 nonmalleable one, with a
blackbox construction that achieves a quasilinear blowup in the size
of the ciphertext. This improves upon the previous nonblackbox
construction of Pass, Shelat and Vaikuntanathan (Crypto ’06).
Our construction departs from the oftused paradigm of reencrypting the same message with different keys and then proving consistency of encryptions in zeroknowledge. Instead, we encrypt an encoding of the message with certain locally testable and selfcorrecting properties. In this talk, I will focus on how we exploit properties of lowdegree polynomials to compute such an encoding. This is joint work with Seung Geol Choi, Dana DachmanSoled and Tal Malkin.
