基于统计差分的轨迹隐私保护

朱维军 1 游庆光 1 杨卫东 2 周清雷 1

1 (郑州大学信息工程学院 郑州 450001) 2 (河南工业大学信息科学与工程学院 郑州 450001)

(zhuweijun@zzu.edu.cn)

摘 要 随着车联网不断地发展,车联网为驾乘者提供便捷服务的同时,也带来了相应的隐私保护问题.轨迹数据发布将可能泄露用户位置隐私,从而危害用户人身安全;为改变已有差分隐私保护方法中添加随机噪音的弊端,提出一种基于统计差分隐私的轨迹隐私保护方法.车辆行驶轨迹具有Markov过程的特点,根据车辆轨迹的特征计算轨迹中位置节点敏感度;并根据位置敏感度,统计阈值和敏感度阈值添加适量Laplace噪音;使用平均相对误差评价轨迹数据的可用性大小.实验证实了基于统计差分隐私的轨迹隐私保护方法的可用性和有效性.

关键词 轨迹数据;差分隐私;Markov过程;数据发布;隐私保护

随着车联网的快速发展,车辆产生大量轨迹数据.在信息时代中,交通部门可以对大量的轨迹数据挖掘和分析,从而优化交通道路并减少交通事故等.轨迹数据中存在大量的敏感信息 [1-4] (用户ID、家庭地址、医院和学校等);若直接发布原始轨迹数据,攻击者可以对发布的轨迹数据进行挖掘分析,从而获取用户的敏感信息;用户隐私泄露将威胁到用户的人身安全,因此轨迹隐私保护至关重要.

轨迹数据发布的隐私保护技术主要有假数据法、抑制法和泛化法 [5] .其中 k -匿名 [6] l -diversity [7] 是基于泛化法的轨迹隐私保护方法中最常用的方法,但 k -匿名易受到一致性攻击和背景知识攻击; l -diversity易受到相似性攻击等.为解决其相关问题,2006年Dwork [8-9] 首次提出利用差分隐私保护解决基于背景知识的攻击等.

差分隐私 [9] 建立在坚实的数学基础上,并对隐私保护进行了严格的数学定义;确保差分隐私保护在攻击者拥有任意背景知识下仍能够保护用户隐私;其中,差分隐私保护模型的基本思想是对原始数据 [2,10] 、原始数据的转换数据或者统计结果 [1,11] 添加噪音来达到隐私保护效果;而对原始数据扰动将影响轨迹数据中位置的可用性,影响数据的挖掘和分析.现有基于统计的差分隐私保护方法 [11-12] 对统计结果添加随机噪音,但添加随机噪音不能有效控制噪音量和控制数据可用性.为解决差分隐私保护中添加随机噪音的弊端,本文对轨迹统计结果添加适量噪音实现隐私保护效果,同时确保数据的可用性.

1 相关工作

轨迹数据有2种类型 [13-16] ,本文使用以轨迹为数据库记录的轨迹数据库.目前,轨迹数据隐私保护相关研究如下,Abul等人 [17] 计算轨迹距离相近的 k 条轨迹构成匿名集,并发布 k 条轨迹对应采样点的匿名区域,实现轨迹隐私保护;孟小峰等人 [18] 遍历轨迹数据构建前缀树,并对前缀树进行剪枝和重构形成 k -匿名前缀树,遍历经过处理的 k -匿名前缀树得到 k -匿名轨迹数据,从而达到轨迹 k -匿名隐私保护效果.虽然轨迹 k -匿名方法是目前最常用并且简单的隐私保护方法,但基于知识背景的攻击将威胁到用户隐私泄露.

