李志慧，張娜娜

（陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，西安710119）

·安全技術(shù)·

基于一類超圖的理想存取結(jié)構(gòu)

李志慧，張娜娜

（陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，西安710119）

具有n個(gè)參與者形成的存取結(jié)構(gòu)集合與具有n個(gè)頂點(diǎn)的超圖集合之間存在一一對(duì)應(yīng)關(guān)系。定義一類超圖，即r-一致完全k分超圖，運(yùn)用向量空間構(gòu)造法證明該類超圖對(duì)應(yīng)的存取結(jié)構(gòu)是理想的，進(jìn)而利用組合數(shù)學(xué)知識(shí)計(jì)算出該類超圖存取結(jié)構(gòu)的數(shù)目。在有限域F7上給出參與者人數(shù)為4，5，6的所有r-一致完全k分超圖存取結(jié)構(gòu)。驗(yàn)證結(jié)果表明，相比（r，n）門限存取結(jié)構(gòu)和完全k分圖存取結(jié)構(gòu)，該類理想的超圖存取結(jié)構(gòu)更為一般化，應(yīng)用更為廣泛。

超圖；完全k分超圖；存取結(jié)構(gòu)；理想存取結(jié)構(gòu)；向量空間構(gòu)造

1 概述

秘密共享在提供重要數(shù)據(jù)的安全性、防止秘密信息丟失等方面有著重要的作用，它被廣泛地應(yīng)用于通信密鑰管理、電子拍賣、電子選舉等實(shí)踐中。設(shè)n是一個(gè)正整數(shù)，令參與者集合P=｛P1，P2，…，Pn｝，在一個(gè)秘密共享體制中，對(duì)于主密鑰s，參與者集合P中只有那些事先授權(quán)的子集中的參與者，利用他們所持有的秘密份額才能恢復(fù)秘密，這些子集組成的集合Γ稱為存取結(jié)構(gòu)，其中的子集叫授權(quán)子集。如果一個(gè)授權(quán)子集的任意真子集均不能恢復(fù)秘密，稱這個(gè)授權(quán)子集為極小授權(quán)子集，由所有極小授權(quán)子集組成的集合稱為極小存取結(jié)構(gòu)。

一個(gè)秘密共享體制稱作完善的，如果參與者中的非授權(quán)子集不能得到關(guān)于密鑰的任何信息。文獻(xiàn)［1］利用熵的概念，證明了在任何完善門限秘密共享方案中，參與者得到的共享一定至少和密鑰一樣長，隨后，文獻(xiàn)［2］把這個(gè)結(jié)果推廣到任何完善秘密共享方案中。這意味著在完善秘密共享方案中有數(shù)據(jù)擴(kuò)散。出于安全性考慮，主密鑰空間通常取得較大，以防止攻擊者的窮搜索。但是另一方面，數(shù)據(jù)擴(kuò)散增加了子密鑰的長度，給子密鑰的保管帶來了困難，因此，希望找到?jīng)]有數(shù)據(jù)擴(kuò)散的完善秘密共享方案。針對(duì)這種想法，文獻(xiàn)［3］引進(jìn)了理想秘密共享體制的概念。對(duì)于任意一個(gè)存取結(jié)構(gòu)Γ來說，都存在一個(gè)實(shí)現(xiàn)該結(jié)構(gòu)的秘密共享方案，當(dāng)存在一個(gè)理想的秘密共享方案實(shí)現(xiàn)了存取結(jié)構(gòu)Γ，即存取結(jié)構(gòu)Γ是理想的。

Sham ir［4］和B lak ley［5］于1979年分別獨(dú)立地提出了秘密共享的概念，并給出了Sham ir（k，n）門限秘密共享方案。這類方案對(duì)應(yīng)的門限存取結(jié)構(gòu)是理想的，但結(jié)構(gòu)比較單一。文獻(xiàn)［6-8］研究了圖存取結(jié)構(gòu)的秘密共享方案，證明了完全k分圖（也稱作完全多劃分圖）所對(duì)應(yīng)的存取結(jié)構(gòu)均是理想的，但是這類方案的存取結(jié)構(gòu)的秩只能為2。

本文對(duì)完全k分圖的定義給予推廣，提出r-一致完全k分超圖的概念，證明了該類超圖對(duì)應(yīng)的存取結(jié)構(gòu)，進(jìn)而計(jì)算這類理想超圖存取結(jié)構(gòu)的數(shù)目。

2 預(yù)備知識(shí)

定義2 在超圖H（V，E）中，設(shè)Ei，Ej是它的任意兩個(gè)超邊，若滿足Ei?Ej，則必有Ei=Ej，稱H（V，E）為一個(gè)簡單超圖［9］。秩為r的簡單一致超圖稱為r-一致超圖。

注1 秩為2的超圖，即將超圖H（V，E）記為G（V，E）。

定義3 在超圖H（V，E）中，如果對(duì)任意2個(gè)頂點(diǎn)u，v∈V都存在從u到v的一條超徑，則該超圖被稱作是連通超圖［10］，即存在一個(gè)超邊序列Ei1，Ei2，…，Eis使得：

其中，j=1，2，…，s-1。

定義4 在圖G（V，E）中，若每對(duì)互異頂點(diǎn)恰有一條邊相連接，則稱此圖為完全圖［11］。階為n的完全圖記為Kn。

定義5 在超圖H（V，E）中，若每r個(gè)互異頂點(diǎn)恰有一條邊相連接，則稱此超圖為r-一致完全超圖，階為n的r-一致完全超圖記為。

定義6 在圖G（V，E）中［11］，若V=V1∪V2，V1∩V2=φ，且Vi中任意2個(gè)頂點(diǎn)都不相連接（i= 1，2），則稱H（V，E）為二分圖；若V1中每個(gè)頂點(diǎn)都與V2中的每個(gè)頂點(diǎn)相連接，則稱H（V，E）為完全二分圖，記為Km，n，其中，。

注2 當(dāng)k=n時(shí)，r-一致完全k分超圖可以看作r-一致完全超圖。

例1 在超圖H（V，E）中，令V=｛1，2，3，4，5｝，E=｛123，124，125，134，135，234，235｝。令V1=｛1｝，V2=｛2｝，V3=｛3｝，V4=｛4，5｝，則這時(shí)該超圖H（V，E）可看作一個(gè)3-一致完全4分超圖。

定義9 超圖H（V，E）與H′（V′，E′）稱為同構(gòu)的［9］，當(dāng)且僅當(dāng)存在一一映射f：V→V′和g：E→E′。且這2個(gè)映射保持關(guān)聯(lián)關(guān)系，即：g（e）=f（v1）f（v2）…f（vt），?e=v1v2…vt∈E，vi∈V，i=1，2，…，t。

引理1 如果2個(gè)超圖同構(gòu)，那么這2個(gè)超圖的頂點(diǎn)數(shù)相同，超邊數(shù)相同，秩相同，且頂點(diǎn)在超邊中出現(xiàn)的次數(shù)相同［12］。

在秘密共享中，極小存取結(jié)構(gòu)Γ0，Γ0?2P，可以表示為一個(gè)超圖H（P，Γ0），其中每個(gè)參與者表示這個(gè)超圖H（P，Γ0）的一個(gè)頂點(diǎn)，每個(gè)極小授權(quán)子集表示這個(gè)超圖H（P，Γ0）的一個(gè)超邊。顯然，H（P，Γ0）是一個(gè)簡單超圖。將極小存取結(jié)構(gòu)Γ0看作超圖H（V，E）中的超邊集E時(shí)，這個(gè)極小存取結(jié)構(gòu)Γ0就為超圖存取結(jié)構(gòu)。

注3 （r，n）門限存取結(jié)構(gòu)是r-一致完全k分超圖存取結(jié)構(gòu)的特殊情況，設(shè)參與者人數(shù)為n，可看作超圖的n個(gè)頂點(diǎn)，只需把頂點(diǎn)n劃分，那么對(duì)應(yīng)的r-一致完全k分超圖就是（r，n）門限存取結(jié)構(gòu)。

定義10 如果2個(gè)參與者u和v在存取結(jié)構(gòu)中的作用是一樣的，即對(duì)任意包含u但不包含v的授權(quán)子集W和任意包含v但不包含u的授權(quán)子集V，W′=（W｛u｝）∪｛v｝和V′=（V｛v｝）∪｛u｝都是授權(quán)子集，那么這2個(gè)參與者稱為等價(jià)的。

由定義8知，r-一致完全k分超圖中的任一個(gè)頂點(diǎn)集合Vi（i=1，2，…，k）中的頂點(diǎn)都是等價(jià)的。

引理2 設(shè)G（V，E）是一個(gè)完全k分圖，則存在一個(gè)理想秘密共享方案實(shí)現(xiàn)了參與者集合V上的極小存取結(jié)構(gòu)E［13］。

引理3 設(shè)不定方程組［14］：

令B（n，k）為式（1）的正整數(shù)解的個(gè)數(shù)，則有：

（1）B（n，1）=B（n，n-1）=B（n，n）=1；

