基于LWE的密文域可逆信息隱藏

張敏情　　柯　彥　　蘇婷婷(武警工程大學電子技術(shù)系網(wǎng)絡(luò)與信息安全武警部隊重點實驗室　西安　710086)

?

基于LWE的密文域可逆信息隱藏

張敏情柯彥*蘇婷婷
(武警工程大學電子技術(shù)系網(wǎng)絡(luò)與信息安全武警部隊重點實驗室西安710086)

摘要：該文提出了一種基于LWE(Learning With Errors)算法的密文域可逆隱寫方案，利用LWE公鑰密碼算法對數(shù)據(jù)加密，用戶在密文中嵌入隱藏信息，對于嵌入信息后的密文，用戶使用隱寫密鑰可以有效提取隱藏信息，使用解密密鑰可以無差錯恢復(fù)出加密前數(shù)據(jù)實現(xiàn)了提取過程與解密過程的可分離。通過推導(dǎo)方案在解密與提取信息過程中出錯的概率，得到直接影響方案正確性的參數(shù)為所選噪聲的標準差，實驗獲得并驗證了標準差的合理取值區(qū)間；通過推導(dǎo)嵌入后密文的分布函數(shù)，分析密文統(tǒng)計特征的變化情況，論證了嵌入密文的隱藏信息的不可感知性。該方案是在密文域進行的可逆隱寫，與原始載體無關(guān)，適用于文本、圖片、音頻等各類載體。實驗仿真結(jié)果表明該方案不僅能夠保證可逆隱寫的可靠性與安全性，而且1 bit明文在密文域最大可負載1 bit隱藏信息。

關(guān)鍵詞：信息安全；密文域可逆隱寫；格；LWE(Learning With Errors)

1　引言

信息隱藏的多數(shù)隱寫算法在嵌入信息后給原始載體帶來永久性失真，這些失真在一些對數(shù)據(jù)認證要求較高，同時需要無失真恢復(fù)出原始載體的應(yīng)用場合是不可接受的，如云環(huán)境中的隱私數(shù)據(jù)保護、醫(yī)學圖像處理等，為了兼顧信息隱藏與原始載體的無失真恢復(fù)，可逆隱寫作為一種特殊的信息隱藏被提出，要求在提取隱藏信息后可以無差錯恢復(fù)出原始載體[1]。其中密文域可逆信息隱藏是指用于嵌入的載體是經(jīng)過加密的，嵌入信息后仍然可以無差錯解密出載體的技術(shù)。目前代表性的非密文域可逆隱寫方法包括利用差值擴展嵌入[2]，直方圖平移技術(shù)嵌入[3-5]以及利用圖像無損壓縮技術(shù)嵌入[6]等，但是由于數(shù)據(jù)加密后喪失了原有特性，上述非密文域可逆隱寫算法在密文域中適用性比較差。現(xiàn)有的密文域可逆信息隱藏方法中，文獻[7，8]是將部分載體數(shù)據(jù)進行加密并利用另一部分載體數(shù)據(jù)攜帶額外信息，但是會導(dǎo)致原始信息部分泄露；文獻[9，10]用公鑰機制加密載體數(shù)據(jù)，利用同態(tài)加密嵌入信息，這種方法會使加密數(shù)據(jù)量產(chǎn)生明顯擴張與計算復(fù)雜度的急劇增高；文獻[11]提出密文圖像中的可逆隱寫算法操作簡單且滿足可逆性要求，但是加密算法過于簡單，信息提取需要先進行圖像解密，隱寫荷載與隱寫質(zhì)量受密文圖像的限制較大；文獻[12]中提出的加密前空間預(yù)留(Reserving Room Before Encryption，RRBE)算法以及文獻[13-15]中的算法，有效荷載較大但是恢復(fù)得到的載體圖片質(zhì)量較低，解密與信息提取過程不可分離。而且現(xiàn)有的密文域可逆隱寫算法多是針對圖像載體，完全基于密文數(shù)據(jù)不受載體限制的算法還比較少。在密文域可逆隱寫的安全性即抵抗隱寫分析能力方面的研究還比較初級，一般要求保持加密圖像統(tǒng)計特性不變等[16]。

2　LWE問題與方案設(shè)計

