The security of modern cryptosystems relies on the secrecy of the keys. Against the expectation that the keys used in cryptographic algorithms are perfectly secure, the keys can get compromised when implemented on physical devices. Because of the computational leakages from the execution of cryptographic algorithms, a variety of side-channel measurements can lead to full breaks of the targeted physical devices. Leakage-resilient cryptography aims at defining leakages in a generic model and designing provably secure primitives to capture side-channel attacks. For this purpose, several re-keying schemes are proposed to prevent encryption scheme from using the same key many times. In this paper, we propose a leakage-resilient authenticated encryption scheme, called Re-keying Code Book (RCB), that is secure against the side-channel attacks by combining with existing re-keying schemes. Our approach is to find efficient composition by combining two independent primitives, authenticated encryption, and re-keying schemes, rather than designing new algorithms. We also give the precise definitions of privacy and authenticity for authenticated encryption in a leakage-resilient model, and then, we provide the security proofs for RCB in a leakage-resilient model. © 2016, Springer Science+Business Media New York.