According to an embodiment, a data embedding apparatus includes a data acquisition unit and an object generation unit. The data acquisition unit acquires first data formed from a first bit string to be embedded in a first object including a first line segment or a first curve. The object generation unit generates a second object, which includes a deformed line segment or a deformed curve having a displacement corresponding to the first bit string with respect to the first line segment or the first curve and in which the first data is embedded, by deforming at least one of the first line segment and the first curve of the first object based on the first bit string.