基于空间数据的安全范围查询实现方法

基于空间数据的安全范围查询实现方法
【技术领域】
[0001] 本发明设及的是一种信息安全领域的技术，具体是一种基于空间数据的安全范围 查询实现方法。
【背景技术】
[0002] 自从诞生W来，数据安全问题就一直是云存储服务所面临的最重大的挑战之一。 因为数据存储于云端，并且通过网络进行存取，所W难免会遭到攻击者的利用。尽管数据的 内容本身可W进行加密，但是攻击者仍然能够从用户的访问模式中得到有用的信息。如何 设计一种合理的结构，尽量减小云存储中的信息泄露，把受到攻击的风险降到最低，一直是 一个重要的课题。在该个领域，目前比较有代表性的工作如下：
[0003]Gol化eich等人最早研究了如何隐藏访问模式W避免消息泄露的问题。他们的想 法是使用一个带有密钥的物理隔离的CPU来处理指令。CPU接收加密指令，并且使用它的内 部寄存器将其解密。他们最初设计了一种"平方根"方案，来将主存划分为主存储空间和保 护空间。该种方案虽然简单，但是性能并不理想。随后他们又提出了将保护空间结构化的 思路。Pinkas等人在其基础上进行了改进，使其性能得到了进一步的提升。Boneh等人提 出了遗忘存储的bliviousStorage)的方案，在性能上又有了进一步的提升。然而该些解 决方案都只针对一维的数据，对于二维W上的数据并没有很好的办法。
[0004] 另一方面，空间数据对象是地理位置查询中常见的对象。它通常出现在多维（例 如二维）空间中，仅仅用点是不能很好地描述的。对于空间对象，例如城市，街道等等，在二 维空间中都不能用一个孤立点来简单描述。而在数据对象的使用上，范围查询是一个很常 见的操作。例如，想要找到一个用户所在位置附近5公里内的街道。如何根据他们的空间 位置快速有效地返回相应的数据对象是非常重要的。
[0005]R-tree是由伯克利大学的AntomnGuttman等人在1984年最先提出的一种针对 多维数据的动态索引结构，是目前使用最为广泛的多维数据索引结构之一。它采用一种类 似于B+树的结构来存储多维数据，使得用户可W进行快速的查询和修改。Wang化ng等人 在其基础上，结合非对称标量积保存加密（ASP巧，进一步提出了rhat-trees,用于在加密 的情况下向服务器进行查询操作。尽管如此，W上方法对于如何应对由访问模式猜测用户 信息的攻击者都没有很好的解决方案。

【发明内容】

