一种支持正负混合浮点数的密文范围查询方法和系统与流程

1.本技术涉及支持正负混合浮点数的密文范围查询技术领域，特别是涉及一种支持正负混合浮点数的密文范围查询方法和系统。


背景技术：

2.随着云计算等基础设施即服务的广泛应用，很多企业都将数据库放到了云端进行存储。范围查询是数据库中常用的查询方式，根据给定查询的起点和终点，返回满足该范围条件的数据。为了保证数据的安全性，企业在上传数据时几乎都对数据进行了加密。但传统的数据加密算法是对明文进行随机性的变换，破坏了明文的顺序信息，不能支持对密文数据的范围查询。如果将密文数据在云端进行解密后查询则又显然违背了数据加密时想提供的安全初衷，因此，设计支持密文数据的范围查询方法是一个非常有应用价值的研究方向。
3.支持密文数据的范围查询算法的核心是设计的加密算法要能够保持原来明文的顺序。现有较早的方案是基于不经意随机访问内存(oram，oblivious random access memory)来设计的，思想是在不暴露内存位置的前提下访问该位置的数据，如stefanov等人提出的基于oram的协议。全同态加密算法提出后，可以将明文进行全同态加密，然后在密文上执行比较运算从而完成范围查询。这两类方案有着比较明显的缺陷，基于oram的方案需要较高的网络带宽，协议交互轮数多。全同态加密方案密文扩展大，计算效率较差，因此都难以适用于大数据量的场景。相比而言，保序加密是目前最高效的支持范围查询的加密方案。这类加密方法的密文保持了原有明文的大小顺序，因此可以直接在密文上进行大小比较。agrawal等人于2004年首次提出了保序加密的概念，boldyreva等人于2009年首次给出了保序加密的安全性定义并进行了效率上的改进。2013年popa等人构造了第一个达到理想安全性的保序加密方案。2015年beneh等人对保序加密进行了安全方面的改进，将直接进行密文大小的比较改进为通过一个比较函数来计算两个密文的大小关系，这类更安全的方案称为揭序加密ore(order revealing encryption)。chenette、furukawa、lewi等人随后提出了一些效率改进版本的揭序加密算法。bogatov等人详细地分析和比较了现有揭序加密算法的安全性和效率。
4.现有的保序加密算法难以精确地刻画数据加密后的信息泄露量，因此方案的安全性分析后得到的结果不能准确反映出实际安全性。目前支持密文范围查询效率最高的是chenette等人提出的揭序加密方案，但是该方案只能针对数值类型为整数的明文进行加密和密文比较，而实际场景中的数值常常含有浮点型，这就使该方案的应用受到了很大的限制。目前基于揭序加密的范围查询只能支持符号一致的明文数据，现有方案中只支持正数，但理论上若数据全部是负数，则只需把比较结果取反即可，不能支持正负混合的明文数据加密后的密文比较。


技术实现要素：

