  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. Dziembowski
et al. show existence of non-malleable codes for any class of tampering
functions of bounded size.
  We consider constructions of coding schemes against two well-studied classes
of tampering functions: bit-wise tampering functions (where the adversary
tampers each bit of the encoding independently) and split-state adversaries
(where two independent adversaries arbitrarily tamper each half of the encoded
sequence).
  1. For bit-tampering, we obtain explicit and efficiently encodable and
decodable codes of length $n$ achieving rate $1-o(1)$ and error (security)
$\exp(-\tilde{\Omega}(n^{1/7}))$. We improve the error to
$\exp(-\tilde{\Omega}(n))$ at the cost of making the construction Monte Carlo
with success probability $1-\exp(-\Omega(n))$. Previously, the best known
construction of bit-tampering codes was the Monte Carlo construction of
Dziembowski et al. (ICS 2010) achieving rate ~.1887.
  2. We initiate the study of seedless non-malleable extractors as a variation
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 existence of such
extractors, which implies that codes obtained from our reduction can achieve
rates arbitrarily close to 1/5 and exponentially small error. 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.
