李艷玲，上官晉太，賈 靜

（1.長治學(xué)院 計算機(jī)系，山西 長治 046011；2.中北大學(xué) 計算機(jī)與控制工程學(xué)院，山西 太原 030051）

0 引言

同圖構(gòu)的研究已有100多年的歷史，最早是化學(xué)家研究同分異構(gòu)體.計算機(jī)科學(xué)中也研究圖同構(gòu)問題，主要從密碼學(xué)的角度研究零知識證明.因此圖的同構(gòu)問題具有廣泛的應(yīng)用背景，特別是系統(tǒng)建模時，如果需建模型與已有模型同構(gòu)，則不需要新建模型，這將大大節(jié)省求解問題的時間.

但要判定兩個圖同構(gòu)卻并不容易.因為是否存在多項式計算時間的算法，即復(fù)雜性屬于NP類的算法，目前還不知道.多數(shù)的科學(xué)工作者認(rèn)為圖的同構(gòu)判定問題屬NP 完全性問題，這一類問題應(yīng)該存在計算時間多項式有界的算法，即計算機(jī)上可行的算法.盡管目前尚未找到.不過它們具有下列重要的性質(zhì)：只要找到其中一個問題的多項式計算時間算法，其它幾百個同類問題就都能找到時間多項式有界的算法，因此研究圖同構(gòu)問題具有無比重要的理論意義和實際應(yīng)用意義.判定圖形同構(gòu)，在信息科技突飛猛進(jìn)以及網(wǎng)絡(luò)日漸普及的今天，已經(jīng)不僅僅是數(shù)學(xué)領(lǐng)域或工程技術(shù)領(lǐng)域的純理論問題，而是具有極高現(xiàn)實價值的實踐問題.可以說，只要能用圖形描述的識別問題都可使用同構(gòu)判定算法來實現(xiàn).如用計算機(jī)實現(xiàn)數(shù)字、漢字識別，尤其是采用同構(gòu)策略識別甲骨文，可以大大地減少誤判的情況，同時也可以識別標(biāo)準(zhǔn)數(shù)據(jù)庫中所有的同構(gòu)字；如數(shù)據(jù)中心的網(wǎng)絡(luò)故障檢測，通過比較尋找故障結(jié)構(gòu)圖和物理拓?fù)鋱D的不同之處，從而排查出現(xiàn)故障部分；如網(wǎng)上電子支付的身份認(rèn)證和數(shù)字簽名，判斷登錄的人和本人是否為同一人.這些都可以轉(zhuǎn)化為用計算機(jī)判定圖形的同構(gòu)問題.

1 零知識認(rèn)證協(xié)議

1.1 零知識證明模型

20 世紀(jì)80年代初，O.Goldreich，S.Micali和A.Wigderson提出了零知識證明的概念，研究了零知識證明協(xié)議與密碼學(xué)及數(shù)學(xué)的關(guān)系［1］.所謂零知識認(rèn)證協(xié)議，是指證明者P向驗證者V 證明他知道某個秘密，或擁有某種身份，證明過程中還不讓驗證者得到任何有用的信息.尤其是數(shù)學(xué)家，要搶奪定理的發(fā)明權(quán).他希望其他數(shù)學(xué)家承認(rèn)他的確知道某個定理的證明，又不希望透露任何證明過程.

關(guān)于零知識認(rèn)證最經(jīng)典的模型是阿里巴巴洞穴模型，如圖1 所示.

洞穴的C和D之間存在一個密門，只有知道咒語的人才能打開.P 想對V 證明他知道咒語，但P不想對V 泄露咒語.證明過程如下［2-3］：

Step1.首先V 站在A點(diǎn)，P走到C點(diǎn)或者D點(diǎn)；

Step2.V 走到B點(diǎn)，然后V 隨機(jī)要求P從左通道或者右通道出來；

Step3.P從V 要求的通道出來，如果需要就用咒語打開密門；

Step4.P和V 重復(fù)第1步至第3步n次.

圖1 零知識洞穴模型Fig.1 Zero-know ledge cave model

