動態的（ｔ，ｎ）門限多秘密分享方案

摘要：基于單向函數和大整數因子分解問題，提出了一個動態有效的（t，n)門限多秘密分享方案。通過此分享方式，秘密分發者可以給出任一待分享秘密的集合，而每個成員只需持有惟一可以重復使用的秘密份額；它能同時有效地檢測出分發者和分享者的欺詐行為，解決秘密恢復時計算量大等問題。對于本方案來說，新成員的加入是容易的；為了在不影響其他任何成員的情況下刪除某個或某些成員，引入了一個新奇的方法。

關鍵詞：秘密分享； 門限體制； 單向函數； 成員刪除

中圖分類號：TP309文獻標志碼：A

文章編號：1001－3695(2008)01－0241－02



秘密分享的基本問題是允許參與者分享秘密， 并且只有一定的授權子集才能恢復秘密。為了實現這一目標，Shamir[1]在其創新性的工作中，利用Lagrange插值多項式提出了第一個秘密分享方案，即(t，n)門限方案。然而，這個方案有如下幾個缺陷：

a)每運行一次方案，只能分享一個秘密[2];

b)秘密一旦被重構，方案就要求秘密分發者通過安全信道向每一個成員重新分配秘密份額[3];

c)誠實的分發者可以分配一個假的秘密份額， 以至于該成員不能得到真正的秘密[4];

d)在秘密恢復階段，惡意的成員可以向其他成員提供偽造的秘密份額，使得只有他才能重構出真正的秘密[5]。

為了克服上述缺陷，許多有效的(t，n)門限秘密分享方案被提出。Harn[6]綜合考慮上述問題，提出了一個(t，n)門限可驗證的多秘密分享方案。但是，Harn的方案也有缺陷:a)為了防止分發者欺詐，每個成員要完成nt個模指數運算；b)在秘密恢復階段，每個成員要與另外任何一個成員執行交互式的驗證協議，才能證實該成員所提供秘密份額的有效性；c)只能分享預先確定或計算好的秘密。為此，L. Aolleman等人[7]基于因子分解的困難性和模合數下離散對數問題的難解性，進一步提出了一個門限可驗證的多秘密分享方案。遺憾的是，該方案仍然沒有彌補Harn方案中的缺陷c)。T.Y. Chang等人[8]改進了文獻[7]中的方案，完全解決了Harn方案和文獻[7]方案中的問題，還能減少計算復雜性。

但是，這些秘密分享方案都是利用離散對數問題或RSA密碼體制，使得在秘密恢復過程中需要很大的計算量。文獻[9]中提出了安全性僅依賴于單向函數的在線多秘密分享方案。該方案的一個顯著特點是計算量低；然而，在驗證成員的欺詐行為時，需要分發者相對于每一個待分享的秘密和授權子集做相同的工作，并且授權子集是分發者預先指定的，因而體制不靈活。

受文獻[8，9]方案的啟發，基于單向函數和大整數因子分解問題，提出了一個新 (t，n)的門限多秘密分享方案。本方案的突出優點是恢復秘密時需要的計算量小，并且可以容易地增刪成員。

1方案的建立

1．1系統初始化

秘密分發者（dealer，D）首先創建一個公告欄，以便向系統成員提供必要的公開參數。每個成員均可以訪問公告欄中的參數，但是只有D才能更改或刷新公告欄中的內容。然后，D定義如下參數：

3結束語

利用本文提出的動態的門限多秘密分享方案，每個參與者只需持有一個密鑰就可以分享任何一個秘密信息；并且該方案能夠同時檢測出分發者和分享者的欺詐行為。與已知的方案相比，本方案在秘密恢復階段需要的計算量更低，而且能容易地實現成員的加入或刪除。

參考文獻：

[1]SHAMIR A. Hoe to share a secret[J]. Communications of the ACM， 1979，22(11):612－613.

[2]HE J， DAWSON E. Multistage secret sharing based on one way function[J]. Electronics Letters， 1994，30(19):1591 1592.

[3]JACKSON W A， MARTIN K M， O’KEEFE C M. On sharing many secrets[C]//Proc of Advances in Cryptology ASIACRYPT’94. Berlin: Springer Verlag， 1994:42－54.

[4]STADLER M. Publicly verifiable secret sharing[C]//Proc of Advances in Cryptology EUROCRYPY’96. Berlin:Springer Verlag，1996:190 199.

[5]TOMPA M， WOLL H. How to share a secret with cheaters[J]. Journal of Cryptology，1988，1:133 138.

[6]HARN L. Efficient sharing (broadcasting) of multiple secret[J]. IEE Proc Comput Digit Tech， 1995，142(2):237－240.

[7]AOLLEMAN L， McCURLEY K. Open problems in number theoretic complexity[J]. Lecture Notes of Compute Science， 1994，877:291－322.

[8]CHANG T Y， HWANG M S， YANG W P.An improvement on the Liu Wu(t，n) threshold verifiable multi secret sharing scheme[J]. Applied Mathematics and Computation，2005，163:169 178.

[9]劉鋒，張建中.可公開驗證的秘密分享機制[J].蘭州大學學報:自然科學版，2006，42（2）：65－67.

[10]何明星， 范平志，袁丁.一個可驗證的門限多秘密分享方案[J]. 電子學報，2002，30（4）：540－543.

[11]費如純，王麗娜.基于RSA和單向函數防欺詐的秘密共享體制[J].軟件學報，2003，14（1）：146 150.

[12]NAOR D， NAOR M， LOTSPIECH J B. Revocation and tracing schemes for stateless receivers[C]//Proc of Advances in Cryptology CRYPTO’01. Berlin:Springer Verlag，2001:41－62.

[13]NAOR M， PINKAS B. Efficient trace and revoke schemes[C]//Proc of Financial Cryptography’00. Berlin:Springer Verlag，2000:1－20.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”