一种基于云环境的多属性范围查询方法

摘要

本发明提供了一种基于云环境的多属性范围查询方法，本地服务器将数据集索引构造成索引向量并加密，将查询请求构造成请求向量并加密，云端服务器通过计算加密后的索引向量和请求向量的内积确定目标数据，从而实现高效的查询操作。同时，本地服务器将数据加密并打包发送至云端服务器，用户可以直接对云端服务器的密文进行多属性的范围查询，云端服务器接收到查询请求后，在不解密任何数据的情况下，检索出满足查询范围的数据，并将其返回给用户，期间所有的操作都是以密文的形式运行，保证云端服务器无法获知任何数据信息，保证数据的隐私安全。

说明书

技术领域

本发明涉及大数据领域，尤其涉及一种基于云环境的多属性范围查询方法。

背景技术

随着大数据的蓬勃发展，传统平台的数据存储能力与数据处理能力早已无法满足数据的容量和增长速度，云计算的发展为大数据创造了更好的数据处理平台与技术支持。为了减轻本地存储负担，并改善服务质量，越来越多的企业或单位开始将他们的数据打包存放在云端服务器上，同时，为了保护数据的隐私安全，他们会将数据加密。但是，加密带来的最重要的问题就是对数据的查询处理问题，比如范围查询。如何在加密数据的同时，实现对密文数据的安全且高效的查询处理，是云计算领域的一大难题。

目前，已存在的解决方案中最突出的就是保序加密技术(OPE)，即一种数据在加密过后、保证密文与明文顺序保持一致的加密方式，可直接在密文中进行范围查询。但是，现在存在的大多数OPE机制都存在安全性不高的问题。另外，文献《An ideal-securityprotocol for order-preserving encoding》中提出了一种名为“mOPE”的安全OPE机制，但是，其需要客户端与服务器进行大量的交互，存在效率低的问题。

发明内容

为了解决现有技术所存在的上述问题，本发明提供了一种基于云环境的多属性范围查询方法，本地服务器将数据集索引构造成索引向量并加密，将查询请求构造成请求向量并加密，云端服务器通过计算加密后的索引向量和请求向量的内积确定目标数据，从而实现高效的查询操作。同时，用户可以直接对云端服务器中的密文进行多属性的范围查询，云端服务器接收到查询请求后，在不解密任何数据的情况下，检索出满足查询范围的数据，并将其返回给用户，期间所有的操作都是以密文的形式运行，保证云端服务器无法获知任何数据信息，保证数据的隐私安全。

本发明提供了一种基于云环境的多属性范围查询方法，包括：

步骤S1：本地服务器根据预设数据加密算法加密明文数据集得到密文数据集；

步骤S2：本地服务器将与所述明文数据集对应的初始索引构造成索引向量，并采用预设的索引加密算法加密索引向量，得到安全索引向量，将所述密文数据集和安全索引向量发送给云端服务器；

步骤S3：本地服务器根据用户发送的查询请求构造请求向量，并采用所述索引加密算法加密请求向量，得到安全查询向量，将所述安全查询向量发回用户；

步骤S4：云端服务器根据用户转发的所述安全查询向量，计算安全索引向量与安全查询向量的内积，通过内积计算结果确定目标数据密文，并将所述目标数据密文发回用户；

步骤S5：用户通过步骤S1的数据加密算法解密所述目标数据密文，得到目标数据明文。

本发明提供的方法，通过本地服务器根据明文数据构造索引向量，并加密得到安全索引向量，本地服务器根据用户发送的查询请求构造请求向量，并将请求向量加密得到安全查询向量，最后云端服务器通过计算两个向量内积来确定查询结果。使得加密过程只在本地服务器完成，查询过程由云端服务器独立执行，由此不需要用户与服务器的额外交互，提高了处理效率；且本方案密文包含加密后的随机向量，没有泄露与明文相关的信息；再者，本方案的数据传输过程仅传输密文数据，查询过程也是对密文数据直接进行处理，故全过程的安全性得到进一步提高。

进一步的，所述索引加密算法为kNN算法；

