加密域信息隐藏技术很好地结合了加密和信息隐藏的优点, 可以在不暴露数据隐私的情况下对数据进行信息隐藏处理, 适用于网络空间安全下的云计算处理, 是信息安全领域的一个研究热点^{[1, 2]}.

随着计算机技术的快速发展以及云计算时代的到来, 人们越来越多地把敏感数据(如涉及个人隐私、具有重大商业价值等)以数据库形式上传到云端进行存储和发布, 此时需要考虑数据隐私及数据安全等问题^{[3, 4]}.为了避免聘请专业管理人员的昂贵费用, 数据库服务(database as a service, 简称DaaS, 可以提供与本地数据库一样的数据管理服务)^[5]应运而生, 数据拥有者将自身的数据库访问、维护、管理等任务委托给专门的第三方管理, 用户利用不同的访问特权可以获取所需要的数据.

在这种新兴的数据库服务模式中, 将数据库直接交给非可信的数据库服务提供者, 有数据隐私暴露和数据被非法篡改的安全问题, 因此有必要对数据库进行加密并利用数据库水印等技术来保护数据安全.传统上, 数据库安全主要采用用户身份验证和用户权限管理^[6], 在访问过程中保证数据库的完整性、一致性以及数据的整体质量^[7].在明文域, 可以利用认证水印技术来认证数据的完整性, 如, 可通过半脆弱水印来认证图像的完整性^{[8, 9]}.近年来, 越来越多的黑客事件表明:访问控制防线一旦被破解, 数据就失去了保护, 此时, 敏感数据将直接被攻击者随意非法使用.针对这个问题, 一个有效手段是对数据库进行加密, 这样在访问控制失效时, 数据可以得到加密算法的保护.

数据加密后如何管理和操作, 是数据库加密研究的一个重要方面.目前, 数据库加密的主要技术有随机数求和、多项式函数、存储桶、秘密同态、子密钥和加密智能卡等^[10].这些方法运用于不同的场景, 但都存在一个弊端——加密后的数据库不能进行对比操作.数据库的对比操作涉及到索引技术^[11], 如果加密后索引失效, 那么数据库的操作性就会降低.因此, 文献[10]率先提出了一种基于数值型数据的保序加密(order- preserving encryption, 简称OPE)方案, 能够保证密文顺序和对应明文顺序的一致, 在不解密情况下, 允许对加密数据进行比较操作.这样, 等式和范围查询(MAX, MIN, COUNT, GROUPBY, ORDERBY)等关系运算都可以直接应用于加密数据.文中, Agrawal等人并没有给出算法正式的安全性证明.为了确保攻击者即使得到全部密文也得不到除顺序以外的其他有用信息, Boldyreva等人提出了一种利用随机保序函数和超几何分布设计的可证安全的OPE算法^[12], 该算法适用于云计算下的数据隐私保护, 并且取得了很好的效果^{[13, 14]}.接着, Boldyreva等人进一步分析了OPE算法的安全性, 提出了一种可提高任何OPE安全性的Modular OPE方案^[15], 该方案下, 加密后的密文不再严格保序, 但仍允许范围查询——模查询.基于保序加密的安全分析还有许多研究^[16-18], 很好地解决了保序加密的安全性问题.

数据库与一般多媒体数据有所不同, 它具有低冗余、低敏感、无序、更新频繁等特点, 嵌入时需要进行特殊的设计, 需要考虑两个问题:①数据冗余小, 数据库不同字段的属性要求不同, 难以找到大量可嵌水印空间; ②进行完整性认证时, 要求水印算法有很强的敏感性.目前, 针对明文数据库有几个水印算法.Agrawal等人^[19]在允许一定的误差范围内对数值型数据的LSB(least significant bits)进行水印替换操作, 该算法易于实现, 但鲁棒性较差, 抗攻击能力较弱.随后, Sion等人^[20]通过修改连续序列的数据分布特征来实现水印嵌入的算法.该算法具有较好的鲁棒性, 但只适用于具有相同分布、数值相差不大的数据.由于数据库中不同字段的取值范围各不相同, 因而限制了水印的嵌入容量.接着, Zhou等人^[21]提出一种基于混沌的DCT域关系数据库水印算法, 利用主键哈希值选出有效的元组作为载体, 并对其候选属性进行DCT变换, 然后把水印嵌入到中频系数中.在DCT域中嵌入可以将水印能量分散, 弥补了空域水印算法隐蔽性不足的问题.上述算法都有一个共同之处:在不影响数据库使用的情况下, 允许对数据做一些稍微的改动.由于数据库中数据冗余非常小, 需要设计比较复杂的寻找方案来确定嵌入水印的候选数据.此外, 当前的数据库水印技术主要针对于明文数据在云环境下有数据隐私可能暴露的安全问题.

