基于数据分片的参与式感知系统隐私保护方法及系统

技术领域

本发明涉及的是一种信息安全技术领域的方法及系统，具体是一种基于数据分片的参与式感知系统隐私保护方法及系统。

背景技术

参与式感知系统（Participatory Sensing Systems）指利用众多移动通信设备的内置传感器件来进行数据的感知、收集、分析及反馈应用的新型数据服务模式。随着通信技术、传感器技术和移动设备技术的发展，内嵌众多感知器件的手持移动设备得到迅速普及，由此使得参与式感知系统成为当今研究热点。其主要面临两大难题：一是参与用户的隐私数据保护问题：感知数据通常都会带有空间、时间等信息，如果直接由感知用户发送到服务提供商，容易泄露当前用户隐私，比如身份信息、家庭及工作地点、旅游路线、甚至是生活方式及习惯等，反之，隐私信息无法得到有效保护将会直接影响参与者的参与热情，阻碍参与式感知系统的发展；二是缺少针对多媒体数据类型的参与式感知，例如对视频、音频及图像的获取、传输及处理存在很多问题。

基于以上的观察，本发明提出一种基于数据分片编码、交换传输思想的隐私信息保护机制，该机制适用于参与式感知系统，特别是针对多媒体数据类型具有较好的隐私保护效果，同时，该机制可以极大的提高系统整体的容错性能，降低移动设备的系统开销。

经过对现有技术的检索发现，中国专利文献号CN101808095，公开日2010-08-18，公开了一种分布式存储环境下的加密副本组织方法，将系统数据的管理单位数据块分成多个大小相等数据段，系统仍以块为单位进行管理，客户端以数据段为单位对数据进行加密，这样就能对数据块提供更细粒度的控制。由于数据块是被分段加密的，故各个密文数据段之间不具有相关性，可以被并行的加解密，避免了小数据量的读写就对整个数据块进行加解密带来的巨大开销；对于大数据量的读，将读请求进行分组，将不同的分组请求并行的发送到维护着被请求文件数据块副本的各个存储节点，并行读取各个分组，提高读数据的效率。该技术实现了在分布式存储环境下应用加密技术和副本技术，所提出的加密副本组织方法极大的提高了读写数据的效率。但该技术是基于分布式存储环境下、适用于大数量的一种加密手段，但对于具有高移动性、低数据处理能力、小数据量的参与式感知系统是完全不适用的。

发明内容

本发明针对现有技术存在的不足，提出一种基于数据分片的参与式感知系统隐私保护方法及系统，针对参与式感知系统当中用户隐私保护问题，采用对原始感知数据（特别针对多媒体数据）进行分片编码、交换传输的思想，将数据片传送到服务提供商（服务器端），达到隐私保护的目的，同时该机制增强了系统容错性能，降低了系统开销。

本发明是通过以下技术方案实现的：

本发明涉及一种基于数据分片的参与式感知系统隐私保护方法，包括以下步骤：

第一步、由移动设备获取原始感知数据，采用纠删码对原始数据进行分片编码，然后将经哈希函数加密后的移动设备用户标识与分片编码后的数据片进行非对称数据加密，产生用于传输的加密数据片。

第二步、将第一步生成的加密数据片保留一片并将其余数据片与周围用户进行交换，并在交换后向服务器传输所有加密数据片。

所述的交换包括：相遇交换和最小代价交换。

所述的相遇交换是指：所有者将其加密数据片依次发送给移动过程中遇到的其他用户，直到加密数据片生命周期结束，然后由接收到加密数据片的用户周期性地发送给服务器。

所述的最小代价交换是指：在保证尽可能小的系统开销的前提下选取加密数据片交换对象，即设在加密数据片生命周期内，用户a_i∈N会与|N(a_i)|个用户相遇，对于将要相遇的每一个用户a_j∈N(a_i)而言，p(a_j)表示a_j与a_i的相遇概率，c(a_j)表示a_j与a_i交换一片数据所需要承担的系统开销。

所述的相遇概率p(a_j)和系统开销c(a_j)通过历史数据和移动预测模型获得。

所述的移动预测模型是指：对于每个用户a_j∈N(a_i)，在保证尽可能小的系统开销前提下，选取一个子集作为其加密数据片的中继传输节点，并且满足下面的任意一个条件：

条件1：要求至少遇到m-1个用户（满足该条件的问题称之为MCT-EXP问题），即满足：

Objective：$>\min \underset{a_j\in N\left(a_i\right)}{\Sigma }\left(a_j\right)p\left(a_j\right)x_j$>

Subject to：$>\underset{a_j\in N\left(a_i\right)}{\Sigma }p\left(a_j\right)x_j\ge m-1,---\left(1\right);$>

