Explicit non-malleable codes against bit-wise tampering and permutations

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings
EditorsMatthew Robshaw, Rosario Gennaro
Number of pages20
ISBN (Print)9783662479889
StatePublished - 2015
Event35th Annual Cryptology Conference, CRYPTO 2015 - Santa Barbara, United States
Duration: Aug 16 2015Aug 20 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other35th Annual Cryptology Conference, CRYPTO 2015
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Explicit non-malleable codes against bit-wise tampering and permutations'. Together they form a unique fingerprint.

Cite this