为解决轨迹 k -匿名隐私保护方法中存在的问题,Mir等人 [11] 首次将基于统计的差分隐私运用到轨迹数据中,通过对轨迹数据中轨迹统计构造成前缀树,并对其统计结果添加随机Laplace噪音实现差分隐私保护;而后Chen等人 [12] 为提高轨迹数据的可用性,提出自适应差分预算决定添加噪音量,但是该方法容易耗尽差分预算使差分隐私失效影响隐私保护等;Jiang等人 [14] 通过采样相应方向和距离的轨迹,进行差分隐私处理达到隐私保护的效果;Yang等人 [19] 根据 w -event privacy [20] 对其进一步改进优化为 l -trajectory privacy,通过自适应差分预算添加随机噪音,从而提高数据的可用性;Yu等人 [21] 提出一种高效的差分隐私保护方法实现无线网络数据轨迹的隐私保护.Hua等人 [2] 利用 k -means聚类轨迹中位置并通过指数机制实现最优泛化,然后应用添加随机Laplace噪音的差分隐私,构建成并发布噪音轨迹数据集,实现用户隐私保护,但这种轨迹隐私保护的方法不能解决轨迹数据集较大并且轨迹位置域大的问题.

为避免对原始轨迹数据直接添加噪音 [2,14,19,22] 影响数据的可用性;本文也是通过构建前缀树,并对其统计结果添加相应的Laplace噪音实现隐私保护;本文与文献[1,22]的不同之处:1)车联网中车辆的行驶轨迹具有Markov过程的特性,并根据其特性计算轨迹中位置节点的敏感度,通过敏感度控制噪音量;2)遍历轨迹数据库中完整轨迹,并统计轨迹数据的位置节点,从而确保轨迹数据的完整性和可用性;3)本文为确保经过差分隐私后的轨迹数据的安全性和可用性,使用轨迹统计阈值 θ 、敏感度阈值 μ 和极大敏感度阈值 μ m ,在确保实现差分隐私保护的情况下对轨迹数据添加适量噪音实现轨迹隐私保护,同时提高轨迹数据的可用性等.

2 预备知识

2 . 1 轨迹数据库

轨迹和轨迹数据集 [1-2,11,13,23] 的定义如下:

定义1 . 轨迹.轨迹中的位置节点 C i 是由时间和位置构成( ti , L i );轨迹 T 是由有限个位置节点组成:( t 1, L 1 )→( t 2, L 2 )→( t 3, L 3 )→…→( ti , L i );其中 T ( ti )= L i .每条轨迹代表车联网中车辆行驶的轨迹,作为轨迹数据库中的一条记录.车联网中车辆的轨迹形成轨迹数据库 D ={ T 1 , T 2 ,…, T | D | }.

表1是轨迹数据库样例,轨迹数据库中位置节点域 L ={ L 1 , L 2 , L 3 , L 4 };下面以该数据库为例具体阐述该隐私保护方法.

Table 1 Trace Database
表1 轨迹数据库

IDT(t1)→T(t2)→T(t3)→T(t4)1L1→L2→L32L3→L2→L4→L13L1→L24L1→L2→L35L3→L2→L4→L16L2→L1→L37L1→L2→L48L1→L2→L39L3→L1

2 . 2 位置敏感度

车联网中车辆的行驶轨迹具有Markov过程的特征,因此轨迹中位置节点的敏感度与当前位置节点发生的概率有关.

Markov过程.设{ T ( t ), t }的状态空间为 S ,如果对于任意的 n ≥2,任意的 t 1< t 2< t 3<…< tn ,在条件 T ( ti )= L i , L i S , i =1,2,…,| T |下,即:

P ( T ( t n )= L n | T ( t 1 )= L 1 ,…, T ( t n -1 )= L n -1 )=
P ( T ( t n )= L n | T ( t n -1 )= L n -1 ),

(1)

则称其是Markov过程.

定义2 . 位置节点敏感度 ω .指轨迹中发生在位置节点在泄露轨迹用户隐私的概率: ω = P s × P m ;其中 P m 是时刻 ti 下轨迹位置节点 C i T ( ti )= L i 状态时发生的概率:

P m = P ( L i | L 1 L 2 →…→ L i -1 )= P ( L i | L i -1 ),

(2)