所述索引加密密钥为SK＝(sk,σ,L₁,L₂)；

其中，sk＝(M₁,M₂,S)，σ为随机排列数列[1,2,...,d]得到的洗牌函数，L₁和L₂均为长度为的二进制随机字符串、该字符串仅由0和1构成且0和1的个数相等，d为正整数；

M₁和M₂均为d行d列的可逆矩阵，S为一个长度为d的二进制随机字符串、该字符串仅由0和1构成且0和1的个数相等。

现有文献资料《Secure>

进一步的，当所述明文数据集为DS＝{D₁,D₂,...,D_i,...,D_n},n为正整数时，其中，每一个数据D_i都对应包含m个属性值的属性值集合1≤k≤m且m为正整数；

每一个数据D_i对应的每一个属性值所对应的所述索引向量的构造方法为：

步骤S201：随机生成一个包含个非负数的填充集合C，且且集合中所有数的和大于0；

步骤S202：从第1位开始，依次填充索引向量的前位：

当字符串L₁的第t位字符为1时，填充的第t位为否则，填充的第t位为1，其中，

步骤S203：从第位开始，依次填充索引向量的后位：

当字符串L₂的第位字符为1时，填充的第t位为并使x＝x+1，否则，填充的第t位为c_y，并使y＝y+1，其中，

步骤S204：采用洗牌函数σ对填充完毕后的索引向量进行洗牌操作，得到洗牌后的索引向量

在本方案中，构造索引向量时，每一个数据D_i对应的每一个属性值都对应一个索引向量故每一个数据D_i对应的为一个由m个索引向量构成的向量集合。

进一步的，采用kNN算法对所述索引向量加密的方法为：

步骤S211：将d维索引向量拆分为两个d维向量p_a和p_b，拆分规则为：

从字符串S的第1位开始，若第t位字符为1，则将索引向量的第t位的值随机拆分为两个数值分别填充到向量p_a和p_b的第t位中；若第t位字符为0，则直接将索引向量的第t位的值分别填充到向量p_a和p_b的第t位中；

步骤S212：将向量p_a和p_b分别乘以矩阵M₁和M₂的置换矩阵M₁^T和M₂^T，从而得到安全索引向量

在本方案中，先构造索引向量，然后采用kNN算法对索引向量加密，得到加密后的安全索引向量，再将安全索引向量从本地服务器发送给云端服务器。由此，在数据交互过程中汇总、传输的均为加密的内容，可以提高本方案的安全性。

进一步的，步骤S3中根据用户发送的查询请求构造请求向量的方法为：

当所述查询请求为时，根据低边界构造请求向量根据高边界构造请求向量

请求向量的构造方法为：

步骤S301：随机生成一个包含个非负数的填充集合且且集合中所有数的和大于0；

步骤S302：从第1位开始，依次填充请求向量的前位：

当字符串L₁的第t位字符为1时，填充的第t位为并使x＝x+1，否则，填充的第t位为并使y＝y+1，其中，

步骤S303：从第位开始，依次填充请求向量的后位：

当字符串L₂的第位字符为1时，填充的第t位为-1，否则，填充的第t位为其中，

步骤S304：采用洗牌函数σ对填充完毕后的请求向量进行洗牌操作，得到洗牌后的请求向量

其中，中的s∈[1,u]。

在本方案中，因为查询请求为多属性的范围查询请求，故在构建请求向量时，需要分别根据查询范围的低边界和高边界分别构造请求向量，其中，为低边界和高边界的通用标示符，为请求向量的通用标示符。

进一步的，采用kNN算法对所述请求向量加密的方法为：

步骤S211：将d维请求向量拆分为两个d维向量q_a和q_b，拆分规则为：

从字符串S的第1位开始，若第t位字符为1，则直接将请求向量的第t位的值分别填充到向量q_a和q_b的第t位中；若第t位字符为0，则将请求向量的第t位的值随机拆分为两个数值分别填充到向量q_a和q_b的第t位中；

步骤S212：将向量q_a和q_b分别乘以矩阵M₁和M₂的逆矩阵M₁^-1和M₂^-1，从而得到安全查询向量