（3）當(dāng)k＞n時(shí)，B（n，k）=0；

（4）B（n，k）=B（n-1，k-1）+B（n-k，k），n，k∈N；

（5）B（n+k，k）=B（n，1）+B（n，2）+…+B（n，k），n，k∈N。

3 理想存取結(jié)構(gòu)

設(shè)Γ是一個(gè)存取結(jié)構(gòu)，（Fp）d是Fp上所有的d元組組成的向量空間，其中，p是素?cái)?shù)，d≥2。假定存在函數(shù)：

滿足性質(zhì)：

若找到滿足式（2）的向量的集合，則可建立實(shí)現(xiàn)存取結(jié)構(gòu)Γ的理想秘密共享方案。這個(gè)方案被稱為基于向量空間秘密共享方案［13］。

定理1 設(shè)H（V，E）是一個(gè)r-一致完全k分超圖（2≤r≤k），則存在一個(gè)理想秘密共享方案實(shí)現(xiàn)了參與者集合V上的極小存取結(jié)構(gòu)E。

證明：易知H（V，E）的秩為r，設(shè)參與者人數(shù)為n，令V1，V2，…，Vk是頂點(diǎn)集合V的劃分，x1，x2，…，xk是有限域Fp中互不相同的非零元素，其中，p＞k，令d=r。設(shè)，其中，i=1，2，…，k，l1+ l2+…+lk=n。為了簡便起見，不妨設(shè)V1=｛v1，v2，…，vl1｝，…，Vk=｛vl1+…+lk-1+1，…，vl1+…+lk｝，對(duì)于每個(gè)參與者v∈V，構(gòu)造φ函數(shù)如下：

其中，vi1，vi2，…，vir表示頂點(diǎn)集V中任意r個(gè)不同的頂點(diǎn)，當(dāng)vi1，vi2，…，vir是一個(gè)極小授權(quán)子集時(shí)，由該類超圖存取結(jié)構(gòu)以及φ函數(shù)定義代入式（3）。式（3）對(duì)于mod p運(yùn)算有且僅有一個(gè)解，且各分量都是非零的；對(duì)任何非授權(quán)子集代入相應(yīng)的φ函數(shù)，此時(shí)式（3）的系數(shù)矩陣與其增廣矩陣的秩不等，故對(duì)于mod p運(yùn)算無解，從而得不到主密鑰的任何信息，顯然滿足式（2）。根據(jù)基于向量空間秘密共享方案是理想秘密共享方案知，r-一致完全k分超圖存取結(jié)構(gòu)是理想的存取結(jié)構(gòu)。

注4 當(dāng)r=2時(shí)，就是完全k分圖，由引理2知存在一個(gè)理想秘密共享方案實(shí)現(xiàn)了該圖存取結(jié)構(gòu)。

例2（接例1） 令k=4，r=3，在有限域F7上定義函數(shù)φ如下：

如果B是最大非授權(quán)子集，只需證明（1，0，0）?〈φ（pi）：pi∈B〉。一共有6個(gè)這樣的子集B需要考慮：｛12｝，｛13｝，｛23｝，｛145｝，｛245｝，｛345｝。對(duì)每種情況需建立一個(gè)特定的線性方程組，易知這些方程組均無解。例如，假設(shè)（1，0，0）=xφ（1）+yφ（2），其中，x，y∈F7，容易看出，此方程組無解。其余情況類似驗(yàn)證。所以該存取結(jié)構(gòu)是理想的。

定理2 設(shè)H（V，E）是一個(gè)含有n個(gè)頂點(diǎn)的超圖，將頂點(diǎn)集V劃分成k個(gè)非空子集的并，則這種劃分共有B（n，k）種。

證明：由于n個(gè)頂點(diǎn)與k個(gè)非空集合均是無區(qū)別，因此可以將這個(gè)頂點(diǎn)集的劃分問題可以看成式（1）的整數(shù)解的個(gè)數(shù)問題，從而頂點(diǎn)集合的這種劃分有B（n，k）種。

例3 在超圖H（V，E）中，令n（H）=9，k=5，那么這種情況下頂點(diǎn)集V的5劃分的個(gè)數(shù)為：B（9，5）=B（4+5，5）=B（4，1）+B（4，2）+ B（4，3）+B（4，4）+B（4，5）=1+2+1+1+0=5。

定理3 設(shè)H（V，E）是一個(gè)含有n個(gè)頂點(diǎn)且秩為r的超圖，則r-一致完全k分超圖存取結(jié)構(gòu)有（k-1）B（n，k）個(gè)，其中，2≤r≤k≤n。

