The majority of real-world applications of digital signatures use timestamping to ensure non-repudiation in face of possible key revocations. This observation led Buldas, Laanoja, and Truu to a server-assisted digital signature scheme built around cryptographic timestamping.

We propose an efficient and flexible system for a secure and authentic data exchange in a multiinstitutional environment, where the institutions maintain different databases and provide secure and limited access services to employees of other institutions. The main motivation for building such a system was to organize efficient cooperative use of state registers, in order to increase the efficiency and quality of public services in Estonia. In order to meet high security requirements, several contemporary measures are integrated (using digital signatures, distributing certificate information by means of DNS protocol and linking log files with cryptographic checksums). We give rationale for the design decisions made in the implementation process and conclude with the current state of public use of the resulting infrastructure.

This paper presents a method to increase the accountability of certificate management by making it intractable for the certification authority (CA) to create contradictory statements about the validity of a certificate. The core of the method is a new primitive, undeniable attester, that allows som eone to commit to some set S of bitstrings by publishing a short digest of S and to give attestations for any x that it is or is not a member of S. Such an attestation can be verified by obtaining in authenticated way the published digest and applying a verification algorithm to the triple of the bitstring, the attestation and the digest. The most important feature of this primitive is intractability of creating two contradictory proofs for the same candidate element x and digest. We give an efficient construction for undeniable attesters based on authenticated search trees. We show that the construction also applies to sets of more structured elements. We also show that undeniable attesters exist iff collision-resistant hash functions exist.

This paper initiates a study of accountable certificate management methods, necessary to support long-term authenticity of digital documents.Our main contribution is a model for accountable certificate management, where clients receive attestations confirming inclusion/removal of their certificates from the database of valid certificates.We explain why accountability depends on the inability of the third parties to create contradictory attestations.After that we define an undeniable attester as a primitive that provides efficient attestation creation, publishing and verification, so that it is intractable to create contradictory attestations.We introduce authenticated search trees and build an efficient undeniable attester upon them.The proposed system is the first accountable long-term certificate management system.Moreover, authenticated search trees can be used in many security-critical applications instead of the (sorted) hash trees to reduce trust in the authorities, without decrease in efficiency.Therefore, the undeniable attester promises looks like a very useful cryptographic primitive with a wide range of applications.