Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-078 | 16th April 2018 14:37

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

RSS-Feed




Revision #1
Authors: Divesh Aggarwal, Nico Döttling, Jesper Buus Nielsen, Maceij Obremski, Erich Purwanto
Accepted on: 16th April 2018 14:37
Downloads: 59
Keywords: 


Abstract:

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs at ICS 2010, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. In particular, progress in the study of non-malleable codes and the related notion of non-malleable extractors has led to new insights and progress on even more fundamental problems like the construction of multi-source randomness extractors.

A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature, e.g., strong NMCs, super strong NMCs and continuous NMCs. The most general, and hence also the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. We present the first efficient 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 rst failed decoding.

We believe that our main technical result could be of independent interest and some of the ideas could in future be used to make progress on other related questions.



Changes to previous version:

The current version uses much less states than the previous version. It uses new and simpler techniques. The presentation has also been improved considerably.


Paper:

TR17-078 | 21st April 2017 13:18

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





TR17-078
Authors: Nico Döttling, Jesper Buus Nielsen, Maceij Obremski
Publication: 1st May 2017 00:47
Downloads: 201
Keywords: 


Abstract:

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