**Limits to Non-Malleability**

*Marshall Ball and Dana Dachman-Soled and 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 symbols is a function of $n-\log n$ input symbols.

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}$.

**Category / Keywords: **foundations / non-malleable codes, black box impossibility, tamper-resilient cryptography, average case hardness

**Date: **received 2 May 2019, last revised 10 May 2019

**Contact author: **marshall at cs columbia edu, danadach@ece umd edu, mukul@umd edu, tal@cs columbia edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20190510:133930 (All versions of this report)

**Short URL: **ia.cr/2019/449

[ Cryptology ePrint archive ]