Multiple transform utilization and applications for secure digital watermarking

Abstract

Multiple transform utilization and applications for secure digital watermarking. In one embodiment of the present invention, digital blocks in digital information to be protected are transformed into the frequency domain using a fast Fourier transform. A plurality of frequencies and associated amplitudes are identified for each of the transformed digital blocks and a subset of the identified amplitudes is selected for each of the digital blocks using a primary mask from a key. Message information is selected from a message using a transformation table generated with a convolution mask. The chosen message information is encoded into each of the transformed digital blocks by altering the selected amplitudes based on the selected message information.

What is claimed is:  
     
         1 . A method for encoding a message into digital information, the digital information including a plurality of digital blocks, comprising the steps of: 
 transforming each of the digital blocks into the frequency domain using a fast Fourier transform;    identifying a plurality of frequencies and associated amplitudes for each of the transformed digital blocks;    selecting a subset of the identified amplitudes for each of the digital blocks using a primary mask from a key;    choosing message information from the message using a transformation table generated with a convolution mask; and    encoding the chosen message information into each of said transformed digital blocks by altering the selected amplitudes based on the chosen message information.    
     
     
         2 . A method for encoding a message into digital information, the digital information including a plurality of digital blocks, comprising the steps of: 
 transforming each of the digital blocks into the frequency domain using a spectral transform;    identifying a plurality of frequencies and associated amplitudes for each of the transformed digital blocks;    selecting a subset of the identified amplitudes for each of the digital blocks using a primary mask from a key;    choosing message information from the message using a transformation table generated with a convolution mask; and    encoding the chosen message information into each of said transformed digital blocks by altering the selected amplitudes based on the chosen message information.    
     
     
         3 . The method of    claim 1   , wherein the digital information contains pixels in a plurality of color channels forming an image, and each of the digital blocks represents a pixel region in one of the color channels.  
     
     
         4 . The method of    claim 2   , wherein the digital information contains audio information.  
     
     
         5 . The method of    claim 1   , wherein said step of identifying comprises: 
 identifying a predetermined number of amplitudes having the largest values for each of the transformed digital blocks.    
     
     
         6 . The method of    claim 1   , wherein the chosen message information is a message bit and wherein said step of encoding comprises the step of: 
 encoding the chosen message bit into each of said transformed digital blocks by reducing the selected amplitudes using a strength fraction if the message bit is true, and not reducing the selected amplitudes if the message bit is false.    
     
     
         7 . The method of    claim 6   , wherein the strength fraction is user defined.  
     
     
         8 . The method of    claim 1   , further comprising the step of storing each of the selected amplitudes and associated frequencies in the key.  
     
     
         9 . The method of    claim 1   , further comprising the step of storing a reference subset of the digital information into the key.  
     
     
         10 . The method of    claim 1   , wherein the digital information contains pixels forming an image, further comprising the steps of: 
 saving a reference subset of the pixels in the key; and    storing original dimensions of the image in the key.    
     
     
         11 . The method of    claim 2   , wherein the digital information contains audio information, further comprising the steps of: 
 saving a reference subset of audio information in the key; and    storing original dimensions of the audio signal in the key.    
     
     
         12 . The method of    claim 10   , wherein the reference subset of pixels form a line of pixels in the image.  
     
     
         13 . The method of    claim 11   , wherein the reference subset of audio information includes an amplitude setting.  
     
     
         14 . The method of    claim 8   , wherein the image is a rectangle and the reference subset of pixels form a diagonal of the rectangle.  
     
     
         15 . The method of    claim 1   , further comprising the step of: 
 requiring a predetermined key to decode the encoded message information.    
     
     
         16 . The method of    claim 1   , further comprising the step of: 
 requiring a public key pair to decode the encoded message information.    
     
     
         17 . The method of    claim 1   , further comprising the steps of: 
 calculating an original hash value for the message; and    storing the original hash value in the key.    
     
     
         18 . A method for descaling a digital image using a key, comprising the steps of: 
 determining original dimensions of the digital image from the key;    scaling the digital image to the original dimensions;    obtaining a reference subset of pixels from the key; and    comparing the reference subset of pixels with corresponding pixels in the scaled digital image.    
     
     
         19 . A method for descaling audio digital information using a key, comprising the steps of: 
 determining original dimensions of the audio digital information from the key;    scaling the audio digital information to the original dimensions;    obtaining a reference subset of audio information from the key; and    comparing the reference subset of audio information with corresponding information in the scaled audio information.    
     
     
         20 . The method of    claim 18   , wherein said step of comparing determines a first fit value based on the comparison, and wherein the method further comprises the steps of: 
 padding the scaled digital image with an area of pad pixels; and    re-comparing the reference subset of pixels with corresponding pixels in the padded image to determine a second fit value.    
     
     
         21 . The method of    claim 20   , wherein the area of pad pixels is a row of single pixels.  
     
     
         22 . The method of    claim 20   , wherein the area of pad pixels is a column of single pixels.  
     
     
         23 . The method of    claim 20   , wherein said steps of padding and re-comparing are performed a predetermined number of times.  
     
     
         24 . The method of    claim 20   , further comprising the step of choosing a best fit value among the determined fit values and restoring the digital image to the original size, including any pad pixels associated with the best fit value.  
     
     
         25 . The method of    claim 14   , wherein said steps of padding and re-comparing are performed until a satisfactory fit value is obtained.  
     
     
         26 . A method of extracting a message from encoded digital information using a predetermined key, comprising the steps of: 
 decoding the encoded digital information into digital information, including a plurality of digital blocks, using the predetermined key;    transforming each of the digital blocks into the frequency domain using a fast Fourier transform;    identifying a plurality of frequencies and associated amplitudes for each of the transformed digital blocks;    selecting a subset of the identified amplitudes for each of the transformed digital blocks using a primary mask from the key;    comparing the selected amplitudes with original amplitudes stored in the predetermined key to determine the position of encoded message information; and    assembling the message using the encoded message information and a reverse transformation table.    
     
     
         27 . A method of extracting a message from encoded digital information using a predetermined key, comprising the steps of: 
 decoding the encoded digital information into digital information, including a plurality of digital blocks, using the predetermined key;    transforming each of the digital blocks into the frequency domain using a spectral transform;    identifying a plurality of frequencies and associated amplitudes for each of the transformed digital blocks;    selecting a subset of the identified amplitudes for each of the transformed digital blocks using a primary mask from the key;    comparing the selected amplitudes with original amplitudes stored in the predetermined key to determine the position of encoded message information; and    assembling the message using the encoded message information and a reverse transformation table.    
     
     
         28 . The method of    claim 26   , further comprising the steps of: 
 calculating a hash value for the assembled message; and    comparing the calculated hash value with an original hash value in the predetermined key.    
     
     
         29 . A method for descaling a digital signal using a key, comprising the steps of: 
 determining original dimensions of the digital signal from the key;    scaling the digital signal to the original dimensions;    obtaining a reference signal portion from the key; and    comparing the reference signal portion with a corresponding signal portion in the scaled signal.    
     
     
         30 . A method for protecting a digital signal comprising the step of: 
 creating a predetermined key comprised of a transfer function-based mask set and offset coordinate values of the original digital signal; and    encoding the digital signal using the predetermined key.    
     
     
         31 . The method of    claim 30   , wherein the digital signal represents a continuous analog waveform.  
     
     
         32 . The method of    claim 30   , wherein the predetermined key comprises a plurality of mask sets.  
     
     
         33 . The method of    claim 30   , wherein the mask set is ciphered by a key pair comprising a public key and a private key.  
     
     
         34 . The method of    claim 30   , further comprising the step of: 
 using a digital watermarking technique to encode information that identifies ownership, use, or other information about the digital signal, into the digital signal.    
     
     
         35 . The method of    claim 30   , wherein the digital signal represents a still image, audio or video.  
     
     
         36 . The method of    claim 30   , further comprising the steps of: 
 selecting the mask set, including one or more masks having random or pseudo-random series of bits; and    validating the mask set at the start of the transfer function-based mask set.    
     
     
         37 . The method of    claim 36   , wherein said step of validating comprises the step of: 
 comparing a hash value computed at the start of the transfer function-based mask set with a determined transfer function of the hash value.    
     
     
         38 . The method of    claim 36   , wherein said step of validating comprises the step of: 
 comparing a digital signature at the start of the transfer function-based mask set with a determined transfer function of the digital signature.    
     
     
         39 . The method of    claim 36   , further comprising the step of: 
 using a digital watermarking technique to embed information that identifies ownership, use, or other information about the digital signal, into the digital signal; and 
 wherein said step of validating is dependent on validation of the embedded information.  
   
     
     
         40 . The method of    claim 30   , further comprising the step of: 
 computing a secure one way hash function of carrier signal data in the digital signal, wherein the hash function is insensitive to changes introduced into the carrier signal for the purpose of carrying the transfer function-based mask set.    
     
     
         41 . A method for protecting a digital signal, comprising the steps of: 
 creating a predetermined key comprised of a transfer function-based mask set and offset coordinate values of the original digital signal;    authenticating the predetermined key containing the correct transfer function-based mask set during playback of the data; and    metering the playback of the data to monitor content.    
     
     
         42 . The method of    claim 30   , wherein the digital signal is a bit stream and further comprising the steps of: 
 generating a plurality of mask sets to be used for encoding, including a random primary mask, a random convolution mask and a random start of message delimiter;    obtaining a transfer function to be implemented;    generating a message bit stream to be encoded;    loading the message bit stream, a stega-cipher map truth table, the primary mask, the convolution mask and the start of message delimiter into memory;    initializing the state of a primary mask index, a convolution mask index, and a message bit index; and    setting a message size equal to the total number of bits in the message bit stream.    
     
     
         43 . The method of    claim 30   , wherein the digital signal is a bit stream and further comprising the steps of: 
 generating a mask set to be used for encoding, the set including a random primary mask, a random convolution mask, and a random start of message delimiter;    obtaining a message to be encoded;    compressing and encrypting the message if desired;    generating a message bit stream to be encoded;    loading the message bit stream, a stega-cipher map truth table, the primary mask, the convolution mask and the start of message delimiter into memory;    initializing the state of a primary mask index, a convolution mask index, and a message bit index; and    setting the message size equal to the total number of bits in the message bit stream.    
     
     
         44 . The method of    claim 42    wherein the digital information has a plurality of windows, further comprising the steps of: 
 calculating over which windows in the sample stream the message will be encoded;  
 computing a secure one way hash function of the information in the calculated windows, the hash function generating hash values insensitive to changes in the samples induced by a stega-cipher; and  
 encoding the computed hash values in an encoded stream of data.  
 
     
     
         45 . The method of    claim 36   , wherein said step of selecting comprises the steps of: 
 collecting a series of random bits derived from keyboard latency intervals in random typing;    processing the initial series of random bits through an MD5 algorithm;    using the results of the MD5 processing to seed a triple-DES encryption loop;    cycling through the triple-DES encryption loop, extracting the least significant bit of each result after each cycle; and    concatenating the triple-DES output bits into the random series of bits.