5.基于此，针对上述技术问题，提供一种支持正负混合浮点数的密文范围查询方法
和系统，以解决现有方案中存在不支持浮点数的密文范围查询、不能支持正负混合的明文数据加密后的密文比较以及难以精确地刻画数据加密后的信息泄露量的问题。
6.第一方面，一种支持正负混合浮点数的密文范围查询方法，所述方法包括：
7.生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
8.将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
9.调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
10.云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
11.接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
12.上述方案中，可选地，所述第一算法为浮点型明文加密算法floatencrypt，包括：接收单精度浮点数m，安全参数λ长度的加密密钥和混淆密钥，所述密文数据表中数据m所在的行号index；
13.判断所述浮点数m的正负性，若m《0，令m
←‑
m，记符号位s＝1；若m≥0，符号位s＝0；
14.设定放大倍数δ＝106，提取出m的放大后的基数b和指数e；其中，所述指数e为真实指数加上38；
15.对长度为7比特的指数e进行编码；设整数m＝3，令
[0016][0017]
f为伪随机函数，其中，为密钥空间，[n]表示整数集合{1,2,
…
,n}，表示模m的剩余类；对待编码的数据p，设b1,b2,
…
,bn是p的二进制表示形式；对i∈[n]，计算
[0018]
ti＝f(key1,(i,b1b2…bi-1
||0
n-i
))+bi(mod m)
[0019]
其中，符号||表示数据级联；，其中，n取值7；
[0020]
令t＝t1||t2…
||tn，使伪随机函数f对24比特的基数b进行编码，输出v＝v1||v2…
||v
n2
；其中，n2取值24；添加上符号位，得到的m的编码为u＝s||t||v,数据m的编码函数为floatencode(m,key1)，所述函数的输出为u；
[0021]
令伪随机函数其中，表示自然数集合，表示包含32个分量的向量，每个分量取值都在中；计算mix＝r(key2,index)；
[0022]
计算明文数据m的密文符号表示u和mix按照分量模3相加，密文c＝c1||c2||
…
||c
32
，其中，c1为符号位s；
[0023]
输出所述密文c。
[0024]
上述方案中，进一步可选地，所述第二算法为范围查询陷门生成算法floattrapgen，包括：
[0025]
接收所述范围查询的明文起点值start和终点浮点数end，且满足start≤end，所述加密密钥和混淆密钥；
[0026]
计算范围查询起点的密文cstart＝floatencode(start,key1)；其中，所述key1为加密密钥；
[0027]
计算范围查询终点的密文cend＝floatencode(end,key1)；其中，所述key2为混淆密钥；
[0028]
输出范围查询的陷门trap＝(cstart,cend)。
[0029]
上述方案中，进一步可选地，所述调用第四算法为范围查询判定算法floatrangequery，包括：
[0030]
接收所述范围查询的陷门trap＝(cstart,cend)，数据表中密文c，所述密文c所在的数据行号index，混合密钥key2；
[0031]
对密文c进行去混淆，计算mix＝r(key2,index)，计算符号表示c和mix按照分量模3相减；
[0032]
调用第三算法，计算
[0033]
r1＝floatcompare(cstart,c)和r2＝floatcompare(cend,c)，
[0034]
若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果。
[0035]
上述方案中，进一步可选地，所述若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果，具体为：r1≠1表示对应的明文start≤m为第一条件，r2≠-1表示对应的明文m≤end为第二条件；若第一条件和第二条件同时成立，则表示密文c对应的明文m满足查询的范围[start,end]，所述第一结果为true，否则不满足，则所述第一结果为false。
[0036]
上述方案中，进一步可选地，所述第三算法为密文数据大小比较算法floatcompare，包括：
[0037]
接收密文数据c1和c2；
[0038]
算法输出：大小比较结果result。
[0039]
令所述c1＝u1||u2||
…
||u
32
，所述c2＝u'1||u'2||
…
||u'
32
，其中，所有的
[0040]
若c1和c2相同，则结果result＝0，算法结束；
[0041]
若u1≠u'1且u1＝0，则result＝1，否则result＝-1，算法结束；
[0042]
设i是使得ui≠u'i的最小正整数，则i＞1；
[0043]
若u'i＝ui+1(mod3)，则result＝-1，否则result＝1；
[0044]
若u1＝u'1＝1，则取反：
[0045]
result
←‑
result，算法结束；
[0046]
输出结果result。
[0047]
上述方案中，进一步可选地，所述输出结果result为-1表示所述c1对应的明文小于所述c2对应的明文；
[0048]
所述输出结果result为0表示所述c1对应的明文等于所述c2对应的明文；
[0049]
所述输出结果result为1表示所述c1对应的明文大于所述c2对应的明文。
[0050]
第二方面，一种支持正负混合浮点数的密文范围查询系统，所述系统包括：
[0051]
生成模块：用于生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
[0052]
发送模块：用于将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
[0053]
计算模块：用于调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
[0054]
记录模块：用于云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
[0055]
输出模块：用于接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
[0056]
第三方面，一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现以下步骤：
[0057]
生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
[0058]
将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
[0059]
调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
[0060]
云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
[0061]
接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
[0062]
第四方面，一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：
[0063]
生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
[0064]
将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
[0065]
调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
[0066]
云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
[0067]
接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
[0068]
本发明至少具有以下有益效果：
[0069]
本发明基于对现有技术问题的进一步分析和研究，认识到现有方案中存在不支持浮点数的密文范围查询、不能支持正负混合的明文数据加密后的密文比较以及难以精确地刻画数据加密后的信息泄露量的问题，本发明通过数据拥有者生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s，接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。本发明算法支持浮点数的加密以及对应密文比较和范围查询，算法效率高，效率和目前基于整数的效率最高的揭序加密方案几乎相同，支持正负
数混合的明文数据加密，并且加密后得到的密文数据可以方便地进行统一的比较和范围查询，本发明算法的密文数据进行大小比较时可以清楚地刻画出信息泄露量，由此对算法的安全性可以得到准确的分析结果。
附图说明
[0070]
图1为本发明一个实施例提供的支持正负混合浮点数的密文范围查询方法的流程示意图；
[0071]
图2为本发明一个实施例提供的支持正负混合浮点数的密文范围查询方法数据交互示意图；
[0072]
图3为本发明一个实施例提供的支持正负混合浮点数的密文范围查询方法的明文形式的数据库表图；
[0073]
图4为本发明一个实施例提供的支持正负混合浮点数的密文范围查询方法的密文形式的数据库表图；
[0074]
图5为一个实施例中计算机设备的内部结构图。
具体实施方式
[0075]
为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
[0076]
在一个实施例中，如图1所示，提供了一种支持正负混合浮点数的密文范围查询方法，包括以下步骤：
[0077]
生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
[0078]
将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
[0079]
调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
[0080]
云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
[0081]
接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
[0082]
在一个实施例中，所述第一算法为浮点型明文加密算法floatencrypt，包括：接收单精度浮点数m，安全参数λ长度的加密密钥和混淆密钥，所述密文数据表中数据m所在的行号index；
[0083]
判断所述浮点数m的正负性，若m《0，令m
←‑
m，记符号位s＝1；若m≥0，符号位s＝0；
[0084]
设定放大倍数δ＝106，提取出m的放大后的基数b和指数e；其中，所述指数e为真实指数加上38；
[0085]
对长度为7比特的指数e进行编码；设整数m＝3，令
[0086][0087]
f为伪随机函数，其中，为密钥空间，[n]表示整数集合{1,2,
…
,n}，表示模
m的剩余类；对待编码的数据p，设b1,b2,
…
,bn是p的二进制表示形式；对i∈[n]，计算
[0088]
ti＝f(key1,(i,b1b2…bi-1
||0
n-i
))+bi(mod m)
[0089]
其中，符号||表示数据级联；，其中，n取值7；
[0090]
令t＝t1||t2…
||tn，使伪随机函数f对24比特的基数b进行编码，输出v＝v1||v2…
||v
n2
；其中，n2取值24；添加上符号位，得到的m的编码为u＝s||t||v,数据m的编码函数为floatencode(m,key1)，所述函数的输出为u；
[0091]
令伪随机函数其中，表示自然数集合，表示包含32个分量的向量，每个分量取值都在中；计算mix＝r(key2,index)；
[0092]
计算明文数据m的密文符号表示u和mix按照分量模3相加，密文c＝c1||c2||
…
||c
32
，其中，c1为符号位s；
[0093]
输出所述密文c。
[0094]
在一个实施例中，所述第二算法为范围查询陷门生成算法floattrapgen，包括：
[0095]
接收所述范围查询的明文起点值start和终点浮点数end，且满足start≤end，所述加密密钥和混淆密钥；
[0096]
计算范围查询起点的密文cstart＝floatencode(start,key1)；其中，所述key1为加密密钥；
[0097]
计算范围查询终点的密文cend＝floatencode(end,key1)；其中，所述key2为混淆密钥；
[0098]
输出范围查询的陷门trap＝(cstart,cend)。
[0099]
在一个实施例中，所述调用第四算法为范围查询判定算法floatrangequery，包括：
[0100]
接收所述范围查询的陷门trap＝(cstart,cend)，数据表中密文c，所述密文c所在的数据行号index，混合密钥key2；
[0101]
对密文c进行去混淆，计算mix＝r(key2,index)，计算符号表示c和mix按照分量模3相减；
[0102]
调用第三算法，计算
[0103]
r1＝floatcompare(cstart,c)和r2＝floatcompare(cend,c)，
[0104]
若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果。
[0105]
在一个实施例中，所述若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果，具体为：r1≠1表示对应的明文start≤m为第一条件，r2≠-1表示对应的明文m≤end为第二条件；若第一条件和第二条件同时成立，则表示密文c对应的明文m满足查询的范围[start,end]，所述第一结果为true，否则不满足，则所述第一结果为false。
[0106]
在一个实施例中，所述第三算法为密文数据大小比较算法floatcompare，包括：
[0107]
接收密文数据c1和c2；
[0108]
算法输出：大小比较结果result。
[0109]
令所述c1＝u1||u2||
…
||u
32
，所述c2＝u'1||u'2||
…
||u'
32
，其中，所有的
[0110]
若c1和c2相同，则结果result＝0，算法结束；
[0111]
若u1≠u'1且u1＝0，则result＝1，否则result＝-1，算法结束；
[0112]
设i是使得ui≠u'i的最小正整数，则i＞1；
[0113]
若u'i＝ui+1(mod 3)，则result＝-1，否则result＝1；
[0114]
若u1＝u'1＝1，则取反：
[0115]
result
←‑
result，算法结束；
[0116]
输出结果result。
[0117]
在一个实施例中，所述输出结果result为-1表示所述c1对应的明文小于所述c2对应的明文；
[0118]
所述输出结果result为0表示所述c1对应的明文等于所述c2对应的明文；
[0119]
所述输出结果result为1表示所述c1对应的明文大于所述c2对应的明文。
[0120]
如图2所示，上述支持正负混合浮点数的密文范围查询方法中，明文数据拥有者利用加密密钥对数据进行加密后，由伪随机函数的特性保证了无法从密文恢复从明文。范围查询的起点和终点也通过查询陷门进行了同样的掩码操作，从而提供了查询时两个端点的安全性。另外，我们通过引入混淆密钥key2使得数据拥有者和云服务器之外的第三方攻击者无法通过观察数据库里的密文得到明文的相关信息(比如是否是同一明文的密文)，因为混淆后的密文完全变成了伪随机数。云服务器知晓混淆密钥key2用来对存储在数据库里的密文进行去混淆，服务器运行密文大小比较算法时可以得到两个数在哪一个比特位置不同的信息，因此密文数据泄露的关于明文的信息量只有1比特。这点与chenette等人提出的揭序加密方案中的信息泄露量相同，在考虑安全和效率的权衡下，1比特的泄露是可以接受的。
[0121]
本实施例所设计的算法都是基于对称密码原语(主要是伪随机函数)，算法效率高。此外，对于浮点数，提取基数和指数也是比较快速的。我们经过实际测试，浮点数的密文范围查询效率几乎和chenette等人提出的整型数据范围查询方案的效率相同，保证了实际中的可用性。此外，可以看出针对每次范围查询，查询陷门只需要计算一次。密文大小的比较算法仅与陷门和数据位置index有关，因此算法可以采用多线程方式并性化地执行，能够显著提高查询时的计算效率。从明文数据对加密算法可以看出，算法能够支持明文数据的灵活扩展，满足实际中数据的增加(或删除)等动态变化时的场景需求。
[0122]
本实施例设计了一种高效安全的密文范围查询方法，可以支持正负数混合的浮点型数据的加密范围查询，拓展了现有只能基于正整数类型的范围查询方案，由此能够支持更多的查询场景应用。算法执行效率高并且支持并性化处理密文数据的范围判定，算法也具备良好的可扩展性，非常适合于大规模数据量时的外包数据库的范围查询。算法引入混淆密钥进一步加强了数据的安全性，第三方攻击者无法知晓密文数据的大小关系和对应明文是否相同，这是现有保序加密和揭序加密所不具有的特性。本实施例算法支持浮点数的加密以及对应密文比较和范围查询，算法效率高，效率和目前基于整数的效率最高的揭序加密方案几乎相同，支持正负数混合的明文数据加密，并且加密后得到的密文数据可以方便地进行统一的比较和范围查询，本发明算法的密文数据进行大小比较时可以清楚地刻画出信息泄露量，由此对算法的安全性可以得到准确的分析结果。
[0123]
在一个实施例中，如图2所示，本实施例提出了一种支持浮点数的高效安全的密文数据范围查询方法，可应用于数据外包等密文查询场景中。下面描述所设计的密文范围查询方法，主要包括四个算法：浮点型明文加密算法floatencrypt，范围查询陷门生成算法floattrapgen，密文数据大小比较算法floatcompare，范围查询判定算法floatrangequery。
[0124]
描述算法之前，我们先设计对于浮点数的编码方法，浮点数可以采用科学计数法进行表示，对正值的浮点数m，我们可以表示为m＝b
·
10e，其中b表示区间[1,10)之间的小数，称为基数。e称为指数，可以为负数，e为负时表示m小于1。
[0125]
为了能将浮点数进行编码，对于浮点数m，首先提取m的基数b和指数e，然后将基数放大一定的倍数δ并取整得到整数b。我们对整数b和指数e利用现有针对整数的方法分别进行加密编码。如果m是负数，我们单独编码其符号位。可以看出，放大倍数δ决定了我们进行数据比较时的精度。以常用的单精度浮点数为例，这里我们可以选择δ＝106，从而达到比较精度为7位有效数字(基数的1位整数数字加上放大后的6位整数数字)。
[0126]
对于单精度浮点数，指数e的范围在[-38,38]之间，为了省去单独编码指数的符号位，我们将提取的指数全部加上38将其变成非负数。此时指数范围变成了[0,76]，最长用7个比特就可以表示。
[0127]
综合起来，放大后的基数b的范围为[1000000,9999999]，最长使用24比特就可以表示。加上m的符号位，最终我们可以用7+24+1＝32个比特就能表示出m。32比特的编码长度也非常适合编程实现时利用计算机中的整型来表示。
[0128]
下面我们依次描述密文范围查询方法的四个算法。
[0129]
算法1：浮点型明文加密算法floatencrypt
[0130]
算法输入：单精度浮点数m，安全参数λ长度的加密密钥key1和混淆密钥key2，数据表中数据m所在的行号index；
[0131]
算法输出：浮点数m的密文c。
[0132]
算法描述：(1)判断m的正负性，若m《0，令m
←‑
m，记符号位s＝1；若m≥0，符号位s＝0。
[0133]
(2)设定放大倍数δ＝106，提取出m的放大后的基数b和指数e，这儿指数e为真实指数加上38。
[0134]
(3)首先对长度为7比特的指数e进行编码。设整数m＝3，令
[0135][0136]
是一个伪随机函数，其中为密钥空间，[n]表示整数集合{1,2,
…
,n}，表示模m的剩余类。对需要编码的数据p，设b1,b2,
…
,bn是p的二进制表示形式。对i∈[n]，计算
[0137]
ti＝f(key1,(i,b1b2…bi-1
||0
n-i
))+bi(mod m)
[0138]
其中符号||表示数据级联。
[0139]
令t＝t1||t2…
||tn，同样地，使用上面的伪随机函数f对24比特的基数b进行编码，得到输出v＝v1||v2…
||vn。注意这两次编码中的n取值不同，分别为7和24。添加上符号位，记最终得到的m的编码为u＝s||t||v,我们记这样对数据m的编码函数为floatencode(m,key1)，该函数的输出为u。
[0140]
(4)令伪随机函数其中表示自然数集合，表示包含32个分量的向量，每个分量取值都在中。计算mix＝r(key2,index)。
[0141]
(5)进行密文混淆，计算明文数据m的密文符号表示u和mix按照分量模3相加(符号位除外)，密文c＝c1||c2||
…
||c
32
，其中c1为符号位s。
[0142]
(6)输出密文c。
[0143]
算法2:范围查询陷门生成算法floattrapgen
[0144]
为了保护查询范围的安全性，需要对查询的起点和终点也进行加密，生成对应的范围查询陷门。云服务器基于这个查询陷门进行密文比较，不能知晓明文形式的起点和终点。
[0145]
算法输入：范围查询的明文起点值start和终点浮点数end,满足start≤end，密钥key1和key2；
[0146]
算法输出：范围查询的陷门trap＝(cstart,cend)。
[0147]
算法描述：
[0148]
(1)计算范围查询起点的密文cstart＝floatencode(start,key1)；
[0149]
(2)计算范围查询终点的密文cend＝floatencode(end,key1)；
[0150]
(3)输出范围查询的陷门trap＝(cstart,cend)。
[0151]
算法3:密文数据大小比较算法floatcompare
[0152]
算法输入：密文数据c1和c2；
[0153]
算法输出：大小比较结果result。
[0154]
算法描述：
[0155]
(1)令c1＝u1||u2||
…
||u
32
，c2＝u'1||u'2||
…
||u'
32
，按之前密文的计算可知所有的
[0156]
(a)若c1和c2完全相同，则结果result＝0，算法结束；
[0157]
(b)若u1≠u'1且u1＝0，则result＝1，否则result＝-1，算法结束；
[0158]
(c)设i是使得ui≠u'i的最小正整数,此时i＞1，若u'i＝ui+1(mod 3)，则令result＝-1，否则result＝1.
[0159]
根据我们的编码顺序，这里会先比较符号位，然后是指数的大小，指数若是相同的才比较后续基数的大小。根据这样的编码顺序，我们可以不用再单独区分指数和基数的大小比较，因为指数能优先决定出数据的大小。
[0160]
(2)根据符号位修正结果。若u1＝u'1＝1，则将结果取反：
[0161]
result
←‑
result，算法结束。
[0162]
(3)输出结果result。可以看出，结果为-1，0，1分别表示c1对应的明文小于，等于，大于c2对应的明文。
[0163]
算法4：范围查询判定算法floatrangequery
[0164]
算法输入：范围查询的陷门trap＝(cstart,cend)，数据表中密文c，密文c所在的数据行号index，混合密钥key2；
[0165]
算法输出：密文c是否位于查询范围的判定结果result。
[0166]
算法描述：
[0167]
(1)对密文c进行去混淆，计算mix＝r(key2,index)，计算符号表示c和mix按照分量模3相减(符号位除外)；
[0168]
(2)调用密文数据大小比较算法floatcompare，计算
[0169]
r1＝floatcompare(cstart,c)和r2＝floatcompare(cend,c)，
[0170]
若r1≠1且r2≠-1，则令结果result＝true，否则令result＝false。
[0171]
容易看出，根据比较算法floatcompare的输出，r1≠1表示对应的明文start≤m,r2≠-1表示对应的明文m≤end。因此这两个条件同时成立就表示密文c对应的明文m满足查询的范围[start,end]，结果用true表示，否则不满足时用false表示。
[0172]
(3)输出c是否处于查询范围的判定结果result。
[0173]
我们利用以上四个算法(算法1至算法4)设计的支持正负混合浮点数的密文范围查询方法执行步骤如下(如图1所示)，其中步骤1和步骤2对应于密文数据表生成、发送和存储阶段，步骤3至步骤6对应于数据范围查询和结果返回阶段。
[0174]
步骤1：数据拥有者生成加密密钥key1和混淆密钥key2，调用算法1对数据表中指定列的每个明文浮点数据进行加密，形成整个密文数据表。
[0175]
步骤2：数据拥有者将密文数据表发送给云服务器，云服务器接收并存储该密文数据表。
[0176]
步骤3：针对范围查询的起点和终点，数据拥有者调用算法2生成查询陷门trap，将查询陷门trap发送给云服务器。
[0177]
步骤4：云服务器收到查询陷门trap，调用算法4(其中会自动调用算法3)，并记录算法4返回true的所有数据行index的集合s。
[0178]
步骤5：云服务器返回集合s给数据拥有者。
[0179]
步骤6：数据拥有者接收集合s，范围查询结束，可根据实际需求对集合s表示的数据记录做进一步的处理。
[0180]
本实施例可以支持正负数混合的浮点型数据的加密范围查询，拓展了现有只能基于正整数类型的范围查询方案，由此能够支持更多的查询场景应用。算法执行效率高并且支持并性化处理密文数据的范围判定，算法也具备良好的可扩展性，非常适合于大规模数据量时的外包数据库的范围查询。算法引入混淆密钥进一步加强了数据的安全性，第三方攻击者无法知晓密文数据的大小关系和对应明文是否相同，这是现有保序加密和揭序加密所不具有的特性。本实施例算法支持浮点数的加密以及对应密文比较和范围查询，算法效率高，效率和目前基于整数的效率最高的揭序加密方案几乎相同，支持正负数混合的明文数据加密，并且加密后得到的密文数据可以方便地进行统一的比较和范围查询，本发明算法的密文数据进行大小比较时可以清楚地刻画出信息泄露量，由此对算法的安全性可以得到准确的分析结果。
[0181]
在一个实施例中，为了简便起见，假设数据拥有者有一个数据表，包含了10个人的某种实验数据(数据类型为浮点型)，数据字段包括编号index，姓名name，实验数据data，明文形式的数据表如图2所示。
[0182]
第一步：数据拥有者加密实验数据字段，形成密文数据表，如图3和图4所示。
[0183]
选择基于sha-256的伪随机函数，明文加密算法floatencrypt中的函数f和r都基于sha-256来进行实现，加密密钥key1和混淆密钥key2都是16字节，即安全参数λ为128比
特。具体地，
[0184]
key1[16]＝{0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,0x10}；
[0185]
key2[16]＝{0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,0x10,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08}.
[0186]
调用明文加密算法floatencrypt对每个明文数据依次进行加密，形成的密文形式的数据表如图3所示。数据拥有者将密文数据表和混淆密钥key2以安全的方式(比如通过tls协议)发送给云服务器，实现数据加密外包。
[0187]
第二步：根据查询范围的起点和终点生成查询陷门。
[0188]
假设现在查询范围的起点start＝-200.26，终点end＝1.2，数据拥有者调用范围查询陷门生成算法floattrapgen生成该查询范围的查询陷门trap为：
[0189]
(12111021200022001021212111212102,02110001200012200000111022012101)。
[0190]
然后数据拥有者将查询陷门trap发送给云服务器。
[0191]
第三步：云服务器根据密文数据表和查询陷门进行范围查询。
[0192]
云服务器读取密文数据表，根据收到的查询陷门进行数据比较，判定数据表的每行的实验数据密文值是否在查询的范围之内，如果在则输出该行的行号index。具体地，对每行的密文数据，调用范围查询判定算法floatrangequery，如果该判定算法输出true，则将该数据行编号index保存起来，遍历完整个数据表后，得到满足查询范围的数据行编号集合s＝{2,5,6,7,10}，这与明文方式的查询结果一致。云服务器将该查询结果发回给数据拥有者，查询结束。
[0193]
应该理解的是，虽然图1的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1中的至少一部分步骤可以包括多个步骤或者多个阶段，这些步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤中的步骤或者阶段的至少一部分轮流或者交替地执行。
[0194]
在一个实施例中，提供了一种支持正负混合浮点数的密文范围查询系统，包括以下程序模块：
[0195]
生成模块：用于生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；
[0196]
发送模块：用于将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；
[0197]
计算模块：用于调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
[0198]
记录模块：用于云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；
[0199]
输出模块：用于接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。
[0200]
关于支持正负混合浮点数的密文范围查询系统的具体限定可以参见上文中对于
支持正负混合浮点数的密文范围查询方法的限定，在此不再赘述。上述支持正负混合浮点数的密文范围查询系统中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。
[0201]
在一个实施例中，提供了一种计算机设备，该计算机设备可以是终端，其内部结构图可以如图5所示。该计算机设备包括通过系统总线连接的处理器、存储器、通信接口、显示屏和输入系统。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的通信接口用于与外部的终端进行有线或无线方式的通信，无线方式可通过wifi、运营商网络、nfc(近场通信)或其他技术实现。该计算机程序被处理器执行时以实现一种支持正负混合浮点数的密文范围查询方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入系统可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。
[0202]
本领域技术人员可以理解，图5中示出的结构，仅仅是与本技术方案相关的部分结构的框图，并不构成对本技术方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。
[0203]
在一个实施例中，提供了一种计算机设备，包括存储器和处理器，存储器中存储有计算机程序，涉及上述实施例方法中的全部或部分流程。
[0204]
在一个实施例中，提供了一种计算机可读存储介质，其上存储有计算机程序，涉及上述实施例方法中的全部或部分流程。
[0205]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和易失性存储器中的至少一种。非易失性存储器可包括只读存储器(read-only memory，rom)、磁带、软盘、闪存或光存储器等。易失性存储器可包括随机存取存储器(random access memory，ram)或外部高速缓冲存储器。作为说明而非局限，ram可以是多种形式，比如静态随机存取存储器(static random access memory，sram)或动态随机存取存储器(dynamic random access memory，dram)等。
[0206]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0207]
以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术专利的保护范围应以所附权利要求为准。

