Arrangement/order of data in main information is changed in accordance with a value of additional information and with a predetermined encoding algorithm, and thus an electronic watermark of the additional information is embedded in the form of a change in the arrangement/order of the data without values of the data in the main information being changed. Time information of a plurality of performance data in the main information may be changed in accordance with the value of the additional information so that an electronic watermark of the additional information is embedded in the form of a combination of changes of the time information. Control may be made as to whether particular status information in music performance data should be used or not so that a one-bit electronic watermark corresponding to the use/non-use of the particular status information is embedded. The number of spaces in text data may be controlled so that an electronic watermark of a value corresponding to the number of spaces is embedded.