  Randomness extractors and error correcting codes are fundamental objects in
computer science. Recently, there have been several natural generalizations of
these objects, in the context and study of tamper resilient cryptography. These
are seeded non-malleable extractors, introduced in [DW09]; seedless
non-malleable extractors, introduced in [CG14b]; and non-malleable codes,
introduced in [DPW10].
  However, explicit constructions of non-malleable extractors appear to be
hard, and the known constructions are far behind their non-tampered
counterparts.
  In this paper we make progress towards solving the above problems. Our
contributions are as follows.
  (1) We construct an explicit seeded non-malleable extractor for min-entropy
$k \geq \log^2 n$. This dramatically improves all previous results and gives a
simpler 2-round privacy amplification protocol with optimal entropy loss,
matching the best known result in [Li15b].
  (2) We construct the first explicit non-malleable two-source extractor for
min-entropy $k \geq n-n^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and
error $2^{-n^{\Omega(1)}}$.
  (3) We initiate the study of two natural generalizations of seedless
non-malleable extractors and non-malleable codes, where the sources or the
codeword may be tampered many times. We construct the first explicit
non-malleable two-source extractor with tampering degree $t$ up to
$n^{\Omega(1)}$, which works for min-entropy $k \geq n-n^{\Omega(1)}$, with
output size $n^{\Omega(1)}$ and error $2^{-n^{\Omega(1)}}$. We show that we can
efficiently sample uniformly from any pre-image. By the connection in [CG14b],
we also obtain the first explicit non-malleable codes with tampering degree $t$
up to $n^{\Omega(1)}$, relative rate $n^{\Omega(1)}/n$, and error
$2^{-n^{\Omega(1)}}$.