證明：由r-一致完全k分超圖的定義知：2≤r≤k，2≤k≤n。當(dāng)k=2時(shí)，由定理2知頂點(diǎn)集V的劃分有B（n，2）種，此時(shí)r只能有一種取值，即r=2，故對(duì)應(yīng)的r-一致完全k分超圖有1·B（n，2）= B（n，2）個(gè)；當(dāng)k=3時(shí)，頂點(diǎn)集V的劃分有B（n，3）種，此時(shí)r有2種可能取值，即r=2，3，故對(duì)應(yīng)的r-一致完全k分超圖有2·B（n，2）=2B（n，2）個(gè)；依次類推，當(dāng)k=n時(shí)，頂點(diǎn)集V的劃分有B（n，n）種，此時(shí)r的n-1個(gè)可能取值為2，3，…，n，故對(duì)應(yīng)的r-一致完全k分超圖有（n-1）·B（n，n）個(gè)。故頂點(diǎn)數(shù)為n時(shí)，所對(duì)應(yīng)的r-一致完全k分超圖有B（n，2）+2B（n，3）+…+（n-1）B（n，n）=B（n，k）個(gè)，故這類超圖存取結(jié)構(gòu)有B（n，k）個(gè)。

例4 設(shè)H（V，E）是一個(gè)含有6個(gè)頂點(diǎn)的超圖，則所對(duì)應(yīng)的r-一致完全k分超圖存取結(jié)構(gòu)的個(gè)數(shù)為∑6

k=2（k-1）B（6，k）=B（6，2）+2B（6，3）+ 3B（6，4）+4B（6，3）+5B（6，6）=24。

4 實(shí)例驗(yàn)證

根據(jù)定義8中r-一致完全k分超圖的概念，給出了有限域F7上頂點(diǎn)數(shù)為4，5，6的所有r-一致完全k分超圖（2≤r≤k）及相對(duì)應(yīng)的理想存取結(jié)構(gòu)，如表1所示。

表1 F7上頂點(diǎn)數(shù)為4，5，6的r-一致完全k分超圖存取結(jié)構(gòu)（2＜r≤k≤n）

根據(jù)引理1及定義9，在表1中給出了所有互不同構(gòu)的r-一致完全k分超圖，即表中這些理想存取結(jié)構(gòu)是互不同構(gòu)的。在表1中，當(dāng)n=4，5，6時(shí)，相對(duì)應(yīng)的這類理想存取結(jié)構(gòu)的數(shù)目分別為7，13，24。分析表明，當(dāng)頂點(diǎn)數(shù)n增大時(shí)，這類理想存取結(jié)構(gòu)的數(shù)目明顯增多。從表1中看到，這類新的理想存取結(jié)構(gòu)比較豐富，且理想的（r，n）門限存取結(jié)構(gòu)和完全k分圖對(duì)應(yīng)的理想的存取結(jié)構(gòu)均是這類超圖存取結(jié)構(gòu)的特殊情況。

5 結(jié)束語

本文定義了一類特殊超圖-r，即一致完全k分超圖，利用向量空間構(gòu)造法證明了基于該類超圖的存取結(jié)構(gòu)是理想的，給出了這類超圖存取結(jié)構(gòu)的計(jì)數(shù)，本文構(gòu)造的這類特殊超圖存取結(jié)構(gòu)在結(jié)構(gòu)上是豐富的。相比理想的（r，n）門限存取結(jié)構(gòu)和完全k分圖對(duì)應(yīng)的理想的存取結(jié)構(gòu)，r-一致完全k分超圖對(duì)應(yīng)的理想存取結(jié)構(gòu)更為一般化，不局限于一個(gè)（r，n）門限存取結(jié)構(gòu)中極小授權(quán)子集的個(gè)數(shù)為以及一個(gè)完全k分圖存取結(jié)構(gòu)中秩一定為2的情況。在實(shí)際應(yīng)用中，由于這類超圖存取結(jié)構(gòu)還具有向量空間秘密共享方案的（+，+）同態(tài)性質(zhì)［15］，且結(jié)構(gòu)豐富，因此這類超圖存取結(jié)構(gòu)可用于替代許多電子協(xié)議中曾使用的存取結(jié)構(gòu)，能克服這些方案存在的不足。如在文獻(xiàn)［16-17］的電子投票協(xié)議中計(jì)算選票時(shí)，唱票人所在的存取結(jié)構(gòu)不具有靈活性或存取結(jié)構(gòu)是非完善的，均可用這類存取結(jié)構(gòu)替代，以提高方案的效率及使用時(shí)的靈活性。

