Authenticated encryption schemes need redundancy schemes to link up the message blocks; however, these redundancies increase communication costs. To construct links without increasing communication costs, we propose a general solution for all the authenticated encryption schemes based on the discrete logarithm problem. Because the computation cost to construct links is small, the improved scheme adopting our solution is almost as efficient as the original one. Moreover, by our solution, the recipient can easily determine the missing message blocks, and then acknowledge the sender to send only these blocks again. The communication cost will be also reduced. Adopting our solution, we also propose two new authenticated encryption schemes with message linkage.
