Privacy Preserving kNN Query Protocol for Wireless Body Sensor Networks

文献[14]提出了一种基于ASPE的隐私保护安全kNN查询机制。假设数据采集单元采集的数据为集合D，D中数据有u个属性，表示为 ${A^1}, {A^2}, \cdots, {A^u}$ ，D中某条数据表示为 $({d^1}, {d^2}, \cdots, {d^u})$ 。查询条件是{q, k}, q与数据D在同一维度空间，即q $ = ({q^1}, {q^2}, \cdots, {q^u})$ 。kNN的查询结果是返回数据集合D中与查询条件q距离最近的k个数据。d_i和d_j $(1 \le i, j \le n, i \ne j)$ 为采集到的两条数据，需判断d_i和d_j哪一个距离查询条件q更近。

为了对数据进行隐私保护，D中所有病人的数据在上传给服务器前都要进行加密，用Enc(D)表示。为了保证kNN查询的安全，通常采用可恢复距离加密方法(distance-recoverable encryption, DRE)，该方法能通过密文Enc(D)计算d_i和d_j间的距离dist(d_i, d_j)。例如，使用密钥K分别对数据d_i和d_j进行加密，得到Enc(d_i, K)、Enc(d_j, K)，DRE可利用Enc(d_i, K)、Enc(d_j, K)计算得到dist(d_i, d_j)。

ASPE的基本思路是通过密文计算得到数据记录与查询条件之间的距离关系。设Enc(d, K_d)表示用密钥K_d加密后的采集数据d；Enc(q, K_q)表示用密钥K_q加密后的查询条件q；ASPE须满足条件：

可见， ${\mathit{\boldsymbol{d}}^{\rm{T}}}\mathit{\boldsymbol{Iq}} = ({\mathit{\boldsymbol{d}}^{\rm{T}}}\mathit{\boldsymbol{M}})({\mathit{\boldsymbol{M}}^{ - 1}}\mathit{\boldsymbol{q}})$ 。为了满足ASPE，加密过程为： ${\rm{Enc}}({{\boldsymbol{d}}_{\boldsymbol{i}}}, {{\boldsymbol{K}}_{\boldsymbol{d}}}) = {\mathit{\boldsymbol{M}}^{\rm{T}}}{{\boldsymbol{d}}_{\boldsymbol{i}}}$ ， ${\rm{Enc}}({\boldsymbol{q}}, {{\boldsymbol{K}}_{\boldsymbol{q}}}) = {\mathit{\boldsymbol{M}}^{ -1}}{\boldsymbol{q}}$ 。

假设d_i距离q比d_j更近，则不等式成立：

可见，ASPE能对 ${{\boldsymbol{d}}^{\rm{T}}}{\boldsymbol{q}}$ 的值进行隐私保护。每一个数据d对应的 $\left\| {\boldsymbol{d}} \right\|$ 是一个定值，为了方便后续计算，将 $\left\| {\boldsymbol{d}} \right\|$ 与数据d一同进行预存储。因此，加密前将数据d增加到u+1维，用向量 ${\boldsymbol{\hat d}}$ 表示，并将第u+1维设为 $ -0.5{\left\| {\boldsymbol{d}} \right\|^2}$ ，即 ${{\boldsymbol{\hat d}}^{\rm{T}}} = ({{\boldsymbol{d}}^{\rm{T}}}, -0.5{\left\| {\boldsymbol{d}} \right\|^2})$ ；为了使 ${\boldsymbol{q}}$ 与d在同一维度空间，将q也增加到u+1维，并将第u+1维设为1，即 ${\boldsymbol{\hat q}} = ({{\boldsymbol{q}}^{\rm{T}}}, 1)$ 。为了使每个q都不可估计，对其乘以随机系数r，表示为向量 ${\boldsymbol{\hat q}} = r({{\boldsymbol{q}}^{\rm{T}}}, 1)$ 。

