一種基于二維細胞自動機的秘密圖像共享方案

摘 要：基于二維細胞自動機提出了一種新的秘密圖像共享方案，該方案把秘密圖像作為細胞自動機的一個初始配置，通過利用二維n階可逆存貯細胞自動機進行分解成n為份的影子圖像，再利用其逆細胞自動機進行反向迭代來重構所共享的秘密圖像。分析表明，該方案實現簡單，在計算上是安全的，并且是一個完備的(n，n)方案。

關鍵詞：秘密圖像；影子圖像；二維細胞自動機；秘密圖像共享

中圖分類號：TN918.1 文獻標識碼：B

文章編號：1004373X(2008)0309103

A Secret Image Sharing Scheme Based on Bidimensional Cellular Automata

WANG Liqin1，CHEN Guiqiang2，3

(1.Zhangjiakou Voca.Colle.of Tech.，Zhangjiakou，075000，China;2.Colle.of Comput.Sci.and Tech.，Beijing Univ.of Tech.，Beijing，100022，China;

3.Hebei North Univ.，Zhangjiakou，075000，China)

Abstract：Based on the bidimensional cellular automata，a new secret image sharing scheme is proposed in this paper.The secret image is considered as one of the initial configurations of the bidimensional cellular automata，The n shadow images of the secret image are made by the bidimensional reversible cellular automata with memory of order n.The backward iteration of the bidimensional reversible cellular automata with memory of order n is used to recover the shared secret image.Analysis show the proposed scheme can be implemented easily，and is a computationally secure and perfect (n，n) scheme.

Keywords：secret image；shadow image；the bidimensional cellular automata；secret image sharing

1 引 言

秘密圖像共享是現代密碼學的一個重要部分，已被廣泛應用于信息安全中。Shamir[1]和Blakley[2]最早提出秘密共享的概念，并分別給出了一個(k，n)門限秘密共享方案。Shamir的門限方案是一個完備的秘密共享方案[3]，即在訪問結構上的任意合格子集都可以恢復所共享的秘密，而任意不合格子集都得不到關于所共享秘密的任何信息。Naor和Shamir提出了可視密碼學[3](Visual Cryptography，VC)的概念，后來基于灰度和彩色圖像的VC方案都被構造出來。雖然VC具有一些優點，但由于VC本身的條件所限，共享的圖像恢復之后所能達到的視覺效果和原始圖像有較大差距，因此在一些對圖像質量有較高要求的場合，VC就不太適用了。Chang和Lin[4—6]提出的共享彩色圖像的(t，n)門限圖像隱藏方案，Lukac和Plataniotis[7]提出的彩色秘密圖像共享的方案，雖然其恢復圖像可以達到和原圖一樣，但由于其利用了(2，2)VC方案的思想，故生成的影子秘密圖像是原圖大小的4倍，呂超等人[8]提出的一種圖像秘密共享方案能夠較好地保證恢復圖像的質量，生成的影子秘密圖像和原圖的大小也相同。然而，他還是有損于圖像的質量而不是完備的方案，且他們的方案需要應用Lagrange插值操作，當n很大時(其中n代表共享的參與者數量)，其計算量仍然比較大。細胞自動機的概念最早是由Von Neumann于1948年提出的[8]。在1985年美洲密碼學年會上，Wolfram首次提出了將細胞自動機的初始狀態作為密鑰，使用細胞自動機前向迭代產生的偽隨機序列作為序列密碼[9]，從而開創了細胞自動機在密碼學領域的應用研究。細胞自動機具有組成單元的簡單規則性、單元之間作用的局部互連性和信息處理的高度并行性，并表現出復雜的全局特性等特點[10]，使得他尤其適合密碼學中的應用。本文作者的創新點是基于一個n階二維可逆細胞自動機RCAM提出了一個新的秘密圖像共享方案。分析表明，本文方案是一個完備的(n，n)方案，在計算上是安全的，也是一個簡單實用的方案，易于在軟件和硬件上得以實現。

2 二維細胞自動機原理

二維細胞自動機(Bidimensional cellular automata)是由r×s矩陣的細胞單元構成的一種離散的動態系統[9]，簡稱為CA。令代表CA的第i行、第j列的細胞(其中0≤i≤r-1，0≤j≤s-1)，他具有一定狀態aij∈Zc={0，1，…，c-1}(其中Zc是細胞的狀態空間)。令C(t)表示CA的所有細胞在t時刻的狀態即C(t)=(a(t)ij)，在t+1時刻，細胞的轉移狀態a(t+1)ij由局部轉移函數f 和該單元鄰域內9個細胞單元在t時刻的狀態來確定。令Vij={，，，，，，，，}表示細胞鄰域內的9個細胞單元，其在t時刻的狀態為:

