An information embedding apparatus (100) which embeds information by changing the character spacing in a document image includes a discrimination unit (101) which discriminates a text area in the document image, a circumscribed rectangle extraction unit (102) which extracts the circumscribed rectangle of each character in the text area, a determination unit (103) which determines, based on the position and size of each extracted circumscribed rectangle, whether a portion having a character spacing smaller than a threshold exists, a reduction unit (104) which, for a character determined to have a character spacing smaller than the threshold, reduces the size of the character in at least the character arrangement direction, and a character position changing unit (105) which changes, in accordance with information to be embedded, the position of a character determined to have a character spacing equal to or larger than the threshold, and that of a character reduced.