数据d_i和d_j增加一维后得到向量 ${{\boldsymbol{\hat d}}_{\boldsymbol{i}}}{\rm{, }}{{\boldsymbol{\hat d}}_{\boldsymbol{j}}}$ ，使用ASPE对向量 ${\boldsymbol{\hat d}}$ 和 ${\boldsymbol{\hat q}}$ 加密，对于d_i, d_j通过计算 $({\rm{Enc}}{({{\boldsymbol{d}}_{\boldsymbol{i}}}, {{\boldsymbol{K}}_{\boldsymbol{d}}})^{\rm{T}}} -{\rm{Enc}}{({{\boldsymbol{d}}_{\boldsymbol{j}}}, {{\boldsymbol{K}}_{\boldsymbol{d}}})^{\rm{T}}}){\rm{Enc}}({\boldsymbol{q}}{\rm{, }}{{\boldsymbol{K}}_{\boldsymbol{q}}})$ 的值来判断d_i和d_j哪一个距离查询条件q更近。

使用矩阵M加密d_i和d_j，并使用 ${{\boldsymbol{M}}^{ -1}}$ 加密q，M是(u+1)*(u+1) 维的矩阵。可见加密后的的矩阵向量积与加密前相等：

${{\boldsymbol{\hat d}}_{\boldsymbol{i}}}, {{\boldsymbol{\hat d}}_{\boldsymbol{j}}}$ 和 ${\boldsymbol{\hat q}}$ 的相对距离：

可得出：

为了提高ASPE加密过程中数据的随机性，在上述ASPE机制中引入随机划分向量S，并根据S对d和q进行划分。S是由0和1组成的向量，由数据采集单元与数据用户共享，用于将d划分为 ${\boldsymbol{d'}}$ 和 ${\boldsymbol{d''}}$ 、将q划分为 ${\boldsymbol{q'}}$ 和 ${\boldsymbol{q''}}$ 。当S[i]=1时， ${\boldsymbol{d}}[i] = {\boldsymbol{d'}}[i] + {\boldsymbol{d''}}[i]$ ， ${\boldsymbol{q}}[i] = {\boldsymbol{q'}}[i] = {\boldsymbol{q''}}[i]$ ，其中 ${\boldsymbol{d'}}[i]$ 随机。当S[i]=0时， ${\boldsymbol{d}}[i] = {\boldsymbol{d'}}[i] = {\boldsymbol{d''}}[i]$ ， ${\boldsymbol{q}}[i] = {\boldsymbol{q'}}[i] + {\boldsymbol{q''}}[i]$ ，其中 ${\boldsymbol{q'}}[i]$ 随机。

对划分后的d和q，使用M₁和M₂加密。加密过程表示为： $E({\boldsymbol{d'}}) = {{\boldsymbol{M}}_1}^{\rm{T}}{\boldsymbol{d'}}$ ， $E({\boldsymbol{d''}}) = {{\boldsymbol{M}}_2}^{\rm{T}}{\boldsymbol{d''}}$ ， $E({\boldsymbol{q'}}) = {{\boldsymbol{M}}_1}^{ -1}{\boldsymbol{q'}}$ ， $E({\boldsymbol{q''}}) = {{\boldsymbol{M}}_2}^{ -1}{\boldsymbol{q''}}$ ，如式(6) 所述，加密后 ${{\boldsymbol{d}}^{\rm{T}}}{\boldsymbol{q}}$ 的值不被泄露。

显然，随着数据记录的增多ASPE的查询过程非常耗时。为此，本文提出一种基于Rtree构建的桶划分索引——BRtree，该索引能有效提高查询效率。

图 1为一个Brtree结构，它是一棵二维满二叉树，每个节点对应一个分桶。根节点所在层记为第一层，树的第一层分辨器对应第一个数据维度，即j=0 mod 2；树的第二层对应第二个数据维度，即j=1 mod 2。非叶子节点对应的桶B₁、B₂、B₃中保存了节点的最小边界值 ${V_{n -l}}$ 和最大边界值 ${V_{n -h}}$ (n=1, 2, 3)，叶子节点对应的桶B₄、B₅、B₆、B₇中不仅保存了节点的最小边界值 ${V_{n -l}}$ 和最大边界值 ${V_{n -h}}$ (n=4, 5, 6)，还保存了节点的数据集合 ${D_4}, {D_5}, {D_6}, {D_7}$ 。子节点个数满足 ${2^{h -1}}$ ，h=3。

假设数据采集单元C={C₁, C₂, …, C_n}采集的数据集合是D={D₁, D₂, …, D_n}, $D \subseteq {D_R}$ 。假设叶子节点对应的分桶大小为m，即叶子节点对应分桶中数据集合D所包含的数据个数最大为m。下面介绍BRtree的创建过程。

1) 根据 ${D_R}$ 创建BRtree索引

创建过程如图 2所示，B₁表示初始分桶根节点，B₁上下界{V₁, V₂}分别是数据集合D_R中的最小边界值和最大边界值。树的第一层分辨器对应第一维数据，记作j=0 mod 2。对分桶B₁在第一维数据上进行折半划分，得到分桶B₂={V₁, V₃}和B₃={V₄, V₂}。再将B₂和B₃分别按照分辨器j=1 mod 2进行折半划分，得到分桶B₄, B₅, B₆, B₇。每划分一个数据维度，树的高度增加一层。按照上述方法递增分辨器循环每一个数据维度对节点进行折半划分，直到分桶中的数据个数小于或等于m。对每一个分桶使用ASPE机制进行加密得到[B_i]={E(V_l), E(V_h)}，并将加密后的BRtree分桶索引上传到服务器。

2) 将采集数据插入BRtree分桶中

