一類存取結(jié)構(gòu)信息率的上界

麻敏

摘要：文章研究了Csirmaz存取結(jié)構(gòu)信息率的上界，從Shannon熵的角度出發(fā)，運用了Shannon熵的單調(diào)性這一良好的性質(zhì)得出該類存取結(jié)構(gòu)的上界，該上界與Pradeep Sarvepalli所得到的結(jié)果相比更加精確。

關(guān)鍵詞：熵;Csirmaz存取結(jié)構(gòu);單調(diào)性;上界

中圖分類號：TP311? ? ? ?文獻標識碼：A? ? ? ? 文章編號：1009-3044（2019）03-0050-03

1 引言

秘密共享方案是指多個參與者共享同一秘鑰. 完善的秘密共享方案是指合法子集能夠恢復(fù)秘密，非合法子集不能得到秘密的任何信息。秘密共享方案的完善性可由Shannon熵或者Von Neumann熵來刻畫，Shannon熵測量的不確定性與經(jīng)典概率分布相關(guān)聯(lián)，描述量子態(tài)的方式是類似的，只是用密度算子代替了概率分布，即Von Neumann熵。Shannon熵和Von Neumann熵分別對應(yīng)于經(jīng)典秘密共享方案和量子秘密共享方案。

本文主要是在Pradeep? Sarvepalli 論文的基礎(chǔ)上對Csirmaz 存取結(jié)構(gòu)的信息率上界給出了更細致的刻畫。 Csirmaz 存取結(jié)構(gòu)可以看作一個量子存取結(jié)構(gòu)，但同時也是一個經(jīng)典的存取結(jié)構(gòu)，這一性質(zhì)為本文的研究提供了理論基礎(chǔ)。

下面給出一些相關(guān)知識與結(jié)論。

2 預(yù)備知識

定義1.存取結(jié)構(gòu)

設(shè)參與者集合為[P=p1，p2，p3…，pn，P]的子集構(gòu)成的集合記為[2p，]存取結(jié)構(gòu)[Γ?2p]。[Γ]由授權(quán)子集組成，授權(quán)子集中的參與者可以利用他們持有的秘密所分配的份額經(jīng)典（或量子）態(tài)恢復(fù)秘密。如果一個授權(quán)子集的任一真子集均不能恢復(fù)秘密，則該授權(quán)子集稱為極小授權(quán)子集。極小授權(quán)子集組成的集合稱為極小存取結(jié)構(gòu)，用[Γ0]表示. [S]代表秘密空間。

顯然，存取結(jié)構(gòu)滿足單調(diào)性，即若[A∈Γ，]且[A?B?2p]，則[B∈Γ.]也就是說，若[A]中的參與者能恢復(fù)秘密，則[B]中的參與者也能恢復(fù)秘密。

定義2.完善的秘密共享方案

一個秘密共享方案中，如果任意授權(quán)集可以恢復(fù)秘密，而非授權(quán)集不能得到關(guān)于秘密的任何信息，則稱該方案為完善的。

定義3.不重要的參與者[2]

如果沒有一個非授權(quán)集通過增加參與者x能變成授權(quán)集，則參與者x稱為不重要的參與者。顯然，不重要參與者的共享可以被忽略，因此x的共享可被視為0。

定義4.信息率

信息率可認為是一個秘密共享方案實現(xiàn)的效率。可理解為秘密長度與最長共享的比值，用熵來刻畫。即信息率[ε=H（s）maxpi∈PH（pi）]，顯然，[ε≤1]。如果一個完善的秘密共享方案的信息率為1，則稱該方案是理想的。

定義5.相關(guān)熵理論

一個有限集[X]上的概率分布[{p（x）}x∈X]，定義[X]的熵（Shannon熵）[H（X）=][-x∈Xp（x）logp（x），]一般地，[H（X）]的單位為比特[（bit）]，[log]代表以[2]為底的對數(shù)。

3 Shannon熵與存取結(jié)構(gòu)