在本方案中，先构造请求向量，然后采用kNN算法对请求向量加密，得到加密后的安全查询向量，再将安全查询向量从本地服务器发送给用户，最后由用户将安全查询向量发送给云端服务器。由此，在数据交互过程中汇总、传输的均为加密的内容，可以提高本方案的安全性。

进一步的，所述步骤S4中内积的计算方法为：

步骤S401：计算安全查询向量与安全索引向量的内积：

其中，s∈[1,u]，表示低边界对应的安全查询向量，表示高边界对应的安全查询向量；

步骤S402：当V_k,1≤0且V_k,u≥0时，确定此时安全索引向量对应的多属性密文数据属于目标数据密文。

因为在本方案中，与多属性密文数据集对应的索引是向量，而查询请求也被构造成向量，故云端服务器无需查看密文数据的具体内容，只需计算索引向量和查询向量的内积，即可确定索引向量对应的密文数据是否为用户需要查找的目标数据。由此，云端服务器根本不需要进行加密或解密操作，直接对加密后的向量进行计算即可得到目标数据密文，然后将目标数据密文返回给用户。整个过程中都是对加密后的内容进行操作，因为不可能存在泄漏明文数据的风险，进一步保证了本方案的安全性。

进一步的，在对所述请求向量加密前，根据随机数f、r和h将请求向量扩充为请求矩阵，然后，将所述请求矩阵中的每一列数据作为一个向量，采用kNN算法对向量进行加密，得到安全查询矩阵，最后，通过计算安全索引向量与所述安全查询矩阵的内积，得到一个中间向量，再计算该中间向量所有元素之和，通过判断该和值是否满足预设条件，当满足预设条件时，确定此时安全索引向量对应的多属性密文数据属于目标数据密文；

其中，r∈R,h∈R且r+h>0,f∈[2,d]；

所述将请求向量扩充为请求矩阵扩充方法为：

步骤S221：构建一个d行f列的请求矩阵将请求矩阵中的各个元素初始化为0；

步骤S222：从请求矩阵的第一行开始，将随机填充到请求矩阵第i行的任意列上，并使得请求矩阵中每一列至少包含一个请求向量中的元素；

步骤S223：将请求矩阵第i行的剩余位置上填充随机数，并使得请求矩阵第i行填充的随机数之和为由此得到请求矩阵

因为基础的kNN算法无法抵御选择明文攻击，故本发明方案，将请求向量扩充为请求矩阵，以在向量内积的结果中加入噪声，从而使攻击者无法通过技术手段获得明文信息，进一步提高本方案的安全性。因为向量与矩阵的乘积结果为一个向量，而将请求向量扩充为请求矩阵并加密为安全查询矩阵(包括低边界安全查询矩阵和高边界安全查询矩阵)后，安全索引向量与两个安全查询矩阵的内积将会是两个向量，故只有分别计算两个向量中各个元素之和，得到低边界对应的向量元素之和与高边界对应的向量元素之和，然后判断是否满足“边界对应的向量元素之和小于等于0且高边界对应的向量元素之和大于等于0”这一条件，来确定此时安全索引向量对应的密文数据是否为目标数据密文。若满足这一条件，则安全索引向量对应的密文数据为目标数据密文。

有益效果

本发明提供了一种基于云环境的多属性范围查询方法，本地服务器将数据集索引构造成索引向量并加密，将查询请求构造成请求向量并加密，云端服务器通过计算加密后的索引向量和请求向量的内积确定目标数据，从而实现高效的查询操作。同时，本地服务器将数据加密并打包发送至云端服务器中，用户可以直接对云端服务器中的密文进行多属性的范围查询，云端服务器接收到查询请求后，在不解密任何数据的情况下，检索出满足查询范围的数据，并将其返回给用户，期间所有的操作都是以密文的形式运行，保证云端服务器无法获知任何数据信息，保证数据的隐私安全。本方案的加密算法都只涉及独立的数据，且查询算法由服务器独立执行，不需要客户端与服务器额外的交互，效率高。

附图说明

