Electronic watermark processing apparatus

0001The present invention relates to an electronic watermark processing apparatus for embedding and hiding, into a digital work such as audio or image data, certain information called watermark or fingerprint (to be referred to as watermark hereinafter) associated with the copyright owner of the digital work or user of the digital data without making the watermark perceptible to the copyright owner or user.

0002With an advance in digital technology, various works such as movies, music, and photographs are being distributed as digital data (digital works). Under this circumstance, a serious problem is posed in association with copyrights of digital works. In recent years, an electronic watermark technology has received a great deal of attention as a technique of preventing illicit use of digital works. This technique is used to protect the right of a copyright owner or provider of data. Watermark associated with the copyright owner, the provider, or a user is embedded into the data without making the watermark recognizable to the user. If the data is illicitly used, the user can be specified.

0003Prevention of illicit use will be described in more detail. Before distribution of a digital work, the copyright owner embeds watermark for identifying the user. The user may copy the digital work without permission of the copyright owner and sell the copy to a third party. Upon finding a copy which is suspected of illicit copying, the copyright owner can detect the watermark from the data to specify the user who has copied it without permission and illicitly sold the copy, and impose a penalty on the user. Since the user cannot know the type of watermark or the embedding position thereof in the digital data, he/she cannot remove the watermark.

0004However, if the watermark is including information for identifying the user and is different for every user, the presence of the watermark can be easily known when two or more users collude. More specifically, when a user "A" and a user "B" calculate the difference between the two data, the embedding position can be estimated, though the watermark of the user "A" and that of the user "B" cannot be identified. For this reason, the users can alter the watermark by adding a certain signal to this difference data.

0005For example, watermark information as 2-bit digital data for identifying each of three users "A", "B", and "C" is embedded into digital data of an MPEG moving image. The ID mark of the user "A" is "10", that of the user "B" is "01", and that of the user "C" is "11". The ID mark "00" does not identify any users. To embed the 2-bit ID mark, the first bit is embedded into the luminance data of a pixel (x, y) of an i-th frame. When the first bit data is "1", luminance data V is set to be V + 1. When the first bit data is "0", the luminance data V is not changed. The second bit data is embedded into the luminance data of a pixel (v, w) of a j-th frame. When the second bit data is "1", luminance data V' is set to be V' + 1. When the first bit data is "0", the luminance data V' is not changed.

0006The user can be specified by checking the luminance data of the pixel (x, y) of the i-th frame and that of the pixel (v, w) of the j-th frame. The ID mark "10" of the user "A" is (V + 1, V'), and the ID mark "01" of the user "B" is (V, V' + 1).

0007By comparing the data, the users "A" and "B" can detect the differences between luminance data of the pixel (x, y) of the i-th frame and that of the pixel (v, w) of the j-th frame, i.e., can know that the watermark for identifying the users is embedded into these data. These luminance data can be rewritten to alter the identification information such that it represents another user. <ul id="ul0001" list-style="none" compact="compact"><li>(i; x, y) : (V + 1, or V) → V + ΔV</li></ul>

0008This means that the luminance data V + 1 or V of the pixel (x, y) of the i-th frame is rewritten to V + ΔV. <ul id="ul0002" list-style="none" compact="compact"><li>(j; v, w) : (V', or V' + 1) → V' + ΔV'</li></ul>

0009This means that the luminance data V' or V' + 1 of the pixel (v, w) of the j-th frame is rewritten to V' + ΔV'.

0010How to select ΔV and ΔV' will be considered. <ul id="ul0003" list-style="none" compact="compact"><li>(a) ΔV = 1, ΔV' = 0 This is the same as the ID mark of the user "A". </li><li>(b) ΔV = 0, ΔV' = 1 This is the same as the ID mark of the user "B". </li><li>(c) ΔV = 1, ΔV' = 1 This is the ID mark of the user "C". </li><li>(d) ΔV = 0, ΔV' = 0 This ID mark is not defined and therefore specifies nobody. </li></ul>

0011For the users "A" and "B", ΔV and ΔV' need be rewritten to data other than (a) and (b) because the identification information (a) and (b) represent the users "A" and "B" themselves, respectively. Although the users "A" and "B" do not recognize the specific meaning of the rewritten identification information (c) and (d), they can estimate that this rewrite allows to alter the identification information representing themselves.

0012The watermark embedding processing described above is a merely example, and watermark can be embedded into digital data in a variety of manners as more general transformation.

0013As described above, the conventional electronic watermark embedding technique allows to embed and hide watermark for identifying a user without making the watermark perceptible to the user. However, when a plurality of users collude and compare their data, information associated with the position where the watermark is embedded can be obtained. This undesirably facilitates forgery or erasure of the watermark.

0014Accordingly, it is an object of the present invention to provide an electronic watermark processing apparatus for embedding and hiding watermark associated with a user of digital data into the data such that even when a plurality of users collude and compare their data, information associated with the embedded watermark cannot be sufficiently obtained to result in a difficulty in forgery or erasure of the watermark.

0015According to the present invention, there is provided an electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein information representing whether the user is included in arbitrary two of all users who may receive the digital data is used as the information for identifying the user.

0016According to the present invention, there is provided another electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein information representing whether the user is one of users who may receive the digital data is used as the information for identifying the user.

0017According to the present invention, there is provided a still another electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein an order is set for users who may receive the digital data, and information representing whether an ordinal number of the user is smaller than, equal to, or larger than that of one of the users is used as the information for identifying the user.

0018According to the present invention, there is provided a still further electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein an order is set for users who may receive the digital data, and letting N be the total number of users who may receive the digital data, relatively prime numbers <u>p</u> and <u>q</u> for satisfying N ≦ p × q are obtained, and information representing whether a remainder of an order n of the user to modulus <u>p</u> is smaller than, equal to, or larger than each of 0 to p-1 and information representing whether a remainder of the order n of the user to modulus <u>q</u> is smaller than, equal to, or larger than each of 0 to q-1 are used as the information for identifying the user.

0019According to the present invention, there is provided an identification information generation apparatus for generating identification information to be added to digital data to be distributed to a user without making the information perceptible to the user, wherein information representing whether an object to be identified is included in arbitrary two of all identification objects is generated as the information for identifying the object.

0020According to the present invention, there is provided another identification information generation apparatus for generating identification information to be added to digital data to be distributed to a user without making the information perceptible to the user, wherein information representing whether an object to be identified is one of all identification objects is generated as the information for identifying the object.

0021According to the present invention, there is provided a still another identification information generation apparatus for generating identification information to be added to digital data to be distributed to a user without making the information perceptible to the user, wherein an order is set for identification objects, and information representing whether an ordinal number of an object to be identified is smaller than, equal to, or larger than that of one of the identification objects is generated as the information for identifying the object.

0022According to the present invention, there is provided an ID mark processing apparatus comprising: <ul id="ul0004" list-style="none" compact="compact"><li>a syntax analyzer for syntax-analyzing digital data and outputting information associated with a token representing a certain meaning of a set of data;</li><li>a data transformation assignor storing various data transformation contents, the data transformation assignor outputting the data transformation contents corresponding to the token;</li><li>means for generating an ID mark in accordance with information unique to an identification object; and</li><li>ID mark embedding means for changing a predetermined portion of the digital data in accordance with the ID mark and the data transformation contents output from the data transformation assignor.</li></ul>

0023According to the present invention, there is provided another ID mark processing apparatus comprising: <ul id="ul0005" list-style="none" compact="compact"><li>a syntax analyzer for syntax-analyzing digital data and outputting information associated with a token representing a certain meaning of a set of data;</li><li>a data transformation assignor storing various data transformation contents together with a cost representing the degree of change in data by data transformation, the data transformation assignor outputting the data transformation contents corresponding to the token;</li><li>means for accumulating the degree of change in data after transformation;</li><li>means for generating an ID mark in accordance with information unique to an identification object;</li><li>ID mark embedding means for changing a predetermined portion of the digital data in accordance with the ID mark and the data transformation contents output from the data transformation assignor; and</li><li>means for inhibiting an operation of the ID mark embedding means when an accumulation value of the degree of change in data, which is accumulated in the accumulation means, exceeds a predetermined value.</li></ul>

