New Designs Of Authentication Hash Table

Hash table is a data structure which can greatly improve the efficiency of data search.As the application of hash table becomes more and more extensive,the authenticity of hash table has become increasingly important.For example,Company A outsources the information of its employees to Server B.Client C then sends a query to Server B,who returns a response.In this scenario,Client C would like to verify the validity of the response.In order to satisfy this practical need,the notion of authenticated hash tables was proposed by Papamanthou,Tamassia and Triandopoulos at ACM CCS in 2009.Compared with ordinary hash tables,authenticated hash tables allow anyone to verify the validity of query results.This thesis presents new designs of authenticated hash tables from Merkle-Tree and lattice,to further improve the efficiency and security of authenticated hash tables.The main contributions are two-fold:1.The first contribution is a more efficient authenticated hash table.Papamanthau,Tamassia and Triandopoulos proposed an authenticated hash table using RSA accumulator and Bilinear-Map accumulator.While their design successfully adds authenticity on hash table,Bilinear-Map is a costly operation which takes heavy computations.To further improve the efficiency,this thesis proposes a new authenticated hash table scheme based on Merkle-Tree(MAHT).Its security can be reduced to the Integer Factorization problem and the collision-resistance of hash functions.It does not need costly Bilinear-Map operations,which reduces the time of evidence generation and improves the overall efficiency.2.The second contribution is a quantum-resistant authenticated hash table.Since the introduction of authenticated hash table,little research has been seen on its extension and variants.At present,there is no formal research on authenticated hash table in the post-quantum era.To fill this gap,this thesis gives a design of authenticated hash table(LAHT),whose security can be reduced to complexity problems on lattice.As these complexity problems are hard to solve even with quantum algorithms,LAHT can be used in the post-quantum era.