Paper 2014/841

Explicit Non-malleable Codes Resistant to Permutations and Perturbations

Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran

Abstract

A non-malleable code protects messages against various classes of tampering. Informally, a code is non-malleable if the message contained in a tampered codeword is either the original message, or a completely unrelated one. Although existence of such codes for various rich classes of tampering functions is known, \emph{explicit} constructions exist only for ``compartmentalized'' tampering functions: \ie the codeword is partitioned into {\em a priori fixed} blocks and each block can {\em only be tampered independently}. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. In this paper, for the first time we construct explicit non-malleable codes against a natural class of non-compartmentalized tampering functions. We allow the tampering functions to {\em permute the bits} of the codeword and (optionally) perturb them by flipping or setting them to 0 or 1. We construct an explicit, efficient non-malleable code for arbitrarily long messages in this model (unconditionally). We give an application of our construction to non-malleable commitments, as one of the first direct applications of non-malleable codes to computational cryptography. We show that non-malleable {\em string} commitments can be ``entirely based on'' non-malleable {\em bit} commitments. More precisely, we show that simply encoding a string using our code, and then committing to each bit of the encoding using a {\em CCA-secure bit commitment} scheme results in a non-malleable string commitment scheme. This reduction is unconditional, does not require any extra properties from the bit-commitment such as ``tag-based'' non-malleability, and works even with physical implementations (which may not imply standard one-way functions). Further, even given a partially malleable bit commitment scheme which allows toggling the committed bit (instantiated, for illustration, using a variant of the Naor commitment scheme under a non-standard assumption on the PRG involved), this transformation gives a fully non-malleable string commitment scheme. This application relies on the non-malleable code being explicit.