假设传感器单元C采集的数据集合D={d₁, d₂, …, d_n}。首先，将D中的数据逐个放置到满足边界值范围的相应叶子节点分桶中。分桶B_i中的数据是{d₁, d₂, …, d_m'}， $0 \le m' \le m$ 。为采集数据找到相应的分桶后，对分桶中的数据使用ASPE进行加密，记作E (B_i)={E(d₁), E(d₂), …, E(d_m)}。将E(B_i)发送至服务器并存储在相应的分桶中。因此，叶子节点的分桶B_i中除了包含上下边界值[B_i]={E(V_l), E(V_h)}，还包含了当前分桶中的加密数据E(B_i)={E(d₁), E(d₂), …, E(d_m)}。所有的叶子节点构成的桶集合表示为：B_leaf={B_{l_1}, B_{l_2}, …, B_{l_t}}，叶子节点B_{l_i} $(1 \le i \le t)$ 中的数据为B_{l_i}={d₁, d₂, …, d_m}；所有的非叶子节点构成的桶表示为：B_node={B_{n_1}, B_{n_2}, …, B_{n_z}}；创建的BRtree共h层，第c $(1 \le c \le h -1)$ 层包含y个桶节点，c层构成的桶集合为B_l=c={B₁, B₂, …, B_y}。然后，数据采集单元将创建好的BRtree索引B={[B_{n_1}], [B_{n_2}], …, [B_{n_z}], [B_{l_1}], [B_{l_2}], …, [B_{l_t}]}和E(B)={E(B_{l_1}), E(B_{l_2}), …, E(B_{l_t})}发送至服务器。

执行一次查询q时，首先，从根节点开始递归BRtree的每一层，即c=0, 1, …, h−1。计算查询q到B_l=c={B₁, B₂, …, B_y}中每一个非叶子节点B_x(B_x $ \in $ B_l=c)的边界距离参数：最小边界距离dist_min(B_x, q)、最大边界距离dist_max(B_x, q)和最小最大边界距离dist_{min_max}(B_l=c, q)。其中，最小边界距离dist_min(B_x, q)是查询条件q距离当前节点上界和下界的最小值，即dist_min(B_i, q)=min{dist(B_{i_low}, q), dist(B_{i_high}, q)}；同理，最大边界距离dist_max(B_i, q)=max{dist(B_{i_low}, q), dist(B_{i_high}, q)}；此外，还需计算查询条件距离当前层所有节点的最小最大边界距离dist_{min_max}(B_l=c, q)，表示该层节点中距离查询条件q的最大边界距离中的最小值，即dist_{min_max}(B_l=c, q) = min{dist_max(B₁, q), dist_max(B₂, q), …, dist_max(B_y, q)}。

然后，根据计算得到的边界距离参数进行剪枝。当且仅当dist_min(B_x, q) > dist_{min_max}(B_l=c, q)时，B_x节点所在的分枝将被剪去。图 3为一个BRtree分枝节点，该节点包含的两个非叶子的桶节点分别是B_a和B_a+1，它们所在的层是c。当执行查询q时，计算得q到B_a的最大距离是该层的最小最大距离，即dist_{min_max}(B_l=c, q)=dist_max(B_a, q)。被查询的当前桶是B_a+1，计算q到B_a+1的最小距离大于该层节点的最小最大距离：dist_min(B_a+1, q) > dist_{min_max}(B_l=c, q)，根据上述剪枝条件，将删除桶节点B_a+1及其孩子节点。

为了防止数据用户滥用病人医疗数据导致隐私信息的泄漏，本文引入可信第三方实体，实现对病人信息的访问权限控制与迁移。

可信第三方实体根据病人密钥和其责任医生密钥，生成该病人数据的访问权限密钥，并将密钥分配给服务器。服务器只有从可信第三方获得正确权限密钥，才能访问病人的医疗数据，并为授权用户提供正确的查询结果。一旦用户的责任医生发生更换，原来的权限密钥将会失效，服务器须从可信第三方获取新的权限密钥，同时新责任医生被授权。

访问权限控制如图 4所示，病人P持有密钥M_η，其责任医生A所持密钥N_a，此时可信第三方根据病人P的密钥和其责任医生A的密钥生成权限密钥L_ηa。当病人P更换为持有密钥N_b的责任医生B后，可信第三方生成病人P和新责任医生B的权限密钥L_ηb，并将其发送至服务器。此时，医生B被授予访问病人P的医疗数据权限，同时医生B能够通过服务器查询到正确的结果，医生A的访问权限L_ηa失效，访问权限被撤销，无法查询到正确的结果。

本文在ASPE机制中引入访问权限控制过程，其数据的流动过程如图 5所示。数据采集单元C_η的密钥是{M_η1, M_η2}，C_η采集的数据向量是d_η，对划分后的数据向量 ${\boldsymbol{d}}{\eta ^\prime }, {\boldsymbol{d}}{\eta ^{\prime \prime }}$ 通过ASPE进行加密，得到 $E({\boldsymbol{d}}\eta) = \{ E({\boldsymbol{d}}{\eta ^\prime }), E({\boldsymbol{d}}{\eta ^{\prime \prime }})\} $ ，其中， $E({\boldsymbol{d}}{\eta ^\prime }) = {\boldsymbol{M}}\eta {{\rm{1}}^{\rm{T}}}{\boldsymbol{d}}{\eta ^\prime }$ ， $E({\boldsymbol{d}}{\eta ^{\prime \prime }}) = {\boldsymbol{M}}\eta {2^{\rm{T}}}{\boldsymbol{d}}{\eta ^{\prime \prime }}$ 将其发送至服务器。

服务器接收到数据采集单元C_η发送的加密数据E(d_η)后，使用密钥L_η1和L_η2分别对 $E({\boldsymbol{d}}{\eta ^\prime })$ 和 $E({\boldsymbol{d}}{\eta ^{\prime \prime }})$ 进行加密，其中， ${\boldsymbol{L}}\eta 1 = {\boldsymbol{M}}\eta {1^{ -1}}{\boldsymbol{N}}1$ , ${\boldsymbol{L}}\eta 2 = {\boldsymbol{M}}\eta {2^{ -1}}{\boldsymbol{N}}2$ ，加密后表示为 $\{ {\rm{ \mathsf{ δ} }}(E({\boldsymbol{d}}{\eta ^\prime })), {\rm{ \mathsf{ δ} }}(E({\boldsymbol{d}}{\eta ^{\prime \prime }}))\} $ ，其中 ${\rm{ \mathsf{ δ} }}(E({\boldsymbol{d}}{\eta ^\prime })) = E({\boldsymbol{d}}{\eta ^\prime }){\boldsymbol{L}}\eta 1$ ， ${\rm{ \mathsf{ δ} (}}E({\boldsymbol{d}}{\eta ^{\prime \prime }})) = E({\boldsymbol{d}}{\eta ^{\prime \prime }}){\boldsymbol{L}}\eta 2$ 。

授权用户执行一次查询q时，用户密钥为{N₁, N₂}。用户使用密钥N₁和N₂对划分后的查询向量 ${\boldsymbol{q'}}{\rm{, }}{\boldsymbol{q''}}$ 分别进行加密，得到 $E({\boldsymbol{q'}}) = {\boldsymbol{N}}{1^{ -1}}{\boldsymbol{q'}}$ ， $E({\boldsymbol{q''}}) = {\boldsymbol{N}}{2^{ -1}}{\boldsymbol{q''}}$ 。用户将加密后的查询条件 $\{ E({\boldsymbol{q'}}), E({\boldsymbol{q''}}), k\} $ 一并发送至服务器。

