Hoeteck Wee

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.

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.