  Syndrome coding has been proposed by Crandall in 1998 as a method to
stealthily embed a message in a cover-medium through the use of bounded
decoding. In 2005, Fridrich et al. introduced wet paper codes to improve the
undetectability of the embedding by nabling the sender to lock some components
of the cover-data, according to the nature of the cover-medium and the message.
Unfortunately, almost all existing methods solving the bounded decoding
syndrome problem with or without locked components have a non-zero probability
to fail. In this paper, we introduce a randomized syndrome coding, which
guarantees the embedding success with probability one. We analyze the
parameters of this new scheme in the case of perfect codes.