0024According to the present invention, there is provided an identification information detection apparatus for reading identification information from digital data in which the identification information is embedded without making the information perceptible to a user, comprising: <ul id="ul0006" list-style="none" compact="compact"><li>means for extracting an ID mark embedded at a predetermined position of the digital data; and</li><li>means for decoding the extracted ID mark to obtain the identification information.</li></ul>

0025According to the present invention, there is provided an identification information reading method of reading identification information for identifying a user from digital data in which the information is embedded by an electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user and wherein information representing whether the user is included in arbitrary two of all users who may receive the digital data is used as the information for identifying the user, comprising the steps of: <ul id="ul0007" list-style="none" compact="compact"><li>reading a portion corresponding to each user pair from the identification information extracted from the digital data; and</li><li>determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that the user pair includes a user corresponding to the digital data, or another mark,</li><li>wherein a user pair for which it is determined that the portion has the mark embedded by the electronic watermark processing apparatus and representing that the user pair includes the user corresponding to the digital data is estimated as a candidate pair of colluding users.</li></ul>

0026According to the present invention, there is provided another identification information reading method of reading identification information for identifying a user from digital data in which the information is embedded by an electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein information representing whether the user is one of users who may receive the digital data is used as the information for identifying the user, comprising the steps of: <ul id="ul0008" list-style="none" compact="compact"><li>reading a portion corresponding to each user from the identification information extracted from the digital data; and</li><li>determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that the user is a user corresponding to the digital data, or another mark,</li><li>wherein a user for which it is determined that the portion has the mark embedded by the electronic watermark processing apparatus and representing that the user is the user corresponding to the digital data is estimated as a candidate of a colluding user.</li></ul>

0027According to the present invention, there is provided a still another identification information reading method of reading identification information for identifying a user from digital data in which the information is embedded by an electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein an order is set for users who may receive the digital data, and information representing whether an ordinal number of the user is smaller than, equal to, or larger than that of one of the users is used as the information for identifying the user, comprising the steps of: <ul id="ul0009" list-style="none" compact="compact"><li>1) sequentially reading a portion corresponding to each user from the identification information extracted from the digital data;</li><li>2) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that an ordinal number of the user is smaller than that of a user corresponding to the digital data or another data, and repeating the steps 1) and 2) until another mark is detected;</li><li>3) sequentially reading a portion corresponding to each user from a portion next to another mark which has been detected for the first time in the step 2);</li><li>4) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that the ordinal number of the user is larger than that of the user corresponding to the digital data or another data, and repeating the steps 3) and 4) until another mark is detected; and</li><li>5) repeating the steps 3), 4), and 5) until a final bit of the extracted identification information is reached, wherein the step 2) comprises estimating, as a first colluding user candidate, the user corresponding to the portion having another mark detected for the first time, and</li><li>the step 4) comprises estimating, as a second colluding user candidate, the user corresponding to the portion having another mark finally detected.</li></ul>

0028According to the present invention, there is provided a still further identification information reading method of reading identification information for identifying a user from digital data in which the information is embedded by an electronic watermark processing apparatus for embedding information for identifying a user into digital data to be distributed to the user without making the information perceptible to the user, wherein an order is set for users who may receive the digital data, and letting N be the total number of users who may receive the digital data, relatively prime numbers <u>p</u> and <u>q</u> for satisfying N ≦ p× q are obtained, and information representing whether a remainder of an order <u>n</u> of the user to modulus <u>p</u> is smaller than, equal to, or larger than each of 0 to p-1 and information representing whether a remainder of the order <u>n</u> of the user to modulus <u>q</u> is smaller than, equal to, or larger than each of 0 to q-1 are used as the information for identifying the user, comprising the steps of: <ul id="ul0010" list-style="none" compact="compact"><li>1) sequentially reading a portion corresponding to each user to modulus <u>p</u> from the identification information extracted from the digital data;</li><li>2) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that a remainder of an order of the user to modulus <u>p</u> is smaller than a remainder of an order of a user corresponding to the digital data to modulus <u>p</u> or another mark, and repeating the steps 1) and 2) until another mark is detected;</li><li>3) sequentially reading a portion corresponding to the remainder of the order of each user to modulus <u>p</u> from a portion next to another mark which has been detected for the first time in the step 2);</li><li>4) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that the remainder of the order of the user to modulus <u>p</u> is larger than the remainder of the order of the user corresponding to the digital data to modulus <u>p</u> or another mark, and repeating the steps 3) and 4) until another mark is detected;</li><li>5) repeating the steps 3), 4), and 5) until all portions of orders of users to modulus <u>p</u> are read from the extracted identification information;</li><li>6) after all portions of the remainders of the orders of the users to modulus <u>p</u> are read from the extracted identification information in the step 5), sequentially reading, from the next portion, a portion corresponding to the remainder of the order of each user to modulus <u>q</u>;</li><li>7) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that a remainder of the order of the user to modulus <u>q</u> is smaller than the remainder of the order of the user corresponding to the digital data to modulus <u>q</u> or another mark, and repeating the steps 6) and 7) until another mark is detected;</li><li>8) sequentially reading a portion corresponding to the remainder of the order of each user to modulus <u>q</u> from a portion next to another mark which has been detected for the first time in the step 7);</li><li>9) determining whether the portion has a mark embedded by the electronic watermark processing apparatus and representing that the remainder of the order of the user to modulus <u>q</u> is larger than the remainder of the order of the user corresponding to the digital data to modulus <u>q</u> or another mark, and repeating the steps 8) and 9) until another mark is detected; and</li><li>10) repeating the steps 8), 9), and 10) until all portions of orders of the users to modulus <u>q</u> are read from the extracted identification information, wherein a Chinese remainder theorem is applied to a set of the remainder of the order of the user to modulus <u>p</u> corresponding to the portion having another mark detected for the first time in the step 2), the remainder of the order of the user to modulus <u>p</u> corresponding to the portion having another mark finally detected in the step 4), the remainder of the order of the user to modulus <u>q</u> corresponding to the portion having another mark detected for the first time in the step 7), and the remainder of the order of the user to modulus <u>q</u> corresponding to the portion having another mark finally detected in the step 9), thereby estimating a candidate of a colluding user.</li></ul>

0029This summary of the invention does not necessarily describe all necessary features so that the invention may also be a sub-combination of these described features.

0030This invention can be more fully understood from the following detailed description when taken in conjunction with the accompanying drawings, in which: <ul id="ul0011" list-style="none" compact="compact"><li>FIG. 1 is a block diagram showing the arrangement of an electronic watermark processing apparatus according to a first embodiment of the present invention;</li><li>FIG. 2 is a block diagram showing the arrangement of a modification of the first embodiment;</li><li>FIG. 3 is a block diagram showing details of the arrangement of a data transformation assignor shown in FIG. 1;</li><li>FIG. 4 is a block diagram showing a modification of the data transformation assignor shown in FIG. 1;</li><li>FIG. 5 is a flow chart showing an ID mark generation algorithm in the first embodiment;</li><li>FIG. 6 is a block diagram showing the arrangement of a watermark detection apparatus in the first embodiment;</li><li>FIG. 7 is a block diagram showing the arrangement of a watermark detection apparatus in the modification of the first embodiment;</li><li>FIG. 8 is a flow chart showing an ID mark decoding algorithm in the first embodiment;</li><li>FIG. 9 is a flow chart showing an ID mark generation algorithm in a second embodiment of the present invention;</li><li>FIG. 10 is a flow chart showing an ID mark decoding algorithm in the second embodiment;</li><li>FIG. 11 is a flow chart showing an ID mark generation algorithm in a third embodiment of the present invention;</li><li>FIG. 12 is a flow chart showing an ID mark decoding algorithm in the third embodiment;</li><li>FIG. 13 is a flow chart showing a first half of an ID mark generation algorithm in a fourth embodiment of the present invention;</li><li>FIG. 14 is a flow chart showing a second half of the ID mark generation algorithm in the fourth embodiment of the present invention;</li><li>FIG. 15 is a flow chart showing a first half of an ID mark decoding algorithm in the fourth embodiment of the present invention;</li><li>FIG. 16 is a flow chart showing a second half of the ID mark decoding algorithm in the fourth embodiment of the present invention; and</li><li>FIG. 17 is a flow chart showing an ID mark generation algorithm in a modification of the fourth embodiment of the present invention.</li></ul>