图1是本发明提供的一种基于云环境的多属性范围查询方法的步骤示意图；

图2是本发明实施例提供的具体示例的流程图；

图3是本发明实施例提供的具体示例的明文数据集；

图4是本发明实施例提供的具体示例的索引向量；

图5是本发明实施例提供的具体示例的请求向量；

图6是本发明实施例提供的具体示例的内积计算结果；

图7是本发明实施例提供的具体实例的请求矩阵。

具体实施方式

为了更好的理解本发明方案的内容，下面结合具体实施例进行进一步阐述。

本发明实施例提供了一种基于云环境的多属性范围查询方法，包括：

步骤S1：本地服务器根据预设数据加密算法加密明文数据集得到密文数据集；步骤S2：本地服务器将与所述明文数据集对应的初始索引构造成索引向量，并采用预设的索引加密算法加密索引向量，得到安全索引向量，将所述密文数据集和安全索引向量发送给云端服务器；步骤S3：本地服务器根据用户发送的查询请求构造请求向量，并采用所述索引加密算法加密请求向量，得到安全查询向量，将所述安全查询向量发回用户；步骤S4：云端服务器根据用户转发的所述安全查询向量，计算安全索引向量与安全查询向量的内积，通过内积计算结果确定目标数据密文，并将所述目标数据密文发回用户；步骤S5：用户通过步骤S1的数据加密算法解密所述目标数据密文，得到目标数据明文。

在本实施例中，所述索引加密算法为kNN算法；所述索引加密密钥为SK＝(sk,σ,L₁,L₂)；其中，sk＝(M₁,M₂,S)，σ为随机排列数列[1,2,...,d]得到的洗牌函数，L₁和L₂均为长度为的二进制随机字符串、该字符串仅由0和1构成且0和1的个数相等，d为正整数；M₁和M₂均为d行d列的可逆矩阵，S为一个长度为d的二进制随机字符串、该字符串仅由0和1构成且0和1的个数相等。现有文献资料《Secure>

在本实施例中，当所述明文数据集DS为DS＝{D₁,D₂,...,D_i,...,D_n},n为正整数时，其中，每一个数据D_i都对应包含m个属性值的属性值集合A_i，1≤k≤m且m为正整数；每一个数据D_i对应的每一个属性值所对应的所述索引向量的构造方法为：步骤S201：随机生成一个包含个非负数的填充集合C，且且集合中所有数的和大于0；步骤S202：从第1位开始，依次填充索引向量的前位：当字符串L₁的第t位字符为1时，填充的第t位为否则，填充的第t位为1，其中，步骤S203：从第位开始，依次填充索引向量的后位：当字符串L₂的第位字符为1时，填充的第t位为并使x＝x+1，否则，填充的第t位为c_y，并使y＝y+1，其中，步骤S204：采用洗牌函数σ对填充完毕后的索引向量进行洗牌操作，得到洗牌后的索引向量在本方案中，构造索引向量时，每一个数据D_i对应的每一个属性值都对应一个索引向量故每一个数据D_i对应的为一个由m个索引向量构成的向量集合。

在本实施例中，采用kNN算法对所述索引向量加密的方法为：步骤S211：将d维索引向量拆分为两个d维向量p_a和p_b，拆分规则为：从字符串S的第1位开始，若第t位字符为1，则将索引向量的第t位的值随机拆分为两个数值分别填充到向量p_a和p_b的第t位中；若第t位字符为0，则直接将索引向量的第t位的值分别填充到向量p_a和p_b的第t位中；步骤S212：将向量p_a和p_b分别乘以矩阵M₁和M₂的置换矩阵M₁^T和M₂^T，从而得到安全索引向量在本方案中，先构造索引向量，然后采用kNN算法对索引向量加密，得到加密后的安全索引向量，再将安全索引向量从本地服务器发送给云端服务器。由此，在数据交互过程汇总，传输的均为加密的内容，可以提高本方案的安全性。