服务器根据已有的加密数据，对授权用户发送的查询条件进行计算，得到满足条件的k个查询结果E(d_res)={E(d_i), E(d_i+1), …, E(d_i+k)}, E(d_res) $ \in $ E(d_η)，将结果E(d_res)发送给授权用户，用户使用密钥{N₁, N₂}解密得到明文信息。

假定某传感单元采集了n个u维数据，BRtree剪枝后剩余计数α。表 1给出了本文协议在最坏情况下的计算复杂度、通信开销，及空间复杂度。

本文提出的协议能够有效保护数据隐私。1) 假设存储节点被妥协，攻击者没有加密密钥，仅通过存储节点存储的密文数据来计算明文数据是十分困难的。2) 无线体域网络中数据维数大，未知量计数远超已知密文信息的维度。因此，当暴露部分明文数据记录、密文索引信息时，攻击者仍无法计算出密钥，也无法从密文中获取有用的明文信息。

实验数据来自移动健康数据集，采集了10名志愿者在进行不同体育活动时的生命体征数据记录。数据集共包含10个传感器单元采集的23维属性数据文件，每个文件数据量在10~15万，将数据划分为不重叠的周期T，每10分钟为一个周期。

图 6为创建索引时间开销随数据维度u的变化曲线。其中m=200，k=50。随u由13~23维递增，ASPE索引创建时间从0.41~0.88 s递增，BRtree索引创建时间从0.49~0.97 s递增，BRtree的平均创建索引时间是ASPE的1.15倍。

