An apparatus for and method of embedding a watermark into original information, transmitting the watermarked information, and reconstructing the watermark from the transmitted watermarked information include embedding a portion of a plurality of components constituting the watermark into the original information, and using the remaining portion of the components as keys for reconstructing the watermark. According to the method, since a size of data to be embedded is greatly reduced, degradation of the watermarked information is prevented, and the information becomes more robust against hacking attacks or errors occurring in a variety of ways when transmitting the information.