Block-wise Non-Malleable Codes

Non-malleable 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. It is known that non-malleable codes cannot exist for the class of all tampering functions and hence a lot of work has focused on explicitly constructing such codes against a large and natural class of tampering functions. One such popular, but restricted, class is the so-called split-state model in which the tampering function operates on different parts of the codeword independently. In this work, we consider a stronger adversarial model called block-wise 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 however that one cannot construct such codes that are non-malleable (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 non-malleable 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 information-theoretic 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 block-wise non-malleable codes from sub-exponentially hard one-way permutations. Moreover, we provide an interesting connection between block-wise non-malleable codes and non-malleable commitments. We show that any block-wise nonmalleable code can be converted into a non-malleable (w.r.t. opening) commitment scheme. Our techniques, quite surprisingly, give rise to a non-malleable commitment scheme (secure against so-called 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 non-interactive non-malleable (w.r.t. opening) commitment can be used to construct a block-wise non-malleable code only with 2 blocks. Unfortunately, such commitment scheme exists only under highly non-standard assumptions (adaptive one-way functions) and hence can not substitute our main construction.