A complexity-theoretic model for public-key steganography with active attacks is introduced. The notion of
steganographic security against adaptive chosen-covertext attacks (SS-CCA)
and a relaxation called
steganographic security against publicly-detectable replayable adaptive chosen-covertext attacks (SS-PDR-CCA)
are formalized. These notions are closely related to
for public-key cryptosystems. In particular, it is shown that any SS-(PDR-)CCA stegosystem is a (PDR-)CCA-secure public-key cryptosystem and that an SS-PDR-CCA stegosystem for any covertext distribution with sufficiently large min-entropy can be realized from any PDR-CCA-secure public-key cryptosystem with pseudorandom ciphertexts.