考虑到云环境下数据隐私保护和数据安全的需要, 本文提出了一种保序加密域数据库认证水印算法.该算法首先对数据库某一属性列数据进行保序加密, 加密数据分组后进行DCT变换, 然后, 每组随机选取一个交流系数并用哈希算法生成认证水印信息; 利用QIM(quantization index modulation)算法将水印嵌入到直流系数中, 然后进行IDCT变换, 得到含水印信息的加密数据库; 数据库的完整性认证可通过比对交流系数的哈希值和直流系数中的水印信息来完成.本文所提出的算法很好地结合了保序加密的特点:(1)利用了保序概率加密引入的冗余, 使得加密数据库里的每个数值都可用于水印嵌入, 没有明文数据库难以寻找嵌入位置的问题; (2)水印嵌入步长根据密文可修改范围进行设计, 确保了加密数据的水印嵌入不会影响到明文数据的正确恢复, 即, 对加水印后的加密数据库直接解密可以得到原数据库.实验结果表明, 本文所提出的加密域水印算法不仅可以用于保护数据库数据的隐私, 而且能检测出不同程度的篡改, 适用于云环境下的数据库数据隐私保护和完整性认证.

1 保序概率加密算法^[12]

Boldyreva等人在文献[12]中提出了一种利用随机保序函数和超几何分布设计的可证安全的OPE算法.其根据语义安全的概念定义了OPE算法的理想安全状态, 并给出了OPE算法的安全性证明, 即:攻击者即使得到全部密文, 除了密文的顺序以外, 就再也得不到其他任何有用的信息.保序加密框架(OPES)能够保证密文顺序和对应明文顺序的一致性, 在不解密情况下, 它允许查询操作直接应用在加密数据上.

下面是对保序概率加密算法^[12]的介绍和相应说明.

1.1 OPES定义

若E是一个保序加密函数, p₁和p₂是两个明文值, 并且有密文c₁=E(p₁), c₂=E(p₂), 则有:if (p₁ < p₂) then (c₁ < c₂).

1.2 随机保序函数和超几何分布的关系

●  超几何分布

在一个抽球模型中, 假若有N个球, 其中黑球M个, 则白球N-M个, 每次不放回地随机抽取一个球.用随机变量X表示在抽取的y个球中黑球的个数, 那么X=x的概率为

$ {P_{HGD}}(x;N, M, y) = \frac{{\left( \begin{array}{l} y\\ x \end{array} \right) \cdot \left( \begin{array}{l} N - y\\ M - x \end{array} \right)}}{{\left( \begin{array}{l} N\\ M \end{array} \right)}} $

(1)

●  随机保序函数

假设有明文域[M]和密文域[N], N > M, 从密文域[N]中随机抽取M个不同的整数组成有序集合S, 构造了一个保序函数f, 把第i个明文m∈[M]映射到第i个密文c∈S.那么, 一个保序函数f对应唯一的组合C_N^M.为更好地理解该过程, 给出明文和密文映射关系的例子, 如图 1所示.

对于M, N∈ℕ, 任何x, x+1∈[M], y∈[N], 有:

$ {\text{Pr}}\left[ {f(x) \leqslant y < f(x + 1):f\xleftarrow{\$ }OP{F_{[M], [N]}}} \right] = \frac{{\left( \begin{gathered} y \hfill \\ x \hfill \\ \end{gathered} \right) \cdot \left( \begin{gathered} N - y \hfill \\ M - x \hfill \\ \end{gathered} \right)}}{{\left( \begin{gathered} N \hfill \\ M \hfill \\ \end{gathered} \right)}} $

(2)

其中, OPF_{[M], [N]}为包含所有保序函数f的集合, $ f\mathop \leftarrow \limits^\$ OP{F_{[M], [N]}}$表示从集合中均匀随机抽取一个保序函数f.

根据公式(1)、公式(2)可知, 我们可以把构造随机保序函数($f([M])\mathop \to \limits^{映射} [N]$)看做一个抽球实验(有N个球, 其中有黑球M个).

1.3 保序概率加密

文献[12]中, 所用的保序概率加密算法具有可证明的安全性, 其加密过程和解密过程如下所示.