如果P知道密門咒語，就能正確地從V 要求的通道出來.在協(xié)議的每一輪中，如果P 不知道洞穴密門的咒語，那么他只能從進(jìn)去的路出來，也就是P有1／2的概率欺騙V.經(jīng)過n輪后，P都猜中的概率是1／2n.當(dāng)n很大的情況下，V 有理由相信P一定知道洞穴密門的咒語.

V 相信P知道咒語，但V 并不知道咒語本身是什么，所以這個協(xié)議是零知識證明協(xié)議，因為其滿足3個條件：

1）完備性.如果證明是成功的，V 以一個大的概率接受P的結(jié)論.

2）可靠性.如果證明不成功，V 以一個大的概率拒絕P的結(jié)論.

3）零知識性.證明過程中，無論V 采取什么手段，只能接收P 知道秘密的結(jié)論，而無法獲取秘密本身的任何信息.

1.2 基本的零知識證明協(xié)議

零知識證明過程需要使用分割選擇協(xié)議，假設(shè)P知道一個難題的解法，基本的零知識協(xié)議如下［4］：

Step1.P用他所知道的信息的特點(diǎn)和隨機(jī)數(shù)將這個難題轉(zhuǎn)變成另一個和原難題同構(gòu)的新難題，然后用自己的隨機(jī)數(shù)特點(diǎn)求解新難題的解.

Step2.P利用未承諾方案提交這個新難題的解法.

Step3.P向V 透露這個新難題，但V 不能用這個新難題得到原難題或其解法的任何信息.

Step4.V 可以要求P 提交新舊難題同構(gòu)的證明過程，或公開P 在第2步中提交的解法并證明其是新難題的解.

Step5.P同意.

Step6.P和V 重復(fù)第1步至第5步n次.

新難題和隨機(jī)數(shù)要保證，無論V 采取什么方法，都得不到原難題解法的任何信息.

2 圖同構(gòu)的零知識證明協(xié)議

2.1 圖同構(gòu)的概念

定義1 假設(shè)有兩個無向（或有向）圖G1＝〈V1，E1〉和G2＝〈V2，E2〉，若存在雙射函數(shù)f：V1→V2，使得?vi，vj∈V1，（vi，vj）∈E1當(dāng)且僅當(dāng)（f（vi），f（vj））∈E2，并 且（vi，vj）與（f（vi），f（vj））的重數(shù)相同，則稱G1和G2是同構(gòu)的，記作G1≌G2.

從定義1可以看出，所謂圖同構(gòu)，就是兩個圖能夠完全重合，即：若圖的結(jié)點(diǎn)可以任意挪動位置，而邊是完全彈性的，只要在不拉斷的條件下，一個圖可以變形為另一個圖，那么這兩個圖就是同構(gòu)的.如圖2 中的兩個圖G1和G2是同構(gòu)的，實際上是同一個圖.

圖2 圖G1和圖G2Fig.2 Figue G1and G2

圖G1的鄰接矩陣

圖G2的鄰接矩陣

通過MATLAB 程序判斷G1的鄰接矩陣V（G1）是否可以經(jīng)過有限次的初等變換得到G2的鄰接矩陣V（G2），即

式中：Pi是單位矩陣的行（或列）對換所得到的初等矩陣.

2.2 設(shè)計零知識的證明協(xié)議

假設(shè)證明者P知道G1和G2是同構(gòu)的，同構(gòu)置換為f，即（A，B，C，D，E）＝f（A，B，C，D，E）.P用協(xié)議證明G1和G2是同構(gòu)的，執(zhí)行協(xié)議的結(jié)果使驗證者V 相信這兩個圖的確是同構(gòu)的，但V并不知道頂點(diǎn)如何對應(yīng).交互式零知識證明協(xié)議如下［5］：

Step1.P隨機(jī)地選擇置換φ，將圖G1轉(zhuǎn)換為圖H，即H＝φ（G1），并將H發(fā)送給V.

Step2.V 隨機(jī)選擇α∈｛0，1｝，發(fā)送給P.

