Watermarks for customer identification

A digital watermarking method, comprising the steps of:

• forming a first collection of masks;
• forming a second collection of masks, each mask in said second collection being different from said masks in said first collection;
• and
• encoding a pair of masks into a digital image to form an authorized digital image, a first mask of said pair derived from said first collection and a second mask of said pair derived from a second collection, wherein said pair of masks are used to perform a recognition among said plurality of customers that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers.

A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:

• forming a first collection of masks, said first collection including a sub-collection of a first type and a sub-collection of a second type;
• forming a second collection of masks, said second collection including a sub-collection of a first type and a sub-collection of a second type, each mask in said second collection being different from said masks in said first collection;
• assigning to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j, 1)), M(K(I,j, 2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j, 1) in each pair being derived from said first collection and the second mask M(K(I,j, 2) in each pair being derived from said second collection, the first mask and the second mask in each pair either both being of said first type or both being of said second type, wherein said pair of masks will be used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers;
• accepting a request to use one of said digital images from one of said customers;
• and
• encoding into said digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers in said assigning step which corresponds to the requested digital image.

A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:

• forming a pair of masks where each mask (M) is a two-dimensional concatenation of two smaller masks, a second one of said smaller masks (Ms′) being an inversion of a first one of said smaller masks (Ms), said first mask corresponding to a first letter of an alphabet and said second mask corresponding to a second letter of said alphabet, with said pair of masks (M) being a pair of code words written in said first and second letters;
• assigning said pair of masks (M) to a customer Ci;
• accepting a request from said customer Ci to use one of said digital images,
• encoding said pair of masks (M) into said digital image;
• obtaining a digital image suspected of being an unauthorized version of said authorized digital image;
• locating said pair of code words corresponding to said pair of masks (M) in said unauthorized digital image;
• and
• identifying the customer assigned to said pair of masks having said pair of code words as one who distributed the unauthorized version of said authorized digital image.

A watermark detection method, comprising the steps of:

• forming n collections of pairs of watermarks;
• forming a set of n pairs of watermarks W(I) for a customer, said n pairs of watermarks in said set being chosen one from each said n collections of pairs of watermarks, respectively;
• encoding a different one of said pair of watermarks from said set of pairs into a respective plurality of images;
• authorizing said customer to use said plurality of images;
• obtaining a group of images suspected of being unauthorized versions of said plurality of images;
• analyzing watermarks in a predetermined number of said unauthorized versions of said plurality of images;
• and
• identifying said group of images as being derived from said customer when, in said analyzing step, watermarks in said predetermined number of said unauthorized versions of said images are determined to belong to said customer.

A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:

• forming n collections of pairs of watermarks, where n is less than a number of customers of said vendor;
• randomly choosing pairs of watermarks from said n collections of pairs of watermarks;
• encoding said randomly chosen pairs of watermarks into respective ones of a plurality of images;
• authorizing at least two customers to use said plurality of images, at least a portion of said images used by said two customers being encoded with a common pair of watermark;
• obtaining a group of images suspected of being unauthorized versions of said plurality of images;
• analyzing said group of images to determine which images in said group have said common pair of watermarks;
• and
• identifying said two customers as ones who colluded to produce said unauthorized versions of said plurality of digital images as a result of said common pair of watermarks being found in said group of images.

A computer program product for use with a computer, comprising:

• a computer readable medium with a computer program recorded thereon, the program including:
• first code means for causing the computer to form a first collection of masks;
• second code means for causing the computer to form a second collection of masks, each mask in said second collection being different from said masks in said second collection;
• third code means for causing the computer to assign to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j, 1)), M(K(I,j, 2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j, 1) in each pair being derived from said first collection and the second mask M(K(I,j, 2) in each pair being derived from said second collection;
• and
• fourth code means for causing the computer to encode into a digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers by said third code means which corresponds to the requested digital image, wherein said pair of masks are used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers.