一种密文数据库隐私保护查询方法

摘要

本发明在不改变数据库管理系统内部运行机制的前提下，利用结构化的附加数据结构实现密文数据库表单查询，它包括含有索引查询结构的密文数据生成方法、以及全密文查询处理过程。数据库服务器首先判断用户持有的一定等级的密钥可检索的信息范围，之后在这个信息范围中进行快速信息检索，从而保护了数据库中信息的隐私性。

说明书

技术领域

本发明涉及数据库以及信息安全技术，尤其涉及一种密文数据库的查询方法。

背景技术

随着信息技术的不断发展，数据库系统的应用日益普及，利用数据库系统实现数据共享，可以使人们的日常生活和工作更加方便、快捷，但同时也给非正当地获取数据库的数据信息提供了更多的机会，数据库系统中的敏感数据保护问题日趋严重。

在诸多针对敏感数据的保护方法中，对数据库中的数据信息进行加密是一种非常有效的方案。但是另一方面，数据库中的数据经过加密后，原来相同的关键字可能变成了不同的密文信息，关键字之间的序关系也被破坏，从而使基于这些关键字进行查询的算法无法正常工作，如何在不对密文数据进行解密的条件下，针对密文数据进行查询是一项富有挑战性的工作。近几年，国内外学者围绕该问题进行了一系列的研究工作，并取得了一些成果，其中主要包括：基于对称密码的隐私保护数据查询方法；基于公钥密码的隐私保护数据查询方法；基于同态加密理论，对有序数据进行保序加密的数据查询方法。

隐私保护数据查询方法可应用于涉及政府、企业和个人的敏感数据的信息系统中，实现对不同部门、不同类型和不同涉密级别的分类管理，使不同的用户在查询同一个数据库，甚至是同一张数据表中的信息时，可使用的信息量各不相同。例如，在医院的电子病历管理系统中，通过使用本方案可以使患者的电子病历只可由患者本人、该患者的主治医生、该主治医生所在科室的主管医生，以及分管医疗的院长查看，包括数据库管理员在内的其他人均无法查看该患者的病历信息。最理想的情况下，可以实现该患者不同病症的主治医生和该主治医生所在科室的主管医生只能查看其负责诊治的病症对应的病历，该患者的其他病症的病历记录无法查看。

参考文献1(Zhiqiang Yang，Sheng Zhong，Rebecca N.Wright：“Privacy-Preserving Queries on Encrypted Data”，In ESORICS，2006)描述以隐私保护查询概念和最小信息暴露的理论为基础，以非可信服务器平台的攻击与信任模型为假设环境，设计的基于对称加密算法的隐私保护数据查询方案。

在该方案中，使用随机产生的密钥对明文表中每个元素进行加密处理。加密后对应每一个元素的密文数据都包含两部分，第一部分是使用分组加密算法对元素进行加密得到的结果；第二部分为检查值，是使用相同的加密算法对第一部分进行加密的结果，加密过程中采用的加密密钥是一个函数；该检查值能够使数据库判断其对应的元素是否符合查询的条件，因此在使用中又称该检查值为索引值。在存储的密文数据表中，密文数据的两个部分满足一个与用户输入的查询值相关联的检验等式，当把数据库中的元素导入这个与查询值相关联的检验等式时，通过把密文数据的两部分放入检验等式中就能够检验出该密文单元是否满足查询要求。在本发明中，该方案简称为“Y&R方案”。

该方案中构造的检验等式的特点是将用户输入的查询值加密后，以密钥的形式带入检验等式中，使存储在数据库中的数据与查询信息有效的关联在一起。当用户使用查询值进行查询时，客户端发送用户查询值加密后的数据给数据库服务器。该方案中，由于检验等式的使用，数据库服务器端进行数据检索过程中使用的数据均为密文数据；同时，服务器端不具备解密数据的能力。

但是，参考文献1设计的方案中存在以下不足之处：

1.运算速度较慢：在建立密文数据表时，针对每一条记录的每一个属性值分别采用两次分组加密算法，其计算的复杂度较大，从而造成密文数据表产生时的速度受到制约；而在进行查询时，如可能获得的查询结果较多时，由于同样的原因，会在查询时产生处理时间较长的问题，从而其方案在效率上有待提高。

2.查询方式单一：在建立密文数据表时，并未将序关系以某种方式存储在索引值中，从而使产生的密文数据表并未保持相同属性不同属性值之间的序关系。使得参考文献1中的方案只能处理精确查询一种查询方式。而在实际使用中，查询方式一般为精确查询与模糊查询两种方式。因此参考文献1设计的方案在实际使用中存在比较大的局限性。

3.安全性有限：在参考文献1设计的方案中，索引值以及检验等式中使用的密钥值的加密算法均使用分组加密算法。分组加密算法加解密过程使用同一个密钥，分组加密算法的安全性依赖于密钥。这样在一定程度上影响了安全性。

发明内容

为了克服上面归纳的技术问题，提出了本发明的数据存储结构和查询方案，本发明的目的是有效地提高数据表产生和查询过程的运算速度，并基于这种数据结构设计适用于密文数据区间查询的查询方案。本发明改进了参考文献1设计的基于分组密码的密文数据库存储与查询方案的显著缺点，设计了一种基于对称密码与安全散列函数的隐私保护数据查询方案，该方案在实现效率上明显优于现有的基于对称密码的隐私保护数据查询方案，并提供区间查询方式，满足不等式查询条件。

本发明的技术方案是：在加密表T′上存储了由保序列A_j的元素T_i，j生成的二元组T′_i，j(T′_i，j<1>，T′_i，j<2>)，其中T′_i，j<1>是采用分组加密算法，使用随机产生的加密密钥S₁处理T_i，j得到的密文值，通过解密过程Ds₁(T′_i，j<1>)可以得到T_i，j；T′_i，j<2>是元素T_i，j的索引值，在进行密文查询过程中，通过验证检验等式

T_i，j<2>＝H(T_i，j<1>，H(v))是否成立，判断是否返回该检验等式中对应的T′_i，j<1>，其中v为用户输入的查询值明文，H为加密运算函数。通过上面对于Y&R方案中未利用的技术特点的分析，本发明利用了散列函数计算方法H(*)改进Y&R方案中索引值生成算法，以及查询等式中保持密码隐私性的f运算，并借鉴单项散列函数中MAC的思想，构造了基于安全散列函数SHA—1算法的检验等式，改进的等式在不降低Y&R方案安全性的前提下，提高了数据处理速度，并充分利用了索引值使用时的特点。安全散列函数特点在于：能够对于任意的x，得到H(x)的处理速度快；对于任意给定h，要发现满足H(x)＝h的x在计算上是不可行的；能够处理任意长度的输入；以及原始数据与生成的消息摘要一一对应，即使原始数据的变化很小，也可以引起消息摘要的很大变化。这些特点满足检查等式的构造条件，并且满足本发明的设计要求。

本发明中使用的检验等式T′_i，j<2>＝H(T′_i，j<1>，H(v))在应用现有技术中检验等式设计思想的基础上，通过改造等式中使用的函数和数据结构，使原来f(v)计算的密钥值转化为类似于MAC密钥的查询值密钥H(v)。

在新构成的检验等式中，通过对用户查询值v进行散列运算，得到用户查询值v的摘要信息，并将该摘要信息H(v)作为查询密钥发送给数据库服务器。数据库服务器通过使用查询密钥和数据库中存储的元素密文值T′_i，j<1>，得到与索引值进行比对的查询值。通过判断是否满足检验等式，判断这个元素对应的密文值T′_i，j<1>是否符合查询条件。通过新构造的等式进行查询，客户端与数据库服务器之间通信的内容为敏感信息的摘要值，且安全散列函数运算中不包含加解密密钥，所有相关信息均作为输入，从而保证了本发明的安全性。

查询过程中，将满足检验等式的密文值T′_i，j<1>所在行中对应的返回属性的密文值提取至内存中，按照一定的格式封装后返回给用户。用户使用预先存储的加密密钥S₁解密得到的返回值，得到用户需要的明文信息。

区间索引值的构造基于定值索引值的结构，构造一个双射关系，通过对定值索引值进行处理产生区间索引值。密文数据表产生过程中，首先在明文数据表T中对保序列A_j的元素T_i，j进行排序，得到A_j列的元素序关系P{P_i<P_j，其中1≤i<j≤N}，然后对P中的元素P_i(1≤i≤N)进行映射，将Pi映射到区间[1，N]中，最后把映射值的二进制值放大，得到变换后的序关系值S_i。将S_i存储在定值索引值中，使原本无序的定值索引值呈现有序的状态。

因此，本发明提供一种密文数据库隐私保护查询方法，其特征在于，该方法包括以下步骤：

A、向第一查询单元输入明文查询；

B、第一查询单元对所述明文查询进行加密处理，将处理后的密文值查询发送给第二查询单元；

C、第二查询单元处理所述通过第一查询单元得到的密文值查询，将加密结果返回给第一查询单元；

