@inproceedings{agrawal2015explicit,
author = {Agrawal, Shashank and Gupta, Divya and Maji, Hemanta K. and Pandey, Omkant and Prabhakaran, Manoj},
title = {Explicit Non-malleable Codes Against Bit-Wise Tampering and Permutations},
booktitle = {CRYPTO},
year = {2015},
month = {August},
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, explicit constructions exist only for “compartmentalized” tampering functions: i.e. the codeword is partitioned into a priori fixed blocks and each block can 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 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 string commitments can be “entirely based on” non-malleable bit commitments.},
url = {http://approjects.co.za/?big=en-us/research/publication/explicit-non-malleable-codes-against-bit-wise-tampering-and-permutations/},
}