In an information embedding apparatus, an image selecting unit selects original image data from an original image data group, a decoder detects a code from the selected original image data, and a candidate code determining unit calculates a candidate code. A candidate code embedding unit embeds the candidate code in the selected original image data.