D、第一查询单元利用预先存储在第一查询单元的第一密钥，对所述加密结果进行解密，得到解密结果a；

E、第一查询单元将解密结果a输出。

根据本发明的一个方面，在上述步骤A之前，还存在根据明文数据表生成第一密钥、第二密钥并将所述第一密钥、第二密钥预先存储在第一查询单元中的步骤。

根据本发明的一个方面，在上述步骤C中具体包括以下步骤：

C₁、使用第一算法生成密文数据；

C₂、使用第二算法生成索引值数据；

C₃、在第二查询单元中存储所述密文数据和所述索引值数据，其中所述索引值数据包含使用第二算法生成的查询使用散列值数据；

C₄、第二查询单元根据检验公式，利用所述密文数据和所述索引值数据得到所述加密结果。

根据本发明的一个方面，所述第一算法是对称密码算法，第二算法是安全散列函数。

根据本发明的一个方面，第二查询单元通过第二密钥和所述密文数据得到与所述索引值数据进行比对的查询值。

根据本发明的一个方面，所述第一查询单元是查询客户端，所述第二查询单元是数据库服务器，所述第一密钥是加密密钥，所述第二密钥是查询密钥。

本发明的有益效果是，在实现效率上明显优于现有的基于对称密码的隐私保护数据查询方案，并提供区间查询方式。本发明通过使用检验等式进行查询处理，从而使数据库服务器端进行用户查询请求处理时使用的数据均为密文数据，且服务器端不具备解密能力，也无需得到于明文内容关联的信息。

为了进一步说明本发明的原理及特性，以下结合附图和具体实施方式对本发明进行详细说明。

附图说明

图1是按照本发明一个实施方式的密文数据库查询系统的示意图。

图2是按照本发明一个实施方式的原始数据加密处理单元获得密文值和索引值的数据处理流程图。

图3是按照本发明一个实施方式的密文数据库查询系统的系统结构示意图。

图4是按照本发明一个实施方式的数据库存储信息的实例。

图5是按照本发明一个实施方式的密文数据库查询方法的循环处理数据过程的消耗时间统计图。

图6是按照本发明一个实施方式的密文数据库查询系统从接收到Q(v)开始，到提取加密结果的消耗时间统计图。

具体实施方式

下面结合附图详细描述本发明的具体实施方式。

图1是按照本发明一个实施方式的密文数据库查询系统的示意图。其中原始数据加密处理单元、查询客户端以及数据库服务器通过网络相互连接。所述网络包括但不限于局域网、广域网、因特网。

图2是按照本发明一个实施方式的原始数据加密处理单元获得密文值和索引值的数据处理流程图。众所周知，在数据库查询系统中，最为关键的是数据库中存储数据的数据结构，以及如何利用存储的数据结构进行查询的查询协议。

在按照本发明一个实施方式的密文数据库查询系统中设定的存储数据的数据结构如下：

T′_i，j<1>数据结构使用分组加密算法E()处理后得到的密文值，其密钥空间，明文空间与密文空间为使用符号E_S(M₁‖M₂)表示使用分组加密算法加密信息M₁与M₂的拼接值，其中加密密钥为S，M₁、M₂分别是一个k₁、k₂位串，满足k₁+k₂＝k₀。使用符号H(M₁‖M₂‖S)表示使用安全散列函数SHA—1计算M₁与M₂拼接值的信息摘要，其中S为查询密钥，密钥空间为，M₁、M₂位数不限。

为在数据库中建立加密表T′，首先从空间中随机选取加密密钥S₁、查询密钥S₂，并由使用者保管。从中为每个元素T_i，j随机选择r_i，j，其中r_i，j是k₂bit的随机字符串，即随机产生的k₂个0或者1。r_i，j的使用可以避免两个明文值相等的元素通过加密计算后，得到的密文值相等。然后，使用分组加密算法计算密文值T′_i，j<1>，将产生的查询密钥S₂与元素T_i，j、j(j为元素T_i，j所在列的列号，为了避免不同属性列中的元素有相同的查询值f(v)，在进行f运算之前，追加j给f(v)作为输入值的一部分。)按(T_i，j‖j‖S₂)的格式存储，并且在加密表T′中按如下数据格式进行保存：

   $=(E_{S_1}\left(T_{i,j}{\left|\right|r}_{i,j}\right),H\left(E_{S_1}\left(T_{i,j}\left|\right|r_{i,j}\right),H\left(T_{i,j}\left|\right|j\left|\right|S_2\right)\right))$

