Helger Lipmaa's publications

Optimally Efficient Accountable Time-Stamping

Ahto Buldas, Helger Lipmaa and Berry Schoenmakers. Optimally Efficient Accountable Time-Stamping. In Yuliang Zheng and Hideki Imai, editors, PKC 2000, volume 1751 of Lecture Notes in Computer Science, pages 293--305, Melbourne, Australia, January 18--20, 2000. Springer, Heidelberg.

File: [.ps.bz2 (81 KB), .pdf (246 KB)] ps recommended.


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 \emph{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 \emph{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..

Keywords: NA.

Comment: See Cuculus Homepage for other time-stamping papers.

More information: CiteSeer.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.