International Association
for Cryptologic Research

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 \\emph{split-state} model in which the tampering function operates on different parts of the codeword \\emph{independently}.

In this work, we remove the above restriction by considering a stronger adversarial model that we call the {\\em block-wise tampering} model. In this model, the adversary can tamper every block of the codeword, with the only restriction being that he can tamper every block at most once. As an example, if a codeword $c = (c_1,c_2)$, then the first tampering function $f_1$ could produce a tampered part $c_1\'=f_1(c_1)$ and the second tampering function $f_2$ could produce $c_2\' = f_2(c_1,c_2)$ which can depend on {\\em both} $c_2$ and $c_1$. An example is when the blocks are being sent one by one and the adversary must temper and send the first block before the second block comes along.

- Surprisingly, defining non-malleability in the block-wise tampering model is challenging. Our first contribution is that of providing a relaxed, yet meaningful definition of non-malleability for this model. Unfortunately, we show, that even this notion is impossible to achieve in the information-theoretic setting (i.e., when the tampering functions can be unbounded) and we must turn our attention towards computationally bounded adversaries.

- Next, we provide an interesting connection between block-wise non-malleable codes and non-malleable commitments. We show that any block-wise non-malleable code can be converted into a non-malleable (wrt opening) commitment. In the other direction, we show that any non-interactive non-malleable (wrt opening) commitment can be used to construct a block-wise non-malleable code (with $2$ blocks).

- While the above transformation gives us a construction of a block-wise non-malleable code, it is based on the highly non-standard assumption of adaptive one-way functions (which can only be realized based on assumptions such as Oracle DDH). As our main result, we show, how to construct a block-wise non-malleable code from any sub-exponentially hard one-way permutations. Our techniques, quite surprisingly, also give rise to a non-malleable commitment scheme (secure against so-called synchronizing adversaries), in which {\\em only} the committer sends messages. We believe this result to be of independent interest.