Eliminating counterevidence with applications to accountable certificate management.
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 someone 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.
Introduction
The concept of public-key cryptography was created in an effort to solve the cryptographic
management problem [DH76]. While giving an answer to many difficult
problems, public-key cryptography also raised several of its own. Not surprisingly,
one of the main problematic areas to be solved before public-key cryptography can be
successfully applied in practice is still that of key management. There has been a huge
A preliminary version of this paper [BLL00] appeared in the ACM CCS '2000 Conference. The current
version is the final submission to the Journal of Computer Security.
y Tallinn Technical University/University of Tartu/Cybernetica AS, Akadeemia tee 21, 12618 Tallinn,
Estonia, ahto.buldas@cyber.ee
z Universit at des Saarlandes, FB 14 Informatik, Im Stadtwald - Bau 45, Postfach 15 11 50, 66041
Saarbr ucken, Germany, laud@cs.uni-sb.de
x Helsinki University of Technology, Laboratory for Theoretical Computer Science, Department of Computer
Science and Engineering, FIN-02015 HUT, Espoo, Finland, helger@tcs.hut.fi
body of research on key management methods since [Koh78] but key management
involves still considerably more trust toward the third parties than rest of cryptography.
We say a certificate management system is accountable when all forgeries by
third parties can be explicitly proven and all false accusations explicitly disproven.
Efficient and accountable identity-based certificate management is necessary in par-
ticular, but not only to support authenticity of digital documents with a long life-
time. A body of supporting methods for long-term authenticity was developed in
the area commonly known as digital time-stamping [HS91]. Recent work in time-stamping
has also shown how to build efficient yet accountable time-stamping systems
[BLLV98, Lip99, BLS00] with minimal trust in the third parties. However,
one has to complement the techniques of accountable time-stamping with methods
from other areas of applied cryptography to support long-term authenticity and non-
repudiation. One of such areas is accountable efficient certificate management. Unfor-
tunately, cryptographic literature has only briefly treated the question of how to achieve
the latter [CL96].
First, we present informal motivation and definition of accountable certificate man-
agement, where every validity change of a certificate is accompanied by a transferable
attestation ascertaining this act, and a short digest of the current state of database of
valid certificates is periodically published. In Section 2, we argue informally that a certificate
management system is accountable if and only if it is intractable for anybody
to create a pair of contradictory attestations, so that a certificate would be accepted
as valid or not, depending on which certificate is in possession of the verifier. Under
this intractability assumption, our certificate management system has several desirable
properties. The most important property is that if physical visits to the Certification
Authority (CA) are audited, every subsequent dispute in court can be solved by the
present evidence. Moreover, one can verify certificate validity at some moment, based
only on a short digest of the certificate database, a short certificate-specific attestation
and the certificate itself. The rest of the paper is focused on this assumption.
In Section 3, we give the formal definition of a new primitive called undeniable
attester. Informally, an attester is a triple (P; D;V ) of algorithms, such that
The proving algorithm P , given a candidate string x and a set S, outputs an
attestation certifying whether x 2 S.
The digest algorithm D, given a set S, outputs a short digest it.
The verification algorithm V is given a candidate element x, a digest d, and an
attestation p. V accepts or rejects on input (x; d; p), depending on whether x
belongs to a set with digest d. Here, p contains additional information about the
status of x 2 ? S.
We call an attester undeniable if it is intractable to generate a digest d, an element x
and two attestations p and p such that V (x; d; p) accepts but V (x; d; p) rejects. In the
context of certificate management, S is a database of identity certificate serial numbers.
In Section 4 we survey some attesters whose subsystems were considered previously
in certificate management and public-key infrastructure. In particular, we review
attesters based on certificate revocation lists, hash trees [Mer80], certificate revocation
trees [Koc98, NN00] and RSA accumulators [BdM93, BP97]. However, since most
of the mentioned systems have not been designed with accountability in mind, they all
have some implicit trust assumptions. As a result, we conclude that the only previously
known undeniable attester is the trivial one (similar in efficiency to the certificate
revocation lists) with attestation lengths (jSj  log jSj).
A good example of an attester that is not undeniable is the sorted hash tree attester,
defined in Section 4.4. Sorted hash tree attesters are based on an efficient construction
similar to the certificate revocation trees. We show in Section 4.4 that sorted hash tree
attesters are not undeniable and therefore a sorted hash tree attester-based certificate
management system makes it possible for the CA to cheat clients.
In Section 5, we propose a very simple efficient authenticated search tree-based
construction of undeniable attesters that we call an authenticated search tree attester.
The key difference between sorted hash tree attesters and the proposed construction is
that authenticated search tree attesters assign to every internal node v of a search tree
a hash value S[v], taken over the labels of v's children and the search key of v. (In
sorted hash tree attesters, S[v] does not authenticate the search key of v.) Moreover,
authenticated search tree attesters are in several aspects more intuitive than sorted hash
tree attesters: Being directly based on search trees as they are generally understood
in computer science, they allow us to carry over to cryptography the research done in
the area of algorithms and data structures [Knu98]. As such, the proposed undeniable
attester might have surprisingly wide applications in different security applications,
and not only in certificate management.
After defining new attester, we will prove that it is undeniable. As with any new
cryptographic primitive it is good to know how it relates to previously known prim-
itives. A proof that undeniable attesters exist if and only if collision-resistant hash
functions exist is presented in Section 5.
We show in Section 5.4 that our methods can be extended to multi-field records.
First, we can think of every x 2 S as composed of two parts, a unique key and a body.
Searching can be performed only by looking up the key; the authenticated search tree
attester can be modified to enable detecting the case when the key is not unique. Further
extensions are possible. These extensions provide also a better answer to natural
question what exactly is a candidate string x in the case of certificate management. We
purposefully have not yet specified this: x could be certificate serial number, but also a
hash of whole certificate, whatever is more relevant in practical applications. However,
the best solution might be to let the unique key to correspond to serial number, and the
body to correspond to the hash of whole certificate.
In Section 6, we will provide efficiency analysis of the authenticated search tree
attester. We show that attestations in the authenticated search tree can be compressed,
under ideal conditions, by a factor of 2; this makes authenticated search tree attester
almost as space efficient as the sorted hash tree attester. While this method is straight-
forward, the authors are unaware of any previous constructions that use the same technique
to compress search trees. Moreover, it is unusual to apply standard compression
methods to make cryptographic primitives more space efficient. The attestation compressing
method given in Section 6 might be of independent interest.
Terminology. We have intentionally chosen to use slightly nonstandard but self-consistent
terminology. In particular, we have tried to avoid overloading already notoriously
overloaded terms "certificate" and "proof" and relatives, by introducing the term
attestation. We use the more concrete term certificate management instead of "PKI".
(Certificate management denotes usually the process whereby certificates are managed
and used, while the PKI refers to the entire framework established for certificate man-
agement.)
Motivations
Our research is motivated by the observation that for long-term authenticity and non-repudiation
of digital documents, new methods are necessary for verifying whether
identity certificates (bindings between a person and a signature key) were valid at some
moment of time. Since many digitally signed documents (e.g., loan agreements) may
have important legal value for decades, it would be desirable to ensure that validity
information of certificates cannot be forged by anybody, including the authorities.
We aim at construction of an accountable certificate management system, where all
forgeries by third parties can be explicitly proven and all false accusations explicitly
disproven [BLS00]. More precisely, we would like the only part of certificate management
(physical visit of a person to an authority) that clearly cannot be mathematically
modeled also to be the only stage in the system that needs some non-cryptographic
solution (i.e., involving physical presence of a client-chosen notary) to trust problems.
If visits were "correct", the system should need no auditing anywhere else. In partic-
ular, clients should be able to discover if the CA has maliciously issued new invalid
certificates or removed valid certificates that are still valid.
Long-term certificate validity can be partially ensured by the methods of time-stamping
[HS91, BLLV98], where absence of a proof that a certificate was issued is
implicitly counted as the proof of its nonexistence. However, such an assumption is
clearly undesirable in many situations. We would like to have not only explicit positive
attestations stating that valid certificates are valid, but also explicit negative attestations
stating that non-valid certificates are not valid. In this way, all disputes regarding
the validity of a certificate could be solved based on the present evidence (a positive
or a negative attestation), given that it is intractable for anybody to create a pair of
contradictory attestations.
From now on, we will work in a setting where the CAmaintains a dynamic database
S of valid certificates. See [Riv98, GGM00] for argumentation why a database of
valid certificates is better than a database of revoked certificates. In our case, database
of revoked certificates would just add unnecessary complexities to the system. The
presence of a central authority lessens the communication complexity of the scheme
and simplifies tracking of the origins of frauds. Our model also includes the Publication
Authority [BLS00] and a (possibly huge) number of clients.
We assume that every client receives a positive (resp. negative) attestation from the
her certificate x belongs (resp. does not belong) to the database S of valid certifi-
cates. This assumption is not restricting, since some sort of attestation-or receipt-is
returned to the client by the CA in every certificate management system. In our sys-
tem, it is in client's own interest to store the attestation so that he can later explicitly
prove or disprove the validity of his certificate at some time. Additionally, everyone
can make membership queries of type "x 2 ? S" to the CA, who then returns an attes-
tation. Clients who want later to use an attestation p of "x 2 S" (or of "x 62 S") as
evidence in court, should obtain it from the CA in some suitable time-frame. This is
very similar to what is done in time-stamping [BLLV98, Lip99].
A digest of database S (denoted as D(S)) is published by the Publication Authority
in some authenticated and widely available medium by using accountable
publishing protocols [BLS00]. Motivations behind this are the same as in time-stamping
[HS91, BLLV98, BLS00]. First, without authenticated information about
the database, the CA can easily create contradictory attestations. Second, long-term
authenticity should not depend on the security of private keys [HS91]. Publishing
the digest is the most natural and widely accepted solution in digital time-stamping to
achieve the long-term authenticity. Third, nobody should be forced to store old versions
of the dynamic database S: The system should still be accountable, if a verifier does
not have anything more than an element, a short attestation, and a short digest of the
database. This is again very similar to the situation in time-stamping, where clients can
verify a time stamp given only the time stamp (equivalent to the attestation), the round
stamp (equivalent to the digest), and the candidate element itself [HS91, BLLV98].
Our model of accountable certificate management incorporates at least three different
algorithms. Motivated by this, we define a new primitive, attester, to be a triple
algorithms. The proving algorithm P , given a candidate string x and a
set S, outputs an attestation. The digest algorithm D, given a set S, outputs a short
digest of the database. Finally, the verification algorithm V takes as input a
candidate element x, a digest d, and an attestation p, and accepts or rejects depending
on whether x belongs to a set S such that
In described model, the CA cannot cheat a client. (We assume that Denial of Service
attacks by the CA, where the CA does not return an attestation to the client, can
be prevented for example by letting a client-chosen notary to participate in handing
over the attestation.) That is, if a client has a positive (resp., negative) attestation that
some certificate belonged (resp., did not belong) to the database of valid certificates at
some time, the CA has no means to generate a contradictory attestation, claiming that
the same certificate was not (resp. was) in this database at that time, assuming that the
CA is not able to break some underlying cryptographic primitives. More formally, we
call an attester undeniable, if it is intractable to generate a set S, an element x and two
attestations p and p such that V (x; D(S); p) accepts but V (x; D(S); p) rejects.
For long-term authenticity undeniability is crucial-e.g., when the CA who issued
a concrete certificate might have gone bankrupt long before the verification act, so that
it is impossible to sue her for cheating. Moreover, if a client has accidentally deleted
his attestation, he can at least be sure that nobody else can sue him, based on a contradictory
attestation. These properties will significantly increase the trustworthiness of
the CAs.
Application in Court
The relevance of undeniable attestations can probably be best exemplified by the next
application. If a digital signature law is passed in some country, it becomes natural to
expect that digital signatures would then be considered as legally valid as handwritten
ones. In particular, one should be able to solve legal disputes based on the validity
of a particular signature on a particular document. As is well known, one needs certificate
management for that in order to determine the validity of the digital signature.
However, one often overlooks the real process in court, where a person presents to
the judge a piece of evidence, which in this case is a signed document together with
a certificate. The judge cannot take an action, based on the evidence (that we call an
attestation) alone, if it is possible for somebody else to create counterevidence (that we
call the contradictory attestation). For example, certificate revocation list can be seen
as counterevidence.
Currently, it is almost always possible, at least for the CA, to create counterevi-
dence. Therefore, court's decisions often base on heuristics that involve trust in some
authorities, eyewitnesses or other human beings. In the case of digital signatures, the
definition of eyewitnesses is unclear, and one might not want to trust the authorities.
Not only is it possible that the authorities might be corrupted, but a malicious client
could also claim that a honest authority is guilty. In such cases the judge cannot take
an action, since the authority might or might not be guilty. If it is intractable to create
a counterevidence even for the authorities, the court can always authoratively decide
a case, based on evidence. By doing this, the judge does not have to trust anybody,
and everybody can also check that judge's actions are correct. The latter means that
one cannot question ambiguous actions of court related to digital signatures, and hence
there is no reason to appeal to a higher court if the actions of the the lower court were
provably wrong.
Separation of Duties
Functions of the CA should be divided between at least two authorities, an off-line
CA, and an on-line Validation Authority, as it is done also in many other certificate
management systems [CL96]. However, while the distinction between the CA and the
Validation Authority is important in practice, it is not a subject of this paper: Since
our methods help to prevent forgeries even in the case when one possibly misbehaving
party (the CA) has control over the whole system, it also prevents forgeries if there are
several third parties. For simplicity, in this paper we will not stress separation between
the authorities. For the same reason, we do not elaborate on the accountable publication
protocols but rather refer the reader to [BLS00] for necessary information.
3 Formal Definitions
3.1 Preliminaries
1g. As usually,  k denotes the set of k-bit words,   :=
. For
denotes string of k -s. From now on, k denotes the security parameter,
relative to which security of various schemes is measured. We assume that nil is a special
encoded differently from any x 2   . Let EA be the class of probabilistic
algorithms with execution time that is polynomial in the length of their first input. A
family negligible if for all " > 0 there exists a
Notation X S means that X is assigned
according to the probability space S that may be the output space of some probabilistic
algorithm.
A collision-resistant hash function (CRHF) H for some index set I    is a pair
(G; H), such that (1) G 2 EA is a generation algorithm, such that G(1 k
(2) For an index i 2 I , H(i;
polynomial p, where p(k) > k; (3) For all algorithms A 2 EA, the
probability family CRHH (A) is negligible in k, where
Note that index i is only necessary when one requires H to be collision-resistant. Otherwise
one can assume that jI
3.2 Definition of Attester
We have already given informal definitions of attesters. Next, we present the full for-
malism, followed by discussion.
is an attester for an index set I    , if
there is a polynomial f , f(k) > k, such that
1. A generating algorithm G 2 EA takes as input a security parameter 1 k and
outputs an index i 2  k \ I .
2. A proving algorithm P 2 EA takes as input an index i, an element x 2  k and a
set S   k , jSj  f(k) and outputs an attestation P i (x;
3. A digest algorithm D 2 EA takes as input an index i, a set S   k , jSj  f(k)
and outputs a digest D i
4. A verification algorithm V 2 EA takes as input an index i, a candidate element
digest d and an attestation p and outputs
We require that if i 62  k \ I , S 6  k , jSj > f(k) or x 62  k , then for
any p, V i (x; D i (S); practice, one should set D i
Otherwise, for any S   k with jSj  f(k),
and for any x 2  k , outputs Accept if x 2 S and Reject
if x 62 S.
be an attester and let A 2 EA. Let
x
and
Attester A is a collision-resistant prover (resp. collision-resistant disprover) if 8A 2
negligible. A is a collision-resistant attester if
for any A 2 EA, both CRPA (A) and CRDA (A) are negligible.
undeniable if for any A 2 EA, UNA (A) is negligible.
3.3 Discussion
Note that in the definition of attesters the role of generating function and indices is the
same as in the definition of hash functions. Namely, they are not necessary unless we
discuss strong security properties like collision-resistance and undeniability. Otherwise
we can assume that jI In informal treatment, one can omit I at all. However, in
our constructions of undeniable attesters we have to assume that the used hash function
is collision-resistant, which automatically introduces need for the index set I in the
formal treatment.
It is important to understand the seemingly subtle but crucial in applications difference
between collision-resistant attesters and undeniable attesters. Collision-resistant
attesters assume that a verifier has access to the correctly computed value D i (S). In
practice, it means that she either has to rely on some trusted third party to provide a
correct D i (S) or has to have access to S herself. Both possibilities are undesirable in
many security applications, including accountable certificate management. Undeniable
attesters stay secure even in the presence of an adversary who forges the digest, and
therefore potentially provide a much higher level of confidence in the system.
In practice, S is organized as a certain data structure. In many cases, attester is
just a security add-on to this data structure. We will see this in Sections 4.4 and 4.3,
where attesters will be based on corresponding types of trees. Therefore, we will often
use the terminology of data structures in the context of attesters. For example, one
would like an attester to have "succinct" attestations and digests but also fast average-case
update time of the data structure. Informally, we say that an attester is dynamic
if average-case time per insertion and deletion of elements to the corresponding data
structure is O(jij log jSj) for any i 2 I . We say an attester is succinct if for any i 2 I ,
log jSj). Note that since
attester has jD i
4 Some Known Constructions
Next, we will give a short survey of some attesters based on previously proposed ideas.

Table

1 summarizes the properties of attesters described in this section, together with
authenticated search tree attesters described later in Section 5. Note that the hash tree
attester and the RSA attester are not succinct, since they have negative attestations of
length (jSj  log jSj). However, one can easily modify both attesters to be succinct, by
Primitive
type
Name Digest Positive
attestation
Negative
attestation
Length in ()
A List (x4.1) k n log n n log n
Hash Tree
CRA Sorted Hash Tree
UA Authenticated Search Tree

Table

1: Some known succinct attesters, i.e., security is given only for the succinct
versions (see Section 3.3). For example, while the list attester is an undeniable attester,
it is only a succinct attester. Here log n is the security parameter.
defining to be equal to some fixed constant for all x 6= S. Both the modified
hash tree attester and the modified RSA attester are succinct collision-resistant provers.
A similar trick does also work with the list attester, but the resulting succinct construct
will only be attester without satisfying any stronger security requirements.
As emphasized in Section 2, in accountable certificate management we are interested
in undeniable attesters. In the following we will briefly explain why already
known attesters fail to satisfy our requirements. The main result of this paper is the
provably secure authenticated search tree attester, described in Section 5.
List attester is the most trivial attester. For any x and a set S, attestation P (x; S) is
D(S) is equal to a short k-bit hash H(S) of S, where H is a collision-resistant hash
function. (Remember that k is a security parameter.) The verification algorithm V ,
accepts if and only if
S). The resulting construction is clearly undeniable.
Unfortunately, the list attester becomes utterly inefficient if the number of simultaneously
valid certificates grows, since both storage requirements and verification time
are at least linear in jSj. One of the possibilities to decrease the verification time is to
assume that the CA has sorted the database. Although then the clients can perform a
binary search in the database, the attester will cease to be undeniable since the CA may
leave the database unsorted. This method would also not reduce the storage requirements

4.2 RSA Attester
The RSA attester can be in a natural way built upon the RSA accumulator [BdM93,
BP97]. Here, the positive attestations have the form
for some y therefore the attestation length is (k), where k is again a
security parameter. The digest has the same form and therefore also the same length.
However, as first pointed out by Nyberg [Nyb94, Nyb96], the length of the attestations
can be reduced by introducing built-in trapdoor information known to some coalition
of participants, which should therefore be trusted. The best known method [San99]
of making the RSA accumulator trapdoorless introduces attestation lengths of order
log jSj, the trapdoorless RSA accumulator has longer attestations
than the sorted hash tree attester, described below. Moreover, the negative
attestations are equal to all of S.
4.3 Hash Tree Attester
Hash trees [Mer80] are widely used to authenticate an element as a set member. In the
full generality, the hash tree is a labeled tree, with the leaves labeled by different values
nodes labeled by the hash over their children labels, where a fixed
collision-resistant hash function is used.
In the hash tree attester, a positive attestation consists of the minimal amount of
data necessary to verify the hash path from the leaf, labeled by x, to the root. We
assume that the hash trees used have depth logarithmic in the number of nodes. As a
result, the positive attestations have length (k log jSj), where k is again the output
length of the used collision-resistant hash function. The digest D(S) of length (k)
is equal to the label of the root. On the other hand, negative attestations must include
every element of S an have hence length (kjSj).
4.4 Sorted Hash Tree Attester
Similarly to the case of the list attester, hash tree attester can be made more efficient if
the CA sorts the leaves, an idea only recently proposed in [Koc98, NN00]. (We assume
that the values stored at the leaves are sorted from left to right.) The resulting sorted
hash tree attester has both negative and positive attestations with length (k log jSj)
and is therefore succinct. However, as also in the case of (sorted) list attester, the
proposed solution hides in itself an implicit assumption that the CA dutifully sorts the
leaves. Since the observed weakness in sorted hash trees is a crucial motivation to our
subsequent work, we will next give a detailed definition of sorted hash tree attesters
together with a full explanation of their weak points.
4.4.1 Construction
The next attester (G; is based on a fixed CRHF H). The only role
of the generating function G in this attester is to choose a concrete hash function H i
from this family, according to the function GH . Therefore, for the sake of simplicity,
we will describe attesters for a fixed i 2  k \ I and for a fixed hash function
. The latter can in practice be instantiated with SHA-1 [NIS94] or any other strong
(keyed) hash function. Let f be an a priori fixed polynomial that does not depend on k.
Next, suppose that is a nonempty set of k-bit integers such
that S[j] < S[j +1] for any 1  j < n. Let T be a (directed) binary tree with n leaves,

Figure

1: A toy example of the sorted hash tree attester. Dashed lines are present only
in the improved sorted hash tree attester, described in Section 4.4.2. The values S[v]
are given for the unimproved construction. For the ease of illustration we have chosen
all vertices to be elements of Z, although the concrete values of v's are not important
in practice.
with its jth leftmost leaf labeled by S[j] (Figure 1). A non-leaf vertex labeled
by an auxiliary hash value
where v L (v R ) denotes the left (right) child of v. The digest of S is equal to
the label of the root vertex v, or to Error, if the leaves were unsorted, jSj > f(k), or
some leaf had a label S[v] 62  k .
with 0 corresponding to the left and 1 corresponding to the right direction. The verification
algorithm V (x; d; p) returns Error if p does not have such form. Otherwise, V
computes dm by assigning d 0 := x and then recursively, for every j > 0,
Verification returns Accept, if d d, and Error, otherwise. If x 2 S, the proving
algorithm P returns a p such that V (x; d; p) accepts. Proving that x 62 S is equivalent to
finding a quadruple
correspond to two neighboring leaves in the tree T . If x is
smaller than the least element x 1 of S, we can define P (x; S) to be equal to P
The situation when x is bigger than the greatest element of S is dealt with analogously.
Looking at the tree depicted in Figure 1,
and P (35; On the other hand,

Figure

2: A toy example of improperly created sorted hash tree attester.
4.4.2 Further Efficiency Improvements
One can further shorten the negative attestations by inserting additional arcs to the
underlying tree as follows (slightly different methods were also proposed in [Koc98,
If the parents of a leaf v 6= 1 and its left neighbor leaf w are different, then
add an arc from w to v's parent, as in Figure 1. Build an attester upon the resulting
graph, by modifying the algorithms P , D and V to account for the new arcs. Let the
negative attestation of x be equal to the positive attestation of the smallest x 0 > x in
set S if such x 0 exists, or of the x, otherwise. As the result, both negative and positive
attestations will have the same length.
4.4.3 Sorted Hash Tree Attester is not Undeniable
Sorted hash tree attester is succinct, dynamic (if built upon dynamic trees) and
collision-resistant. However, it is not undeniable. We show this by the example depicted
in Figure 2. There, the positive attestations of 10, 40 and 20 are respectively
also a negative attestation of 20. Therefore, a verifier, given the digest S[7] (root of the
hash tree), accepts or rejects 20 depending on which attestation was earlier submitted
to her. The same is also true for improved sorted hash tree attesters.
Such "unsorting" attack is possible since there is no efficient way for the verifier
to check whether the CA dutifully sorted the database. The only obvious possibility to
prevent this attack, without involving another trusted third party, is to send the entire
database of total size jSj  log jSj to the verifier. The verifier would then recompute the
tree, verifying that this database in the sorted order results in digest d, obtained
by her beforehand from a reliable source. However, such solution is clearly impractical
if jSj is large, since the verifier has to do jSj 1 hash computations per every verifi-
cation. Moreover, such a solution is impossible if some elements in the database are
inaccessible (if, to lessen the storage requirements, the old versions of the certificate
database are not stored).
Intuitively, the need to send the entire database is caused by the fact that a candidate
string x can be a label of any leaf, and therefore a negative attestation should
incorporate all positive attestations. To understand it, think of searching from an unsorted
database S. Showing that x belongs to S is accelerated by presenting an index j
(an attestation) of x's occurrence, followed by checking that the jth element is equal to
x. However, if x does not belong to the database, one has to verify for each j that the
jth element is not equal to x. Therefore, a corrupted CA may easily build an unsorted
hash tree without being detected by anyone who does not possess a copy of the whole
S.
5 Authenticated Search Tree Attester
Next, we give a construction of what we call authenticated search trees. After that
we show that the resulting attester (authenticated search tree attester) is an undeniable
attester, and finish the section with some discussions. First, let us remember that a
directed binary tree T is a search tree [Knu98, Section 6.2.2] if every node v 2 T has
a unique search key K[v] associated to it, such that if w is the left (resp. right) child of
v, then K[w] < K[v] (resp. K[w] > K[v]).
5.1 Construction
Let f be some a priori fixed polynomial. We give, as in Section 4.4, a construction for
fixed k. and for fixed i 2  k \ I . Let S   k be a nonempty set and let T be a binary
search tree with jSj vertices. Each vertex v of T is labeled by a pair (K[v]; S[v]). Here,
the elements K[v] belong to the set S and K[v 1 . Moreover, the
tree T together with keys K[v] is a search tree. The value S[v] is equal to
equal to the label S[] of the v's left (resp. right) child if the
corresponding child exists, or to nil, otherwise. For example, if v is a leaf, then
Once again, the digest D(S) is defined as S[v], where v is the root
vertex, or as Error, if T is not a proper search tree, in particular, if jSj > f(k) or for
some leaf v, S[v] 62  k .
For a x 2 S (resp. x 62 S), the attestation P (x; S) is defined as the least amount of
data necessary to verify that v, given that
T is a proper search tree). Intuitively, following an attestation of x 2  k is equivalent
to searching x from a search tree, where the usage of hash functions in the vertices
guarantees that the CA has to work with the same tree during each query. Moreover,
the verification algorithm V returns Error if the tree is not found to be a proper search
tree.
The rest of this subsection gives a more technical definition of the authenticated
search tree attesters, including the necessary (local) verifications that T is a search
tree. It is necessary to perform these verifications for the authenticated search tree
attester to be undeniable, and therefore to avoid any fraud.
Let
where all the elements are from  k , and m  0. The verification algorithm V (x; d; p)
returns Error if (1) h L 6= nil and x < k 0 , or (2) h R 6= nil and x > k 0 . Naturally, V
also returns Error if the attestation p does not have the specified form. Otherwise, V

Figure

3: A toy example of authenticated search tree. Note that vertices can be enumerated
arbitrarily. For the ease of illustration we have chosen all vertices to be elements
of Z, although the concrete values of v's are not important in practice.
assigns d 0 := H(h
After that, V outputs Error if
Otherwise, V returns Accept or Reject, depending on whether k
If x 2 S, the algorithm P (x; S) returns a list p such that V (x; D(S); p) accepts.
As we will see below, such a p is easy to find. If x 62 S, P (x; S) finds (1) An element
x 0 , such that x 0 is the greatest element x 0  x (the predecessor of x), if such x exists,
or the smallest element in S, otherwise; (2) An element x 00 , such that x 00 is the smallest
element x 00  x (the successor of x), if such x exists, or the greatest element in S,
otherwise.
By the construction of search trees, either x v 00 on the
root path starting from the node with sorting key x 0 , or vice versa. (Otherwise P (x; S)
returns returns a list p such that V
x 0 in the first case and x in the second case.
Clearly, V (x; D(S); p) accepts if and only if x 2 S. Note that the verification
returns Error only if the tree fragment, reconstructed from p, cannot be a part of
a search tree.
toy example with is depicted in Figure 3.
Here,
This attestation contains the predecessor and the successor of 41 (40 and 42, resp.), 42
(42 and 42, resp.) and 43 (42 and 56, resp.
5.2 Security
Theorem 1 The authenticated search tree attester is undeniable if H is a collision-resistant
hash function family, where the reduction is security preserving in the next
meaning. Let A 2 EA be an algorithm, s.t. UNA ". Then there exists an
adversary
Proof. The adversary M is defined as follows. Given an index i and the security
parameter performs a query to A(1 k ; i). With probability ", this query outputs a
tuple (x; d; p; p), such that V i (x; d; Reject. Therefore,
Analogously, we will
overline the variables d j that are computed during the verification of p.
The adversary processes p and p in parallel. From (ST1) d
Therefore, using
(ST2) we get that for some s and s,
(Remember also that nil 62  k ).
Next, if k s 6= k s , then M has found a collision H i
let us assume, without loss of generality, that x < k
has found
a collision H i (d s
Therefore, the adversary M finds a collision to H with probability ". Note that M
works in time (t log jSj), where t is the working time of A. ut
As with any new cryptographic primitive-and undeniable attester is a new
primitive-it is good to know how it relates to the previously known primitives. Next
results establish the relationships between collision-resistant attesters, undeniable at-
testers and CRHFs.
undeniable attester is a collision-resistant attester.
Proof. Let A be a machine, such that either CRPA
or ". Next we construct an efficient machine M that has UNA
returns (x; d; p; p), if
otherwise.
queries once the algorithms G(1 k ),
in constant time. With probability " k , either (a) x 62 S   k , but
Reject. Therefore, UNA
Note that the construction in Section 4.4 showed that not each collision-resistant
attester is undeniable, and hence the opposite of this lemma is not true.
Theorem 2 Undeniable attesters exist if and only if CRHFs exist.
Proof. Let be an undeniable attester. By Lemma 1, A is also
collision-resistant. Next, we show that if A is collision-resistant, then (G; D) is
a CRHF on 2  k
(i.e., on the subsets of  k ). Let A 2 EA be an adversary, such that
Let M be the next machine. For i). With the
, we can
efficiently find an element x in (w.l.o.g.) S 1 nS 2 . Let p := P i By the definition
of attesters,
Thus, we have found a tuple (x;
Accept. A contradiction, and thus D i is a CRHF on sets (i.e., on 2  jij
, or alternatively,
on concatenated strings S[1]S[2]    S[jSj], where
We finish the proof by constructing a CRHF on the input domain
as follows. Let p(k), be an arbitrary string, such that
p(k). (It is sufficient to look at strings with length
dividing k log 2 p(k), due to the constructions presented in [Dam89, Mer89]. Now
denotes a k-bit binary fixed representation of i 2 N . Clearly, if D is a CRHF on the
domain 2  k
, then H is a CRHF on domain   .
The opposite was proven by Theorem 1. ut
5.3 Discussion
The construction of Section 5.1 generalizes to the case when the underlying tree is a
multiway search tree [Knu98, Section 6.2.4]. However, if we wish the attestations to
have length O(k log jSj), we are restricted to the trees where the number of children
of every node is upper-bounded with some constant that does not depend on k. As a
result, we cannot base our construction on exponential search trees and other related
data structures that have been lately extensively used in sub-logarithmic search algorithms
[BF99].
Authenticated search trees can be made dynamic as in [NN00] by requiring that
the CA stores the whole hash tree, and after each database update updates all the necessary
hash values in the tree, including the value D(S). Updating can be done in
time O(k log jSj) by using appropriate dynamic search trees (say, AVL or 2-3 trees but
also skip lists). Since our construction is just a slight reformulation of what is usually
meant by search trees, and most of the "reasonable" data structures for searching can
be seen as search trees, one can choose the data structure that is the most convenient in
a concrete application.
There are many other possible constructions of undeniable attesters. For example,
one could add a number of arcs to a binary tree as follows: For any non-leaf node v,
add an arc (if it already does not exist) from its left child's rightmost descendant leaf
to v. We emphasize that the main difference between the described constructions of
collision-resistant and undeniable attesters is that in the first case the choice between
the left and the right subtree is just done by an explicitly given bit b i . In the latter case,
there is instead an explicit search key K[v], such that based on K[v], the verifier can
additionally check that the element returned in a query is in the correct location in this
tree.
5.4 Extensions to Multi-Field Records
Both our definition of the attesters and the construction of authenticated search trees
were given for the case when the database S consists of some indivisible records x.
However, quite often one works in a situation where x is composed of several fields.
For example, in many cases the first field key(x) acts as a unique key to the entire
record In such a case,
there is a need for a set of algorithms allowing the database maintainer to
commit to the value of S in such a way, that
The clients can perform a query S, to which the response is either
body(x) if the database S contains a unique record with the key key(x)
or Undened if there is none;
It is intractable for the database maintainer to give different answers to queries
for the same key key(x) (thus the response of the CA has to contain some kind
of proof).
The authenticated search tree can be used to construct the necessary primitive. The
database S is organized as an authenticated search tree; the algorithm D is left un-
changed. If there exists a y for which key(x)jjy 2 S then let x 0 be the predecessor
of key(x)jjy and x 00 be the successor of key(x)jjy in S. Otherwise, let x 0 be the predecessor
and x 00 be the successor of key(x)jj0 t in S. (If
The attestation P (key(x); S) is equal to P
some well-defined presentation. Given negative attestation, the verification procedure
additionally checks that and that there are no elements
x with in the tree, and returns Error if this is not the
case. Given positive attestation, the verification algorithm additionally checks that
that there are no elements
or in the tree, and that there is some key(x)jjy 2
In both cases, (non-)existence of such
x can be efficiently verified,
because the positions of the vertices labeled by x 0 , key(x)jjy and x 00 in the search tree
can be determined from the attestation.
More generally, one could use authenticated k-d trees to perform multidimensional
queries. Here, authenticated k-d trees are natural extensions of authenticated search
trees to Bentley's k-d trees [Ben75, Ben79] for handling databases with k fields. As
shown by Bentley, k-d trees can be balanced to have depth (log jSj), in which case it
takes O(jSj 1 t=k ) steps to find all records with t fields equal to specified values, and
steps to find all elements in a t-dimensional subspace, when there is
q such elements. (See [Knu98, Section 6.5] for more information.)
In the context of certificate management, one could take, for example, key(x) to be
equal to the unique certificate serial number, while body(x) would be the hash of the
whole certificate.
6 Efficiency
6.1 Average-case Attestation Length
For a fixed size of S, authenticated search trees result in the shortest worst case attestation
length if the underlying tree T is a complete binary tree. In this case, if we
additionally assume that the search keys have length k-in practice, we store at leaves
the hash values of certificates that are generally longer than k bits-then the worst case
attestation length is k  simple
calculation shows that the attestations P i (x; S) have in total 1
which makes the average-case
attestation length equal to
This is about twice as much as the attestation length in the complete binary tree based
(improved) sorted hash tree attester. Also, in general, upon other types of trees, our
construction has on average twice longer attestations than the optimal construction
of collision-resistant attesters presented in Section 4.4.2. When using the dynamic
AVL trees [Knu98, Section 6.2.3], the worst case certificate length of the dynamic
authenticated search tree attester is therefore  2:88  k log n.
6.2 Attestation Compression
Next, we describe a method for compressing the attestations. More often than not,
compression algorithms are seen as consisting of two standard parts, modeling and
coding [BCW90]. An adaptive modeling algorithm estimates the source from the part
of the data sequence seen so far, by outputting a probability distribution for the new
symbol. After that, an encoder (say, the arithmetic encoder) uses this distribution to
encode a new symbol by using as few bits as possible.
We can apply this general approach to the authenticated search trees. First, let T be
a fixed search tree, and let k be the security parameter. We remind you that the elements
of S are k bits long. During the modeling, we assign to every node v recursively a range
As previously, let min S  0 be the least and let maxS
be the greatest element in S. If v is the root vertex, then ('
let v be an arbitrary vertex. To the left child v L (if existing) of v, we assign a
range (' v L
1). Analogously, to the right child v R (if existing) of
v we assign the range (' v R
every root path in T can be
seen as a data sequence. For a node v in this sequence, the adaptive modeling algorithm
returns the uniform distribution in (' v ; u v ) to the encoder.
After that, the encoder encodes the value K[v] ' v as a binary number K c [v],
using dlog 2 (u v ' v )e bits. The compressed attestation P c (x; S) is equal to the uncompressed
attestation P (x; S), with search keys K[v] replaced with corresponding
compressed keys K c [v]. We additionally assume that the new digest D c (S) is equal
to the triple (D(S); min Verification still needs the uncompressed attestation
which can be easily computed from P c (x; S). Not surprisingly, the fact
that all intermediate values K[v] can be unambiguously reconstructed from P c (x; S) is
crucial for undeniability, and guided us during the choice of the encoder. Some more
efficient encoders that we are aware of do not guarantee unambiguous reconstruction of
all intermediate values, especially since the verifier has no previous knowledge about
the tree T .
Assuming that T is a complete binary tree, the uncompressed attestations have the
length is the height of T . The compressed
attestations are never longer than k(n +n. The worst case is obtained if
2g. (We will not count in the short additional data necessary to
encode the lengths of K[v]'s. One could use, for example, Elias !-codes [Eli75] for
the latter.) This provable gap between the worst case length of the compressed and
uncompressed attestations is achieved thanks to the implicit structure hidden in the
ordered data. However, the value kn n 2 +n
unexpected
quantification of the amount of this structure.
On the other hand, the attestations never shorten by a factor greater than two and
therefore the authenticated search tree attester has longer attestations than the sorted
hash tree one. However, the factor can be arbitrarily close to 2 when k  n. As an
example, let us look again at Figure 3. The root path from the root to the leaf with label
has nodes with search keys K[v 1
Computing the ranges, we find that (' v 1
Therefore (as previously, we
denote the n-bit binary encoding of m as hmin ), K c
and jP c (42; the compression
gain is  1:754  9=5. While this is an unrealistic example due to maxS  min S
(remember that the elements of S are collision-resistant hashes of certificates. When
the hash function is modeled as a random function, maxS  min S holds with a
negligible probability), it shows that this compression method can result in quite big
savings already for small n-s. In real life situations an example with
database of that size might be typical in future certificate management
systems in middle-sized countries), depicted by Table 2, is more appropriate.
6.3 Optimality Questions
The classical predecessor problem requires one to maintain a set S so that the queries
of the form "Is j an element of S and, if not, what element of S, if any, is just before it
Method Attestation length in bits
Collision-Resistant Attesters
Sorted hash tree k(n
Undeniable Attesters

Table

2: Comparison of the worst-case attestation lengths of collision-resistant and
undeniable attesters in bytes, where
in sorted order?" may be answered efficiently. Membership problem only requires that
the question "Is j an element of S?" may be answered efficiently.
There exist extremely efficient dynamic attesters if one does not require them to be
collision-resistant. On the one hand, let A be an arbitrary attester, such that f i , where
works in the worst-case time t f;jij . Straightforwardly, there exists a
search algorithm working in time t D which solves the membership
problem.
On the other hand, according to the results of [DKM + 94] for search algorithms
solving the membership problem, there exists a dynamic attester, such that for any
S   k and for every x 2
(Define only if x 2 S, and fix D i (S) to be the empty string).
However, both the sorted hash trees and our authenticated search trees do not solve
only the membership but also the predecessor problem, since the attestation P (x; S)
always contains the predecessor of x, if it exists, or the smallest element in S. An
interesting open problem is whether this is really necessary.
Conclusions
The approach to certificate management in this paper is straightforward: First we went
back to the source (in our case, the legal system, and more precisely, the court), then
we identified why certificate management is necessary there and how to minimize the
number of frauds; in our case, this was achieved by making it infeasible to create coun-
terevidences. We then gave a rigorous definition of necessary cryptographic primitives
(undeniable attesters), and described and analyzed an efficient undeniable attester, the
authenticated search tree attester. We showed that the latter is almost as efficient as less
secure sorted hash tree attesters, by using a simple (but novel) compression technique.
The resulting certificate management system has many desirable properties. It is
accountable, since all disputes can be solved by the present undeniable evidence. This
means in particular that all forgeries by the third parties can be explicitly proven and
all false accusations explicitly disproven. It is efficient, since certificate validity can be
verified, given only the certificate, a short digest of the certificate database and a short
attestation.
Apart from the model of accountable certificate management system, the second
main result of this paper is a construction of undeniable attesters. Undeniable attesters
may become a very useful security primitive, since they make it possible for anyone to
perform securely membership (and predecessor) queries without relying on the trusted
third parties nor requiring an access to the whole database.
We stress that the current paper provides a model of certificate management, not a
complete system, and that more work is needed for making the certificate management
really accountable. More precisely, our system guarantees that it is intractable to create
a certificate database S, such that if x 2 S (resp., x 62 S), the CA can create an
attestation certifying that x 62 S (resp., x 2 S). In practice, S is dynamic and the
may remove valid certificates or insert invalid certificates from S at his will. Such
malpractice can be detected, for example, if interested parties ask attestations of x 2 ? S
every time S is updated. One possibility would be to introduce another trusted party (or
a set of volunteers), who would compare the changes between the subsequent versions
of S with official documentation provided by the CA and notaries about the physical
visits of clients. However, it would be desirable to find more efficient protocols for this
purpose. (See [Sar00] for some preliminary analysis.)
Further Work
Strict optimality of our constructions is left as an open question. For example, since
it is easier to solve the membership problem [DKM than the predecessor problem
[BF99], it would be interesting to know whether succinct undeniable attesters can
be built upon the search algorithms solving the membership problem. Elaboration of
exact protocols and duties of different participants in accountable certificate management
is of utmost importance.
Finally, what benefits would be gained by using authenticated search trees instead
of sorted hash trees in other areas of data security? As an use example, results of the
preliminary version of this paper [BLL00] have already been used to build a secure key
archival service in [MB02].

Acknowledgments

The authors were partially supported by the Estonian Science Foundation, grant 3742.
The first author was partially supported by the Estonian Science Foundation, grant
4760. A preliminary version of this paper was published as [BLL00]. We would like
to thank Andris Ambainis, Carl Ellison, Kobbi Nissim, Berry Schoenmakers, Stuart
Stubblebine and anonymous referees for useful comments that helped to improve the
paper.



--R

Text Compression.

Multidimensional Binary Search Trees Used for Associative Searching.
Multidimensional Binary Search Trees in Database Applications.
Optimal Bounds for the Predecessor Prob- lem
Accountable Certificate Management Using Undeniable Attestations.

Optimally Efficient Accountable Time-stamping
Niko Bari
A Certification Scheme for Electronic Commerce.
A Design Principle for Hash Functions.
New Directions in Cryptography.
Friedhelm Meyer Auf Der Heide
Universal Codeword Sets and Representations for the Inte- gers
In Hideki Imai and Yuliang Zheng
How to Time-stamp a Digital Document
The Art of Computer Programming.
On Certificate Revocation and Validation.
Toward a Practical Public-key Cryptosystem
Secure and Efficient Time-stamping Systems
Enabling the Archival Storage of Signed Documents.
Protocols for Public Key Cryptosystems.
One Way Hash Functions and DES.

Certificate revocation and certificate up- date
Commutativity in Cryptography.
Fast Accumulated Hashing.
Can We Eliminate Revocation Lists?
Efficient Accumulators without Trapdoor.
Analysis and Application of Accountable Certificate Man- agement
--TR
Text compression
A design principle for hash functions
One way hash functions and DES
Dynamic Perfect Hashing
One-way accumulators
The art of computer programming, volume 3
Optimal bounds for the predecessor problem
Accountable certificate management using undeniable attestations
Multidimensional binary search trees used for associative searching
Enabling the Archival Storage of Signed Documents
Efficient Accumulators without Trapdoor Extended Abstracts
Time-Stamping with Binary Linking Schemes
A Certification Scheme for Electronic Commerce
Can We Eliminate Certificate Revocations Lists?
On Certificate Revocation and Validation
Fast Accumulated Hashing
Efficient and Fresh Cerification
Optimally Efficient Accountable Time-Stamping

--CTR
Glen Nuckolls , Chip Martel , Stuart Stubblebine, Certifying data from multiple sources [Extended Abstract], Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
Peeter Laud , Tarmo Uustalu , Varmo Vene, Type systems equivalent to data-flow analyses for imperative languages, Theoretical Computer Science, v.364 n.3, p.292-310, 8 November 2006
Petros Maniatis , Mary Baker, Secure History Preservation Through Timeline Entanglement, Proceedings of the 11th USENIX Security Symposium, p.297-312, August 05-09, 2002
attesters;long-term authenticity;accountable certificate management;search trees;public-key infrastructure;time-stamping;non-repudiation;authenticated search trees