AUTHENTICATED ENCRYPTION SCHEMES WITH MESSAGE LINKAGE

Authenticated encryption schemes need redundancy schemes to link up th e message blocks; however, these redundancies increase communication c osts. To construct links without increasing communication costs, we pr opose 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 t hen acknowledge the sender to send only these blocks again. The commun ication cost will be also reduced. Adopting our solution, we also prop ose two new authenticated encryption schemes with message linkage.