0031A preferred embodiment of an electronic watermark processing apparatus according to the present invention will now be described with reference to the accompanying drawings.

First Embodiment

0032FIG. 1 is a block diagram showing the entire arrangement of an electronic watermark processing apparatus of the first embodiment. Digital data (to be referred to as original contents hereinafter) as a work is supplied to a syntax analyzer 10 and a data transformer 12. The contents are constituted by a set of data having a plurality of certain meanings. This set of data will be referred to as a token hereinafter in this specification. In coding, e.g., MPEG video data, various header codes or VLC codes etc. are used as a token. The position in the contents and value of each token can be known by analyzing the syntax of the data. The syntax analyzer 10 analyzes the syntax of the original contents to obtain the token. Information associated with the token is supplied to a data transformation assignor 14. The data transformation assignor 14 supplies data transformation rules to the data transformer 12 in accordance with the token.

0033A user ID unique to a user is supplied to an ID mark generator 16. An ID mark allowing to specify the user name is generated and supplied to an error detection/correction coding encoder 18. The error detection/correction coding encoder 18 performs error detection/correction coding of the user ID mark and supplies the coded ID mark to the data transformer 12. The error detection/correction coding encoder 18 is not essential for the present invention and may be omitted, as shown in FIG. 2.

0034The data transformer 12 processes a predetermined bit of the contents, in correspondence with the ID mark, in accordance with a data transformation instruction supplied from the data transformation assignor 14, thereby embedding the ID mark (electronic watermark) into the contents. As a method of embedding an electronic watermark into, e.g., an MPEG moving image, luminance data V of a pixel (x, y) of an i-th frame is set to be V + 1 when the data to be embedded is "1" or V when the data to be embedded is "0", thereby embedding the electronic watermark, as in the prior art.

0035FIG. 3 is a block diagram showing details of the arrangement of the data transformation assignor 14. The data transformation assignor 14 comprises a state transition storage 22 for storing various rules of the state transition, data transmission for the transitions, a state buffer 26 for storing the current state of contents, a cost evaluation rule storage 28 for storing a cost evaluation rule, a cost accumulator 20, and a controller 24 for controlling the respective sections. Information associated with the token from the syntax analyzer 10 is supplied to the controller 24. Data after electronic watermark embedding is supplied from the data transformer 12 to the controller 24. The controller 24 outputs a data transformation instruction representing the contents of data transformation read out from the state transition storage 22 to the data transformer 12. The state transition storage 22 stores the contents of data transformation (data embedding rule) for each precondition, the transition state as the state after transformation, and the cost (a quantity for determining whether the contents quality such as an image quality or the data length largely changes due to embedding of watermark). Every time data transformation (watermark embedding) is performed, a transition state corresponding to the selected contents of data transformation is set in the state buffer 26. The controller 24 searches for a precondition corresponding to the token, reading out corresponding contents of data transformation, and supplies the contents of data transformation to the data transformer 12. If it is estimated on the basis of the cost that the data largely changes due to watermark embedding, no data transformation is performed and, if exists, other appropriate data transformation is selected. The cost evaluation rule storage 28 is arranged for this purpose. The storage 28 compares the cost accumulated in the cost accumulator 20 with the cost corresponding to the contents of data transformation selected in the state transition storage 22. If a change in data beyond a predetermined value is expected, rule of data transformation is not executed.

0036The data transformer 12 returns to information associated with the actually transformed data to the controller 24. The controller 24 calculates the cost on the basis of the data, and the cost accumulator 20 accumulates the cost.

0037In the present invention, determination of a change in quality of contents, which is made on the basis of the cost, is not essential, and the cost determination may be omitted. In this case, the item of "cost" is omitted from the state transition storage 22, as shown in FIG. 4, and the cost accumulator 20 and the cost evaluation rule storage 28 are omitted.

0038As the characteristic feature of the first embodiment, information representing not only the user but also whether the user is included in a user pair, i.e., arbitrary two of all users, who may receive the digital data is used for a watermark, unlike the prior art.

0039Assuming that digital data of an MPEG moving image is used by three users "A", "B", and "C", a 3-bit ID mark representing whether one of the users is included in the pair of users "A" and "B", the pair of users "B" and "C", or the pair of users "A" and "C" is embedded. When the user is included in the pair of users "A" and "B", the first bit of the ID data is set at "1". When the user is included in the pair of users "B" and "C", the second bit of the ID data is set at "1". When the user is included in the pair of users "A" and "C", the third bit of the ID data is set at "1". The remaining bit data are set at "0". As in the prior art, to embed this 3-bit ID mark, when the first bit data is "1", luminance data V1 of a pixel (x1, y1) of a first frame is set to be "V1 + 1"; otherwise, the luminance data V1 is not changed. When the second or third bit data is "1", a corresponding one of luminance data V2 and V3 of pixels (x2, y2) and (x3, y3) of second and third frames is set at "V2 + 1 or V3 + 1; otherwise, the luminance data V2 or V3 is not changed.

0040Such luminance data transformation is performed by the data transformer 12.

0041A case wherein the user illicitly copies such marked contents without permission of the copyright owner and sells it will be described next. As in the prior art, the users "A" and "B" try to collude and compare their data to alter the ID mark. It can be estimated that the difference data, i.e., the luminance data V2 of the pixel (x2, y2) of the second frame or the luminance data V3 of the pixel (x3, y3) of the third frame is part of the watermark unique to the user "A" or user "B", so the users "A" and "B" try to rewrite the watermark in the following manner. <ul id="ul0012" list-style="none" compact="compact"><li>(f2; x2, y2) : (V2 or V2 + 1) → V2 + ΔV2</li></ul>

0042This means that the luminance data V2 or V2 + 1 of the pixel (x2, y2) of the second frame is rewritten to V2 + ΔV2. <ul id="ul0013" list-style="none" compact="compact"><li>(f3; x3, y3) : (V3 or V3 + 1) → V3 + ΔV3</li></ul>

0043This means that the luminance data V3 or V3 + 1 of the pixel (x3, y3) of the third frame is rewritten to V3 + ΔV3.

0044How to select ΔV2 and ΔV3 will be considered. <ul id="ul0014" list-style="none" compact="compact"><li>(a) ΔV2 = 1, ΔV3 = 0 This is the same as the ID mark embedded for the user "B". </li><li>(b) ΔV2 = 0, ΔV3 = 1 This is the same as the ID mark embedded for the user "A". </li><li>(c) ΔV2 = 1, ΔV3 = 1 This means that the colluders are included in the users "A", "B", and "C" although the two cannot be specified. </li><li>(d) ΔV2 = 0, ΔV3 = 0 This means that the colluders are the users "A" and "B". </li></ul>

0045Due to the same reasoning as in the prior art, the users "A" and "B" determine that ΔV2 and ΔV3 need be rewritten to data other than (a) and (b) because the pieces of identification information (a) and (b) represent the users "B" and "A" themselves, respectively. The users "A" and "B" rewrite ΔV2 and ΔV3 to the data (c) or (d) and re-distribute the illicit copy. However, unlike the prior art, when the data is rewritten to the data (d), it is obvious that the colluders are the users "A" and "B". In (c), the colluders cannot be specified. However, when the ID mark is embedded L times, i.e., into 3L pixels, all of the L ID marks accidentally have the data (d) at a probability of only (1/2)^L. This is sufficiently effective in practice.

0046As described above, according to the first embodiment, information representing whether a user is included in a user pair, i.e., arbitrary two of all users, who may receive the digital data, is embedded. With this arrangement, even when a plurality of users collude and alter the difference data to data other than those representing themselves, the data representing the user pair remains in the altered data, and the collusion fails.

0047The ID mark is not limited to the information for identifying the user name, and the present invention can also be applied to a case wherein information for identifying a general object is added to digital data to be transferred to the user without making the information perceptible to the user. For example, the information can be transferred as part of a message without making the meaning of the mark noticeable to the user, though the user can perceive the presence of the mark. As information other than the user name identification information, information for identifying the date and time of use, the user terminal, or the digital data, the digital data transfer path, or a description of a use condition can be used.

