In an encoding device that creates an image in which data is embedded, an embedding unit divides an image into a plurality of blocks, and embeds data in the image based on a difference in value of characteristics of adjacent blocks; and a restriction information recording unit records use restriction information that restricts use of embedded data.