V(t)ij={a(t)i－1，j－1，a(t)i－1，j，a(t)i－1，j+1，a(t)i，j－1，a(t)i，j，a(t)i，j+1，

a(t)i+1，j－1，a(t)i+1，j，a(t)i+1，j+1}

因此，CA的局部轉移函數f具有以下形式：

當t=0時，C(0)表示CA的初始配置，則{C(0)，C(1)，…，C(k)}為CA的k階進化序列。若令C表示CA所有可能的狀態集合，則|C|=2r×s。在CA中的細胞數目是有限的，為了保證CA具有良好的動態性必須限定一些邊界條件。在本文中，考慮周期邊界條件，即如果i≡u(mod r)和j≡v(mod s)，那么a(t)ij=a(t)uv。CA進化過程中的下一時刻的狀態由一個線性全局轉移函數Φ：C→C來產生，即C(t+1)=Φ(C(t))，如果Φ是一個雙射函數，那么他有逆函數Φ-1，存在另一個細胞自動機以Φ-1為全局函數[11]，他稱為CA的逆，記為RCA。當一個CA存在逆，那么他是可逆的，即他可以反向進化。

一般情況下，在CA中每個細胞在t+1時刻的狀態依賴于他鄰域內細胞在t時刻的狀態。若CA中每個細胞在t+1時刻的狀態不僅跟某些細胞在t時刻的狀態有關，而且還跟其他一些細胞在t-1，t-2等時刻的狀態有關，這種細胞自動機稱為存貯細胞自動機(Cellular Automata with Memeory，CAM)[11]。一個n階CAM是每次進化都依靠t，t-1，t-2，…，t-n-1時刻的狀態。因此n階CAM的局部轉移函數具有以下形式：

其中fm (1≤m≤n)是n個CA的局部轉移函數，在這種情況下，n階CAM的初始配置具有n個CA的初始配置即C(0)，C(1)，…，C(n-1)。

定義[12]:如果fn(V(t－n+1)ij)=a(t－n+1)ij，那么由式(2)給出的n階RCAM是一個可逆的細胞自動機，并具有以下局部轉移函數:

他的逆仍然為一個n階RCAM，也具有以下局部轉移函數:

基于定義給出的RCAM，我們提出了一個新的圖像共享方案，他可以對黑白圖像、灰色圖像、彩色圖像進行共享。

3 秘密圖像共享方案

3.1 系統參數

假設系統中有n個參與者，他們構成的集合記為Q={P1，P2，…，Pn}，D(DQ)表示一個秘密圖像分發者，在本文中，假設秘密圖像分發者是一個可信的第三方。令I表示共享的秘密圖像，具有r×s個象素，每個象素的具有c個象素值(c=2b且b的取值為{1，8，24})。把圖像I看作矩陣M，矩陣元素的系數(i，j)代表象素的位置，矩陣M的元素值a代表圖像I的象素值。因此，矩陣M看作是n階RCAM的初始配置之一，n階RCAM的局部狀態轉換函數是式(3)給出的形式。

3.2 秘密圖像的分發

秘密圖像分發者D執行以下步驟實現秘密圖像分發:

(1) 秘密圖像分發者D構造在狀態空間Zc上的n階RACM，c是圖像I的色彩值(即c=2b且b的取值為{1，8，24})，并定義式(3)中的局部狀態轉移函數fm，即：

其中λα，β∈Zc是隨機選擇，1≤m≤n－1。

(2) 秘密圖像分發者D構造的n階RACM的初始狀態，在狀態空間Zc上隨機選擇n-1個r×s大小矩陣C(0)，C(1)，…，C(n-2)和C(n-1)=M作為n階RACM的初始狀態n個CA的初始配置。

(3) 秘密圖像分發者D隨機選擇一個整數k，從n階RACM的初始配置C(0)，C(1)，…，C(n-2)，C(n-1)計算所構造n階RCAM的(n+k+1)階進化序列：C(n)，C(n+1)，…，C(n+k+1)，…，C(2n+k)。

(4) 令最后n個配置作為參與者的份額，即Y1=C(n+k+1)，Y2= C(n+k+2)，…，Yn=C(2n+k)。

(5) 將每個份額Yi通過安全信道發送給參與者Pi(1≤i≤n)。

3.3 秘密圖像的重構

秘密圖像的重構需要所有參與者提供的n個連續的份額，即Y1=C(n+k+1)，Y2= C(n+k+2)，…，Yn=C(2n+k)，令(0)=C(2n+k)，(1)=C(2n+k－1)，…，(n－1)=C(n+k+1)作為n階逆RCAM的初始配置，利用其局部狀態轉換函數式(4)進行k+2次進化(迭代)得到的配置(n+k+1)=C(n－1)=M，即原始秘密圖像得以重構。

4 實 例

