Efficient, Practical Technique for Dynamically Maintaining an Authenticated, Accumulated Dictionary (Case 1419)

Principal Investigator:


Roberto Tamassia, PhD, Professor

Department of Computer Science

Brown University

Providence, RI


Brief Description:


Three parties are involved in electronic data/records use and transfer: a trusted source, an untrusted directory, and a user.  The source is a finite set of elements that evolves over time through insertions and deletions of elements.  The directory maintains a copy of this finite set, and it receives time-stamped updates from the source together with update authentication information, such as signed statements about the update and current set elements.  The user performs membership queries on the set via the directory, thereby not directly contacting the source.  The directory provides 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. 


An authenticated dictionary is the data structure used by the directory to maintain a set, together with the protocol for queries and updates.  Authenticated dictionaries should be designed with the goals of low computational cost (simple, fast computations and small memory space of data structures), low communication overhead among the three parties, and high security (directory data authenticity should be validated, verifiable, reliable).  Existing schemes for authenticated dictionaries still have complications and shortcomings in terms of practicality, efficiency and computational performance on simple devices.


The invention is an efficient, secure, and practical method for dynamically maintaining an authenticated dictionary using a skip list data structure and communicative collision-resistant hash functions to provide a dictionary database.  The innovation has essentially two new ideas: 1) rather than hashing up a dynamic 2-3 tree, hashes are created in a skip list, with the benefits of replacing complex details of 2-3 trees with easy-to-implement details of skip lists and avoiding complication of storing intervals at leaf nodes instead of storing actual items at the base nodes; 2) commutative hashing is introduced as a means to greatly simplify the verification process for a user, while retaining the basic security properties of signing a collection of values via cryptographic hashing.


This improved technique factors away many of the complications of existing schemes, while maintaining asymptotic performance properties.  Also, the innovation retains the basic security properties of previous schemes, but makes the dynamic maintenance of the dictionary more practical, particularly for contexts where user computations must be performed on simple devices.  Furthermore, the data structure of this invention matches theoretical performance parameters of the best previous approaches that attempt to optimize simultaneously all performance measures/goals.  However, in addition, the proprietary algorithms of this invention are simpler to implement and deploy in practical applications; user computations are indeed very simple and can be easily performed on devices with limited memory and computing power – smart cards, PDAs, mobile phones, and the like.  By making the dynamic maintenance of an accumulated dictionary more practical, computations can be performed on these relatively simple devices.  This dictionary database stores information objects so that any individual object can be authenticated as belonging - or not - to the dictionary.  Authentication consists of a short sequence of values beginning with an element and a sequence of values that, when hashed in order using a cryptographic associative hash function, create the same value as the hashed digest of the entire dictionary.  As such, validation of the result of the authenticating step is provided if the hash of the short sequence matches a signed hash of the entire skip list. 


Applications for authenticated dictionaries exist in numerous market segments (e.g., mobile devices, software, smart cards, etc.).  Examples include: for use in certificate revocation in public key infrastructure (often the basis for e-commerce transactions); scientific data mining (e.g., genomic or astrophysical querying); the publication of data collections on the internet; geographic data sewers (e.g., GIS querying); third-party data publication on the internet (e.g., stock exchange publishing stock prices via a Web portal); for use in the cloud, and/or computational software in simple and/or wireless, mobile devices such as PDAs, smart cards, and cellphones; scientific R&D to advance the field of computer science and software development. 


Relevant markets include: computer software, hardware, and/or applications; scientific R&D research tools. 




US Patent 7,257,711 is issued (08/14/2007)

Patent Information:
Research Tools
For Information, Contact:
Margaret Shabashevich,
Manager of Operations
Technology Ventures Office
Brown University
401-863-7499 TVO_Patents@brown.edu
Roberto Tamassia
© 2017. All Rights Reserved. Powered by Inteum