上述算法中, 密钥表(key_table)是一个保存抽样点的n×2矩阵, 密钥表初始是空的, 随着加密明文越多而增加.在整个加密过程中共用该密钥表, 其作用类似于使用同一个随机保序函数f, 使得每次加密都沿着该函数进行.解密过程中, 密钥表只作查询使用, 并不会有所增加.

与文献[12]中描述的算法相比, 第5行~第11行进行了重新描述, 以便更好地理解本文的认证水印算法, 见第2.3节图 4及其描述说明.

1.4 各OPE算法比较

为逐步解决OPE的安全性问题, 越来越多的研究(如文献[10, 12, 15])都提出了新的OPE方案.为比较3种OPE算法的安全性, 做出以下实验:用该3种算法分别加密相同的明文数据.加密后的数据如图 2所示.

由图 2可知:文献[10]几乎成递增的线性变化, 文献[12]是递增的非线性变化, 安全性比文献[10]高, 这两种算法的密文都是严格保序的.文献[15]中的MOPE算法是非保序的, 不泄露密文的大小关系, 可通过模查询方式进行范围查询, 安全性更好.虽然MOPE算法的安全性更高, 但该算法由于不保序, 不适用于本文所提出的认证水印算法.文献[15]中的另一种方案保序, 算法的安全性类似于文献[12].故而, 本文采用了文献[12]中所提出的可证安全的OPE算法, 用于加密后的数据隐藏.

2 保序加密域数据库认证水印算法

本文提出的数据库认证水印算法的框架如图 3所示, 数据库所有者首先对数据库某一属性列数据进行保序加密, 然后将加密数据库传递给信息隐藏者, 信息隐藏者对加密数据进行分组和DCT变换, 选择交流系数并用哈希算法生成水印信息, 然后利用QIM算法将水印信息嵌入到直流系数中, 进行相应IDCT变换后, 得到含水印信息的加密数据库; 接收者接收到含水印信息的加密数据库后, 可通过类似于嵌入过程生成哈希值和提取的水印信息进行对比, 以验证加密数据库的完整性.对于拥有加密密钥的接收者, 可直接对加密数据库进行解密, 得到原数据库.可以看出:所提出的框架虽然在加密域中嵌入了水印信息, 但相对于明文是无损的, 好处是水印信息可以用来认证加密数据的完整性, 同时不会对明文内容造成任何影响.

2.1 数据库加密

数据库所有者按照第1节OPE系统中描述的保序概率加密算法, 对原数据库数据进行加密, 得到加密数据库, 并将加密数据库传递给信息隐藏者, 将密钥表(key_table)传递给接收者.

2.2 生成水印信息

1) 数据分组

设I为加密数据库某属性列数据, 长度为L, 对数据进行分组, 每组长度为l, 划分成了$ n = \left\lfloor {\frac{L}{l}} \right\rfloor $组数据.

2) 生成交流系数序列

对每组数据进行DCT变换, 生成的数据组表示为

$ {Y_i} = \{ {D_i}_{, 1}, {A_i}_{, 1}, {A_i}_{, 2}, \ldots , {A_i}_{, (l - 1)}\} , i \in \left[ {1, n} \right] $

(3)

其中, D_{i, 1}表示第i组数据的第1个直流系数, A_{i, j}表示第i组数据的第j个交流系数.获取每一组的第j个交流系数组成一个序列, 表示为

$ {S_j} = \{ {A_{1, j}}, {A_{2, j}}, \ldots , {A_n}_{, j}\} , j \in \left[ {1, l - 1} \right] $

(4)

3) 生成水印信息

用哈希算法处理所生成的交流系数序列S_j, 可表示为

$ {w_j} = hash({S_j}), j \in \left[ {1, l - 1} \right] $

(5)

通过hash函数, 把交流系数序列S_j转化为128比特二值序列w_j.若只处理一个交流系数序列, 则水印信息为

$ W = {w_j}, j \in \left[ {1, l - 1} \right] $

(6)

此时, 水印信息长度为128.当随机选择两个序列进行处理时, 则水印信息为

$ W = \{ {w_j}, {w_k}\} , j, k \in \left[ {1, l - 1} \right] $

(7)

此时, 水印信息长度为256.由于在每一组的直流系数中嵌入1个比特, 所以水印信息的长度W_l必须满足128≤W_l≤n, 这里, n是数据分组的数目.

2.3 水印信息嵌入

1) OPE后水印嵌入的影响

