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 difintion 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.Category / Keywords: Non-malleable Codes, Non-malleable Commitments, Split-state Original Publication (with minor differences): ICALP (Track-A) 2016 Date: received 18 Feb 2015, last revised 16 Oct 2016 Contact author: pratyay85 at gmail com Available format(s): PDF | BibTeX Citation Version: 20161017:032703 (All versions of this report) Short URL: ia.cr/2015/129 Discussion forum: Show discussion | Start new discussion