基于R-LWE的密文域多比特可逆信息隱藏算法

柯 彥 張敏情 蘇婷婷

(網(wǎng)絡(luò)與信息安全武警部隊重點實驗室(武警工程大學(xué)) 西安 710086) (武警工程大學(xué)電子技術(shù)系 西安 710086) (15114873390@163.com)

?

基于R-LWE的密文域多比特可逆信息隱藏算法

柯 彥 張敏情 蘇婷婷

(網(wǎng)絡(luò)與信息安全武警部隊重點實驗室(武警工程大學(xué)) 西安 710086) (武警工程大學(xué)電子技術(shù)系 西安 710086) (15114873390@163.com)

密文域可逆信息隱藏是一種以密文為載體進行信息嵌入與提取，同時能夠?qū)η度胄畔⒑蟮拿芪倪M行無失真解密并恢復(fù)出原始明文的信息隱藏技術(shù)，具有隱私保護與信息隱藏雙重功能，在密文域數(shù)據(jù)處理與管理中具有較好的應(yīng)用前景.因此，提出了一種基于R-LWE(ring-learning with errors)的密文域多比特可逆信息隱藏方案.首先使用R-LWE算法對載體明文進行快速高強度加密，然后通過對單位比特明文在密文空間映射區(qū)域的重量化以及對應(yīng)密文的再編碼，實現(xiàn)了在密文中嵌入多比特隱藏信息；嵌入信息時，根據(jù)加密過程中的數(shù)據(jù)分布特征來進行嵌入編碼，保證了加解密與信息提取的魯棒性；解密與提取信息時，先計算量化系數(shù)，而后采用不同的量化標(biāo)準(zhǔn)分別進行解密或信息提取，實現(xiàn)了解密與提取過程的可分離.分析方案的正確性時，首先推導(dǎo)方案出錯的概率，說明了算法中引入的噪聲的標(biāo)準(zhǔn)差對方案正確性的影響，然后結(jié)合理論分析與實驗得出了保證方案正確性的噪聲標(biāo)準(zhǔn)差的取值區(qū)間；通過推導(dǎo)嵌入后密文的分布函數(shù)，分析密文統(tǒng)計特征的變化，論證了密文中嵌入隱藏信息的不可感知性.實驗結(jié)果表明：該文方案不僅能夠?qū)崿F(xiàn)嵌入后密文的無差錯解密與秘密信息的可靠提取，并且單位比特明文在密文域能夠負載多比特隱藏信息，密文嵌入率最高可達到0.2353 bpb.

信息安全；可逆信息隱藏；密文域；多比特嵌入；環(huán)上帶誤差的學(xué)習(xí)

傳統(tǒng)的信息隱藏算法在嵌入過程中會給原始載體帶來永久性失真，不能適用于嵌入信息后需要無失真恢復(fù)出原始載體的應(yīng)用場合，如云環(huán)境下隱私數(shù)據(jù)標(biāo)注、遠程醫(yī)學(xué)診斷、司法取證等對載體失真較為敏感的應(yīng)用領(lǐng)域，因此可逆信息隱藏技術(shù)被提出，要求嵌入信息后可以無差錯恢復(fù)出原始載體[1].隨著網(wǎng)絡(luò)的普及尤其是云服務(wù)的興起，隱私保護與信息安全需求日益增強，數(shù)據(jù)往往以密文的形式進行傳輸與存儲，因此面向密文載體的可逆信息隱藏技術(shù)受到廣泛的關(guān)注.密文域可逆信息隱藏是指用于信息嵌入的載體是經(jīng)過加密的，嵌入后仍然可以無差錯解密并恢復(fù)出原始載體的一種信息隱藏技術(shù)，主要用于加密數(shù)據(jù)的管理與認證、加密域隱蔽通信[2]或其他安全保護.例如，遠程醫(yī)學(xué)診斷中為了保護患者隱私，通常加密傳輸或存儲醫(yī)學(xué)圖像，同時為了對密文圖像進行歸類與管理，需要以可逆方式嵌入患者的私人信息甚至病歷、診斷結(jié)果、病理圖等隱私數(shù)據(jù)；云環(huán)境下，用戶需要先對數(shù)據(jù)進行加密以確保云服務(wù)不泄露數(shù)據(jù)隱私，同時為了使云端或用戶能夠直接在密文域完成數(shù)據(jù)的檢索或聚類，需要可逆嵌入一些額外的備注信息而不能影響用戶解密原始數(shù)據(jù)；另外，在密文傳輸過程中，通過以可逆方式嵌入校驗碼或Hash值，可以實現(xiàn)不解密情況下數(shù)據(jù)的完整性與正確性檢驗等.綜上，密文域可逆信息隱藏對于信息安全與隱私保護可以起到雙重保險的作用，是當(dāng)前密文域數(shù)據(jù)處理與信息隱藏技術(shù)的研究重點之一[3-4].

當(dāng)前密文域可逆信息隱藏的技術(shù)難點主要在于實現(xiàn)秘密信息的大容量嵌入、載體數(shù)據(jù)恢復(fù)得完全可逆、信息提取與解密過程的可分離以及嵌入信息的不可檢測性等方面.針對上述難點，該領(lǐng)域研究者們提出了多種解決方案，主要可分為部分加密和全局加密2類.部分加密算法是在加密前保留載體部分特征用于數(shù)據(jù)嵌入，而將載體剩余部分進行加密，如文獻[5]是在壓縮過程中利用部分DCT系數(shù)攜帶額外信息而將其余系數(shù)加密；文獻[6]提出在H.264AVC格式視頻的壓縮過程中加密部分特征，而剩余部分特征用于數(shù)據(jù)嵌入；文獻[7]利用樹型哈爾變換域中的部分系數(shù)的位層實現(xiàn)信息嵌入.部分加密算法能夠較好地保證載體恢復(fù)的可逆性與秘密信息的嵌入率，但是保留載體部分原始特征容易導(dǎo)致原始信息泄露，威脅載體信息安全，因此當(dāng)前密文域可逆信息隱藏技術(shù)研究的重點在于全局加密類算法.

