EECS500 Fall 2014 Department Colloquium

Mahdi Cheraghchi
Non-Malleable Codes: Applications and Constructions
White 411
November 20, 2014

The general area of non-malleable cryptography aims for providing the maximum degree of security in a cryptosystem; that is, securing against a tampering adversary who is able to observe an encrypted message and wishes to create the encryption of a correlated message. Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) are regarded as a central combinatorial tool in this area. A direct application of a non-malleable coding scheme makes it possible to secure a cryptosystem against tampering of memory components that store sensitive information. While this has been the original application leading to the development of non-malleable codes, the abstraction is so natural that has led to numerous other applications within non-malleable cryptography. As a coding-theoretic object extending the notion of error-detecting codes, non-malleable codes are also of interest to the information and coding theory communities.

In this talk, I discuss the background on non-malleable cryptography and introduce the notion of non-malleable codes. The talks follows by a discussion of the following:

1. How non-malleable codes can be applied to provide security against tampering of the storage;

2. Existence of non-malleable codes for any given family of tampering adversaries, and matching upper and lower bounds on their redundancy;

3. Constructions of non-malleable codes; including a general and efficient randomized construction as well as an explicit optimal constructions for the so-called “bit-tampering” adversaries;

4. More recent applications of non-malleable codes in cryptography, such as public-key encryption and string-commitment schemes secure against chosen ciphertext attacks;

5. Remaining open problems in the area.

Based on joint work with Venkatesan Guruswami and articles arXiv:1309.0458 (ITCS 2014) and arXiv:1309.1151 (TCC 2014).



Mahdi Cheraghchi is a post-doctoral fellow at the Computer Science and Artificial Intelligence Lab of MIT. Previously, he held similar positions at the Computer Science Department of Carnegie Mellon University and the University of Texas at Austin. He obtained his Ph.D. and M.Sc. degrees in computer science from EPFL, Switzerland, in 2010 and 2005, respectively and B.Sc. in computer engineering from Sharif University of Technology, Iran, in 2004. He has been awarded two Swiss NSF research grants and EPFL’s Patrick Denantes thesis prize. His research interests include the interconnections between coding theory and theoretical computer science, sparse recovery and high-dimensional geometry, information-theoretic privacy and security, and approximation algorithms.