Step3.P判斷α是否屬于｛0，1｝，如果不屬于，則拒絕.

1）如果α＝0，記π＝φ-1；

2）如果α＝1，記π＝φ-1f；

3）P發(fā)送π給V.

Step4.V 驗證H 在π的變換下是否等于Gα，即Gα＝π（H）是否成立，若不成立就拒絕接受P的宣稱；若是，則接受.

協(xié)議重復(fù)執(zhí)行n次以后，V 以接近于1的概率接受P的證明.協(xié)議的每一輪中P 都會產(chǎn)生一個新圖H，協(xié)議運(yùn)行n輪結(jié)束以后，V 只能得到圖G1或圖G2的一些隨機(jī)同構(gòu)拷貝，所以此協(xié)議是零知識的.

3 圖同構(gòu)的零知識證明應(yīng)用

3.1 算法實例分析

設(shè)有任意個符號構(gòu)成字母表A，這里字母表只考慮有限集.A＊的任意一個子集稱為A上的一個語言.如漢語是由基本漢字構(gòu)成的漢字區(qū)位碼表AC上的語言，英語是由｛A，B，C，…，X，Y，Z，a，b，c，…，x，y，z｝52個字符構(gòu)成的字母表AE上的語言.

由字母表A中有限個字母組成的序列稱為字母表A上的串，串ω中所含的字母個數(shù)稱為串的長度，記作｜ω｜.如是A上的串，且｜ω｜＝k.將這個串關(guān)聯(lián)于整數(shù)x，.以后可以用這個數(shù)計算該串，使得計算機(jī)可以像處理數(shù)值一樣來處理A上的語言.

給定字母表A，Ak＝｛〈ak，ak-1，…，a2，a1〉｜ai∈A，k≥i｝［7］.

假設(shè)P和A 要進(jìn)行聯(lián)絡(luò)，證明者P要向驗證者V 證明他確實合法地持有該秘密組織的某份文件，但又不能直接將文件給V 看，因為如果在V沒有文件的情況下，就會發(fā)生信息泄漏.文件內(nèi)容如下：“茲定于2012年8月25日在西部進(jìn)行有計劃的生物武器的秘密投放”，則零知識證明協(xié)議按如下順序執(zhí)行［8］：

1）把文件的每一個字符作為數(shù)組X（n）＝X（32）中的一個元素；

2）構(gòu)造和原文件同構(gòu)的子文件，生成一個隨機(jī)數(shù)組K（m）＝k（10）＝k（2，7，10，31，16，12，23，18，29，25）（m≤n）；

3）計算字符串函數(shù)z＝f（X（K（1）），X（K（2）），…，X（K（9）），X（K（10）））＝“定2月放部5生行密武”；

4）計算和字符串關(guān)聯(lián)的整數(shù)x，每個漢字取與其關(guān)聯(lián)的唯一的區(qū)位碼，并作模n運(yùn)算（n不取素數(shù)）［9］：

xmod 10 000＝（2 208×10 0009+2×10 0008+5 234×10 0007+2 337×10 0006+1 831×10 0005+5×10 0004+4 190×10 0003+4 848×10 0002+3 560×101+4 668）mod 10 000＝768.

5）將計算結(jié)果768，K（m）和n一起發(fā)送給V；

6）V 根據(jù)他持有的文件和P發(fā)送的數(shù)據(jù)進(jìn)行相同的計算，驗證P 是否擁有文件，但V 如果沒有持有該文件，他不能從這些數(shù)據(jù)中得到任何有關(guān)的文件信息.

3.2 算法零知識性分析

該算法是零知識的，其安全性體現(xiàn)在：

1）如果V 持有該份文件，他能夠通過K（m）和n驗證計算結(jié)果的正確性，否則V 不能得到有關(guān)秘密文件的任何信息.因為n不是素數(shù)，根據(jù)素數(shù)理論，ax＝b（modn）無解，所以V 從結(jié)果768求出x是不可能的［10］.