全局加密算法是對載體信息全部加密，數(shù)據(jù)嵌入過程完全在密文域上進行，不會造成原始信息泄露.全局加密算法中的一類算法是通過引入密文域信息處理技術(shù)實現(xiàn)密文域嵌入，如同態(tài)技術(shù)[8-9]與熵編碼[10]等.文獻[8-9]用公鑰密碼加密載體數(shù)據(jù)，利用同態(tài)加密嵌入信息，能夠在密文域直接進行操作實現(xiàn)嵌入，具有良好的可逆性；文獻[2]利用雙層嵌入的方法在明文數(shù)據(jù)中嵌入信息，并設(shè)計了一種修正的全同態(tài)加密算法對載密數(shù)據(jù)進行加密，最后在密文域上提取隱藏信息，該算法能夠可分離地進行載密數(shù)據(jù)解密與隱藏信息提取，并且在密文域同態(tài)嵌入的基礎(chǔ)上進一步引入密碼學(xué)中可證明安全理論論證了所提方案的安全性.但是上述文獻中引入全同態(tài)加密后造成算法的計算復(fù)雜度過大，執(zhí)行效率與秘密信息嵌入率較低.文獻[10]引入熵編碼技術(shù)在密文編碼過程中嵌入信息，能夠達到完全可逆，執(zhí)行效率與嵌入率有了很大提高，但是由于算法的可逆性是基于解碼過程的可逆性，因此解密與信息提取過程不可分離.而當(dāng)前全局加密的另一類重要算法主要是基于圖像處理與加密、密文數(shù)據(jù)壓縮等技術(shù)來實現(xiàn)密文域嵌入，該類算法計算復(fù)雜度較小、執(zhí)行效率較高：文獻[1]首次將圖像加密技術(shù)和信息隱藏結(jié)合一體，提出密文圖像中的可逆信息隱藏算法，操作簡單且滿足一定的可逆性要求，但是信息提取需要先進行圖像解密，隱寫荷載與可逆恢復(fù)質(zhì)量受加密算法與圖像內(nèi)容限制較大；在此基礎(chǔ)上，文獻[11]通過改進失真函數(shù)提升了這種方案的可逆性能，而文獻[12-13]通過改進嵌入技術(shù)進一步提高了嵌入容量，但是嵌入量提高后的載體圖片解密失真會有所增大；之后文獻[14]提出在加密的JPEG比特流中嵌入可逆信息以及文獻[15]提出基于鄰域像素平均差值的密文域可逆信息隱藏算法對文獻[1]進行改進，但仍然存在嵌入容量與可逆性相互制約的問題；文獻[16]引入隨機擴散的方法有效利用了文獻[1]中的像素空域關(guān)聯(lián)性，通過設(shè)計精確預(yù)測的算法在降低解密差錯的同時提高了嵌入容量.但是上述算法[1,11-16]均不能實現(xiàn)載體解密恢復(fù)與信息提取過程的可分離，為此，文獻[17]提出可分離的加密圖像隱藏算法，利用矩陣運算的方法把加密的圖像的 LSB 進行壓縮騰出空間嵌入信息，在接收方分3種情況：使用隱藏密鑰可以提取嵌入數(shù)據(jù)、使用解密密鑰可以對攜秘密文圖像直接解密，2個操作可以單獨執(zhí)行；同時使用隱隱藏密鑰與解密密鑰可基本實現(xiàn)載體的完全恢復(fù).文獻[17]的方案操作簡單，適用于更多的應(yīng)用場景，但是圖像載體恢復(fù)是基于像素間相關(guān)性，因此使用解密密鑰直接對攜秘密文解密時，由于可參考的像素點有限，造成解密存在一定失真；文獻[18]使用壓縮傳感的方法實現(xiàn)了解密與信息提取可分離，將加密后圖像與隱藏信息2部分數(shù)據(jù)壓縮成原始密文圖片的大小，壓縮過程即完成了密文域額外信息的嵌入，解密與信息提取過程可分別在解壓后獨立進行，能夠較好地保證載體恢復(fù)的可逆性，但是嵌入量受密文內(nèi)容與壓縮方式限制，而且解密恢復(fù)與提取過程都依賴于無損解壓，因此解密過程會導(dǎo)致隱藏信息暴露.此外，現(xiàn)有的密文域可逆信息隱藏算法在安全性，即保證密文嵌入前后統(tǒng)計特征不變與嵌入數(shù)據(jù)的不可感知性方面的相關(guān)研究還比較少.

通過上述分析可知，構(gòu)造完全可逆、高嵌入率且解密與信息提取可分離的密文域可逆嵌入算法是該領(lǐng)域研究與技術(shù)應(yīng)用的重點.而當(dāng)前全局加密類算法使用的加密系統(tǒng)多數(shù)為對稱密碼系統(tǒng)，與公鑰密碼系統(tǒng)相比，對稱密碼密鑰生成與管理難度大，適用的加密場景有限，為此文獻[19]提出基于格上的LWE(learning with errors)公鑰加密的可逆隱寫方案，在可逆性、可分離性、執(zhí)行效率與隱寫安全性方面都有著較好的保證.本文主要針對文獻[19]進行嵌入過程編碼算法的優(yōu)化，以及執(zhí)行效率與嵌入量上的改進.

在文獻[19]中，首先對LWE算法加密過程中引入噪聲的標(biāo)準(zhǔn)差進行約束來產(chǎn)生可控冗余，然后對密文進行再編碼實現(xiàn)在密文的可控冗余中嵌入額外數(shù)據(jù)，1 b明文在密文域可最大負載1 b秘密信息，解密恢復(fù)與信息提取的正確性基本達到了100%，并且在信息提取與解密過程中使用不同的量化標(biāo)準(zhǔn)實現(xiàn)了解密與信息提取的可分離.但是當(dāng)明文長度增加時，為保證加密安全性，密鑰長度也相應(yīng)增長，造成密文擴展率較高.設(shè)格空間向量長度為m，文獻[19]中一次可加密與嵌入的數(shù)據(jù)長度為O(m)，安全密鑰長度為O(m2)，1 b明文對應(yīng)密文域空間為O(m2)，因此文獻[19]的加密與嵌入方案依然存在大量的計算冗余與空間冗余可用于提高信息嵌入效率.由此，本文基于文獻[19]的算法進行3方面的改進：

