New linking schemes for digital time-stamping.

Abstract

. Binary Linking Schemes #BLS# for digital time-stamping #3# provide #1# relative temporal authentication to be performed in logarithmic time, and #2# time-certi#cates of reasonable size, which together with the data published in a widely available medium enable the veri#er to establish their relative temporal positions, even if the database held by the Time-Stamping Service #TSS# ceases to exist. Weshow that the size of a time-certi#cate ##X# of a document X in the scheme presented in #3# is bounded by4# 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 # #X# # 6 log 2 3 # k # log 2 N and prove that the presented scheme is optimal in that sense. 1 Introduction Time-stamps enable an incredulous veri#er to ascertain the date a digital documentwas created, signed or last modi#ed. Most of the time-stamping systems proposed to date are based on trusted third parties and are, thereby, more or less ...