A digital signature with a subliminal channel, that allows a signer to embed subliminal messages in the digital signature. Any receivers may verify the signature, but can not discover the subliminal messages, only authorized receivers can extract the subliminal messages. In this paper we propose two digital signature schemes with subliminal channels based on discrete logarithms. Both schemes allow a signer to generate a digital signature, which may contain two or more subliminal messages for various subliminal receivers. Compared to the previously proposed schemes, both our schemes greatly reduce the size of secret keys that must be kept by the signer and the subliminal receiver; as well as the length of the digital signature. The security of the proposed schemes is based on the difficulty of computing the discrete logarithm problem.