2005年，REGEV首次提出了LWE(Learning With Errors)問題[17]。其復(fù)雜性可以歸約到格上的判定性最短向量問題gap-SVP(gap version of SVP)和最短無關(guān)向量問題SIVP(Shortest Linearly Independent Vectors Problem)[18]，即標準格中困難問題的最困難情況[19]，在對LWE算法的研究中，發(fā)現(xiàn)LWE算法加密后的數(shù)據(jù)攜帶一定的信息冗余，這些冗余可嵌入隱藏信息，由此本文設(shè)計了基于LWE算法的密文域隱寫方案，該方案在保證LWE算法困難性的基礎(chǔ)上，實現(xiàn)了信息的隱藏與有效提取，同時保證了隱寫后密文的安全性與無差錯解密。用戶首先初始化系統(tǒng)參數(shù)，生成公私鑰；使用公鑰加密后，對密文進行信息嵌入；用戶使用隱寫密鑰可從嵌入后的密文中提取隱藏信息，使用解密密鑰可對嵌入后的密文進行無差錯解密，解密與提取的過程可分離。本文方案是在密文中嵌入信息，因此不受加密前載體種類的限制，適用于文本、圖片、音頻等各類載體。加密后數(shù)據(jù)的相關(guān)性較差，分布基本符合均勻分布，因此本方案的信息嵌入量很少受密文數(shù)據(jù)內(nèi)容限制。

3　基于LWE的密文域可逆信息隱藏算法

在LWE算法中，如果沒有附加錯誤噪聲的干擾，已知公鑰中P使用高斯消元法可以在多項式時間內(nèi)求出私鑰S，但是引入錯誤噪聲后如果使用高斯消元，會將極小的錯誤放大到無法控制的級別，對于攻擊者來說，LWE算法加密數(shù)據(jù)產(chǎn)生的冗余是不能控制的。但是私鑰擁有者在解密過程中，用于判斷明文信息是0還是1的每個量化分量的取值范圍占整數(shù)域?q長度的1/2，因此對于私鑰擁有者來說數(shù)據(jù)加密后攜帶一定的可控冗余，可用來嵌入隱藏信息。

3.1參數(shù)設(shè)置與數(shù)據(jù)預(yù)處理

(3)每次加密數(shù)據(jù)長度為l∈?，為保證隱寫后密文數(shù)據(jù)的安全性，用于加密和信息隱藏的序列要滿足隨機分布的特點，因此將pl與隨機序列異或生成用于加密的序列，me與隨機序列異或生成用于嵌入的序列，若me的數(shù)據(jù)長度小于l，則對me填充0或1。

3.2 加密與信息嵌入

(1)私鑰SK：隨機選取?q上均勻分布的矩陣，解密密鑰(S，R1)，隱寫密鑰(S，R2)。

(2)公鑰PK：隨機選取?q上均勻分布的矩陣，同時選擇服從χ分布的噪聲，公鑰為。

3.3 解密與信息提取

4　算法分析與仿真實驗

4.1正確性分析

根據(jù)上述要求，分析ETa中各分量值大于■■，即方案出錯的概率如下：

圖1　整數(shù)域?q的取值分布

根據(jù)正態(tài)分布的截尾不等式[20]：設(shè)z～ N(0，1)，則

同理，

仿真實驗估計n的取值區(qū)間：n在[10，90]之間取值，測試n取不同值時能夠正確解密并提取隱藏信息的α上限值與滿足噪聲分布基本符合χ分布的α下限值。結(jié)果表明α的上下限與n基本符合線性關(guān)系，其分布與線性回歸分析結(jié)果如圖2所示。

圖2　α臨界值隨n變化情況

相關(guān)性分析得出以上樣本在該區(qū)間n∈[10，90]中，α上限值與n基本符合正相關(guān)，其相關(guān)性系數(shù)，-1表示負相關(guān)，1表示正相關(guān))，線性關(guān)系可用表示；α下限值基本保持穩(wěn)定，約為，根據(jù) α上下限得到對應(yīng)不同n值下α的合理取值區(qū)間。取對其他大量數(shù)據(jù)樣本進行實驗，結(jié)果表明α在上述區(qū)間取值，方案解密與信息提取的正確性基本達到100%。

4.2 安全性分析

當前對可逆隱寫的安全性分析主要是分析嵌入信息前后的峰值信噪比(PSNR)，但是隱寫分析者在對密文進行隱寫分析時通常不能獲得原始密文數(shù)據(jù)，而且公鑰加密算法要求明文的極小改變也將擴散到整個密文空間，所以PSNR不能有效分析密文變化是由于明文數(shù)據(jù)不同還是嵌入了額外信息，因此對于密文域隱寫的安全性，不能簡單通過隱寫前后密文數(shù)據(jù)的改變量來說明，通常要求保持密文數(shù)據(jù)嵌入前后統(tǒng)計特性不變[16]。為保證本方案能夠抵抗隱寫分析，嵌入信息后的密文分布應(yīng)該符合原始密文分布，即在?q上的均勻分布。推導(dǎo)嵌入信息后密文的分布函數(shù)如下：

