Register or Login To Download This Patent As A PDF
United States Patent Application 
20060136728

Kind Code

A1

Gentry; Craig B.
; et al.

June 22, 2006

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
resign 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.
Inventors: 
Gentry; Craig B.; (Mountain View, CA)
; Hevia; Alejandro; (Seal Beach, CA)
; Kumar; Ravi; (Palo Alto, CA)
; Kawahara; Toshiro; (Saratoga, CA)
; Ramzan; Zulfikar Amin; (San Mateo, CA)

Correspondence Address:

MACPHERSON KWOK CHEN & HEID LLP
1762 TECHNOLOGY DRIVE, SUITE 226
SAN JOSE
CA
95110
US

Serial No.:

543640 
Series Code:

10

Filed:

August 4, 2004 
PCT Filed:

August 4, 2004 
PCT NO:

PCT/US04/25513 
371 Date:

July 28, 2005 
Current U.S. Class: 
713/176; 348/E7.056; 713/160; 713/181; 713/193; 714/E11.207 
Class at Publication: 
713/176; 713/160; 713/181; 713/193 
International Class: 
H04L 9/00 20060101 H04L009/00; G06F 12/14 20060101 G06F012/14; H04L 9/32 20060101 H04L009/32; G06F 11/30 20060101 G06F011/30 
Claims
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.sup.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 multilayer 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 multilayer
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 anypair 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 multilayer 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
tobesent 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 tobesent 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 tobesent 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 multilayer 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.
Description
CROSSREFERENCE TO RELATED APPLICATIONS
[0001] This application claims the benefit of Provisional Application No.
60/495,787, filed Aug. 15, 2003. The present application incorporates the
disclosure of this provisional application by reference.
BACKGROUND OF THE INVENTION
[0002] 1. Field of the Invention
[0003] The present invention relates to data stream authentication, and
more specifically to authentication schemes with adaptively controlled
packet loss.
[0004] 2. Description of the Related Art
[0005] In many cases, it is desirable to append authentication information
to a stream of data to assure a recipient that the data came from a
specific source and was not modified enroute. For example, if the data
is being provided to an application, then it would be important for the
application that the data has not been corrupted either maliciously or by
accident.
[0006] In cryptography, there are two traditional mechanisms for
permitting such authentication:
[0007] 1. Message Authentication Codes (MAC)
[0008] 2. Digital Signatures
[0009] With a MAC, both the original source and the ultimate receiver must
possess knowledge of a shared secret key. The sender applies a
mathematical transformation involving the original data and secret key,
and produces a tag. The receiver can then apply a similar transformation
with the data, the tag, and the secret key to verify the origin and the
integrity of the data.
[0010] With Digital Signatures, the key is split into two parts: a secret
signing key and a public verification key. The public verification key
can be used to verify anything signed using the secret signing key. The
key is split in such a way that it is not possible to derive the private
portion from the public portion. The sender applies a mathematical
transformation involving the original data and secret signing key, and
produces a signature. The recipient can then apply a similar
transformation with the data, the signature, and the public verification
key to ascertain the identity of the sender and the integrity of the
data.
[0011] Digital signatures have a nonrepudiation property that MACs do
not. Namely, the signer cannot later deny having signed the document
since the signing key is secret and was in the signer's possession. Of
course, the signature owner can always claim that the secret signing key
was stolen by some adversary.
[0012] Because of their nature, traditional authentication schemes do not
tolerate any transformations to the data made by the source or by an
intermediate. If a document is modified after it is signed, the
verification step will so indicate, and will fail.
[0013] But for many applications, it is not only convenient, but sometimes
necessary, to permit some specific types of modifications. For example,
scalable video coding schemes, a highlevel picture of the principle of
which is shown in FIG. 1, have the property that a subset of the stream
can be decoded and the quality is commensurate with the amount decoded.
These schemes may encode video into a base layer and then zero or more
"enhancement" layers. Just the base layer alone would be sufficient to
view the stream. Enhancement layers are utilized to improve the overall
quality.
[0014] Now, in an environment that is resource constrained, one might want
to strip the enhancement layers and only send the base layers. If the
entire stream has been digitally signed or authenticated in conventional
ways, then by removing the enhancement layers, the original tag or
signature becomes invalid. Thus the entire stream would have to be
reauthenticated.
[0015] Alternatively, one may want to splice several streams of different
qualities as in a simulcast situation. There may be one highquality
version of the stream, one mediumquality version of the stream, and one
lowquality version of the stream. If network resources are available,
then the highquality stream may be sent, but if the network congestion
goes up, then one may want to shift to the medium or low quality streams.
In an alternate scenario, it could be the case that the receiver is
mobile and is leaving one network environment and entering another that
has different resource restrictions. The splicing situation can be
considered a special case of a lossy situation where the quality of
signal transmission is poor or otherwise is degraded, for example, by
viewing the three data streams as one huge layered stream and imagining
that two out of three frames are being discarded.
[0016] Yet another application is dynamic advertising. A source may
include in a given slot a number of advertisements that can be displayed.
An intermediary can then choose from among these choices which
advertisement it would like to display. The choice can, for example, be
based upon what the intermediary thinks will be the best advertisement
for the target audience. The advertisements themselves can be created by
an intermediary or some other party, and can be provided to the source
either in their original form or may be hashed. The source would then
include them when signing the stream.
[0017] Thus, signature schemes that can handle these types of losses in a
secure manner are needed. Here, "secure" means that the ultimate end
receiver can determine with overwhelmingly high confidence that the data
it receives comes from a stream that was originally signed validly, but
for which certain portions were removed. In addition, there is also a
need for an intermediary that can adaptively and intelligently decide
which blocks to drop.
[0018] One conventional solution to the controlled loss authentication
problem is to authenticate each packet individually. This solution has
two substantial drawbacks. First, in the case of using digital
signatures, a fairly expensive computation must be performed for each
packet. Second, in both the digital signature and MAC case,
authentication information must be appended to each packet, which may not
be feasible in consideration of efforts to remove portions of the stream
stem to meet bandwidth constraints. levels. Then, the decoder 984 is
designed to select one of the tone voltages of 64 IEEE/ACM Transactions
on Networking, 7(4):502:513, August 1999, the authors propose a solution
in which each data element is hashed, and then the resulting hashes are
digested using a Merkletree. The root of the Merkle tree is
authenticated. Then, with each data element, the conodes are sent,
thereby allowing the receiver to authenticate without it. Since Wong and
Lam deal with perpacket authentication, each packet contains
authentication information. In particular, if v is the size, in bytes,
of a Merkle tree node, h is the height of the Merkle tree, then each data
element transmitted must be accompanied by v.times.h bytes. Thus,
this approach does not deal with the controlled loss authentication
problem, and is not bandwidth efficient.
[0019] In R. Johnson, D. Molnar, D. Song, and D. Wagner, Homomorphic
Signature SchemesRSA 2002, Cryptographer's Track, the authors propose a
redactable signature scheme. It permits certain specific transformations
on the data while still allowing the receiver to verify. It also allows
arbitrary deletion of substrings in a signed document and has
applications for censoring. Suppose n message blocks m=m.sub.1, . . . ,
m.sub.n are to be signed, and assume that n is a power of 2. The scheme
starts with an initial secret key k and uses it to generate n keys
k.sub.1, . . . , k.sub.n with the aid of a treelike construction such as
that of Goldreich, Goldwasser, and Micali (GGM), O. Goldreich, S.
Goldwasser, and S. Micali, How to Construct Random Functions, Journal of
the ACM, vol. 33, No. 4, 1986, pages 210217. Then, to sign message m,
the triplets (0, m.sub.1, k.sub.1), . . . , (0, m.sub.n, k.sub.n) are
hashed in a Merklelike tree and the root r is signed to produce the
signature s. The difference between this tree and a regular Merkle tree
is that the value 1 is prepended before the internal hashes are
computed. With knowledge of k, anyone can verify s. However, in order to
censor the data stream, the value of k is never published. Instead, only
certain intermediate values of the GGM tree are published. These values
correspond to the information needed to derive the final keys k.sub.i
corresponding to the data elements which are not censored. With
uncensored blocks, the intermediate GGM values, and the conodes in the
Merklelike tree, the signature can be verified. However, the above
Homomorphic Signature Scheme takes precautions, via a GGM tree, to
protect the confidentiality of censored data and requires all uncensored
message blocks, all conodes, and all keying information in order to
permit verification, and thus is not efficient.
[0020] Accordingly, there has been a need for a secure authentication
scheme that permits controlled removal of certain blocks in a stream
without weakening the receiver's ability to verify the authentication
information, and without requiring confidentiality of censored data.
SUMMARY OF THE INVENTION
[0021] In view of the foregoing, it is an object of the present invention
to provide schemes for secure authentication under adaptive data loss
both in the symmetric setting (with MAC) or in the asymmetric setting
(with digital signatures), which are efficient with respect to the
computation requirements of the sender, receiver, and intermediary, as
well as the bandwidth requirements of the channels over which these
parties communicate.
[0022] Briefly, the present invention addresses the following problems:
[0023] 1. adaptive loss (subsequence) authentication, wherein data chunks
are removed arbitrarily;
[0024] 2. simulcast authentication, wherein several data streams are
intertwined and only one data chunk is taken at a time from a given
stream, and the data from the other streams is dropped; and
[0025] 3. adaptively lossy simulcast authentication, wherein sometimes the
entire data chunk is dropped altogether.
[0026] The present invention provides the following schemes:
[0027] 1. Linear Scheme for Subsequence Authentication;
[0028] 2. Linear Scheme for Simulcast Authentication;
[0029] 3. Tree Scheme for Subsequence Authentication; and
[0030] 4. Tree Scheme for Simulcast Authentication.
[0031] Each of the above schemes may incorporate either a digital
signature or a MAC. Therefore, the present invention implicitly provides
8 (=4.times.2) schemes.
[0032] The schemes use cryptographic hash functions to process the blocks
of the original stream and create a short digest. A digital signature or
MAC is then applied to the digest, thereby providing authentication
information. If the receiver is given the entire stream, then it can
recompute the digest and verify the signature. When specific portions of
the stream need to be removed, the remover sends information that allows
the receiver to efficiently compute the digest. The amount of information
provided to the receiver in this setting is related to the output size of
the cryptographic hash function and is otherwise independent of the
actual data stream.
[0033] According to one aspect of this invention, Linear Scheme for
Subsequence Authentication, the intermediary or source can remove
arbitrary blocks (irrespective of their location) while still permitting
the receiver to authenticate information. The scheme involves computing a
twolayer hash chain and providing the recipient with various values in
this chain. The scheme is online for the receiver in the sense that the
receiver does not have to incur any delay in verifying the authentication
information. In an optimization and generalization to this scheme, one
second layerhash is computed for every bundle of r firstlayer hashes.
When r=1, the scheme is the original linear scheme for subsequence
authentication. In an improvement to this scheme, several firstlayer
hashes are aggregated before performing the secondlayer hash.
Consequently, fewer secondlayer hashes need to be performed.
[0034] According to a second aspect of this invention, Linear Scheme for
Simulcast Authentication, the intermediary or source is provided with
multiple streams and can arbitrarily switch among which stream it
transmits while still permitting the receiver to authenticate
information. The scheme involves computing a multilayer hash chain and
providing the recipient with various values in this chain. The scheme is
online for the tone power source lines by 1/2, 1/4, 1/8, . . . . Then,
the area occupied by the authentication information.
[0035] According to a third aspect of this invention, Tree Scheme for
Subsequence Authentication, the intermediary or source can remove
arbitrary blocks (irrespective of their location) while still permitting
the receiver to authenticate information. The scheme involves computing a
hash tree and providing the recipient with various values in this tree.
In the case that some subset (of size greater than one) of dropped blocks
constitute a subtree of the hash tree, the hashed scheme is more
efficient with respect to bandwidth than the corresponding linear scheme.
The scheme is not online for the receiver in the sense that the receiver
must wait for all blocks before being able to verify the authentication
information.
[0036] According to a fourth aspect of this invention, Tree Scheme for
Simulcast Authentication, the intermediary or source is provided with
multiple streams and can arbitrarily switch among which stream it
transmits while still permitting the receiver to authenticate
information. The scheme involves computing a hash tree and providing the
receiver with various values in this tree. The scheme is not online for
the receiver in the sense that the receiver must wait for all blocks
before being able to verify the authentication information.
[0037] In all aspects of this invention, it is assumed that the sender has
possession of all data to be signed at the onset. In most cases, such as
when media is prerecorded, this will not be a concern. In the case of a
live stream, the present invention breaks the stream into smaller chunks
and applies the schemes specified herein. Those skilled in the art will
recognize that variations and modifications can be made without departing
from the spirit of the invention.
[0038] The present invention permits a situation in which an intermediary
may adaptively and intelligently decide which blocks are to be dropped.
The schemes of the present invention readily adapt to any model for
dropping blocks. Moreover, the intermediary is not required to know of
any cryptographic keying material. Furthermore, if the source provides
the intermediary with various hash values, then the intermediary can
avoid having to do any cryptographic related computation. Instead, it
just has to forward the blocks it desired together with the hash
information for those blocks that are dropped.
[0039] All of the inventive schemes have the property that, given
knowledge ahead of time that a given block will not be dropped, then the
first layer hash on that block will not be performed. That is, the first
layer hash for just that block can be replaced with the identity function
(h(x)=x).
[0040] Both the linear and treebased schemes can take advantage of
correlation among blocks of data. For example, in the treebased scheme,
if a given subset of blocks has the behavior that all will be dropped or
all will be kept, then these blocks can be placed as all the leaves of
the same subtree. In the event that all packets in the given subset are
dropped, only the root has to be transmitted. However, this concept
applies even if the correlation is probabilistic. For example, if a given
block being dropped makes it more likely that another block will be
dropped, then these blocks should also be clustered. Likewise, in the
linear schemes, if a given sequence of frames are to be all kept or
dropped, these frames can be treated as a single block unit to be hashed.
Then, if the entire sequence of frames is dropped only a single hash
value needs to be sent.
BRIEF DESCRIPTION OF THE DRAWINGS
[0041] The present invention is described herein with reference to the
accompanying drawings, similar reference numbers being used to indicate
functionally similar elements.
[0042] FIG. 1 shows a highlevel depiction of a scalable coder.
[0043] FIG. 2 shows a block diagram of a sender or source.
[0044] FIG. 3 shows a block diagram of a receiver.
[0045] FIG. 4 shows a block diagram of an intermediary.
[0046] FIG. 5 shows a block diagram of a system including a sender, a
receiver, and an intermediary.
[0047] FIG. 6 illustrates a Merkle Tree with eight leaves.
[0048] FIG. 7 illustrates a basic linear subsequence authentication scheme
according to one embodiment of the present invention.
[0049] FIG. 8 illustrates an optimized linear subsequence authentication
scheme with r=3 and with n a multiple of r, according to one embodiment
of the present invention.
[0050] FIG. 9 illustrates a basic linear simulcast authentication scheme
according to one embodiment of the present invention.
[0051] FIG. 10 illustrates a treebased subsequence authentication scheme
according to one embodiment of the present invention.
[0052] FIG. 11 illustrates a treebased simulcast authentication scheme
according to one embodiment of the present invention.
DETAILED DESCRIPTION OF EMBODIMENTS
[0053] In the schemes of the present invention, an initial sender 200 in
FIG. 2 is responsible for authenticating the data stream. As shown, each
sender 200 includes a processor 201 in bidirectional communication with a
memory 202. The processor 201 executes program code for carrying out the
schemes of the present invention to generate, transmit or receive data
streams. The memory 202 stores cryptographic keys, program codes, as well
as intermediate results and other information used during execution of
the schemes. A communications network 203 is provided over which the
sender may communicate with receivers.
[0054] FIG. 3 shows a block diagram of a receiver which receives data
streams from the sender or server or an intermediary over a communication
network according to one embodiment of the present invention. The system
of the present invention includes a number of receivers, which verify the
received data. Each receiver 300 includes a processor 301 in
bidirectional communication with a memory 302. The processor 301 executes
program code for carrying out the schemes of the present invention to
generate, transmit, and receive data streams. Program code may be created
according to methods known in the art. The memory 302 stores
cryptographic keys and the program code, as well as intermediate results
and other information used during execution of the schemes.
[0055] A communications network 303 is provided over which the sender and
the receivers may communicate. The communications network may be of
various common forms, including, for example, a local area network (LAN),
a wide area network (WAN), and/or a mobile telephone network. The network
may permit either wired or wireless communications.
[0056] FIG. 4 shows a block diagram of an intermediary. There may be more
than one intermediary; alternatively, the source and intermediary may be
identical. If the intermediary and source are not identical, then the
intermediary needs not have any cryptographic keying material. The data
for the sender may pass through one or more intermediaries shown in FIG.
4 on its way to the sender or receiver. The intermediaries may choose to
perform certain transformations on the data. Each intermediary 400
includes a processor 401 in bidirectional communication with a memory
402. The processor 401 executes program code for carrying out the schemes
of the present invention to generate, transmit, and receive data streams.
The memory 402 may store cryptographic keys.
[0057] FIG. 5 shows a block diagram of a system according to one
embodiment of the present invention, including a sender 501, an
intermediary 503, a receiver 505, and communication networks 502 and 504.
As shown, the sender 501 transmits an original data stream with signature
and optional helper information to the intermediary 503 via the
communication network 502, which then transmits a reduced data stream
with signature and relevant helper information to receiver 505 via
communication network 504.
[0058] The abovementioned transformations involve removing certain
portions of the data. If an intermediary modifies the data stream, it
will determine what information, if any, is required by the receiver to
verify the authentication information associated with the stream.
[0059] M denotes a media stream that can be broken up into it blocks of
length b: M=M.sub.1M.sub.2 . . . M.sub.n, M.sub.i=b,
1.ltoreq.i.ltoreq.n. H denotes a cryptographic compression function that
takes as input a bbit payload as well as a vbit initialization vector
or IV, and produces a vbit output where typically v<b. These
cryptographic compression functions are collision resistant, that is, it
is hard to find two inputs m.sub.1 and m.sub.2 with m.sub.1.noteq.m.sub.2
such that H(IV,m.sub.1)=H(IV, m.sub.2) for a fixed IV. It is assumed that
there is a standard IV, called IV.sub.0, that is fixed and publicly
known. For notational simplicity, the description below will not
explicitly list the IV as an argument in the hash functionthough it
should be thought of as being there implicitly.
[0060] Examples of such cryptographic compression functions are found in
SHA1 or MD5. The compression function in SHA1 has an output and IV size
of 160bits whereas the compression function in MD5 works with 128bit
values. Both allow for a 512bit payload size. When it is necessary to
operate on data blocks that are larger than the payload size, application
of the compression function is repeated. Functions that operate as such
while still retaining the collision resistance property are termed
cryptographic hash functions. For simplicity, this term is used below
even if a data block that fits within the payload is dealt with.
[0061] For the schemes involving digital signatures, it is assumed that a
publickey infrastructure exists, and that the sender has a key pair (Pk,
Sk). Sk is the sender's private signing keywhich can be used for
appending a digital signature to a message, and Pk is the sender's public
verification key which can be used to verify the authenticity of any
signature issued using Pk. .sigma.(Sk, M) denotes the digital signature
algorithm on message M under signing key Sk, and v(Pk, M, .sigma.)
denotes the verification algorithm. The intermediate does not need to
know either the signing or the verification key. For the schemes
involving MAC, it is assumed that both the initial sender S and the
ultimate receiver R share knowledge of a symmetric key, which need not be
known by the intermediaries.
[0062] The schemes of the present invention make use of conventional
constructs involving cryptographic compression functions. One such
construct is an iterated hash function which is built from cryptographic
compression functions as follows. Suppose a message M can be broken up
into n blocks of length b, and H is a cryptographic compression function
with a bbit payload and a vbit output. The iterated hash function
defined by H is the value x.sub.n where: x 1 = H .times.
.times. ( IV 0 , M 1 ) x 2 = H .times. .times. (
x 1 , M 2 ) .times. x n = H .times. .times.
( x n  1 , M n )
[0063] Assuming that it is hard to find collisions in the compression
function H, it is then hard to find collisions in the iterated hash.
Typically, when one wants to digitally sign a message, an iterated hash
is applied to the message, and the resulting output is signed. The
methods, systems, and components of the present invention will involve
similar constructions, but intermediate values will be provided to aid in
verification.
[0064] Another conventional construct involving cryptographic compression
functions is a Merkle tree. FIG. 6 shows a graphical depiction of a
Merkle tree with eight leaves. Each leaf is the hash of the message below
it. Each interior node represents the hash of its children. The root is
signed. Suppose that M can be broken up into n blocks M=M.sub.1 . . .
M.sub.n. For least 2K bits so that voltages of 4.sup.K different voltage
levels can be output from the incorporate powers other than 2. The Merkle
tree associated with M under hash function H is a binary tree in which
each node is associated with a specific value. There are n leaves, and
each leaf l.sub.i takes on the hash of M.sub.ithat is, H(IV.sub.0,
M.sub.i). Each interior (nonleaf) node then takes on the value
associated with the hash of the concatenations of the values of its two
children. That is, if vertex v has children v.sub.1 and v.sub.2 where
v.sub.1 has value x.sub.1 and v.sub.2 has value x.sub.2, then the value
associated with v is H(IV.sub.0, x.sub.1 x.sub.2).
[0065] the selection circuit receives as input first through mth
(=2.sup.K, where K is a root of the tree associated with the message M
forming the digest is signed. If the underlying compression or hash
function is collision resistant, then it will be hard to find two
different messages whose Merkle root value is identical.
[0066] The present invention also makes use of the notion of the conodes
for a given vertex in a Merkle tree. The conodes of a vertex v consist
of the direct siblings of the vertices on the path from v to the root.
Given a vertex v and its conodes, one can compute the sequence of hash
functions that lead from v to the root.
1. Subsequence Authentication
[0067] The linear subsequence authentication scheme of the present
invention allows stream authentication even when arbitrary blocks from
the message are removed. As long as the blocks sent by an intermediate
node are a proper subsequence of the original message, the receiver can
authenticate the stream.
1.1 Signing
[0068] FIG. 7 illustrates a basic linear subsequence authentication scheme
according to one embodiment of the present invention. Given a message M,
signature generation follows a similar paradigm to an iterated hash,
except that it uses "two hashing layers".
[0069] Given a message M=M.sub.1M.sub.2 . . . M.sub.n, in one embodiment,
the present invention generates partial hash computations h.sub.1, . . .
, h.sub.n as follows: h 0 = IV 0 g 1 = H .times.
.times. ( h 0 , M n ) h 1 = H .times. .times. (
h 0 , g 1 ) g 2 = H .times. .times. ( h 1 , M n
 1 ) h 2 = H .times. .times. ( h 1 , g 2 )
.times. g n = H .times. .times. ( h n  1 , M
1 ) h n = H .times. .times. ( h n  1 , g n )
( 1 )
[0070] In the process of computing h.sub.1, . . . , h.sub.n, the scheme
shown in FIG. 7 computes auxiliary hash values g.sub.1, . . . , g.sub.n
which are not sent. The initial sender S transmits (M,
.sigma..sub.Sk(h.sub.n)). The value of IV.sub.0 can be used as the IV for
the computation of all the g.sub.i values.
[0071] Alternatively, the sender S may decide to transmit the hash values
h.sub.i along with the message blocks (M.sub.1, h.sub.n1,
.sigma..sub.Sk(h.sub.n)), (M.sub.2, h.sub.n2) . . . (M.sub.n,h.sub.0).
1.2 Signature Update
[0072] If an intermediate node wants to strip off k arbitrarily located
message blocks, the node generates a resulting "message" M', identical to
M but where k blocks have been removed. The receiver needs to be able to
authenticate M'.
[0073] Given the received nblock message M, the intermediate node
computes "new" blocks M.sub.1', . . . , M.sub.n'. For each message block
M.sub.ni+1 (starting from the end, i=1 to i=n), the intermediate node
computes the corresponding auxiliary and partial hashes as follows:
g.sub.i=H(h.sub.i1, M.sub.ni+1), h.sub.i=H(h.sub.i1, g.sub.i) (2)
[0074] Depending on whether the block will be forwarded or dropped, the
intermediate node computes M'.sub.ni+1=M.sub.ni+1, if block M.sub.i is
forwarded, or g.sub.i, if block M.sub.i is dropped (3)
[0075] Let t be the index of the last message block that the intermediate
node wants to send to the receiver, such that M.sub.t'=M.sub.t, and
M.sub.l'.noteq.M.sub.l for all l>t. The intermediate node finally
transmits M.sub.1', . . . M.sub.n'.sigma..sub.Sk(h.sub.n), h.sub.nt)
[0076] Some standard encoding is applied to the block contents to
facilitate distinguishing between "message blocks" and "hashes". Skilled
artisans would appreciate that there are numerous ways to perform this
encoding.
[0077] Alternatively, to enable online verification, the intermediate
node transmits (M.sub.1',h.sub.n1,.sigma..sub.Sk(h.sub.n)),
(M.sub.2',h.sub.n2), . . . (M.sub.n', h.sub.0)
1.3 Verification
[0078] The receiver can verify the signature by computing h.sub.n from
M.sub.1', . . . , M.sub.k' and h.sub.nt as follows: for each message
block M'.sub.ni+1 (starting from the end, i=1 to i=n), and depending on
whether the received block is a "message block" or a "hash", it computes
h.sub.i=H(h.sub.i1, H(h.sub.i1, M'.sub.ni+1)), if M'.sub.ni+1 is a
"message block" H(h.sub.i1, M'ni+1)), if M'.sub.ni+1 is a "hash" (4)
[0079] The receiver can then verify the signature on h.sub.n as normal
using the verification algorithm v.
[0080] The alternative online verification proceeds as follows: the
receiver computes the partial hash h.sub.n from (M'.sub.1, h.sub.n1)
using relation (4) and then it verifies the signature on the partial hash
h.sub.n. Afterwards, for i=2, . . . , n, it computes the partial hash
h.sub.i from (M'.sub.i, h.sub.ni) using (4) and verifies that the so
computed hash matches the hash value received in iteration i1.
1.4 Security
[0081] As mentioned above, the iterated hash construction is collision
resistant so long as the underlying hash function H is as well. In
particular, if one finds a collision in the iterated construction, then
at some point there is an internal collision, which means one can find a
collision on the hash function H. If an adversary can come up with a
nonsubsequence forgery (that is, a message/signature pair that is not
obtained by merely taking a subsequence of the original message), then it
is possible to show that one can demonstrate either a collision in the
hash function or a forgery on the underlying signature scheme. Therefore,
as long as the signature scheme is not easily susceptible to forgery and
the hash function is not easily susceptible to collisions, the scheme
presented above is secure.
1.5 Performance
[0082] When the intermediary removes blocks, it only needs to compute the
hash of the block being removed. This computation does not involve any
publickey steps and is fairly efficient. In fact, the throughput of
algorithms like SHA1 is on the order of a few hundred megabits per
second. Moreover, if the intermediate nodes are resource bounded with
respect to computation, the source can follow the alternative approach
and include the intermediate h.sub.i values. In the case of SHA1, each
such value is 20bytes long, so the bandwidth overhead will likely be
quite small.
[0083] A tradeoff between bandwidth usage and buffering/computation is
possible by sending some intermediate h.sub.i values selectively. If the
receiver can store up to b message blocks, then the intermediate node can
send the hash value h.sub.nb only after b message blocks. Authentication
can be done as described above starting from h.sub.nb. Then, the
intermediate node sends a second "bundle" (next b message blocks and
h.sub.n2b), which is authenticated by recomputing the partial hashes
h.sub.nb, . . . , h.sub.n2b+1 and then verifying the recomputed hash
value h.sub.nb matching the one received in the first bundle.
[0084] The computations of this embodiment do not require storing the
entire stream in memory since only a single input block to the hash
function is needed at any given time.
[0085] The scheme of the first embodiment permits the role of an
intermediary which can adaptively and intelligently choose to remove any
number of blocks without requiring knowledge of any cryptographic keying
material. Moreover, the intermediary can be proximate to the receiver and
can control the loss (and therefore the amount of hash information)
dynamically. Furthermore, the authentication information can be verified
in an online manner by the receiver. That is, the receiver can verify the
authentication information as it receives the stream, and will not be
required to do any form of extensive buffering. Also, the first layer
hash computations are not required for any block that will not be
dropped. For example, an MPEG Iframe or the base layer of a scalable
coding scheme will not be intentionally dropped. For these blocks, only
the second layer is required. In this instance, the first layer hash
function for that block can be replaced with the identity function
h(x)=x. In a similar spirit, if a given sequence of frames will either
all be dropped or all be kept, then the above scheme is even more
advantageous since it can cluster these as a single block before hashing.
2. An Efficiency Improvement to the Subsequence Authentication
[0086] The second embodiment of the present invention provides an
efficiency improvement to the basic linear subsequence authentication, by
aggregating several first layer hashes before performing the second layer
hashes. As a result, the method according to the second embodiment
performs fewer second layer hashes. For a typical compression function,
such as the one accompanying SHA1, the payload size is 64 bytes whereas
the digest size is 20 bytes. As a result, in this situation, three
digests can be concatenated together before the second layer function is
called. In the second embodiment, it is assumed that r hashes are
aggregated. In addition, for any decimal number a, .left brktbot.a.right
brktbot. denotes the smallest integer greater or equal than a, and .left
brkttop.a.right brktbot. denotes the largest integer less or equal than
a.
2.1 Signing
[0087] For a message M, signature generation according to the second
embodiment follows a similar paradigm to the scheme of the first
embodiment, and uses "two hashing layers". However, the scheme of the
second embodiment involves fewer hashes than that of the first
embodiment. FIG. 8 shows an improved linear subsequence authentication
scheme according to one embodiment of the present invention, with r=3 and
with n a multiple of r. In this scheme groups of r firstlayer hashes are
hashed in the second layer. Given a message M=M.sub.1M.sub.2 . . .
M.sub.n, the scheme of the second embodiment generates the partial hash
computations h.sub.1, . . . , h.sub.m, where m = n r .times.
.times. as .times. .times. follows .times. : g 1 = H
.function. ( IV 0 , M n ) g 2 = H .function. ( IV 0
, M n  1 ) g r = H .function. ( IV 0 , M n 
( r  1 ) ) h 1 = H .function. ( IV 0 , g 1 ,
.times. , g r ) g r + 1 = H .function. ( IV 0 ,
M n  r ) g r + 2 = H .function. ( IV 0 , M n  (
r + 1 ) ) g 2 .times. r = H .function. ( IV 0
, M n  ( 2 .times. r  1 ) ) h 2 = H .function. (
h 1 , g r + 1 , .times. , g 2 .times. r )
g r .times. n r  r + 1 = H .function. ( IV 0 , M n 
( r .times. n r  r ) ) g r .times. n r 
r + 2 = H .function. ( IV 0 , M n  ( r .times. n r 
r + 1 ) ) g r .times. n r = H .function. (
IV 0 , M n  ( r .times. n r  1 ) ) h m  1
= H .function. ( h m  2 , g r .times. n r  r + 1 ,
.times. , g r .times. n r ) g r .times. n r
+ 1 = H .function. ( IV 0 , M n  ( r .times. n r )
) g n = H .function. ( IV 0 , M 1 ) h
m = H .function. ( h m  1 , g r .times. n r + 1 ,
.times. , g n ) ( 5 )
[0088] Similarly to the scheme of the first embodiment, in the process of
computing h.sub.1, . . . , h.sub.m, the scheme of the second embodiment
computes auxiliary hash values g.sub.1, . . . , g.sub.n which are not
sent. The initial sender transmits (M, .sigma..sub.Sk(h.sub.m)), and the
value of IV.sub.0 can be used as the IV for the computation of all the
g.sub.i values.
[0089] Alternatively, the sender may decide to transmit the hash value
h.sub.i along with every rth message block
(M.sub.1,.sigma..sub.Sk(h.sub.m)),(M.sub.2), . . . ,(M.sub.r,
h.sub.m1),(M.sub.r+1), . . . , (M.sub.2r,h.sub.m2), . . .
(M.sub.n,h.sub.0).
2.2 Signature Update
[0090] Now, suppose an intermediate node wants to strip off nk
arbitrarily located message blocks. It generates a resulting "message"
M', identical to M but where nk blocks have been removed. The receiver
needs to be able to authenticate M'.
[0091] Given the received nblock message M, the intermediate node
computes "new" blocks M'.sub.1, . . . , M'.sub.n. For each message block
M.sub.ni+1 (starting from the end, i=1 to i=n), it computes the
corresponding auxiliary and partial hashes g.sub.i=H(IV.sub.0,
M.sub.ni+1) (6)
[0092] Depending on whether the block will be forwarded or dropped, the
intermediate node computes M'.sub.ni+1=M.sub.ni+1, if block M.sub.i is
forwarded, or g.sub.i, if block M.sub.i is dropped (7)
[0093] The hash values h.sub.m, . . . , h.sub.1 are computed as in the
signing operation. The intermediary finally transmits M.sub.1' . . .
M.sub.n'k,.sigma..sub.Sk(h.sub.m).
[0094] The above transmission requires buffering r packets to perform
verification. In practice r will be quite small. For a SHA1 based scheme
r=3 and for an MD5 based scheme, r=4.
[0095] Alternatively, the intermediary may transmit the hash values hi
along with the "new" message blocks
(M.sub.1',.sigma..sub.Sk(h.sub.m)),(M.sub.2'), . . . ,(M.sub.r',
h.sub.m1),(M.sub.r+1'), . . . , (M.sub.2r',h.sub.m2), . . . ,
(M.sub.n',h.sub.0).
2.3 Verification
[0096] The receiver can verify the signature by computing h.sub.m from
M'.sub.1, . . . , M'.sub.n as follows. First, for each message block
M'.sub.ni+1 (starting from the end, i=1 to i=n), and depending on
whether the received block is a "message block" or a "hash", the receiver
computes g'.sub.i=H(h.sub.i1,M'.sub.ni+1), if M'.sub.ni+1 is a
"message block" M'.sub.ni+1, if M'.sub.ni+1 is a "hash" (8)
[0097] Finally, the receiver computes h.sub.m: h 1 = H .times.
.times. ( IV 0 , g 1 ' , .times. , g r ' ) h 2
= H .times. .times. ( h 1 , g r + 1 ' , .times. , g 2
.times. r ' ) h m = H .times. .times. ( h m 
1 , g r .times. .times. n r + 1 , .times. , g n
) ( 9 )
[0098] The receiver can then verify the signature on h.sub.m as normal
using the verification algorithm v.
[0099] To perform online verification, the receiver needs to be able to
compute the intermediate hash h.sub.i. To do so, the receiver needs to
buffer r blocks so it can compute the appropriate g values. The online
verification of this scheme is analogous to that of the first embodiment.
2.4 Security
[0100] Similarly to the first embodiment, so long as the signature scheme
is not easily susceptible to forgery and the hash function is not easily
susceptible to collisions, the scheme of the second embodiment is secure.
2.5 Performance
[0101] Similarly to the first embodiment, when the intermediary removes
blocks, it only needs to compute the hash of the block being removed.
[0102] It takes less time for the subsequence scheme of the second
embodiment to both compute and verify the signature compared to the
subsequence scheme of the first embodiment, since only one secondlayer
hash is performed for every r first layer hashes. If r is chosen
carefully (for example, setting r=3 for SHA1 or r=4 for MD5), then each
secondlayer hash only requires a single call to the compression
function. So, in the second embodiment, only n r compression
function calls are made in the second layer compared to the n calls in
the first embodiment.
[0103] In addition to the advantages of the first embodiment, the receiver
of the second embodiment can verify the authentication information after
receiving every r blocks. In practice, r will be fairly smallon the
order of 2 or 3, thus reducing the number of the second layer hashes.
3. Simulcast Authentication: the Multiplex Scheme
[0104] Now, assume the original sender S transmits k different streams
M.sup.(1), M.sup.(2), . . . , M.sup.(k) simultaneously. Each stream
consists of n blocks of length b, M.sup.(j)=M.sub.1.sup.(j), . . . ,
M.sup.n.sup.(j). The scheme of the third embodiment allows the
intermediate node not only to select one stream and retransmit it in an
authenticated fashion, but also to "switch" to some other stream
adaptively (at any point during block transmission). Of course, the
receiver should be able to authenticate the resulting stream.
3.1 Signing
[0105] FIG. 9 shows a basic linear simulcast authentication scheme
according to one embodiment of the present invention. Given a message M,
signature generation follows the same approach as in the first and second
embodiments, i.e., reverse iterated hash, but computing partial hashes of
every block in each stream.
[0106] Given messages M.sup.(1), M.sup.(2), . . . , M.sup.(k), where
M.sup.(j)=M.sub.1.sup.(j), M.sub.2.sup.(j), . . . , M.sub.n.sup.(j), the
scheme of the third embodiment of the present invention generates the
partial hash computations h.sub.1, . . . , h.sub.n as follows: d
1 ( 1 ) = H .times. .times. ( M n ( 1 ) ) d 1 ( 2
) = H .times. .times. ( M n ( 2 ) ) d 1 ( k )
= H .times. .times. ( M n ( k ) ) h 1 = H .times.
.times. ( h 0 , d 1 ( 1 ) , .times. , d 1 ( k ) )
d n ( 1 ) = H .times. .times. ( M 1 ( 1 ) )
d n ( 2 ) = H .times. .times. ( M 1 ( 2 ) )
d n ( k ) = H .times. .times. ( M 1 ( k ) ) h n =
H .times. .times. ( h n  1 , d n ( 1 ) , .times. , d
n ( k ) ) ( 10 ) . d.sub.n.sup.(1)=H(M.sub.1.sup.(1))
d.sub.n.sup.(2)=H(M.sub.1.sup.(2)) . . .
d.sub.n.sup.(k)=H(M.sub.1.sup.(k)) h.sub.n=H(h.sub.n1,d.sub.n.sup.(1), .
. . ,d.sub.n.sup.(k)) (10)
[0107] The initial sender transmits .sigma..sub.Sk(h.sub.n) and then sends
M.sup.(1), . . . , M.sup.(k) simultaneously. In practice, the message
blocks of the different streams will be interleaved in the transmission.
3.2 Signature Update
[0108] Suppose an intermediate node wants to select a possibly different
stream (message) for each message block received. For instance, if each
message encodes a video stream of different quality, the intermediate
node may want to select a lower or higher quality depending on network
congestion. It generates a "resulting message" M', comprising "chunks"
(consecutive message blocks) of the different streams. The intermediate
node may pick a single stream (message) at each moment. It should be
understood that the present invention allows for the possibility of
layered streams. The receiver needs to be able to authenticate M'.
[0109] Given the received nblock messages M.sup.(1), . . . , M.sup.(k),
the intermediate node computes "new" blocks M'.sub.1, . . . , M'.sub.n.
For each set of message blocks M.sub.ni+1.sup.(1), . . . ,
M.sub.ni+1.sup.(k), (starting from the end, i=1 to i=n), it computes the
partial hashes d i ( 1 ) = H .times. .times. ( M n 
i + 1 ( 1 ) ) d i ( 2 ) = H .times. .times. ( M n
 i + 1 ( 2 ) ) d i ( k ) = H .times. .times.
( M n  i + 1 ( k ) ) h i = H .times. .times. ( h
i  1 , d i ( 1 ) , .times. , d i ( k ) ) ( 11
)
[0110] Then if stream l is chosen, 1.ltoreq.l.ltoreq.k, it computes
M'.sub.ni+1=(d.sub.i.sup.(1), . . .
,d.sub.i.sup.l1),M.sub.ni+1.sup.(l),d.sub.i.sup.(l+1), . . .
,d.sub.i.sup.(k)). (12)
[0111] The intermediate node finally transmits M'.sub.1 . . .
M'.sub.n,.sigma..sub.Sk(h.sub.n).
[0112] Alternatively, to enable online verification, the intermediate
node transmits
(M'.sub.1,h.sub.n1,.sigma..sub.Sk(h.sub.n)),(M'.sub.2,h.sub.n2), . . .
, (M'.sub.n,h.sub.0) (13) 3.3 Verification
[0113] The receiver can verify the signature by computing h.sub.n, from
M'.sub.1, . . . , M'.sub.k and h.sub.0=IV.sub.0. For each message block
M'.sub.ni+1 (starting from the end, i=1 to i=n) if M'.sub.ni+1 is of
the form M'.sub.ni+1=(d.sub.i.sup.(1), . . .
,d.sub.i.sup.(l1),M.sub.ni+1.sup.(l),d.sub.i.sup.(l+1), . . .
,d.sub.i.sup.(k))
[0114] then, the receiver computes d.sub.i.sup.(k)=H(M.sub.ni+1.sup.(k))
h.sub.i=H(h.sub.i1,d.sub.i.sup.(1), . . .
,d.sub.i.sup.(l1),d.sub.i,d.sub.i.sup.(l+1), . . . ,d.sub.i.sup.(k))
(14)
[0115] The receiver can then verify the signature on h.sub.n as normal
using the verification algorithm v.
[0116] The alternative online verification procedure is straightforward.
The receiver computes the partial hash h.sub.n from (M'.sub.1, h.sub.n1)
using relation (14) and then it verifies the signature on the partial
hash h.sub.n. Afterwards, for i=2, . . . , n, it computes the partial
hash h.sub.i from (M'.sub.i, h.sub.ni) using (14) and verifies the so
computed hash matches the hash value received in iteration i1.
3.4 Performance
[0117] In addition to the advantages of the scheme of the first
embodiment, the hash step of the scheme of the third embodiment can be
iterated using a compression function with either the linear chaining
scheme or a Merkle scheme.
[0118] By using a Merkle treelike construction to hash down each sequence
of blocks M.sub.i.sup.(1), . . . , M.sub.i.sup.(k), bandwidth can be
saved at the cost of more intensive computation (by the intermediate
node).
4. Tree Scheme for Subsequence Authentication
[0119] The fourth embodiment of the present invention is a scheme for
authenticating subsequences using Merkle Trees. Like the linear
subsequence authentication scheme, the treebased scheme allows stream
authentication even when arbitrary blocks from the message are removed.
As long as the blocks sent by the intermediate node are a proper
subsequence of the original message, the receiver can authenticate the
stream. By exploiting certain aspects of the tree structure, the tree
scheme is more efficient with respect to bandwidth than the linear
scheme.
4.1 Signing
[0120] FIG. 10 illustrates a treebased subsequence authentication scheme
according to one embodiment of the present invention. Given a message
M=M.sub.1M.sub.2 . . . M.sub.n, the scheme of the fourth embodiment
generates a Merkle tree shown in FIG. 6. If v denotes the root of the
tree and x denotes the value associated with the root, then the initial
sender transmits (M, .sigma..sub.Sk(x)).
4.2 Signature Update
[0121] If an intermediary wants to strip off k arbitrarily located message
blocks, the intermediary generates a resulting "message" M', identical to
M, but with k blocks removed. The receiver needs to be able to
authenticate M'. Let d.sub.1, . . . , d.sub.k denote the indices of the
blocks that will be dropped and let s.sub.1, . . . , s.sub.nk denote the
blocks that will stay. Given the received nblock message M, the
intermediate node computes the corresponding authentication information
as follows.
[0122] 1) For all blocks M.sub.d.sub.1, . . . , M.sub.d.sub.k that are to
be dropped, the intermediary first determines the set of vertices
corresponding to leaves l.sub.d.sub.1, . . . l.sub.d.sub.k in the Merkle
tree associated with these blocks.
[0123] 2) If any pair of vertices are siblings in the Merkle tree, the
intermediary replaces these two vertices both with their parent.
[0124] 3) The intermediary keeps repeating the above process until no two
vertices in the set are siblings.
[0125] 4) The intermediary takes this set of vertices, and computes the
Merkle tree values x.sub.1, . . . , x.sub.r associated with them. The
intermediary can easily perform this step since the
[0126] fifth and sixth switches (405, 406) connected between the first
terminal
[0127] The intermediate node finally transmits M.sub.s.sub.1 . . .
M.sub.s.sub.nk,.sigma..sub.Sk(x),x.sub.1, . . . x.sub.r (15)
[0128] Similarly to other embodiments of the present invention, applying
standard encoding to the block contents facilitates distinguishing
between "message blocks" and "hashes".
4.3 Verification
[0129] The receiver verifies the signature by computing the value of the
root of the Merkle tree, using the following algorithm:
[0130] 1) For every actual message block M.sub.s.sub.i received, compute
the value y.sub.i=H(IV.sub.0,M.sub.s.sub.i).
[0131] 2) Consider the set of all hashes y.sub.1, . . . , y.sub.nk,
x.sub.1, . . . , x.sub.r. Each of these corresponds to values of vertices
in a Merkle tree.
[0132] 3) For each pair of values, if they correspond to vertices who are
siblings, then replace the pair with their hash (which corresponds to the
parent node).
[0133] 4) Repeat the above step until only one value remainsthis value
is the root.
[0134] If one has all the initial message blocks, then the above algorithm
constitutes the standard algorithm for computing the root of a Merkle
tree. Whenever the receiver receives some hashes x.sub.1, . . . ,
x.sub.r, these come from the intermediary running the same algorithm on
the subset of missing blocks. Therefore, the intermediary and receiver
have together run the algorithm on all n blocks which yield the value of
the Merkle root. This is why the above computation yields the Merkle
root.
[0135] With the value of the Merkle root, the receiver can verify the
signature it receives.
4.4 Security
[0136] The Merkle hash construction is collision resistant so long as the
underlying hash function H is collision resistant. In particular, if one
finds a collision in the Merkle tree, then at some point there is a
collision at an internal node, which means one can find a collision on
the hash function H. If an adversary can come up with a nonsubsequence
forgery (that is, come up with a message/signature pair that is not
obtained by merely taking a subsequence of the original message), then
one can demonstrate either a collision in the hash function or a forgery
on the underlying signature scheme. Therefore, as long as the signature
scheme is not easily susceptible to forgery and the hash function is not
easily susceptible to collisions, the scheme of the fourth embodiment is
secure.
4.5 Performance
[0137] When the intermediary removes blocks, it needs to provide the
receiver with a sufficient number of internal hashes to compute the
Merkle root of the tree without those message blocks. The intermediary
will require k hashes for each of the blocks to be dropped and then at
most k1 hashes when replacing pairs of hashes with a single hash (since
a single hash results in replacing two values with a single one, thereby
reducing the net number by one). The total computation is therefore at
most 2k1 hashes. The total hashes computed by a single common switch
(the number of switching elements is 12) to be shared.
[0138] When the receiver receives the stream, it needs to compute the
root. If it has all the message blocks, this would require 2n1 hashesn
to initially hash each block, and then n1 additional hashes when
replacing pairs of hash values with a single hash (since a single
function computation results in replacing two values with a single one,
and at the end only one value is remaining). However, t of these hashes
are computed by the intermediary. Therefore the receiver only has to
compute 2n1t hashes.
[0139] The total work in this scheme between the intermediary and the
receiver is at most 2n1 hashes. In the previous linear schemes 2n hashes
were required.
[0140] In terms of bandwidth, the tree based scheme may be much more
efficient. Only r.ltoreq.k hashes are finally sent. In the best case, if
all k blocks to be dropped entirely constitute all leaves of a subtree in
the Merkle tree, then only the single value corresponding to the root of
this subtree is sent, that is r=1. In the worst case, if no pair of
blocks are siblings, then the bandwidth requirements are the exact same
as in the linear case, and k hash values need to be sent.
5. Tree Scheme for Simulcast Authentication
[0141] The fifth embodiment of the present invention is a treebased
scheme for authenticating multiple parallel streams in which one data
block is selected from one stream at each step of the transmission. As in
the linear multiplex setting of the third embodiment, it is assumed that
the original sender S transmits k different streams M.sup.(1), M.sup.(2),
. . . , M.sup.(k) simultaneously. Each stream consists of n blocks of
length b, M.sup.(j)=M.sub.I.sup.(j), . . . , M.sup.n.sup.(j). This scheme
allows the intermediate node not only to select one stream and retransmit
it in an authenticated fashion, but also to "switch" to some other stream
adaptively (at any point during block transmission). Of course, the
receiver is able to authenticate the resulting stream. As in the
treebased scheme for subsequence authentication of the fourth
embodiment, the scheme of the fifth embodiment exploits certain aspects
of the tree structure, so as to be more efficient with respect to
bandwidth than the analogous linear scheme. On the other hand, like the
tree construct of the fourth embodiment, the scheme of the fifth
embodiment does not readily lend itself to online verification. Instead,
the receiver has to wait for all packets before it can verify. In
practice, the delay can be reduced by splitting the stream into segments
of reasonable size and authenticating each segment separately.
5.1 Signing
[0142] Given k different streams M.sup.(1), M.sup.(2), . . . , M.sup.(k),
the signature generation of the scheme of the fifth embodiment works as
follows.
[0143] 1) The signer first generates a separate Merkle tree for each
stream. Let v.sup.(1), . . . , v.sup.(k) denote the k roots of the tree,
and let x.sup.(1), . . . , x.sup.(k) denote the respective values
associated with these roots.
[0144] 2) The signer then computes x=H(IV, x.sup.(1), . . . , x.sup.(k)).
Here the hash function H can be computed using a Merkle tree construction
as well.
[0145] 3) Finally, the signer transmits (M, .sigma..sub.Sk(x)).
5.2 Signature Update
[0146] Now, suppose an intermediate node wants to select a possibly
different stream (message) for each message block received. For instance,
if each message encodes a video stream of different quality, the
intermediate node may want to select a lower or higher quality depending
on network congestion. It generates a resulting "message" M', comprising
"chunks" (consecutive message blocks) of the different streams. The
receiver needs to be able to authenticate M'.
[0147] If the receiver can accurately compute each of the x.sub.i values,
then it can verify the signature. Therefore, the intermediary simply has
to provide the user with the information necessary to compute these
values. By treating each Merkle tree separately, the intermediary can
compute the set of required values as it did in the Merkle scheme of the
fourth embodiment. The intermediary transmits these values to the
receiver which can then compute the x.sub.i values and inturn verify the
authentication information.
[0148] Specifically, for each i with 1.ltoreq.i.ltoreq.k, let ks(i) denote
the number of blocks that will actually be sent from stream M.sup.(i).
For the stream M.sup.(i), let s.sub.1.sup.(i), . . . ,
s.sub.ks(i).sup.(i) denote the indices of the blocks that will be
included. Let M'.sup.(i) denote these blocks: M ' .function. ( i
) = M s 1 .function. ( i ) ( i ) .times. .times.
.times. M s ks .function. ( i ) ( i ) ( i ) ( 16 )
[0149] As to the indices of blocks that are to be dropped, for each i with
1.ltoreq.i.ltoreq.k, let kd(i) denote the number of blocks that will
actually be dropped from stream M.sup.(i). For the stream M.sup.(i), let
d.sub.1.sup.(i), . . . , d.sub.kd(i).sup.(i) denote the indices of the
blocks that will be dropped.
[0150] As in the tree scheme of the fourth embodiment, for each stream
M.sup.(i) the intermediary computes the values necessary for the receiver
to verify as follows:
[0151] 1) For all blocks M d 1 ( i ) ( i ) , .times. , M
d k ( i ) ( i ) that are to be dropped, the intermediary first
determines the set of vertices corresponding to leaves l d 1 ( i )
, .times. , l d kd .function. ( i ) ( i ) in the Merkle
tree associated with these blocks.
[0152] 2) Now, if any pair of vertices are siblings in the Merkle tree,
the intermediary replaces these two vertices both with their parent,
i.e., the hash of concatenation of the values associated with the
siblings.
[0153] 3) The intermediary keeps repeating the above process until no two
vertices in the set are siblings.
[0154] 4) The intermediary takes this set of vertices, and computes the
Merkle tree values X.sup.(i)=x.sub.1.sup.(i), . . . , x.sub.r.sup.(i)
associated with them. The intermediary can easily perform this step since
the cryptographic hash function is globally computable.
[0155] The intermediate node finally transmits the following information:
{M'.sup.(1), . . . , M'.sup.(n)}, .sigma..sub.Sk (x), X.sup.(1), . . . ,
X.sup.(k) (17)
[0156] The stream is sent in the proper order, that is, blocks from each
of the M'.sup.(i) may be interleaved so that the receiver can view the
stream. Some standard encoding is applied to the block contents so the
receiver can distinguish between message blocks versus hash values.
5.3 Verification
[0157] The receiver verifies the signature by first computing the values
of the roots of each of the Merkle treesafter that it hashes these
values and verifies the signature. It achieves this goal using the
following algorithm which is run for each i:
[0158] 1) First, for every actual message block M.sub.sj.sup.(i) received,
the receiver computes the value
y.sub.j.sup.(i)=H(IV.sub.0,M.sub.sj.sup.(i)).
[0159] 2) Consider the set of all hashes computed above in the previous
step as well the hash values contained in sets X.sup.(1), . . . ,
X.sup.(k) received in the transmissions.
[0160] 3) For each pair of values, if the pair corresponds to vertices who
are siblings, then replace the pair with their hash (which corresponds to
the parent node in the Merkle tree).
[0161] 4) Repeat the above step until only one value remainsthis value
is the root x.sup.(i).
[0162] If one has all the initial message blocks, then the above algorithm
constitutes the standard algorithm for computing the root of a Merkle
tree. Whenever the receiver receives some hashes x.sub.1.sup.(i), . . . ,
x.sub.r.sup.(i), these come from the intermediary running the same
algorithm on the subset of missing blocks. Therefore, the intermediary
and receiver have together run the algorithm on all n blocks which yield
the value of the Merkle root. This is why the above computation yields
the Merkle root.
[0163] With the values of the Merkle roots, x.sup.(1), . . . , x.sup.(k),
the receiver can compute x=H(IV, x.sup.(1), . . . , x.sup.(k)) and verify
the signature it receives.
[0164] FIG. 11 illustrates the signing and verification of the fifth
embodiment of the invention, an example with four streams and four
message blocks. As shown, each of the four streams M.sup.(1), M.sup.(2),
M.sup.(3), M.sup.(4) consists of four blocks. The black leaves denote the
message blocks that are actually sent. The remaining ones are dropped.
The shaded vertices represent the cover; that is, the values
corresponding to these vertices are sent to the receiver. The roots of
the four Merkle trees are x.sup.(1), x.sup.(2), x.sup.(3), and x.sup.(4)
respectively. The final root value x is computed by hashing the Merkle
roots x.sup.(1), x.sup.(2), x.sup.(3), x.sup.(4). This hash can be also
be performed in a Merklelike fashion. Finally, the value x is actually
signed. In this scheme only six hash values are sent to the receiver. In
the linear simulcast scheme, twelve hashes (three per each block
transmitted) would have been transmitted. Thus, savings is achieved
whenever dropped blocks are clustered. For example, in FIG. 11, all
blocks in the stream M.sup.(4) are dropped. As a result, one only needs
to send the root x.sup.(4) of the associated Merkle tree.
[0165] Also, because the Merkle roots are themselves hashed in a
Merklelike construction, there is room for further optimization. In
particular, suppose that all blocks are dropped for two entire subtrees
whose Merkle roots are siblings in the even larger tree. Then, instead of
sending the two Merkle roots, their hash could be sent.
5.4 Security
[0166] Similarly to the fourth embodiment, the fifth embodiment is secure
as long as the signature scheme is not easily susceptible to forgery, and
the hash function is not easily susceptible to collisions. Thus the
invention presented above is secure.
5.5 Performance
[0167] The performance of the fifth embodiment can be analyzed by
extending the analysis for the treebased subsequence scheme and the
linear simulcast scheme.
[0168] In all embodiments above, a hash function with a specific payload
size and a specific IV is used. The chaining constructions tend to take
some existing output and use that as the IV of the next block. In a
further embodiment, instead of loading the current output as an IV, the
current output can be concatenated to the next payload.
[0169] The linear and tree schemes of the present invention can be
combined to obtain hybrid solutions, giving rise to useful tradeoffs. In
a further embodiment, a scheme starts by splitting each stream M.sup.(i)
into segments of length b blocks. Then, a tree scheme is applied on the
first segment of all streams to compute the Merkle root x.sub.1, then the
root on the second segment, and so on, until all segments are processed.
In this way, Merkle roots x.sub.1, . . . , x.sub..left brktbot.n/b.right
brktbot. are obtained. Instead of signing each one of these roots, as in
the tree schemes described above, the roots are combined using the linear
scheme. Hence, if the receiver can buffer b blocks, then verification can
be done "online". Moreover, the communication overhead is decreased
compared to the plain linear scheme since for each segment of b blocks,
the number of transmitted hashes may be much less than the number of
dropped blocks (although equal on the worst case). A similar approach can
be taken for subsequence authentication. This hybrid approach allows
trading buffer space for communication overhead.
[0170] In a further embodiment, a linear scheme is applied to each stream,
and then a Merkle tree is computed on the results.
[0171] Although the embodiments described above use binary Merkle trees,
the constructions can be applied to general trees. It may be more
advantageous to group certain blocks together if they have similar
behavior; i.e., they either all will be dropped or all will be kept.
[0172] If there are correlations among blocks, then it makes sense to
cluster these blocks together in the treebased schemes. For example, if
a group of blocks will either all be dropped or all be kept, it is
advantageous to have these blocks constitute all the leaves of a subtree.
Then, if the packets are dropped, only the root of the subtree must be
sent.
[0173] In addition, the Merkle tree construction could be optimized. In
one embodiment, if one of the streams will more likely be used than the
others, it is advantageous to use a lopsided Merkle tree in which the
priority stream is close to the root (e.g., perhaps right below it). In
conjunction with the hybrid scheme mentioned previously, the streams are
prioritized, so that the high priority streams are closer to the final
value in the chain. This ordering particularly makes sense when layered
streams are used. In such cases, the voltage difference between V(T1) and
V(,, 2) to 2:1.
[0174] There are blocks that should never be dropped, such as, an I frame
in an MPEG stream, or the base layer in a scalably coded stream. The
signer can avoid directly computing the initial firstlayer hash on a
block that will not be dropped. In the linear schemes, there are two hash
layers. If a block will not be dropped, then there is no need to compute
the hash in the first layer; instead only the second layer needs to be
computed.
[0175] The schemes of the present invention can be interpreted as having
two phases. In the first phase, it finds a convenient way to hash each
data block. In the second phase, it signs the hashes. The reason for
doing so is that if a block is dropped, it is not necessary to retransmit
it in its entirety. Instead, only the hash computed in the first phase is
transmitted. This information is sufficient to allow the receiver to
verify, since the signature can be viewed as being performed on the
hashes. dividing the voltage difference between V(T1) and V(,, 2) to 2:1.
In FIG. 6, the is, the sender drops particular blocks on purpose. Of
course, in many practical applications, one may have to deal with
uncontrolled loss situations. These situations may occur, for example, if
the transport protocol is not reliable such as the case with UDP, or if
the environment is subject to lossy behavior such as is the case with
wireless networks. The present invention can be used to deal with the
uncontrolled loss by replicating the hashes that would be sent if the
packet were dropped.
[0176] By applying Forward Error Correction (FEC) techniques such as
Erasure Codes to the hashes of the present invention, it is possible to
deal with the uncontrolled loss situation without having to replicate.
This approach might be especially useful in a multicast setting where
different receivers have lost different packets but can be provided with
identical errorcorrecting information. One consideration of this
approach is that the receiver must perform a decoding step so may have to
compromise the ability to verify authentication information in an online
manner.
[0177] Moreover, schemes of the present invention involve an intermediary
which can adaptively choose the amount of forward error correction to the
authentication information (i.e., hash outputs). In other words, rather
than having a source estimate how much loss will occur and include
sufficient authentication forward error correction information to
accommodate that, the source can choose not to include authentication
forward error correction information at all, and instead allow an
intermediary to include the authentication forward error correction
information dynamically to further increase the probability that the
stream can be authenticated.
[0178] The intermediary becomes an integral part of a scheme which
considers both uncontrolled losses handled through forward error
correction as well as adaptive and intelligent controlled losses. For
example, in the Merkle tree constructions, it may suffice for the
recipient to recover intermediate nodes (as opposed to just leaf nodes).
In such a case, the intermediary can choose to supply forward error
correction information to allow recovery of the (possibly interior) nodes
necessary to authenticate, thus requiring possibly less forward error
correction information.
[0179] If the intermediary is sending different versions of the same
stream to multiple receivers, because, for example, each has a different
resource constraint with respect to the quality they view, the
intermediary can recycle the work effort. In particular, the between the
terminals T1, T2 and adapted to receive as input data bit signals D1B,
most one full set of firstlayer hashes.
[0180] Along these lines, work can be recycled between the source and the
intermediary. That is, the source can provide the intermediary with any
necessary hash computations for assisting with authentication. Then, the
intermediary is not required to perform any work of a cryptographic
nature. Instead, it can choose which blocks to drop and select the
corresponding authentication information to be transmitted.
[0181] Another application of the present invention is insertion and
selection of advertisements in a stream. The intermediary or some other
party provides advertisements or a hash of advertisements, for example
hashed using a Merkle tree, to the source. The source then includes the
Merkle hash in its stream as a placeholder, allowing the intermediary to
choose which advertisement it would like to use. Of course, this concept
is not necessarily limited to advertisers.
[0182] Although the focus of the present invention is on authenticating
information, the above scheme can also be used in conjunction with an
encryption scheme provided that the scheme is designed to permit the
recipient to decrypt a given block without requiring the decryption of or
presence of many other blocks. Two block cipher encryption modes
facilitate this approach. One is countermode encryption and the other is
electronic code book (ECB) encryption. Alternatively, it is possible to
use a stream cipher, though a caveat is that the receiver may need to
perform work that is proportional to the size of the original stream as
opposed to the portion of it that he receives. One may be able to use
chaining or feedback modes (cipher block chaining (CBC), output feed back
(OFB), etc) provided that the receiver receives any intermediate
information to decrypt. Such information may include intermediate IVs or
actual ciphertext blocks. Yet another approach is to mix the modes, i.e.,
for large segments which will not be dropped, a chaining or feedback mode
can be used; whereas for other blocks, a counter mode or ECB mode can be
used. For example, in an MPEG stream, Iframes are never dropped
intentionally, so they can be treated differently and encrypted using CBC
mode. A similar remark applies to the base layer of any scalable coding
scheme.
[0183] While the invention has been described in detail above with respect
to various embodiments, the ordinarily skilled artisan will appreciate
that variations of these embodiments are possible without departing from
the scope and spirit of the invention. Therefore, the invention should be
considered as limited only by the scope of the appended claims.
* * * * *