Provided are an information processing apparatus, method, program and storage medium whereby prescribed additional information such as a digital watermark can be embedded directly in encoded data, and later extracted, without decoding data that has been compressed and encoded by the JPEG scheme, etc. First, encoded data, which is information that has been encoded, is input from an encoded data input unit (101). An embed coefficient is selected in an embed coefficient selector (102) block by prescribed block, and a code transformation unit (103) replaces the encoded data by different encoded data, which corresponds to the input encoded data, input using a transformation table (104), whereby a digital watermark is embedded.