图 7为创建索引时间开销随时间周期T的变化曲线。其中u=23, m=200, k=50。BRtree的创建索引时间从0.21~2.18 s递增，ASPE的创建索引时间从0.17~1.73 s递增，BRtree的平均创建索引时间是ASPE的1.14倍。

图 8为查询时间开销随数据维度u的变化曲线。其中m=200，k=50。ASPE查询过程各周期查询时间从7.60~10.77 s递增，BRtree查询过程各周期查询时间从5.30~6.20 s变化。BRtree查询时间比ASPE查询时间加快了0.47倍。

图 9为查询时间开销随时间周期的变化曲线。其中u=23, m=200, k=50。ASPE各周期查询时间从2.01~22.62 s递增，BRtree查询时间从0.98~11.91 s递增。BRtree查询查询时间比ASPE加快了0.48倍。

图 10为查询时间开销随时间周期的变化曲线，其中u=23, k=30。图中4条曲线分别是ASPE和BRtree索引分桶大小为m=100, 200, 300时的查询时间曲线。m=200比m=100查询时间加快了0.21倍，m=300比m=100查询时间加快了0.48倍。

图 11为查询时间随k的变化曲线，其中u=23, m=200。图中3条曲线分别表示TimeSlot=1, 5, 10时查询时间的变化曲线。可见，k增加对查询时间的影响非常小。TimeSlot=1, 5, 10的平均查询时间分别是1.03, 5.71, 11.87 s。

在无线体域网中实现了隐私保护安全的kNN查询协议。通过ASPE机制，在服务器既不知道数据真实值，也不知道查询条件的情况下实现了安全的kNN查询机制，该机制能够抵抗已知部分明文攻击。此外，通过基于R树的桶划分索引BRtree，采用剪枝策略有效地提高了kNN的查询效率。最后，根据ASPE机制特征，从ASPE加密矩阵中分解出权限矩阵，通过引入可信第三方，解决了无线体域网中数据级访问权限控制以及访问权限的迁移问题。