方案中sm經(jīng)隨機置亂，則

綜上可知嵌入信息后密文數(shù)據(jù)的分布函數(shù)與原始密文分布函數(shù)一致，符合?q上的均勻分布。實驗測試密文在嵌入信息后的分布情況如下：n依次取值30，60，80，90，q取，l取8n，α從4.1節(jié)得到的區(qū)間取值，對多組樣本數(shù)據(jù)進行加密與隱寫，如圖3～圖8所示為原始密文與隱寫后密文分布直方圖，圖中的不同灰度代表不同組的樣本數(shù)據(jù)。

由實驗結(jié)果可以看出嵌入信息后密文的直方圖沒有出現(xiàn)明顯變化，表明嵌入信息后密文數(shù)據(jù)的分布與原始密文基本一致。

圖3　原始密文分布直方圖(n =30)

圖4　隱寫后密文分布直方圖(n =30)

圖5　原始密文分布直方圖(n =60)

圖6　隱寫后密文分布直方圖(n =60)

圖7　原始密文分布直方圖(n =90)

圖8　隱寫后密文分布直方圖(n =90)

在概率分布中，若C～ U(a，b)，則其理論期望值為(b-a)/2，通過仿真實驗得到密文數(shù)據(jù)的期望與所在?q中均勻分布下理想期望值的關(guān)系如下：n在[10，150]中取值依次增加5，q取n2+ n + 1，l取64n，每次加密l2bit數(shù)據(jù)并嵌入隱藏信息。得到圖9、圖10的圖像，圖9中的“■”和圖10中的“*”表示嵌入前后密文數(shù)據(jù)的期望值，曲線表示隨n的變化情況，兩者在誤差允許范圍內(nèi)基本一致。表明方案在嵌入信息后密文分布的期望未發(fā)生明顯變化，安全性較強。

4.3 方案執(zhí)行效率

關(guān)于方案的執(zhí)行效率，主要從信息嵌入容量與加解密速度二方面進行說明。在嵌入容量方面，文獻[22]中載荷約為0.0328 bpp；文獻[15]通過翻轉(zhuǎn)第6LSB位的方式實現(xiàn)了載荷的有效提升，約0.06 bpp；文獻[23]將LDPC編碼引入密文域可逆隱寫，將載荷提升到0.1 bpp。已有的密文域可逆隱寫算法通常是基于圖像加密，其嵌入容量受到像素空間內(nèi)容的限制較大，因此有效載荷基本不超過0.5 bpp。而本文是在LWE算法加密后數(shù)據(jù)的冗余部分嵌入信息，受加密前載體數(shù)據(jù)限制較小，根據(jù)4.2節(jié)中分析可知對于加密序列與隱藏序列，只要保證其隨機性，即可保證方案的安全性，因此1 bit明文在密文域最大可負載1 bit隱藏信息。

本文的隱寫方案是在密文域進行的可逆隱寫，與載體的種類無關(guān)。為直觀表示實驗效果，本節(jié)選擇圖像載體來介紹實驗過程。圖片Lena數(shù)據(jù)長度為512×512 Byte，嵌入隨機選取的二值序列。n在[20，300]中取值，q取，l取8n，α根據(jù)4.1節(jié)得到的區(qū)間取值，向密文中嵌入信息，一次嵌入信息長度為l/64 bit到l bit(一次加密或嵌入信息長度小于l bit時填充0或1)。圖11～圖19為n取30，α取1.1107，加密7200 Byte數(shù)據(jù)，嵌入7200 Byte信息的實驗效果。

實驗圖像Lena如圖11；將Lena圖像的前7200 Byte數(shù)據(jù)按位平面分離為二值序列作為明文，用大小240×240 bit的二值圖像表示明文數(shù)據(jù)如圖12。將明文與7200 Byte秘密信息進行隨機置亂如圖13、圖14；圖15、圖16分別是本文加密與隱寫后的數(shù)據(jù)；提取隱藏信息如圖17，通過對比可知圖17與圖14完全一致；解密結(jié)果如圖18。載體的剩余數(shù)據(jù)重復(fù)上述過程，將全部解密結(jié)果逆置亂得到所有明文的二值序列，按位填充于各像素，最終恢復(fù)得到載體圖像如圖19。