1) 對加密與嵌入的執(zhí)行效率進行改進，引入環(huán)上更高效的環(huán)上帶誤差的學(xué)習(xí)(ring-learning with errors, R-LWE)[20]加密算法，設(shè)環(huán)上多項式向量維數(shù)為m，多項式長度為n，在與文獻[19]相同時間復(fù)雜度與加密強度的情況下本文方案一次可加密與嵌入的數(shù)據(jù)長度為O(mn)，由于R-LWE算法[20]中沒有詳細給出R-LWE加密系統(tǒng)的參數(shù)取值，本文結(jié)合理論分析與實驗仿真對方案中加密與嵌入過程的參數(shù)取值進行了詳細地討論說明；

2) 文獻[19]中要求加密過程對噪聲標(biāo)準(zhǔn)差進行約束來控制噪聲波動規(guī)模以保證方案的正確性，本文通過改進嵌入編碼方式，充分利用噪聲的原始分布進行重新編碼來嵌入額外信息而不需要對噪聲分布標(biāo)準(zhǔn)差進行額外的約束，有效保證了原始加密的魯棒性與方案的正確性；

3) 通過對密文域進行重量化，并劃分子區(qū)域，可對應(yīng)嵌入多進制數(shù)據(jù)構(gòu)成的秘密信息，當(dāng)秘密信息為B進制數(shù)據(jù)時，1 b明文在密文域最大可負載logBb額外信息.實驗結(jié)果表明與文獻[19]相比，本文在運行效率提高、計算復(fù)雜度不變的前提下，信息嵌入量提升到1 b明文，在密文域可負載4～8 b秘密信息.

最后，本文在安全性分析中通過理論分析與仿真實驗結(jié)果說明了方案嵌入后的密文服從均勻分布，符合傳統(tǒng)加密數(shù)據(jù)的統(tǒng)計分布特性.

1 相關(guān)技術(shù)

1.1 (R)LWE問題與分析

2005年，Regev首次提出了LWE問題[21].其復(fù)雜性可以歸約到格上的判定性最短向量問題(gap version of shortest vectors problem, GAP-SVP)和最短無關(guān)向量問題(shortest linearly independent vectors problem, SIVP)[22]，上述2種格中困難問題已經(jīng)被證明是NP困難的，而LWE問題可以看作隨機線性碼的解碼問題，或者格上的有限距離解碼問題(bounded distance decoding problem, BDD)，其困難性可以歸約到標(biāo)準(zhǔn)格中困難問題的最困難情況[23].而且已知求解LWE問題的算法都運行在指數(shù)時間內(nèi)，能夠抵抗量子攻擊，因此LWE問題具有可靠的理論安全性.此外，各類媒體的數(shù)據(jù)量極大，而格是一種線性結(jié)構(gòu)，LWE算法中的運算基本都是線性運算，加密速度比目前廣泛使用的基于大整數(shù)分解難題和離散對數(shù)難題的公鑰密碼高出很多，可以很好地適用于媒體數(shù)據(jù)量極大的云環(huán)境.但是隨著格空間向量長度m的增大，為保證加密安全性， LWE算法需要相當(dāng)大的密鑰長度，通常是m2階，并且方案密文數(shù)據(jù)的擴展與計算復(fù)雜度也隨之增大，實用性降低.2007年，Kawachi等人針對Regev等人的LWE算法，提出格上的多比特加密算法[24]，通過約束[21]等算法中噪聲分布的標(biāo)準(zhǔn)差，使密文域中可容納的噪聲有效波動區(qū)間數(shù)從2個增加到2n個，實現(xiàn)明文可一次加密位數(shù)為O(lbn)，但是與原LWE算法相比，文獻[24]損失了一定的加密安全性與加解密魯棒性.2010年，Lyubashevsky等人提出LWE環(huán)上的代數(shù)變種R-LWE[20]，并證明其困難性也可以歸約到標(biāo)準(zhǔn)格中困難問題的最困難情況，與Regev與Kawachi等人的算法相比，Lyubashevsky的R-LWE算法通過運算結(jié)構(gòu)的改進，在保持加密強度與加解密魯棒性不變的情況下加密效率更高，密鑰長度更小.

Lyubashevsky的R-LWE算法可有效應(yīng)用于密文域可逆信息隱藏，因為R-LWE算法加密后的數(shù)據(jù)擴展攜帶大量信息冗余，該部分冗余對于沒有私鑰的攻擊者來說不包含任何有用信息，但是對于擁有私鑰的用戶來說可嵌入隱藏信息.本文主要工作為在數(shù)據(jù)加密與嵌入前的預(yù)處理過程中，通過引入流密碼進行隨機置亂，保持了嵌入前后R-LWE算法加密的困難性；通過對1位二進制明文在密文空間映射區(qū)域的重量化與對應(yīng)密文的再編碼來嵌入1位多進制數(shù)據(jù)，實現(xiàn)了單位比特明文可在密文域負載多比特隱藏信息；通過在密文域重量化過程中劃分子區(qū)域，并根據(jù)加密過程中的數(shù)據(jù)分布進行再編碼保證了加解密過程的魯棒性，而對影響R-LWE算法加解密正確性的各關(guān)鍵參數(shù)(如噪聲標(biāo)準(zhǔn)差)沒有額外的約束，保證了嵌入后密文的無差錯解密與嵌入信息的可靠提?。蛔詈?，在解密與信息提取過程中，分別采用不同的量化標(biāo)準(zhǔn)實現(xiàn)了提取與解密過程的可分離.

文獻[24]是當(dāng)前基于格進行多比特加密的代表算法，通過控制噪聲標(biāo)準(zhǔn)差縮小噪聲波動區(qū)間，使原算法中1 b明文對應(yīng)的密文空間可容納多個噪聲波動，從而滿足多比特明文在一次加密過程中可以映射在不同的噪聲波動區(qū)間，實現(xiàn)一次加密多比特明文，但是對噪聲標(biāo)準(zhǔn)差的約束會直接造成LWE算法的加密強度與加解密魯棒性降低.而本方案主要通過對密文域空間的重量化與密文數(shù)據(jù)的再編碼實現(xiàn)多比特信息嵌入，嵌入編碼根據(jù)加密過程中的數(shù)據(jù)分布進行，對加密過程中引入噪聲的標(biāo)準(zhǔn)差沒有額外約束，充分保證了原R-LWE算法的加密強度與魯棒性，本文在第3節(jié)具體分析了算法的正確性與安全性.最后，本文方案是在載體數(shù)據(jù)按比特位加密的過程中嵌入信息，與載體種類無關(guān)，適用于文本、圖片、音頻等載體.

