Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS '10), provide roughly the following guarantee: if a codeword c encoding some message x is tampered to c' = f (c) such that c' not equal c, then the tampered message x' contained in c' reveals no information about x. The nonmalleable codes have applications to immunizing cryptosystems against tampering attacks and related -key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions f. However, in this paper we show "the next best thing": for any polynomial bound s given a -priori, there is an efficient non-malleable code that protects against all tampering functions f computable by a circuit of size s. More generally, for any family of tampering functions of size vertical bar F vertical bar <= 2(s), there is an efficient non-malleable code that protects against all f is an element of F. The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information -theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the "common reference string" model. We also introduce a new notion of non-malleable key derivation, which uses randomness x to derive a secret key y = h(x) in such a way that, even if x is tampered to a different value x' = f (x), the derived key y' = h(x') does not reveal any information about y. Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of "leakage -resilient storage" of Davi, Dziembowski, and Venturi (SCN '10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes.