基于多項式秘密共享的圖像密文域可逆信息隱藏

張敏情 王澤曦 柯 彥 孔詠駿 狄富強

(武警工程大學密碼工程學院 西安 710086)

(中國人民武裝警察部隊密碼與信息安全保密重點實驗室 西安 710086)

1 引言

密文域可逆信息隱藏[1](Reversible Data Hiding in Encrypted Domain, RDH-ED)將密文圖像作為載體，能夠在密文圖像中嵌入額外信息，并且在準確提取額外信息的同時又不對原始圖像造成任何失真。RDH-ED為用戶提供了隱私保護和密文檢索與管理的功能，可應用于軍事、遠程醫療、司法取證等既要求載體安全，又要保證載體無失真重構的領域。近年來，隨著社交媒體與云計算等領域的不斷發展，數據隱私保護的需求日益緊迫。秘密共享(Secret Sharing, SS)作為一種重要的多方安全密碼體制，利用門限函數將重要數據分割成不同的份額存儲在不同用戶端，當部分數據份額遭受攻擊或者損壞時，能起到分擔系統風險，增強數據容災的作用。然而，如何在不泄露用戶隱私的情況下，對這些數據份額進行認證、管理與檢索是當前亟待解決的問題之一。本文將圖像秘密共享方案與密文域可逆信息隱藏相結合，不僅能實現多用戶場景下的圖像容災，還能將額外信息可逆地嵌入密文圖像，實現對密文圖像的認證、管理與檢索等功能。

RDH-ED根據應用場景可分為：信息隱藏單用戶模型與多用戶模型。其中單用戶模型是當前研究的熱點，主要有加密后生成冗余(Vacating Room After Encryption, VRAE)、加密前生成冗余(Vacating Room Before Encryption, VRBE)和加密過程冗余(Vacating Redundancy In Encryption,VRIE)3種框架。在VRAE框架下，Puech等人[2]最早提出了AES加密后騰出空間的方法，額外信息只能在標記圖像解密前根據圖像局部標準差提取；隨后，Zhang[3]基于流密碼加密后，通過翻轉3個最低有效位騰出空間，只有在標記圖像解密后才能利用圖像局部特性定義的波動函數提取秘密信息；為了實現算法的可分離性，Zhang[4]通過無損壓縮密文圖像生成冗余的方法首次提出了可分離的方案，但是嵌入率較小。VRBE模式即在圖像加密前利用圖像的相關性或者其他預處理操作生成冗余，實現方式主要有：基于無損壓縮[5,6]、基于像素預測[7–9]和基于頻域變換[10]等方法。這類算法充分壓縮了自然圖像的冗余，實現了大容量的可逆嵌入。Wu等人[11]在加密前通過自嵌入的方法騰出冗余，并利用Paillier密碼的同態特性和自盲屬性提出了兩種嵌入算法，實現了算法的可分離性。然而，復雜的預處理操作難以在實際應用中實現，存在一定應用局限。Zhang和Ke等人[12,13]首次提出了基于VRIE的RDH-ED方案，通過量化LWE加密后的密文空間，并利用密文擴展產生的冗余嵌入秘密信息；Huang等人[14]利用預測誤差在流密碼加密過程中騰出冗余空間，提升了嵌入容量。近年來，Chen等人[15]首次提出了基于Paillier公鑰加密的算法，利用同態性質在密文域嵌入信息，解密后的明文仍能保持嵌入信息的相關特性，但是嵌入信息后存在部分像素溢出的情況；Wu等人[16]通過解決溢出問題改進了文獻[15]的方法，同態加密算法的安全性依賴于長密鑰，這會增大計算開銷并帶來嚴重的數據擴展。為了解決上述問題，Wu等人[17]首次提出了基于秘密共享加密的RDH-ED算法，將原始圖像用秘密共享加密分割成多幅與原始圖像大小相同的影子圖像，再通過差值擴展和預測誤差直方圖平移的方式將秘密信息嵌入到影子圖像中，有效解決了加密開銷大和數據擴展嚴重的問題。之后，Chen等人[18]利用多秘密共享的加法同態性質并結合差值擴展的方式將秘密信息嵌入一對像素中，進一步減小了時間復雜度。Ke等人[19]基于中國剩余定理提出了一種可分離的RDH-ED，該方案通過組合兩種嵌入方法實現了可分離性。

