外包数据库中的查询结果验证技术 外包数据库这个题目行吗？ 文洁 2013年3月29日

大纲 研究背景 查询验证的基本知识 位置隐私保护的查询验证技术 总结 数字签名链 Merkle 哈希树 Authenticating Location-based Services without Compromising Location Privacy. SIGMOD 2012 总结

研究背景 外包数据库模型 1) 篡改数据 2) 篡改查询结果 查询请求 数据和索引 结果 数据拥有者 服务提供商 用户 查询结果验证 包数据库模型主要由三个实体组成:(l)数据所有者，(2)数据库服务提供商，(3)用户。在该模型中，数据所有者将数据及相关索引结构上传到外部数据库服务器，数据库服务器代表数据所有者向用户提供服务。 进行查询结果验证的动机：第三方的数据库服务器有是不可信的，它可能会为了自己的利益 1）篡改数据；2）篡改查询结果。如果缺乏有效的措施，一旦出现这些情况，而用户又无法证明数据的真伪，往往会给用户，甚至数据拥有者造成严重的后果。因此，需要为客户提供一种手段使其能够快速准确地验证查询结果是否真实和完整。 数据拥有者 服务提供商 用户 查询结果验证

查询结果验证目标 返回的查询结果满足查询要求 正确性 数据拥有者的数据没有被篡改 真实性 查询结果全部返回客户端 完整性

查询结果验证技术 基于概率的方法 基于有验证功能的数据结构 监测元组 没有返回满足条件的监测元组，则断定数据库已被攻击 全部返回满足条件的监测元组，则以一定概率断定数据库 完整性没有收到攻击 基于有验证功能的数据结构 返回查询结果和验证对象VO 数字签名链 Merkle 哈希树 基于概率的结果完整性验证方法。数据拥有者在将数据外包给第三方服务提供商时，在数据中混入了一组特别的监测元组。这些混在原始数据中的监测元组就会以一定概率包含在查询结果中，并返回给提交查询的用户。用户可以通过监控这些额外插入的元组来监控外包数据库的完整性。如果一个满足查询条件的监控元组没有被返回，那么用户就可以断言完整性已经被攻击。反之，如果所有满足查询条件的监控元组都完整地返回，则以一定概率断定完整性没有受到攻击。 返回结果和VO，大多数查询验证都是基于这两种方法的。

基本知识 消息摘要 （digest） 非对称加密技术 消息通过单向哈希函数得到的一个固定长度的值 消息的指纹：相同的消息得到相同的摘要，不同的消 息得到不同的摘要 单向性：给定消息摘要不能得到原消息 非对称加密技术 两把钥匙：公钥和私钥，分别加密和解密 RSA 我先来介绍一下关于查询验证的基本知识。 第一个，消息摘要，是经过单向hash函数得到的一个固定长度的值，相同的消息得到相同的摘要，不同的消息得到不同的摘要，哪怕只更改该段落的一个字母，通过哈希算法作用后都将产生不同的值。消息摘要是消息的指纹，确保消息的完整性。 非对称加密技术，加密和解密用的是两把不同的钥匙。或者用公钥加密，用私钥解密；或者用私钥加密，用公钥解密。 假设两个用户要加密交换数据 明文 明文 加密 密文 解密 公钥 私钥 解密 加密 密文 明文 明文

数字签名 数字签名是消息摘要与非对称加密技术的应用 数字签名的功能： 保证信息的完整性 认证消息发送者的身份 比较 消息 单向hash函数 数字签名是消息摘要和非对称加密技术的综合应用。数字签名的功能是保证信息传输的完整性、认证发送者的身份。 数字签名技术是如何使用的。 数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。 消息摘要digest 消息摘要digest 消息摘要digest 私钥 单向hash函数 公钥 消息 + 数字签名 消息 + 数字签名 消息发送者 消息接受者