[0006] 本发明针对现有技术存在的上述不足，提出一种基于空间数据的安全范围查询实 现方法，在保证查询效率的同时，不但实现数据的加密，同时对数据的访问模式也进行隐藏 和保护，从而大大降低信息泄漏的风险。
[0007] 本发明是通过W下技术方案实现的：
[0008] 本发明当用户端C从服务器端S获取一个id的时候，要对其进行解密，并在用户 端返回服务器数据时进行重加密，具体为：
[0009] 步骤1、执行端判断V是否存在于层级列表L中
[0010] 步骤2、当V存在于L中时；
[0011] 2. 1)对于L中的每一层，用户端C向服务器端S发出一个数据项查询指令 GW(/W/y的)，W获取一个伪装数据编号抑对应的数据值，并在接收到后忽略该数 据值。
[0012]2. 2)向服务器发送数据项查询指令Get(PRP,(v))，并在接收到服务器端S返回的 结果b。
[0013] 2. 3)执行加密传输处理shelterinsert(V,b)。
[0014] 2. 4)将decryptsK(b)作为结果返回给用户。
[0015] 步骤3、当V不存在于L中时；
[0016] 3. 1)设1为L中id为V的项目所在的层中最高的一层。
[0017] 3.。对于L中的每一个i声1的层，用户端向服务器端发出一个仙：)）的 请求，W获取一个伪装数据。接收并忽略该数据；发送GW(P/?6.i(u))，设b为服务器返回的结 果。
[0018] 3.3)向服务器端S发送一个数据项查询指令Get(PRP,(d))W获取一个伪装数据 编号PK6-,.(d)对应的数据值，并在接收到后忽略该数据值。
[0019] 3. 4)执行加密传输处理shelterinsert(V,b)。
[0020] 3.W将decryptsK(b)作为结果返回给用户。
[0021] 在服务器上存储的数据结构为（v，b)，而用户输入的数据结构则为（a,b)。其中；b 和服务器端的b相同，代表存储的数据。a表示该条数据在多维空间中的坐标，结构为（di， (V，，d。)，其中；n为空间的维度，di，d2…分别代表该条数据的坐标在每一个维度的取值范 围。在该里为了讨论方便，不妨设n= 2,即二维空间。则a= (di，cg，其中；di= (Xi，X2)， d2=(y1，y2)，表示该条数据在经度Xi到X之间，维度y剧y之间的区域。
[0022] 当接收到一个请求的同时，执行端同时向服务器的隐藏存储区的每一层W及主存 储区都发送一个请求，并且只留下需要的结果，其他结果都被直接忽略。该样攻击者就无法 分辨究竟哪一个才是用户真正想要查询的数据对，从而大大降低了攻击者通过访问模式来 猜测用户信息的风险。 技术效果
[0023] 与现有技术相比，本发明的技术效果包括：
[0024] 首先，在服务器端采用了简单的一维id,使得服务器上不需要存储复杂的多位数 据，从而使得服务器数据结构的复杂度大大降低。
[00巧]其次，避免将地址信息a直接存储在服务器，可W避免泄密的风险。潜在的攻击者 只能获取到一维id的信息，而无法获知用户查询的真实范围。
[0026]此外，本方法当服务器的存储空间M固定时，用户端的存储空间m越大，算法的运 行速度越快。实验结果表明，在保证数据安全的前提下，对二维空间数据的处理速度达到了 接近一维速度的效果。
【附图说明】
[0027]图1为实施例中动态索引结构R-tree规模测试效果示意图；
[002引图2为实施例执行时间效果示意图；
[0029] 图3为实施例中置乱等待时长示意图；
[0030] 图4为实施例系统结构示意图；
[0031] 图5为实施例置乱处理示意图。
【具体实施方式】
[0032] 下面对本发明的实施例作详细说明，本实施例在W本发明技术方案为前提下进行 实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施 例。
[0033]W下实施例的应用环境包括：
[0034] 服务器端S，该服务器端S上的数据形式为（V，b)，其中；V表示数据标识（id)，b 表示数据内容；
[00巧]用户端C，包括；一个地址翻译模块和一个执行端，当用户端处理用户U发送的指 令，向服务器进行查询，并将结果返回给用户。
[0036] 所述的服务器端S响应W下指令：
[0037] 数据项查询指令Get(V):当id为V的项存在于服务器端S，则返回（v，b)，否则返 回空值。
[003引数据项更新指令化t(v);服务器端S将（v，b)加入到存储空间中，且当V已经存 在时覆盖原数据。
[0039] 数据项批量查询指令GetRange(vl，v2):服务器端S返回所有满足vl《V《v2 的（v，b)值。
[0040] 数据项批量删除指令DelRange(VI，v2):服务器端S删除所有满足vl《V《v2 的（v，b)值。
[0041] 所述的用户端C响应W下指令：
[0042] 数据获取指令Get_o(a);获取范围a内的所有数据。
[0043] 数据更新指令^t_o(a,b);将范围a内的数据覆盖为b。
[0044] 其中；a= (di，d2"〇为查询的范围，di，d2…分别代表不同维度内的范围信息。例 如，对于二维的地理坐标，di和d2分别表示经度和绅度的范围。
[0045] 所述的用户U向用户端C发送Get _o(a)或是化t_o(a，b)的指令，且只有在接到 前一条指令的结果之后，U才会发送下一条指令。
[0046] 所述的地址翻译模块中包含一个动态索引结构R-tree,将其命名为R。当接到用 户的请求时，地址翻译模块负责将形如（a，b)的数据转换为形如（v，b)的数据，即；将a转 换为V。
[0047] 与传统数据结构不同，地址翻译模块中的R-tree的叶子节点不需要存储节点的 具体信息b，取而代之的是存储该条信息在服务器上对应的idV，即地址翻译模块中的R-tree存储的是（a,V)的信息。该样就大大减小了R-tree的体积，使得可W将存储了所有 节点信息的整个R-tree都放置在用户端C。
[004引当地址翻译模块收到获取范围a内的所有数据的指令Get_o(a)时，在R中寻找a 范围内的节点，令结果为V，v= (Vi，V2…）。对于每一个V"GV，发送一个Get(v)请求到执 行端。收到结果后，将结果输出给用户。
[0049] 当地址翻译模块收到将范围a内的数据覆盖为b的指令^t_o(a,b)时，在R中寻 找a范围内的节点，令结果为V，V= (V。V2…）。对于每一个v"GV，发送一个化t(V，b)请 求到执行端。收到结果后，将结果输出给用户。
[0050] 所述的执行端中包含一个层级列表L该层级列表L中存储着服务器上隐蔽存储 区的结构信息。当收到地址翻译模块的请求后，执行端向服务器执行查询请求，并将得到结 果并返回给用户。为了数据安全考虑，当系统开始运行的时候，必须输入一个密钥SK，|SK| =k，用于数据加密。
[0051] 置乱函数PRP,为一个定长伪随机置换，对应服务器端S上所有包括主存储区W及 隐蔽存储区的数据的id,都用该PRP,进行加密。 实施例1
[005引如图4所示，本实施例中，当用户端C从服务器端S获取一个id的时候，要对其进 行解密，并在用户端返回服务器数据时进行重加密，具体为：
[0053] 步骤1、执行端判断V是否存在于层级列表L中
[0054] 步骤2、当V存在于L中时；
[0055] 2. 1)对于L中的每一层，用户端C向服务器端S发出一个数据项查询指令 化))，W获取一个伪装数据编号PRAi姑)对应的数据值，并在接收到后忽略该数 据值。
[0056] 2. 2)向服务器发送数据项查询指令Get(PRP,(V))，并在接收到服务器端S返回的 结果b。
[0057] 2. 3)执行加密传输处理shelterinsert(V,b)。
[005引 2. 4)将decryptsK(b)作为结果返回给用户。
[0059] 步骤3、当V不存在于L中时；
[0060] 3. 1)设1为L中id为V的项目所在的层中最高的一层。
[00川 3.。对于L中的每一个i声1的层，用户端向服务器端发出一个仙：)）的 请求，W获取一个伪装数据。接收并忽略该数据；发送的)，设b为服务器返回的结 果。
[0062] 3.3)向服务器端S发送一个数据项查询指令Get(PRP,(d))W获取一个伪装数据 编号的对应的数据值，并在接收到后忽略该数据值。
[0063] 3. 4)执行加密传输处理shelterinsert(V,b)。
[0064] 3.W将decryptsK(b)作为结果返回给用户。
[0065] 所述的加密传输处理shelterinsert(V,b)，包括W下步骤：
[0066] i.对数据值进行更新，具体为b=enc巧ptsK(dec巧ptsK化)）
[0067] ii.向服务器端S发送数据项更新指令Put(PRPsi(V)，b)
[0068] iii.当服务器端S的层级列表L的某一层的存储空间已被写满，执行移层操作 shuffleLevel0将该层中的数据转移到下一层，重复该步骤直至没有一层满为止，当最底 层满时，则服务器端S进行全局置乱处理shuffleMainPart0。
[0069] 当接收到一个请求的同时，执行端同时向服务器的隐藏存储区的每一层W及主存 储区都发送一个请求，并且只留下需要的结果，其他结果都被直接忽略。该样攻击者就无法 分辨究竟哪一个才是用户真正想要查询的数据对，从而大大降低了攻击者通过访问模式来 猜测用户信息的风险。当用户对一条数据执行了数据项查询指令或数据项更新指令后，该 条数据就被加入到隐藏存储区中。
[0070] 如图5所示，所述的移层操作shuffleLevel0是指；将隐蔽存储区中一个等级i 的层中的数据转移到等级i+1的层中，具体步骤包括：
[0071] 一、使用局部置乱处理shuffle0来置乱第i层数据。
[0072] 二、使用局部置乱处理shufTle0来置乱束i+1层数据。
[0073]S、将第i层中不是假数据的数据对写入到第i+1层中。当一个第i层中的数据 对的id同时存在于第i+ 1层的数据对中，则将第i+ 1层中的数据对覆盖，否则将它们写入 到原本的假数据的位置。
[0074] 四、将第i层的所有数据删除。
[00巧]五、使用局部置乱处理shuffle0来置乱第i+1层数据。
[0076] 当整个结构的最后一层也满了之后，用户端C使用全局置乱处理 shuffleMainPart0来将最后一层合并到主存储区。
[0077] 所述的全局置乱处理ShuffleMainPart0是指；将服务器端隐蔽存储区中底层的 数据合并到主存储区中，并且将合并后的主存储区进行置乱操作，具体包括W下步骤：
[0078]I)在服务器端创建一个新的结构化的隐藏存储区，内容为空，称为同步隐藏存储 区。
[0079]II)生成一个当前服务器上隐藏存储区的副本，称为隐藏存储区副本。
[0080]III)使用局部置乱处理shuffleO置乱服务器的主存储区。
[0081]IV)使用局部置乱处理shuffleO置乱原本的隐藏存储区。
[0082]V)将隐藏存储区里的数据都更新到主存储区里。当该条数据是伪装数据，那么也 用它更新主存储区的伪装数据。
[008引VI)使用局部置乱处理shuffleO置乱服务器的主存储区。
[0084]VII)删除隐藏存储区副本和原本的隐藏存储区。同步隐藏存储区成为新的隐藏存 储区。
[0085] 所述的局部置乱处理shuffleO是指；将服务器上某个部分的数据置乱，将他们 的id用相同的PRP算法进行变更，具体步骤包括：
[0086] 1.将服务器端S上的存储空间按逻辑分为大小为0(m)的数个数据块并标记为i =1，2...#C，其中；#C= 0(MB/m)
[0087] 2.通过数据项批量查询指令GetRange依次获得每个数据块的值，然后使用数据 项批量删除指令DelRange依次从服务器上删除该数据块，并在该数据块的每个id前面加 上"i:"的前缀，然后通过数据项更新指令Put将该添加过前缀的数据块放回服务器端S上。
[0088] 3.添加完前缀后，对所有数据块进行W下遍历操作：
[0089] 3. 1)把数据块按照W下规则组成逻辑对；当块j没有被组对过，那么将它和块j* 组队，其中；j* =j+2i
[0090] 3.2)采用置乱函数PRPi置乱每一个数据块对，然后使用数据项批量查询指令 GetRange(j. 0，j:9. . 9)和GetRange(j*:0. . 0，j*:9. . 9)将数据块复制到用户端，并使 用数据项批量删除指令DelRange将对应的数据块对从服务器端S上删除，然后对每个id， 令i= 但"iW)，重新加密数据块，将数据块对按照新的id重新排列。在数据块对的 前半部分加上前缀"j:"，后半部分加上前缀"j*:"。使用数据项更新指令Put命令将他们 都传输到服务器上。
[00川 3.扣在置乱索引中添加"ITi"的项目，记录该个步骤中被置乱过的数据对的信 息。
[00 92] 4.置乱结束后，将步骤1和2中添加在服务器端S上所有的数据id前的前缀（i: 和j:)去掉，并将用户端C的置乱索引删除。
[0093] 上述过程用户端共发出 0 ((MB/m)log(MB/m))次请求，Get/Put0(Mlog(MB/M))个 数据对。
[0094] 该些置乱操作会随着用户的操作不断发生。当一个置乱操作正在发生的时候，用 户就无法继续进行查询操作了。该对于整个系统的操作体验是有很大影响。
[0095] 为了保证在对服务器的数据进行置乱操作的同时，用户端可W对服务器进行访 问，采用W下方法：
[009引A.在置乱的时候，用户端C生成一个置乱索引，用于保存置乱目录的数据结构，来 保存一个id被置乱后的变化，该样用户端就可W从一个正在进行置乱的存储结构中准确 而有效地找到数据。
[0097] B.用户端C生成一个同步隐藏存储区，并将置乱期间所有的数据访问请求都会被 存储在里面，W防止被置乱的部分被重复访问。
[0098] C.用户端C在一次置乱期间只允许一定数量的查询请求，把过多的请求延迟或是 拒绝掉，W保证在一次置乱没有结束之前不会马上开始另一次置乱。
[0099] 用户对服务器进行数据操作时，采用W下并发查询策略W保证能够在数据置乱操 作时仍不影响用户操作：
[0100] 1)当采用并发查询请求时没有全局置乱处理shuffleMainPartO正在执行，则直 接执行数据项查询指令get(V)或数据项更新指令put(V)，并返回结果，否则：
[010。 2)当采用并发查询请求的同时正在进行全局置乱处理shuffleMainPart0，则；
[0102] 2. 1)用户端首先需要检查同步隐藏存储区，W确定需要的id是否在里面。当在里 面，用户端需要向服务器的主存储区发送一个对伪装数据的请求，否则它需要发送一个对V的请求到服务器。
[010引 2. 2)当发送请求到主存储区的时候，判断当全局置乱处理ShuffleMainPartO执 行情况并进行对应操作，然后将访问的数据加入到同步隐藏存储区中，具体为：
[0104]a)当全局置乱处理ShuffleMainPartO正进行到第S步之前，则直接向主存储区 发出请求。
[010引 b)当全局置乱处理ShuffleMainPartO正进行到第S步到第四步之间，则从置乱 索引中找到目的id,并且发出请求。
[0106] C)当全局置乱处理ShuffleMainPartO正进行到第四步到第六步之间，则利用用 户端在shuffle0的第S步所使用的最后一个序列来向服务器发出请求。
[0107] d)当全局置乱处理ShuffleMainPart0正进行到第六步到第走步之间，则从置乱 索引中找到目的id,并且发出请求。
[0108] e)当全局置乱处理shuffleMainPartO已进行到第走步之后，则利用用户端在 shuffle0的第S步所使用的最后一个序列来向服务器发出请求。
[0109] 当所述请求所访问的目标是原本的隐藏存储区中的内容时，则使用复制隐藏存储 区代替原本的隐藏存储区进行操作；如当移层操作shuffleLevelO正在进行，则等待置乱 完成后再响应请求。
[0110] 实施效果：
[0111] 利用随机生成的数据进行了实验。实验主机的配置如下：内存8G，CPU主频 3.4GHz。的实验数据是二维数据，每个数据块的大小为4096,其中；前32位是坐标信息，其 余部分为数据块内容。坐标信息包含两个维度。生成的数据规模如表1所示。
[0112] 一共生成了 =组实验数据，数据的条数M分别是16384条、65536条和262144条。 服务器端的数据的总大小MB分别约为64MB、256MB和1GB。用户端的大小为m=Vi庶，即 8邸、1日邸、32邸。
[0113] 表1实验数据规模
[0114] 为了测试用户端的R-tree的性能，分别对S组数据进行了R-tree建模，用 LC(LeafCapacity)代表一个R-tree节点能承受的最大子节点数量。对S组数据分别进行 了测试，使用的LeafCapacity值取值和得到的R-tree大小如下；
[0115] 表2R-tree规模测试
[0116] 从图1和表格3的结果可W看到，R-tree的规模足够小，可W存储在用户端。随 着LeafCapacity的增大，R-tree的规模也会随之减小，但是减小的速度会逐渐下降直至 停止。出于性能方面的考虑，在接下来的实验中将LeafCapacity选择为400。
[0117] 共进行了 =组实验，每组进行的查询操作分别是10000次、50000次和100000次， 各做10次，取平均值。实验结果如图2;
[0118] 因为本地检索的速度非常快，和通信所花费的时间相比可W忽略，所W在整个系 统中，服务器端和用户端的通信是性能瓶颈。用户端存储的数据容量为BV而，在不考虑置乱 的情况下，每次查询请求需要的get/put次数为O(l〇gM)。在考虑了置乱的情况下，需要的 次数则为0(^l〇gM巧。但是从实验结果看，和理论数值却存在一定的偏差。原因在于，当服 a 务器正在进行一次置乱操作的时候，是禁止进行新的置乱操作进行的。当置乱期间用户的 请求数超过了 一定的数量时，新的请求就会被延迟。
[0119] 为了证明该个结论，统计了置乱操作期间Get/Put的I/O次数W及系统的置乱等 待时间（即从一个请求被延迟开始到置乱结束该个请求开始执行之间的时间的叠加）。次 数结果如表3,等待时间结果如图3 :
[0120] 表3置乱操作Get/化t的I/O次数
[012。 表3的结果验证了算法的理论速度。同时也表明，当MB/m= 2"时，系统的性能能够 达到最优。从图3的实验结果也表明，随着数据量的增加，置乱等待的时间是逐渐上升的。 该是由两方面的因素共同造成的。一方面，如同表3的结果所示，随着数据量的增加，一次 置乱需要的访问量也大大增加。该使得置乱的速度降低，从而使得等待的时间变长。另一 方面，随着数据量的增加，隐藏存储区的空间也随之扩大。该就使得置乱的次数随之降低。 与此同时，由于同步隐藏存储区也随之扩大，在置乱期间允许的请求数也随之上升。该对于 减少等待的时间也是有帮助的。
【主权项】
1. 一种基于空间数据的安全范围查询实现方法，其特征在于，当用户端从服务器端获 取一个id的时候，要对其进行解密，并在用户端返回服务器数据时进行重加密，具体为： 步骤1、执行端判断V是否存在于层级列表L中 步骤2、当V存在于L中时： 2. 1)对于L中的每一层，用户端C向服务器端S发出一个数据项查询指令 以获取一个伪装数据编号P/^s.i(cQ对应的数据值，并在接收到后忽略该数 据值； 2. 2)向服务器发送数据项查询指令Get (PRPs (V))，并在接收到服务器端S返回的结果 b ； 2.3)执行加密传输处理8116]^61'111861'1：(￥，13)，其中：￥表示数据标识（1(1)，13表示数据 内容； 2. 4)将decryptSK(b)作为结果返回给用户； 步骤3、当V不存在于L中时： 3. 1)设1为L中id为V的项目所在的层中最高的一层； 3. 2)对于L中的每一个i辛1的层，用户端向服务器端发出一个的请求， 以获取一个伪装数据，接收并忽略该数据；发送:Gd(PRP Si(i〇)，设b为服务器返回的结果； 3. 3)向服务器端S发送一个数据项查询指令Get (PRPs (d))以获取一个伪装数据编号 /WGi (X)对应的数据值，并在接收到后忽略该数据值； 3. 4)执行加密传输处理shelterlnsert (V，b); 3. 5)将decryptSK(b)作为结果返回给用户； 当接收到一个请求的同时，执行端同时向服务器的隐藏存储区的每一层以及主存储区 都发送一个请求，并且只留下需要的结果，其他结果都被直接忽略；这样攻击者就无法分辨 宄竟哪 一个才是用户真正想要查询的数据对，从而大大降低了攻击者通过访问模式来猜测 用户信息的风险；当用户对一条数据执行了数据项查询指令或数据项更新指令后，这条数 据就被加入到隐藏存储区中。2. 根据权利要求1所述的方法，其特征是，所述的层级列表L中存储着服务器上隐蔽 存储区的结构信息；当收到地址翻译模块的请求后，执行端向服务器执行查询请求，并将得 到结果并返回给用户；为了数据安全考虑，当系统开始运行的时候，必须输入一个密钥SK， SK| = k，用于数据加密。3. 根据权利要求1所述的方法，其特征是，所述的伪装数据编号'/〃化,.⑷)，通过置乱函 数PRPs实现，该置乱函数为定长伪随机置换，对应服务器端S上所有包括主存储区以及隐 蔽存储区的数据的id，都用该PRPs进行加密。4. 根据权利要求1所述的方法，其特征是，所述的加密传输处理shelterlnsert (V，b)， 包括以下步骤： ：1.对数据值进行更新，具体为6 = 611〇巧?1^((16〇巧?1^(13)); ii. 向服务器端S发送数据项更新指令Put (PRPsl (v)，b); iii. 当服务器端S的层级列表L的某一层的存储空间已被写满，执行移层操作 shuff IeLevel ()将该层中的数据转移到下一层，重复该步骤直至没有一层满为止，当最底 层满时，则服务器端S进行全局置乱处理shuffleMainPart O。5. 根据权利要求1所述的方法，其特征是，所述的移层操作shuffIeLevel ()是指：将 隐蔽存储区中一个等级i的层中的数据转移到等级i+Ι的层中，具体步骤包括： 一、 使用局部置乱处理shuffleO来置乱第i层数据； 二、 使用局部置乱处理shuffleO来置乱第i+Ι层数据； 三、 将第i层中不是假数据的数据对写入到第i+Ι层中；当一个第i层中的数据对的id 同时存在于第i+Ι层的数据对中，则将第i+Ι层中的数据对覆盖，否则将它们写入到原本的 假数据的位置； 四、 将第i层的所有数据删除； 五、 使用局部置乱处理shuffleO来置乱第i+Ι层数据； 当整个结构的最后一层也满了之后，用户端C使用全局置乱处理shuffleMainPart () 来将最后一层合并到主存储区。6. 根据权利要求1或4或5所述的方法，其特征是，所述的全局置乱处理 ShuffleMainPartO是指：将服务器端隐蔽存储区中底层的数据合并到主存储区中，并且 将合并后的主存储区进行置乱操作，具体包括以下步骤： I) 在服务器端创建一个新的结构化的隐藏存储区，内容为空，称为同步隐藏存储区； II) 生成一个当前服务器上隐藏存储区的副本，称为隐藏存储区副本； III) 使用局部置乱处理shuffleO置乱服务器的主存储区； IV) 使用局部置乱处理shuffleO置乱原本的隐藏存储区； V) 将隐藏存储区里的数据都更新到主存储区里；当这条数据是伪装数据，那么也用它 更新主存储区的伪装数据； VI) 使用局部置乱处理shuffleO置乱服务器的主存储区； VII) 删除隐藏存储区副本和原本的隐藏存储区；同步隐藏存储区成为新的隐藏存储 区。7. 根据权利要求6所述的方法，其特征是，所述的局部置乱处理shuff Ie ()是指：将服 务器上某个部分的数据置乱，将他们的id用相同的PRP算法进行变更，具体步骤包括：1. 将服务器端S上的存储空间按逻辑分为大小为0(m)的数个数据块并标记为i = 1， 2…#C，其中：#C = 0(MB/m);2. 通过数据项批量查询指令GetRange依次获得每个数据块的值，然后使用数据项批 量删除指令DelRange依次从服务器上删除该数据块，并在该数据块的每个id前面加上 "i: "的前缀，然后通过数据项更新指令Put将该数据块放回服务器端S上；3. 添加完前缀后，对所有数据块进行以下遍历操作： 3. 1)把数据块按照以下规则组成逻辑对，当块j没有被组对过，那么将它和块组队， 其中：_f = j+21 3.2)采用置乱函数PRPi置乱每一个数据块对，然后使用数据项批量查询指令 GetRange(j:0. . 0, j:9. . 9)和 GetRangeU^O. . 0, _f:9. . 9)将数据块复制到用户端，并使用 数据项批量删除指令DelRange将对应的数据块对从服务器端S上删除，然后对每个id，令 i = 重新加密数据块，将数据块对按照新的id重新排列；在数据块对的前 半部分加上前缀" j : "，后半部分加上前缀" _f: ";使用数据项更新指令Put命令将他们都传 输到服务器上； 3.3)在置乱索引中添加"IT i"的项目，记录这个步骤中被置乱过的数据对的信息；4.置乱结束后，将步骤1和2中添加在服务器端S上所有的数据id前的前缀（i :和 j:)去掉，并将用户端C的置乱索引删除。8. 根据上述任一权利要求所述的方法，其特征是，在对服务器的数据进行置乱操作的 同时，用户端通过以下方法对服务器进行访问： 步骤A.在置乱的时候，用户端C生成一个置乱索引，用于保存置乱目录的数据结构，来 保存一个id被置乱后的变化，这样用户端就可以从一个正在进行置乱的存储结构中准确 而有效地找到数据； 步骤B.用户端C生成一个同步隐藏存储区，并将置乱期间所有的数据访问请求都会被 存储在里面，以防止被置乱的部分被重复访问； 步骤C.用户端C在一次置乱期间只允许一定数量的查询请求，把过多的请求延迟或是 拒绝掉，以保证在一次置乱没有结束之前不会马上开始另一次置乱。9. 根据上述任一权利要求所述的方法，其特征是，用户对服务器进行数据操作时，采用 以下并发查询策略以保证能够在数据置乱操作时仍不影响用户操作： 1) 当采用并发查询请求时没有全局置乱处理shuff IeMainPart ()正在执行，则直接执 行数据项查询指令get (V)或数据项更新指令put(V)，并返回结果，否则： 2) 当采用并发查询请求的同时正在进行全局置乱处理ShuffleMainPartO，则： 2. 1)当用户端请求的id在同步隐藏存储区时，用户端向服务器的主存储区发送一个 对伪装数据的请求；否则用户端发送一个对V的请求到服务器； 2. 2)当发送请求到主存储区的时候，判断当全局置乱处理ShuffleMainPartO执行情 况并进行对应操作，然后将访问的数据加入到同步隐藏存储区中。10. 根据权利要求9所述的方法，其特征是，步骤2. 2中的对应操作是指： a) 当全局置乱处理ShuffleMainPartO正进行到第三步之前，则直接向主存储区发出 请求； b) 当全局置乱处理ShuffleMainPartO正进行到第三步到第四步之间，则从置乱索引 中找到目的id，并且发出请求； c) 当全局置乱处理ShuffleMainPartO正进行到第四步到第六步之间，则利用用户端 在shuffleO的第三步所使用的最后一个序列来向服务器发出请求； d) 当全局置乱处理ShuffleMainPartO正进行到第六步到第七步之间，则从置乱索引 中找到目的id，并且发出请求； e) 当全局置乱处理ShuffleMainPartO已进行到第七步之后，则利用用户端在 shuffleO的第三步所使用的最后一个序列来向服务器发出请求； 当所述请求所访问的目标是原本的隐藏存储区中的内容时，则使用复制隐藏存储区代 替原本的隐藏存储区进行操作；如当移层操作shuffIeLevelO正在进行，则等待置乱完成 后再响应请求。
【专利摘要】一种基于空间数据的安全范围查询实现方法，当用户端从服务器端获取一个id的时候，要对其进行解密，并在用户端返回服务器数据时进行重加密，本发明在保证查询效率的同时，不但实现数据的加密，同时对数据的访问模式也进行隐藏和保护，从而大大降低信息泄漏的风险。
【IPC分类】G06F21/62, G06F17/30
【公开号】CN104881614
【申请号】CN201510299618
【发明人】过敏意, 姚斌, 沈耀, 谢丁星, 周憬宇, 薛广涛
【申请人】上海交通大学
【公开日】2015年9月2日
【申请日】2015年6月3日