1.2 Lyubashevsky的R-LWE加密算法[20]

Lyubashevsky的R-LWE算法是格上基于R-LWE問題的經(jīng)典公鑰密碼算法，本節(jié)介紹R-LWE算法過程，并對算法正確性進行說明.

設(shè)多項式向量維數(shù)d=O(lbq)，f(x)=xn+1，q>2n2,多項式環(huán)Rq=q[x]〈f(x)〉，r∈q.

結(jié)合圖示對上述算法的正確性進行簡要說明：

Fig. 1 The distribution of integers in q.圖1 整數(shù)域q的取值分布

2 本文算法介紹

2.1 設(shè)計思想

Fig. 2 The partition of integers in q.圖2 整數(shù)域q的區(qū)域劃分

算法主要包括參數(shù)設(shè)置、數(shù)據(jù)預(yù)處理、加密并嵌入數(shù)據(jù)、數(shù)據(jù)解密與信息提取等過程.圖3為算法的系統(tǒng)架構(gòu)與流程框架，圖3(a)中隨機序列作為用戶私鑰的一部分，用于預(yù)處理及解密或數(shù)據(jù)提取后的信息恢復(fù)，因此通常要求與系統(tǒng)參數(shù)及加密公私鑰一同更新.由圖3系統(tǒng)架構(gòu)可見，算法主要應(yīng)用于公鑰加密系統(tǒng)下的秘密通信雙方，隱藏密鑰的持有者才能進行密文域的嵌入提取及密文管理.如果通信雙方以外的可信第三方(如云服務(wù)器端)要進行數(shù)據(jù)嵌入與提取，可以通過事先協(xié)商系統(tǒng)參數(shù)并相應(yīng)調(diào)整密鑰(隱藏密鑰與解密密鑰)的分配策略來實現(xiàn).

Fig. 3 Brief framework of proposed scheme.圖3 算法框架示意

算法過程中使用函數(shù)L來返回輸入值x所在子區(qū)域的編號.

定義1. 函數(shù)L：y=L(x),y∈{0,1,…,B-1},

x∈q，表示q中元素x位于子區(qū)域y.則：

(1)

下面詳細介紹算法過程.

2.2 本文算法過程

2.2.1 參數(shù)設(shè)置

選取安全參數(shù)k>1、模數(shù)q，構(gòu)造多項式環(huán)Rq=q[x]〈f(x)〉，生成多項式f(x)=xn+1，n=2k，所有運算在多項式環(huán)Rq上進行.多項式向量維數(shù)d=O(lbq)，噪聲的分布為χ，其中α=1poly(n)；

2.2.2 數(shù)據(jù)預(yù)處理

設(shè)明文信息為p∈{0,1}n，隱藏信息為二進制序列mh.將p與隨機二進制序列r1異或生成用于加密的序列s1=[m0,m1,m2,…,mn-1]，mi∈{0,1}；mh與隨機二進制序列r2異或得到序列s2：

s1=r1⊕p,

(2)

s2=r2⊕mh,

(3)

將s1編碼為系數(shù)為二進制數(shù)的環(huán)多項式m用于加密，m=m0+m1x+…+mn-1xn-1，mi∈{0,1}；將s2編碼為系數(shù)為B進制數(shù)的環(huán)多項式w用于嵌入，w=w0+w1x+…+wn-1xn-1，wi∈{0,1,2,…,B-1}.

2.2.3 加密與信息嵌入

(4)

其中，

(5)

bi=wi-L(hi),

(6)

βibi∈{-1,1}，其符號決定嵌入過程中密文ci改變的正負；bi∈{-B+1,-B+2,…,-1,0,1,…,B-1}，bi的絕對值表示嵌入過程中原始密文ci偏移|bi|個量化步長.

2.2.4 解密與信息提取

(7)

(8)

(9)

(10)

3 算法分析與仿真實驗

3.1 正確性分析

Fig. 4 The distribution of integers in q.圖4 整數(shù)域 q 的取值分布

方案的正確性主要包括嵌入后密文的正確解密與嵌入信息的正確提取2方面.本節(jié)首先分析影響方案正確性的相關(guān)參數(shù).

完成上述加密與嵌入過程后，用戶即可實現(xiàn)可分離的解密得到原始明文或提取隱藏信息：

(11)

則方案出錯的概率為

P(|Ei|>q4)=Pr(|Ei|σ>q4σ)≤

(12)

由式(12)可知，當(dāng)標(biāo)準(zhǔn)差α足夠小時σ越小，噪聲產(chǎn)生的波動Ei較小，方案出錯的概率接近于0.在LWE算法中α通常取O(1lbn)[23].另一方面LWER-LWE問題求解的困難性依賴于噪聲的存在，如果α太小，噪聲分布在均值0附近偏差很小，噪聲波動區(qū)間的過小影響方案的安全性.為了保證加密強度，引入噪聲的波動范圍要足夠大，R-LWE算法中通常要求lbn[20].因此系統(tǒng)參數(shù)確定的情況下，噪聲分布的標(biāo)準(zhǔn)差對方案的正確性與安全性起著關(guān)鍵作用.文獻[20]中算法通過理論證明了R-LWE算法的安全性與正確性，但是關(guān)于相關(guān)參數(shù)對方案性能的影響只是進行了理論上的分析，在實用過程中的各關(guān)鍵參數(shù)的取值范圍并未具體說明，本文在參考理論分析的基礎(chǔ)上通過對大量數(shù)據(jù)進行加密與信息隱藏測試，進一步確定不同加密情況下噪聲分布標(biāo)準(zhǔn)差α的合理取值.

