In a copy generation management on paper, the present invention aims to detect a falsification in embedded information and increase the capacity of embedded information while maintaining security. The image processing device embeds second additional information into document image data embedded with first additional information. The image processing device deletes a part where the first additional information is embedded in the document image data, and embeds the second additional information into the part of the first additional information thus deleted. The image processing device further embeds third information different from the first and second additional information at a position different from position at which the second additional information is embedded. Further, the embedding means embeds the third information at a position indicated by the second additional information.