在本实施例中，步骤S3中根据用户发送的查询请求构造请求向量的方法为：当所述查询请求为时，根据低边界构造请求向量根据高边界构造请求向量请求向量的构造方法为：步骤S301：随机生成一个包含个非负数的填充集合且且集合中所有数的和大于0；步骤S302：从第1位开始，依次填充请求向量的前位：当字符串L₁的第t位字符为1时，填充的第t位为并使x＝x+1，否则，填充的第t位为并使y＝y+1，其中，步骤S303：从第位开始，依次填充请求向量的后位：当字符串L₂的第位字符为1时，填充的第t位为-1，否则，填充的第t位为其中，步骤S304：采用洗牌函数σ对填充完毕后的请求向量进行洗牌操作，得到洗牌后的请求向量其中，中的s∈[1,u]。在本方案中，因为查询请求为多属性的范围查询请求，故在构建请求向量时，需要分别根据查询范围的低边界和高边界分别构造请求向量，其中，为低边界和高边界的通用标示符，为请求向量的通用标示符。

在本实施例中，采用kNN算法对所述请求向量加密的方法为：步骤S211：将d维请求向量拆分为两个d维向量q_a和q_b，拆分规则为：从字符串S的第1位开始，若第t位字符为1，则直接将请求向量的第t位的值分别填充到向量q_a和q_b的第t位中；若第t位字符为0，则将请求向量的第t位的值随机拆分为两个数值分别填充到向量q_a和q_b的第t位中；步骤S212：将向量q_a和q_b分别乘以矩阵M₁和M₂的逆矩阵M₁^-1和M₂^-1，从而得到安全查询向量在本方案中，先构造请求向量，然后采用kNN算法对请求向量加密，得到加密后的安全查询向量，再将安全查询向量从本地服务器发送给用户，最后由用户将安全查询向量发送给云端服务器。由此，在数据交互过程汇总，传输的均为加密的内容，可以提高本方案的安全性。

在本实施例中，所述步骤S4中内积的计算方法为：步骤S401：计算安全查询向量与安全索引向量的内积：其中，s∈[1,u]，表示低边界对应的安全查询向量，表示高边界对应的安全查询向量；步骤S402：当V_k,1≤0且V_k,u≥0时，确定此时安全索引向量对应的多属性密文数据属于目标数据密文。因为在本方案中，与多属性密文数据集对应的索引是向量，而查询请求也被构造成向量，故云端服务器无需查看密文数据的具体内容，只需计算索引向量和查询向量的内积，即可确定索引向量对应的密文数据是否为用户需要查找的目标数据。由此，云端服务器根本不需要进行加密或解密操作，直接对加密后的向量进行计算即可得到目标数据密文，然后将目标数据密文返回给用户。整个过程中都是对加密后的内容进行操作，因为不可能存在泄漏明文数据的风险，进一步保证了本方案的安全性。

具体而言，假设本地服务器为数据拥有者，则流程图如图2所示。假设此时明文数据集为DS＝{D₁,D₂,D₃,D₄,D₅}＝{(300,480),(350,420),(400,440),(450,520),(450,300)}，且每个数据都具有二维属性值。用户的查询请求为从属性值为(380,460)的位置开始查询距离该点50以内的其他数据(如图3所示)。采用的预设数据加密算法为AES加密算法。

步骤S1：数据拥有者采用AES加密算法加密明文数据集，得到密文数据集。

步骤S2：数据拥有者根据kNN算法生成索引加密密钥，SK＝(sk,σ,L₁,L₂)其中，L₁＝"1100"，L₂＝"0011"；并根据明文数据集构造索引向量：例如，代表数据D₁的第一维属性值300对应的索引向量，其对应的填充集合为C＝(c₁,c₂)＝(0.1,0)，其构造过程为：(1)因为L₁＝"1100"，所以填充(2)因为L₂＝"0011"，所以填充最后得到的所有索引向量如图4所示。再通过kNN算法对所有的索引向量加密，得到安全索引向量。

步骤S3：数据拥有者将密文数据集合安全索引向量发送到云端服务器。

步骤S4：用户向数据拥有者发送查询请求Q＝{Q1,Q2}＝{[q_1,1,q_1,u],[q_2,1,q_2,u]}＝{[330,410],[430,510]}。

