1. An information embedding device, comprising: a memory; and a processor configured to execute a procedure, the procedure including: from an image that is stored in the memory, detecting, as an embedding target pixel block, a pixel block having a pixel value that, after being changed by a specific value corresponding to information to be embedded into the image, will be within a first specific range of an average value of pixel values of a surrounding pixel block; and changing the pixel value of the detected embedding target pixel block by the specific value.