引理1[7] 實現(xiàn)一個存取結(jié)構(gòu)[Γ]的秘密共享方案是完善的，如果以下兩條被滿足：

4 量子秘密共享方案與Von Neumann熵

一個存取結(jié)構(gòu)如果能由一個量子秘密共享方案實現(xiàn)，則該存取結(jié)構(gòu)稱為量子存取結(jié)構(gòu)。一個存取結(jié)構(gòu)是量子存取結(jié)構(gòu)當(dāng)且僅當(dāng)任兩個授權(quán)集都有交集。易得量子存取結(jié)構(gòu)中，授權(quán)集的補集是非授權(quán)的。由此可知量子存取結(jié)構(gòu)是一種特殊的存取結(jié)構(gòu)。這種特殊性體現(xiàn)在信息率等的刻畫上，一般的存取結(jié)構(gòu)是用Shannon熵及經(jīng)典信息論模型來描述的，而對于量子存取結(jié)構(gòu)而言，引入了Von Neumann熵這一新的概念來更具體地刻畫這一類存取結(jié)構(gòu)，Von Neumann熵與Shannon熵很多性質(zhì)都比較相似，一個較大的差異就是Von Neumann熵不滿足單調(diào)性要求，所以在求量子存取結(jié)構(gòu)的信息率時引入了存取結(jié)構(gòu)的純化，得到了自對偶結(jié)構(gòu)。

這樣，我們在計算Csirmaz存取結(jié)構(gòu)信息率時，可以從Shannon熵與Von Neumann熵兩個角度出發(fā)。而在Pradeep? Sarvepalli 論文中已經(jīng)從Von Neumann熵及存取結(jié)構(gòu)的純化等角度出發(fā)，得出了Csirmaz存取結(jié)構(gòu)信息率的上界[ε1]為[2k+12k+1-1][4]，我們致力于從Shannon熵的角度出發(fā)，得出一個更確切的信息率上界，Shannon熵的單調(diào)性這一良好的性質(zhì)是一個有力的工具。

首先，給出Csirmaz存取結(jié)構(gòu)滿足的一個特殊的不等式并給出證明，這在計算信息率上界時是非常重要的。

5 結(jié)論

本文從Shannon熵角度出發(fā)得出Csirmaz存取結(jié)構(gòu)信息率的上界，對Pradeep? Sarvepalli先前的研究作了一些改進，得到了一個更具體的信息率上界。

參考文獻：

[1] 宋云，李志慧，李永明.含至多四個參與者的量子秘密共享方案的最優(yōu)信息率[J].電子學(xué)報，2014（10）.

[2] Laszlo Csirmaz. The Size of a Share Must Be Large[J].Cryptology， 1997（10）： 223- 231.

[3] Hideki Imai， Jorn Muller Quade. A Quantum Information Theoretical Model for Quantum Secret Sharing? Schemes[J].Comput.5， 2005，069.

[4] Pradeep Sarvepalli. Bounds on the information rate of quantum secret sharing schemes[J].PhysRevA ，2010.

[5] 劉木蘭，張志芳.秘鑰共享體制和安全多方計算[M].北京：電子工業(yè)出版社，2008：133-134.

[6] 周展飛.秘鑰共享體制—性質(zhì)、結(jié)構(gòu)和構(gòu)造[D].北京：中國科學(xué)院系統(tǒng)科學(xué)研究所，1997.

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

[8] R.M.Capocelli，A.De Santis，and U.Vaccaro，On the Size of Shares for Secret Sharing Schemes，Journal of Cryptology ， 1993（6）：157-167.

[9] D.Markham and B.Sanders，Phys. Rev. A 78，042309（2008）.

[10] D.Gottesman，Phys. Rev.A 61，042311（2000）.

[11] 宋云，李志慧.一類完善秘密共享方案的最優(yōu)信息率[J].計算機工程，2012，38（12）：9-12，16.

【通聯(lián)編輯：代影】