Patent ID: 7257711

Claim:
A computer implemented method for dynamically maintaining an authenticated dictionary comprising: providing a skip list structure of nodes, each of said nodes having an object value associated with a dictionary object; maintaining an authentication dictionary by generating, for each node of the skip list structure, a node hash value based on applying a commutative hash function to the object value of the node and to at least one of its linked nodes, the commutative hash function being such that applying said function to sequences of nodes traversed in a skip list rule search of the skip list generates a hash value equal to applying the commutative hash function to the entire skip list; generating a signed skip list digest, based on applying the commutative hash function to the entire skip list and signing the resulting hash value; authenticating objects as belonging or not belonging to the authentication dictionary by searching the skip list for the object and generating a sequence of the node hash values associated with the path of the nodes traversed by the search; and validating said authenticating by generating a validation hash value by applying the commutative hash function to said sequence of hash values and comparing the validation hash value to the signed skip list digest.