Home » About us » Research

Research Papers on Timestamping Security

  • On provably secure time-stamping schemes. (Ahto Buldas and Märt Saarepera. In Asiacrypt 2004, LNCS 3329, pp. 500-514, 2004)
    The paper presents a security proof for hash-function based timestamping schemes in which there is an explicit upper bound N for the number of time stamps issued during an aggregation period (1 second in this case). The authors also show that it is probably impossible to prove the security without this explicit bound – the so-called black-box reductions will certainly fail in this task. Considering that all known practically relevant and efficient security proofs are black-box, this negative result is quite strong.
  • Universally composable time-stamping schemes with audit. (Ahto Buldas, Peeter Laud, Märt Saarepera, and Jan Willemson. In ISC 2005, LNCS 3650, pp.359-373, 2005)
    The authors show that bounded timestamping schemes with a trusted audit party (who periodically reviews the list of all timestamps 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).
  • Do broken hash functions affect the security of time-stamping schemes? (Ahto Buldas and Sven Laur. In ACNS 2006, LNCS 3989, pp. 50-65, 2006)
    Does secure time-stamping imply collision-free hash functions? (Ahto Buldas and Aivo Jürgenson. In ProvSec 2007, LNCS 4784, pp.138-150, 2007)
    In these two papers it is shown that the hash functions used in secure timestamping schemes are not necessarily collision-resistant and even one-way (Buldas and Jürgenson) and that secure timestamping 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).
  • Knowledge-binding commitments with applications in time-stamping. (Ahto Buldas and Sven Laur. In PKC 2007, LNCS 4450, pp. 150-165, 2007)
    In this paper it is shown that bounded timestamping schemes are secure in a very strong sense – they satisfy the so-called “knowledge-binding” condition. The authors also improve the security guarantee of the previous security reduction (Buldas and Saarepera) by diminishing the security loss coefficient from N to sqrt(N).

Research Papers on Hash Linking

  • Time-Stamping with binary linking schemes. (Ahto Buldas, Peeter Laud, Helger Lipmaa and Jan Villemson. In Advances in Cryptology – CRYPTO’98, LNCS 1462, 486-501. Springer-Verlag, 1998)
    New linking schemes for digital time-stamping. (Ahto Buldas and Peeter Laud. In Proceedings of The 1st International Conference on Information Security and Cryptology – ICISC’98, 3-14, Seoul, Korea, 1998)
    The Crypto 98 paper introduces the concept of independently verifiable (comparable) time certificates based on binary hash linking. In the second paper a more efficient scheme was then discovered and proven to be optimally efficient (in terms of certificate size) under the assumption that every node of the linkage graph contains an input hash value.
  • Optimally efficient accountable time-stamping. (Ahto Buldas, Helger Lipmaa and Berry Schoenmakers. In Public Key Cryptography – PKC’2000, Melbourne, Australia. LNCS 1751, 293-305. Springer-Verlag, 2000)
    Improving the availability of time-stamping services. (Arne Ansper, Ahto Buldas, Märt Saarepera and Jan Willemson. In The 6th Australasian Conference on Information Security and Privacy – ACISP’2001, Sydney, Australia, July 2-4, 2001. LNCS 2119, 360-375. Springer-Verlag, 2001)
    In the third paper, it was realized that if the input hash values are stored only to the “leaves” of the linkage graph, then the certificates become even more compact. In the next paper the hash linking concept was generalized. Certain weaknesses of linkage schemes were pointed out and a concept of fault tolerant linkage presented.
  • Accountable Certificate Management using undeniable attestations. (Ahto Buldas, Peeter Laud and Helger Lipmaa. In The 7th ACM Conference on Computer and Communication Security – CCS’00, Athens, Greece. Nov. 1-4, 2000)