0048FIG. 5 is a flow chart showing an ID mark generation algorithm in the first embodiment. This algorithm can be applied not only the user name ID mark but also a general ID mark. In step S2, an order is set for identification object subsets (pairs of arbitrary two of all users who may receive the digital data) p₁, p₂, ..., p_max for convenience (p₁ &lt; p₂ &lt; ... &lt; p_max). In step S4, a user "u" as an identification object is specified. In step S6, 1 is set as a variable <u>i</u>, and a bit length of 0 is set as an initial value of "code". In step S8, it is determined whether the user "u" is included in a subset p_i. If YES in step S8, an ID mark bit code (u ε p_i) (= 1: in the first embodiment) is generated in step S10 to concatenate to the preceding ID mark. If NO in step S8, an ID mark bit code (u ≠ p_i) (= 0: in the first embodiment) is generated in step S12 to concatenate to the preceding ID mark. The mark generated in step S10 or S12 is not limited to 1 bit and may be a plurality of bits. The symbol ≠ means that the user does not belong to the set (negation of ε). In step S14, it is determined whether the variable <u>i</u> is larger than max (the total number of subsets). If NO in step S14, the variable <u>i</u> is incremented by one (+1) in step S16. The flow returns to step S8 to determine whether the user "u" is included in the next subset p_i. If YES in step S14, determination whether the user "u" is included is complete for all the subsets p_i. It is determined that each bit of the ID mark is completely generated to concatenate to the preceding ID mark, and the operation is ended.

0049FIG. 6 shows an example of a watermark detection apparatus used to identify a user who is suspected for having illicitly extracted watermark from contents when contents which are suspected to be an illicit copy are being distributed. To detect the watermark embedding position, original contents are supplied to a syntax analyser 40, and information associated with the token is input to a data transformation assignor 42, as in the electronic watermark processing apparatus shown in FIG. 1. The data transformation assignor 42 generates, from the token, transformation contents information representing the watermark embedding position and the transformation contents. Since the watermark embedding position and the transformation contents are determined in units of original contents, the transformation contents information need not be obtained from the token every time. Once the transformation contents information is obtained, the information may be stored in, e.g., a storage in units of contents and read out. In this case, a storage is arranged in place of the syntax analyser 40 and the data transformation assignor 42.

0050The marked contents and the transformation contents information from the data transformation assignor 42 are supplied to an ID mark extractor 44. The ID mark extractor 44 extracts the embedded ID mark from the contents in accordance with the transformation contents information. The extracted ID mark is supplied to an ID mark decoder 48 through an error detection/correction decoder 46 to detect the user ID in accordance with the ID mark. When the electronic watermark processing apparatus has no error detection/correction coding encoder 18, the error detection/correction decoder 46 is omitted. FIG. 7 shows a watermark detection apparatus having no error detection/correction decoder 46.

0051FIG. 8 shows the algorithm of the ID mark decoder 48 in the first embodiment. In step S202, the same order as in embedding is set for the identification object subsets (arbitrary two of all users who may receive the digital data) p₁, p₂, ..., P_max (p₁ &lt; p₂ &lt; ... &lt; p_max). In step S204, the input extracted mark is set as the initial value of "code". In step S206, 1 is set as the variable <u>i</u>, and the set of all user pairs {p₁, p₂, ..., p_max} is set for "candidate-pairs", i.e., the candidates of user pairs corresponding to colluders.

0052In step S208, it is determined whether the first bit of code is 1. If YES in step S208, the flow immediately advances to step S212. If NO in step S208, the user pair p_i is removed from "candidate-pairs" in step S210, and then, the flow advances to step S212. In step S212, it is determined whether the variable <u>i</u> is larger than max (the total number of subsets). If NO in step S212, the variable <u>i</u> is incremented by one (+1) in step S214. In step S216, "code" is shifted to the MSB by one bit, and the flow returns to step S208 to determine the first bit of "code". If YES in step S212, the operation is ended. After this, a user pair P remaining in "candidate-pairs" is estimated as a colluder pair.

0053The characteristic features of the algorithm shown in FIG. 8 will be summarized below. 1) A portion corresponding to each user pair p_i is read from the ID mark extracted from digital data, 2) it is determined whether the portion corresponds to "code_u" (u ε p_i) embedded on the basis of the algorithm shown in FIG. 5 or any other code, and 3) the user pair p_i for which it has been determined that the portion corresponds to "code_u" (u ε pi) can be estimated as a pair of colluding users.

0054When the ID mark is embedded L times, the above algorithm is executed L times. The user pair P always remaining in "candidate-pairs" in every execution of the algorithm is estimated as a colluder pair.

0055In the first embodiment, letting N be the number of users, the total number of subsets consisting of arbitrary user pairs is given by _NC₂. The code amount of the ID mark is represented on the order of N². As compared to the prior art in which the code amount is on the order of log₂ N, the code amount increases although the arrangement is resistant to collusion of a plurality of users.

0056Other embodiments of watermark embedding which are resistant to alteration by collusion of users and can prevent an increase in a code amount of an ID mark will be described. The same reference numerals as in the first embodiment denote the same parts in the other embodiments, and a detailed description thereof will be omitted.

Second Embodiment

0057The arrangement of the apparatus of the second embodiment is the same as that of the first embodiment, and block diagrams showing the arrangement and a detailed description thereof will be omitted.

0058As the characteristic feature of the second embodiment, information representing whether a user may receive digital data are used in a concatenation form of AND (represented by a symbol ∩). For example, for a user u_i, the following data having a logical meaning that he/she is the user u_i, i.e., he/she is included neither in users u₁ to u_i-1 nor in users u_i+1 to u_N is embedded. <ul id="ul0015" list-style="none" compact="compact"><li>¬u₁ ∩ ¬u₂ ∩ ... ∩ ¬u_i-1 ∩ u_i ∩ ¬u_i+1 ∩ ¬u_i+2 ∩ ... ∩ ¬u_N where ¬ represents negation, and ¬u₁ is data representing negation of the user u₁.</li></ul>

0059Codes of data to be embedded are specifically assigned in correspondence with the respective items with AND (∩) in the above logical expression. <ul id="ul0016" list-style="none" compact="compact"><li>¬u_i → code_i (¬u_i)</li><li>u_i → code_i (u_i)</li></ul>

0060The ID mark to be embedded is generated by causing the codes assigned to the respective items concatenate (represented by a symbol ∥ ). The order of concatenation is not associated with the nature of this embodiment. For the descriptive convenience, the order of suffixes corresponding to users is set. <ul id="ul0017" list-style="none" compact="compact"><li>An ID mark to be embedded for the user u₁: code₁(u₁) ∥ code₁(¬u₂) ∥ code₁(¬u₃) ∥ ... ∥ code₁(¬u_N)</li><li>An ID mark to be embedded for the user u₂: code₂(¬u₁) ∥ code₂(u₂) ∥ code₂(¬u₃) ∥ ... ∥ code₂(¬u_N)</li><li>An ID mark to be embedded for the user u₃: code₃(¬u₁) ∥ code₃(¬u₂) ∥ code₃(u₃) ∥ ... ∥ code₃(¬u_N) ...</li><li>An ID mark to be embedded for the user u_i: code_i(¬u₁) ∥ code_i(¬u₂) ∥ code_i(¬u₃) ∥ ... ∥ code_i(¬u_i-1) ∥ code_i(u_i) ∥ code_i(¬u_i+1) ∥ ... ∥ code_i(¬u_N) ...</li><li>An ID mark to be embedded for the user u_N: code_N(¬u₁) ∥ code_N(¬u₂) ∥ code_N(¬u₃) ∥ ... ∥ code_N(¬u_N-1) ∥ code_N(u_N)</li><li>Assume that code_i(u_j) is "1", and code_i(¬u_j) is "0".</li></ul>