2020年，Chen等人[20]首次針對信息隱藏多用戶場景，基于秘密共享加密提出了兩種聯合、兩種可分離的RDH-ED框架并提供了一種具體的可分離方案，它將載體圖像分割成多幅與原始圖像大小相同的影子圖像，并分發至多位用戶以獨立地嵌入額外信息；當其中部分用戶管理的含密圖像遭受攻擊或損壞時，仍可根據其他用戶重構原始圖像，進一步增強了圖像的安全性。然而，該算法沒有完全實現多用戶的獨立嵌入，嵌入前需要根據用戶數量為每位用戶分配指定的嵌入位置，導致用戶間彼此制約且影響嵌入容量。此外，在提取額外信息的過程中，沒有發揮秘密共享門限效應的技術優勢，即當部分用戶管理的影子圖像遭受攻擊或損壞時，無法提取額外信息。

本文面向信息隱藏多用戶場景，設計了一種基于多項式秘密共享的圖像密文域可逆信息隱藏算法，該算法在不同門限方案和影子圖像壓縮率的條件下，均能實現大容量的可逆嵌入，可以有效減小數據擴展，充分發揮圖像秘密共享技術的門限優勢，增強原始圖像與嵌入信息的容錯性和抗災性。

2 相關知識

2.1 秘密共享

Shamir[21]最早提出了基于拉格朗日(Lagrange)插值多項式的秘密共享方案，該方案將一個秘密分割成n份影子后分別供不同的參與者享有，只有收集k份或更多有效影子才能重構秘密，任何少于k份有效影子的重構都是無效的。將秘密共享應用于圖像共享時[22]，為了避免像素溢出將方案構建在有限域G F(qm)的 代數結構上，其中q為素數，m為正整數。

2.2 矩陣編碼隱寫

矩陣編碼隱寫[23]是一種基于線性變換且遵循最小嵌入失真原則的隱寫方法，相比基于最低有效位(Least Significant Bit, LSB)嵌入的方法，該方法對載體修改的平均次數更少，嵌入效率更高。

定理2最小碼距為d的二元(t,r)線性分組隱寫碼，最多修改d比特即可嵌入t?r比特信息。

假設有 G F(2) 上的(t,r)線性分組碼，其最小碼距為d，生成矩陣為G，一致校驗矩陣為H，滿足H ·GT=0。基于該線性碼構造隱寫碼的方法如下：

首先，選擇二元序列x=(x1,x2,...,xt)T作為嵌入載體，并取t ?r比特秘密信息m=(m1,m2,...,mt?r)T。然后，通過計算伴隨式S=m ?H ·x，在譯碼表中找出錯誤圖樣E且滿足H ·E=S=m?H ·x，由此在秘密信息與錯誤圖像之間建立了一種一一映射關系。最后，計算y=x+E，即將錯誤圖樣E嵌入載體中生成含密載體y=(y1,y2,...,yt)。信息提取時，利用一致校驗矩陣H計算H ·y=m即可得到嵌入的信息。

3 算法設計

3.1 算法框架

在分布式云存儲的多用戶場景中，原始圖像被分割成多幅影子圖像并存儲在不同的用戶端，可以增強圖像的安全性，同時為滿足多用戶對密文數據的標記、管理與檢索等需求。本文提出了兩種嵌入算法，算法1是多項式嵌入，即在圖像分割的過程中將額外信息嵌入多項式的冗余系數中，與圖像1同分割成多幅含有額外信息的影子圖像，該算法需要在圖像重構之后提取額外信息，可用于秘密信息的隱蔽傳輸；算法2是同態嵌入，它針對圖像分割后的任一影子圖像，利用秘密共享的加法同態特性在影子圖像中嵌入額外信息，該算法可以直接從影子圖像中提取額外信息，可用于對密文圖像的標記、管理與檢索。圖像重構以后，需要同態解密才能無失真地恢復原始圖像。通過結合兩種嵌入算法，不僅實現了額外信息的大容量可逆嵌入，還實現了額外信息提取與圖像重構的可分離性，算法框架如圖1所示。

圖1 算法框架

表1對文中相關變量做出了說明。

表1 相關變量說明

3.2 算法步驟

3.2.1 密鑰生成

其中，xi,yi表 示置亂前像素的位置，xi+1,yi+1表示置亂后像素的位置，mod為模運算，a,b是由置亂密鑰生成的參數。

3.2.3 信息嵌入

(1) 多項式嵌入

