LBH-based Optimal Authenticated Data Structure Model And Application

With the gradual deepening development of computer networks, distributed data systems gradually become the clients’ data management collection at all levels. More and more information is stored in remote entities. In distributed environment, data is stored and transmited through untrust networks and servers. And this makes it difficult to check the integrity of remotely stored data and where it is from. So how to authenticate the integrity and completeness of the data received has been an important research subject in the field of imformation security.The paper starts from the cryptography and lattice theory basics, and deeply studies the authenticated data strucure and digital signature scheme. And then constructs a lattice-based hash function LBH, whose security relies on the hardness of GAPSVP. The paper describes the design idea and the LBH construction. After proving the correctness and security of LBH, complexity analysis is proved.The paper then presents an update optimal ADS using the LBH and Merkle tree, named LBH-UADS. In specific, the digest update time is O(1), improving in this way the "a priori" logarithmic limit (in n) of Merkle tree constructions. The digest calculation and a new radix-2representation are presents. And the "sum" form of the digest is based on these. After proving the correctness and security of LBH-UADS, the paper also analyzes the complexcity of the structure.In order to show the advantage of the LBH-UADS, the paper applies it into the3-party ADSM. The entity construction and communication protocol are presents before the security certification. After the comparison of the complexity among schemes, the paper presents an electronic identity authentication system, which provides the source with instant update time. The flow of entities cooperating and prototype implementation of the system are presented at the end of the paper.