0 引言

可逆信息隐藏是指秘密信息通过可逆的方式嵌入, 在提取隐藏信息后可以无差错恢复出原始载体的一类信息隐藏技术^[1], 其中加密域可逆信息隐藏是指用于嵌入的载体是经过加密的, 嵌入信息后要求可以无差错解密原始载体。加密域可逆信息隐藏作为加密信号处理与隐写技术的结合, 是当前云环境下隐私数据保护的研究热点之一^[2], 主要应用于加密数据的管理与认证、隐蔽通信或其他安全保护。可分离的可逆信息隐藏强调用户提取隐藏信息与可逆恢复载体数据两过程的可分离, 对于用户的隐私保护与云环境下信息安全与数据管理具有更大意义, 例如在云环境中, 为了使云服务不泄露数据隐私, 用户需要加密个人数据, 并希望云端能直接在加密域完成数据的检索或聚类分析, 需要嵌入额外的备注信息, 可分离性保证了终端或云服务器的密文分析过程直接在携密密文中, 提取信息不会解密用户的个人数据, 因此可分离的加密域可逆信息隐藏算法是当前可逆信息隐藏的研究重点之一^[3-4]。

密文域可逆信息隐藏的技术难点主要可总结为以下三点:一是可逆性, 即嵌入后密文的无失真解密及载体恢复的完全可逆; 二是秘密信息的大容量嵌入; 三是信息提取与解密过程的可分离等。分析上述难点的原因:一是当前的信息隐藏技术极大地依赖载体的编码方式、所属的媒体类型及变换域的属性, 而嵌入信息会对载体数据特征进行重新的量化与修改, 但是加密会使明文内容呈现出最大的无规律性和不确定性, 原有特征难以被提取和利用; 另一方面, 现代加密算法要求明文的极小改变也将扩散到整个密文空间, 而可逆算法的嵌入过程往往独立于加密过程, 嵌入过程中密文修改越多, 解密失真越大。当前加密域可逆信息隐藏算法存在诸多不足, 如文献[5-7]将加密与信息隐藏过程针对载体的不同部分独立进行, 将部分载体数据或变换特征进行加密, 并利用剩余部分载体数据携带额外信息, 但是会导致原始信息部分泄露, 影响载体的安全性; 为了保证载体的安全性, 文献[1]首次将加密和信息隐藏结合一体, 提出基于加密后图像的可逆隐写算法, 操作简单且满足可逆性要求, 但是加密算法过于简单, 信息提取需要先进行图像解密不可分离, 隐写荷载与载体恢复质量受密文图像的限制较大; 之后文献[8]通过改进失真函数提升了文献[1]的可逆性能。文献[9-11]以损失载体数据解密质量为代价进一步提高了文献[8]的嵌入容量, 但是嵌入量提高后的载体图片解密失真过大; 文献[12]提出在加密的JPEG比特流中嵌入可逆信息以及文献[13]提出基于邻域像素平均差值的密文域可逆信息隐藏算法, 也都存在嵌入容量提高后, 载体数据的恢复效果明显下降、可逆性较差的问题。为了提高算法的可逆性, 编码技术被引入加密域可逆信息隐藏, 如文献[14]提出利用熵编码实现密文域可逆嵌入, 能够完全保证载体无失真恢复, 但是其可逆实现主要是基于熵编码过程的可逆, 因此信息提取与解密过程的先后顺序要求固定, 不可分离。

