Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1999-10-20
2001-10-30
Barron, Jr., Gilberto (Department: 2131)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C713S176000, C713S181000, C370S522000, C380S030000, C380S037000
Reexamination Certificate
active
06311271
ABSTRACT:
TECHNICAL FIELD
This invention describes a method of signing and authenticating a stream of data using a reduced number of digital signatures.
DESCRIPTION OF THE PRIOR ART
Several prior art solutions have been envisioned to solve the problem of stream signing and are actually proposed to be used in practice.
One solution splits the stream in blocks. The sender signs each individual block and the receiver loads an entire block and verifies its signature before consuming it. This solution also works if the stream is infinite. However this solution forces the sender to generate a signature for each block of the stream and the receiver to verify a signature for each block. With today's signature schemes either one or both of these operations can be very expensive computationally, which in turns means that the operations of signing and verifying can create a bottleneck to the transmission rate of the stream.
Another type of solution works only for finite streams. In this case, once again the stream is split into blocks. Instead of signing each block, the sender creates a table listing cryptographic hashes of each of the blocks. Then the sender signs this table. When the receiver asks for the authenticated stream, the sender first sends the signed table followed by the stream. The receiver first receives and stores this table and verifies the signature on it. If the signature matches then the receiver has the cryptographic hash of each of the following stream blocks. Thus each block can be verified when it arrives. The problem with the foregoing solution is that it requires the storage and maintenance of a potentially very large table on the receiver's end. In many realistic scenarios the receiver buffer is very limited as compared to the size of the stream. E.g. in MPEG a typical movie may be 20 GBytes whereas the receiver buffer is only required to be around 250 Kbytes. Therefore the hash table can itself become fairly large (e.g., 50000 entries in this case or 800 Kbytes for the MD5 hash function). The hash table itself has to be stored and this may not be possible. Secondly the hash table itself needs to be transmitted first and if it is too large then there will be a significant delay before the first piece to the stream is received and consumed.
The above solution can be modified by using an authentication tree: the blocks are placed as the leaves of a binary tree and each internal node takes as a value the hash of its children (see [3]). This way the sender needs to sign and send only the root of this tree. However in order to authenticate each following block the sender has to send the whole authentication path (i.e. the nodes on the path from the root to the block, plus their siblings) to the receiver. This means that if the stream has k blocks, the authentication information associated with each block will be O(log k) in size.
It is an objective of the present invention to eliminate all these shortcomings whereby the invention works for both infinite and finite streams, only one expensive digital signature is ever computed, there are no big tables to store, and the size of the authentication information associated with each block does not depend on the size of the stream.
Some of the ideas involved in the solution for unknown streams have appeared previously, although in different contexts and with different usages.
Mixing “regular” signatures with 1-time signatures, for the purpose of improving efficiency is discussed in [4]. However the focus of that invention was to make the signing operation of a message M efficient by dividing such operation in two parts. An off-line part in which the signer signs a 1-time public key with his long-lived secret key even before the messages M is known. Then when M has to be sent the signer computes a 1-time signature of M with the authenticated 1-time public key and sends out M tagged with the 1-time public key and the two signatures. Notice that the receiver must compute two signature verifications: one against the long-lived key to authenticate the 1-time key associated to M, and one against such 1-time key to authenticate M itself. In our scheme we need to make both signing and verification extremely fast, and indeed in our case each block (except for the first) is signed (and hence verified) only once with a 1-time key. The first is signed and verified only once with a long-lived key.
Old 1-time keys are used in order to authenticate new 1-time keys. This has appeared in several places but always for long-lived keys. Examples include [5,6,7] where this technique is used to build provably secure signature schemes. We stress that the results in [5,6,7] are mostly of theoretical interest and do not yield practical schemes. Our on-line solution somehow mixes these two ideas in a novel way, by using the chaining technique with 1-time keys, embedding the keys inside the stream flow so that old keys can authenticate at the same time both the new keys and the current stream block.
SUMMARY OF THE INVENTION
It is therefore an object of this invention to reduce computation time necessary to sign and authenticate a stream of data by reducing the number of digital signatures required for one to authenticate the data stream. The foregoing is accomplished without having to resort to storing large portions of the data stream and without maintaining excessively large authentication tables. With this invention, the receiver authenticates the stream without receiving the entire stream. Further the receiver detects corruption of the stream almost immediately after tampering of a portion of the stream. As a consequence, the receiver can consume authenticated data from the stream at the same rate he receives such data from the stream.
The present solution makes some reasonable/practical assumptions about the nature of the streams being authenticated. First of all we assume that it is possible for the sender to embed authentication information in the stream. This is usually the case (e.g., USER DATA section in MPEG video elementary stream etc.) We also assume that the receiver has a “small” buffer in which it can first authenticate the received bits before consuming them. Finally we assume that the receiver has processing power or hardware that can compute a small number of fast cryptographic ckecksums faster than the incoming stream rate while still being able to play the stream in real-time.
The basic idea of the present solution is to divide the stream into blocks and embed some authentication information in the stream itself. The authentication information placed in block i will be used to authenticate the following block i+1. This way the signer needs to sign just the first block and then the properties of this single signature will “propagate” to the rest of the stream through the authentication information. Of course the key problem is to perform the authentication of the internal blocks fast.
In the first scenario the stream is finite and is known in its entirety to the signer in advance. This is not a very limiting requirement since it covers most of the internet applications (digital movies, digital sounds, applets). In this case we will show that a single hash computation will suffice to authenticate the internal blocks. The idea is to embed in the current block the hash of the following block (which in turns includes the hash of the following one and so on . . . )
In this first scenario, verification of the find stream is performed by verifying the signature of the first block and subsequently verifying hashes of the following blocks.
The second case is for (potentially infinite) streams which are not known in advance to the signer (for example live feeds, like sports event broadcasting and chat rooms). In this case our solution requires several hash computations to authenticate a block. The idea here is to use fast 1-time signature schemes (introduced in [1,2]) to authenticate the internal blocks. So block i will contain a 1-time public key and also the 1-time signature of itse
Gennaro Rosario
Rohatgi Pankaj
Barron Jr. Gilberto
Cameron Douglas W.
DiLorenzo Anthony
Dougherty Anne Vachon
International Business Machines - Corporation
LandOfFree
How to sign digital streams does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with How to sign digital streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to sign digital streams will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617084