New Linking Schemes for Digital Time-Stamping
Ahto Buldas and Peeter Laud. New linking schemes for
digital time-stamping. In The 1st International Conference on
Information Security and Cryptology, pages 3--14, Seoul, Korea, 18--19
December 1998. Korea Institute of Information Security and Cryptology.
Abstract:
Binary Linking Schemes (BLS) for digital time-stamping [BLLV98]
provide (1) relative temporal authentication to be performed in
logarithmic time, and (2) time-certificates of reasonable size, which
together with the data published in a widely available medium enable the
verifier to establish their relative temporal positions, even if the
database held by the Time-Stamping Service (TSS) ceases to exist. We
show that the size of a time-certificate t(X) of a document X in the scheme
presented in [BLLV98] is bounded by 4·log2 N
where k is the output size of the hash function and N
is the number of time-stamps issued. We then present a new BLS with
t(X)»[6/(log2 3)]·k·
log2 N and prove that the presented scheme is
optimal in that sense. Binary Linking Schemes (BLS) for digital
time-stamping [BLLV98] provide (1) relative temporal authentication to
be performed in logarithmic time, and (2) time-certificates of
reasonable size, which together with the data published in a widely
available medium enable the verifier to establish their relative
temporal positions, even if the database held by the Time-Stamping
Service (TSS) ceases to exist. We show that the size of a
time-certificate t(X) of a document
X in the scheme presented in [BLLV98] is bounded by
4·log2 N where k is the output size of
the hash function and N is the number of time-stamps issued. We
then present a new BLS with t(X)»[6/(log2 3)]·k·
log2 N and prove that the presented scheme is
optimal in that sense.
© by
Korea Institute of Information Security and Cryptology.