To deeply encrypt and embed auxiliary information into image data, table generation means generates a table, based on a quantization error which occurs when image data S0 is converted from a first color space, to which the image data S0 belongs, to a second color space that is a destination of conversion. The table represents which color coordinate of a second color space a color coordinate of a first color space is mapped onto. In coding means, information H0 to be embedded is coded by referring to the table, whereby coded auxiliary information H1 is obtained. When the image data S0 is converted in color conversion means, the auxiliary information H1 is embedded into the quantization error, whereby image data S1 embedded with the auxiliary information H1 is obtained.