Non-malleable coding against bitwise and split-state tampering
Venkatesan Guruswami · 2016
Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for pro-tecting the integrity of information against tampering attacks in situations where error-detection is impos-sible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable coding is possible against any class of adversaries of bounded size. In particular, Dziembowski et al. show that such codes exist and may achieve positive rates for any class of tampering functions of size at most 22 αn, for any constant α ∈ [0, 1). However, this result is existential and has thus attracted a great deal of subsequent research on explicit constructions of non-malleable codes against natural classes of adversaries. In this work, we consider constructions of coding schemes against two well-studied classes of tam-pering functions; namely, bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and the much more general class of split-state adversaries (where two indepen-dent adversaries arbitrarily tamper each half of the encoded sequence). We obtain the following results for these models.