分层哈希链表及其在数据查询认证中的应用

摘要

分布式环境下的数据发布模式与传统的，数据拥有者承担用户查询处理的集中式模式相比具有网络等待时间短，服务器维护便宜，抗DDoS攻击等一系列的优势，具有广阔的应用前景。然而在分布式网络环境中，发布服务器的可信性很低，因而保证查询结果的正确性，正成为这一领域中研究的热点。
　　认证跳表等方案在处理简单的查询认证问题方面性能优秀，但无法正确认证诸如关系查询等复杂查询的结果。近年来一些学者提出的签名链方案弥补了该缺点，但对每个数据项都签名的实现手段却使其效率过低。本文在分析了现有数据认证方案不足的基础上，提出了分层哈希链表(Hierarchical Hash Linklist，HHL)，给出了HHL的构建、更新、查询和认证算法。通过对HHL中冗余哈希节点的分析，提出了效率更优秀的分层哈希链表改进方案，将其应用于分布式环境下的三方认证模型中。通过利用统计学的方法对HHL的代价进行理论分析，指出其拥有O(logn)的代价。并列举多种破坏数据认证性的手段对应用HHL的认证模型进行安全性分析，表明该模型能够检测出任何一种对查询结果认证性的破坏行为。将HHL与签名链方案进行了仿真比较，实验数据表明HHL在通信及计算等认证代价方面要优于签名链方案。
　　本文将HHL应用于关系查询结果的认证中，解决了不同种类关系查询的结果认证问题。设计并实现了一个数据查询认证原型系统，保证了在分布式数据发布中，发布服务器只返回用户想要的结果，但却能提供足够的证据证明所有的返回结果都具有认证性和来源可靠性。研究结果表明基于HHL的数据认证在空间和时间方面是高效的。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 本文的研究内容

1．4 本文的组织结构

第2章 相关理论研究基础

2．1 密码学哈希函数

2．1．1 抗碰撞哈希函数

2．1．2 可交换哈希函数

2．1．3 多元哈希函数

2．2 跳表认证技术

2．2．1 认证数据结构与跳表

2．2．2 认证跳表

2．2．3 三方数据认证模型

2．3 数据库查询认证技术

2．3．1 基本的签名链方案

2．3．2 选择查询的认证

2．3．3 选择-投影查询的认证

2．3．4 多属性查询的认证

2．4 小结

第3章 分层哈希链表

3．1 问题的提出

3．1．1 基本的分布式查询认证问题

3．1．2 查询结果的认证性

3．1．3 现有数据认证方案的分析

3．2 分层哈希链表的构建与认证

3．2．1 HHL构建

3．2．2 HHL认证和更新

3．3 改进的分层哈希链表

3．3．1 N-HHL算法

3．3．2 N-HHL的实现

3．4 基于HHL的数据查询认证模型

3．5 小结

第4章 性能分析

4．1 数据认证问题的代价分析模型

4．2 数据认证问题的安全分析模型

4．3 代价分析

4．4 安全性分析

4．4．1 一致性分析

4．4．2 认证性分析

4．5 性能比较

4．6 小结

第5章 数据查询认证原型系统的设计与实现

5．1 总体设计

5．1．1 系统体系结构

5．1．2 系统功能模块划分

5．2 关键技术

5．3 系统实现

5．3．1 发布服务器模块的实现

5．3．2 客户端模块的实现

5．4 小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读硕士学位期间的论文项目情况