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 $$ symbols, where $$ is the distance of the code; 2. Functions where each input symbol affects only a single output symbol; 3. Functions where each of the $$ output bits is a function of $$ input bits. We additionally rule out constructions of non-malleable codes for certain classes $$ via reductions to the assumption that a distributional problem is hard for $$, 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 $$, even assuming average-case variants of $$.