秘密共享方案在實際應用中為了快速解密通常僅將常數項作為秘密，而將其他系數用隨機數代替，在秘密重構時僅恢復常數項，而忽略其他各項系數，由于多項式的各項系數均可恢復，這些隨機數可作為加密過程中的冗余空間。多項式嵌入算法就是利用圖像分割過程中產生的隨機數作為冗余空間嵌入額外信息的，它將原始圖像與額外信息嵌入多項式的冗余系數中分割成多幅含有額外信息的影子圖像，該算法必須在圖像重構以后才能提取額外信息。由于該算法嵌入信息時具有更好的隱蔽性，可用于秘密信息隱蔽傳輸。

定義1在多項式嵌入算法中，每次選取w個像素嵌入多項式，經過秘密共享后每位用戶僅需要保存一個影子像素，即將w個像素壓縮為一個像素，則稱w為影子圖像壓縮系數。

(2) 同態嵌入

同態嵌入算法將圖像分割后的任一影子圖像作為嵌入載體，利用秘密共享的加法同態特性，使每位用戶都可以獨立地將額外信息嵌入到影子圖像中，該算法可以直接從新生成的影子圖像中快速提取額外信息，方便多用戶獨立標記、管理與檢索密文圖像。為提高嵌入效率，即用較少的修改嵌入盡量多的信息，本文采用了矩陣編碼隱寫[23]的方法進行同態嵌入，并在4.4節提供了矩陣編碼代替同態加法操作的安全性證明。嵌入過程如下：

3.2.4 信息提取與圖像重構

信息提取時，由于采用了兩種嵌入算法使得額外信息在圖像重構前后均可提取。多項式嵌入算法支持在圖像重構之后提取額外信息，同態嵌入算法支持在圖像重構之前直接從影子圖像中提取額外信息。圖像重構時，同態嵌入算法對分割后的影子圖像進行了第2次嵌入，它會對影子圖像造成一定的修改，因此，圖像重構以后是含有噪聲的，需要根據輔助信息進行同態解密消除噪聲才能無失真地重構原始圖像。

表2 譯碼表

4 仿真實驗與分析

實驗選取如圖2所示4幅大小均為5 12×512的灰度圖像作為測試集。實驗環境為：主機配置CPU Intel(R) Core(TM) i7-10875 H 2.30 GHz，內存32 GB，操作系統Windows 10，編程語言MATLAB 2019 b。

圖2 測試圖像

參數設置：門限參數為k=3,n=4，圖像壓縮系數w=2 ，用戶集合：{′A′,′F′,′b′,′o′}，以Lena圖像為例，實驗結果分析如下。Lena圖像經多項式嵌入后生成4幅互不相同且含有額外信息的影子圖像，并存儲在不同的用戶端。從中任選1幅如圖3(a)所示，影子圖像被壓縮為原來的一半，4幅影子圖像的總量為原始圖像的兩倍，即數據擴展率為2；圖3(b)是以圖3(a)為載體經同態嵌入后生成的影子圖像。兩次嵌入后的影子圖像均為噪聲狀，保證了圖像的安全性。

圖3 兩次嵌入后含有額外信息的影子圖像

圖4為Lean重構圖像及其直方圖，其中，圖4(a)–圖4(c)分別表示同態解密前重構置亂圖像、同態解密前重構明文圖像、同態解密后重構明文圖像，圖4(c)–圖4(e)分別為其相應的直方圖。同態解密前重構密文圖4(a)是含有噪聲的置亂圖像，其直方圖僅呈現出部分規律分布。置亂操作破壞了像素間的相關性，但不會改變圖像的直方圖分布，因此，恢復置亂后的明文圖4(b)呈現出Lena圖像的部分紋理，其統計特征沒有改變。由于圖像中含有大量的噪聲，圖像均呈現噪聲狀，需要同態解密消除噪聲才能無損地恢復原始圖像。同態解密后重構的明文圖4(c)在視覺效果上與原始圖像無任何區別，其直方圖4(f)與原始圖像直方圖也具有相同的分布特征。

圖4 Lena重構圖像及其直方圖

4.1 嵌入容量

本文算法的嵌入容量(Embedding Capacity,EC)由兩部分組成，一部分是多項式嵌入的額外信息比特，另一部分是同態嵌入的額外信息比特，兩種方法的嵌入容量均不受載體圖像紋理的影響，且只與算法參數有關，即當門限參數為(k, n)，圖像壓縮系數為w時，對于大小為M×N原始圖像，嵌入容量可由式(14)、式(15)計算

