Welcome to the resource topic for 2019/449
Title:
Limits to Non-Malleability
Authors: Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, 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}.
ePrint: https://eprint.iacr.org/2019/449
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .