趙梅梅, 姚 兵
(1. 甘肅農(nóng)業(yè)大學(xué) 理學(xué)院, 甘肅 蘭州 730070; 2. 西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070)
眾所周知,密碼保護(hù)系統(tǒng)的安全性取決于多個(gè)因素,公鑰和私鑰在密碼學(xué)中發(fā)揮著重要作用。密碼問(wèn)題的經(jīng)典研究可以追溯到40多年前,一些學(xué)者對(duì)現(xiàn)有的圖形密碼做了深入的研究[1-3]。圖形密碼是不同于文本密碼的一種新型密碼,圖形密碼易于用戶記憶,而且很難被攻擊者破解?,F(xiàn)有的圖形密碼缺點(diǎn)是圖片頻繁更改會(huì)占用計(jì)算機(jī)龐大的空間,用戶需要學(xué)習(xí)更多的相關(guān)知識(shí)并具有良好的記憶,不支持更多的個(gè)性化創(chuàng)意和個(gè)性化的圖形密碼。為了解決圖形密碼的缺點(diǎn),王宏宇等[4-6]提出了拓?fù)鋱D形密碼, 其思想是“拓?fù)浣Y(jié)構(gòu)+數(shù)論”。 拓?fù)鋱D形密碼是由圖論中的拓?fù)浣Y(jié)構(gòu)和著色(標(biāo)號(hào))組成的。由于拓?fù)鋱D形密碼通過(guò)代數(shù)矩陣保存在計(jì)算機(jī)中[7],這就使得拓?fù)鋱D形密碼比現(xiàn)有的圖形密碼占用計(jì)算機(jī)的空間小,關(guān)于數(shù)矩陣的算法是多形式的,因此,可以快速實(shí)現(xiàn)拓?fù)鋱D形密碼。更為重要的是,拓?fù)鋱D形密碼可以用來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行整體加密,加之大量的NP-問(wèn)題和猜想存在于拓?fù)鋱D形密碼中,使得拓?fù)鋱D形密碼具有抗量子計(jì)算的能力[8]。
云計(jì)算引入“同態(tài)加密”技術(shù)提供了一種對(duì)加密數(shù)據(jù)進(jìn)行處理的功能[9],提高了數(shù)據(jù)的安全隱私保護(hù),實(shí)現(xiàn)“數(shù)據(jù)不可見(jiàn)”性。同態(tài)加密技術(shù)可以應(yīng)用在很多領(lǐng)域,例如,在案件調(diào)查過(guò)程中,警察可以搜索嫌犯的行程、財(cái)務(wù)記錄,以及調(diào)查通訊和郵件記錄,且不會(huì)暴露嫌犯的數(shù)據(jù)。醫(yī)學(xué)研究人員可以根據(jù)數(shù)百萬(wàn)患者的記錄,來(lái)識(shí)別基于人口結(jié)構(gòu)和地理位置的疾病趨勢(shì)。政府和商業(yè)機(jī)構(gòu)能夠很好地對(duì)財(cái)務(wù)數(shù)據(jù)進(jìn)行分析和處理。值得注意的是,同態(tài)加密技術(shù)也可以在原有基礎(chǔ)上使用區(qū)塊鏈技術(shù),且不會(huì)對(duì)區(qū)塊鏈屬性造成任何重大的改變。圖群整體加密技術(shù)在公有區(qū)塊鏈上進(jìn)行加密,隨時(shí)加密公用區(qū)塊鏈上的數(shù)據(jù)。
本文介紹的任意零元阿貝爾有限??杉訄D群可以應(yīng)用于“同態(tài)圖群”,這將產(chǎn)生“同態(tài)圖群加密”技術(shù),在云計(jì)算、抗量子計(jì)算中具有可應(yīng)用性。下面給出一個(gè)網(wǎng)絡(luò)整體加密的例子, 采用了圖1中的任意零元(7)-模混合優(yōu)美圖群,它是一個(gè)任意零元阿貝爾有限??杉訄D群。圖2為給網(wǎng)絡(luò)T進(jìn)行整體加密。
圖1 一個(gè)(7)-模混合優(yōu)美圖G能生成19個(gè)(7)-模圖
圖2 給網(wǎng)絡(luò)T進(jìn)行整體加密Fig.2 Encrypting integrally a network T
圖2給出網(wǎng)絡(luò)T的4個(gè)整體加密, 其中,T1和T2的節(jié)點(diǎn)著色相同,但是邊著色不同,這是用于網(wǎng)絡(luò)整體加密的零元不同,T1的零元是(7)-?;旌蟽?yōu)美圖群中的G6,T2的零元是(7)-模混合優(yōu)美圖群中的G10。T3和T4的邊著色有著規(guī)律,T3的邊著色為G1,G2,G3,G4,G5, 不難看到,T4的邊著色為G1,G3,G5,G7,G9。 每個(gè)Gk(k∈[1,19])可以產(chǎn)生數(shù)字串, 例如,G1導(dǎo)出數(shù)字串
S1,i=314 123 134 145 055 566
(1)
它由18個(gè)數(shù)字組成。圖2中的T1的節(jié)點(diǎn)G1和節(jié)點(diǎn)G7被標(biāo)有G2的邊連接在一起, 節(jié)點(diǎn)G1導(dǎo)出的數(shù)字串S1,i與節(jié)點(diǎn)G7導(dǎo)出的數(shù)字串S7,i通過(guò)標(biāo)有G2的邊導(dǎo)出的數(shù)字串S2,i進(jìn)行連接認(rèn)證, 使得節(jié)點(diǎn)G1和節(jié)點(diǎn)G7之間有通訊聯(lián)通,認(rèn)證是由54個(gè)數(shù)字組成。當(dāng)網(wǎng)絡(luò)整體的零元發(fā)生變化后,連接2個(gè)節(jié)點(diǎn)邊著色也發(fā)生變化,邊著色導(dǎo)出的數(shù)字串也發(fā)生變化,使得2個(gè)節(jié)點(diǎn)的通訊認(rèn)證必須采用新的數(shù)字認(rèn)證。
一般情形下,一個(gè)任意零元阿貝爾有限??杉訄D群中的圖Gk導(dǎo)出mk個(gè)數(shù)字構(gòu)成的數(shù)字串,k為整數(shù)。任意2個(gè)節(jié)點(diǎn)Gi,Gj,通過(guò)Gk通訊認(rèn)證需由mi+mj+mk個(gè)數(shù)字構(gòu)成。 因?yàn)樯婕暗綀D的同構(gòu),加之已經(jīng)有數(shù)百種著色運(yùn)用于實(shí)際[10,11], 所以由式(1)中的數(shù)字串S1,i找到圖1中的著色圖G1是及其困難的。這說(shuō)明用任意零元阿貝爾有限??杉訄D群進(jìn)行網(wǎng)絡(luò)整體加密的優(yōu)勢(shì)。
文中所考慮的圖均為有限、無(wú)向、簡(jiǎn)單圖。文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)參考文獻(xiàn)[12]。為敘述簡(jiǎn)便起見(jiàn), 用記號(hào)[m,n]表示集合{m,m+1,m+2,…,n}, 其中,m和n均為整數(shù), 且滿足m 對(duì)于(q+1)-?;旌蟽?yōu)美圖, 其最小的頂點(diǎn)標(biāo)號(hào)是負(fù)數(shù), 最大的頂點(diǎn)標(biāo)號(hào)是正數(shù)。設(shè)圖G有(q+1)-?;旌蟽?yōu)美標(biāo)號(hào)f:V(G)→[-q,q], 使得 f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)} ({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。 如果G中最小的頂點(diǎn)標(biāo)號(hào)為s, 最大的頂點(diǎn)標(biāo)號(hào)為t, 記G的標(biāo)號(hào)f=fm, 其中,m=t+q+1,G=Gm, 那么對(duì)于G的每個(gè)拷貝Gk, 定義其(q+1)-模混合優(yōu)美標(biāo)號(hào)為:fk(x)=fm(x)-(m-k)(modq+1), 其中x∈V(G),k∈[1,3q+1]。 定義1[10,12]對(duì)于給定的 (p,q)-圖G, 如果存在一個(gè)單射f:V(G)→[0,q], 使得邊標(biāo)號(hào)集合f(E(G))={f(uv)=|f(u)-f(v)|:uv∈E(G)}=[1,q], 則稱f是G的一個(gè)優(yōu)美標(biāo)號(hào)(graceful labelling), 也稱G為優(yōu)美圖 (graceful graph)。此外, 若圖G是具有頂點(diǎn)二部劃分(X,Y)的二部圖, 且f滿足max{f(x)|x∈X} 定義2 對(duì)于給定的 (p,q)-圖G, 如果存在一個(gè)單射f:V(G)→[-q,q], 使得G的任何不同的2個(gè)頂點(diǎn)u,v滿足f(u)≠f(v), 且邊標(biāo)號(hào)集合 f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)} ({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q], 則稱f是圖G的一個(gè)(q+1)-模混合優(yōu)美標(biāo)號(hào)((q+1)-modular mixed graceful labelling), 也稱G為(q+1)-?;旌蟽?yōu)美圖((q+1)-modular mixed graceful graph)。特別地, 若f:V(G)→[0,q], 則稱f是圖G的一個(gè)(q+1)-模優(yōu)美標(biāo)號(hào)((q+1)-modular graceful labelling);若f:V(G)→[-q,0], 則稱f是圖G的一個(gè)(q+1)-模負(fù)優(yōu)美標(biāo)號(hào)((q+1)-modular negative graceful labelling)。 假設(shè)F是群,F′是它的非空子集且對(duì)于F中的加法運(yùn)算封閉, 如果F′本身對(duì)于F中這個(gè)加法運(yùn)算是群, 則稱F′是F的子群, 并且表示成F′ 已知, 一個(gè) (q+1)-?;旌蟽?yōu)美圖G拷貝可以得到3q+1個(gè)圖。 事實(shí)上, (q+1)-?;旌蟽?yōu)美圖的頂點(diǎn)標(biāo)號(hào)是在[-q,q]中取得, (q+1)-模優(yōu)美圖的頂點(diǎn)標(biāo)號(hào)是在[0,q]中取得, (q+1)-模負(fù)優(yōu)美圖的頂點(diǎn)標(biāo)號(hào)在[-q, 0]中的取得。 這些圖做成一個(gè)集合, 稱此集合是由(q+1)-?;旌蟽?yōu)美圖G生成的, 記作Mixg(G)。 任取一個(gè)固定的元Gk∈Mixg(G), 對(duì)任意的2個(gè)元Gi,Gj∈Mixg(G)={Gk:k∈[1,3q+1]}, 定義加法運(yùn)算“Gi⊕kGj”如下: [fi(x)+fj(x)-fk(x)](modq+1)=fλ(x) (2) 其中,λ=i+j-k(modq+1),x∈V(G)=V(Gi)=V(Gj)=V(Gk)。 (1)若[fi(x)+fj(x)-fk(x)]<-q, 則 [fi(x)+fj(x)-fk(x)](modq+1)=q+1+fi(x)+ fj(x)-fk(x); (2)若[fi(x)+fj(x)-fk(x)]>q, 則 [fi(x)+fj(x)-fk(x)](modq+1)=fi(x)+fj(x)- fk(x)-(q+1); (3)若不是上面(1)和(2)的情形,[fi(x)+fj(x)-fk(x)](modq+1)=fi(x)+fj(x)-fk(x)。 集合Mixg(G)和加法運(yùn)算構(gòu)成一個(gè)任意零元阿貝爾有限模可加圖群(見(jiàn)定理1的證明), 特記作{Mixg(G),f;⊕}。 定理1 設(shè) (p,q)-圖G有 (q+1)-?;旌蟽?yōu)美標(biāo)號(hào)f。 以下結(jié)論成立: (1)G生成了3q+1個(gè)圖, 構(gòu)成一個(gè)任意零元阿貝爾有限模可加圖群{Mixg(G),f;⊕}。 (2)任意連續(xù)的q+1+i個(gè)圖構(gòu)成一個(gè)任意零元阿貝爾有限??杉訄D子群, 且階為3q+1-i的子群有i+1 個(gè), 其中,i∈[0,2q]。 (3)G可以生成2個(gè)特殊的任意零元阿貝爾有限??杉訄D子群, 其中,一個(gè)子群中的圖都是(q+1)-模優(yōu)美的, 另一個(gè)子群中的圖都是(q+1)-模負(fù)優(yōu)美的。 證明任取一個(gè)圖Gk0∈Mixg(G)作為零元, 對(duì)任意2個(gè)元Gi,Gj∈Mixg(G), 定義加法運(yùn)算Gi⊕k0Gj=Gλ(λ=i+j-k0(modq+1)∈[1,3q+1]) 如下: [fi(x)+fj(x)-fk0(x)](modq+1)=fm(x)- [m-(i+j-k0)](modq+1)=fλ(x) (3) 其中,λ=i+j-k0(modq+1),x∈V(G)=V(Gi)=V(Gj)=V(Gk0)。 (1)首先證明Mixg(G)是任意零元阿貝爾有限??杉訄D群。Gi⊕k0Gj∈Mixg(G), 假設(shè)Gi⊕k0Gj=Gλ,Gi⊕k0Gj=Gμ, 則有λ=i+j-k0(modq+1)=μ。 1)零元 因?yàn)镚i⊕k0Gk0=Gi, 所以Gk0是Mixg(G)的零元。 2)逆元 因?yàn)镚i⊕k0G2k0-i=Gk0, 所以Gi∈Mixg(G)的逆元是G2k0-i∈Mixg(G)。 3)結(jié)合律 因?yàn)閇Gi⊕k0Gj]⊕k0Gl=Gi+j-k0⊕k0Gl=Gi+j+l-2k0以及Gi⊕k0[Gj⊕k0Gl]=Gi⊕k0Gj+l-k0=Gi+j+l-2k0,所以[Gi⊕k0Gj]⊕k0Gl=Gi⊕k0[Gj⊕k0Gl]。 綜上,Mixg(G)是一個(gè)任意零元阿貝爾有限??杉訄D群{Mixg(G),f;⊕}。 而Gi⊕k0Gj=Gj⊕k0Gi, 可知它又是交換群。 (2)Mixg(G)中任取連續(xù)的q+1+i個(gè)圖, 構(gòu)成集合H, 可得H是Mixg(G)的一個(gè)任意零元阿貝爾有限??杉訄D子群, 且階為3q+1-i的子群有i+1 個(gè), 其中,i∈[0,2q]。 (3)顯然,Mixg(G)中的前q+1個(gè)圖都是(q+1)-模負(fù)優(yōu)美的, 后q+1個(gè)圖都是(q+1)-模優(yōu)美的。 它們構(gòu)成的圖群都是Mixg(G)的任意零元阿貝爾有限模可加圖子群。 事實(shí)上, 圖1中的19個(gè)圖就是按照?qǐng)D3中Gk的生成方式由G生成的, 其中,前7個(gè)圖是(7)-模負(fù)優(yōu)美的, 后7個(gè)圖是(7)-模優(yōu)美的, 中間的圖都是(7)-?;旌蟽?yōu)美的。 圖3 圖G是(7)-?;旌蟽?yōu)美圖, G能生成19個(gè)(7)-模圖Gk, 其中k∈[1,19] 定理2設(shè)H是Mixg(G)的一個(gè)非空子集, 則H是Mixg(G)的任意零元阿貝爾有限模可加圖子群的充分必要條件是對(duì)于任意Hi,Hj∈H, 給定Hk0, 有Hi⊕k0H2k0-j∈H。 證明充分性。 由于Hi∈H, 給定Hk0, 則有Hk0=Hi⊕k0H2k0-i∈H, 因此,對(duì)于任意的Hj∈H,H2k0-j=Hk0⊕k0H2k0-j∈H。 如果Hi,Hj∈H, 那么H2k0-j∈H, 所以Hi⊕k0Hj=Hi⊕k0H2k0-(2k0-j)∈H。因?yàn)镸ixg(G)是任意零元阿貝爾有限??杉訄D群, 從而H中的加法運(yùn)算滿足結(jié)合律, 所以H是Mixg(G)的任意零元阿貝爾有限??杉訄D子群。 必要性。 顯然。 設(shè)連通圖G有 (q+1)-模優(yōu)美標(biāo)號(hào)f:V(G)→[0,q], 使得 f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。 記圖G的(q+1)-模優(yōu)美標(biāo)號(hào)f=f1,G=G1。 則對(duì)于G的每個(gè)拷貝Gk定義(q+1)-模優(yōu)美標(biāo)號(hào)fk如下: fk(x)=f1(x)+(k-1)(modq+1), 其中,x∈V(G),k∈[1,q+1]。 如果G有 (q+1)-模負(fù)優(yōu)美標(biāo)號(hào)號(hào)f:V(G)→[-q,0], 使得 f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。 記圖G的(q+1)-模負(fù)優(yōu)美標(biāo)號(hào)f=f1,G=G1。 則對(duì)于G的每個(gè)拷貝Gk定義(q+1)-模負(fù)優(yōu)美標(biāo)號(hào)fk如下: fk(x)=f1(x)-(k-1)(modq+1), 其中,x∈V(G),k∈[1,q+1]??傻靡韵陆Y(jié)論: 推論1設(shè)圖G有(q+1)-模(負(fù))優(yōu)美標(biāo)號(hào)f, 則G能生成q+1個(gè)(q+1)-模(負(fù))優(yōu)美圖, 這些圖構(gòu)成一個(gè)階為q+1的任意零元阿貝爾有限??杉訄D群。 推論3 (q+1)-模(負(fù))優(yōu)美圖的對(duì)偶圖能生成q+1個(gè) (q+1)-模(負(fù))優(yōu)美圖, 這些圖構(gòu)成一個(gè)階為q+1的任意零元阿貝爾有限??杉訄D群。 設(shè)(p,q)-圖G有 (q+1)-模優(yōu)美標(biāo)號(hào)f:V(G)→[0,q], 如果G按照f(shuō)l(uv)=f1(uv)+(l-1)(modq+1)能生成q+1個(gè)圖, 其中,uv∈E(G)=E(Gl),G1=G,Gk+q+1=Gk(modq+1), 那么, 邊標(biāo)號(hào)f:E(Gl)→[0,q], 稱這q+1個(gè)圖是邊模圖, 它們有著相同的頂點(diǎn)標(biāo)號(hào)。 這些圖組成的集合記作Gg(G)={Gl:l∈[1,q+1]}。下面在Gg(G) 上定義加法運(yùn)算“Gi⊕kGj”, 任意給定Gk∈Gg(G), 則 [fi(uv)+fj(uv)-fk(uv)](modq+1)=fλ(uv), 其中,λ=i+j-k(modq+1),uv∈E(G)=E(Gi)=E(Gj)=E(Gk), (1)若[fi(uv)+fj(uv)-fk(uv)]<-q, 則[fi(uv)+fj(uv)-fk(uv)](modq+1)=q+1+fi(uv)+fj(uv)-fk(uv); (2)若[fi(uv)+fj(uv)-fk(uv)]>q, 則[fi(uv)+fj(uv)-fk(uv)](modq+1)=fi(uv)+fj(uv)-fk(uv)-(q+1); (3)其他情況時(shí), [fi(uv)+fj(uv)-fk(uv)](modq+1)=fi(uv)+fj(uv)-fk(uv)。 那么Gg(G)是任意零元阿貝爾有限??杉訄D群, 記作{Gg(G),f;⊕}。 設(shè)(p,q)-圖G有(q+1)-模優(yōu)美標(biāo)號(hào)f, 根據(jù)運(yùn)算fk(x)=f1(x)+(k-1)(modq+1)能生成q+1個(gè)圖, 其中,x∈V(G)=V(Gk),G1=G,k∈[1,q+1], 這些圖稱為頂點(diǎn)模圖。每個(gè)圖Gk保持頂點(diǎn)不變, 根據(jù)運(yùn)算fk,l(uv)=fk,1(uv)+(l-1)(modq+1)又可以生成q+1個(gè)邊模圖, 其中,uv∈E(Gk,l)(Gk,l?Gk),l∈[1,q+1],k∈[1,q+1]。Gk,l的標(biāo)號(hào)fk,l定義如下: fk,1(x)=f1,1(x)+(k-1)(modq+1), fk,l(uv)=fk,1(uv)+(l-1)(modq+1), 其中,x∈V(G)=V(Gk,l),uv∈E(G)=E(Gk,l),G1,1=G,f1,1=f,l,k∈[1,q+1]。 事實(shí)上, 邊模圖Gk,1,Gk,2,…,Gk,q+1構(gòu)成了一個(gè)任意零元阿貝爾有限??杉訄D群, 又k∈[1,q+1], 因此,有q+1個(gè)由邊模圖構(gòu)成的任意零元阿貝爾有限??杉訄D群。 頂點(diǎn)模圖G1,l,G2,l,…,Gq+1,l構(gòu)成了一個(gè)任意零元阿貝爾有限??杉訄D群, 又l∈[1,q+1], 因此,有q+1個(gè)由頂點(diǎn)模圖構(gòu)成的任意零元阿貝爾有限模可加圖群。 故每個(gè)(q+1)-模優(yōu)美圖G可以生成 (q+1)2個(gè)圖, 記作Gk,l(k,l∈[1,q+1]), 這些圖構(gòu)成了2(q+1)個(gè)任意零元阿貝爾有限??杉訄D群。 類似可得, 每個(gè)(q+1)-模負(fù)優(yōu)美圖可以生成q+1個(gè)頂點(diǎn)模圖, 每個(gè)頂點(diǎn)模圖又可以生成q+1個(gè)邊模圖, 這些圖構(gòu)成了2(q+1)個(gè)任意零元阿貝爾有限??杉訄D群(圖4)。 每個(gè)(q+1)-?;旌蟽?yōu)美圖可以生成3q+1個(gè)頂點(diǎn)模圖, 每個(gè)頂點(diǎn)模圖又可以生成q+1個(gè)邊模圖, 從而得到4q+2個(gè)任意零元阿貝爾有限??杉訄D群。 圖4 (6,6)-圖G是(7)-模優(yōu)美圖, G可生成頂點(diǎn)模圖和邊模圖,其中k,l∈[0,6]Fig.4 The (6,6)-graph G is a (7)-modular graceful graph, G can generate vertex-modular graphs and edge-modular graphs, k,l∈[0,6] 給出了(q+1)-?;旌蟽?yōu)美標(biāo)號(hào), 子群, 有限群, 邊模圖和頂點(diǎn)模圖等概念。 定理 1 給出了(p,q)-圖G是(q+1)-?;旌蟽?yōu)美圖時(shí)可以生成的任意零元阿貝爾有限??杉訄D群和圖子群及它們的階。 定理 2 證明了H是Mixg(G)的一個(gè)非空子集, 則H是Mixg(G)的任意零元阿貝爾有限??杉訄D子群的充分必要條件是對(duì)于任意Hi,Hj∈H, 給定Hk0, 有Hi⊕k0H2k0-j∈H。 最后提出了每個(gè)(q+1)-模優(yōu)美圖G可以生成q+1個(gè)頂點(diǎn)模圖, 每個(gè)頂點(diǎn)模圖又可以生成q+1個(gè)邊模圖, 這些圖構(gòu)成了2(q+1)個(gè)任意零元阿貝爾有限模可加圖群。 對(duì)于(q+1)-模負(fù)優(yōu)美圖和(q+1)-?;旌蟽?yōu)美圖也可以得到類似的結(jié)果。 在同態(tài)圖群加密技術(shù)中, 若圖的頂點(diǎn)或者邊數(shù)較多, 并結(jié)合已有的數(shù)百種著色就可以大大提高信息的安全性。 這里討論的都是有限圖, 對(duì)于無(wú)限群是否會(huì)有類似的結(jié)論?這是今后需要繼續(xù)研究的課題。3 主要結(jié)果及證明
4 結(jié) 語(yǔ)
廣州大學(xué)學(xué)報(bào)(自然科學(xué)版)2022年1期