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

柯 彥 張敏情 蘇婷婷

(網絡與信息安全武警部隊重點實驗室(武警工程大學) 西安 710086) (武警工程大學電子技術系 西安 710086) (15114873390@163.com)

?

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

柯 彥 張敏情 蘇婷婷

(網絡與信息安全武警部隊重點實驗室(武警工程大學) 西安 710086) (武警工程大學電子技術系 西安 710086) (15114873390@163.com)

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

信息安全；可逆信息隱藏；密文域；多比特嵌入；環上帶誤差的學習

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

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

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

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

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

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

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

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

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

1 相關技術

1.1 (R)LWE問題與分析

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

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

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

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

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

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

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

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

2 本文算法介紹

2.1 設計思想

Fig. 2 The partition of integers in q.圖2 整數域q的區域劃分

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

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

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

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

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

(1)

下面詳細介紹算法過程.

2.2 本文算法過程

2.2.1 參數設置

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

2.2.2 數據預處理

設明文信息為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編碼為系數為二進制數的環多項式m用于加密，m=m0+m1x+…+mn-1xn-1，mi∈{0,1}；將s2編碼為系數為B進制數的環多項式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 整數域 q 的取值分布

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

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

(11)

則方案出錯的概率為

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

(12)

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

為直觀反應實驗結果，以k=11,B=4,n=211加密Lena圖像的前214b數據并嵌入216b信息，檢驗標準差α=8.204 2×10-6時方案的正確性為例來介紹實驗過程.結合圖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的互不重疊的二值數據塊，選取其中第1個塊作為明文數據進行加密，明文用二值圖像表示如圖5(c)；將明文隨機置亂如圖5(d)；隨機選取4進制數據作為隱藏信息如圖5(e)；加密后的原始密文如圖5(f)；對原始密文進行嵌入得到攜秘密文如圖5(g)；直接從攜秘密文中提取到的隱藏信息如圖5(h)；直接將攜秘密文進行解密并逆置亂得到解密結果如圖5(i)；通過逐比特位作差法分別對比解密數據與明文數據、秘密信息與提取信息結果如圖5(j)，表明解密與提取信息無差錯；將圖像Lena的位分離圖中剩余數據塊重復上述過程(當明文數據長度小于n時，填充0或1)，得到完整的位分離圖，按位填充于各像素，最終恢復得到實驗圖像如圖5(k).表明實驗中所選的α=8.204 2×10-6滿足系統參數k=11時密文的正確解密與秘密信息的正確提取，正確率基本達到100%.

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

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

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

(13)

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

(14)

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

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

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

Table 2 PSNR of the Proposed Scheme

3.2 安全性分析

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

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

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

(15)

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

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

故：

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

(16)

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

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

(17)

方案中秘密信息多項式w的系數經隨機置亂，則：

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)，根據離散卷積公式得到bi的分布律如下，表3具體列舉了bi取不同值時各變量的取值情況及其分布律：

Table 3 Distribution Ratio of bi

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

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

(19)

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

(20)

Table 4 Distribution Ratio of λ

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

Fcs(x)=P(csi

(21)

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

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

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

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

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

由實驗結果可見：在誤差允許范圍內，不同嵌入量下的密文數據期望與所在密文域的理想期望基本一致，表明在嵌入信息后密文的統計期望未發生明顯變化.

3.3 嵌入容量分析

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

Fig. 9 Embedding rates in different settings of proposed scheme.圖9 不同系統設置下的密文嵌入率

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

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

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

表5 不同系統設置下單位密文最大嵌入率/bpb

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

4 結束語

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

[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)(陳嘉勇, 王 超, 張衛明, 等. 安全的密文域圖像隱寫術[J]. 電子與信息學報, 2012, 34(7): 1721-1726)

[3]Yin Zhaoxia. Privacy protection oriented image steganography[D]. Hefei: Anhui University, 2014 (in Chinese)(殷趙霞. 面向隱私保護的數字圖像隱寫方法研究[D]. 合肥: 安徽大學, 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]. 電子與信息學報, 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)(余位馳. 格基規約理論及其在密碼設計中的應用[D]. 成都: 西南交通大學, 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)(曾驍, 陳真勇, 陳明, 等. 基于零系數索引的可逆圖像水印[J]. 計算機研究與發展, 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]. 物理學報, 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]. 自動化學報, 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

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

TP309.7

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