Authenticating Location-based Services without Compromising ...

返回查询结果和验证对象VO; 数字签名链; Merkle 哈希树 ... 比较项目, Merkle Hash Tree, 数字签名链 ... B+树索引位置,叶子节点的值按序排列.
展开查看详情

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