在这个数据结构中，T′_i，j<1>为明文数据表T中元素的密文值，T′_i，j<2>为该密文值的索引值，二元组两个元素之间满足新的检验等式：T′_i，j<2>＝H(T′_i，j<1>，H(T_i，j‖j‖S₂))。

按照本发明一个实施方式的区间查询方法，需要进行区间查询的属性列的数据结构如下：

   $=\left(E_{S_1}\left(T_{i,j}{\left|\right|r}_{i,j}\right),\left(S_i\left|\right|H\left(E_{S_1}\left(T_{i,j}\left|\right|r_{i,j}\right)\left|\right|\text{H}(T_{i,j},j,S_2)\right)\right)\right)$

在这个数据结构中，索引值T′_i，j<2>是在定值索引值的数据结构基础上，在高位拼接其进行简单变换后的序关系值S_i。这种保序的方法可以使数据表在不暴露元素值的条件下，实现密文保序存储。在此过程中附加暴露信息仅为暴露的元素序关系P。

在按照本发明一个实施方式的密文数据库查询系统中设定的查询协议如下：用A_j表示明文数据表T的第j个属性列。假设使用查询命令“select from T where $A_{j_0}=v$”进行查询，通过计算q＝H(v‖j₀‖S₂)，并把运算结果q与j₀、(j₁，...，j_e)按照Q(v)的格式打包发送给数据库服务器。其中j₀是查询值v所在的属性列，j₁，...，j_e是需要返回的属性列。Q(v)的格式如下：

 

q＝H(V‖j₀‖S₂)j₀j₁...j_e0/1

其中第一部分为转化后的摘要信息，其长度为20字节；第二部分为查询列的列号，长度为1字节；最后一部分是区间查询的标志位，如发送的为定值查询值则为空，如为最小查询值则为0，最大查询值为1，并位于整个数据包的最后，长度为1字节。

服务器接收到查询请求值Q(v)后遍历查询值所在j₀列的元素，测试$T_{{\mathrm{ij}}_0}<2>=H(T_{{\mathrm{ij}}_0}<1>,q)$是否成立，其中<2>为j₀列元素对应的索引值。对于第i₀行的元素，如上等式成立，服务器端受理程序会把返回给用户。用户使用加密密钥S₁解密收到的元素组$D_{S_1}({T\prime }_{i,j_0}<1>),...,D_{S_1}({T\prime }_{i,j_e}<1>),$得到T_i，j与r_i，j的拼接值，随后删除k₂字节的r_i，j得到T_i，j。

假设查询命令为“select  from T between $A_{j_0}=v_1\mathrm{and}$ and$A_{j_0}=v_2$”进行查询，为实现该查询，计算q₁＝H(v₁‖j₀‖S₂)和q₂＝H(v₂‖j₀‖S₂)并把得到的散列值q₁，q₂与j₀、(j₁，...，j_e)以Q(v₁)、Q(v₂)的方式发送到数据库服务器。其中Q(v₁)、Q(v₂)按Q(v)的格式。j₀是所查询的属性列，j₁，...，j_e是需要返回的属性列。

数据库服务器接收到查询后遍历j₀列的元素，提取j₀列元素对应的索引值，去掉索引值中高位存储的序号S_i后，测试是否与$T_{{\mathrm{ij}}_0}<2>=H(T_{{\mathrm{ij}}_0}<1>,q_1)$或者相等；对于第i₁行的元素，如测试成立，则记录该元素的索引值(或者<2>)；遍历索引值列元素<2>，测试不等式$T_{i_1,j_0}<2>\le T_{i,j_0}<2>\le T_{i_2,j_0}<2>$是否成立；对于第i₀行的元素，如上不等式成立，数据库会把${T\prime }_{i,j_0}<1>,...,{T\prime }_{i,j_e}<1>$返回给用户。

用加密密钥S₁解密收到的元素组$D_{S_1}({T\prime }_{i,j_0}<1>),...,D_{S_1}({T\prime }_{i,j_e}<1>),$得到T_i，j与r_i，j的拼接值，随后删除k₂字节的r_i，j得到T_i，j。

图3是按照本发明一个实施方式的密文数据库查询系统的系统结构示意图。该系统包括两大部分组成，一部分是查询客户端，另一部分是数据库服务器。查询客户端包括：查询转换器1、结果解密器6和密钥单元7。数据库服务器包括：查询分析器2、查询处理器3、密文提取单元4和带辅助数据结构的加密表5。

该系统的工作流程如下：

向查询客户端输入明文查询；

查询客户端中的查询转化器1接收该明文查询，然后对其进行转化，得到转化结果查询，然后将转化结果查询发送到查询分析器2；这种转化包括但不限于加密处理，所述转换结果查询包括但不限于密文值查询(优选地，转化结果查询包括密文值查询、查询列的列号、返回列的列号集合)；