P s 是车辆在当前轨迹中处于 C i -1 位置节点的敏感度.

2 . 3 差分隐私保护理论基础

差分隐私保护是基于数据失真的隐私保护技术,通过添加噪声实现差分隐私保护,同时确保扰动后的数据保持某些统计方面的性质,以便进行数据挖掘等操作 [24] .

定义3 . 差分隐私 [12,22,24-27] .设随机算法 A Pr [ z ]表示事件 z 的披露风险.对于任意差别至多为一个记录的数据集 D 1 D 2 ,若算法 A 在数据集 D 1 D 2 上任意输出结果 D 满足:

(3)

则称算法 A 满足 ε -差分隐私保护.其中, ε 为隐私预算; ε 与其隐私保护强度成反比.

定义4 . 全局敏感度.对任意一个函数 f : D 1 d 函数 f 的全局敏感度为

(4)

其中, 表示映射的实数空间, d 表示函数 f 的查询维度.

添加噪声技术是实现差分隐私保护重要机制;Laplace噪音机制 [28] 和指数噪音机制 [29] 是常用的2种实现差分隐私的噪音添加技术.本文使用Laplace噪音机制对轨迹数据库中位置节点的统计结果添加噪音.

Laplace噪音机制 [10] .Laplace噪音机制是对数值型的输出结果添加噪音实现差分隐私.添加的Laplace噪音服从Laplace分布,则Laplace概率密度函数为

Pr ( x | λ )= ×e -| x |/ λ

(5)

λ = λ 是由Δ f ε 所决定.对于任意一个函数 f : D 1 d ,算法 A 满足等式 A 满足 ε -差分隐私.

3 基于轨迹位置节点统计的差分隐私保护

3 . 1 Laplace机制噪音添加过程

Laplace机制是对输出为数值型的结果添加噪音.

Laplace机制噪音添加过程如下:

1) 生成服从Laplace分布的随机噪音.Laplace概率密度函数为: Pr ( x | λ )= ×e -| x |/ λ ,其中 λ = ,故Laplace累计分布函数为

F ( x )= Pr ( x | λ )d x =

0.5×[1+sgn( x )×(1-e -| x |/ λ )],

(6)

根据Laplace分布得到逆分布函数:

F -1 ( x )=- λ ×sgn( p -0.5)×
ln(1-2×| p -0.5|),

(7)

随机生成一个[0,1]的随机数 p ,通过逆分布函数计算 x ,故生成了服从Laplace分布的随机噪音 x .

2) 对原始数据添加噪音.Laplace噪音机制为 则本文根据位置节点敏感度 p ,通过敏感度的大小添加适量的噪音 x ,实现轨迹数据的差分隐私保护.故 A ( D 1)= f ( D 1)+ x .

3 . 2 基于轨迹位置节点统计的差分隐私保护方法

目前,许多研究是通过添加Laplace噪音机制实现差分隐私保护,文献[1]通过自适应计算差分预算控制噪音量,但其仍是随机添加的噪音,不能有效控制其噪音量.因此本文统计轨迹数据库中轨迹的位置节点,并根据车辆的轨迹具有的Markov过程特性计算轨迹中位置节点的敏感度;控制敏感度阈值和统计阈值保证轨迹数据的最大可用性.

实现基于统计的差分隐私保护方法步骤如下:

1) 构建基于位置节点统计的前缀树.通过对轨迹数据库中的轨迹遍历并统计位置节点,并构建轨迹前缀树,如图1所示.

2) 构建噪音前缀树.车联网中车辆的行驶轨迹具有Markov过程的特性,根据其特性计算轨迹中位置节点的敏感度;并根据轨迹中位置节点敏感度和敏感度阈值 μ 添加相应的Laplace噪音;算法1阐述了具体的构建过程.

3) 发布噪音轨迹数据.为提高轨迹数据安全性,运用文献[1]对添加噪音后的处理过滤技术等;设置轨迹统计阈值 θ ,通过阈值决定是否对噪音树剪枝;算法2将给出具体算法.

