Cryptography Reference
In-Depth Information
disadvantage (in addition to the fact that it only works for streams that are
finite and known in advance to the sender) that it requires potentially very
large tables to be managed.
•
One can address the table management problem of the previous approach by
using a hybrid scheme, in which the digital stream to be signed is split into
consecutive pieces and each piece is treated individually, meaning that it is
preceded by a small digitally signed table.
•
Another approach is to use a Merkle authentication tree [19] to even more
efficiently authenticate the blocks of a digital stream.
When Gennaro and Rohatgi first addressed the problem of digitally signing
streams [18], they followed a chaining strategy, meaning that the digital stream is
divided into blocks and each block carries some authentication information for the
next block of the stream (i.e., the authentication information of block
i
is used to
authenticate block
i
+1). This way the sender only needs to digitally sign the first
block, and the properties of this signature propagate to the rest of the stream through
the authentication information. Of course, the key problem is then to perform the
authentication of all blocks in a way that is as efficient as possible. Gennaro and
Rohatgi distinguished the following two cases:
•
The digital stream is finitely long, and the sender knows the entire stream in
advance. In this case, Gennaro and Rohatgi proposed a solution that is known
as offline solution.
•
The digital stream is (potentially) infinitely long, and the sender does not know
the entire stream in advance. In this case, Gennaro and Rohatgi proposed a
solution that is known as online solution.
Because digital streams can also be seen as messages (with specific proper-
ties), we use
m
to refer to such a stream. In the descriptions that follow,
m
refers to
the digital stream that must be signed, and
m
refers to the signed stream (i.e.,
m
is
the stream that is actually transmitted to the recipient). Note that
m
and
m
may be
infinitely long, that the blocks of
m
and
m
may not be equally long (the blocks of
m
are typically longer than the blocks of
m
, because they comprise authentication
information), and that an initial block
m
0
must usually be prepended to
m
(such a
block is not present in
m
). Let us overview and briefly discuss the offline and online
solutions of Gennaro and Rohatgi next.
•
In the
offline solution
, the digital stream
m
is assumed to be finitely long and
the entire stream is known to the sender in advance—that is,
m
comprises
k
blocks (i.e.,
m
=
m
1
,m
2
,...,m
k
)and
m
comprises
k
+1blocks (i.e.,
