Paper 2019/449

Limits to Non-Malleability

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin

Abstract

There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: "When can we rule out the existence of a non-malleable code for a tampering class $\mathcal{F}$?" We show that non-malleable codes are impossible to construct for three different tampering classes: 1. Functions that change $d/2$ symbols, where $d$ is the distance of the code; 2. Functions where each input symbol affects only a single output symbol; 3. Functions where each of the $n$ output bits is a function of $n-\log n$ input bits. We additionally rule out constructions of non-malleable codes for certain classes $\mathcal{F}$ via reductions to the assumption that a distributional problem is hard for $\mathcal{F}$, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for $\mathsf{NC}$, even assuming average-case variants of $P\not\subseteq\mathsf{NC}$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
non-malleable codesblack box impossibilitytamper-resilient cryptographyaverage case hardness
Contact author(s)
marshall @ cs columbia edu
danadach @ ece umd edu
mukul @ umd edu
tal @ cs columbia edu
History
2019-12-19: last of 3 revisions
2019-05-08: received
See all versions
Short URL
https://ia.cr/2019/449
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/449,
      author = {Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni and Tal Malkin},
      title = {Limits to Non-Malleability},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/449},
      year = {2019},
      url = {https://eprint.iacr.org/2019/449}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.