为了有效实现算法的可分离, 文献[15-17]引入同态技术, 用公钥密码加密载体数据, 利用同态加密嵌入信息, 实现了一定的可分离, 但是同态算法会使加密数据量产生明显扩张与运算复杂度的急剧增高, 因此算法的加密嵌入效率极低, 可用性较差, 而且解密后数据存在失真; 文献[18]使用压缩感知技术实现了可分离, 在密文的特定位置填充额外的冗余数据, 运用压缩感知技术来嵌入信息, 但是解压与解密过程会造成秘密信息泄露, 影响嵌入信息的安全性; 文献[3]提出了一种密文图像中的可分离信息隐藏机制, 用矩阵运算的方法把加密的图像的最低有效位进行压缩, 腾出的空间可嵌入秘密信息, 随后数据提取和图像恢复两个操作可以单独执行, 该方案嵌入效率较高, 满足可分离的要求, 但是该方案中图像恢复和信息提取主要基于图像像素相关性, 其直接解密图像的可逆性不能充分保证。综上, 在加密域嵌入信息, 构造可分离的可逆算法是当前研究的重点与难点。可分离的方案的关键难点在于保证直接对嵌入后密文进行解密的情况下, 载体恢复过程的可逆性, 因为信息隐藏必然要修改一定的加密数据, 根据现代加密算法的扩散性要求, 这些修改往往会影响整个密文空间分布, 最终导致解密失真。但是就应用前景来看, 可分离的可逆隐写算法具有更加广阔的应用空间, 文献[4]提出了基于LWE (Learning With Errors)算法的密文域可逆隐写方案, 通过对加密过程产生的数据冗余的再编码进行信息隐藏, 1比特明文在密文域可最大负载1比特秘密信息, 并且在信息提取与解密过程中引入了不同的量化标准实现了可分离, 但是随着明文数据长度n的增大, 为保证加密安全性, LWE加密算法需要相当大的密钥长度, 通常是n²阶, 方案的计算复杂度与密文数据的扩展性也随之增大。而本文主要对文献[4]算法的执行效率与嵌入量进行改进, 引入R-LWE (Ring-Learning With Errors)算法, 在加密过程中进行十六进制数据的信息嵌入。嵌入后, 用户使用隐写密钥可以完整提取隐藏信息, 使用解密密钥可以无差错解密并恢复出加密前数据, 该算法可以实现携密密文的无差错解密与秘密信息的有效提取, 解密与提取过程可分离, 与文献[4]相比, 本文的执行效率与嵌入量得到了较大提升。由于本方案的嵌入算法是基于加密过程, 其信息嵌入位置不受密文内容影响, 且不受明文载体数据类型的限制, 可应用于文本、图片、音频数据等。

1 相关知识 1.1 (R-) LWE问题

2005年, Regev^[19]首次提出了LWE问题, 其复杂性可以归约到格上的判定性最短向量问题(gap version of SVP, gap-SVP)和最短无关向量问题(Shortest linearly Independent Vectors Problem, SIVP)^[20-21], LWE算法具有以下三方面特点, 可有效用于实现密文域可逆信息隐藏：一是可靠的理论安全性, 已知求解LWE问题的算法都运行在指数时间内, 能够抵抗量子攻击; 二是格空间是一种线性结构, LWE算法中的运算基本是线性运算, 加密速度比目前广泛使用的基于大整数分解难题和离散对数难题的公钥密码高出很多, 适用于数据量极大的多媒体环境与云环境下的数据加密; 三是LWE算法加密后的数据携带大量的信息冗余, 这些冗余对于没有私钥的攻击者来说不包含任何有用信息, 但是对于拥有私钥的用户来说该部分冗余是可控的。由此文献[4]提出了基于LWE算法的密文域可逆隐写方案, 但是随着明文数据长度n的增大, 为保证加密安全性, 基于LWE的可逆隐写方案需要相当大的密钥长度, 通常是n²阶, 并且方案的计算复杂度与密文数据的扩展性也随之增大, 实用性降低。2010年, Lyubashevsky (Lyu)等^[22]提出LWE环上的代数变种R-LWE, 并证明其困难性也可以归约到标准格中困难问题的最困难情况, 同时给出第一个真正实用且有效的可证明安全的格密码方案。本文利用R-LWE算法加密过程中的高效性, 根据Lyu算法中理论推导优化R-LWE加密过程的参数取值, 通过改进文献[4]中的嵌入方法, 提高了对冗余空间的利用率, 加密与嵌入运算的运行效率更高, 而且在加密过程中嵌入的是十六进制数据构成的隐藏信息, 有效提高了嵌入量。

