Mahdi Cheraghchi

Non-Malleable Coding Against Bit-wise and Split-State Tampering


Non-malleable coding, introduced by Dziembowski,
Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of
information against tampering attacks in situations where
error-detection is impossible. 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 exp(2^(c n)), for any constant c < 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 tampering 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 independent adversaries arbitrarily tamper each
half of the encoded sequence). We obtain the following results for
these models.

1. For bit-tampering adversaries, we obtain explicit and efficiently
encodable and decodable non-malleable codes of length n achieving rate
1-o(1) and negligible error (also known as "exact security").
Alternatively, it is possible to improve the error to nearly
exponentially small at the cost of making the construction Monte Carlo
with exponentially small failure probability (while still allowing a
compact description of the code). Previously, the best known
construction of bit-tampering coding schemes was due to Dziembowski et
al. (ICS 2010), which is a Monte Carlo construction achieving rate
close to .1887.

2. We initiate the study of seedless non-malleable extractors as a
natural variation of the notion of non-malleable extractors introduced
by Dodis and Wichs (STOC 2009). We show that construction of
non-malleable codes for the split-state model reduces to construction
of non-malleable two-source extractors. We prove a general result on
existence of seedless non-malleable extractors, which implies that
codes obtained from our reduction can achieve rates arbitrarily close
to 1/5 and exponentially small error. In a separate recent work, the
authors show that the optimal rate in this model is 1/2. Currently,
the best known explicit construction of split-state coding schemes is
due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves
vanishing (polynomially small) rate.

Based on a joint work with Venkatesan Guruswami (arXiv:1309.1151).