  Non-malleable extractors are generalizations and strengthening of standard
randomness extractors, that are resilient to adversarial tampering. Such
extractors have wide applications in cryptography and explicit construction of
extractors. In the well-studied models of two-source and affine non-malleable
extractors, the previous best constructions only work for entropy rate $>2/3$
and $1-\gamma$ respectively by Li (FOCS' 23).
  We present explicit constructions of two-source and affine non-malleable
extractors that match the state-of-the-art constructions of standard ones for
small entropy. Our main results include two-source and affine non-malleable
extractors (over $\mathsf{F}_2$) for sources on $n$ bits with min-entropy $k
\ge \log^C n$ and polynomially small error, matching the parameters of standard
extractors by Chattopadhyay and Zuckerman (STOC' 16, Annals of Mathematics' 19)
and Li (FOCS' 16), as well as those with min-entropy $k = O(\log n)$ and
constant error, matching the parameters of standard extractors by Li (FOCS'
23).
  Our constructions significantly improve previous results, and the parameters
(entropy requirement and error) are the best possible without first improving
the constructions of standard extractors. In addition, our improved affine
non-malleable extractors give strong lower bounds for a certain kind of
read-once linear branching programs, recently introduced by Gryaznov,
Pudl\'{a}k, and Talebanfard (CCC' 22) as a generalization of several
well-studied computational models. These bounds match the previously best-known
average-case hardness results given by Chattopadhyay and Liao (CCC' 23) and Li
(FOCS' 23), where the branching program size lower bounds are close to optimal,
but the explicit functions we use here are different.\ Our results also suggest
a possible deeper connection between non-malleable extractors and standard
ones.