$>x_j\in \left\{\mathrm{0,1}\right\},\forall a_j\in N\left(a_i\right)---\left(2\right).$>

上述约束条件（1）保证了用户a_i∈N至少遇到m-1个其他用户，约束条件（2）表示x_j取值范围，x_j＝1表示a_j被选为交换对象，反之则表示没有被选中。

条件2：要求遇到至少m-1个用户的概率至少为P，0≤P≤1（满足该条件的问题称之为MCT-PRO问题），即满足：

Objective：$>\min \frac{\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=m-1}{\Sigma }\left(\underset{a_j\in N\left(a_i\right)}{\Sigma }\left(c\left(a_j\right)x_j{y}_j\right)\underset{a_j\in N\left(a_i\right)}{\Pi }{p\left(a_j\right)}^{y_j}\right)}{\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=m-1}{\Sigma }\underset{a_j\in N\left(a_i\right)}{\Pi }{p\left(a_j\right)}^{y_j}};$>

Subject to：$>\underset{t=m-1}{\overset{\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k}{\Sigma }}\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=t}{\Sigma }\underset{a_j\in N\left(a_i\right)}{\Pi }(p{\left(a_j\right)}^{t_j}·{(1-p\left(a_j\right))}^{1-y_j})\ge P---\left(5\right);$>

$>x_j\in \left\{\mathrm{0,1}\right\},\forall a_j\in N\left(a_i\right)---\left(6\right).$>

上述约束条件（5）保证a_i遇见至少m-1个其他用户的概率至少为P，满足条件2的要求；为长度为|N(a_i)|的向量。

第三步、服务器接收到加密数据片之后通过构建数据片表实现对原始数据的重构，具体步骤包括：

3.1）根据收到的加密数据片，采用非对称解密技术以及对应第一步中用户的私钥，对加密数据片进行解密，得到标识信息和编码后数据片；

3.2）将标识信息和编码后数据片加入数据片表中，并判断当属于同一条原始数据的编码后数据片至少达到k片时，则采用与第一步对应的纠删码解码技术重构出该原始数据＜t,l,d＞；

3.3）将属于该原始数据的编码后数据片从数据片表中删除，并保存所重构出来的原始数据信息＜t,l,d＞，直至完成所有加密信息片的解密，得到所有原始感知数据。

本发明涉及一种实现上述方法的系统，包括：感知数据分片编码模块、数据片交换模块和数据偏解码重构模块，其中：感知数据分片编码模块与数据片交换模块相连并传输编码加密后数据片信息，数据片交换模块与数据偏解码重构模块相连并传输编码加密后数据片信息。

所述的感知数据分片编码模块包括：纠删码编码单元、标识信息生成单元、非对称加密单元，其中纠删码编码单元是对原始数据进行切分编码，标识信息生成单元是根据用户信息生成用于数据充足的唯一标识，非对称加密单元是对编码后数据片和标识信息进行加密，防止信息窃听。

所述的数据片交换模块包括：数据片交换单元，该单元负责确定数据片的转发对象集合，并将编码加密后的数据片转发给该集合对象。

所述的数据偏解码重构模块包括：非对称解密单元、纠删码解码重构单元，其中非对称解密单元与前面的非对称加密单元相对应，负责加密数据的解密，纠删码解码重构单元与前面的纠删码编码单元相对应，负责编码数据片的解码重组。

技术效果

本发明与现有技术相比，其优点包括：能够有效的保护参与式感知系统中用户的隐私信息，防范来自服务提供商和周围参与者的隐私窃取攻击，同时是第一个针对多媒体感知数据的隐私信息保护机制；其次，该方法可以极大的提高系统容错能力，保证系统较高的鲁棒性，同时减少系统通信开销和计算开销。

附图说明

图1为本发明基于数据分片隐私保护机制总体架构图。

图2为本发明中各个功能模块及单元关系示意图。

图3为实施例中TMU数据片交换策略示意图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例1

如图1所示，本实施例包括以下步骤：

第一步、数据分片编码

1.1）根据用户a_i∈N的感知数据＜t,l,d＞和编码率（k/m），采用纠删编码方法将感知数据分割为k片，然后编码产生m片感知数据块{r_ij|1≤j≤m}，其中：a_i为编号为i的用户，N为所有用户的集合，＜t,l,d＞代表一条时间为t、位置为l、内容为d的感知数据，k是指：纠删码技术将原始数据切分成k片；m是指：k片数据经过纠删码编码后产生的数据片数，且k≤m；k/m表示编码率；r_ij表示用户a_i的第j片编码后数据片；

在本实施例中纠删码采用RS码或Tornado码实现；

