Abstract
Nonmalleable codes, introduced by Dziembowski, Pietrzak, and Wichs (ICS'10) provide the guarantee that if a codeword c of a message m, is modified by a tampering function f to c', then c' either decodes to m or to "something unrelated" to m. In recent literature, a lot of focus has been on explicitly constructing such codes against a large and natural class of tampering functions such as splitstate model in which the tampering function operates on different parts of the codeword independently.
In this work, we consider a stronger adversarial model called blockwise tampering model, in which we allow tampering to depend on more than one block: if a codeword consists of two blocks c = (c1, c2), then the first tampering function f1 could produce a tampered part c'_1 = f1(c1) and the second tampering function f2 could produce c'_2 = f2(c1, c2) depending on both c2 and c1. The notion similarly extends to multiple blocks where tampering of block ci could happen with the knowledge of all cj for j <= i. We argue this is a natural notion where, for example, the blocks are sent one by one and the adversary must send the tampered block before it gets the next block.
A little thought reveals that it is impossible to construct such codes that are nonmalleable (in the standard sense) against such a powerful adversary: indeed, upon receiving the last block, an adversary could decode the entire codeword and then can tamper depending on the message. In light of this impossibility, we consider a natural relaxation called nonmalleable codes with replacement which requires the adversary to produce not only related but also a valid codeword in order to succeed. Unfortunately, we show that even this relaxed definition is not achievable in the informationtheoretic setting (i.e., when the tampering functions can be unbounded) which implies that we must turn our attention towards computationally bounded adversaries.
As our main result, we show how to construct a blockwise nonmalleable code (BNMC) from subexponentially hard oneway permutations. We provide an interesting connection between BNMC and nonmalleable commitments. We show that any BNMC can be converted into a nonmalleable
(w.r.t. opening) commitment scheme. Our techniques, quite surprisingly, give rise to a nonmalleable commitment scheme (secure against socalled synchronizing adversaries), in which only the committer sends messages. We believe this result to be of independent interest. In the other direction, we show that any noninteractive nonmalleable (w.r.t. opening) commitment can be used to construct BNMC only with 2 blocks. Unfortunately, such commitment scheme exists only under highly nonstandard assumptions (adaptive oneway functions) and hence can not substitute our main construction.
BibTeX  Entry
@InProceedings{chandran_et_al:LIPIcs:2016:6310,
author = {Nishanth Chandran and Vipul Goyal and Pratyay Mukherjee and Omkant Pandey and Jalaj Upadhyay},
title = {{BlockWise NonMalleable Codes}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {31:131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6310},
URN = {urn:nbn:de:0030drops63102},
doi = {10.4230/LIPIcs.ICALP.2016.31},
annote = {Keywords: Nonmalleable codes, Nonmalleable commitments, Blockwise Tampering, Complexityleveraging}
}
Keywords: 

Nonmalleable codes, Nonmalleable commitments, Blockwise Tampering, Complexityleveraging 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 