0061FIG. 9 is a flow chart showing an ID mark generation algorithm in the second embodiment. This algorithm can also be applied to a general ID mark other than the user name ID mark. In step S22, an order is set for all identification objects (all users who may receive digital data) u₁, u₂, ..., u_max for convenience (u₁ &lt; u₂ &lt; ... &lt; u_max). In step S24, 1 is set at a variable <u>j</u>, and the initial value (bit length: 0) is set as "code". In step S28, it is determined whether the variable <u>j</u> equals a parameter <u>i</u> representing the user u_i. If YES in step S28, one bit code_i(u_j) (= "1") of the ID mark is generated to concatenate to the preceding ID mark in step S30. If NO in step S28, one bit code_i(¬u_j) of the ID mark is generated to concatenate the preceding ID mark in step S32. In step S34, it is determined whether the variable <u>j</u> is larger than max (the total number of users). If NO in step S34, the variable <u>j</u> is incremented by one (+1) in step S36, and the flow returns to step S28 to determine whether the variable <u>j</u> equals <u>i</u>. If YES in step S34, determination whether the user u_i equals each of all the users is complete. It is determined that each bit of the ID mark is completely generated to concatenate to the preceding ID mark, and the operation is ended.

0062A case wherein the user illicitly copies such marked contents without permission of the copyright owner and sells it will be described next. Assume that the users u_i and u_j collude. In this case, code_i(u_i) and code_i(¬u_j) in the data for the user u_i are different from code_j(¬u_i) and code_j(¬u_j) in the data for the user u_j. A rewrite of these codes will be considered.

0063More specifically, code_i(u_i) and code_i(¬u_j) are rewritten to code_i', and code_j(¬u_i) and code_j(u_j) are rewritten to code_j'. Rewrite forms are as follows. <ul id="ul0018" list-style="none" compact="compact"><li>(a) code_i' = code_i(u_i), code_j' = code_i(¬u_j) This is the same as the ID mark embedded for the user u_i. </li><li>(b) code_i' = code_j(¬u_i), code_j' = code_j(u_j) This is the same as the ID mark embedded for the user u_j. </li><li>(c) code_i' = code_i(u_i), code_j' = code_j(u_j) This means that the colluders are the users u_i and u_j. </li><li>(d) code_i' = code_j(¬u_i), code_j' = code_i(¬u_j) In this case, the colluders cannot be specified. </li><li>(e) code_i' ≠ code_i(u_i) ≠ code_j(¬u_i), code_j' = This means that the user u_i is one of the colluders. </li><li>(f) code_i' = ****, code_j' ≠ code_j(u_j) ≠ code_i(¬u_j) This means that the user u_j is one of the colluders. </li></ul>

0064Due to the same reasoning as in the prior art, the users u_i and u_j determine that the marks need be rewritten to data other than (a) and (b) because the pieces of identification information (a) and (b) represent the users u_i and u_j themselves, respectively. The users u_i and u_j rewrite the marks to (c), (d), (e), or (f) and redistribute the illicit copy. However, unlike the prior art, in (c), it is obvious that the colluders are the users u_i and u_j. In (e) or (f) as well, it is obvious that the user u_i or u_j is one of the colluders. In (d), the colluders cannot be specified. However, when the ID mark is embedded L times, as in the first embodiment, all of the L ID marks have the data (d) at a probability of only (1/4)^L by chance. This is sufficiently effective in practice.

0065FIG. 10 shows the algorithm of the ID mark decoder 48 of the second embodiment. In step S222, the same order as that in embedding is set for the identification objects (users) u₁, u₂, ..., u_max (u₁ &lt; u₂ &lt; ... &lt; u_max). In step S224, the input extracted mark is set as the initial value of "code". In step S226, 1 is set as the variable <u>i</u>, and an empty set { } is set for a set "candidates" as a set of candidates of colluding users.

0066In step S228, it is determined whether the first bit of "code" is code_j(¬u_i) for <u>j</u>. If YES in step S228, the flow immediately advances to step S232. If NO in step S228, the user u_i is added to the set "candidates" in step S230, and then, the flow advances to step S232. In step S232, it is determined whether the variable <u>i</u> is larger than max (the total number of users). If NO in step S232, the variable <u>i</u> is incremented by one (+1) in step S234. In step S236, "code" is shifted to the MSB by the length (the number of bits) of code_j(¬u_i), and the flow returns to step S228 to determine the first bit of "code". If YES in step S232, the operation is ended. After this, the user included in the set "candidates" is estimated to be one of colluders.

0067The algorithm shown in FIG. 10 will be summarized. 1) A portion corresponding to each identification object u_i is read from the ID mark extracted from digital data, 2) it is determined whether the portion is the mark code_i(u_j) embedded on the basis of the algorithm shown in FIG. 9 or other code, and 3) the user for which it has been determined in 2) that the portion corresponds to code_i(u_j) can be estimated as one of colluding users.

0068When the ID mark is embedded L times, the above algorithm is executed L times. The user included in "candidates" in every execution of the algorithm is estimated as one of colluders.

0069As described above, according to the second embodiment, the ID mark to which information representing whether the user is one who may receive the digital data concatenation in a form of AND is embedded. With this arrangement, even when a plurality of users collude to alter the difference data and rewrite the data of themselves to other data, collusion fails because data representing that they are in collusion remains in the altered data.

0070In the second embodiment, the code amount of the ID mark is represented on the order of N and can be much smaller than that in the first embodiment.

Third Embodiment

0071The second embodiment is not resistant to collusion of three or more users.

0072Assume that users u_i, u_j, and u_k collude. <ul id="ul0019" list-style="none" compact="compact"><li>The ID mark embedded for the user u_i: ... ∥ code_i(u_i) ∥ ... ∥ code_i(¬u_j) ∥ ... ∥ code_i(¬u_k) ∥ ...</li><li>The ID mark embedded for the user u_j: ... ∥ code_j(¬u_i) ∥ ... ∥ code_j(u_j) ∥ ... ∥ code_j(¬u_k) ∥ ...</li><li>The ID mark embedded for the user u_k: ... ∥ code_k(¬u_i) ∥ ... ∥ code_k(¬u_j) ∥ ... ∥ code_k(u_k) ∥ ...</li></ul>

0073A portion P_ij of code_i(u_i or ¬u_i) and code_j(u_j or ¬u_j) can be specified from the difference data of the data of the users u_i and u_j. However, the data to which each point belongs cannot be known. Similarly, a portion P_jk of code_j(u_j or ¬u_j) and code_k(u_k or ¬u_k) can be specified from the difference data of the data of the users u_j and u_k. However, the data to which each portion belongs cannot be known.

0074Portions P_i, P_j, and P_k of the users u_i, u_j, and u_k can be specified from these subsets in the following manner. <ul id="ul0020" list-style="none" compact="compact"><li>P_ij ∩ /P_jk → {portion of code_i(u_i or ¬u_i)} ≡ P_i = P_ij - P_jk</li></ul>

0075The symbol "/" represents a complement. When P is a portion in the data, /P is a portion other than P in the data. <ul id="ul0021" list-style="none" compact="compact"><li>P_jk ∩ /P_ij → {portion of code_k(u_k or ¬u_k)} ≡ P_k = P_ij - P_ij</li><li>P_ij ∩ /P_i → {portion of code_j(u_j or ¬u_j)} ≡ P_j = P_ij - P_j</li></ul>

0076The following facts can be known.

0077The portion Pi of the embedded data of the user u_i represents code_i(u_i). The portion P_i of the embedded data of the user u_i represents code_i(¬u_i). Therefore, code_i(u_i) and code_i(¬u_i) are known.

0078In a similar manner, code_j(u_j), code_j(¬u_j), code_k(u_k), and code_k(¬u_k) are known.

0079When the colluders write code_i(¬u_i), code_j(¬u_j), and code_k(¬u_k) in P_i, P_j, and P_k, respectively, data corresponding to nobody can be generated.

0080To increase the resistance to such collusion of three or more users, the following well-order is set for the set of users. This order is determined by the contents provider. <ul id="ul0022" list-style="none" compact="compact"><li>u₁ &lt; u₂ &lt; ... &lt; u_i-1 &lt; u_i &lt; u_i+1 &lt; ... &lt; u_j-1 &lt; u_j &lt; u_j+1 &lt; ... &lt; u_N</li></ul>

