Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-078 | 21st April 2017 13:18

Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model


Authors: Nico Döttling, Jesper Buus Nielsen, Maceij Obremski
Publication: 1st May 2017 00:47
Downloads: 90


We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has been an open problem to construct such a code with information theoretic security. As a conceptual contribution we also introduce the notion of a one-way non-malleable code, which is the main new ingredient in our construction. In this notion, the tampering adversary's goal is to recover the encoded message rather than to distinguish the encodings of two messages. Our technical contribution is two-fold.

1) We show how to construct a full fledged continuously non-malleable code from a one-way continuously non-malleable code while only increasing the number of states by a constant factor.

2) We construct a one-way continuously non-malleable code in the constant split state model with information theoretic security.

ISSN 1433-8092 | Imprint