為直觀反應(yīng)實驗結(jié)果，以k=11,B=4,n=211加密Lena圖像的前214b數(shù)據(jù)并嵌入216b信息，檢驗標(biāo)準(zhǔn)差α=8.204 2×10-6時方案的正確性為例來介紹實驗過程.結(jié)合圖5對實驗過程進行說明如下：

Fig. 5 Experiment the image Lena by the proposed scheme with k=11,B=4,n=211.圖5 本文算法對Lena圖像的實驗過程(k=11,B=4,n=211)

其中圖5(a)為實驗載體圖像Lena；按位平面分離為二值序列得到位分離圖5(b)；將位分離圖分為128×128的互不重疊的二值數(shù)據(jù)塊，選取其中第1個塊作為明文數(shù)據(jù)進行加密，明文用二值圖像表示如圖5(c)；將明文隨機置亂如圖5(d)；隨機選取4進制數(shù)據(jù)作為隱藏信息如圖5(e)；加密后的原始密文如圖5(f)；對原始密文進行嵌入得到攜秘密文如圖5(g)；直接從攜秘密文中提取到的隱藏信息如圖5(h)；直接將攜秘密文進行解密并逆置亂得到解密結(jié)果如圖5(i)；通過逐比特位作差法分別對比解密數(shù)據(jù)與明文數(shù)據(jù)、秘密信息與提取信息結(jié)果如圖5(j)，表明解密與提取信息無差錯；將圖像Lena的位分離圖中剩余數(shù)據(jù)塊重復(fù)上述過程(當(dāng)明文數(shù)據(jù)長度小于n時，填充0或1)，得到完整的位分離圖，按位填充于各像素，最終恢復(fù)得到實驗圖像如圖5(k).表明實驗中所選的α=8.204 2×10-6滿足系統(tǒng)參數(shù)k=11時密文的正確解密與秘密信息的正確提取，正確率基本達到100%.

重復(fù)進行加密與信息隱藏測試，記錄標(biāo)準(zhǔn)差可取值的上限αmax.表1為實驗得到的保證方案正確性的標(biāo)準(zhǔn)差上限值αmax及滿足加密安全需要的下限值αmin.根據(jù)αmax與αmin得到α取值區(qū)間[λ αmin, ν αmax](λ>1,ν<1).根據(jù)該區(qū)間繼續(xù)對標(biāo)準(zhǔn)測試圖片、文本、音頻等數(shù)字載體進行實驗，結(jié)果表明：α在該區(qū)間取值可有效保證方案的正確性，其解密與提取隱藏信息的正確率基本達到100%.

Table 1 Ranges (αmin,αmax) of α with k∈[5,14]

可逆隱寫算法的評價標(biāo)準(zhǔn)中峰值信噪比(peak signal-noise ratio,PSNR)用來評價與原始載體信息相比較，恢復(fù)后載體的質(zhì)量或失真情況.PSNR值越大，表示圖像失真越小.對于大小M×N的256級灰度圖像PSNR：

(13)

其中,MSE表示恢復(fù)圖像像素矩陣I′與原始圖像像素矩陣I的均方誤差(mean squared error,MSE)：

(14)

一般，當(dāng)PSNR>35 dB時，人眼視覺就無法感知圖像的失真[26].圖6為使用密文域可逆信息隱藏算法[1]及可分離算法[17]對標(biāo)準(zhǔn)圖像庫中圖像Lena，Man，Lake，Baboon進行實驗得到的直接解密恢復(fù)圖像的PSNR.

Fig. 6 PSNR comparison of the methods in Ref [1,17].圖6 文獻[1,17]中算法載體直接恢復(fù)的PSNR

PSNR取值基本在35 dB～60 dB，與當(dāng)前大多數(shù)算法的可逆恢復(fù)效果相近，表明數(shù)據(jù)嵌入會在直接解密得到的圖像中引入失真，只是將失真控制在人眼無法感知的程度，且嵌入量越大失真越大.而本文算法解密恢復(fù)的正確率基本保持在100%，將解密結(jié)果代入式(13)(14)得到直接解密恢復(fù)圖像的PSNR值如表2所示，說明可完全保證可逆性.

Table 2 PSNR of the Proposed Scheme

3.2 安全性分析

密文域可逆信息隱藏的安全性主要是保持加密的安全性與嵌入信息的不可感知性2方面，其中不可感知性是可逆隱寫算法的重要評價指標(biāo)與實現(xiàn)密文域隱蔽通信的重要保證[2,19].在保持加密安全性方面，圖像加密及公鑰密碼算法安全性的關(guān)鍵指標(biāo)之一是加密數(shù)據(jù)符合均勻分布[27]，因此為保證嵌入過程不造成加密信息泄露，嵌入后的密文數(shù)據(jù)也應(yīng)服從均勻分布；在不可感知性方面，相關(guān)的研究還比較少，現(xiàn)有算法主要是分析載體嵌入信息前后的峰值信噪比(PSNR)，即嵌入前后載體數(shù)據(jù)的改變量.但是對于密文來說，因為公鑰加密算法要求明文的極小改變也將擴散到整個密文空間，嵌入前后的PSNR不能有效說明密文數(shù)據(jù)的變化是由于明文不同還是嵌入了額外信息，而且隱寫分析技術(shù)在對密文進行隱寫分析時通常不能獲得原始密文，當(dāng)前主要是對載體數(shù)據(jù)進行概率統(tǒng)計上的分析建模、提取特征，通過對特征分類來判斷是否隱藏信息[28]，因此對于密文域隱寫的安全性，不能簡單通過嵌入前后密文數(shù)據(jù)的改變量來說明，而是要求保持嵌入前后密文數(shù)據(jù)統(tǒng)計特性不變[19].綜上，本文在安全性分析中，著重分析密文在嵌入后的分布函數(shù)與統(tǒng)計特征.首先，推導(dǎo)嵌入后密文的分布函數(shù)如下：

P[Ei∈(0,q4)]=Fσ(0)=

P[Ei∈(3q4,q)]=1-Fσ(0)=12.

(15)

又當(dāng)Ei∈(0,q4)時，qq3q)，βi=1；

當(dāng)Ei∈(3q4,q)時，qq3q,q)，βi=-1.

