This study presents a new (t, n) threshold-authenticated encryption scheme with message linkage to reduce the load on the signer using a division-of-labor signature. Only t signers can examine and sign an over-large message on behalf of the whole group, by dividing the whole message into a few readable sub-message blocks; then, each signer needs only to examine and sign the designated sub-message block rather than the whole message. Consequently, the load on the signer should be substantially reduced to improve the performance. Moreover, the proposed scheme is based on the elliptic curve cryptosystem, because of its highly efficient performance and comprehensiveness of security, supporting the practical use of the scheme.