Identification information embedding apparatus and identification information analysis apparatus

Abstract

An identification information apparatus detects first and second boundary position information representing boundary positions on a high-order bit side and a low-order bit side of codes formed of components, extracts a colluder group matching with a set of the first and second boundary position information among colluder groups including combinations of an arbitrary number of identification information which is not more than a predetermined maximum number, and detects identification information which is common to a plurality of the colluder groups.

1 . A method for analyzing items of identification information of an object based on a code extracted from the object, the method comprising: 
 detecting a first boundary position information representing a boundary position on a high-order bit side and second boundary position information representing a boundary position on a low-order bit side in a changed part relative to a pattern of a bit string of each of a plurality of components forming the code extracted from the object;    extracting, from colluder groups formed of combinations of a predetermined number of items of the identification information, a single colluder group or colluder groups matching with a set of the detected first and second boundary position information;    extracting, if the single colluder group is extracted, items of the identification information included in the single colluder group;    extracting, if the colluder groups are extracted, items of the identification information included in all of the extracted colluder groups; and    extracting a colluder group or colluder groups matching with a set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between a set of the first and second boundary position information and one or a plurality of colluder groups matching with the set of the first and second boundary position information.    
   
   
       2 . The method according to  claim 1 , further comprising: 
 outputting information indicative of no item of the identification information when there is no item of the identification information included in all of the extracted colluder groups.    
   
   
       3 . The method according to  claim 1 , wherein the items of identification information extracting comprises at least one of: 
 detecting all of the items of the identification information forming the colluder group matching with the set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between the set of the first and second boundary position information and all of the items of the identification information forming the colluder group matching with the set of the first and second boundary position information;    detecting items of the identification information included in all of the extracted colluder groups matching with the set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between the set of the first and second boundary position information and items of the identification information included in all of the extracted colluder groups matching with the set of the first and second boundary position information; and    detecting that there is no colluder group matching with the set of the first and second boundary position information detected by the detector, based on predetermined information indicative of a relationship between the set of the first and second boundary position information and information indicating that there is no colluder group matching with the set of the first and second boundary position information.    
   
   
       4 . The method according to  claim 1 , further comprising: 
 detecting a colluder group or colluder groups matching with the set of the first and second boundary position information detected, based on the set of the first and second boundary position information detected and a set of third boundary position information representing a boundary position where a pattern of a bit string in each of a plurality of components forming a collusion-secure code corresponding to the identification information varies.    
   
   
       5 . The method according to  claim 1 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    detecting colluder groups including identification information included in the colluder group detected and extracting colluder groups matching with the set of the first and second boundary position information detected among the colluder groups including the identification information; and    detecting identification information common to the colluder groups extracted, and outputting the obtained identification information as information indicative of a colluder attacker relative to the object.    
   
   
       6 . The method according to  claim 1 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    determining whether there is a colluder group which does not include items of the identification information contained in the colluder group detected;    matching with the set of the first and second boundary position information detected; and    outputting the specific identification information as information indicative of a collusion attacker relative to the object when it is determined that there is no colluder group.    
   
   
       7 . A method for analyzing items of identification information of an object based on a code extracted from the object, the method comprising: 
 detecting a first boundary position information representing a boundary position on a high-order bit side and second boundary position information representing a boundary position on a low-order bit side in a changed part relative to a pattern of a bit string of each of a plurality of components forming the code extracted from the object;    extracting, from colluder groups formed of combinations of a predetermined number of items of the identification information, a single colluder group or colluder groups matching with a set of the detected first and second boundary position information;    extracting, if the single colluder group is extracted, items of the identification information included in the single colluder group; and    extracting, if the colluder groups are extracted, items of the identification information included in all of the extracted colluder groups,    wherein the extracting items of identification information comprises at least one of:    detecting all of the items of the identification information forming the colluder group matching with the set of first and second boundary position information based on predetermined information indicative of a relationship between the set of first and second boundary position information and all of the items of the identification information forming the colluder group matching with the set of first and second boundary position information,    detecting items of the identification information included in all of the extracted colluder groups matching with the set of first and second boundary position information based on predetermined information indicative of a relationship between the set of first and second boundary position information and items of the identification information included in all of the extracted colluder groups matching with the set of first and second boundary position information, and    detecting that there is no colluder group matching with the set of first and second boundary position information, based on predetermined information indicative of a relationship between the set of first and second boundary position information and information indicating that there is no colluder group matching with the set of first and second boundary position information.    
   
   
       8 . The method according to  claim 7 , further comprising: 
 outputting information indicative of no item of the identification information when there is no item of the identification information included in all of the extracted colluder groups.    
   
   
       9 . (canceled)  
   
   
       10 . The method according to  claim 7 , further comprising: 
 detecting a colluder group or colluder groups matching with the set of the first and second boundary position information detected, based on the set of the first and second boundary position information detected, and a set of third boundary position information representing a boundary position where a pattern of a bit string in each of a plurality of components forming a collusion-secure code corresponding to the identification information varies.    
   
   
       11 . The method according to  claim 7 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    detecting colluder groups including identification information included in the colluder group detected, and extracting colluder groups matching with the set of the first and second boundary position information detected among the colluder groups including the identification information;    detecting identification information common to the colluder groups extracted; and    outputting the obtained identification information as information indicative of a colluder attacker relative to the object.    
   
   
       12 . The method according to  claim 7 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    determining whether there is a colluder group which does not include items of the identification information contained in the colluder group detected;    matching with the set of the first and second boundary position information detected; and    outputting the specific identification information as information indicative of a collusion attacker relative to the object when it is determined that there is no colluder group.    
   
   
       13 . A method for analyzing items of identification information of an object based on a code extracted from the object, the method comprising: 
 detecting a first boundary position information representing a boundary position on a high-order bit side and second boundary position information representing a boundary position on a low-order bit side in a changed part relative to a pattern of a bit string of each of a plurality of components forming the code extracted from the object;    extracting, from colluder groups formed of combinations of a predetermined number of items of the identification information, a single colluder group or colluder groups matching with a set of first and second boundary position information;    extracting, if the single colluder group is extracted, items of the identification information included in the single colluder group; and    extracting, if the colluder groups are extracted, items of the identification information included in all of the extracted colluder groups,    wherein the detecting comprises detecting the first boundary position information based on a change in pattern of the bit string when seen from a high-order bit side of the components, and detecting the second boundary position information based on a change in pattern of the bit string when seen from a low-order bit side of the components.    
   
   
       14 . The method according to  claim 13 , further comprising: 
 outputting information indicative of no item of the identification information, when there is no item of the identification information included in all of the extracted colluder groups.    
   
   
       15 . The method according to  claim 13 , further comprising: 
 extracting a colluder group or colluder groups matching with a set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between a set of the first and second boundary position information and one or a plurality of colluder groups matching with the set of the first and second boundary position information.    
   
   
       16 . The method according to  claim 13 , comprising at least one of the following steps: 
 a first step of detecting all of the items of the identification information forming the colluder group matching with the set of the first and second boundary position information detected based on predetermined information indicative of a relationship between the set of the first and second boundary position information and all of the items of the identification information forming the colluder group matching with the set of the first and second boundary position information;    a second step of detecting items of the identification information included in all of the extracted colluder groups matching with the set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between the set of the first and second boundary position information and items of the identification information included in all of the extracted colluder groups matching with the set of the first and second boundary position information; and    a third step of detecting that there is no colluder group matching with the set of the first and second boundary position information detected, based on predetermined information indicative of a relationship between the set of the first and second boundary position information and information indicating that there is no colluder group matching with the set of the first and second boundary position information.    
   
   
       17 . The method according to  claim 13 , further comprising: 
 detecting a colluder group or colluder groups matching with the set of the first and second boundary position information detected, based on the set of the first and second boundary position information detected, and a set of third boundary position information representing a boundary position where a pattern of a bit string in each of a plurality of components forming a collusion-secure code corresponding to the identification information varies.    
   
   
       18 . The method according to  claim 13 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    detecting colluder groups including identification information included in the colluder group detected by the first unit and extracting colluder groups matching with the set of the first and second boundary position information detected among the colluder groups including the identification information; and    detecting identification information common to the colluder groups extracted by the second unit and outputs the obtained identification information as information indicative of a colluder attacker relative to the object.    
   
   
       19 . The method according to  claim 13 , further comprising: 
 detecting a colluder group matching with the set of the first and second boundary position information detected;    determining whether there is a colluder group which does not include item of the identification information contained in the colluder group detected;    matching with the set of the first and second boundary position information detected; and    outputting the specific identification information as information indicative of a collusion attacker relative to the object when the second unit determines that there is no colluder group.    
   
   
       20 . The method according to  claim 13 , wherein each of a plurality of the components is a bit string including only continuous 1 or 0 having a predetermined bit number, 
 the code includes a string of unit bits, and further includes a code obtained by concatenating a string of unit bits including only 1 from a high-order bit side and subsequently concatenating a string of unit bits including only 0, a code obtained by concatenating a string of unit bits including only 0, and a code obtained by concatenating a string of unit bits including only 1;    detecting, when there is a first position at which the string of unit bits including only 0 and the string of unit bits including only 1 are adjacent to each other, as the first boundary position information is an integer value indicative of the first position;    detecting, when there is a second position at which the string of unit bits including only 1 and the string of unit bits including only 0 are adjacent to each other, as the second boundary position information an integer value indicative of the second position;    detecting, when the string of unit bits at the most significant bit side comprises a string of unit bits comprising 0 and 1, as the first boundary position information is an integer 0; and    detecting, when the string of unit bits at the most significant bit side comprises a string of unit bits comprising 0 and 1, as the second boundary position information a value obtained by subtracting 1 from the number of the strings of the unit bits that the component has.    
   
   
       21 . A method for analyzing items of identification information of an object based on a code extracted from the object, the method comprising: 
 detecting a first boundary position information representing a boundary position on a high-order bit side and second boundary position information representing a boundary position on a low-order bit side in a changed part relative to a pattern of a bit string of each of a plurality of components forming the code extracted from the object;    extracting, from colluder groups formed of combinations of a predetermined number of items of the identification information, a single colluder group or colluder groups matching with a set of first and second boundary position information;    extracting, if the single colluder group is extracted, items of the identification information included in the single colluder group;    extracting, if the colluder groups are extracted, items of the identification information included in all of the extracted colluder groups;    detecting the first boundary position information based on a change in pattern of the bit string when seen from a high-order bit side of the components;    detecting the second boundary position information based on a change in pattern of the bit string when seen from a low-order bit side of the components;    generating a collusion-secure code corresponding to the identification information of the object, a restriction being provided between a maximum number of colluders defined by a tracing algorithm, number of components forming the code, and a settable range of the identification information; and    embedding the generated code in the object,    wherein c is the maximum number, d is the number of components forming the code, p 0 , p 1 , . . . p d−1  are relatively prime integers (where 0<p 0 <p 1 < . . . <p d−1 ), V mod p i−i  is an integer value which determines a boundary position at which a pattern of a bit string in an i-th component relative to identification information V varies, and a range of the identification information are integers which fall within a range from 0 to p 0 ×p 1 × . . . ×(p k−1 −1), the restriction between d, c and k is represented by d>(c 2 /2)×(k−1).    
   
   
       22 . The method according to  claim 21 , wherein the object comprises a chemical material product, and a component is changed to insert the code into the object.  
   
   
       23 . A method for analyzing items of identification information of an object based on a code extracted from the object, the method comprising: 
 detecting a first boundary position information representing a boundary position on a high-order bit side and second boundary position information representing a boundary position on a low-order bit side in a changed part relative to a pattern of a bit string of each of a plurality of components forming the code extracted from the object;    extracting, from colluder groups formed of combinations of a predetermined number of items of the identification information, a colluder group or colluder groups matching with a set of the first and second boundary position information detected;    extracting items of the identification information included in a single colluder group if the colluder group extraction unit extracts the single colluder group;    extracting items of the identification information included in all of the extracted colluder groups if the colluder group extraction unit extracts colluder groups;    detecting the first boundary position information based on a change in pattern of the bit string when seen from a high-order bit side of the components;    detecting the second boundary position information based on a change in pattern of the bit string when seen from a low-order bit side of the components;    generating a collusion-secure code corresponding to the identification information of the object, a restriction being provided between a maximum number of colluders defined by a tracing algorithm, number of components forming the code, and a settable range of the identification information; and    embedding the generated code in the object, wherein an i-th component of the code comprises a bit string including continuous 1 or 0 having a predetermined bit number, and    the code comprises a string of unit bits obtained by concatenating a string of unit bits including only 1 whose number is the same as the integer value V mod p i−1  from a high-order bit side and subsequently concatenating a string of unit bits including only 0 whose number is the same as a value obtained by subtracting 1 and the integer value V mod p i−1  from the integer value p i−1 .    
   
   
       24 . The method according to  claim 23 , wherein the object comprises a chemical material product, and a component is changed to insert the code into the object.