明文数据经过OPE后带来了冗余, 利用冗余, 我们希望水印在加密域的嵌入不会对明文造成影响.为此, 我们对密文数据进行逐渐增大的修改操作, 观察修改幅度对明文正确恢复的影响.表 1为明文和密文的对照表以及修改测试的结果.

结果表明:密文在一定范围内进行改变, 解密后仍可正确恢复出原明文.随着改变程度的增大, 正确恢复明文的可能性就越小.表 1中虚框内的数据, 当密文改变到一定幅度时, 明文不能全部正确恢复.不同明文对应的密文可修改的幅度不同, 测试表明:密文经过一定篡改, 解密后仍可恢复出原明文.原因是保序加密的保序特性, 使得数据带来了冗余.

2) 确定可改变的幅度

上述分析可知:密文改变幅度不超过某一阈值T时, 解密后仍可恢复出原明文.经过OPE算法^[12]加密后, 密文域R会被划分成length(D)(明文数量)个不等且不相交的子区域, 这里称为桶, 密文就是从每个桶中随机抽取一个得到.当一个密文篡改后的值在其他桶区间时, 就会错误解密成其他明文.桶划分示意图如图 4所示.

图 4中, 有相邻的桶i(区间为[c_li, c_hi])和桶(i+1)(区间为[c_l(i+1), c_h(i+1)]), 桶间距为c_l(i+1)-c_hi=1.明文m_i对应的密文c_i∈[c_li, c_hi], 明文m_i+1对应的密文c_i+1∈[c_l(i+1), c_h(i+1)].位于桶区间内的密文都可以正确解密, 密文篡改后的值落在其他桶区间时就会错误解密, 所以篡改的程度应小于1.特殊的有, 当c_i+1=c_l(i+1)时, 该密文经过篡改后可能位于区间(c_hi, c_l(i+1))内, 但仍能成功解密.由所用OPE算法的解密过程第12行~第17行可知, 两相邻桶是以点c_hi划分的, 即, 第12行的r+y=c_hi, 因此待解密值c∈(c_hi, c_l(i+1))总能被解密成桶(i+1)对应的明文.而密文c_i=c_hi经篡改后可能会错误解密, 为适应本文认证水印算法, 对加密过程第5行进行了修改, 即, 抽样空间不包括最后一个数据, 此时, c_i∈[c_li, c_hi-1], c_i+1∈[c_l(i+1), c_h(i+1)-1], 该修改不影响原加密算法安全性.那么此时阈值T=1, 可篡改范围为(-1, 1).

3) 本文认证水印算法的理论证明

本文水印嵌入算法利用了DCT变换的正交特性——改变直流系数不会影响交流系数, 当水印嵌入到直流系数时, 重新DCT分解后的交流系数不会发生任何改变.为了认证加密数据的完整性, 水印信息由交流系数经过哈希得到, 进而嵌入到直流系数中.在检测端, 类似于水印嵌入过程进行DCT变换得到交流系数和直流系数, 然后通过对比交流系数的哈希值和从直流系数中提取的水印信息来判断数据是否完整.当含水印的加密数据发生改变时, 交流系数及其哈希发生改变, 将不能匹配从直流系数中提取的水印信息, 从而判定发生篡改; 当含水印的加密数据没有改变时, 从直流系数中提取的水印信息将匹配交流系数的哈希值.为了更好地说明DCT下直流和交流系数的正交关系, 我们进行了下面的理论推导.

设f(x)为一维离散函数, x=0, 1, 2, …, $ \tilde N$₁, 可理解为第2.2节中数据分组中的一组, 先在不作修改的情况下进行DCT和IDCT, 根据文献[22]中公式(1)、公式(2), 可得公式(8)~公式(10), 对f(x)进行DCT变换得直流系数:

$F(0) = \frac{1}{{\sqrt N }}\sum\limits_{x = 0}^{N - 1} {f(x)} , u = 0$

(8)

得交流系数:

$F(u) = \sqrt {\frac{2}{N}} \sum\limits_{x = 0}^{N - 1} {f(x)\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} , u = 1, 2, ..., N - 1$

(9)

对F(u)进行IDCT变换得:

$ f(x) = \frac{1}{{\sqrt N }}F(0) + \sqrt {\frac{2}{N}} \sum\limits_{u = 1}^{N - 1} {F(u)} \cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right], x = 0, ..., N - 1 $

(10)

现在开始修改直流系数嵌入水印, 令F(0)=F(0)+C, 再进行IDCT变换有:

