Academic Research

This is a selection of academic research papers. It is important to note that there is no new cryptography introduced and the only cryptographic primitive used is the hash-function. The main focus of the research is understanding what properties hash-functions need to have in order to ensure provable security.

Research Papers on Time-stamping

Black-box Oracle Separation Techniques with Applications in Time-stamping (Margus Niitsoo. Under the supervision of Ahto Buldas, professor of cryptography at the University of Tartu’s Computer Science Institute, 2011)

Research Papers on 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).

Efficiency bounds for adversary constructions in black-box reductions. (Ahto Buldas, Aivo Jürgenson, Margus Niitsoo In: Boyd, C., Gonza ́lez Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 264–275. Springer, Heidelberg)

Optimally tight security proofs for hash-then-publish time-stamping. (Ahto Buldas and Margus Niitsoo, In: R. Steinfeld and P. Hawkes (Eds.): ACISP 2010, LNCS 6168, pp. 318–335, 2010. Springer, Heidelberg)

The ACISP2010 paper presents a new security proof for bounded hash-then-publish time-stamping schemesWhile the previous security reductions create a quadratic loss in the security in terms of time-success ratio of the adversary being protected against, this paper achieves a notably smaller loss of power 1.5. It was shown in the ACISP 2009 paper that power 1.5 reductions are asymptotically optimal (the best one can get), which essentially means that there are some limits to the security of hash-then-publish time-stamping schemes that can be proven based entirely on the collision-freeness of the hash function. So, tighter security proofs have to use security assumptions stronger than collision-resistance.

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)

In the PKC’2000 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.

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 this 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)