故：

P(βi=1)=P(βi=-1)=12.

(16)

函數(shù)L(e)∈{0,1,…B-1},e∈q，表示q中元素e所在的子區(qū)域，記將正態(tài)分布下函數(shù)L值為y時的概率為PL(y).則可得：

y∈{0,1,…,B-1}.

(17)

方案中秘密信息多項式w的系數(shù)經(jīng)隨機置亂，則：

P(wi=0)=P(wi=1)=…=

P(wi=B-1)=1B,

(18)

又bi=wi-L(hi),bi∈{-B+1,-B+2,…,0,…,B-1}，wi,L(hi)∈{0,1,…,B-1}，記bi取值為x時的概率為Pb(x)，根據(jù)離散卷積公式得到bi的分布律如下，表3具體列舉了bi取不同值時各變量的取值情況及其分布律：

Table 3 Distribution Ratio of bi

由上可推得隱寫前后密文產(chǎn)生不同改變量時的概率，

P(βi=-1)Pb(-λ),

(19)

P(βi=1)Pb(-λ),

(20)

Table 4 Distribution Ratio of λ

設(shè)原始密文ci～U(0,q),其分布函數(shù)符合均勻分布，記為Fc(x)=xq,x∈(0,q)，嵌入后密文的分布函數(shù)記為Fcs(x)：

Fcs(x)=P(csi

(21)

由式(21)可知，嵌入信息后密文數(shù)據(jù)的分布函數(shù)與原始密文分布函數(shù)一致，服從q上的均勻分布.

下面通過實驗分析說明嵌入信息后密文的統(tǒng)計特征.實驗參數(shù)設(shè)置如下：k=6，9，12，q=64n3+1，n=2k，B=8；參數(shù)d，r影響方案的密鑰安全，根據(jù)剩余Hash引理[25]，保證公鑰接近均勻分布的一個充分條件就是私鑰的取值空間要遠遠大于公鑰的取值空間，即(r+1)d n?qn，又因為d越大密文擴展率越大，公鑰長度也成倍增加，在滿足安全性的前提下，為節(jié)省公鑰存儲空間，取d=lbq，r=64.α從3.1節(jié)得到的區(qū)間取值：α∈[λαmin,ναmax](λ>1,ν<1).對多組大量樣本數(shù)據(jù)進行加密，1 b明文在加密域攜帶3 b數(shù)據(jù)，如圖7所示嵌入前后密文分布直方圖，圖7中顏色漸變用于區(qū)分不同組的樣本數(shù)據(jù).計算各組樣本實驗結(jié)果的信息熵，記為H，對應(yīng)加密域中元素等概率分布時的最大信息熵記為Hideal，結(jié)果如圖7所示.

由圖7可以看出信息嵌入后密文直方圖沒有出現(xiàn)明顯變化，而且嵌入過程的再編碼相當(dāng)于對密文進行粗粒度的隨機置亂，因此對密文數(shù)據(jù)直方圖的分布特性基本不會發(fā)生破壞.B取其他值進行實驗，結(jié)論與上述一致.對上述直方圖中數(shù)據(jù)計算平均信息熵，結(jié)果表明嵌入后密文數(shù)據(jù)的信息熵不低于原始密文，基本接近于加密域中元素等概率分布時的最大信息熵.

Fig. 7 Histograms and information entropy of encrypted data before embedding and those after embedding.圖7 信息隱藏前后密文數(shù)據(jù)分布直方圖與平均信息熵值

Fig. 8 Relationship between expectation of test data and ideal expectation.圖8 不同嵌入量下密文期望與理想期望關(guān)系

由實驗結(jié)果可見：在誤差允許范圍內(nèi)，不同嵌入量下的密文數(shù)據(jù)期望與所在密文域的理想期望基本一致，表明在嵌入信息后密文的統(tǒng)計期望未發(fā)生明顯變化.

3.3 嵌入容量分析

在嵌入容量方面，文獻[17]中載荷約為0.0328 bpp，即8 b大小的像素可嵌入0.0328 b信息；文獻[13]通過翻轉(zhuǎn)第6LSB位的方式實現(xiàn)了載荷的有效提升，約0.06 bpp；文獻[29]將LDPC編碼引入密文域可逆隱寫，將載荷提升到0.1 bpp.已有針對于圖像載體的密文域可逆信息隱藏算法的嵌入率受到像素內(nèi)容或加密方式的限制較大，有效載荷基本不超過0.5 bpp，文獻[10]使用熵編碼實現(xiàn)通用密文域可逆信息隱藏，在完全可逆的情況下嵌入量基本達到0.169 bpb，即1 b密文可攜帶0.169 b秘密信息；文獻[19]在LWE算法加密后數(shù)據(jù)的冗余部分嵌入信息， 1 b明文在密文域最大可負載1 b隱藏信息.與文獻[19]相比，本文方案當(dāng)選擇B進制數(shù)作為秘密信息時，1 b明文在密文域最大可負載lbBb隱藏信息，本文方案的密文嵌入率的情況具體分析如下.

Fig. 9 Embedding rates in different settings of proposed scheme.圖9 不同系統(tǒng)設(shè)置下的密文嵌入率

如圖9所示為根據(jù)表3中實驗結(jié)果得出在不同的安全參數(shù)k的取值時，單位比特密文的嵌入率隨lbB取值變化的情況.結(jié)合3.1節(jié)、3.2節(jié)分析與圖9可知，系統(tǒng)安全參數(shù)k不變時，嵌入率隨lbB增大而提高；lbB不變時，k越大加密強度越大，一次可加密的明文與嵌入信息量增多，但密文擴展較大，嵌入率降低.因此在實際應(yīng)用中可根據(jù)加密與信息嵌入的現(xiàn)實需要選擇合適的安全參數(shù)k與嵌入信息進制數(shù)B.但是參數(shù)B不能無限增大，原因是隨著B值的增大，方案中q劃分子區(qū)域的量化步長q不斷縮小，造成嵌入過程對加密數(shù)據(jù)的修改粒度越細，由3.2節(jié)中分析可知算法安全性依賴于預(yù)處理過程中嵌入數(shù)據(jù)的隨機性，因此預(yù)處理過程中隨機數(shù)生成器的安全性對加密數(shù)據(jù)的影響隨著量化步長的縮小而加強.如果隨機數(shù)生成器生成數(shù)據(jù)的隨機性低于R-LWE算法加密結(jié)果的隨機性，隨著B的增大，量化步長小于安全性需要的噪聲波動的最小值時，嵌入后密文數(shù)據(jù)的安全性會降低.而高強度的隨機數(shù)生成器會影響方案的執(zhí)行效率，綜合考慮當(dāng)前隨機數(shù)生成算法的安全性與運行效率，B的取值不能無限取大.

本文實驗中相關(guān)參數(shù)的選擇充分保證了量化步長大于噪聲波動的安全性需要的下限，如表5所示為不同系統(tǒng)設(shè)置時的密文最大嵌入率，表5中第1列表項(k,lbB)列舉了嵌入率最大時的系統(tǒng)安全參數(shù)k與秘密信息的進制數(shù)B.

Table 5 Hightest Embedding Rates in Different Settings of Proposed Scheme / bit per bit of ciphertext

表5 不同系統(tǒng)設(shè)置下單位密文最大嵌入率/bpb

根據(jù)實驗結(jié)果，密文嵌入率可達到0.1600 bpb以上，其中k=6，lbB=4時密文嵌入率最小，為0.1600 bpb；當(dāng)k>9時，1 b明文在密文域可最大負載8 b秘密信息，其中k=9，lbB=8時單位密文的最大嵌入率達到0.2353 bpb，此時方案的加密執(zhí)行效率與嵌入率達到最理想狀態(tài).

4 結(jié)束語

本文提出了基于R-LWE的密文域多比特可逆信息隱藏算法，通過對密文域的分區(qū)量化以及加密數(shù)據(jù)的重編碼來嵌入多比特額外信息，提高信息嵌入率的同時保證了攜秘密文的可逆解密與嵌入信息的無失真提取.理論分析與仿真實驗說明了方案的正確性、安全性以及在嵌入容量上的有效保證.當(dāng)前基于(R-)LWE的公鑰加密算法廣泛用于構(gòu)造多種應(yīng)用場景下的密碼方案，如數(shù)字簽名、屬性加密，滿足可信第三方密文處理的代理重加密[30]、全同態(tài)加密[31]等，未來可將本方案的嵌入技術(shù)應(yīng)用于上述基于(R-)LWE的加密環(huán)境與密碼應(yīng)用中，進一步擴展密文域可逆信息隱藏的應(yīng)用場景.但是本方案隨著算法加密規(guī)模的增大，算法的密文擴展仍然較大，未來工作需要進一步精確嵌入容量的有效范圍，改進信息嵌入的編碼方式來更好地利用密文擴展，提高密文域隱藏信息的嵌入率.

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

[2]Chen Jiayong, Wang Chao, Zhang Weiming, et al. A secure image steganographic method in encrypted domain[J]. Journal of Electronics & Information Technology, 2012, 34(7): 1721-1726 (in Chinese)(陳嘉勇, 王 超, 張衛(wèi)明, 等. 安全的密文域圖像隱寫術(shù)[J]. 電子與信息學(xué)報, 2012, 34(7): 1721-1726)

[3]Yin Zhaoxia. Privacy protection oriented image steganography[D]. Hefei: Anhui University, 2014 (in Chinese)(殷趙霞. 面向隱私保護的數(shù)字圖像隱寫方法研究[D]. 合肥: 安徽大學(xué), 2014)

[4]Barni M, Kalker T, Katzenbeisser S. Inspiring new research in the field of signal processing in the encrypted domain[J]. IEEE Signal Processing Magazine, 2013, 30(2): 16

[5]Zhao Bin, Kou Weidong, Li Hui, et al. Effective watermarking scheme in the encrypted domain for buyer-seller watermarking protocol[J]. Information Sciences, 2010, 180(23): 4672-4684

[6]Lian Shiguo, Liu Zhongxuan, Ren Zhen, et al. Commutative encryption and watermarking in video compression[J]. IEEE Trans on Circuits and Systems for Video Technology, 2007, 17(6): 774-778

[7]Cancellaro M, Battisti F, Carli M, et al. A commutative digital image watermarking and encryption method in the tree structured Haartransform domain[J]. Signal Processing: Image Communication, 2011, 26(1): 1-12

[8]Kuribayashi M, Tanaka H. Fingerprinting protocol for images based on additive homomorphic property[J]. IEEE Trans on Image Processing, 2005, 14(12): 2129-2139

9]Memon N, Wong P. A buyer-seller watermarking protocol[J]. IEEE Trans on Image Processing, 2001, 10(4): 643-649

