Cryptology ePrint Archive: Report 2014/841

Explicit Non-malleable Codes Resistant to Permutations and Perturbations

Shashank Agrawal and Divya Gupta and Hemanta K. Maji and 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.

Category / Keywords: foundations / Non-malleable Codes, Explicit Construction, Information Theoretic, Non-malleable Commitment.

Date: received 15 Oct 2014

Contact author: hemanta maji at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141020:134920 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]