外包数据库SQL查询完整性验证方法研究与实现

摘要

数据库外包服务是近些年兴起的一种应用模式。用户或企业为了节约硬件存储资源和管理成本，取消自己的数据中心，将数据库外包给专业的数据库服务提供商进行管理和维护。然而，服务提供商是不可信的，他可能试图篡改数据库的内容或伪造查询结果，数据拥有者在将数据库外包给数据库服务提供商时，会更加关注数据完整性保护的问题。因此，用户希望能够检测并验证查询结果的完整性，防止服务器篡改数据库的查询结果。针对现有的外包数据库完整性验证方案无法很好地支持多种SQL查询以及效率低等缺点，本文对外包数据库SQL查询完整性验证方法进行了研究，完成了以下工作: 本文分析了外包数据库完整性验证的研究现状，提出了外包数据库完整性验证模型。对外包数据库完整性验证模型进行形式化定义，给出了模型的六个基本算法，并对模型的安全性进行定义。此外，借助双线性映射累加器，实现了集合中元素的求和运算的完整性验证方法。在模型的基础上，基于认证跳表、可验证集合运算等技术构建了一个外包数据库SQL查询完整性验证方案，该方案支持的SQL查询有范围查询、函数查询、连接查询和部分嵌套查询，同时方案支持数据拥有者对数据进行更新。基于现有的密码学假设，给出了方案的安全性分析。代价分析表明，该方案具有较高的效率。 本文在Ubuntu系统下使用C++语言设计并实现了外包数据库SQL查询完整性验证的原型系统。针对系统中的数据拥有者、服务器和客户端三方实体，进行了功能设计和类的设计，给出了原型系统关键功能的实现。对原型系统分别进行了功能测试和性能测试，测试结果表明该系统可以正确完成各项功能，同时在初始化、查询与验证等方面的运行时间表现良好。因此，支持多种SQL查询完整性验证的研究具有广阔的应用前景和较高的应用价值。

目录

声明

摘要

第1章绪论

1．1研究背景

1．2研究现状

1．3本文研究内容

1．4本文组织结构

第2章相关理论基础

2．1双线性映射相关理论

2．1．1双线性映射

2．1．2双线性映射累加器

2．2可验证集合运算

2．2．1交集运算

2．2．2并集运算

2．3认证跳表

2．4 SQL查询

2．5本章小结

第3章外包数据库SQL查询完整性验证方案

3．1问题的提出

3．2外包数据库完整性验证模型

3．2．1形式化定义

3．2．2安全性定义

3．3关键技术

3．3．1求和运算的查询与验证算法

3．3．2范围查询的完整性证明方法

3．4方案详细描述

3．4．1密钥生成

3．4．2系统初始化

3．4．3连接查询与验证

3．4．4多维范围查询与验证

3．4．5函数查询与验证

3．4．6嵌套查询与验证

3．4．7更新

3．5代价与安全性分析

3．5．1代价分析

3．5．2安全性分析

3．6本章小结

第4章原型系统设计及实现

4．1系统设计

4．1．1总体设计

4．1．2功能设计

4．2类的设计

4．2．1认证跳表类

4．2．2数据拥有者类

4．2．3服务器端类

4．2．4客户端类

4．3关键功能的实现

4．3．1密钥生成

4．3．2系统初始化

4．3．3交集运算

4．3．4函数查询与验证

4．3．5范围查询与验证

4．3．6插入算法实现

4．3．7删除算法实现

4．4本章小结

第5章原型系统测试

5．1系统环境搭建

5．2功能测试

5．3性能分析

5．4本章小结

第6章总结与展望

6．1总结

6．2展望

参考文献

致谢

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