0081The order is set to specify a subset having users in collusion as the minimum and maximum values. For example, when the subset u_i &lt; u_i+1 &lt; ... &lt; u_j-1 &lt; u_j is specified, the user u_i, u_j, and the like are estimated as users in collusion. <ul id="ul0023" list-style="none" compact="compact"><li>An ID mark to be embedded for the user u₁: code₁(u₁) ∥ code₁(¬u₂) ∥ code₁(¬u₃) ∥ ... ∥ code₁(¬u_N)</li><li>An ID mark to be embedded for the user u₂: code₂(¬u₁) ∥ code₂(u₂) ∥ code₂(¬u₃) ∥ ... ∥ code₂(¬u_N)</li><li>An ID mark to be embedded for the user u₃: code₃(¬u₁) ∥ code₃(¬u₂) ∥ code₃(u₃) ∥ ... ∥ code₃(¬u_N) ...</li><li>An ID mark to be embedded for the user u_i: code_i(¬u₁) ∥ code_i(¬u₂) ∥ code_i(¬u3) ∥ ... ∥ code_i(¬u_i-1) ∥ code_i(u_i) ∥ code_i(¬u_i+1) ∥ ... ∥ code_i(¬u_N) ...</li><li>An ID mark to be embedded for the user u_N: code_N(¬u₁) ∥ code_N(¬u₂) ∥ code_N(¬u₃) ∥ ... ∥ code_N(¬u_N-1) ∥ code_N(u_N)</li></ul>

0082Generally, in the ID mark embedded for the user u_i, code_i(¬u₁) ∥ code_i(¬u₂) ∥ ... ∥ code_i(¬u_i-1) ∥ before code_i(u_i) represents the absence of collinders (users below the i-th user in order are not in collusion). Similarly, code_i(¬u_i+1) ∥ ... ∥ code_i(¬u_N) after code_i(u_i) also means the absence of colluders (users above the i-th user in order are not in collusion). In the third embodiment, an order is set for all the identification objects, and information representing whether an object to be identified is below, equal, or above each of the remaining identification objects in order is used as information for identifying the object.

0083As the ID marks embedded for the users u_i and u_j, different marks are assigned when the marks have different meanings depending on their positions. For example, in the ID mark embedded for the user u_i, the i-th data means that this data corresponds to the user u_i. In the ID mark embedded for the user u_j, the i-th data means that users preceding the user u_j are not in collusion. In addition, in the ID mark embedded for the user u_i, the k-th (i &lt; k &lt; j) data means that the users succeeding the user u_k are not in collusion. In the ID mark embedded for the user u_j, the k-th data means the users preceding the user u_k are not in collusion.

0084In consideration of this, the following marks can be assigned. <ul id="ul0024" list-style="none" compact="compact"><li>code₁(u₁) ≠ code₂(¬u₁) = code₃(¬u₁) = ... = code_N(¬u₁)</li><li>code₁(¬u₂) ≠ code₂(u₂) ≠ code₃(¬u₂) = ... = code_N(¬u₂)</li><li>code₁(¬u₃) = code₂(¬u₃) ≠ code₃(u₃) ≠ code₄(¬u₃) = ... = code_N(¬u₃) ...</li></ul>

0085When the same variable is used as the same codes, a total of three variables "a", "b", and "c" can be used to represent the ID marks as follows. <ul id="ul0025" list-style="none" compact="compact"><li>The ID mark embedded for the user u₁: a⁽¹⁾b⁽²⁾b⁽³⁾................b(N)</li><li>The ID mark embedded for the user u₂: c⁽¹⁾a⁽²⁾b⁽³⁾...a⁽ⁱ⁾.........b^(N)</li><li>The ID mark embedded for the user u_i: c⁽¹⁾c⁽²⁾c⁽³⁾...........c^(N-1)a^(N)</li><li>The ID mark embedded for the user u_N: a⁽¹⁾b⁽²⁾b⁽³⁾.............b^(N)</li></ul>

0086FIG. 11 is a flow chart showing an ID mark generation algorithm in the third embodiment. This algorithm can also be applied to a general ID mark other than the user name ID mark. In step S42, an order is set for all identification objects (all users who may receive digital data) u₁, u₂, ..., u_N (u₁ &lt; u₂ &lt; ... &lt; u_N). In step S44, the user u_i as the identification target is specified. In step S46, 1 is set at a variable j, and the initial value (bit length: 0) is set as "code".

0087In step S48, it is determined whether the variable <u>j</u> equals a parameter <u>i</u> representing the user u_i. If YES in step S48, one bit a⁽¹⁾ of the ID mark is generated to concatenate to the preceding ID mark in step S50. If NO in step S48, it is determined in step S52 whether the variable <u>j</u> is smaller than the parameter <u>i</u> representing the user u_i. If YES in step S52, one bit c^(j) of the ID mark is generated to concatenate to the preceding ID mark in Step S54. If NO in step S52, one bit b^(j) of the ID mark is generated to concatenate to the preceding ID mark in step S56.

0088In step S58, it is determined whether the variable <u>j</u> is smaller than N (the total number of users). If NO in step S58, the variable <u>j</u> is incremented by one (+1) in step S60, and the flow returns to step S48 to determine whether the variable <u>j</u> equals the parameter <u>i</u>. If YES in step S58, determination whether the user u_i equals each of the remaining users is complete. It is determined that each bit of the ID mark is completely generated to concatenate to the preceding ID mark, and the operation is ended.

0089The reason why three users u_i, u_j, and u_k cannot successfully collude when such ID marks are embedded will be described next. <ul id="ul0026" list-style="none" compact="compact"><li>The ID mark embedded for the user u_i: c⁽¹⁾...c^(i-1)a⁽ⁱ⁾b⁽ⁱ⁺¹⁾....................b^(N)</li><li>The ID mark embedded for the user u_j: c⁽¹⁾..........c^(j-1)a^(j)b^(j+1).............b(N)</li><li>The ID mark embedded for the user u_k: c⁽¹⁾.................c^(k-1)a^(k)b^(k+1)......b^(N)</li></ul>

0090For the success of collusion of the three users, the following ID mark must be obtained. <ul id="ul0027" list-style="none" compact="compact"><li>c⁽¹⁾...c^(i-1)*⁽ⁱ⁾*⁽ⁱ⁺¹⁾...*^(k-1)*^(k)b^(k+1)...b^(N)</li></ul>

0091The subset *⁽ⁱ⁾*⁽ⁱ⁺¹⁾...*^(k-1)*^(k) specifies the colluder. Therefore, when the minimum value *⁽ⁱ⁾ is a⁽ⁱ⁾, it can be known that the user u_i is in collusion. To prevent this, *⁽ⁱ⁾ = c⁽ⁱ⁾ must be set to let it be supposed that the user u_i is not in collusion. When *⁽ⁱ⁾ = b⁽ⁱ⁾, or *⁽ⁱ⁾ is set at another code, this means that the user u_i is in collusion. If the portion P_i of the ID mark of the user u_i can be specified, *⁽ⁱ⁾ = c⁽ⁱ⁾ can be easily set from the data of the user u_k. However, it is the whole P_i ∪ ... ∪ P_j-1 (≡ P_ij -P_jk) that can be specified, and the portion P_i cannot be specified.

0092Simultaneously, when the maximum value *^(k) is a^(k), it can be known that the user u_k is in collusion. To prevent this, *^(k) = b^(k) must be set to let it be supposed that the user u_k is not in collusion. When *^(k) = c^(k), or *^(k) is set at another code, this means that the user u_k is in collusion. If the portion P_k of the ID mark of the user u_k can be specified, *^(k) = b^(k) can be easily set from the data of the user u_i. However, it is the whole P_j+1 ∪ ... ∪ P_k (≡ P_jk -P_ij) that can be specified, and the portion P_k cannot be specified.

0093Setting *⁽ⁱ⁾ = c⁽ⁱ⁾ and _*^(k) = b^(k) by a random operation depends on chance. Letting p⁽ⁱ⁾ and p^(k) be the probabilities for setting of these codes, the probability of success of collusion is given by p⁽ⁱ⁾ × p^(k). Generally, p⁽ⁱ⁾ ≦ 1/2 and p^(k) ≦ 1/2. Especially, when the code length of c⁽ⁱ⁾ or b^(k) is long to some extent, p⁽ⁱ⁾ and p^(k) are sufficiently smaller than 1. Therefore, the probability of success of collusion is low. As in the above embodiments, when identification information is embedded L times, this probability can be further lowered to (p⁽ⁱ⁾ × p^(k))^L.