實驗結(jié)果表明本次解密與提取隱藏信息準確率為100%。n取[20，300]中其他值，分別測試1 bit明文在密文域負載0.016 bit到1 bit隱藏信息的實驗過程同上，結(jié)果顯示解密與提取隱藏信息準確率均接近于100%。選擇文本、音頻等其他載體進行實驗，結(jié)果均表明方案不僅能夠有效實現(xiàn)嵌入提取信息與無差錯解密原始載體數(shù)據(jù)，而且1 bit明文在密文域最高可負載1 bit隱藏信息。

在運行速率方面，由于本文方案只包括模q的加法運算和乘法運算，相比基于大整數(shù)分解難題和基于離散對數(shù)難題的公鑰密碼，格密碼體制的運算基本是線性運算，其速度高出很多[24]。關(guān)于LWE算法運行速率的具體理論分析，及與其他公鑰加密算法的比較可參考文獻[24，25]。因此與基于其他公鑰密碼的可逆隱寫算法相比，本文算法加解密與信息嵌入提取速率較高。

圖9　嵌入前密文期望與理想期望

圖10　嵌入后密文期望與理想期望

圖11　實驗圖片Lena

圖12　明文數(shù)據(jù)

圖13　明文置亂后數(shù)據(jù)(用于加密)

圖14　隱藏信息置亂后數(shù)據(jù)(用于嵌入)

圖15　嵌入信息前的密文數(shù)據(jù)

圖16　嵌入信息后的密文數(shù)據(jù)

圖17　提取的隱藏數(shù)據(jù)

圖18　解密得到逆置亂前數(shù)據(jù)

圖19　解密恢復(fù)得到的實驗圖像

5　結(jié)束語

本文提出了基于LWE的密文域可逆信息隱藏，通過隱寫與公鑰密碼算法的有效結(jié)合，既保持了LWE算法加密的安全可靠，同時確保了可逆隱寫的安全可靠。理論分析與仿真實驗說明了本文隱寫方案的正確性、安全性以及較高的隱寫荷載與運算速度。但是隨著n取值增大，方案的計算復(fù)雜度與密文數(shù)據(jù)的信息冗余也隨之增大，如何有效利用增大的信息冗余來提高隱藏信息的嵌入量可作為未來工作的重點。格密碼方案在媒體數(shù)據(jù)加密方面有著理論安全性高，加密效率高的優(yōu)勢，本文所實現(xiàn)的基于LWE算法的密文域可逆隱寫，可以很好地適應(yīng)于云環(huán)境下重要數(shù)據(jù)的密文域可逆信息隱藏。

參考文獻

[1]ZHANG X.Reversible data hiding in encrypted image[J].IEEE Signal Processing Letters，2011，18(4):255-258.

[2]TIAN J.Reversible data embedding using a difference expansion[J].IEEE Transactions on Circuits Systems Video Technology，2003，13(8):890-896.

[3]DRAGOI L and COLTUC D.Local-prediction-based difference expansion reversible watermarking[J].IEEE Transactions on Image Processing，2014，23(4):1779-1790.

[4]CACIULA I and COLTUC D.Improved control for low bit-rate reversible watermarking[C].IEEE International Conference on Acoustics Speech and Signal Processing，F(xiàn)lorence，Italy，2014:7425-7429.

[5]ZHANG W，HU X，LI X，et al.Recursive histogram modification:establishing equivalency between reversible data hiding and lossless data compression[J].IEEE Transactions on Image Processing，2013，2(7):2775-2785.

[6]JARALI A and RAO J.Unique LSB compression data hiding method[J].International Journal of Emerging Science and Engineering，2013，2(3):17-21.

[7]LIAN S，LIU Z，REN Z，et al.Commutative encryption and watermarking in video compression[J].IEEE Transactions on Circuits and Systems Video Technology，2007，17(6):774-778.

[8]CANCELLARO M，BATTISTI F，CARLI M，et al.A commutative digital image watermarking and encryption method in the tree structured Haar transform domain[J].Signal Processing:Image Communication，2011，26(1):1-12.

[9]KURIBAYASHI M and TANAKA H.Fingerprinting protocol for images based on additive homomorphic property[J].IEEE Transactions on Image Processing，2005，14(12):2129-2139.

[10]MEMON N and WONG P W.A buyer-seller watermarking protocol[J].IEEE Transactions on Image Processing，2001，10(4):643-649.

[11]ZHANG X.Reversible data hiding in encrypted image[J].IEEE Signal Processing Letters，2011，18(4):255-258.

[12]MA K，ZHANG W，ZHAO X，et al.Reversible data hiding in encrypted images by reserving room before encryption[J].IEEE Transactions on Information Forensics and Security，2013，8(3):553-562.

