本发明涉及一种分布式多维范围查询方法、装置及系统，属于分布式信息处理。
背景技术：
1、凭借灵活性、可扩展性和按需服务等方面的优势，数据库即服务(dbaas)广泛应用于电子医疗等领域。然而对加密数据执行查询可能会产生较高的计算和存储开销。可搜索加密方案可以支持各种查询类型，然而传统的可搜索加密方案似乎只用于相等搜索而不支持比较操作。很多领域更加需要能够处理表达模式的查询系统，例如包含属性关键字和属性值的电子健康记录(参见表1)。例如，一位医生想要搜索年龄在(15,35)范围内且心率高于110bpm的女性患者的电子病历时，可以提交查询“age(15,35)，heart rate>110，female”，然后数据服务器会返回所有满足查询的记录文件。
2、表1：电子健康记录表
3、
4、为了实现多维的范围查询，一些研究工作使用了公钥加密或保序加密，但是它们要么计算成本高，要么泄露明文数据顺序。为了解决上述问题，研究者们采用将多维范围分解为多个单维范围的方法，然而这种方法泄露了单维隐私，这意味着数据服务器知道每个维度的查询结果。因此研究者们采用r树索引结构结合对称加密的方式实现可以保证单维隐私的多维范围搜索。但是目前的范围搜索方案要么通信复杂度高，要么查询效率有待进一步提高。
5、如上所述，在保护单维隐私的同时实现高效的多维范围查询仍然是一个挑战。因此，本发明提出了一种分布式多维范围查询方法。
技术实现思路
1、为了解决上述问题，本发明提出了一种分布式多维范围查询方法、装置及系统，能够在保护单维隐私的同时减低通信复杂度并提查询效率有待进一步高。
2、本发明解决其技术问题采取的技术方案是：
3、第一方面，本发明实施例提供的一种分布式多维范围查询方法，包括以下步骤：
4、步骤1，系统初始化，根据预设的安全参数生成系统参数；
5、步骤2，构造索引列表，并将标题、区间以及区间内的数据值和文件标识使用秘密共享多项式转换为对应的秘密份额，获得秘密索引结构；
6、步骤3，将w维度的查询转化为个向量，并使用秘密共享获得秘密查询向量；
7、步骤4，根据查询请求搜索匹配的文件。
8、作为本实施例一种可能的实现方式，所述步骤1，包括以下步骤：
9、根据预设的安全参数λ，选择一个大素数p以及α∈[1,p/2),β∈(p/2,p)，假设系统有n个属性，其中w-1个有属性值，n-w+1没有属性值；
10、随机选择w个不同的整数数y1,…,yw∈[0,p-1]来标识属性标题，并随机选择n-w+1个不同的整数h1,…,hn-w+1∈[1,p/2)来标记不带数值的属性；
11、令公共参数p＝p，则秘密参数sp＝{α,β,y1,…,yw,h1,…,hn-w+1}。
12、作为本实施例一种可能的实现方式，在步骤2中，假设是系统中n个数据记录文件的集合，构造索引列表其中ij代表第j个列表且对于每一个ij，tj代表标题，代表m个区间，是区间rr中dr个数据值和十进制文件标识符对，使用秘密共享多项式转换为对应的秘密份额。
13、作为本实施例一种可能的实现方式，所述步骤2，包括以下步骤：
14、1)对于每个标题tj对应的数值yj，随机选择s″j∈fp并令一次多项式f″(j)(u)＝-yj+s″ju，则对应的秘密份额为s(tj)i＝f″(j)(i),1≤i≤2；
15、2)对于tj中的每个区间rr，采用区间交集判定算法得到多项式f′(r)(u)＝x′r+s′ru，则对应的秘密份额为s(rr)i＝f′(r)(i)，1≤i≤2；
16、3)对于rr中的每个数据值drk，采用点交判定算法得到f(rk)(u)＝xrk+srku，并且对每个数据值drk分配十进制标识符yrk，随机选择s″′rk∈fp并令f″′(rk)(u)＝yrk+s″′rku，则对应的秘密份额为(s(drk)i,s(yrk)i)＝(f(rk)(i),f″′(rk)(i))；得到秘密索引其中，
17、作为本实施例一种可能的实现方式，所述步骤3，包括以下步骤：
18、将w维度的查询转化为w个长度为5的向量，使得查询向量的总长度为5w，每个维度的查询其中y′j用来表示查询属性，qj代表该维度对应的查询范围；
19、y′j用于匹配标题，如果需要第j个属性，则y′j＝yj；否则随机选择y′j≠yj；然后随机选择ej′∈fp以获得一次多项式h(j)(u)＝y′j+ej′u；
20、对于查询范围qj，采用点交判定算法将范围转换为查询向量qj并且得到秘密共享多项式g(j)(u)＝qj+eju；
21、获得秘密查询其中
22、作为本实施例一种可能的实现方式，所述步骤4，包括以下步骤：
23、1)对于每个标题tj，计算c″(j)(i)＝f″(j)(i)+h(j)(i)；并且对于tj中的每个区间rr，采用区间交集判定算法得到c′(r)(i)＝f′(r)(i)+g(r)(i)，
24、令对(i,l1(i),l2(i),…,lw(i))进行验证；
25、2)对于每个lj(i)，使用(i,c″(j)(i))插值多项式ψ(j)(u)，其中ψ(j)(0)＝y′j-yj，
26、a)如果ψ(j)(0)＝0，继续对lj(i)中的每个(i,c′(r)(i)),(i,c″(r)(i))运行区间交集判定算法，如果和满足区间交集判定算法的判定条件，返回1；否则返回0；
27、b)如果ψ(j)(0)≠0，随机选择一个区间返回1，并且为其他区间返回0；
28、3)收到返回的结果后，对区间rr(可能有多个区间)中的每个数据值drk采用点交判定算法得到c(rk)(i)＝f(rk)(i)+g(j)(i)，其中rr是tj中对应结果为“1”的区间；令发送(i,l′1(i),l′2(i),…,l′w(i))进行验证；如果tj中的有多个区间对应结果“1”，则对每个区间重复上述过程并将结果合并到同一个lj′(i)中；
29、4)将步骤2)中获得的结果与收到的(i,l′1(i),l′2(i),…,l′w(i))相结合：
30、a)对于步骤2)中ψ(j)(0)＝0的列表tj对应的lj′(i)，用(i,c(rk)(i))插值多项式φ(rk)(u)；如果φ(rk)(0)满足点交判定算法的判定条件，继续使用(i,f″′(rk)(i))插值多项式φ′(rk)(u)，其中φ′(rk)(u)＝yrk；否则不插值；随后，把从同一列表tj中得到的所有y值相加，得到sj＝∑yrk，并将sj转换为相应的二进制形式σj；
31、b)对于步骤2)中ψ(j)(0)≠0的列表tj，不做任何运算；
32、c)将所有的二进制串σj取交集，只将所有串中同时为“1”的位置保留“1”，其余为“0”，从而得到新的二进制串σ；则σ中“1”所对应的文件为满足问询q的文件。
33、作为本实施例一种可能的实现方式，所述点交判定算法包括:
34、参数初始化点交判定算法：选择大素数p使得所有的数据都在区间[0,p/2)中，随机选择[1,p/2),β∈(p/2,p)；
35、索引提取点交判定算法：对于索引数据x对应的索引向量x＝(0,-x)，随机选择向量二维其中是有限域fp上二维向量的集合，并令一次多项式f(u)＝x+su，u为多项式未知量，则两个秘密份额分别为f(1)和f(2)；
36、查询提取点交判定算法：对于询问q＝(a,b)，以“>a,<b”的形式构造查询向量q＝(β,a,α,b)，如果只询问“>a”或“<b”，复制并将其填充成4维，则对应的查询向量为q＝(β,a,β,a)或(α,b,α,b)；而当问询“＝a”时，将其转换为范围(a-1,a+1)，然后，随机选择4维向量其中是有限域fp上4维向量的集合；并令一次多项式g(u)＝q+eu，则两个秘密份额分别为g(1)和g(2)；
37、匹配点交判定算法：计算
38、判定点交判定算法：使用(i,c(i))插值多项式φ(u)，其中φ(0)＝x+q＝(φ1,φ2,φ3,φ4)，如果φ1和φ2都属于(p/2,p)并且φ3和φ4都属于[1,p/2)，或者φ(0)的所有项要么都属于(p/2,p)，要么都属于[1,p/2)，则数据x满足查询q，返回1；否则不满足，返回0。
39、作为本实施例一种可能的实现方式，所述区间交集判定算法包括:
40、参数初始化区间交集判定算法：选择大素数p使得所有的数据都在区间[0,p/2)中，随机选择[1,p/2),β∈(p/2,p)；
41、索引提取区间交集判定算法：对于索引范围(x1,x2)对应的索引向量x′＝(0,-x2,0,-x1)，随机选择4维向量并令一次多项式f′(u)＝x′+s′u，则两个秘密份额分别为f′(1)，f′(2)；
42、查询提取区间交集判定算法：对于询问q＝(a,b)，以“>a,<b”的形式构造查询向量q＝(β,a,α,b)，如果只询问“>a”或“<b”，复制并将其填充成4维，则对应的查询向量为q＝(β,a,β,a)或(α,b,α,b)；而当问询“＝a”时，将其转换为范围(a-1,a+1)，然后，随机选择4维向量其中是有限域fp上4维向量的集合；并令一次多项式g(u)＝q+eu，则两个秘密份额分别为g(1)和g(2)；
43、匹配区间交集判定算法：计算c′(i)＝f′(i)+g(i)，
44、判定区间交集判定算法：使用(i,c′(i))插值多项式其中如果和都属于(p/2,p)并且和都属[1,p/2)，返回1；否则继续使用(i,c″(i))插值多项式其中如果和都属于[1,p/2)，或者和都属于(p/2,p)，返回1；否则返回0；返回1意味着索引范围(x1,x2)满足查询；返回0意味着不满足。
45、第二方面，本发明实施例提供的一种分布式多维范围查询装置，包括：
46、初始化模块，用于系统初始化，根据预设的安全参数生成系统参数；
47、索引构造模块，用于构造索引列表，并将标题、区间以及区间内的数据值和文件标识使用秘密共享多项式转换为对应的秘密份额，获得秘密索引结构；
48、查询转化模块，用于将w维度的查询转化为个向量，并使用秘密共享获得秘密查询向量；
49、文件搜索模块，用于根据查询请求搜索匹配的文件。
50、第三方面，本发明实施例提供的一种分布式多维范围查询系统，包括数据所有者、数据用户、云平台和验证中心vc，其中，云平台包含2个数据服务器；
51、所述验证中心vc根据预设的安全参数λ生成系统参数，并通过安全通道将系统参数传送给数据所有者和数据用户；具体的：
52、根据预设的安全参数λ，验证中心vc选择一个大素数p以及α∈[1,p/2),β∈(p/2,p)，假设系统有n个属性，其中w-1个有属性值，n-w+1没有属性值；随机选择w个不同的整数数y1,…,yw∈[0,p-1]来标识属性标题，并随机选择n-w+1个不同的整数h1,…,hn-w+1∈[1,p/2)来标记不带数值的属性；令公共参数p＝p，则秘密参数sp＝{α,β,y1,…,yw,h1,…,hn-w+1}。最后，验证中心vc将sp发送给数据所有者do和数据用户du；
53、假设是系统中n个数据记录文件的集合，所述数据所有者构造索引列表其中ij代表第j个列表且对于每一个ij，tj代表标题，代表m个区间，是区间rr中dr个数据值和十进制文件标识符对；数据所有者使用秘密共享多项式将它们转换为对应的秘密份额并发送给数据服务器；具体的：
54、1)对于每个标题tj对应的数值yj，数据所有者do随机选择sj″″∈fp并令一次多项式f″(j)(u)＝-yj+s″ju，则数据服务器dsi对应的秘密份额为s(tj)i＝f″(j)(i),1≤i≤2；
55、2)对于tj中的每个区间rr，数据所有者do运行索引提取区间交集判定算法piidie得到多项式f′(r)(u)＝x′r+s′ru，则数据服务器dsi对应的秘密份额为s(rr)i＝f′(r)(i)，1≤i≤2；
56、3)对于rr中的每个数据值drk，数据所有者do运行索引提取点交判定算法ppidie得到f(rk)(u)＝xrk+srku，并且对每个数据值drk分配十进制标识符yrk，数据所有者随机选择s″′rk∈fp并令f″′(rk)(u)＝yrk+s″′rku，则数据服务器dsi对应的秘密份额为(s(drk)i,s(yrk)i)＝(f(rk)(i),f″′(rk)(i))；
57、因此，秘密索引其中，最后，数据所有者do将(i,s(i1)i,…,s(iw)i)发送给数据服务器dsi；
58、所述数据用户将w维度的查询转化为w个长度为5的向量，使得查询向量的总长度为5w，每个维度的查询包含两部分，其中y′j用来表示查询属性，qi代表该维度对应的查询范围；数据用户如果只想查询某些区间，需要随机填充不需要的属性的区间；对于查询
59、1)y′i用于匹配标题，如果需要第j个属性，则y′i＝yi；否则随机选择y′j≠yj；然后随机选择ej′∈fp以获得一次多项式h(j)(u)＝y′j+ej′u；
60、2)对于查询范围qj，采用点交判定算法将范围转换为查询向量qj并且得到秘密共享多项式g(j)(u)＝qj+eju；
61、所以，秘密查询为其中最后，数据用户du将(i,s(q1)i,…,s(qw)i)发送给数据服务器dsi，i＝1,2；
62、所述数据服务器接收查询请求并与验证中心vc协同搜索匹配的文件；具体的：
63、1)对于每个标题tj，dsi计算c″(j)(i)＝f″(j)(i)+h(j)(i)；并且对于tj中的每个区间rr，dsi执行匹配区间交集判定算法piidmatch得到c′(r)(i)＝f′(r)(i)+g(r)(i)，
64、
65、令最后，数据服务器dsi将(i,l1(i),l2(i),…,lw(i))发送给验证中心vc进行验证；
66、2)对于每个lj(i)，验证中心vc使用(i,c″(j)(i))插值多项式ψ(j)(u)，其中ψ(j)(0)＝y′j-yj，如果：
67、a)ψ(j)(0)＝0，继续对lj(i)中的每个(i,c′(r)(i)),(i,c″(r)(i))运行区间交集判定算法piidverify，如果和满足区间交集判定算法的判定条件，返回1；否则返回0；
68、b)ψ(j)(0)≠0，随机选择一个区间返回1，并且为其他区间返回0；
69、3)收到从验证中心vc到返回的结果后，数据服务器dsi对区间rr(可能有多个区间)中的每个数据值drk执行匹配点交判定算法ppidmatch得到c(rk)(i)＝f(rk)(i)+g(j)(i)，其中rr是tj中对应结果为“1”的区间；令dsi将(i,l′1(i),l′2(i),…,l′w(i))发送验证中心vc进行验证；如果tj中的有多个区间对应结果“1”，则数据服务器dsi对每个区间重复上述过程并将结果合并到同一个lj′(i)中；
70、4)验证中心vc将步骤2)中获得的结果与从数据服务器收到的(i,l′1(i),l′2(i),…,l′w(i))相结合来处理以下内容：
71、a)对于步骤2)中ψ(j)(0)＝0的列表tj对应的lj′(i)，用(i,c(rk)(i))插值多项式φ(rk)(u)；如果φ(rk)(0)满足判定点交判定算法ppidverify的判定条件，继续使用(i,f″′(rk)(i))插值多项式φ′(rk)(u)，其中φ′(rk)(u)＝yrk；否则不插值；随后，验证中心vc把从同一列表tj中得到的所有y值相加，得到sj＝∑yrk，并将sj转换为相应的二进制形式σj；
72、b)对于步骤2)中ψ(j)(0)≠0的列表tj，不做任何运算；
73、c)将所有的二进制串σj取交集，只将所有串中同时为“1”的位置保留“1”，其余为“0”，从而得到新的二进制串σ；则σ中“1”所对应的文件为满足问询q的文件。
74、本发明实施例的技术方案可以具有的有益效果如下：
75、本发明实施例的技术方案一种分布式多维范围查询方法，包括以下步骤：步骤1，系统初始化，根据预设的安全参数生成系统参数；步骤2，构造索引列表，并将标题、区间以及区间内的数据值和文件标识使用秘密共享多项式转换为对应的秘密份额，获得秘密索引结构；步骤3，将w维度的查询转化为个向量，并使用秘密共享获得秘密查询向量；步骤4，根据查询请求搜索匹配的文件。本发明通过预先设定安全参数和秘密共享多项式,将用户的查询条件转换成对应的秘密份额,实现了用户查询信息的加密和保护,保证了查询过程的安全性和可靠性。
76、本发明提出了一种新的点交判定和区间交集判定方案，以及新的索引结构，通过结合判定方案、索引结构和shamir阈值方案，本在保护单维隐私的同时减低了通信复杂度并提高了查询效率。
1.一种分布式多维范围查询方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的分布式多维范围查询方法，其特征在于，所述步骤1，包括以下步骤：
3.根据权利要求2所述的分布式多维范围查询方法，其特征在于，在步骤2中，假设是系统中n个数据记录文件的集合，构造索引列表其中ii代表第j个列表且对于每一个ij，tj代表标题，代表m个区间，是区间rr中dr个数据值和十进制文件标识符对，使用秘密共享多项式转换为对应的秘密份额。
4.根据权利要求3所述的分布式多维范围查询方法，其特征在于，所述步骤2，包括以下步骤：
5.根据权利要求4所述的分布式多维范围查询方法，其特征在于，所述步骤3，包括以下步骤：
6.根据权利要求5所述的分布式多维范围查询方法，其特征在于，所述步骤4，包括以下步骤：
7.根据权利要求4-6任意一项所述的分布式多维范围查询方法，其特征在于，所述点交判定算法包括：
8.根据权利要求4-6任意一项所述的分布式多维范围查询方法，其特征在于，所述区间交集判定算法包括：
9.一种分布式多维范围查询装置，其特征在于，包括：
10.一种分布式多维范围查询系统，其特征在于，包括数据所有者、数据用户、云平台和验证中心vc，其中，云平台包含2个数据服务器；
