An efficient authenticated encryption scheme with message linkages is proposed. For achieving both privacy and integrity in data communications, the proposed scheme requires smaller bandwidth and computational time when compared to previously proposed authenticated encryption schemes with message linkages. Moreover, the proposed scheme allows the verifier to recover and verify the message blocks simultaneously, and hence, the message recovery phase could be speeded up. The security of the proposed scheme is based on the authenticated encryption scheme as well as the one-way hash cryptographic function assumption.