假設參與者數n=3，原始秘密圖像I表如圖1所示lena，具有120×120個象素，每個象素的具有256個象素值(即c=2b=256且b的取值為8)。隨機選擇k=3，經過n+k+1=7次進化將最后的3個配置如圖1的影子圖像1、影子圖像2、影子圖像3分配給參與者。在重構過程中，必須所有的參與者提供其影子圖像，運用n階二維可逆細胞自動機RCAM能恢復出和原始秘密圖像完全一致的秘密圖像。

圖1 實驗結果

5 安全性分析

在本文方案中構造了一個n階二維可逆細胞自動機RCAM，只要知道n個連續的配置C(t)，C(t-1)，…，C(t-n+2)，C(t-n+1)，就可以計算出C(t+1)，但如果僅知道其中n-1個或更少的配置，將無法計算出C(t+1)。不失一般性，這里假設僅知道C(t)，C(t-1)，…，C(t-n+2)，不知道配置C(t-n+1)，即不知道a( t - k)，a(t－n+1)ij，0≤i≤r－1，0≤j≤s－1的值，由上面可知，n階二維可逆細胞自動機RCAM是根據以下局部轉移函數反向進化：

這樣重構者就必須解r×s個線性方程組成的如下方程組：

這里bij=∑n－1m=1fn－m(V(t－m+1)ij)是已知，但還有2×r×s個未知量a(t+1)ij，a(t－n+1)ij，(0≤i≤r－1，0≤j≤s－1)，顯然未知量的個數大于方程的個數，即由方程組無法確定這些未知數，從而得不到關于C(t+1)={a(t+1)ij}，(0≤i≤r－1，0≤j≤s－1)的任何信息。由上面的分析可知，任意連續的n個份額可以重構所共享秘密圖像，而n-1個或更少的份額得不到關于所共享秘密圖像的任何信息。因此，本文方案是一個計算上安全的方案，并且是一個完備的方案。

6 結 語

本文作者的創新點是基于一個n階二維可逆細胞自動機RCAM提出了一個新的秘密圖像共享方案。該方案把秘密圖像作為細胞自動機的一個初始配置，通過利用二維n階可逆存貯細胞自動機進行分解成n份完備的影子圖像，再利用其逆n階二維細胞自動機RCAM進行反向迭代來重構所共享的秘密圖像。在秘密圖像分發和秘密圖像重構過程中，僅需簡單的迭代操作，因此本文方案實現簡單。另外，在本文方案中的訪問結構與一般的(k，n)門限訪問結構不同，其包含的合格的集合是全部參與者的連續全集，所以是一個(n，n)方案。分析表明，本方案是一個計算上安全的方案，并且是一個完備的秘密圖像(n，n)共享方案。

參考文獻

[1]Maor M Shamir.Visual Cryptography[J].Lecture Notes in Computer Science，1995:1—12.

[2]Blundo C，De Santis A，Naor M.Visual Cryptography for Grey Level Images[J].Information Processing Letters，2000，75(6):255—259.

[3]Hou Y C.Visual Cryptography for Color Images[J].Pattern Recognition，2003，36(7):1 619—1 629.

[4]Chang C C，Lin I C.A New (t，n) Threshold Image Hiding Scheme for Sharing a Secret Color Image[A].In: Proceedings of the International Conference on Communication Technology[C].2003，1:196—202.

[5]Chang C C，Chuang J C.An Image Intellectual Property Protection Scheme For Gray Level Images Using Visual Secret Sharing Strategy [J].Pattern Recognition Letters，2002，23(8):931—941.

[6]Yang C C，Chang T Y，Hwang M S.A(t，n) Multi—secret Sharing Scheme[J].Applied Mathematics and Computations，2004，151(2):483—490.

[7]Lukac R，Plataniotis K N.Color Image Secret Sharing[J].Electronics Letters，2004，40(9):529—531.

[8]呂超，余梅生，劉艷芳.基于拉格朗日插值多項式的秘密圖像共享方案[J].華中科技大學學報，2005，33(12):285—289.

[9]Wolfram S.Cryptography with Cellular Automata[A].Proc Advances in Cryptology (Crypto′85)[C].Lecture Notes in Computer Sciences，Berlin:Srpinger Verlag，1986，429—432.

[10]Wolfram S.Origins of Randomness in Physical System [J].Physical Review Letters，1985，55(5):449—452.

[11]Toffoli T，Margolus N.Invertible Cellular Automata:Areview.Physica D，1990:229—253.

[12]Martin del Rey A，Pereira Mateus J，Rodriguez Sanchez G.A Secret Sharing Scheme Based on Cellular Automata[J].Applied Mathematics and Computation，2005，170(2):1 356—1 364.

[13]潘志君，嚴壯志，張猛.一種基于元胞自動機的圖像拼接方法[J].微計算機信息，2006，22(30)：245—247.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。