［1］ Karnin E D，Greene J W，Hellman M E.On Secret Sharing System s［J］.IEEE Transactions on Information Theory，1983，29（1）：35-41.

［2］ Capocelli R M，Santis A D，Gargano L.On the Size of Shares for Secret Sharing Schemes［J］.Journal of Cryptology，1993，6（3）：157-167.

［3］ Brickell E F，Davenport D M.On the Classification of Ideal Secret Sharing Schemes［J］.Journal of Cryptology，1991，4（1）：123-134.

［4］ Sham ir A.How to Share a Secret［J］.Communications of the ACM，1979，22（11）：612-613.

［5］ Blahley G.Safeguarding Cryptographic Keys［C］// Proceedings of National Computer Conference.New York，USA：ACM Press，1979：313-317.

［6］ Hsu Changfang，Qi Cheng，Tang Xueming，et al.An Ideal Multi-secret Sharing Scheme Based on MSP［J］. International Journal of Information Sciences，2011，181（7）：1403-1409.

［7］ Jackson W，M artin K M.Pefect Secret Sharing Schemes on Five Participants［J］.Journal of Designs，Codes and Cryptography，1996，9（3）：267-286.

［8］ 劉木蘭，張志芳.密鑰共享體制和安全多方計(jì)算［M］.北京：電子工業(yè)出版社，2008.

［9］ 法C.貝爾熱.超圖-有限集的組合學(xué)［M］.卜月華，張克民，譯.南京：東南大學(xué)出版社，2002.

［10］ Crescenzo G D，Galdi C.Hypergraph Decomposition and Secret Sharing［J］.Discrete Applied Mathematics，2009，157（5）：928-946.

［11］ 王樹禾.圖論［M］.北京：科學(xué)出版社，2004.

［12］ 楊麗杰，李志慧，李 婧.一類超圖存取結(jié)構(gòu)的秘密共享方案的信息率［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（7）：2115-2119.

［13］ Stinson D R.密碼學(xué)原理與實(shí)踐［M］.3版.馮登國，譯.北京：電子工業(yè)出版社，2009.

［14］ 潘永亮，徐俊明.組合數(shù)學(xué)［M］.北京：科學(xué)出版社，2006.

［15］ 張倩倩，李志慧，雷 娟.基于向量空間上的無分發(fā)者的秘密共享方案［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（6）：2230-2232.

［16］ Benaloh J.Secret Sharing Homomorphisms：Keeping Shares of a Secret Secret［C］//Proceedings of CRYPTO'86. Berlin，Germany：Springer，1987：251-260.

［17］ Iftene S.General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting［J］. Elctronic Notes in Theoretical Computer Science，2007，186：67-84.

編輯索書志

Ideal Access Structure Based on a Type of Hypergraph

LI Zhihui，ZHANG Nana
（College of Mathematics and Information Science，Shaanxi Normal University，Xi'an 710119，China）

There exists a one-to-one correspondence between the set of access structures with n participants and that of hypergraphs with nvertices.This paper proposes a type of hypergraph，i.e.，r-uniform hypergraphs with complete kpartition.It proves that the type of hypergraph access structures is ideal by using vector space construction.The paper gives the number of this type of ideal hypergraph access structures using combinatorial mathematics，and gives all the ideal access structures w ith the number of participants（or vertices）4，5，6 over a finite field F7based on the r-uniform hypergraph with complete k-partition.Test results show that，com pared with（r，n）threshold access structures and complete k-partition graph access structures，the proposed ideal access structures are more vivid，and can be extensively applied in practice.

hypergraph；complete k-partition hypergraph；access structure；ideal access structure；vector space construction

李志慧，張娜娜.基于一類超圖的理想存取結(jié)構(gòu)［J］.計(jì)算機(jī)工程，2015，41（11）：165-169.

英文引用格式：Li Zhihui，Zhang Nana.Ideal Access Structure Based on a Type of Hypergraph［J］.Computer Engineering，2015，41（11）：165-169.

1000-3428（2015）11-0165-05

A

TP391

10.3969/j.issn.1000-3428.2015.11.029

國家自然科學(xué)基金資助項(xiàng)目（61373150）；陜西省科學(xué)技術(shù)研究發(fā)展計(jì)劃工業(yè)攻關(guān)基金資助項(xiàng)目（2013K 0611）。

李志慧（1966-），女，教授、博士，主研方向：有限域，密碼學(xué)；張娜娜，碩士研究生。

2014-10-24

2014-12-03 E-m ail：lizhihui@snnu.edu.cn