Cryptology ePrint Archive: Report 2013/730

Stamp \& Extend -- Instant but Undeniable Timestamping based on Lazy Trees

Łukasz Krzywiecki and Przemysław Kubiak and Mirosław Kutyłowski

Abstract: We present a Stamp\&Extend time-stamping scheme based on linking via modified creation of Schnorr signatures. The scheme is based on lazy construction of a tree of signatures.

Stamp\&Extend returns a timestamp immediately after the request, unlike the schemes based on the concept of timestamping rounds. Despite the fact that all timestamps are linearly linked, verification of a timestamp requires a logarithmic number of steps with respect to the chain length. An extra feature of the scheme is that any attempt to forge a timestamp by the Time Stamping Authority (TSA) results in revealing its secret key, providing an undeniable cryptographic evidence of misbehavior of TSA.

Breaking Stamp\&Extend requires not only breaking Schnorr signatures, but to some extend also breaking Pedersen commitments.

Category / Keywords: cryptographic protocols / timestamping, undeniability, forgery evidence, Schnorr signature

Original Publication (in the same form): Chris J. Mitchell and Allan Tomlinson, editors, INTRUST, volume 7711 of Lecture Notes in Computer Science, pages 5–24. Springer, 2012.

Date: received 6 Nov 2013

Contact author: przemyslaw kubiak at pwr wroc pl

Available format(s): PDF | BibTeX Citation

Version: 20131113:052433 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]