@inbook {19630,
	title = {Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2008},
	month = {2008/01/01/},
	pages = {427 - 444},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {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 {\textquoteright}06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt {\textquoteright}07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions; instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. We exploit the fact that low-degree polynomials are simultaneously good error-correcting codes and a secret-sharing scheme.},
	keywords = {Algorithm Analysis and Problem Complexity, black-box constructions, computers and society, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, non-malleability, public-key encryption, semantic security, Systems and Data Security},
	isbn = {978-3-540-78523-1, 978-3-540-78524-8},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-78524-8_24},
	author = {Choi, Seung Geol and Dana Dachman-Soled and Malkin, Tal and Wee, Hoeteck},
	editor = {Canetti, Ran}
}
