Cryptography Reference
In-Depth Information
h
(
m
i−
1+1
)=
h
(
m
i
)). Consequently, the recipient must verify a digital
signature only at the beginning of the stream and a hash value for every
subsequent block. The resulting offline solution is efficient for both the sender
and the recipient.
•
In the online solution, the digital stream
m
is assumed to be (potentially)
infinitely long and the sender does not know the entire stream in advance—
that is,
m
comprises a sequence of blocks (i.e.,
m
=
m
1
,m
2
,m
3
,...
)and
m
comprises another sequence of blocks (i.e.,
m
=
m
0
,m
1
,m
2
,...
). The
basic idea of the online solution is to use a “normal” DSS only to digitally
sign the first block of the stream and to use a fast one-time signature system
to digitally sign all subsequent blocks. More specifically, let (
k, k
−
1
) be the
sender's public key pair of a “normal” DSS and (
k
i
,k
−
i
) be the
i
th
public key
pair of a one-time signature system. The sender then computes the following
sequence of blocks:
m
0
=
k
0
,s
]
m
i
=
m
i
,k
i
,s
i
]for
i
≥
1
The first block
m
0
contains only a verification key
k
0
of a one-time
signature system and a digital signature
s
=
Sign
(
k
−
1
,k
0
) for
k
0
.All
subsequent blocks
m
i
(
i
≥
1) contain
m
i
,
k
i
, and a one-time signature
s
i
=
Sign
(
k
−
1
k
i
)). The resulting stream
m
is sent to the recipient.
On receiving
m
0
=[
k
0
,s
], the recipient verifies that
s
is a valid signature
for
k
0
with respect to the verification key
k
of the sender—that is, he or
she must verify that
Verify
(
k, k
0
,s
) returns
valid
. Afterward, on receiving
m
i
=[
m
i
,k
i
,s
i
], the recipient must verify that
s
i
is a valid one-time signature
for
h
(
m
i
i−
1
,h
(
m
i
k
i
) with respect to the verification key of the previous block (i.e.,
k
i−
1
). Consequently, the recipient has to verify a single digital signature at the
beginning of the stream and then one one-time signature for every subsequent
block of the stream. Again, the resulting online solution is efficient for both the
sender and the recipient. The major disadvantage of the solution is message
expansion, meaning that
m
is considerably larger than
m
(this disadvantage
also applies for the offline solution).
Since the late 1990s, the problem of digitally signing streams has been more
seriously addressed in the research community. The use of streams and stream-
oriented network communication protocols is certainly the driving force behind this
development. It is assumed that digital signatures for streams are becoming more
and more important in the future.