数字签名 数字签名在外包数据库查询验证中的应用 数据拥有者 外包服务商 数据库和数字签名 查询结果 和数字签名 查询请求 公钥 目前较多的还是基于公钥密码的数字签名。首先，数据拥有者对数据库中每一个属性值都签名，然后将签名和数据库外包到服务器，将公钥发送给用户。用户想服务器发送查询请求，外包服务器返回结果和对应的数字签名。用户用公钥解密签名，就能验证结果的真实性，也就是说可以验证数据没有被篡改。 但是，这种方法只能验证真实性，却无法验证查询结果的完整性。服务器可能偷懒，只返回了正确结果集中的部分结果。 公钥 无法验证结果完整性！ 用户

数字签名链 签名和近邻的值有关 第一个值前和最后一个值后添加两个特别对象

数字签名链 服务器返回d2和d3作为结果 验证对象VO: 1) Sig(d2), sig(d3); 2) 边界值d1和d4 验证过程 1保证了结果是完整的；2）保证了结果是正确的

Merkle哈希树 只有根节点签名 签名 d1 d2 d3 d4 这棵树是为四个值d1，d2，d3，d4建立的Merkle哈希树。树的叶子节点是对应值的摘要，由一个单项哈希函数求得。中间节点是所有子节点摘要的串联值。 排好序 串联 d1 d2 d3 d4

Merkle哈希树 服务器返回d2和d3作为结果 验证对象VO: 1) N2的摘要; 2) 根节点N的签名 签名的 d1 d2 d3 d4

Merkle哈希树 客户端验证过程 比较 N = h ( N1 | N2 ) N1 = h ( N11 | N12 ) N11 = h ( d1 ) N12 = h ( d2 ) d1 d2

数字签名链 vs. Merkle哈希树 比较项目 Merkle Hash Tree 数字签名链 数据库创建速度 快 慢 空间占用量 小 大 客户端验证效率 高 低 验证过程 过于依赖根节点签名 与结果签名相关 快速定位被篡改记录 能够 不能 数据更新效率 对这两种方法进行一个小总结 1）数据库创建速度快。中间节点只需要计算其hash值，而且只需要对根节点签名，节省了大量的签名计算，加快了数据库的构建速度。 2）为数据库服务器节省了大量的存储开销。因为保存hash值需要的存储空间远远小于保存数字签名需要的存储空间 3）为了验证查询结果，用户只需要计算部分中间节点的hash值并使用根节点的数字签名验证自己计算出来的根节点的hash值，从而减少的验证数字签名的次数，提高了验证速度 4）安全性较低。MHT树的安全性过于依赖根结点的安全性，容易出现“单点故障’，，一旦根结点的签名被篡改，不管数据库中的记录是否正确，用户都无法验证查询结果的正确性和完整性。 5）不能快速定位被篡改记录的位置。如果返回的查询结果被篡改，用户验证后只知道结果有错误，但不能找到错误一记录的具体位置。因此，一旦数据被篡改，数据所有者必须重传所有记录，同时服务器必须重构整棵树。 6）但是，一旦数据库中有数据需要更新，该类验证技术就需要重新构建MHT树。因此，这类查询验证技术更适合处理静态数据库，例如数据仓库。基于数字签名链的查询验证技术需要对数据库中的所有记录签名，因而数据库创建成本极高。用户只能逐个地验证查询结果，其验证速度比较慢。但是，当有数据需要更新时，该类方法只需要对少数几条数据重新签名，因而更新速度快，适合处理动态数据库。

查询验证中的安全和隐私问题 边界数据 数字签名的安全性 位置数据 目前已有的查询验证技术一般需要将不在用户查询范围内的左右边界一记录的值返回给用户，用户就有机会获取不在其访问权限范围内的数据，从而破坏了访问控制规则，泄露了隐私数据和敏感信息。 已有的查询验证技术一般假设数据库中的数据没有加密，数据都是以明文的形式保存在数据库中。已有的查询验证技术一般使用RSA等普通的公钥签名方案对数据库中的特定数据签名。但是普通签名是自证明和可传递的，任何人只要获取了该签名就可以验证数据的正确性。现有的查询验证技术在查询验证过程中一般直接将数据拥有者的签名发送给用户，泄露了数据拥有者的签名，给数据库查询验证技术带来了许多安全问题。伪装成服务器为他人提供服务。

