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

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.

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.

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.