$ \begin{array}{l} {f^ * }(x) = \frac{1}{{\sqrt N }}(F(0) + C) + \sqrt {\frac{2}{N}} \sum\limits_{u = 1}^{N - 1} {F(u)\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} \\ = f(x) + \frac{C}{{\sqrt N }}, x = 0, 1, ..., N - 1 \end{array} $

(11)

对f^*(x)进行DCT变换, 得直流系数为

$\begin{array}{l} {F^ * }(0) = \frac{1}{{\sqrt N }}\sum\limits_{x = 0}^{N - 1} {{f^ * }(x)} = \frac{1}{{\sqrt N }}\sum\limits_{x = 0}^{N - 1} {\left( {f(x) + \frac{C}{{\sqrt N }}} \right)} \\ = \frac{1}{{\sqrt N }}\sum\limits_{x = 0}^{N - 1} {f(x) + C} = F(0) + C, u = 0 \end{array}$

(12)

可得F^*(0)=F(0)+C.可见, 水印嵌入的确改变了直流系数.可得相应的交流系数为

$ \left. \begin{array}{c} {F^ * }(u) = \sqrt {\frac{2}{N}} \sum\limits_{x = 0}^{N - 1} {{f^ * }(x)\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} \\ = \sqrt {\frac{2}{N}} \sum\limits_{x = 0}^{N - 1} {\left( {f(x) + \frac{C}{{\sqrt N }}} \right)\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} \\ = \sqrt {\frac{2}{N}} \sum\limits_{x = 0}^{N - 1} {f(x)\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} + \\ \frac{{\sqrt 2 C}}{N}\sum\limits_{x = 0}^{N - 1} {\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} \\ = F(u) + \frac{{\sqrt 2 C}}{N}\sum\limits_{x = 0}^{N - 1} {\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} , u = 1, 2, ..., N - 1 \end{array} \right\} $

(13)

设:

$g(u) = \sum\limits_{x = 0}^{N - 1} {\cos \left[ {\frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}(2x + 1)} \right]} , u = 1, ..., N - 1$

(14)

则展开有:

$g(u) = \cos \frac{{u{\rm{ \mathsf{ π} }}}}{{2N}} + \cos \frac{{3u{\rm{ \mathsf{ π} }}}}{{2N}} + ... + \cos \frac{{(2N - 1)u{\rm{ \mathsf{ π} }}}}{{2N}}$

(15)

由和差化积公式:

$\sin a - \sin b = 2\cos \frac{{a + b}}{2}\sin \frac{{a - b}}{2}$

(16)

得:

$ \begin{array}{l} \sin 2nx - \sin (2n - 2)x = 2\cos (2n - 1)x\sin x\\ \Rightarrow \cos (2n - 1)x = \frac{{\sin 2nx - \sin (2n - 2)x}}{{2\sin x}} \end{array} $

(17)

所以,

$\begin{array}{l} \cos x + \cos 3x + \cos 5x + ... + \cos (2n - 1)x = \frac{{\sin 2x}}{{2\sin x}} + \\ \frac{{\sin 4x - \sin 2x}}{{2\sin x}} + ... + \frac{{\sin 2nx - \sin (2n - 2)x}}{{2\sin x}} = \frac{{\sin 2nx}}{{2\sin x}} \end{array}$

(18)

同理可证:

$ \begin{array}{l} g(u) = \frac{{\sin \left( {2N \cdot \frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}} \right)}}{{2\sin \frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}}} = \\ \frac{{\sin u{\rm{ \mathsf{ π} }}}}{{2\sin \frac{{u{\rm{ \mathsf{ π} }}}}{{2N}}}} = 0, u = 1, ..., N - 1 \end{array} $

(19)

即, F^*(u)=F(u).

上面的理论分析表明:改变直流系数不会影响交流系数, 可通过将交流系数的哈希值嵌入到直流系数来认证加密数据的完整性.

4) 水印嵌入

用交流系数序列生成水印信息W后, 利用量化索引调制QIM算法^[23]把水印信息嵌入到加密数据库中, 这是通过嵌入到加密数据的直流系数D_{i, 1}中实现——按照水印信息, 利用不同的量化器将载体数据调制到不同的索引区间, 提取水印时则根据数据所属的索引区间来提取水印信息.

嵌入的基本过程是:根据二值水印b∈{0, 1}, 选择相应的量化器Q_Δ(·)量化载体数据x.这种量化过程表示为

