Cryptology ePrint Archive: Report 2015/129

Block-wise Non-Malleable Codes

Nishanth Chandran and Vipul Goyal and Pratyay Mukherjee and Omkant Pandey and Jalaj Upadhyay

Abstract: 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 remove the above restriction by considering a stronger adversarial model that we call the 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 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 only the committer sends messages. We believe this result to be of independent interest.

Category / Keywords: Non-malleable Codes, Non-malleable Commitments, Split-state

Date: received 18 Feb 2015, last revised 3 Mar 2015

Contact author: pratyay85 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150303:082619 (All versions of this report)

Short URL: ia.cr/2015/129

Discussion forum: Show discussion | Start new discussion