查询分析器2将接收到的转化结果查询进行分析，并将分析结果发送到查询处理器3；

查询处理器3根据接收到的分析结果，按照本发明一个实施方式的上述查询协议，查询带辅助数据结构的加密表5，并将查询结果发送到密文提取单元4，其中带辅助数据结构的加密表5中存有加密数据表；

密文提取单元4根据接收到的查询结果，从带辅助数据结构的加密表5中获取对应的密文值，然后将加密结果发送给查询客户端；

查询客户端接收到返回的加密结果之后，将其发送到结果解密器6；

结果加密器6从密钥单元7中取得预先存储在密钥单元7中的对应密钥，然后对接收到的加密结果进行解密并去除随机串，得到解密后的结果；

查询客户端将解密后的结果返回给用户。

图4是按照本发明一个实施方式的数据库存储信息的实例。下面结合图1-4，说明按照本发明一个实施方式的查询过程。

1.明文数据处理过程

首先需要调用原始数据加密处理单元进行数据转化过程。例如第一行第二列的明文数据usual经过转化后处理为密文值：CF，FE，5A，A3，A3，A3，CF，88，...(共20个字节)；以及索引值：O2，FB，E2，CE，C1，60，04，27，B9，...(共20个字节)。同时随机产生加密密钥S₁、查询密钥S₂，并将变化后的密文数据表存储在图3中数据库服务器端的带辅助数据结构的加密表5中，将加密密钥S₁、查询密钥S₂保存在图3中查询客户端的密钥单元7中。到此为止，不再使用明文数据表。

2.密文数据查询过程

图3中的查询客户端接受到查询命令“select Name，Parents，Has_nurs，Form from T where Children＝1”时，查询转化器1计算Children＝1对应的查询值q，并发送由q、4(Children列的列号)以及(1、2、3)(返回列的列号)组成的Q(v)，即，将图3中的转化结果查询发送给数据库服务器。

数据库服务器接到查询请求后，首先通过查询分析器2进行分析，判断列号4是否对应区间查询结构，发现不是区间查询列，则将查询值q、查询列列号4、以及返回列列号1、2、3送入查询处理器3中，进行按照本发明一个实施方式的查询协议中所述的查询处理，将查询结果发送给密文提取模块4，密文提取模块4提取相应的密文值并发送给查询客户端程序。

3.解密过程

查询客户端收到返回的加密结果后，将加密结果送入结果解密器6中进行解密和去除随机串的操作，解密时使用预存在密钥模块7中的S₁。解密后的结果返回给用户。

本发明提高了参考文献1整个方案的运行速度，因此下面给出按照本发明一个实施方式与参考文献1中的方案的性能对比数据。为方便描述，按照本发明一个实施方式简称为L&Y系统，参考文献1中的方案简称为Y&R系统。

图5是按照本发明一个实施方式的密文数据库查询方法的循环处理数据过程的消耗时间统计图。图5中的横轴表示数据表容量，纵轴表示消耗时间，单位为毫秒。

对记录数量不同的原始明文数据表进行10次加密操作，每张数据表的处理时间取平均值，分别记录L&Y系统和Y&R系统从发送第一个数据到原始数据加密处理单元开始，到最后一个数据通过该单元变为密文数据库中存储的二元组的时间，其消耗时间如图5所示。

图6是按照本发明一个实施方式的密文数据库查询系统从接收到Q(v)开始，到提取加密结果的消耗时间统计图。图6中的横轴表示并发访问用户数，纵轴表示消耗时间，单位为毫秒。

对L&Y系统和Y&R系统中数据库服务器从接收到Q(v)开始，到提取加密结果的时间进行10次记录，记录了数据库服务器根据检验等式循环处理过程所消耗的时间的多次平均值，并记录了多用户同时访问时，数据库服务器处理全部请求消耗的时间，其消耗时间如图6所示。

从图5、6中可以看出，L&Y系统消耗的时间与Y&R系统消耗的时间比近似为1:3。

虽然以上描述了本发明的多个具体实施方式，但是本领域的技术人员应当理解，这些具体实施方式仅是举例说明，本领域的技术人员在不脱离本发明的原理和实质的情况下，可以对上述方法和系统的细节进行各种省略、替换和改变。例如，合并上述模块单元和/或方法步骤，从而按照实质相同的方法执行实质相同的功能以实现实质相同的结果则属于本发明的范围。因此，本发明的范围仅由所附权利要求书限定。