Haibo Hu, Jianliang Xu, Qian Chen, Ziwei Yang Sigmod 2012 Authenticating Location-based Services without Compromising Location Privacy Haibo Hu, Jianliang Xu, Qian Chen, Ziwei Yang 在LBS中，如何实现结果验证，同时不会泄露用户位置信息

为付费用户提供实时的、精准的交通信息；为免费用户提供滞后的、粗糙的信息 背景和动机 告诉我附近拥堵的路段 为付费用户提供实时的、精准的交通信息；为免费用户提供滞后的、粗糙的信息 签到服务，近邻服务 移动客户端 LBS服务请求 在一个公共交通监控服务中， 查询结果 用户位置 位置数据拥有者 第三方服务提供商

背景和动机 找到附近和餐厅和每个餐厅的就餐人数 签到服务，近邻服务 移动客户端 LBS服务请求 在查询结果中添加赞助的餐厅 查询结果 通过提供签到服务，近邻服务，每天可以得到海量的用户位置信息。同时，一些移动运营商也在为用户提供更多的增值服务。 提供一些增值服务，如签到和附近朋友提示等。 为了得到就餐人数，通过在每个餐厅附近执行一次范围查询即可。 为了解决这些信任问题，很必要需要服务提供者在提供服务同时，也提供一套查询结果验证的机制。 以往的技术。。。 在LBS服务中，验证需要返回具体的用户位置信息。比如在这个例子中。 查询结果 用户位置 位置数据拥有者 第三方服务提供商

安全问题和目标 安全问题 目标 客户端可能会通过验证对象包含的的信息推测出用户 的位置信息 服务提供者为了自身利益可能会返回错误的查询结果 在保护位置信息不泄露给客户端的前提下，对查询结 果进行验证 因此在这样一个环境背景下，存在两个安全隐患：1）客户端可能会通过VO的信息推测出用户的位置信息。2）服务提供者为了自身的利益，可能会返回错误的查询结果。 因此这篇文章的主要目的就是：在无条件保护位置信息不被泄露的情况下，对查询结果就行验证。

范围查询的验证 B+树索引位置，叶子节点的值按序排列 基于Merkle Hash Tree的验证技术 验证目标 数据的真实性 数据的正确性 数据的完整性 签名 root digest 为了使得范围查询可验证，这篇文章采用了Merkle 哈希树这种经典做法。 真实性可以保证，MHT可以保证整个数据没有被篡改过。 应为是用B+树索引的，所以要保证数据的正确性和完整性，验证查询结果边界值即可。 digest digest digest digest …… … u1|x1 u2|x2 u3|x3 u4|x4 u8|x8 u9|x9 u10|x10 digest digest digest digest digest digest digest

范围查询的验证 验证查询结果边界值 例子： 验证： 查询：范围在[a, b]之间的用户 结果:（u3, u4, …, u8, u9） u2<a u3>=a u9<=b u10>b 签名 root digest 应为是用B+树索引的，所以要保证数据的正确性和完整性，验证查询结果边界值即可。 在不需泄露位置的情况下完成验证。客户端和服务器联合完成验证过程。 digest digest digest digest …… … u1|x1 u2|x2 u3|x3 u4|x4 u8|x8 u9|x9 u10|x10 digest digest digest digest digest digest digest

联合计算摘要 判断x>=a g(x−L) = g(x−a)⊗g(a−L) 服务器 客户端 g()方法只接受正整数 服务器 客户端 g()方法只接受正整数

查询验证摘要

查询验证过程 步骤一：判断边界值是否正确 步骤二：比较根节点摘要和签名摘要 方法：客户端和服务器联合计算摘要，保护位置隐私 目的： 1）结果正确性； 2）结果完整性 步骤二：比较根节点摘要和签名摘要 方法：自底向上计算节点摘要 结果的真实性

R树索引上的验证 边界验证 B+树：四个值 R树：每个停止分裂的节点 R树上的验证和B+树上的验证差不多，都是需要考虑边界值的验证。 验证每一个停止分裂的节点。 查询处理和VO构造的过程。

谢谢 Q & A