通过直接遍历轨迹数据库的轨迹构建轨迹数据前缀树,以表1轨迹数据库为例构建轨迹数据前缀树,如图1所示:

Fig. 1 Statistical prefix tree of trace data
图1 轨迹数据统计前缀树

通过轨迹数据前缀树计算轨迹数据中位置节点的敏感度;通过敏感度阈值 μ 和敏感度 ω 添加相应Laplace噪音,并生成噪音前缀树.算法1阐述了具体的实现过程.

算法1 . 构建噪音前缀树.

输入:通过遍历轨迹数据库并统计轨迹中位置节点构建的前缀树 PT μ μ m θ ε ,其中 μ 是敏感度阈值, μ m 是最大敏感度阈值;

输出:含有每个位置节点敏感度的前缀树 PT 1 .

① 初始化 Stack Stack . push ( PT ), ε 1 = ε / h

PT p =1;

N = Stack . top ();

PT ω =1/ PT c

⑤ While (! Stack . empty ( N ))

P m = ComputeMarkovP ( N );

P s = N parent ω

N ω = P m × P s

⑨ If N ω > μ And N ω < μ m Then

N c = N c +| laplace ( ω )|;

Else If N ω < μ

N c = N c + laplace ( ω );

Else

N c = θ

End If

End While

Return PT 1 .

算法1首先初始化轨迹前缀树根节点敏感度和差分预算;遍历构建成的轨迹前缀树,计算轨迹中节点的敏感度.通过函数 ComputeMarkovP ( N )计算位置节点 N 在时刻 t 发生的概率;并根据位置节点敏感度定义计算轨迹前缀树中位置节点敏感度.使用 laplace ( ω )噪音函数对轨迹中位置节点添加相应的Laplace噪音,实现差分隐私保护;其中 μ 是敏感度阈值, ω 是敏感度;根据 μ ω 控制噪音量.如图2是对表1轨迹数据库计算轨迹中位置节点的敏感度,并添加相应Laplace噪音,构建成的噪音前缀树.

Fig. 2 Noise prefix tree
图2 噪音前缀树

为提高添加噪音后的轨迹数据的安全性和可用性,由于构建轨迹前缀树需要具有一致性约束 [1,12] 条件.本文利用文献[1,12]的噪音过滤技术;并使用统计阈值 θ 对过滤过的噪音前缀树剪枝,然后将扰动后的数据发布.算法2阐述轨迹数据发布的过程.

算法2 . 发布噪音轨迹数据.

输入:噪音前缀树 PT 1 、统计阈值 θ

输出:发布数据 D 2 .

① 初始化 T , N , Stack

T = FilterNoisyTree ( PT 1 );

Stack . push ( T );

N = Stack . top ();

⑤ While(! Stack . empty ( N ))

⑥ If N c < θ Then

⑦ If N is leaf Then

⑧ 删除节点 N

⑨ Else

⑩ 删除以 N 为根的子树;

End If

End If

End While

Return D 2 .

其中 FilterNoisyTree ()使用了文献[1,12]过滤技术,算法2首先利用 FilterNoisyTree ( PT 1 )对噪音前缀树过滤实现轨迹前缀树的一致性约束;并根据设置的位置节点统计阈值 θ 对过滤后的噪音树剪枝,从而提高轨迹数据的安全性和可用性,并发布扰动后的轨迹数据.

4 实验分析

4 . 1 实验数据与环境

实验数据集来自UCI提供的数据集MSNBC真实数据集,MSNBC是一个公开可用的数据库.从MSNBC数据集中抽取200多条数据进行试验;其中数据特征为:轨迹数据中位置节点域大小为17、轨迹最大长度为324、抽取的数据集平均长度为5.4.

实验的硬件环境为:AMD CPU X5750 3.40 GHz,4.00 GB内存,操作系统为Microsoft Windows 7,算法均是由C++语言编程实现.

4 . 2 实验评估