$ {Q_\Delta }(x) = \left\{ {\begin{array}{*{20}{l}} {\left\lfloor {\frac{x}{\Delta }} \right\rfloor \Delta + \frac{1}{4}\Delta , {\rm{ }}b = 0}\\ {\left\lfloor {\frac{x}{\Delta }} \right\rfloor \Delta + \frac{3}{4}\Delta , {\rm{ }}b = 1} \end{array}} \right. $

(20)

其中, _Δ为量化步长, 符号⎣·⎦表示向下取整.本文方法是将水印信息W嵌入到直流系数Di, 1中.当将数据分成n组进行DCT时, 有n个直流系数, 设水印W的长度为W_l, 且W_l≤n时, 将水印比特嵌入到前W_l个直流系数中(也可以随机选取).水印嵌入函数表示为

$ D{w_i} = {Q_\mathit{\Delta }}({D_i}_{, 1}), i = [1, 2, \ldots , {W_l}] $

(21)

其中, Dw_i为嵌入水印信息的直流系数.嵌入完成后, 对每组进行IDCT变换即可得到含水印信息的加密数据库.

在量化水印算法中, 量化步长的取值是一个关键.本文中, 通过对加密数据进行DCT后, 在直流系数中嵌入交流系数的哈希值来认证加密数据的完整性, 防止非法篡改.为了确保含水印的加密数据在解密后仍为原明文数据, 利用保序概率加密的特性, 水印嵌入时量化步长的取值要满足密文可改变范围不超过(-1, 1).由公式(11)可以知道, 含水印的密文值f^*(x)与密文值f(x)的差为$ \frac{C}{{\sqrt N }}$, 其中, C为直流系数在水印嵌入后的变化值, N为分组长度l.为避免加密数据的水印嵌入失真超过(-1, 1)这一范围, 必须满足下面的表达:

$ - 1 < \frac{C}{{\sqrt l }} < 1 \Rightarrow \left| {\frac{C}{{\sqrt l }}} \right| < 1$

(22)

由公式(20)可知:水印嵌入过程中, 直流系数的最大失真为$|{C_{\max }}| = \frac{3}{4}\mathit{\Delta } $, 则有$\frac{{\frac{3}{4}\mathit{\Delta }}}{{\sqrt l }} < 1$, 进而可得量化步长Δ取值范围为

$0 < \mathit{\Delta } < \frac{{4\sqrt l }}{3}$

(23)

公式(23)表明:当量化步长一定范围内取值时, 对含水印的加密数据直接解密可得到原始明文数据.这说明了水印嵌入对数据库明文是一个无损过程, 有助于认证加密数据库的同时不影响数据库的正常使用.

2.4 数据库完整性认证

接收者接收到含水印的加密数据库, 首先要对数据库的完整性进行认证, 确保在传输过程中没有被攻击者插入、篡改、伪造等, 这可以通过对比交流系数的哈希和直流系数中嵌入的水印信息来完成.

1) 交流系数的哈希

哈希的生成与水印嵌入过程一致, 主要分成3步.

●  数据分组:对长度为L的含水印加密数据库进行分组, 每组长度为l;

●  进行DCT:对每组数据进行DCT变换, 获取每组的交流系数组成交流系数序列;

●  生成哈希:用哈希算法处理交流系数序列, 生成哈希值作为对比信息.

2) 水印信息的提取

首先, 从每一组的直流系数D_{i, 1}中提取1个水印比特, 利用量化步长Δ计算该直流系数D_{i, 1}所属的索引区间:

$ index(i) = {D_{i, 1}} - \left\lfloor {\frac{{{D_{i, 1}}}}{\mathit{\Delta }}} \right\rfloor \mathit{\Delta }, i \in [1, n] $

(24)

进而根据索引区间提取出1比特水印信息:

$ {b_i} = \left\{ {\begin{array}{*{20}{l}} {1, {\rm{ if }}{\kern 1pt} index(i) > \frac{\mathit{\Delta }}{2}}\\ {0, {\rm{ else}}} \end{array}} \right., i \in [1, n] $

(25)

重复以上过程, 直到提取出全部水印信息.

3) 完整性认证

将提取的水印信息与交流系数的哈希值作对比:若一致, 则加密数据完整; 否则, 数据已被非法篡改.导致误判的攻击主要为修改密文保留水印信息, 让水印认证通过但数据库数据实则已被篡改.要达到上面的攻击非常困难, 原因是水印算法结合了DCT变换的全局和正交特性, 通过嵌入交流系数的哈希值到直流系数中来进行认证, 这对篡改具有很强的敏感性.由于水印信息足够长(实验中为1 024比特), 漏警概率非常小.

