Linked timestamping is a type of trusted timestamping where issued time-stamps are related to each other.
Description
Linked timestamping creates time-stamp tokens which are dependent on each other, entangled in some authenticateddata structure. Later modification of the issued time-stamps would invalidate this structure. The temporal order of issued time-stamps is also protected by this data structure, making backdating of the issued time-stamps impossible, even by the issuing server itself. The top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media, like printed newspaper or public blockchain. There are no private keys in use, avoiding PKI-related risks. Suitable candidates for the authenticated data structure include:
The simplest linear hash chain-based time-stamping scheme is illustrated in the following diagram: The linking-based time-stamping authority usually performs the following distinct functions: ;Aggregation ;Linking ;Publishing
Security
Linked timestamping is inherently more secure than the usual, public-key signature based time-stamping. All consequential time-stamps "seal" previously issued ones - hash chain could be built only in one way; modifying issued time-stamps is nearly as hard as finding a preimage for the used cryptographic hash function. Continuity of operation is observable by users; periodic publications in widely witnessed media provide extra transparency. Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design. Absence of secret keys increases system trustworthiness. There are no keys to leak and hash algorithms are considered more future-proof than modular arithmetic based algorithms, e.g. RSA. Linked timestamping scales well - hashing is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations. The common technology for guaranteeing long-term attestation value of the issued time-stamps is periodic over-time-stamping of the time-stamp token. Because of missing key-related risks and of the plausible safety margin of the reasonably chosen hash function this over-time-stamping period of hash-linked token could be an order of magnitude longer than of public-key signed token.
Research
Foundations
Haber and Stornetta proposed 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 and by Bayer, Haber and Stornetta in 1992. Benaloh and de Mare constructed a one-way accumulator 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 started the first commercial linked timestamping service in January 1995. Linking scheme is described and its security is analyzed in the following article by Haber and Sornetta. Buldas et al. continued with further optimization and formal analysis of binary tree and threaded tree based schemes. Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient.
Provable security
Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera in 2004. There is an explicit upper bound 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 that bounded time-stamping schemes with a trusted audit party can be made universally composable - they remain secure in arbitrary environments. Buldas, Laur showed 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 to. The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant or even one-way; secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm. This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions. At the illustration above hash tree based time-stamping system works in rounds, with one aggregation tree per round. Capacity of the system is determined by the tree size. 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.
Standards
part 3 covers 'Mechanisms producing linked tokens'. American National Standard for Financial Services, "Trusted Timestamp Management and Security" from June 2005 covers linking-based and hybrid time-stamping schemes. There is no IETF RFC or standard draft about linking based time-stamping. RFC 4998 encompasses hash tree and time-stamp as an integrity guarantee for long-term archiving.