[13]YU J，ZHU G，LI X，et al.Digital Forensics and Watermarking:An Improved Algorithm for Reversible Data Hiding in Encrypted Image[M].Berlin Heidelberg，Springer-Verlag，2014:384-394.

[14]LI M，XIAO D，PENG Z，et al.A modified reversible data hiding in encrypted images using random diffusion and accurate prediction[J].ETRI Journal，2014，36(2):325-328.

[15]WU X and SUN W.High-capacity reversible data hiding in encrypted images by prediction error[J].Signal Processing，2014，104(11):387-400

[16]陳嘉勇，王超，張衛(wèi)明，等.安全的密文域圖像隱寫術(shù)[J].電子與信息學報，2012，34(7):1721-1726.doi:10.3724/SP.J.1146.2011.01240.WANG J H，WANG C，ZHANG W M et al.A secure image steganographic method in encrypted domain[J].Journal of Electronics ＆ Information Technology，2012，34(7):1721-1726.doi:10.3724/SP.J.1146.2011.01240.

[17]REGEV O.On lattices，learning with errors，random linear codes and cryptography[C].Proceedings of the 37th Annual ACM Symposium on Theory of Couputing，New York，USA，2005:84-93.

[18]余位馳.格基規(guī)約理論及其在密碼設(shè)計中的應(yīng)用[D].[博士論文]，成都:西南交通大學，2005.

[19]REGEV O.The learning with errors problem[OL].http:// www.cs.tau.ac.il/～odedr/papers/lwesurvey.pdf，2010.

[20]GORDON R D.Values of Mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument[J].The Annals of Mathematical Statistics，1941(12):364-366

[21]LYUBASHEVSKY V，PEIKERT C，and REGEV O.On ideal lattices and learning with errors over rings[C]:29th Annual International Conference on the Theory and Applications of Cryptographic Techniques.French Riviera，2010:1-23.

[22]ZHANG X.Separable reversible data hiding in encrypted image[J].IEEE Transactions on Information Forensics and Security.2012，7(2):826-832.

[23]ZHANG X，QIAN Z，F(xiàn)ENG G，et al.Efficient reversible data hiding in encrypted image[J].Journal of Visual Communication and Image Representation，2014，(25)2:322-328.

[24]AJTAI M.Generating hard instances of lattice problems[C].Complexity of Computations and Proofs，Dept.Math.，Seconda University Napoli，Caserta，Italy，2004:1-32.

[25]吳立強.基于格的密碼體制研究[D].[碩士論文]，西安:武警工程大學，2012.

張敏情：女，1967年生，教授，博士，研究方向為密碼學、信息安全、圖像信息隱藏.

柯彥：男，1991年生，碩士生，研究方向為信息安全，信息隱藏.

蘇婷婷：女，1989年生，助教，碩士，研究方向為信息安全.

Reversible Steganography in Encrypted Domain Based on LWE

ZHANG Minqing KE YanSU Tingting
(Key Laboratory of Network and Information Security Under the Armed Police Force Department of Electronic Technology，Engineering University of the Chinese Armed Police Force，Xi’an 710086，China)

Abstract:This paper proposes a novel scheme of reversible steganography in encrypted domain based on Learning With Errors(LWE).The original data is encrypted by the cryptographic algorithms with LWE.Then additional data could be embedded into the cipher text.With embedded cipher text，the additional data can be extracted by using data-hiding key，and the original data can be recovered by using encryption key，and the processes of extraction and decryption are separable.By deducing the error probability of the scheme，the standard deviation of noise sequence which directly related to the scheme’s correctness is mainly discussed，and reasonable range of the standard deviation is obtained by experiments.The probability distribution function of the embedded cipher text is deduced，that proves the embedded cipher text is not detective.The proposed scheme based on encrypted domain can apply to different kinds of media vehicle such as text，image or audio.Experimental results demonstrate that the proposed scheme can not only achieve statistical security without degrading the quality of encryption or data embedding，but realize that 1 bit original data can maximally load 1 bit additional data in encrypted domain.

Key words:Information security; Reversible steganography in encrypted domain; Lattice; LWE(Learning With Errors)

基金項目：國家自然科學基金(61379152，61272492)

*通信作者：柯彥 15114873390@163.com

收稿日期：2015-06-08；改回日期：2015-09-11；網(wǎng)絡(luò)出版：2015-11-19

DOI:10.11999/JEIT150702

中圖分類號：TP309.7

文獻標識碼：A

文章編號：1009-5896(2016)02-0354-07

Foundation Items:The National Natural Science Foundation of China(61379152，61272492)