2）傳統(tǒng)的協(xié)議執(zhí)行一輪，P 有1／2的概率欺騙V，所以需執(zhí)行多輪.但是用模運(yùn)算執(zhí)行一輪的欺騙概率是1／n，所以滿足安全性.

3）由于是用隨機(jī)數(shù)組生成的子文件進(jìn)行驗證，所以占用的內(nèi)存空間小，計算量小，運(yùn)算速度快.

4 結(jié)束語

由于零知識證明的保密性，決定了它在信息安全方面的巨大應(yīng)用價值.本文利用零知識證明協(xié)議向?qū)Ψ阶C明兩個圖是同構(gòu)的，并設(shè)計了字符文字信息的零知識認(rèn)證協(xié)議.該協(xié)議在密碼登錄系統(tǒng)中能識別登錄者，但又不會泄露他的身份信息；同樣對于電子投票，投票是匿名的，這個票是無法追查的，但還要確認(rèn)是自己投出的，而不是別人代替的，既確認(rèn)是你，同時又不知道你是誰，不可偽造，不可追查，所以在信息技術(shù)突飛猛進(jìn)的今天，網(wǎng)絡(luò)安全需要更有效的協(xié)議.

［1］Goldreich O，Micali S，Wigderson A.Proofs that yield nothing but their validity and a methodology of cryptographic protocol design［C］.27 Thannual Sysposium on.FOCS，1986：174-187.

［2］李琳，岳建華.基于零知識證明的匿名身份認(rèn)證機(jī)制［J］.計算機(jī)科學(xué)，2013，40（12）：197-214.Li Lin，Yue Jianhua.Anonymous authentication mechanisms based on zero-knowledge proof［J］.Computer Science，2013，40（12）：197-214.（in Chinese）

［3］趙建.新的可重置的單輪零知識證明［J］.計算機(jī)應(yīng)用，2013，33（S1）：151-153.Zhao Jian.New kind of one-round resettable zeroknowledge proofs［J］.Journal of Computer Applications，2013，33（S1）：151-153.（in Chinese）

［4］郭寶安，盧開澄.關(guān)于圖的非同構(gòu)問題零知識交互證明協(xié)議［J］.軟件學(xué)報，1997，8（7）：481-485.Guo Baoan，Lu Kaicheng.The zero-knowledge proof protocol of the nonisomorphism of graphs［J］.Journal of Software，1997，8（7）：481-485.（in Chinese）

［5］朱洪武.基于零知識證明的圖論問題和網(wǎng)絡(luò)安全的研究［D］.成都：成都理工大學(xué)，2007.

［6］Kenneth H.Rosen.離散數(shù)學(xué)及其應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2011.

［7］王宏俊，丁群.RSA 公鑰算法研究與快速模冪運(yùn)算設(shè)計［J］.黑龍江大學(xué)工程學(xué)報，2013，4（2）：83-88.Wang Hongjun，Ding Qun.RSA public key alglrithm and design of fast modular exponentiation operation［J］.Journal of Heilongjiang University，2013，4（2）：83-88.（in Chinese）

［8］李順東，覃征，竇家維.一種零知識證明算法及其應(yīng)用［J］.西安交通大學(xué)學(xué)報，2001，35（12）：1252-1254.Li Shundong，Qin Zheng，Dou Jiawei.Kind of zero knowledge proof algorithm and its use［J］.Journal of Xi＇an Jiaotong University，2001，35（12）：1252-1254.（in Chinese）

［9］許鑫，李順東.大整數(shù)取模的快速運(yùn)算［J］.計算機(jī)工程與應(yīng)用，2013（6）：1-6.Xu Xin，Li Shundong.Fast algorithm for modular operation，computer engineering and applications［J］.Computer Engineering and Applications，2013（6）：1-6.（in Chinese）

［10］楊剛，陳越，李超零，等.一種基于AES和模運(yùn)算的密文索引方案［J］.計算機(jī)應(yīng)用研究，2012，29（1）：72-75.Yang Gang，Chen Yue，Li Chaoling，et al.A cryptograph index scheme based on AES and modular arithmetic［J］.Application Research of Computers，2012，29（1）：72-75.（in Chinese）