1.2）采用加密哈希算法对每个用户a_i生成唯一对应的标识信息tag，即tag←H(i,nonce)，其中：H()为哈希加密函数，i为用户a_i的编号，nonce为[0,1]之间的随机数；

1.3）采用非对称加密算法对步骤1.1得到的感知数据片{r_ij|1≤j≤m}和加密用户标识tag进行加密，生成用于传输的加密数据片，即r'_ij＝ENCRYPT(r_ij||tag,KEY_pub)，其中ENCRYPT(·,·)为非对称加密函数，||为字符串连接操作，KEY_pub为加密公钥，r'_ij为数据片r_ij对应的加密之后的数据片。

第二步：数据片交换传输：为了防止服务提供商直接识别数据所有者的身份信息，从而泄露用户隐私信息，将第一步生成的加密数据片保留一片并将其余数据片与周围用户进行交换，并在交换后向服务器传输所有数据片。

在本实施例中，提出了两种数据片交换策略，即相遇交换（TMU，Transfer on Meet Up）和最小代价交换（MCT，Minimal Cost Transfer）。

所述的相遇交换是指：所有者将其加密数据片依次发送给移动过程中遇到的其他用户，直到加密数据片生命周期结束，然后由接收到加密数据片的用户周期性地发送给服务器。

如图3所示，形象地展示了TMU数据交换策略的基本思想：设（图3上）用户A从住所行进至办公室，用户A的设备目前存储有三片加密的待传输数据片，并且A在前进过程中依次与B、C、D在T1、T2、T3时刻相遇；则根据TMU交换策略（图3下），T1时刻A发送给B数据片A1，由于B无数据片可供交换，故T1时刻后A剩余2片，B得到1片A的加密数据片，依次类推。

虽然TMU策略可以很好的解决数据片交换问题，但是TMU仍是一种比较盲目的交换对象选择策略。现实环境中，不同的移动设备自身存在较大的差异（比如能耗、带宽、传输时间、传输费用等），故不同的移动设备在交换同一数据片时，可能导致不同的系统开销（统称为cost）。在这种情况下，TMU交换策略会造成极大的系统cost浪费，由此本实施例中采用了最小代价交换，所述的最小代价交换是指：选取数据片交换对象的同时，能够保证尽可能小的系统开销，即设在数据片生命周期内，用户a_i∈N会与|N(a_i)|个用户相遇；对于每一个用户a_j∈N(a_i)均具有两个属性p(a_j)和c(a_j)，其中p(a_j)表示a_j与a_i相遇的概率，c(a_j)表示a_j与a_i交换一片数据所需要承担的系统开销，在本发明中p(a_j)和c(a_j)可通过历史数据和已有的移动预测模型（Mobility prediction model）获得。

由此，MCT策略的目标可表述为：对于每个用户a_j∈N(a_i)，在保证尽可能小的系统开销前提下，选取一个子集作为其加密数据片的中继传输节点，并且满足下面条件之一：

条件1：要求至少遇到m-1个用户；满足该条件的问题称之为MCT-EXP问题；

条件2：要求遇到m-1个用户的概率至少为P(0<=P<=1)，满足该条件的问题称之为MCT-PRO问题；

下面针对以上两个问题提出相应的解决方案：

MCT-EXP问题解决方案

MCT-EXP问题可形式化为0-1整数规划问题，建模如下：

Objective：$>\min \underset{a_j\in N\left(a_i\right)}{\Sigma }\left(a_j\right)p\left(a_j\right)x_j$>

Subject to：$>\underset{a_j\in N\left(a_i\right)}{\Sigma }p\left(a_j\right)x_j\ge m-1,---\left(1\right);$>

$>x_j\in \left\{\mathrm{0,1}\right\},\forall a_j\in N\left(a_i\right)---\left(2\right).$>

上述约束条件（1）保证了用户a_i∈N至少遇到m-1个其他用户，约束条件（2）表示x_j取值范围，x_j＝1表示a_j被选为交换对象，反之则表示没有被选中。

由于上述MCT-EXP问题与传统背包问题极为相似，故可以归约到0-1背包问题，归约结果如下：

Objective：$>\min \underset{a_j\in N\left(a_i\right)}{\Sigma }c\left(a_j\right)p\left(a_j\right)(1-x_j);$>

Subject to：$>\underset{a_j\in N\left(a_i\right)}{\Sigma }p\left(a_j\right)(x-x_j)\le \underset{a_j\in N\left(a_i\right)}{\Sigma }p\left(a_j\right)-(m-1),---\left(3\right);$>[0034]$>x_j\in \left\{\mathrm{0,1}\right\},\forall a_j\in N\left(a_i\right)---\left(4\right).$>

至此，MCT-EXP问题完全转化为0-1背包问题，由于该问题已有成熟的Fully PolynomialTime Approximation Scheme(FPTAS)算法，可以在多项式时间内求得较好的近似解，故此处不再详细叙述。