技术特征：
1.一种支持正负混合浮点数的密文范围查询方法，其特征在于，所述方法包括：生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。2.根据权利要求1所述的方法，其特征在于，所述第一算法为浮点型明文加密算法floatencrypt，包括：接收单精度浮点数m，安全参数λ长度的加密密钥和混淆密钥，所述密文数据表中数据m所在的行号index；判断所述浮点数m的正负性，若m<0，令m
←‑
m，记符号位s＝1；若m≥0，符号位s＝0；设定放大倍数δ＝106，提取出m的放大后的基数b和指数e；其中，所述指数e为真实指数加上38；对长度为7比特的指数e进行编码；设整数m＝3，令f:f为伪随机函数，其中，为密钥空间，[n]表示整数集合{1,2,
…
,n}，表示模m的剩余类；对待编码的数据p，设b1,b2,
…
,b
n
是p的二进制表示形式；对i∈[n]，计算t
i
＝f(key1,(i,b1b2…
b
i-1
||0
n-i
))+b
i
(modm)其中，符号||表示数据级联；其中，n取值7；令t＝t1||t2…
||t
n
，使伪随机函数f对24比特的基数b进行编码，输出v＝v1||v2…
||v
n2
；其中，n2取值24；添加上符号位，得到的m的编码为u＝s||t||v,数据m的编码函数为floatencode(m,key1)，所述函数的输出为u；令伪随机函数r:其中，表示自然数集合，表示包含32个分量的向量，每个分量取值都在中；计算mix＝r(key2,index)；计算明文数据m的密文符号表示u和mix按照分量模3相加，密文c＝c1||c2||
…
||c
32
，其中，c1为符号位s；输出所述密文c。3.根据权利要求2所述的方法，其特征在于，所述第二算法为范围查询陷门生成算法floattrapgen，包括：接收所述范围查询的明文起点值start和终点浮点数end，且满足start≤end，所述加密密钥和混淆密钥；计算范围查询起点的密文cstart＝floatencode(start,key1)；其中，key1为加密密钥；计算范围查询终点的密文cend＝floatencode(end,key2)；其中，key2为混淆密钥；输出范围查询的陷门trap＝(cstart,cend)。
4.根据权利要求3所述的方法，其特征在于，所述调用第四算法为范围查询判定算法floatrangequery，包括：接收所述范围查询的陷门trap＝(cstart,cend)，数据表中密文c，所述密文c所在的数据行号index，混合密钥key2；对密文c进行去混淆，计算mix＝r(key2,index)，计算符号表示c和mix按照分量模3相减；调用第三算法，计算r1＝floatcompare(cstart,c)和r2＝floatcompare(cend,c)，若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果。5.根据权利要求4所述的方法，其特征在于，所述若所述r1≠1且r2≠-1，则第一结果result＝true，否则第一结果result＝false，输出第一结果，具体为：r1≠1表示对应的明文start≤m为第一条件，r2≠-1表示对应的明文m≤end为第二条件；若第一条件和第二条件同时成立，则表示密文c对应的明文m满足查询的范围[start,end]，所述第一结果为true，否则不满足，则所述第一结果为false。6.根据权利要求4所述的方法，其特征在于，所述第三算法为密文数据大小比较算法floatcompare，包括：接收密文数据c1和c2；算法输出：大小比较结果result；令所述c1＝u1||u2||
…
||u
32
，所述c2＝u'1||u'2||
…
||u'
32
，其中，所有的u
i
,若c1和c2相同，则结果result＝0，算法结束；若u1≠u'1且u1＝0，则result＝1，否则result＝-1，算法结束；设i是使得u
i
≠u'
i
的最小正整数，则i＞1；若u'
i
＝u
i
+1(mod3)，则result＝-1，否则result＝1；若u1＝u'1＝1，则取反：result
←‑
result，算法结束；输出结果result。7.根据权利要求6所述的方法，其特征在于，所述输出结果result为-1表示所述c1对应的明文小于所述c2对应的明文；所述输出结果result为0表示所述c1对应的明文等于所述c2对应的明文；所述输出结果result为1表示所述c1对应的明文大于所述c2对应的明文。8.一种支持正负混合浮点数的密文范围查询系统，其特征在于，所述系统包括：生成模块：用于生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；发送模块：用于将所述密文数据表发送给云服务器，云服务器接收并存储所述密文数据表；计算模块：用于调用第二算法生成所述待查询密文的查询陷门trap，将所述查询陷门trap发送云服务器；
记录模块：用于云服务器收到查询陷门trap，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回true的所有数据行index的集合s；输出模块：用于接收云服务器发送的所述集合s，得到所述待查询密文的范围查询结果。9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至7中任一项所述的方法的步骤。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至7中任一项所述的方法的步骤。

技术总结
本发明公开了一种支持正负混合浮点数的密文范围查询方法和系统，本发明通过数据拥有者生成待查询密文的加密密钥和混淆密钥，调用第一算法对待查询密文数据表中指定列的每个明文浮点数据进行加密，生成密文数据表；将密文数据表发送给云服务器，云服务器接收并存储密文数据表；调用第二算法生成待查询密文的查询陷门Trap，将查询陷门Trap发送云服务器，调用第四算法生成所述待查询密文范围的判定结果，并记录所述第四算法返回True的所有数据行index的集合S，接收云服务器发送的所述集合S，得到所述待查询密文的范围查询结果。支持浮点数的加密以及对应密文比较和范围查询，算法效率高，支持正负数混合的明文数据加密，可以清楚地刻画出信息泄露量。楚地刻画出信息泄露量。楚地刻画出信息泄露量。


技术研发人员：潘光明
受保护的技术使用者：翼健（上海）信息科技有限公司
技术研发日：2023.02.23
技术公布日：2023/7/19