1. Field of the Invention
The present invention relates to an efficient and practical technique for dynamically maintaining an authenticated dictionary. The main building blocks of the process are a skip list data structure and cryptographic associative hash functions. Applications of the invention include certificate revocation in public key infrastructure and the publication of data collections on the Internet. By making the dynamic maintenance of an accumulated dictionary more practical, computations can be performed on simple devices, such as personal digital assistants (PDAs), smart cards, or cellphones.
2. Background Description
The problem we address involves three parties: a trusted source, an untrusted directory, and a user. The source defines a finite set S of elements that evolves over time through insertions and deletions of elements. The directory maintains a copy of set S. It receives time-stamped updates from the source together with update authentication information, such as signed statements about the update and the current elements of the set. The user performs membership queries on the set S of the type “is element e in set S?”, but instead of contacting the source directly, it queries the directory. The directory provides the user with a yes/no answer to the query together with query authentication information, which yields a proof of the answer assembled by combining statements signed by the source. The user then verifies the proof by relying solely on its trust in the source and the availability of public information about the source that allows checking the source's signature. The data structure used by the directory to maintain set S, together with the protocol for queries and updates is called an authenticated dictionary (see, for example, M. Naor and K. Nissim, “Certificate revocation and certificate update”, Proceedings of the 7th USENIX Security Symposium (SECURITY-98), pp. 217-228, Berkeley, 1998).
FIG. 1 shows a schematic view of an authenticated dictionary. In the use of the authenticated dictionary, a user 10 makes a query 11 to a directory 12 which responds by providing as its answer authentication information 13. The directory 12, in turn, is provided with update authentication information 14 from the source 15.
The design of an authenticated dictionary should address the following goals:                low computational cost: the computations performed internally by each entity (source, directory, and user) should be simple and fast; also, the memory space used by the data structures supporting the computation should be as small as possible;        low communication overhead: source-to-directory communication (update authentication information) and directory-to-user communication (query authentication information) should be kept as small as possible; and        high security: the authenticity of the data provided by a directory should be verifiable with a high degree of reliability.        
We can formalize the above goals as the algorithmic problem of minimizing the following cost parameters of an authenticated dictionary for set S:    1. space used by the data structure;    2. the time spent by the directory to perform an update initiated by the source;    3. size of the update authentication information sent by the source in an update (source-to-directory communication);    4. time spent by the directory to answer a query and return the query authentication information as a proof of the answer;    5. size of the query authentication information sent by the directory together with the answer (directory-to-user communication); and    6. time spent by the user to verify the answer to a query.
Authenticated dictionaries have a number of applications, including scientific data mining (e.g., genomic querying and astrophysical querying), geographic data sewers (e.g., GIS querying), third-party data publication on the Internet, and certificate revocation in public key infrastructure.
In the third-party publication application, the source is a trusted organization (e.g., a stock exchange) that produces and maintains integrity-critical content (e.g., stock prices) and allows third parties (e.g., Web portals), to publish this content on the Internet so that it widely disseminated. The publishers store copies of the content produced by The source and process queries on such content made by the users. In addition to returning the result of a query a publisher also returns a proof of authenticity of the result, thus providing a validation service. Publishers also perform content updates originating from the source. Even so, the publishers are not assumed to be trustworthy, for a given publisher may be processing updates from the source incorrectly or it may be the victim of a system break-in.
In the certificate revocation application, the source is a certification authority (CA) that digitally signs certificates binding entities to their public keys, thus guaranteeing their validity. Nevertheless, certificates are sometimes revoked (e.g., if a private key is lost or compromised, or if someone loses their authority to use a particular private key). Thus, the user of a certificate must be able to verify' that a given certificate has not been revoked. To facilitate such queries, the set of revoked certificates is distributed to certificate revocation directories, which process revocation status queries on behalf of users. The results of such queries need to be trustworthy, for they often form the basis for electronic commerce transactions.