0094FIG. 12 shows the algorithm of an ID mark decoder 48 of the third embodiment. In step S242, the same order as in embedding is set for the identification objects (users) u₁, u₂, ..., u_N (u₁ &lt; u₂ &lt; ... &lt; u_N). In step S244, 1 is set as the variable <u>i</u>, the input extracted mark is set as the initial value of "code", 1 is set for "candidate 1" as the first colluder candidate, and 1 is set for "candidate 2" as the second colluder candidate. In step S246, it is determined whether the first bit of "code" is c⁽ⁱ⁾. If YES in step S246, the variable <u>i</u> is incremented by one (+1) in step S248, and "candidate 1" as the first colluder candidate and "candidate 2" as the second colluder candidate are incremented by one (+1) in step S250. In step S252, "code" is shifted to the MSB by the length of c⁽ⁱ⁾, and the flow returns to step S246 to determine the first bit of "code". The length of c⁽ⁱ⁾ is represented by |c⁽ⁱ⁾|, and assume that |a⁽ⁱ⁾| = |b⁽ⁱ⁾| = |c⁽ⁱ⁾|. If NO in step S246, the variable <u>i</u> is incremented by one (+1), and "code" is shifted to the MSB by the length of c⁽ⁱ⁾ in step S254. In step S256, it is determined whether the first bit of "code" is b⁽ⁱ⁾. If NO in step S256, the variable <u>i</u> is substituted into "candidate 2" as the second colluder candidate in step S258, and the flow returns to step S254. If YES in step S260, the operation is ended. After this, "candidate 1" and "candidate 2" are estimated to be two of the colluders.

0095The characteristic features of the algorithm shown in FIG. 12 will be summarized. 1) A portion corresponding to each identification object ui is sequentially read from the first bit of the ID mark extracted from digital data, 2) it is determined whether the portion is the mark c⁽ⁱ⁾ embedded on the basis of the algorithm shown in FIG. 11 or another mark, and the processes 1) and 2) are repeated until a mark other than c⁽ⁱ⁾ appears, 3) <u>i</u> obtained when the mark other than c⁽ⁱ⁾ appears for the first time in 2) is determined as one of the colluding user candidates, 4) a portion corresponding to each identification object u_i is read from a portion next to the mark other than c⁽ⁱ⁾ which has appeared for the first time in 2), 5) it is determined whether the portion is the mark b⁽ⁱ⁾ embedded on the basis of the algorithm shown in FIG. 11 or another mark, and the processes 4) and 5) are repeated until a mark other than b⁽ⁱ⁾ appears, 6) <u>i</u> obtained when the mark other than b⁽ⁱ⁾ appears in 5) is "provisionally" determined as the other candidate of the colluding users, 7) the processes 4), 5), and 6) are repeated until the final bit of the extracted ID mark is reached, and 8) the user who has been "provisionally" determined as the other candidate of the colluding users when the final bit of the extracted ID mark is reached is determined as the other candidate of the colluding users.

0096When the ID mark is embedded L times, the above algorithm is executed L times, and "candidate 1" and "candidate 2" in every execution of the algorithm is estimated as colluders.

0097In the third embodiment as well, the code amount of the ID mark is represented on the order of N and can be much smaller than that in the first embodiment.

0098Conventional electronic watermarking methods against collusion are described in "A Scheme of Making Collusion-Secure Watermark", Masahiro Suzuoki et al., SCIS '97 (the 1997 Symposium on Cryptography and Information Security), and "Collusion-Secure Fingerprinting for Digital Data", D. Boneh and J. Shaw, Advances in Cryptography Proceedings of CRYPTO '95, pp. 257 - 270 (1994). In the example of Susuoki et al., a = 00, b = 10, and c = 01. In the example of Boneh et al., "a", "b", and "c" are L (arbitrary positive integer) bits, and aa = b = 00...0 (all 0s), and c = 11...1 (all 1s). That is, coding of the third embodiment is more general than these methods.

Fourth Embodiment

0099An embodiment for further reducing the code amount will be described. The Chinese remainder theorem is applied to this embodiment. The Chinese remainder theorem defines that when there are relatively prime numbers p₁, p₂, ..., p_k (these integers satisfy a relationship n ≦ p1 × p1 × ... × p_k), n is uniquely obtained from n₁ = n mod p₁, n₂ = n mod P₂, ..., n_k = n mod p_k. In an application of this theorem (assume N ≦ p × q), by specifying the r-th user in 1 to p, and the s-th user in 1 to q, the n-th user in the set of all users N in the third embodiment can be specified. The ID mark for specifying the r-th (= n mod p) user and the s-th (= n mod q) user in the two sets of <u>p</u> users and <u>q</u> users has a code amount smaller than that for specifying the nth user in the set of all users with the number N of users.

0100In the fourth embodiment, the relatively prime numbers <u>p</u> and <u>q</u> for satisfying N ≦ p × q are defined. Instead of the parameter <u>i</u> (i = 1 to N) for specifying the user, the parameter <u>r</u> (1 to p) and <u>s</u> (1 to q) are used to specify each user. For the descriptive convenience, assume that p = 7, and q = 5. <ul id="ul0028" list-style="none" compact="compact"><li>The ID mark embedded for a user u₁: a^{(<sup2>1</sup2>)}b^{(<sup2>2</sup2>)}b^{(<sup2>3</sup2>)}b⁽⁴⁾b⁽⁵⁾b⁽⁶⁾b⁽⁷⁾ a⁽¹⁾b⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾</li><li>The ID mark embedded for a user u₂: c⁽¹⁾a⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾b⁽⁶⁾b⁽⁷⁾ c⁽¹⁾a⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾ ...</li><li>The ID mark embedded for a user u₆: c⁽¹⁾c⁽²⁾c⁽³⁾c⁽⁴⁾c⁽⁵⁾a⁽⁶⁾b⁽⁷⁾ a⁽¹⁾b⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾</li><li>The ID mark embedded for a user u₇: c⁽¹⁾c⁽²⁾c⁽³⁾c⁽⁴⁾c⁽⁵⁾c⁽⁶⁾a⁽⁷⁾ c⁽¹⁾a⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾</li><li>The ID mark embedded for a user u₈: a⁽¹⁾b⁽²⁾b⁽³⁾b⁽⁴⁾b⁽⁵⁾b⁽⁶⁾b⁽⁷⁾ c⁽¹⁾c⁽²⁾a⁽³⁾b⁽⁴⁾b⁽⁵⁾</li><li>The first half portion of the above mark, *(1)*(2)*(3)*(4)*(5)*(6)*(7) is a mark portion code_r associated with <u>r</u>, and the second half portion *(1)*(2)*(3)*(4)*(5) is a mark portion code_s associated with <u>s</u>. The position of the mark "a" represents the value of <u>r</u> or <u>s</u>. The marks "a", "b", and "c" included in the mark portion associated with <u>r</u> need not be the same as those included in the second half portion, and the marks included in the second half portion may be <u>d</u>, <u>e</u>, and <u>f</u>.</li></ul>

0101FIGS. 13 and 14 are flow charts showing an ID mark generation algorithm in the fourth embodiment. This algorithm can also be applied to a general ID mark other than the user name ID mark. In step S64, an order is set for all identification objects (all users who may receive digital data) u₁, u₂, ..., u_N (u₁, u₂, ..., u_N). In step S66, a user u_i as an identification object is specified. In step S68, the relative prime numbers <u>p</u> and <u>q</u> for satisfying N ≦ p × q are obtained. In step S70, 1 is set as a variable <u>j</u>, and the initial value (bit length: 0) is set as code_r. In step S72, it is determined whether the variable <u>j</u> equals i mod p. If YES in step S72, one bit a^(J) of the ID mark code_r is generated to concatenate to the preceding ID mark code_r in step S74. If NO in step S72, it is determined in step S76 whether the variable <u>j</u> is smaller than i mod p. If YES in step S76, one bit c^(j) of the ID mark coder is generated to concatenate to the preceding ID mark code_r in step S78. If NO in step S76, one bit b^(j) of the ID mark code_r is generated to concatenate to the preceding ID mark in step S80.

