To provide an alteration detecting technology not requiring the management of an encryption key and self-concluding in objective data for preventing alteration.

A watermark padding section 30 pads an encryption key K, as a watermark, in input host data P to create key padding host data w which is then imparted to a hash forming section 32 and a signature adding section 36. The hash forming section 32 forms hash h by mapping the key padding host data w with a monodirectivity function and imparts the hash to an encrypting section 34. The encrypting section 34 encrypts the hash h formed at the hash forming section 32 with the encryption key K to create a digital signature s. A signature adding section 36 adds the digital signature s created at the encrypting section 34 to the key padding host data w created at the watermark padding section 30 to output key padding host data with signature w+s.