一种满足差分隐私的轨迹数据安全存储和发布方法 - 吴万青, 赵永新, 王巧, 底超凡.pdf
免费下载
计 算 机 研 究 与 发 展
DOI
:
１０．７５４４∕issn１０００Ｇ１２３９．２０２１．２０２１０５８９
JournalofCom
p
uterResearchandDevelo
p
ment ５８
(
１１
):
２４３０ ２４４３
,
２０２１
收稿日期
:
２０２１
－
０６
－
１０
;
修回日期
:
２０２１
－
０７
－
３０
基金项目
:
河北省高等学校科学技术研究项目
(
ZD２０２１０１１
);
河北省自然科学基金项目
(
F２０１９２０１３６１
)
Thisworkwassu
pp
ortedb
y
theScienceand Technolo
gy
Research Pro
j
ectofHebeiHi
g
herEducation
(
ZD２０２１０１１
)
andthe
NaturalScienceFoundationofHebeiProvince
(
F２０１９２０１３６１
)
．
通信作者
:
赵永新
(
z
y
x４２３７＠１６３．com
)
一种满足差分隐私的轨迹数据安全存储和发布方法
吴 万 青
赵 永 新
王
巧
底 超 凡
(
河北大学网络空间安全与计算机学院
河北保定
０７１０００
)
(
河北省高可信信息系统重点实验室
(
河北大学
)
河北保定
０７１０００
)
(
wuwan
q
in
g
８８８８＠１２６．com
)
ASafeStora
g
eandReleaseMethodofTra
j
ector
y
DataSatisf
y
in
g
Differential
Privac
y
Wu Wan
q
in
g
,
ZhaoYon
g
xin
,
Wan
g
Qiao
,
andDiChaofan
(
Colle
g
eo
f
C
y
berSecurit
y
andCom
p
uter
,
HebeiUniversit
y
,
Baodin
g
,
Hebei
０７１０００
)
(
Ke
y
Laborator
y
o
f
Hi
g
hTrustedIn
f
ormationS
y
stemin HebeiProvince
(
HebeiUniversit
y
),
Baodin
g
,
Hebei
０７１０００
)
Abstract Inrecent
y
ears
,
althou
g
hlocationＧbasedservicesoftwarefacilitates
p
eo
p
leslife
,
itbrin
g
s
theriskof
p
rivac
y
leaka
g
e．Inordertosolvethis
p
roblem
,
we
p
ro
p
oseatra
j
ector
y
data
p
ublishin
g
methodthatisbasedonthenoise
p
refixtreestructure．Inthefirst
p
art
,
thetra
j
ector
y
e
q
uivalence
classisconstructedaccordin
g
tothes
p
aceＧtimecharacteristicsofthetra
j
ector
y
,
andthenthelocus
location
p
ointsaredividedb
y
Hilbertcurvetoobtainthecentral
p
ointsofthedividedre
g
ion．Finall
y
,
theobtained central
p
ointsareconver
g
edintothe new tra
j
ector
y
,
so astoreducethes
p
atial
com
p
lexit
y
．Thesecond
p
artbuildsa
p
refixtreeforstorin
g
location
p
ointsaccordin
g
tothenatureof
the
p
refixtree
,
andstoresthea
gg
re
g
atedtracklocation
p
ointsintothe
p
refixtree
,
whichcanim
p
rove
q
uer
y
efficienc
y
．Inthethird
p
art
,
inorderto
p
rotectthesensitiveinformationstoredinthenodes
,
thisarticlewilladdLa
p
lacenoisetothenodesofthe
p
refixtree
,
sothatsafertra
j
ector
y
datacanbe
released．Considerin
g
thatthe
p
ublisheddatashould beofhi
g
havailabilit
y
,
this
p
a
p
erusesthe
arithmetic
p
rivac
y
bud
g
etallocation methodtoaddLa
p
lacenoisetothenodedata
,
andlimitsthe
amountofnoiseb
y
thethresholdvalueofeachla
y
er
,
soastofinall
yp
ublishtra
j
ector
y
datawithhi
g
h
availabilit
y
satisf
y
in
g
thedifferential
p
rivac
y
model．Throu
g
htheex
p
erimentalverificationofrealdata
sets
,
andcom
p
arin
g
withtheexistin
g
NTPTal
g
orithm
,
our
p
ro
p
osedTDPPal
g
orithmislowerthan
theNTPTal
g
orithmindifferenterrorvalues
,
andcan
p
rovidebetter
p
rivac
yp
rotection．Itisverified
thattheal
g
orithm
p
ro
p
osedinthis
p
a
p
erim
p
rovesdataavailabilit
y
whileensurin
g
data
p
rivac
y
．
Ke
y
words differential
p
rivac
y
;
location
p
rivac
y
;
Hilbertcurve
;
p
refixtree
;
tra
j
ector
y
data
摘
要
近些年基于位置服务的软件便利人们生活的同时
,
也带来了隐私泄露的风险
．
针对这一问题
,
提
出一种基于噪 声 前 缀 树 结 构 的 轨 迹 数 据 发 布 方 法
．
首 先 根 据 轨 迹 时 空 特 性 构 建 轨 迹 等 价 类
,
利 用
Hilbert
曲线对轨迹位置点进行划分
,
得到划分区域的中心点
,
将得到的中心点聚合成新的 轨 迹
,
因此达
到减少空间复杂度的目的
．
然后构建前缀树
,
并将 聚 合的 轨 迹位 置 点存 入 到前 缀 树中
,
可以 有 效地 提 高
查询效率
．
最后为了保护节点中存储的敏感信息
,
利用等差隐私预算分配方式 对 前 缀 树 节 点 中 数 据 添 加
La
p
lace
噪声
,
保证轨迹数据的安全性的同 时也 提 高了 数 据可 用 性
．
通过 真 实数 据 集实 验 对比 已 有的 方
案
,
验证了所提出的算法在保证数据隐私性的同时
,
也提高了数据可用性
．
关键词
差分隐私
;
位置隐私
;
Hilbert
曲线
;
前缀树
;
轨迹数据
中图法分类号
TP３０９
随着互联网的快 速 发展
,
许多 电 子设 备 融入 现
实生活
,
例如智 能 手 机
、
智 能 手 环 等
．
但 是 在 享 受 大
数据便利的同时
,
也面临着隐私安全隐患
．
一些基于
位置 服 务
(
locationbasedservices
,
LBS
)
应 用 软 件
在用户未知情的情 况 下
,
采集 用 户的 地 理位 置 信息
并发布
,
不仅造成用户的位置隐私泄露
,
而且有可能
造成更多的敏感信息泄露
,
如用户的生活习惯
、
宗教
信仰等
．
据微软统计报告
,
有一半以上的用户担心自
己在使用基于
LBS
的应用 程序时 泄露自 己的 隐 私
．
因此在用户使用
LBS
时
,
如何实现位置轨迹数据的
安全分享与发布
,
保护 用 户的 个 人隐 私 成为 一 个 重
要问题
．
为解决位 置隐私 保护 这 一问 题
,
国内外 许多学
者纷纷置身于此问题 之中
．２００２
年
Sweene
y
等人提
出
K
Ｇ
匿名理论
[
１
]
．
文献
[
１
]
中定义了伪标 识符 和
K
Ｇ
匿名性
,
广泛 应 用 于 轨 迹 匿 名 和 隐 私 保 护
．２００３
年
Gruteser
等人将
K
Ｇ
匿名 的 理论 引 入 到 位 置 隐 私 保
护
,
提出一种空间位置隐藏方法
[
２
]
．
该方法的思 想是
通过空间隐藏方法隐藏单个用户与其他
K
－１
个用
户的地理位置使之 无 法区 分
,
但是 这 种方 法 必须 在
特定情形下才能实 现
,
所以 用 户不 能 根据 自 己的 需
求设置不同
K
值和需要隐藏的区域
．２００９
年
Chow
等人提出一种个性化
K
Ｇ
匿名模型
[
３
]
,
该方法是基于
用户出现在 隐藏 区域 相等 的概 率 下 提 出 的 一 种 模
型
,
但当用户出现的概率不等时
,
该模型不能很好地
反映用户隐私的保护程度
．
许多学者基于
KＧ
匿 名 模 型
,
相 继 提 出 了
K
Ｇ
匿
名模型的变体
．２００６
年
Wan
g
等人提出
(
X
,
Y
)
Ｇ
匿名
的概念
,
其中
X
,
Y
表示
２
个不 相 交的 属 性集 合
[
４
]
．
该方法主要在处理 敏 感数 据 时增 加 了限 制 条 件
,
在
属性组
X
中属 性 相同 的 情况 下
,
每一 组
X
均 需 要
对应至少
K
个 不 同 敏 感 属 性 组
Y
中 的 值
．２００７
年
Zhan
g
等人提出了
(
K
,
e
)
Ｇ
匿名模 型
,
目的 处 理敏 感
数值型数据
,
其思想 为在 每 个等 价 类中 元 组 个 数 不
能低于
K
个
,
每个等价类中的敏感属性的取值范围
不能低于 给定 的 阈 值
e
[
５
]
．Machanava
jj
hala
等 人 在
２００７
年提出
l
Ｇ
多样化模型
[
６
]
,
这一方 法是通 过熵 值
定义数据的多样性 及 变化 特 征
,
要求 在 准标 识 符相
同的情况下
,
敏感数据满足一定的多样化要求
,
保证
了敏感数据的多样 性
,
但是 敏 感数 据 如何 分 布该 方
法并 未 考 虑
．
而
t
Ｇ
贴 近 模 型 的 提 出 解 决 了 这 一 问
题
[
７Ｇ８
]
．
tＧ
贴近模型定义了一 个阈 值
t
,
并要 求 等价 类
中敏感属性的分布和整个表的敏感属性分布的距离
不能超过阈值
t
．
K
Ｇ
匿名模型优 势在 于攻 击者 能力 不超 过假 设
的前提下
,
能够以较 小 的代 价 保证 同 一等 价 类 中 记
录的不可区分性
,
但当攻击者能力超过假设范畴
,
攻
击者就可以进一步 区 分等 价 类中 不 同的 记 录
,
从而
实现去匿名化
,
造成 背景知 识攻 击
．
lＧ
多样 化 模型 虽
然在一定程度上处理了
KＧ
匿名缺乏多样性的问题
,
但是该模型仍不能 抵 御概 率 推理 攻 击
,
若敏 感 属性
分布不均匀时
,
导致 实现 该技 术 困难
．
tＧ
贴近 模 型作
为
lＧ
多样化模型 的改 进
,
解决 了 针对 敏 感 属 性 的 攻
击
,
但是仍无法抵御背景知识的攻击
,
而且面对不同
的敏感属性值时缺乏保护水平的灵活性
．
因此
,
Dwork
等 人 在
２００６
年 提 出 差 分 隐 私 技
术
,
很好 地 解 决 了 背 景 知 识 攻 击 及 推 理 攻 击 的 问
题
[
９Ｇ１０
]
．
该方法的主要思 想 是在 数 据库 中 添 加 噪 声
,
达到攻击者无法识别其中任意一个数据是否在该数
据库中
．
该技术是一种新的隐私保护技术
,
具有健强
的数学基础
,
可 以 提 供 严 谨 的 数 学 证 明
[
１１
]
．
差 分 隐
私技术的提出
,
受到广 大 隐私 保 护领 域 研 究 者 的 关
注
,
并广泛应用于支 持 隐私 保 护的 数 据挖 掘 和 数 据
发布领 域
[
１２
]
．２０１２
年
Andrés
等人 提 出基 于 位 置 的
差分隐私扩展模型
,
并生 成 一个 在 隐私 预 算范 围 内
不会受攻击的匿名 位置
[
１３
]
．
但是 由于 生 成的 匿 名位
置与用户的真实位 置 之间 的 距离 无 法预 测
,
所以 不
能保证
LBS
的 服 务 质 量
．２０１３
年
Dewri
等 人 利 用
Hilbert
分布的匿名集获得高质量服务
[
１４
]
．
但是匿名
位置和真实位置没有相似性
,
攻击者很容易区分开
．
２０１８
年
Gurso
y
等人提出一种 名为
DPＧStar
的轨迹
隐私保 护 框 架
[
１５
]
．
该 框 架 构 建 了 一 个 密 度 感 知 网
络
,
可以确保添加噪声之后满足差分隐私的需求
,
保
持数据的空间密度
,
并采 用 中值 长 度估 计 方法 保 护
１３４２
吴万青等
:
一种满足差分隐私的轨迹数据安全存储和发布方法
of 14
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论