MCT-PRO问题解决方案：尽管MCT-EXP问题可以找到FPTAS算法解决问题，但是MCT-EXP问题本身存在缺陷，因为其不能保证用户ai与其他至少m-1个用户相遇的概率，即不能满足条件2。因此，提出针对MCT-PRO问题的优化策略，使得用户ai遇见其他m-1个用户的概率至少为P。

MCT-PRO问题可形式化表示如下：

Objective：$>\min \frac{\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=m-1}{\Sigma }\left(\underset{a_j\in N\left(a_i\right)}{\Sigma }\left(c\left(a_j\right)x_j{y}_j\right)\underset{a_j\in N\left(a_i\right)}{\Pi }{p\left(a_j\right)}^{y_j}\right)}{\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=m-1}{\Sigma }\underset{a_j\in N\left(a_i\right)}{\Pi }{p\left(a_j\right)}^{y_j}};$>

Subject to：$>\underset{t=m-1}{\overset{\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k}{\Sigma }}\underset{\overrightarrow{y:}\underset{a_k\in N\left(a_i\right)}{\Sigma }{x}_k{y}_k=t}{\Sigma }\underset{a_j\in N\left(a_i\right)}{\Pi }(p{\left(a_j\right)}^{t_j}·{(1-p\left(a_j\right))}^{1-y_j})\ge P---\left(5\right);$>

$>x_j\in \left\{\mathrm{0,1}\right\},\forall a_j\in N\left(a_i\right)---\left(6\right).$>

上述约束条件（5）保证ai遇见至少m-1个其他用户的概率至少为P，满足约束条件（2）的要求；为长度为|N(a_i)|的向量，约束条件（6）与约束条件（2）、（4）相同。

经过分析，上述问题为NP难问题，无法在多项式时间内求的最优解，由此提出一种多项式贪心算法解决MCT-PRO问题，该算法分为两个步骤完成，步骤一称为发现临界用户，步骤二称为确定目标集合，具体可描述如下：

首先，判断条件|N(a_i)|＜m-1是否成立，若成立，则说明集合元素个数少于m-1，无法满足条件2的要求，程序停止，算法无解，其中|N(a_i)|表示可能与用户a_i相遇的用户个数；

否则，对于集合N(a_i)元素按照p(a_j)/c(a_j)降序排序得到序列对β序列采用动态规划算法，找出β序列中第一次使得约束条件（5）得到满足的前α个元素；由于β序列中前α个元素满足（5），分析可知，前γ（γ≥α）个元素也一定满足约束条件（5），记α为临界数，a'_α记为临界用户。

上述的临界用户发现算法可确定临界用户a'_α，则对于任意包含β序列前个元素的集合，均可作为MCT-PRO问题的可行解。下面是基于临界值α提出的目标集合确定算法，用来确定目标集合的规模，即γ的值，使得MCT-PRO问题的目标函数最小。

为确定目标集合规模，将用户集合N(a_i)、集合元素相遇概率和系统开销以及序列和临界用户a'_α作为算法输入，采用动态规划的思想，找出使得MCT-PRO问题目标函数值最小的γ（γ≥α），并取序列β的前γ个元素加入目标集合F。该算法是一种多项式时间贪心算法，通过该算法可确定出使得系统开销最小的数据片交换对象集合。

第三步：数据片解码重构：原始数据在经过分片编码和交换传输阶段之后，最终汇聚到服务提供商（服务器）。对于每条原始数据，服务器接收到至少k片数据之后就可以成功重构出原始数据。本步骤中为所有收到的数据片在内存空间维护一张数据表(Cache table T)，作为重构算法的输入，具体步骤包括：

3.1）根据收到的加密数据片，采用非对称解密函数以及对应第一步中用户的私钥，对加密数据片进行解密，得到标识信息和编码后数据片；

3.2）将标识信息和编码后数据片加入数据片表中，并判断当属于同一条原始数据的编码后数据片至少达到k片时，则采用与第一步对应的纠删码解码技术重构出该原始数据＜t,l,d＞；

3.3）将属于该原始数据的编码后数据片从数据片表中删除，并保存所重构出来的原始数据信息＜t,l,d＞，直至完成所有加密信息片的解密，得到所有原始感知数据。

与现有技术相比，本实施例所具有的技术性能的进步以及实验数据指标的提升表现在：首先，本实施例极好的保护了参与式感知系统参与者的隐私信息，达到k-anonymity的保护效果，其次，本实施例可良好的运行在移动终端设备之上，极大的增强了参与式感知系统的容错能力，同时，通过算法的设计和优化，有效的降低了移动设备的系统开销。