0102In step S82, it is determined whether the variable <u>j</u> is larger than <u>p</u>. If NO in step S82, the variable <u>j</u> is incremented by one (+1) in step S84, and the flow returns to step S72 to determine whether the variable <u>j</u> equals i mod p. If YES in step S82, it is determined that all bits (<u>p</u> bits) of the ID mark code_r is completely generated to concatenate to the preceding ID mark, and the operation shifts to generation of code_s.

0103In step S86, 1 is set as the variable <u>j</u>, and the initial value (bit length: 0) is set as code_s. In step S88, it is determined whether the variable <u>j</u> equals i mod q. If YES in step S88, one bit a(j) of the ID mark code_s is generated to concatenate to the preceding ID mark code_s in step S90. If NO in step S88, it is determined in step S92 whether the variable <u>j</u> is smaller than i mod q. If YES in step S92, one bit c^(j) of the ID mark code_s is generated to concatenate to the preceding ID mark code_s in step S94. If NO in step S92, one bit b^(j) of the ID mark code_s is generated to concatenate to the preceding ID mark in step S96.

0104In step S98, it is determined whether the variable <u>j</u> is larger than <u>q</u>. If NO in step S98, the variable <u>j</u> is incremented by one (+1) in step S100, and the flow returns to step S88 to determine whether the variable <u>j</u> equals i mod q. If YES in step S98, it is determined that all bits (<u>q</u> bits) of the ID mark code_s is completely generated to concatenate to the preceding ID mark. In step S102, the ID marks code_r is made to concatenate to the ID mark code_s, and generation of ID marks is ended.

0105When the ID mark is divided into two parts, the code amount is represented not on the order of N but on the (order of <u>p</u>) and (order of <u>q</u>). If p ≒ q, then p2 ≒ q2 ≒ N so the length of the ID mark is on the order of N^1/2.

0106In the fourth embodiment, r1 and r2 are obtained as <u>r</u>, and s1 and s2 are obtained as <u>s</u>. For this reason, it cannot be specified whether the colluders are one user defined by r1 and s1 and the other user defined by r2 and s2, or one user defined by r1 and s2 and the other user defined by r₂ and s₁. To specify one of the combinations, the following third number <u>t</u> must be introduced. Assume that n mod t = u. <ul id="ul0029" list-style="none" compact="compact"><li>N = p × q</li><li>N ≦ p × t</li><li>N ≦ q × t</li></ul>

0107In this case, r1 and r2 are obtained as <u>r</u>, s1 and s2 are obtained as <u>s</u>, and t1 and t2 are obtained as <u>t</u>. As is apparent from <u>r</u> and <u>s</u>, the colluder pair includes one user defined by r1 and s1 and the other user defined by r2 and s2 (these candidates will be referred to as n1 and n2), or one user defined by r1 and s2 and the other user defined by r2 and s1 (these candidates will be referred to as n1' and n2'). As is apparent from <u>s</u> and <u>t</u>, the colluder pair includes one user defined by s1 and t1 and the other user defined by s2 and t2 (these candidates will be referred to as m1 and m2), or one user defined by s1 and t2 and the other user defined by s2 and t1 (these candidates will be referred to as m1' and m2'). The colluders are determined as those matching in these four combinations of candidates: (n1, n2), (n1', n2'), (m1, m2), and (m1', m2').

0108As the algorithm of the ID mark decoder 48 of the fourth embodiment, the algorithm of the third embodiment shown in FIG. 12 is executed for each of the numbers <u>p</u> and <u>q</u>. This algorithm is shown in FIGS. 15 and 16. In step S272, the same order as in embedding is set for the identification objects (users) u₁, u₂, ..., u_N (u₁, u₂, ..., u_N), and simultaneously, the same numbers <u>p</u> and <u>q</u> as in embedding are given. In step S274, 1 is set as a variable <u>i</u>, the input extracted mark is set as the initial value of "code", 1 is set for "candidate-p1" as the first colluder candidate, and 1 is set for "candidate-p2" as the second colluder candidate. In step S276, it is determined whether the first bit of "code" is c⁽ⁱ⁾. If YES in step S276, the variable <u>i</u> is incremented by one (+1) in step S278, and in step S280, "candidate-p1" as the first colluder candidate and "candidate-p2" as the second colluder candidate are incremented by one (+1). In step S282, "code" is shifted to the MSB by the length of c⁽ⁱ⁾, and the flow returns to step S276 to determine the first bit of "code". If NO in step S276, the variable <u>i</u> is incremented by one (+1), and "code" is shifted to the MSB by the length of c(i), and in step S286, it is determined whether the first bit of "code" is b⁽ⁱ⁾. If NO in step S286, <u>i</u> is set for "candidate-p2" as the second colluder candidate in step S288, and the flow returns to step S284. If YES in step S286, it is determined in step S290 whether the variable <u>i</u> is larger than <u>p</u>.

0109If NO in step S290, the flow returns to step S284. If YES in step S290, 1 is set for "candidate-q1" as the first colluder candidate, and 1 is set for "candidate-q2" as the second colluder candidate in step S292. in step S294, the variable <u>i</u> is incremented by one (+1). In step S296, it is determined whether the first bit of "code" is c(i). If YES in step S296, the variable <u>i</u> is incremented by one in step S298. In step S300, "candidate-q1" as the first colluder candidate and "candidate-q2" as the second colluder candidate are incremented by one (+1). In step S302, "code" is shifted to the MSB by the length of c(i), and the flow returns to step S296 to determine the first bit of "code". If NO in step S296, the variable <u>i</u> is incremented by one (+1), and "code" is shifted to the MSB by the length of c⁽ⁱ⁾ in step S304. In step S306, it is determined whether the first bit of "code" is b⁽ⁱ⁾. If NO in step S306, <u>i</u> is set for "candidate-q2" as the second colluder candidate in step S308, and the flow returns to step S304. If YES in step S306, it is determined in step S310 whether the variable <u>i</u> is larger than p + q. If NO in step S310, the flow returns to step S304. If YES in step S310, in step S312, the Chinese remainder theorem is applied to (candidate-p1, candidate-q1), (candidate-p2, candidate-q2), (candidate-p1, candidate-q2), and (candidate-p2, candidate-q1) to calculate and determine the order <u>n</u> of the candidates of colluding users.

0110In the above-described fourth embodiment, the combination of two numbers <u>p</u> and <u>q</u> is used. However, according to the Chinese remainder theorem, <u>k</u> numbers p₁, p₂, ..., p_k may be used. FIG. 17 shows an algorithm for obtaining <u>n</u> from v_i assuming that v_i = N mod p_i.

0111In step S210, 1 is set as the variable <u>i</u>. In step S122, y_i = inv ((N/p_i) mod P_i, P_i) is obtained. In step S124, it is determined whether the variable <u>i</u> is larger than <u>k</u>. If NO in step S124, the variable <u>i</u> is incremented by one in step S126, and step S122 is executed again. If YES in step S124, the initial value of 0 is set for <u>x</u>. In step S130, 0 is set as the variable <u>i</u> again. In step S132, x = x (x + (N/p_i)· y_i · v_i) mod N is calculated. In step S134, it is determined whether the variable <u>i</u> is larger than <u>k</u>. If NO in step S134, the variable <u>i</u> is incremented by one in step S136, and step S132 is executed again. If YES in step S134, <u>x</u> is output as information for specifying a user.

0112The present invention is not limited to the above-described embodiments, and various changes and modifications can be made. For example, in the above embodiments, the ID mark is generated and embedded into digital data on the side of the provider who distributes the digital data. However, generation and embedding of the ID mark may be separated. More specifically, the ID mark may be generated by a reliable third party and distributed to the digital data provider as a client. The provider directly embeds the distributed ID mark.

0113In this case, the ID mark can be used for a purpose other than an electronic watermark. For example, the ID mark can be transmitted/received as part of a message such that the user can perceive the presence of the ID mark but does not know the meaning of the mark. The ID mark can also be used for a purpose other than user name identification. The ID mark can also be used to identify the date and time of use, the user terminal, the digital data, or the digital data transfer path, or describe a use condition.

0114As has been described above, according to the present invention, in the electronic watermark processing apparatus for embedding and hiding watermark associated with a user of digital data in the data, even when a plurality of users collude to compare their data, the watermark can hardly be altered to watermark associated with another user.