A data embedding device includes a dynamic image storage unit storing inter-frame prediction coded dynamic image data, an embedding data storage unit storing embedding data that is embedded into the inter-frame prediction coded dynamic image data, and an embedding unit embedding the embedding data into a rounding direction flag contained per frame data in the inter-frame prediction coded dynamic image data.