The present invention relates to a data processing apparatus. Additional information is embedded in coded data obtained by encoding image data, without increasing the amount of the coded data, and the data in which the additional information is embedded is correctly decoded into the image data and the additional information. An embedded compression encoder 11 encodes image data according to a predetermined coding rule, and destroys the coding rule based on additional information, thereby embedding the additional information. A decoder 12 restores the embedded coded data, obtained by embedding the additional information in the coded data, into the coded data encoded according to the coding rule, thereby decoding the additional information and also decoding the coded data into the image data.