Cuculus

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.