2.5 数据库解密

接收者接收到加密数据库后, 可以根据解密过程用密钥表(key_table)进行解密, 密钥表只作查询使用, 不会增加表内容.

3 字符数据的处理及密文数据库关系运算 3.1 字符数据的处理

目前, 大多数OPE方案都是针对数值型数据而设计的, 但也有部分研究是关于字符数据的保序加密, 如Li等人^[24]在文献[10]基础上, 提出了一种针对字符数据的保序加密方法OPES+.OPES+继承了OPES的基本思想, 相对于OPES方法, OPES+只增加了一步, 即:在建模前进行类型转换, 把字符型数据转换成数值型, 英文字符转换成其ASCll值, 汉字转换成区位码值.在本算法框架中, 当遭遇字符型数据时, 在加密前应进行相应的类型转换.

3.2 密文数据库的关系运算

经过OPE的数据库并不能实现所有密文域上的数据库关系运算, 例如, SUM, AVG等运算需要解密后才能实现.但由于保持顺序的关系, 仍可以在不解密情况下进行等式和范围查询(如MAX, MIN, COUNT, GROUPBY, ORDERBY)等关系运算.图 5显示了在加密数据库下用户查询处理的过程, 查询SQL语句经过翻译层时, 对数值型数据和字符型数据分别进行OPES和OPES+, 数据库系统返回符合请求的加密数据, 在翻译层中进行解密并返回给用户.

4 实验结果及分析

本文算法使用版本为1.8.0的JVM运行在配置为3.50GHz Intel i5处理器, 4GB运行内存的Windows 7系统上, 通过JDBC方式连接到MySQL 5.6数据库, 实现数据的增、删、改、查操作.首先建立一个数据库, 并建立一张含有几个属性列的表, 实验选取图像大小为128×128的Lena灰度图像的像素值作为实验数据.

4.1 水印生成及嵌入

将128×128个像素值数据写入数据库某个数值型属性列, 进行保序加密得到加密数据.信息隐藏者对加密数据进行分组, 每组16个数据, 共1 024组, 对每组进行DCT变换后获取其后8个交流系数, 得到8个由1 024个交流系数组成的交流系数序列, 每个序列进行哈希分别得到128比特的二值信息, 然后对这些信息进行合并, 得到1 024比特的水印信息.利用QIM算法将水印信息分别嵌入到1 024个直流系数中, 根据公式(23)可知, 量化步长Δ取值范围为(0, 16/3), 这里取Δ=5, 然后将含水印的密文更新到数据库.图 6(a)显示了将1 024比特的水印信息分别嵌入到1 024个直流系数前后的差值, 范围在(-4, 4)之间; 图 6(b)显示加密数据库嵌入水印前后的差值, 水印嵌入失真刚好控制在(-1, 1)范围内, 显示了前面理论分析的正确性.

4.2 完整性认证及篡改对数据库恢复影响

在接收端, 接收者可对加密数据库进行完整性认证, 也可根据密钥直接对数据库进行解密, 得到原明文数据库.为了测试篡改对数据库恢复的影响, 表 2显示了随机选取5个含水印的密文值进行了不同程度的篡改, 实验结果如图 7所示.

图 7(a)显示在没有篡改的情况下, 含水印加密数据库完整性认证情况, 差值均为0, 可以看出, 提取出来的水印信息与生成的对比信息完全相同.图 7(b)表示在不篡改情况下, 含水印加密数据库的明文恢复情况, 差值也均为0, 即, 解密后的数据库与原数据库完全相同, 说明对加密数据进行水印嵌入不影响明文数据的恢复.图 7(c)~图 7(g)分别表示对表 2中的一个含水印密文进行不同程度的篡改操作后的认证情况.可以看出:即使是很小幅度的篡改, 直流系数中提取出来的水印信息与交流系数生成的哈希也是完全不同的, 这充分显示了本文加密域认证水印算法的有效性.图 7(h)表示在表 2所有密文进行篡改的情况下, 对含水印加密数据库进行解密后得到的明文情况, 可以看出有4处错误(除了+0.1的篡改), 这说明了认证水印对于数据库完整性保护的必要性.通过在加密域引入认证水印, 可以保护敏感数据的安全, 防止非法篡改.

4.3 不同步长选取对认证水印算法及明文恢复的影响