為準確反映算法的實際嵌入率(Embedding Rate, ER)，不僅要考慮密文數據的擴展，還需要減去輔助信息占用的空間，計算方法由式(16)給出。表3列出了算法在不同參數下的實際最大嵌入率。算法的嵌入率只與算法參數有關，與載體圖像平滑程度或像素間相關性等因素無關。當門限參數n和k固定時，壓縮系數w越大嵌入率越小；當門限值k和壓縮系數w固定時，n越大嵌入率也越小；當n和w固 定時，k越大嵌入率越大。因此，門限參數和壓縮系數與嵌入率之間存在折中關系。

表3 實際最大嵌入率

其中，k，n表示秘密共享的門限參數; w為影子圖像壓縮系數，滿足n>k>w，且n,k,w ∈N?。

圖5對比了不同類型隱藏算法的最大嵌入率，參數為k=3,n=4,w=2時算法的最大嵌入率達到4.182 bpp (bit per pixel)；參數為k=3,n=5,w=2時算法的最大嵌入率達到3.782 bpp。與文獻[8]算法基于MSB預測的大容量隱藏方法和Huang等人[14]基于特殊加密過程的隱藏方案相比，嵌入率顯著提升；在密文數據擴展率均為2的情況下，相比文獻[17,20]算法的(2, 2)門限隱藏方案，嵌入率平均分別高出約2.112 bpp, 0.482 bpp；在門限參數相同的條件下，最大嵌入率比文獻[20]的算法高出3.932 bpp。

圖5 最大嵌入率對比

4.2 圖像質量

峰值信噪比(Peak Signal to Noise Ratio, PSRN)用于評估可逆信息隱藏算法重構圖像的失真程度，當PSNR > 35 dB時，人眼就無法察覺明顯的失真；當PSNR為無窮大時，重構圖像與原始圖像相比無任何失真。表4為同態解密前重構密文圖像、明文圖像與同態解密后重構明文圖像的PSNR和信息熵。同態解密前的重構密文圖像是含有噪聲的置亂圖像，與原始圖像相比PSNR < 35 dB，無法通過人眼識別圖像的內容。對其恢復置亂后得到同態解密前重構的明文圖像，由于仍含有大量噪聲其PSNR增幅不大，信息熵保持不變。同態解密后重構明文圖像與原始圖像相比PSNR為無窮大，信息熵有明顯的減小且與原始圖像的信息熵相等，表明該圖像與原始圖像完全相同無任何失真。

表4 同態解密前后重構圖像質量

4.3 可分離性

在RDH-ED中，可分離性是一種重要的實用性指標，即信息的提取均可在圖像解密前后完成。本文算法的可分離性是指額外信息均可在圖像重構前后提取，該方案組合使用兩種不同嵌入方法實現了信息提取的可分離性，一種是多項式嵌入，支持在圖像重構之后提取額外信息；另一種是同態嵌入，支持在圖像重構前提取額外信息。在圖像重構前，接收方根據信息隱藏密鑰可以直接提取同態嵌入的額外信息且不影響原始圖像的重構；在圖像重構后，接收方根據信息隱藏密鑰可以提取多項式嵌入的額外信息，但是含有噪聲，需要利用輔助信息同態解密才能消除噪聲。

4.4 安全性分析

RDH-ED將密文圖像作為載體，嵌入信息后的圖像仍為密文圖像。然而，嵌入操作可能會對密文圖像進行修改導致其統計特征改變，破壞原有加密算法的強度與安全性，威脅含密圖像的安全性。多項式嵌入算法是在圖像分割過程中，利用加密后的額外信息替換多項式中隨機系數的方法嵌入的，由于加密后的額外信息與隨機數都服從均勻分布，因此，不會降低秘密共享的安全強度，保證了載體圖像的安全；同態嵌入算法是針對分割后的任意影子圖像，利用秘密共享的加法同態屬性嵌入信息的，經同態操作后得到的密文仍是安全的密文，保證了嵌入過程不會削弱秘密共享的安全強度。

4.4.1 相鄰像素相關性分析

自然圖像加密后相鄰像素間的相關性極小，其期望值為零。嵌入過程可能會修改密文數據導致其相關性增強。以Lena圖像為例，經兩次嵌入后從生成的多幅含密影子圖像中隨機選取一幅，分別從水平、垂直、對角45°和135°4個方向計算嵌入前后3000對隨機采樣的相鄰像素相關性，并繪制相關性散點圖，如圖6所示，其中Rxy_h,Rxy_v,Rxy_d45,Rxy_d135分別表示水平、垂直、對角45°和對角135°的相關系數。根據像素點的分布情況可知，嵌入后的密文圖像相鄰像素相關性仍保持不相關的狀態，表明嵌入過程沒有使密文數據的相關性增強。