为评价基于统计差分隐私轨迹保护方法(CDPM)的好坏,实验计算CDPM方法、文献[1]和文献[1]中方法的计数查询 [1,11,26,30] ,并比较分析3种方法的好坏.计数查询是计算噪音保护的数据库 的相对误差:

(8)

为了有效评价轨迹数据的可用性,使用平均相对误差评价轨迹数据库的可用度.

首先,在不同的差分预算下,实验运行50次,计算Prefix, N -Garm,CDPM这3种方法的平均相对误差.图3是不同的差分预算下Prefix, N -Garm,CDPM方法的平均相对误差的比较.图3显示在不同的差分预算下CDPM方法的平均相对误差比Prefix和 N -Garm方法的平均相对误差明显减小;由于Prefix方法是随机添加Laplace噪音,故噪音量比较大,平均相对误差大,而 N -Garm方法通过自适应改变差分预算,但并没改变随机添加噪音,减小了平均相对误差.随机添加噪音,不能有效地控制Laplace噪音量.因此CDPM方法通过位置节点敏感度添加适量Laplace噪音.实验表明在相同的差分预算下,CDPM方法既可以实现差分隐私保护,同时可以有效地降低平均相对误差,提高轨迹数据的可用性.

Fig. 3 Average relative error of three different methods of differential privacy protection
图3 3种不同差分隐私保护方法的平均相对误差

在实现差分隐私保护的情况下,图4和图5是轨迹数据通过CDPM方法显示不同的可用性;图4是差分预算 ε =0.2和统计阈值 θ =2情况下,平均相对误差随统计阈值增加而增大,同时轨迹数据可用性降低.由于 θ 不断增加,将可能剪枝更多的前缀树中的位置节点,从而影响轨迹的可用性.而图5是差分预算 ε =0.2和敏感度阈值 μ =0.5的情况下,其 平均相对误差在先减小而后增加最后趋于不变;当敏感度阈值与统计阈值相对应时,可以实现轨迹数据的最大可用性;而 μ 决定了对节点是否添加噪音, μ 越大添加的噪音越多,影响轨迹数据的可用性;故应适量地决定统计阈值和敏感度阈值,提高轨迹数据的可用性.

Fig. 4 Average relative error vs statistical threshold
图4 平均相对误差与统计阈值

Fig. 5 Average relative error vs sensitivity threshold
图5 平均相对误差与敏感度阈值

5

本文研究了车联网中轨迹数据隐私保护机制,提出了一种对轨迹统计结果扰动的差分隐私保护机制,即使攻击者拥有任何的背景知识仍能保护车辆的身份等隐私.我们的主要贡献在于:对轨迹中的位置统计进行定向而非随机扰动.如此即可实现轨迹发布的差分隐私保护,同时又可提高数据的可用性,这是使用新方法的益处.

参考文献

