Introduction

Work presented here has been conducted within the framework of the ACI sécurité informatique 2003-2006 . It has also received the support of the conseil général des landes and the cellule de valorisation of the university of Pau

Timestamping is a technique for providing proof-of-existence of a message/document at a given time. Parties of a timestamping system are the followings :

  Client : forms the timestamping request which is the digest of the document to be timestamped. The client computes this digest by using a well known one-way collision-free hashing function. Submitting the digest of the document instead of the document itself preserves the confidentiality of the document.

  TimeStamping Authority (TSA) : receives the timestamping request at time t and issues the timestamp. The timestamp is a proof that the digest was received at time t. The TSA produces the timestamp according to a timestamping scheme.

  Verifier : verifies the correctness of the timestamp by using the verification scheme corresponding to the timestamping scheme which was used to produce the timestamp.

Timestamping Authorities mostly use some linking schemes in order to reduce the scope of operations they have to be trusted for. Thus, during a time interval called a round, the TSA receives a set of timestamping requests and aggregates them in order to produce a round token. Each timestamp consists of the round token, the digest and the authentication path proving that the round token depends on the digest. Round tokens are regularly published in a widely distributed media (a newspaper). After the publication it becomes impossible to forge timestamps even for the TSA.

There are two types of linking schemes : partially ordered linking schemes and totally ordered linking schemes. In the case of partially ordered linking schemes, only timestamps from different rounds are comparable whereas in the case of totally ordered linking schemes, the temporal order of any two timestamps can be verified even if these two timestamps belong to the same round.

We have defined a new totally ordered timestamping scheme. Our scheme is simpler than the existing ones and shows optimal performances. It is based on skip lists. A first version of our scheme can be found in [2]. The last version will be presented at the next Applied Cryptography and Information Security conference [1].

Chronos is our prototype based on our scheme. We arbitrarily fixed the round duration to one hour. Chronos is ISO/IEC 18014-1:2002, 2:2002 and 3:2004 compliant.

Suggestions, comments can be sent to k.blibech@etud.univ-pau.fr or alban.gabillon@univ-pau.fr

[1] K. Blibech & A. Gabillon. New Timestamping Scheme Based on Skip Lists. To be presented at the next Applied Cryptography and Information Security conference (ACIS). Glasgow May 2006.

[2] K. Blibech & A. Gabillon. Chronos : An Authenticated Dictionary based on Skip Lists for Timestamping. Proc. of 12th ACM Conference on Computer Security (Workshop Secure Web Services). George Mason University, Fairfax, VA, USA. November 2005.