Steganography is the science of sending messages hidden in harmless
communications over a public channel so that an adversary eavesdropping 
on the channel cannot even detect the presence of the hidden
messages. Several models for steganography have been introduced. Some are
private-key settings, and the others are public-key settings. In this
paper, we propose a model of public-key steganography with authentication. We
formalize its security condition. We also construct a concrete scheme of
public-key steganography with authentication via a public-key
encryption scheme and a digital signature scheme.