步骤S5：数据拥有者根据查询请求Q构造请求向量(如图5所示)：例如，与q_1,1对应的填充集合为故填充过程为：(1)因为L₁＝"1100"，所以填充(2)因为L₂＝"0011"，所以填充q_1,1[5]＝q_1,1[6]＝330，q_1,1[7]＝q_1,1[8]＝-1，其他请求向量以此类推。再通过kNN算法对请求向量加密，得到安全查询向量，并将该安全查询向量发回给所述用户。

步骤S6：用户将接收到的安全查询向量转发给云端服务器。

步骤S7：所述云端服务器在接收到安全查询向量后，开始计算安全查询向量与安全索引向量的内积。因且则计算结果如图6所示：可知满足条件V_k,1≤0且V_k,u≥0的数据仅有D₂和D₃。故云端服务器向用户返回数据D₂和D₃对应的密文数据。

步骤S8：用户根据AES加密算法对云端服务器返回的密文数据进行解密，得到解密后的明文数据D₂和D₃。

在其他实施例中，还可以在对所述请求向量加密前，根据随机数f、r和h将请求向量扩充为请求矩阵，然后，将所述请求矩阵中的每一列数据作为一个向量，采用kNN算法对向量进行加密，得到安全查询矩阵，最后，通过计算安全索引向量与所述安全查询矩阵的内积，得到一个中间向量，再计算该中间向量所有元素之和，通过判断该和值是否满足预设条件，当满足预设条件时，确定此时安全索引向量对应的多属性密文数据属于目标数据密文；其中，r∈R,h∈R且r+h>0,f∈[2,d]；所述将请求向量扩充为请求矩阵扩充方法为：步骤S221：构建一个d行f列的请求矩阵将请求矩阵中的各个元素初始化为0；步骤S222：从请求矩阵的第一行开始，将随机填充到请求矩阵第i行的任意列上，并使得请求矩阵中每一列至少包含一个请求向量中的元素；步骤S223：将请求矩阵第i行的剩余位置上填充随机数，并使得请求矩阵第i行填充的随机数之和为由此得到请求矩阵因为现有文献《Secure Nearest Neighbor Revisited》揭示了基础的kNN算法无法抵御选择明文攻击，故本发明方案，将请求向量扩充为请求矩阵，以在向量内积的结果中加入噪声，从而使攻击者无法通过技术手段获得明文信息，进一步提高本方案的安全性。因为向量与矩阵的乘积结果为一个向量，而将请求向量扩充为请求矩阵并加密为安全查询矩阵(包括低边界安全查询矩阵和高边界安全查询矩阵)后，安全索引向量与两个安全查询矩阵的内积将会是两个向量，故只有分别计算两个向量中各个元素之和，得到低边界对应的向量元素之和与高边界对应的向量元素之和，然后判断是否满足“边界对应的向量元素之和小于等于0且高边界对应的向量元素之和大于等于0”这一条件，来确定此时安全索引向量对应的密文数据是否为目标数据密文。若满足这一条件，则安全索引向量对应的密文数据为目标数据密文。

假设给定的请求向量为q_1,1和q_1,u，则根据上述方法构造的请求矩阵如图7所示。

本发明提供了一种基于云环境的多属性范围查询方法，本地服务器将数据集索引构造成索引向量并加密，将查询请求构造成请求向量并加密，云端服务器通过计算加密后的索引向量和请求向量的内积确定目标数据，从而实现高效的查询操作。同时，本地服务器将数据加密并打包发送至云端服务器中，用户可以直接对云端服务器中的密文进行多属性的范围查询，云端服务器接收到查询请求后，在不解密任何数据的情况下，检索出满足查询范围的数据，并将其返回给用户，期间所有的操作都是以密文的形式运行，保证云端服务器无法获知任何数据信息，保证数据的隐私安全。本方案的加密算法都只涉及独立的数据，且查询算法由服务器独立执行，不需要客户端与服务器额外的交互，效率高。

以上所述仅为本发明的实施例而已，并不用以限制本发明，凡在本发明精神和原则之内，所作任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。