## 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·log_{2} *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/(log_{2} 3)]·*k*·
log_{2} *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·log_{2} *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/(log_{2} 3)]·*k*·
log_{2} *N* and prove that the presented scheme is
optimal in that sense.

© by
Korea Institute of Information Security and Cryptology.