[10]Abdul Karim M S, Wong K. Universal data embedding in encrypted domain[J]. Signal Processing, 2014, 94(2): 174-182

[11]Hong Wien, Chen Tungshou, Wu Hanyan. An improved reversible data hiding in encrypted images using side match[J]. IEEE Signal Processing Letters, 2012, 19(4): 199-202

[12]Yu Jie, Zhu Guopu, Li Xiaolong, et al. Digital Forensics and Watermarking: An Improved Algorithm for Reversible Data Hiding in Encrypted Image[M]. Berlin: Springer, 2014: 384-394

[13]Wu Xiaotian, Sun Wei. High-capacity reversible data hiding in encrypted images by prediction error[J]. Signal Processing, 2014, 104(11): 387-400

[14]Qian Zhenxing, Zhang Xinpeng, Wang Shuozhong. Reversible data hiding in encrypted JPEG bitstream[J]. IEEE Transaction on Multimedia, 2014, 16(5): 1486-1491

[15]Liao Xin, Shu Changwen. Reversible data hiding in encrypted images based on absolute mean difference of multiple neighboring pixels[J], Journal of Visual Communication and Image Representation, 2015, 28(4): 21-27

[16]Li Ming, Xiao Di, Peng Zhongxian, et al. A modified reversible data hiding in encrypted images using random diffusion and accurate prediction[J]. ETRI Journal, 2014, 36(2): 325-328

[17]Zhang Xinpeng. Separable reversible data hiding in encrypted image[J]. IEEE Trans on information forensics and security, 2012, 7(2): 826-832

