Abstract: Authenticated skip list is an important authenticated data structures. It has been widely used in data authenticanon. Since the hash scheme has the important influence on the cost of the authenticated skip fist, a new hash scheme which is based on the idea of separating the hash scheme and data storage scheme was proposed in this paper. And the new algorithm of authenticated skip list(ASI: DHT for short) based on directed hash tree was also proposed. We applied hierarchical data processing and probability analysis methods to analyze the cost of ASL-DHT, and also made an algorithm simulation to compare with that of the original authenticated skip list. hhc results show that, ASI= DH T algorithm has got great improvement on storage cost, communication cost, and time cost.

Key words: Authenticated skip fist, Authenticated hash scheme, Directed hash tree, Authenticated data structures