外包数据库模型中的完整性检测方案

An Integrity Checking Scheme in Outsourced Database Model

外包数据库模型中完整性保护的目标是防止数据库服务提供商篡改数据库内容,完整性检测方案的作用是让查询方能够验证查询结果是真实的、未被篡改的.在现有的基于验证数据结构方法的基础上进行改进,提出了一种以带掩码的验证树作为核心数据结构的完整性检测方案,给出了数据结构的形式化定义并证明了其安全性.该方案将数据结构中共同的计算信息抽取到两个掩码向量中,通过避免使用大量幂指数运算,降低了查询验证过程的计算代价,减少了查询验证的时间.其特有的验证数据结构增量更新的优点能够提高数据库更新的执行效率.实验表明,该方案在查询验证时间上略优于现有的同类型方案,在数据更新性能上较同类方案具有明显优势.

In the outsourced database model, databases face potential threats from malicious database service providers. Security mechanisms are needed to assure the queriers that the query results have not been tempered with and are authentic with respect to the actual data owner. As an improvement of the existing authenticated-data-structure-based methods, a new integrity checking scheme is proposed using the masked authenticating B＋-tree （MABTree） as the underlying data structure. Common computational information is extracted from the MABTree and is stored in two mask vectors, so as to make the computation in the data structure more efficient. By avoiding mass exponential computation, the scheme reduces both the computational overhead in the integrity check process and the verification time of the query results. The MABTree is designed to support incremental updating, which makes the scheme more efficient when the owner updates the data and the authenticated data structures are updated accordingly. The security proof of the scheme is presented together with the formal definition of the MABTree. Experiments show that, compared with the existing methods, the proposed scheme has a better performance in query verification and a much better performance in the authenticated data structure updating operations.