Algebraic Manipulation Detection (AMD) codes [CDFPW08] are keyless message authentication codes that protect messages against additive tampering by the adversary assuming that the adversary cannot “see” the codeword. For certain applications, it is unreasonable to assume that the adversary computes the added offset without any knowledge of the codeword c. Recently, Ahmadi and Safavi-Naini [AS13], and then Lin, Safavi-Naini, and Wang [LSW16] gave a construction of leakage-resilient AMD codes where the adversary has some partial information about the codeword before choosing added offset, and the scheme is secure even conditioned on this partial information. In this paper we show the bounds on the leakage rate ρ and the code rate K for leakage-resilient AMD codes. In particular we prove that and for the weak case (security is averaged over a uniformly random message) . These bounds hold even if adversary is polynomial-time bounded, as long as we allow leakage function to be arbitrary. We present the constructions of AMD codes that (asymptotically) fulfill above bounds for almost full range of parameters ρ and κ. This shows that above bounds and constructions are in-fact optimal. In the full version of the paper we also show that if a leakage function is computationally bounded (we use Ideal Cipher Model) then it is possible to break these bounds.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value". Although such codes do not exist if the family of "tampering functions" cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families cF. The family which received the most attention [DPW10,LL12,DKO13,ADL14,CG14a,CG14b] is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L|=|R|=O(|x|).