Linked timestamping

Stuart Haber and W. Scott Stornetta proposed[4] in 1990 to link issued time-stamps together into linear hash-chain, using a collision-resistant hash function. The main rationale was to diminish TSA trust requirements.

Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991[5] and by Bayer, Haber and Stornetta in 1992.[6]

Benaloh and de Mare constructed a one-way accumulator[7] in 1994 and proposed its use in time-stamping. When used for aggregation, one-way accumulator requires only one constant-time computation for round membership verification.

Surety[8] started the first commercial linked timestamping service in January 1995. Linking scheme is described and its security is analyzed in the following article[9] by Haber and Sornetta.

Buldas et al. continued with further optimization[10] and formal analysis of binary tree and threaded tree[11] based schemes.

Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient.[12]

Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera[13] in 2004. There is an explicit upper bound ${\displaystyle N}$ for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task. Considering that all known practically relevant and efficient security proofs are black-box, this negative result is quite strong.

Next, in 2005 it was shown[14] that bounded time-stamping schemes with a trusted audit party (who periodically reviews the list of all time-stamps issued during an aggregation period) can be made universally composable - they remain secure in arbitrary environments (compositions with other protocols and other instances of the time-stamping protocol itself).

Buldas, Laur showed[15] in 2007 that bounded time-stamping schemes are secure in a very strong sense - they satisfy the so-called "knowledge-binding" condition. The security guarantee offered by Buldas, Saarepera in 2004 is improved by diminishing the security loss coefficient from ${\displaystyle N}$ to ${\displaystyle {\sqrt {N}}}$.

The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant[16] or even one-way;[17] secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find collisions for any hash function). This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions.

Hash tree based linking scheme

At the illustration above hash tree based time-stamping system works in rounds (${\displaystyle t}$, ${\displaystyle t+1}$, ${\displaystyle t+2}$, ...), with one aggregation tree per round. Capacity of the system (${\displaystyle N}$) is determined by the tree size (${\displaystyle N=2^{l}}$, where ${\displaystyle l}$ denotes binary tree depth). Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction.