Authenticating Location-based Services without Compromising ...

1 .外包数据库中的查询结果验证技术 文洁 2013 年 3 月 29 日 

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

3 . 研究背景 外包数据库模型 1) 1) 篡改数据 篡改数据 2) 2) 篡改查询结果 篡改查询结果 数据和索引 查询请求 结果 数据拥有者 服务提供商 用户 查询结果验证 

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

5 .查询结果验证技术 基于概率的方法 监测元组 没有返回满足条件的监测元组，则断定数据库已被攻击 全部返回满足条件的监测元组，则以一定概率断定数据 库完整性没有收到攻击 基于有验证功能的数据结构 返回查询结果和验证对象 VO 数字签名链 Merkle 哈希树 

6 .基本知识 消息摘要 （ digest ） 消息通过单向哈希函数得到的一个固定长度的值 消息的指纹：相同的消息得到相同的摘要，不同的消息 得到不同的摘要 单向性：给定消息摘要不能得到原消息 非对称加密技术 两把钥匙：公钥和私钥，分别加密和解密 RSA 明文 明文 加密 密文 解密 公钥 私钥 解密 加密 密文 明文 明文 

7 . 数字签名 数字签名是消息摘要与非对称加密技术的应用 数字签名的功能： 保证信息的完整性 认证消息发送者的身份 比较 消息 单向 hash 函数 消息摘要 digest 消息摘要 digest 消息摘要 digest 私钥 单向 hash 函数 公钥 消息 数字签名 消息 数字签名 + + 消息发送者 消息接受者 

8 .数字签名 数字签名在外包数据库查询验证中的应用 数据拥有者 外包服务商 数据库和数字签名 查询结果 查询请求 和数字签名 公钥 无法验证结果完整性 ！ 用户 

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

10 .数字签名链 服务器返回 d2 和 d3 作为结果 验证对象 VO: 1) Sig(d2), sig(d3); 2) 边界值 d1 和 d4 验证过程 边界值 d1 和 d4 在查询范围之外 签名 Sig(d2), 和 sig(d3) 是有效的 

11 .Merkle 哈希树 只有根节点签名 签名 d1 d2 d3 d4 

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

13 .Merkle 哈希树  客户端验证过程 签名的 N = h ( N1 | N2 ) 比较 N = h ( N1 | N2 ) N1 = h ( N11 | N12 ) N2 = h ( N21 | N22 ) N11 = h ( d1 ) N12 = h ( d2 ) d1 d2 

14 .数字签名链 vs. Merkle 哈希树 比较项目 Merkle Hash Tree 数字签名链 数据库创建速度 快 慢 空间占用量 小 大 客户端验证效率 高 低 验证过程 过于依赖根节点签名 与结果签名相关 快速定位被篡改记录 能够 不能 数据更新效率 低 高 

15 .查询验证中的安全和隐私问题 边界数据 数字签名的安全性 位置数据 

16 . Sigmod 2012 Authenticating Location-based Services without Compromising Location Privacy Haibo Hu, Jianliang Xu, Qian Chen, Ziwei Yang 

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

18 . 背景和动机 找到附近和餐厅和每 找到附近和餐厅和每 个餐厅的就餐人数 个餐厅的就餐人数 服务 LB 邻 S服 ， 近 移动客户端 务请在查询结果中添 务 在查询结果中添 服 求 签到 查询 加赞助的餐厅 加赞助的餐厅 结果 用户位置 位置数据拥有者 第三方服务提供商 

19 .安全问题和目标 安全问题 客户端可能会通过验证对象包含的的信息推测出用户 的位置信息 服务提供者为了自身利益可能会返回错误的查询结果 目标 在保护位置信息不泄露给客户端的前提下，对查询结 果进行验证 

20 .范围查询的验证 B+ 树索引位置，叶子节点的值按序排列 基于 Merkle Hash Tree 的验证技术 签名 验证目标 数据的真实性 root digest 数据的正确性 数据的完整性 digest …… digest digest digest u1|x1 u2|x2 u3|x3 u4|x4 … u8|x8 u9|x9 u10|x10 digestdigest digest digest digest digest digest 

21 .范围查询的验证 验证查询结果边界值 例子： 查询：范围在 [a, b] 之间的用户 结果 : （ u3, u4, …, u8, u9 ） 签名 root 验证： digest u2<a u3>=a u9<=b digest …… digest digest digest u10>b u1|x1 u2|x2 u3|x3 u4|x4 … u8|x8 u9|x9 u10|x10 digestdigest digest digest digest digest digest 

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

23 .查询验证摘要 

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

25 .R 树索引上的验证 边界验证 B+ 树：四个值 R 树：每个停止分裂的节点 

26 .谢谢 Q& A