In this paper, we propose EM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> A, a novel scheme that guarantees the authenticity of a mobile node (MN) and a relay node (RN) in a multi-hop-enabled Proxy Mobile IP (PMIP) network. EM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> A works in conjunction with a proposed scheme for key establishment, based on symmetric polynomials, to generate a shared secret key between MN and RN. This scheme achieves lower revocation overhead than that achieved by existing symmetric polynomial-based schemes. For a PMIP domain with n points of attachment, EM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> A achieves t×2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> -secrecy, whereas the existing authentication schemes achieve only t-secrecy. Computation and communication overhead analysis, as well as simulation results, demonstrate that EM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> A achieves low authentication delay and is suitable for seamless multi-hop IP communications.