Method and apparatus for authentication of data streams with adaptively controlled losses

Abstract

Methods, components, and systems for efficient authentication, either through a digital signature or message authentication codes, and verification of a digital stream sent from a source to a receiver via zero or more intermediaries, such that the source or intermediary (or both) can remove certain portions of the data stream without inhibiting the ability of the ultimate receiver to verify the authenticity and integrity of the data received. According to the invention, a source may sign an entire data stream once, but may permit either itself or an intermediary to efficiently remove certain portions of the stream before transmitting the stream to the ultimate recipient, without having to re-sign the entire stream. Applications may include the signing of media streams which often need to be further processed to accommodate the resource requirements of a particular environment. Another application allows an intermediary to choose an advertisement to include in a given slot.

1 . A method for communicating data between a server and a receiver, said method comprising: 
 signing at least one original data stream which includes a plurality of blocks;    generating an intermediate data stream for the signed data stream, with arbitrary blocks adaptively removed without censoring the blocks of the original data stream;    communicating the intermediate data stream to the receiver; and    authenticating the intermediate data stream at the receiver.    
     
     
         2 . The method according to  claim 1 , wherein signing the original data stream further comprises generating a hash computation comprising auxiliary hash values and partial voltage levels equal to square of the number of input voltages m=4 2 , or sixteen  
     
     
         3 . The method according to  claim 2 , wherein generating the intermediate data stream further comprises computing the partial hash values and auxiliary hash values for each block of the signed data stream.  
     
     
         4 . The method according to  claim 2 , wherein the intermediate data stream comprises: 
 data stream blocks to be sent to the receiver; and    auxiliary hash values for the blocks to be removed.    
     
     
         5 . The method according to  claim 4 , further comprising determining, at the receiver, whether a received block is a data stream block.  
     
     
         6 . The method according to  claim 4 , further comprising recomputing, at the receiver, the partial hash value for the data stream block.  
     
     
         7 . The method according to  claim 6 , further comprising verifying, at the receiver, the signature on the recomputed partial hash value.  
     
     
         8 . The method according to  claim 2 , further comprising aggregating several auxiliary hash values before computing a partial hash value.  
     
     
         9 . The method according to  claim 1 , wherein signing the original data stream further comprises generating a Merkle tree for the original data stream and computing a value associated with a root of the Merkle tree.  
     
     
         10 . The method according to  claim 9 , wherein the intermediate data stream comprises: 
 Merkle tree values for the receiver to recompute the root of the Merkle tree; and    data stream blocks.    
     
     
         11 . The method according to  claim 9 , wherein generating the intermediate data stream further comprises: 
 determining a set of vertices corresponding to leaves in the Merkle tree associated with the blocks to be removed;    if any pair of vertices are siblings in the Merkle tree, replacing these two vertices with their parent; and    otherwise, computing the Merkle tree values associated with vertices.    
     
     
         12 . The method according to  claim 11 , further comprising recomputing, at the receiver, the value of the root of the Merkle tree.  
     
     
         13 . The method according to  claim 11 , wherein the replacing step is repeated until there are no pair of vertices that are siblings remaining.  
     
     
         14 . The method according to  claim 12 , further comprising verifying, at the receiver, the signature with the value of the root of the Merkle tree.  
     
     
         15 . The method according to  claim 1 , wherein signing the original data stream further comprises computing partial hash values of each block of each original data stream to compute a multi-layer hash chain.  
     
     
         16 . The method according to  claim 15 , wherein generating the intermediate data stream further comprises computing the partial hash values for each block of each signed data stream.  
     
     
         17 . The method according to  claim 15 , wherein the intermediate data stream comprises data stream blocks adaptively selected from different data streams.  
     
     
         18 . The method according to  claim 15 , further comprising recomputing, at the receiver, the partial hash value for each block of the intermediate data stream.  
     
     
         19 . The method according to  claim 18 , further comprising verifying, at the receiver, the signature on the recomputed partial hash value.  
     
     
         20 . The method according to  claim 1 , wherein signing the original data streams further comprises: 
 generating a Merkle tree for each of the original data streams;    computing a value associated with a root of each of the Merkle trees; and    generating a final root value by hashing the values of the roots of the Merkle trees.    
     
     
         21 . The method according to  claim 20 , wherein the intermediate data stream comprises: 
 data stream blocks; and    Merkle tree values for the receiver to recompute the root of the Merkle tree.    
     
     
         22 . The method according to  claim 20 , wherein generating the intermediate data stream further comprises: 
 determining, for each signed data stream, a set of vertices corresponding to leaves in the Merkle tree associated with the blocks to be removed;    if any pair of vertices are siblings in the Merkle tree, replacing these two vertices with their parent; and    otherwise, computing the Merkle tree values associated with vertices.    
     
     
         23 . The method according to  claim 22 , wherein the replacing step is repeated until there are no pair of vertices that are siblings remaining.  
     
     
         24 . The method according to  claim 20 , further comprising recomputing, at the receiver, the values of the roots of each Merkle tree.  
     
     
         25 . The method according to  claim 24 , further comprising recomputing, at the receiver, the final root value by hashing the values of the roots of the Merkle trees.  
     
     
         26 . The method according to  claim 25 , further comprising verifying, at the receiver, the signature with the final root value.  
     
     
         27 . The method according to  claim 25 , wherein the final root value is recomputed by an iterated hash.  
     
     
         28 . The method according to  claim 25 , wherein the final root value is recomputed by a Merkle hash.  
     
     
         29 . The method according to  claim 9 , wherein the Merkle tree is lopsided.  
     
     
         30 . The method according to  claim 20 , wherein the Merkle tree is lopsided.  
     
     
         31 . The method according to  claim 9 , further comprising forming a subtree by a group of blocks which will all be removed.  
     
     
         32 . The method according to  claim 20 , further comprising forming a subtree by a group of blocks which will all be removed.  
     
     
         33 . The method according to  claim 9 , further comprising forming a subtree by a group of blocks which will all be sent.  
     
     
         34 . The method according to  claim 20 , further comprising forming a subtree by a group of blocks which will all be sent.  
     
     
         35 . The method according to  claim 20 , wherein the final root value is generated by an iterated hash.  
     
     
         36 . The method according to  claim 20 , wherein the final root value is generated by a Merkle hash.  
     
     
         37 . The method according to  claim 1 , further comprising determining blocks that will never be removed.  
     
     
         38 . The method according to  claim 37 , further comprising applying identity function as a first layer hash when the blocks will never be removed.  
     
     
         39 . The method according to  claim 2 , further comprising applying Forward Error Correction (FEC) techniques to the hash values.  
     
     
         40 . The method according to  claim 15 , further comprising applying Forward Error Correction (FEC) techniques to the hash values.  
     
     
         41 . The method according to  claim 1 , wherein signing the original data stream uses a digital signature.  
     
     
         42 . The method according to  claim 41 , wherein the digital signature is applied to final hash values of the blocks of the original data stream.  
     
     
         43 . The method according to  claim 1 , wherein signing the original data stream uses message authentication codes.  
     
     
         44 . The method according to  claim 43 , wherein the message authentication codes are applied to final hash values of the blocks of the original data stream.  
     
     
         45 . The method according to  claim 1 , wherein the removed data stream blocks include advertisements.  
     
     
         46 . A system for communicating data between a server and a receiver, comprising: 
 a signer signing at least one original data stream which includes a plurality of blocks;    a data stream generator generating an intermediate data stream for the signed data stream, with arbitrary blocks adaptively removed without censoring the blocks of the original data stream;    a receiver authenticating the intermediate data stream.    
     
     
         47 . The system according to  claim 46 , wherein the signer generates a hash computation comprising auxiliary hash values and partial hash values.  
     
     
         48 . The system according to  claim 47 , wherein the data stream generator receives the signed data stream, and computes the partial hash values and auxiliary hash values for each block thereof.  
     
     
         49 . The system according to  claim 47 , wherein the receiver receives the intermediate data stream and recomputes the partial hash value for the data stream block.  
     
     
         50 . The system according to  claim 47 , wherein the signer aggregates several auxiliary hash values before computing a partial hash value.  
     
     
         51 . The system according to  claim 46 , wherein the signer computes values associated with a root of a Merkle tree generated for an original data stream.  
     
     
         52 . The system according to  claim 51 , wherein the data stream generator: 
 receives the signed data stream;    determines a set of vertices corresponding to leaves in the Merkle tree associated with the blocks to be removed;    if any pair of vertices are siblings in the Merkle tree, replaces these two vertices with their parent; and    otherwise, computes the Merkle tree values associated with vertices.    
     
     
         53 . The method according to  claim 52 , wherein the replacing step is repeated until there are no pair of vertices that are siblings remaining.  
     
     
         54 . The system according to  claim 51 , wherein the receiver receives the intermediate data stream and recomputes the value of the root of the Merkle tree.  
     
     
         55 . The system according to  claim 46 , wherein the signer computes partial hash values of each block of each data stream to compute a multi-layer hash chain.  
     
     
         56 . The system according to  claim 55 , wherein the data stream generator receives the signed data stream and computes the partial hash values for each block of each signed data stream.  
     
     
         57 . The system according to  claim 55 , wherein the receiver receives the intermediate data stream and recomputes the partial hash value for each block of the intermediate data stream.  
     
     
         58 . The system according to  claim 46 , wherein the signer: 
 generates a Merkle tree for each of the original data streams;    computes a value associated with a root of each of the Merkle trees; and    generates a final root value by hashing the values of the roots of the Merkle trees.    
     
     
         59 . The system according to  claim 58 , wherein the data stream generator: 
 receives the signed data stream;    determines, for each signed data stream, a set of vertices corresponding to leaves in the Merkle tree associated with the blocks to be removed;    if any-pair of vertices are siblings in the Merkle tree, replaces these two vertices with their parent; and    otherwise, computes the Merkle tree values associated with vertices.    
     
     
         60 . The method according to  claim 59 , wherein the replacing step is repeated until there are no pair of vertices that are siblings remaining.  
     
     
         61 . The system according to  claim 58 , wherein the receiver receives the intermediate data stream and recomputes the values of the roots of each Merkle tree.  
     
     
         62 . A computer program product containing program code for performing a method of signing an original data stream, the method comprising: 
 decomposing at least one original data stream into a plurality of blocks;    computing ancillary information selected from the group consisting of partial hash values of blocks of the signed data stream, values associated with a root of a Merkle tree generated for the original data stream, a multi-layer hash chain computed from partial hash values of each block of each data stream, and a final root value computed by hashing values of roots of Merkle trees, each of which corresponds to an original data stream;    computing authentication information for each block based on the ancillary information;    generating a signed data stream comprising the original data stream and the authentication information; and    generating an intermediate data stream by adaptively removing arbitrary blocks without censoring the original data stream, wherein the intermediate data stream can be authenticated by a receiver.    
     
     
         63 . The computer program product according to  claim 62 , wherein a digital signature is used for authentication.  
     
     
         64 . The method according to  claim 63 , wherein the digital signature is applied to final hash values of the blocks of the original data stream.  
     
     
         65 . The computer program product according to  claim 62 , wherein message authentication codes are used for authentication.  
     
     
         66 . The method according to  claim 65 , wherein the message authentication codes are applied to final hash values of the blocks of the original data stream.  
     
     
         67 . The method according to  claim 62 , wherein the ancillary information is computed at a signer.  
     
     
         68 . The method according to  claim 62 , wherein the ancillary information is computed at an intermediary.  
     
     
         69 . A computer program product containing program code for performing a method of adaptively removing arbitrary blocks from a signed data stream for an original data stream, the method comprising: 
 determining to-be-sent data stream blocks in the signed data stream without censoring the original data stream;    adaptively removing other blocks in the signed data stream by generating an intermediate data stream; and    sending the intermediate data stream to a receiver for authentication.    
     
     
         70 . The computer program product according to  claim 69 , wherein the method further comprises computing the partial hash values and auxiliary hash values for each block of the signed data stream.  
     
     
         71 . The computer program product according to  claim 70 , wherein the intermediate data stream comprises to-be-sent data stream blocks and the auxiliary hash values for the blocks to be removed.  
     
     
         72 . The method according to  claim 70 , further comprising transmitting the partial hash values and auxiliary hash values.  
     
     
         73 . The computer program product according to  claim 69 , wherein the method further comprises: 
 determining a set of vertices corresponding to leaves in the Merkle tree associated with the blocks to be removed;    if any pair of vertices are siblings in the Merkle tree, replacing these two vertices with their parent; and    otherwise, computing the Merkle tree values associated with vertices.    
     
     
         74 . The computer program product according to  claim 73 , wherein the intermediate data stream comprises to-be-sent data stream blocks and Merkle tree values associated with the blocks to be removed.  
     
     
         75 . The method according to  claim 73 , wherein the replacing step is repeated until there are no pair of vertices that are siblings remaining.  
     
     
         76 . The computer program product according to  claim 69 , wherein the intermediate data stream comprises data stream blocks adaptively selected from different data streams.  
     
     
         77 . A computer program product containing program code for performing a method of authenticating an intermediate data stream, the method comprising: 
 distinguishing data stream blocks in the intermediate data stream, which is derived from an original data stream, but has some data removed from it;    computing ancillary information for blocks in the intermediate data stream, the ancillary information being selected from the group consisting of partial hash values of blocks of the intermediate data stream, values associated with a root of a Merkle tree generated for the original data stream, a multi-layer hash chain, and a final root value computed by hashing values of roots of Merkle trees generated for original data streams; and    verifying authentication information.    
     
     
         78 . The computer program product according to  claim 77 , wherein a digital signature is used for authentication.  
     
     
         79 . The computer program product according to  claim 77 , wherein message authentication codes are used for authentication.  
     
     
         80 . A server in a data communication network, comprising a processor and the computer program product according to  claim 62 .  
     
     
         81 . An intermediate node in a data communication network, comprising a processor and the computer program product according to  claim 69 .  
     
     
         82 . A receiver in a data communication network, comprising a processor and the computer program product according to  claim 77.