1.2 R-LWE加密算法^[22]

设多项式向量维数d=ο(lb q), f(x)=xⁿ+1, q>2n², 多项式环R_q=Z _q[x]/〈f(x)〉, r∈ Z _q。

私钥SK  随机选取环多项式向量${\mathit{\boldsymbol{\hat{S}}}}$∈R_r^d, 其系数均匀取自{-r, -r+1, …, r }。

公钥PK  随机选取均匀分布的${\mathit{\boldsymbol{\hat{A}}}}$∈R_q^d, 选择噪声e, e₁∈R_q和${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$∈R_q^d, e、e₁、${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$的系数服从χ分布, 噪声的分布记为χ=${{{\mathit{\bar{\Psi }}}}_{\mathit{\alpha q}}}$, 其中${{{\mathit{\bar{\Psi }}}}_{\mathit{\alpha q}}}$={「qx」mod q|x~N (0, α²) (「qx」表示对qx取整), 公钥为(${\mathit{\boldsymbol{\hat{A}}}}$, P=${\mathit{\boldsymbol{\hat{A}}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$+e), ${\mathit{\boldsymbol{\hat{X}}}}$⊗ ${\mathit{\boldsymbol{\hat{Y}}}}$=$\sum\limits_{\mathit{i=1}}^{\mathit{m}}{{{\mathit{x}}_{\mathit{i}}}{{\mathit{y}}_{\mathit{i}}}}\in \mathit{\boldsymbol{R}}$, ${\mathit{\boldsymbol{\hat{X}}}}$、${\mathit{\boldsymbol{\hat{Y}}}}$∈R^d。

加密  将加密消息编码为环多项式m∈R_q, m=a₀+a₁x+…+a_n-1x^n-1, 选取均匀分布的多项式x∈R_q。密文为(${\mathit{\boldsymbol{\hat{u}}}}$=${\mathit{\boldsymbol{\hat{A}}}}$x+${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$, c=Px+e₁+$\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor $)∈R_q^d×R_q。

解密  得到密文对(${\mathit{\boldsymbol{\hat{u}}}}$, c)∈R_q^d×R_q, 计算ms=c-${\mathit{\boldsymbol{\hat{u}}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$∈R_q。如果多项式ms的每个系数到0的距离比到$\left\lfloor \mathit{q}/\rm{2} \right\rfloor $的距离近, 那么对应的解密比特值m′相应解密为0, 否则m′解密为1。

结合图示对上述算法的正确性进行简要说明:

$ \begin{align} & \mathit{ms}=\mathit{c}-\widehat{\mathit{\boldsymbol{u}}}\otimes \widehat{\mathit{\boldsymbol{S}}}=\mathit{\boldsymbol{P}}\mathit{x}+{{\mathit{e}}_{1}}+\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor - \\ & (\widehat{\mathit{\boldsymbol{A}}}\mathit{x}+\widehat{{{\mathit{\boldsymbol{e}}}_{2}}})\otimes \widehat{\mathit{\boldsymbol{S}}}=(\widehat{\mathit{\boldsymbol{A}}}\otimes \widehat{\mathit{\boldsymbol{S}}}+\mathit{e})\mathit{x}+ \\ & {{\mathit{e}}_{1}}+\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor -(\widehat{\mathit{A}}\mathit{x}+\widehat{{{\mathit{\boldsymbol{e}}}_{2}}})\otimes \widehat{\mathit{\boldsymbol{S}}}= \\ & \mathit{ex}+{{\mathit{e}}_{1}}-\widehat{{{\mathit{\boldsymbol{e}}}_{2}}}\otimes \widehat{\mathit{\boldsymbol{S}}}+\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor \\ \end{align} $

如图 1所示用圆周表示Z _q上所有取值, 此时ms=a₀′+a₁′x+…+a_n-1′x^n-1的每个系数a_i′∈ Z _q可以看作是分布于圆周上的点。由于引入了噪声ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$, m′对应系数a_i′在圆上的位置不确定, 通过控制噪声分布的标准差α, 可以使ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$中对应系数的波动不超过$\mathit{m}\left\lfloor \mathit{q}/\rm{4} \right\rfloor $, 若a₁取值为0, 此时a₁′对应圆上的点位于图中Ⅰ、Ⅳ部分, 即在点0(q)附近, 就是解密步骤中若多项式ms的每个系数到0的距离比到$\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor $的距离近, 那么相应为0, 否则为1。该方案安全性与正确性的详细分析可参考文献[22]。

2 加密域的可分离十六进制可逆信息隐藏算法

R-LWE算法中, 私钥拥有者在得到ms=ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗$\widehat{\mathit{\boldsymbol{S}}}+\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor $后, 用于判断明文信息是0还是1的ms的每个系数a_i′的取值范围占Z _q长度的1/2, 即取值空间为$\mathit{m}\left\lfloor \mathit{q}/\rm{2} \right\rfloor $的a_i′对应1b明文m_i, 因此对于私钥拥有者来说, 数据加密后携带大量的可控冗余, 本文主要利用该部分冗余嵌入信息。如图 2所示, 将整个噪声分布空间平均分为Ⅰ、Ⅱ、Ⅲ、Ⅳ区域, 各区域平均量化为子区域0, 1, 2, …, E, F (如图 2)。在嵌入信息过程中在同一个区域内对密文值进行修改, 使ms_i位于同一区域内的子区域i(i∈{0, 1, 2, …, F}), 表示嵌入隐藏信息为i。

首先定义函数L:

定义1  函数L:i=L(x), i∈{0, 1, 2, 3, …, F}, x∈ Z _q表示Z _q中元素x位于子区域i。

$ \mathit{L}\rm{(}\mathit{x}\rm{)}=\left\{ \begin{matrix} \left\lfloor \rm{64}\mathit{x}/\mathit{q} \right\rfloor ,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathit{x}\in [\rm{0},\mathit{q}/\rm{4}) \\ \rm{32}-\left\lfloor \rm{64}\mathit{x}/\mathit{q} \right\rfloor -\rm{1},\mathit{x}\in [\mathit{q}/\rm{4},\mathit{q}/\rm{2}) \\ \left\lfloor \rm{64}\mathit{x}/\mathit{q} \right\rfloor -\rm{32},\ \ \ \mathit{x}\in [\mathit{q}/\rm{4},\rm{3}\mathit{q}/\rm{4}) \\ \rm{64}-\left\lfloor \rm{64}\mathit{x}/\mathit{q} \right\rfloor -\rm{1},\mathit{x}\in [\rm{3}\mathit{q}/\rm{4},\mathit{q}) \\ \end{matrix} \right. $

(1)

下面详细介绍算法过程。

2.1 参数设置与数据预处理

1)选取一个安全参数k >1, 模数记为q, 构造多项式环R_q=Z _q[x]/〈f(x)〉, 生成多项式f(x)=xⁿ+1, n=2^k, 所有运算在多项式环R_q上进行。多项式向量维数d=ο(lb q), 噪声的分布为χ=${{{\mathit{\bar{\Psi }}}}_{\mathit{\alpha q}}}$, 其中α=ο($\rm{1/}\sqrt{\mathit{d}}\rm{1b}\mathit{n}$)。

2)设明文信息为pl∈{0, 1}, 隐藏信息为me∈{0, 1}。

3)pl与随机序列r₁∈{0, 1}异或生成用于加密的序列se₁∈{0, 1}^l, me∈{0, 1}与随机序列r₂∈{0, 1}异或得到序列se₂:

$ \mathit{s}{{\mathit{e}}_{\rm{1}}}={{\mathit{r}}_{\rm{1}}}\oplus \mathit{pl} $

(2)

$ \mathit{s}{{\mathit{e}}_{\rm{2}}}={{\mathit{r}}_{\rm{2}}}\oplus \mathit{me} $

(3)

将se₁编码为系数为二进制数的多项式m用于加密, 将se₂编码为系数为十六进制数的多项式sm用于嵌入, sm=sm₀+sm₁x+sm₂x²+…sm_n-1x^n-1, sm_i∈{0, 1, 2, …, F}。

2.2 加密与信息嵌入

1)私钥SK:随机选取环多项式向量${\mathit{\boldsymbol{\hat{S}}}}$∈R_q^d, 其系数均匀取自{-r, -r+1, …, r}, 解密密钥(${\mathit{\boldsymbol{\hat{S}}}}$, r₁), 隐写密钥(${\mathit{\boldsymbol{\hat{S}}}}$, r₂)。

2)公钥PK:随机选取环多项式向量${\mathit{\boldsymbol{\hat{A}}}}$∈R_q^d, 同时选择噪声e∈R_q, e中各系数服从χ分布的, 公钥为(${\mathit{\boldsymbol{\hat{A}}}}$, P=${\mathit{\boldsymbol{\hat{A}}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$+e)。

3)加密:选取随机分布的多项式x∈R_q, 选择噪声e₁∈R_q和${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$∈R_q^m, e₁和${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$的系数服从χ分布, 密文:($\widehat{\mathit{\boldsymbol{u}}}$=${\mathit{\boldsymbol{\hat{A}}}}$x+${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$, c=Px+e₁+m$\left\lfloor \mathit{q}/\rm{2} \right\rfloor $)。

4)信息嵌入:设量化向量h=c-$\widehat{\mathit{\boldsymbol{u}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$, 其中h=h₀+h₁x+…+h_n-1x^n-1, 设嵌入后密文($\widehat{\mathit{\boldsymbol{u}}}$, cs), cs=cs₀+cs₁x+…+cs_n-1x^n-1, 则:

$ \mathit{c}{{\mathit{s}}_{\mathit{i}}}={{\mathit{c}}_{\mathit{i}}}+{{\mathit{\beta }}_{\mathit{i}}}\cdot {{\mathit{b}}_{\mathit{i}}}\cdot \left\lfloor \mathit{q}\rm{/64} \right\rfloor $

(4)

其中:

$ {{\mathit{\beta }}_{\mathit{i}}}=\left\{ \begin{matrix} \rm{1},{{\mathit{h}}_{\mathit{i}}}\in (\rm{0},\mathit{q}/\rm{4})\bigcup (\mathit{q}/\rm{2},\rm{3}\mathit{q}/\rm{4}) \\ -\rm{1},{{\mathit{h}}_{\mathit{i}}}\in (\mathit{q}/\rm{4},\mathit{q}/\rm{2})\bigcup (\rm{3}\mathit{q}/\rm{4},\mathit{q}) \\ \end{matrix} \right. $

(5)

β_i∈{-1, 1}影响嵌入过程中密文改变的正负;

$ {{\mathit{b}}_{i}}=\mathit{s}{{\mathit{m}}_{\mathit{i}}}-\mathit{L}({{\mathit{h}}_{\mathit{i}}}) $

(6)

b_i∈{-F, …, -2, -1, 0, 1, 2, …, F}, 其绝对值表示密文改变量。

2.3 解密与信息提取

解密  私钥为(${\mathit{\boldsymbol{\hat{S}}}}$, r₁), 密文为($\widehat{\mathit{\boldsymbol{u}}}$, cs), 计算h ′=cs-$\widehat{\mathit{\boldsymbol{u}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$=h₀′+h₁′x+…+h_n-1′x^n-1。解密多项式m′：

$ {{\mathit{m}}_{i}}'=\left\{ \begin{align} & \rm{1},\ \ \ \ {{\mathit{h}}_{\mathit{i}}}'\in \left( \rm{0},\mathit{q}/\rm{4} \right)\cup \left[ \rm{3}\mathit{q}\rm{/4,}\mathit{q} \right) \\ & -\rm{1,}\ \ \ {{\mathit{h}}_{\mathit{i}}}'\in \left[ \mathit{q}/\rm{4,3}\mathit{q}\rm{/4} \right) \\ \end{align} \right. $

(7)

得到序列se₁′=[m₀′, m₁′, …, m_n-1′], 最后明文pl′为:

$ \mathit{pl}'={{\mathit{r}}_{\rm{1}}}\oplus \mathit{s}{{\mathit{e}}_{\rm{1}}}' $

(8)

信息提取  密钥为(${\mathit{\boldsymbol{\hat{S}}}}$, r₂), 密文为($\widehat{\mathit{\boldsymbol{u}}}$, cs), 计算h ′=cs-$\widehat{\mathit{\boldsymbol{u}}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$=h₀′+h₁′x+…+h_n-1′x^n-1, 则得到提取信息sm′, 其各项为:

$ \mathit{s}{{\mathit{m}}_{\mathit{i}}}'=\mathit{L}({{\mathit{E}}_{\mathit{i}}}) $

(9)

最后将sm′编码为二进制序列se₂′, 则可得到隐藏信息为me′:

$ \mathit{me}'={{\mathit{r}}_{\rm{2}}}\oplus \mathit{s}{{\mathit{e}}_{\rm{2}}}' $

(10)

综上, 概括算法的流程框架如下。

1)加密与数据嵌入。

步骤1  初始化系统参数, 对明文与秘密信息进行预处理;

步骤2  产生公私钥, 私钥分为解密密钥与隐藏密钥;

步骤3  使用公钥加密得到密文数据;

步骤4  在密文数据中嵌入秘密信息, 得到携密密文。

2)解密与信息提取。

解密  使用解密密钥对携密密文直接进行解密, 得到明文数据。

信息提取  使用隐写密钥对携密密文提取信息, 得到嵌入数据。

解密与提取过程可分离。

3 理论分析与仿真实验 3.1 理论分析

本节通过理论分析对影响方案的正确性的相关参数条件进行说明, 方案的正确性主要包括嵌入后密文的正确解密与嵌入信息的正确提取两方面, 是加密域可逆隐写的基本要求, 也是当前算法设计与实现的难点。本文方案的正确性分析如下:

如图 2所示圆周上的点表示整数域Z _q的取值分布, 根据2.2节的方案设计, 通过α控制ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$ ⊗${\mathit{\boldsymbol{\hat{S}}}}$的波动范围在(0, q/4)∪[3q/4, q), 在加密的过程中:当m_i为0时, 对应h_i位于图中的区域Ⅰ、Ⅳ, 当m_i为1时, 对应h_i位于图中的区域Ⅱ、Ⅲ; 在信息嵌入的过程中:当携带隐藏信息sm_i为i时(i∈{0, 1, 2, …, F}), 密文数据向正(负)方向偏移q/64的整数倍, 使解密或提取信息过程中的ms_i′位于相同区域的子区域i中, 加密与嵌入过程完成。

完成上述加密与嵌入过程后, 用户即可实现可分离的解密得到原始明文或提取隐藏信息:

当拥有解密密钥(${\mathit{\boldsymbol{\hat{S}}}}$, r₁)时, 将密文代入解密算法步骤, 计算得到ms_i, 判断其所位于的区域:

h_i∈(0, q/4)∪[3q/4, q)时, 对应区域为Ⅰ、Ⅳ, 此时解密m_i′=0;

h_i∈[q/4, 3q/4)时, 对应区域为Ⅱ、Ⅲ, 此时解密m_i′=1。

当拥有解密密钥(${\mathit{\boldsymbol{\hat{S}}}}$, r₂)时, 根据解密算法步骤, 计算h_i, 判断所在子区域, 根据式(9), 函数L可对应输出此时h_i的子区域编号i(i=0, 1, 2, …, F), 即为提取信息sm′。

综上, 正确解密与信息提取的充要条件是保证加密过程中ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$的波动范围在(0, q/4)∪[3q/4, q), 即噪声之和的多项式E=ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$的各系数E_i的值不大于$\left\lfloor \mathit{q}/\rm{4} \right\rfloor $。

分析E_i值大于$\left\lfloor \mathit{q}/\rm{4} \right\rfloor $, 即方案出错的概率如下:

在E=ex+e₁-${{{\mathit{\boldsymbol{\hat{e}}}}}_{2}}$⊗${\mathit{\boldsymbol{\hat{S}}}}$各部分噪声采样来自χ分布, 由文献[22]可知E_i可认为符合期望为0的高斯分布, 因此可设E_i~N(0, δ), 且α越小, δ越小。正态分布的截尾不等式如下所示:设z~N (0, 1), 则

$ \begin{align} & \rm{Pr}(|\mathit{z}|>\mathit{x})=\rm{2}\int_{x}^{+\infty }{\frac{\rm{1}}{\sqrt{\rm{2}\pi }}}\exp (-\frac{\rm{1}}{\rm{2}}{{\mathit{z}}^{2}})d\mathit{z} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \le \frac{\rm{1}}{\mathit{x}}\sqrt{\frac{\rm{2}}{\rm{ }\!\!\pi\!\!\rm{ }}}\exp (-\frac{\rm{1}}{\rm{2}}{{\mathit{z}}^{\rm{2}}});\mathit{x}>\rm{0} \\ \end{align} $

(11)

由式(11)可知, 当方差α足够小时, δ越小, 噪声产生的波动E_i较小, 方案出错的概率接近于0。在LWE算法中α通常取o($\rm{1/}\sqrt{\mathit{m}}\rm{1b}\mathit{n}$)^[21]。另一方面LWE/R-LWE问题求解的困难性依赖于噪声的存在, 如果α太小, 噪声分布在均值0附近偏差很小, 噪声波动区间的大小影响方案的安全性。由于R-LWE算法加密后的数据密文扩展较大, 为了保证噪声的波动区间, R-LWE算法中通常要求αq>$\sqrt{\mathit{n}}\rm{1b}\mathit{n}$^[21], 因此本文算法中在保证密文合理波动存在的前提下, 将划分密文域空间中子区域的量化步长取为于$\left\lfloor \mathit{q}/\rm{64} \right\rfloor $, 对应可嵌入十六进制数据。原算法^[22]中通过理论分析了R-LWE算法的安全性与正确性, 但是相关参数的取值未具体说明, 本文在理论分析的基础上主要通过对大量数据进行加密与隐写测试, 进一步确定噪声分布标准差的合理取值。

实验均采用Matlab 2010b软件。为保证加密效率与计算机运行速度, k在5~14取值, 且q≡1(mod 2n); 为保证环上多项式不可逆, n取2^k, 实验测试一次加密2⁵~2¹⁴位明文时α的取值区间。为避免出现循环依赖问题^[22], 须满足q>2n²。综上, 结合实验效果与运行效率, 本文取q=64n³+1, 对大量数据样本进行加密与隐写, 测试k取不同值, 能够正确解密并提取隐藏信息的α上限值, 结果如表 1所示。

下面通过仿真实验说明方案实现提取信息与解密恢复明文可分离的效果。

3.2 实验结果

实验首先选取标准图像Lena如图 3进行仿真, 为直观反映实验效果, 本文实验过程以加密Lena图像中的2¹²b数据, 嵌入2¹⁶ b信息为例进行说明, 实验中参数设置:k=8, n=2⁸, q=64n³+1, α=3.121 2×10^-5。

如图 4所示为实验过程:将标准图像Lena按位平面分离, 其位分离图用二值图像表示如图 4(a); 将明文分为64×64的互不重叠的块; 明文中选择其中的第1块进行加密与嵌入实验, 结果如图 4(b)~4(i)所示:将所选块为64×64的二值图像如图 4(b); 将明文随机置乱如图 4(c); 选取十六进制数组成的随机序列作为隐藏信息如图 4(d); 加密第一块中的数据如图 4(e); 在加密后数据中嵌入随机选择的十六进制数据如图 4(f)。使用提取算法提取隐藏信息如图 4(g), 通过图像作差进行对比, 可知提取信息与嵌入信息完全一致如图 4(h); 直接对嵌入后的密文进行解密, 结果如图 4(i)。其中对携密密文图 4(f)进行提取信息与解密的两过程相互没有影响, 实现了可分离。由于算法是基于加密过程进行数据嵌入, 其嵌入位置不受密文内容影响, 故1b明文在加密域最大可负载lb 16 b隐藏信息。最后将图像Lena的剩余块中的数据重复上述过程(当明文数据长度小于多项式长度时, 填充0或1), 将全部解密结果按位填充于各像素, 最终恢复得到载体图像如图 5。解密与信息提取的正确性基本达到100%。

可逆隐写算法的评价标准中峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)用来评价恢复后载体与原始载体信息相比的失真情况。对于大小M×N的256级灰度图像PSNR的定义如下:

$ \mathit{PSNR}=\rm{10}\times \lg (\frac{\rm{255}\times \rm{255}}{\mathit{MSN}}) $

(12)

其中:MSE表示恢复图像像素矩阵I ′与原始图像像素矩阵I的均方误差(Mean Squared Error, MSE), 定义如下:

$ \mathit{MSE}=\frac{\sum\limits_{\mathit{i}=0}^{\mathit{M}-\rm{1}}{\sum\limits_{\mathit{j}=0}^{\mathit{N}-\rm{1}}{{{({{\mathit{I}}_{\mathit{i,j}}}-{{\mathit{I}}_{\mathit{i,j}}}')}^{\rm{2}}}}}}{\mathit{M}\rm{ }\!\!\times\!\!\rm{ }\mathit{N}} $

(13)

PSNR的单位为dB, PSNR值越大, 表示图像失真越小。通常, 当PSNR值大于35dB时, 人眼视觉就无法感知图像的失真。

继续对标准图像库中图像Lena、Man、Lake、Baboon进行实验并计算直接解密图像与原始图像间的PSNR, 与经典的加密域可逆隐写算法^[1]及可分离算法^[3]进行比较如下:图 6为文献[1, 3]算法可逆恢复后载体的PSNR, 可见嵌入的过程中引入了失真, 只是将失真程度控制在人眼无法感知的程度(PSNR>36dB), 且嵌入量越大, 失真越大。

本文直接解密恢复的图像结果代入式(12)、(13)得到PSNR值均为“∞”, 说明可完全保证恢复过程的可逆性。在嵌入容量方面, 由于嵌入的信息是十六进制数, 与文献[4]相比, 本文在嵌入量上提升了4倍, 1比特明文在加密域可负荷4比特隐藏信息。

本算法是在R-LWE算法的加密过程中嵌入信息, 不受加密前载体种类的限制, 适用于文本、图片、音频等各类载体。通过对文本、音频等数字载体进行实验测试, 结果表明本文算法可有效在各类载体中嵌入秘密信息, 1比特明文在加密域可最大负载4比特秘密信息, 信息提取与原始载体的解密恢复过程可分离, 而且提取信息与解密的正确率基本达到100%。

4 结语

本文提出加密域的可分离信息隐藏算法, 通过信息隐藏技术与R-LWE加密算法的结合, 保证了加解密的安全可靠与秘密信息的有效嵌入提取。通过理论推导与仿真实验论证了方案的可分离性与正确性。实验结果表明, 本文方案的载体恢复可实现完全可逆, 嵌入容量单位比特明文在密文域可嵌入4比特秘密信息。对于加密过程中产生的密文扩展, 未来工作的重点是优化嵌入编码方式, 利用密文扩展来进一步提高嵌入容量。