1. An information embedding device, comprising: a memory; and a processor configured to execute a procedure, the procedure including: acquiring an image including a plurality of pixel blocks from the memory; from the plurality of pixel blocks, determining a position of a pixel block having a 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 of values of surrounding pixels within the pixel block as a position of an embedding target pixel block, while distinguishing a position of a pixel block that is not determined to be the embedding target pixel block as a position of a non-embedding target pixel block, to thereby suppress image quality degradation due to embedding information into the image according to the determined positions of the embedding target pixel block and the non-embedding target pixel block; and changing the value of the embedding target pixel within the embedding target pixel block by the specific value corresponding to the information to be embedded into the image.