Cryptography Reference
In-Depth Information
The Lamport one-time signature system is illustrated in Figure 15.3. As
mentioned earlier, a PRBG and a seed are typically used to generate the 2
n
values
u
10
,u
11
,u
20
,u
21
,...,u
n
0
,u
n
1
, and a cryptographic hash function
h
is typically
used to compute the public key
p
.
There are several possibilities to generalize and improve the efficiency of
the Lamport one-time signature system. These generalizations and improvements,
however, are beyond the scope of this topic. Neverthelss, it is important to note
that the Lamport one-time signature system and variations thereof are used in many
cryptographic applications. For example, it can be used to protect against the double-
spending problem in anonymous offline digital cash systems (e.g., [17]).
15.5
DIGITAL SIGNATURES FOR STREAMS
Most DSSs in use today are message oriented, meaning that they are used to sign
messages or message blocks and to verify the signatures that are attached to them
accordingly. A problem first addressed by Rosario Gennaro and Pamkaj Rohatgi in
1997 is how one can digitally sign streams
7
[18]. There are several approaches and
corresponding solutions one can find.
•
The simplest approach is to split the digital stream into a sequence of blocks,
to digitally sign each block individually, and to have the recipient verify the
digital signature of each block before he or she consumes it. This approach
works for every stream (even if it is infinitely long). However, it has the
disadvantage that it forces the sender to generate a digital signature and
the recipient to verify a signature for every block in the stream. This is
computationally expensive (for both the sender and the verifier).
•
A less expensive approach can be used if the digital stream that must be
signed is finite and known in advance to the sender. In this case, the sender
can split the stream into a sequence of blocks, create a table that contains a
cryptographic hash value for every block in the stream, and digitally sign the
table. The digital stream is then transmitted with the prepended table to the
recipient. The recipient, in turn, can verify the digital signature for the table,
temporarily store the table in the positive case, and verify the hash value for
every block in the stream with the entry in the table. This apporach has the
7A
digital stream
(or
stream
in short) is a potentially very long (or even infinite) message or sequence
of bits that a sender sends to one (or multiple) recipient(s) and the recipient(s) is (are) required
to consume at more or less the input rate (i.e., without excessive delays). Examples of digital
streams include digitized audio or video files, data feeds, and software modules that are dynamically
downloaded if needed (e.g., Java applets).