公式(23)表明, 量化步长Δ允许在一定范围内取值.下面通过实验分析不同步长的选取对认证水印算法及明文数据库恢复的影响.随机选取了2个不同的量化步长进行实验, 分别为Δ=1和Δ=3.实验结果如图 8所示.图 8(a)~图 8(d)分别表示了选取不同量化步长下, 含水印加密数据库完整性认证情况和明文恢复情况, 差值均为0.结果表明:在公式(23)的约束下, 量化步长Δ的选取不会影响认证水印算法以及明文数据库的恢复.

4.4 认证水印算法对明文数据库的可用性测试

下面测试本文认证水印算法对于明文数据库的可用性, 明文数据同样是128×128的像素值.为了保持明文顺序不变, 可篡改范围设为(-0.5, 0.5), 由公式(23)计算量化步长为D=2.测试结果如图 9所示.图 9(a)显示明文数据库嵌入水印前后的差值, 水印嵌入失真刚好控制在(-0.5, 0.5)范围内, 即, 水印的嵌入没有改变明文数据的顺序, 印证了公式(23)的正确性; 图 9(b)显示在没有篡改的情况下, 含水印明文数据库完整性认证情况, 可以看出, 提取出来的水印信息与生成的对比信息完全相同; 图 9(c)表示随机选取一个含水印明文, 并进行+5篡改操作后的认证情况, 可以看出, 明文数据库下本文认证算法仍然有效.

从实际意义上来说, 在明文数据库上直接嵌入水印并不明智, 因为明文数据已经遭到了破坏, 尤其对于准确性要求较高的数据库.通过保序概率加密和其引入的冗余, 本文达到了保护隐私、嵌入认证信息和进行关系运算等目的.

4.5 时间开销

下面分析在资源受限的用户端下, 本文的保序概率加密算法和认证水印算法的时间开销(计算时间开销和存储时间开销).为了测试方便, 本文实验的数据库表只含有两个属性列(自增的索引列和待加密数据列), 每一行数据代表一个元组.

图 10显示了文献[10, 12]算法(本文所用算法)在不同元组数下, 加/解密所需的时间开销.可以看出:随着处理元组数量越多, 加密和解密所需的时间开销也随之增加.可以看出:本文所用的保序概率加密算法在时间开销上比文献[10]要大一些, 但在安全性上比文献[10]要好得多.

图 11显示了一次性插入或读取不同数量的元组所需要的时间开销, 可以看出:随着插入和读取的元组数量增加, 所需要的时间开销也随之增加, 其中:插入元组时时间开销增加非常快, 而读取元组时则很缓慢.这是因为插入操作会改动原有数据库, 而查询仅仅是返回所需数据.

图 12显示了在不同元组数下, 本文认证水印算法的水印嵌入过程和水印提取过程所需要的时间开销.水印嵌入的时间由水印嵌入算法运行时间和含水印数据更新到数据库的时间组成.结合图 11可知, 水印嵌入的时间主要取决于后者所用的时间.水印提取不涉及数据库更改, 其时间开销由水印提取算法运行时间和数据读取时间组成, 随着元组数的增加, 时间开销增加缓慢.

5 结论

本文实现了一种新的保序加密域数据库认证水印算法.数据库所有者首先对数据库某一属性列的敏感数据进行加密, 以保护其内容隐私; 信息隐藏者对加密数据进行水印嵌入处理, 防止数据被非法篡改, 水印嵌入不影响用户对数据的查询和使用; 接收者可通过验证数据库的完整性来确保是否被篡改, 对于拥有加密密钥的接收者, 可直接对加密数据库进行解密, 得到原数据库.本文算法解决了以下几点问题并获得了很好的效果.

1) 通常, 明文数据库中数据冗余非常小, 进行水印保护时难以找到用于嵌入的冗余空间.经过保序加密的数据库数据不仅保护了内容隐私, 而且所有数据都可以进行水印处理, 很好地解决了数据库的保护问题;

2) 水印嵌入过程很好地结合了保序加密的特点, 对加密数据的水印嵌入相对于明文数据是无损的, 对含水印的密文数据库直接解密可得到原数据库.好处是:水印对加密数据提供了认证保护, 但不会影响数据库的使用;

3) 水印算法很好地利用了DCT的全局和正交特性, 将交流系数的哈希值嵌入直流系数, 达到了对数据库的完整性认证, 能够识别不同程度的篡改, 对加密数据的完整性提供了很好的保护.

本文算法适合于网络空间安全大背景下的云数据库服务, 很好地结合了加密和信息隐藏技术, 为数据内容的隐私保护和数据安全提供了一种有效的潜在技术手段.