圖6 額外信息嵌入前后密文圖像不同方向相關性對比

4.4.2 明密文敏感性及信息熵

圖像安全加密理論[24]要求加密圖像必須對明文和密鑰極端敏感，通過計算像素數改變率(Number of Pixels Change Rate, NPCR)和歸一化平均變化強度(Unified Average Changing Intensity,UACI)并結合圖像的信息熵，分析兩種嵌入算法生成的密文對明文及密鑰的敏感性。當圖像加密方法足夠安全時，對位深為8位的灰度圖像，NPCR和UACI的期望值分別為99.6094%和33.4635%，其信息熵的極限為8。

多項式嵌入是在秘密共享的過程中進行的，同態嵌入也是利用密文數據的同態運算，故將載體圖像經過兩次嵌入后生成含密影子圖像的過程可分別視為新的加密過程，通過對載體圖像的細微改變并分別進行兩次嵌入以生成不同的影子圖像。表5分析了信息嵌入前后影子圖像的安全性，其中，未嵌入信息的影子圖像是通過秘密共享方案分割得到的，其信息熵接近極限熵，表明經秘密共享分割的圖像是安全的。從實驗數據來看，經多項式嵌入后生成的影子圖像信息熵約為7.9985，接近密文圖像熵的極限。此外，NPCR均大于99.5%，UACI也均高達33%，表明含有額外信息的影子圖像與未嵌入信息的影子圖像具有相同的加密強度。因此，多項式嵌入后的影子圖像是安全的。同態嵌入算法將額外信息變換后與影子圖像相加得到新的影子圖像，與未嵌入信息的影子圖像相比，NPCR與UACI同樣高于99.5%和33%，信息熵較之前平均增加了0.000075。因此，同態嵌入后的影子圖像也是安全的。

表5 信息嵌入前后含密影子圖像安全性分析

表6從算法框架，加密方式、時間復雜度、密文擴展率、可分離性以及是否支持多用戶等多個角度與不同算法的特性進行了對比。在時間復雜度方面，所提算法與基于流密碼的RDH-ED具有相同的時間復雜度，且低于基于公鑰密碼的方案；在密文擴展方面，基于公鑰加密的RDH-ED產生的密文擴展較大，秘密共享加密產生的密文擴展較小，一般取決于門限值(k, n)，文獻[17,20]算法的密文擴展均為n。本文算法通過對影子圖像的壓縮減小了密文擴展，使其由門限值(k, n)與壓縮系數w共同決定。假設門限值為(3, 4)，壓縮系數為2，文獻[17,20]算法的密文擴展為4，而本文算法的密文擴展為2。在實用性方面，本文算法不僅支持多用戶環境而且具有可分離性，能夠滿足不同用戶和不同應用場景下的大容量可逆嵌入需求。

表6 不同算法特性對比

5 結束語

本文將圖像秘密共享方案與密文域可逆信息隱藏相結合，發揮秘密共享在多用戶場景下的容災特性以增強圖像安全性，并針對RDH-ED多用戶場景下嵌入容量低，可分離性差等問題，提出了兩種嵌入算法，一是多項式嵌入算法，利用秘密共享的冗余嵌入額外信息，不僅能夠增強載體圖像與額外信息的安全性，還能使秘密信息的傳輸更加隱蔽；二是同態嵌入算法，利用秘密共享的加法同態特性在影子圖像中嵌入額外信息以滿足多用戶標記與管理密文數據的需求。最后，通過理論分析與仿真實驗驗證可得出以下結論：(1)在不同門限方案和影子圖像壓縮率條件下，均可實現大容量的可逆嵌入；(2)通過組合兩種嵌入方法實現了算法的可分離性；(3)將圖像秘密共享與密文域信息隱藏相結合，更好地發揮了圖像秘密共享技術的門限優勢，不僅增強了密文圖像與嵌入信息的容錯性與抗災性，還實現了多用戶場景下對密文數據的管理、標記與檢索。在下一步的研究中，一是解決輔助信息占用嵌入空間的問題，進一步提升嵌入容量；二是設計門限方案可動態改變的RDH-ED，提升算法的靈活性。