[1]Chen Rui, Fung B, Desai B, et al. Differentially private transit data publication: A case study on the montreal transportation system[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221

[2] Hua Jingyu, Gao Yue, Zhong Sheng. Differentially private publication of general time-gerial trajectory data[C] //Proc of IEEE ICC 2015. Piscataway, NJ: IEEE, 2015: 163-175

[3] Clarke R. Person location and person tracking-technologies, risks and policy implication[J]. Information Technology & People, 2001, 14(2): 206-231

[4] Zhou Changli, Ma Chunguang, Yang Songtao. Location privacy-preserving method for LBS continuous KNN query in road networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2628-2644 (in Chinese)(周长利, 马春光, 杨松涛. 路网环境下保护LBS位置隐私的连 续KNN查询方法[J]. 计算机研究与发展, 2015, 52(11): 2628-2644)

[5] Huo Zheng, Meng Xiaofeng. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830 (in Chinese)(霍峥, 孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报, 2011, 34(10): 1820-1830)

[6] Sweeney L. K-anonymity: A model for protecting privacy[J]. IEEE Security & Privacy Magazine, 2012, 10(5): 557-570

[7] Machanavajjhala A, Kifer D, Gehrke J. L-diversity: Privacy beyond k -anonymity[C] //Proc of the 29th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 66-92

[8] Dwork C. Differential privacy: A survey of results[G] //LNCS 4978: Proc of Int Conf on Theory and Applications of Models of Computation (TAMC 2008). Berlin: Springer, 2008: 1-19

[9] Dwork C. Differential Privacy[G] //LNCS 4052: Proc of the 33rd Int Conf on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12

[10] Quan Daiyong, Yin Lihua, Guo Yunchuan. Enhancing the trajectory privacy with Laplace mechanism[C] //Proc of IEEE TRUSTCOM’15. Piscataway, NJ: IEEE, 2015: 1218-1223

[11] Mir D, Isaacman S, Cáceres R, et al. Dp-where: Differentially private modeling of human mobility[C] //Proc of IEEE Big Data 2013. Piscataway, NJ: IEEE, 2013: 580-588

[12] Chen Rui, Acs G, Castelluccia C. Differentially private sequential data publication via variable-length n -grams[C] //Proc of ACM CCS’12. New York: ACM, 2012: 638-649

[13] Shao Dongxu, Jiang Kaifeng, Kister T, et al. Publishing trajectory with differential privacy: A priori vs a posteriori sampling mechanisms[C] //Proc of the 24th Int Conf on Database and Expert Systems Applications. New York: ACM, 2013: 357-365

[14] Jiang Kaifeng, Shao Dongxu, Bressan S, et al. Publishing trajectories with differential privacy guarantees[C] //Proc of the 25th Int Conf on Scientific and Statistical Database Management. New York: ACM, 2013: 12

[15] He Yunhua, Sun Limin, Yang Weidong, et al. Privacy preserving for node trajectory in VSN: A game-theoretic analysis based approach[J]. Journal of Computer Research and Development, 2014, 51(11): 2483-2492 (in Chinese)(何云华, 孙利民, 杨卫东, 等. 基于博弈分析的车辆感知网络节点轨迹隐私保护机制[J]. 计算机研究与发展, 2014, 51(11): 2483-2492)

[16] Wu Yingjie, Tang Qingming, Ni Weiwei, et al. A clustering hybrid based algorithm for privacy preserving trajectory data publishing[J]. Journal of Computer Research and Development, 2013, 50(3): 578-593 (in Chinese)(吴英杰, 唐庆明, 倪巍伟, 等. 基于聚类杂交的隐私保护轨迹数据发布算法[J]. 计算机研究与发展, 2013, 50(3): 578-593)

[17] Abul O, Bonchi F, Nanni M. Never walk alone: Uncertainty for anonymity in moving objects databases[C] //Proc of the 29th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2008: 376-385

[18] Huo Zheng, Meng Xiaofeng, Huang Yi. PrivateCheckin: Trajectory privacy-preserving for check-in services in MSNS[J]. Chinese Journal of Computers, 2013, 36(4): 716-726 (in Chinese)(霍峥, 孟小峰, 黄毅. PrivateCheckIn: 一种移动社交网络中的轨迹隐私保护方法[J]. 计算机学报, 2013, 36(4): 716-726)

[19] Yang Cao, Yoshikawa M. Differentially private real-time data release over infinite trajectory streams[C] //Proc of the 16th IEEE Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2015: 68-73

[20] Kellaris G, Papadopoulos S, Xiao Xiaokui, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1155-1166

[21] Yu Jiadi, Dong Xin, Luo Yuan, et al. Differentially private wireless data publication in large-scale WLAN networks[C] //Proc of the 21st Int Conf on Parallel & Distributed Systems. Piscataway, NJ: IEEE, 2015: 290-297

[22] Yu Dong, Kang Haiyan. Privacy protection method on time-series data publication[J]. Journal on Communications, 2015, 36(S1): 243-249 (in Chinese)(于东, 康海燕. 面向时序数据发布的隐私保护方法研究[J]. 通信学报, 2015, 36(S1): 243-249)

[23] Agard B. Mining public transport user behaviour from smart card data[J]. IFAC Proceedings Volumes, 2006, 39(3): 399-404

[24] Xiong Ping, Zhu Tianqing, Wang Xiaofeng. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122 (in Chinese)(熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[J]. 计算机学报, 2014, 37(1): 101-122)

[25] Chen Rui, Mohammed N, Fung B, et al. Publishing set-valued data via differential privacy[J]. VLDB, 2011, 4(4): 1087-1098

[26] Hay M, Li Chao, Miklau G, et al. Accurate estimation of the degree distribution of private networks[C] //Proc of the 9th Int Conf on Data Mining. Piscataway, NJ: IEEE, 2009: 169-178

[27] Lan Lihui, Ju Shiguang. Privacy preserving based on differential privacy for weighted social networks[J]. Journal on Communications, 2015, 36(9): 145-159 (in Chinese)(兰丽辉, 鞠时光. 基于差分隐私的权重社会网络隐私保护[J]. 通信学报, 2015, 36(9): 145-159)

[28] Dwork C, Mcsherry F, Nissim K. Calibrating noise to sensitivity in private data analysis[C] //Proc of the 3rd conf on Theory of Cryptography. New York: ACM, 2006: 265-284

[29] Mcsherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of IEEE FOCS’07. Piscataway, NJ: IEEE, 2007: 94-103

[30] Xiao Xiaokui, Bender G, Hay M, et al. iReduct: Differential privacy with reduced relative errors[C] //Proc of ACM SIGMOD’11. New York: ACM, 2011: 229-240 Zhu Weijun , born in 1976. PhD, associate professor. Senior member of CCF. His main research interests include information security, DNA computing and formal methods.

Trajectory Privacy Preserving Based on Statistical Differential Privacy

Zhu Weijun 1 , You Qingguang 1 , Yang Weidong 2 , and Zhou Qinglei 1

1 ( School of Information Engineering , Zhengzhou University , Zhengzhou 450001) 2 ( College of Information Science and Engineering , Henan University of Technology , Zhengzhou 450001)

Abstract With the continuous development of Internet of vehicles, Internet of vehicles provides the convenient services to drivers and passengers. But it also brings some new problems of privacy protection. The existing methods for trajectory data publishing may leak users’ location privacy. Thus, it may endanger the users’ personal safety. In order to avoid the drawbacks of adding random noise in the existing methods for differential privacy protection, we propose a novel method for trajectory privacy protection based on statistical differential privacy. At first, one can calculate the sensitivity of position nodes in vehicle traces according to the characteristics of traces since there are some characteristics of Markov process in vehicle traces. And then, one can add some moderate Laplace noises according to the sensitivity of position nodes, statistical threshold and sensitivity threshold. As a result, the new method is obtained. Evaluating the availability of the trajectory data through the average relative error, the experimental results verify the availability and effectiveness of the proposed approach for privacy preserving based on statistical differential privacy.

Key words trajectory data; differential privacy; Markov process; data publishing; privacy protection

收稿日期: 2016-08-22;

修回日期: 2016-12-09

基金项目: 国家重点研发计划项目(2016YFB0800100);国家自然科学基金项目(61202099,U1204608,U1304606,61572444);中国博士后科学基金项目(2015M572120,2012M511588)

This work was supported by the National Key Research and Development Program of China (2016YFB0800100), the National Natural Science Foundation of China (61202099, U1204608, U1304606, 61572444), and the China Postdoctoral Science Foundation (2015M572120, 2012M511588).

通信作者: 游庆光(757383480@qq.com)

中图法分类号 TP309

You Qingguang , born in 1990. Master. His main research interests include information security and vehicular ad hoc network.

Yang Weidong , born in 1977. PhD, associate professor. Senior member of CCF. His main research interests include vehicular ad hoc network and information security.

Zhou Qinglei , born in 1962. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include DNA computing, formal methods and information security.