International Association
for Cryptologic Research

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.