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

李志慧，張娜娜

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

·安全技術·

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

李志慧，張娜娜

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

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

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

1 概述

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

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

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

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

2 預備知識

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

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

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

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

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

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

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

注2 當k=n時，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｝，則這時該超圖H（V，E）可看作一個3-一致完全4分超圖。

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

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

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

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

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

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

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

引理3 設不定方程組［14］：

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

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

（3）當k＞n時，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)

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

滿足性質(zhì)：

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

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

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

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

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

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

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

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

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

例3 在超圖H（V，E）中，令n（H）=9，k=5，那么這種情況下頂點集V的5劃分的個數(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 設H（V，E）是一個含有n個頂點且秩為r的超圖，則r-一致完全k分超圖存取結(jié)構(gòu)有（k-1）B（n，k）個，其中，2≤r≤k≤n。

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

例4 設H（V，E）是一個含有6個頂點的超圖，則所對應的r-一致完全k分超圖存取結(jié)構(gòu)的個數(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 實例驗證

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

表1 F7上頂點數(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中，當n=4，5，6時，相對應的這類理想存取結(jié)構(gòu)的數(shù)目分別為7，13，24。分析表明，當頂點數(shù)n增大時，這類理想存取結(jié)構(gòu)的數(shù)目明顯增多。從表1中看到，這類新的理想存取結(jié)構(gòu)比較豐富，且理想的（r，n）門限存取結(jié)構(gòu)和完全k分圖對應的理想的存取結(jié)構(gòu)均是這類超圖存取結(jié)構(gòu)的特殊情況。

5 結(jié)束語

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

［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］ 劉木蘭，張志芳.密鑰共享體制和安全多方計算［M］.北京：電子工業(yè)出版社，2008.

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

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

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

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

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

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

［15］ 張倩倩，李志慧，雷 娟.基于向量空間上的無分發(fā)者的秘密共享方案［J］.計算機應用研究，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］.計算機工程，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

國家自然科學基金資助項目（61373150）；陜西省科學技術研究發(fā)展計劃工業(yè)攻關基金資助項目（2013K 0611）。

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

2014-10-24

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