Optimally efficient accountable time-stamping

A. Buldas, H. Lipmaa, L.A.M. Schoenmakers

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

39 Citations (Scopus)


Efficient secure time-stamping schemes employ a 2-level approach in which the time-stamping service operates in rounds. We say that a time-stamping service is accountable if if it makes the TSA and other authorities accountable for their actions by enabling a principal to detect and later prove to a judge any frauds, including attempts to reorder time-stamps from the same round. We investigate the paradigm of time-stamping services based on simply connected graphs, and propose a simple, yet optimal, accountable time-stamping service, using what we call threaded tree schemes. We improve upon the previously best scheme by Buldas and Laud by reducing the size of a time stamp by a factor of about 3.786 and show that our construction is optimal in a strict sense. The new protocols also increase the trustworthiness of the publication process, which takes place at the end of each round.
Original languageEnglish
Title of host publicationPublic Key Cryptography (Proceedings PKC 2000, Melbourne, Australia, January 18-20, 2000)
EditorsH. Imai, Y. Zheng
Place of PublicationBerlin
ISBN (Print)3-540-66967-1
Publication statusPublished - 2000

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Optimally efficient accountable time-stamping'. Together they form a unique fingerprint.

Cite this