[18]Xiao Di, Chen Shoukuo. Separable data hiding in encrypted image based on compressive sensing[J]. Electronics Letters, 2014, 50(8): 598-600

[19]Zhang Minqing, Ke Yan, Su Tingting. Reversible steganography in encrypted domain based on LWE[J]. Journal of Electronics & Information Technology, 2016, 38(2): 354-360 (in Chinese)(張敏情, 柯彥, 蘇婷婷. 基于LWE的密文域可逆信息隱藏[J]. 電子與信息學(xué)報, 2016, 38(2): 354-360)

[20]Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[J]. Journal of the ACM, 2013, 60(6): Article 43(1)-43(23)

[21]Regev O. On lattices, learning with errors, random linear codes and cryptography[J]. Proceeding of the Annual ACM Symposium of Theory of Computing, 2009, 56(6): 84-93

[22]Yu Weichi. Lattice basis reduction theory and applications in crypto scheme designing[D]. Chengdu: South West Jiao Tong University, 2005 (in Chinese)(余位馳. 格基規(guī)約理論及其在密碼設(shè)計中的應(yīng)用[D]. 成都: 西南交通大學(xué), 2005)

[23]Regev O. The learning with errors problem[C] //Proc of the 25th Annual IEEE Conf on Computational Complexity (CCC 2010). Los Alamitos, CA: IEEE Computer Society, 2010: 191-204

[24]Akinori K, Keisuke T, Keita X. Multi-bit cryptosystems based on lattice problems[G] //LNCS 4450: Proc of Int Conf on Public Key Cryptograghy (PKC2007). Berlin: Springer, 2007: 315-329

[25]Rückert M, Schneider M. Estimating the security of lattice-based cryptosystems[EB/OL]. (2010-10-06) [2016-08-10]. http://eprint.icur.org/2010/137.pdf

[26]Zeng Xiao, Chen Zhenyong, Chen Ming, et al. Invertible image watermarking based on zero coefficient index[J]. Journal of Computer Research and Development, 2010, 47(7): 1304-1312 (in Chinese)(曾驍, 陳真勇, 陳明, 等. 基于零系數(shù)索引的可逆圖像水印[J]. 計算機研究與發(fā)展, 2010, 47(7): 1304-1312)

[27]Peng Zaiping, Wang Chunhua, Lin Yuan. A novel four-dimensional multi-wing hyper-chaotic attractor and its application in image encryption[J]. Acta Physica Sinica, 2014, 63(24): 240506-1-240506-10 (in Chinese)(彭再平, 王春華, 林愿. 一種新型的四維多翼超混沌吸引子及其在圖像加密中的研究[J]. 物理學(xué)報, 2014, 63(24): 240506-1-240506-10)

[28]Wang Ran, Xu Mankun, Ping Xijian, et al. Steganalysis of spatial images based on segmentation[J]. Acta Automatica Sinica, 2014, 40(12): 2936-2943 (in Chinese)(汪然, 許漫坤, 平西建, 等. 基于分割的空域圖像隱寫分析[J]. 自動化學(xué)報, 2014, 40(12): 2936-2943)

[29]Zhang Xinpeng, Qian Zhenxing, Feng Guorui, et al. Efficient reversible data hiding in encrypted image[J]. Journal of Visual Communication and Image Representation. 2014, 25(2): 322-328

[30]Xagawa K, Tanaka K. Proxy re-encryption based on learning with errors (mathematical foundation of algorithms and computer science)[J]. Rims Kokyuroku, 2010, 1691: 29-35

[31]Gentry C. Fully homomorphic encryption using ideal lattices[C] //Proc of the 41st ACM Symp on Theory of Computing (STOC2009). New York: ACM, 2009: 169-178

Ke Yan, born in 1991. MEn candidate. His main research interests include information security, reversible data hiding and cryptography, etc.

Zhang Minqing, born in 1967, PhD, professor, PhD supervisor. Her main research interests include cryptography and information security (api_zmq@126.com).

Su Tingting, born in 1989. MEn. Her main research interests include information security and network security (suting0518@163.com).

A Novel Multiple Bits Reversible Data Hiding in Encrypted Domain Based on R-LWE

Ke Yan, Zhang Minqing, and Su Tingting

(KeyLaboratoryofNetworkandInformationSecurityUndertheChinesePeopleArmedPoliceForce(EngineeringUniversityofPAP),Xi’an710086) (DepartmentofElectronicTechnology,EngineeringUniversityofPAP,Xi’an710086)

Reversible data hiding in encrypted domain is one kind of information hiding techniques which can both extract secret messages and decrypt the embedded ciphertext to restore the original cover vehicle losslessly, possessing privacy protection and data hiding dual function. It is a potential technique in signal processing and data management of the encrypted domain fields. This paper proposes a novel scheme of multiple bits reversible data hiding in encrypted domain based on R-LWE (ring-learning with errors). Multi-band data can be embedded by quantifying the encrypted domain and recoding in the redundancy of cipher text without degrading the hardness of R-LWE algorithm; the embedding recoding method is based on the data distribution during encryption, which maintains the robustness of R-LWE algorithm; By dividing the integer domain into the sub-regions and introducing different quantifying rules, the processes of extraction and decryption can be separated. By deducing the error probability of the scheme, parameters in the scheme which is directly related to the correctness of the scheme is mainly discussed, and reasonable ranges of the parameters are obtained by experiments. When analyzing the security, the probability distribution function of the embedded cipher text is deduced and the statistic features of cipher data are analyzed, which both prove the embedded data isn’t detective. Experimental results have demonstrated that the proposed scheme can not only keep fully reversibility of vehicle recovering and lossless extraction of secret message, but realize that one bit original data can load multiple-bit additional data in encrypted domain, achieving an embedding capacity of 0.2353 bit per every bit of the encrypted data.

information security; reversible data hiding; encrypted domain; multiple bits embedding; ring-learning with errors (R-LWE)

2016-06-16；

2016-08-11

國家自然科學(xué)基金項目(61379152,61403417)

TP309.7

This work was supported by the National Natural Science Foundation of China (61379152,61403417).