基于二元多項式與中國剩余定理的多秘密分享方案

黃科華

(泉州幼兒師范高等?？茖W校初等教育系，福建泉州362000)

秘密分享方案的主要目的是用來解決在特定用戶(準入結構)中分享一個秘密.一個秘密分享方案(SSS)主要包含以下幾個方面:秘鑰分發者D，參與用戶集合P，準入結構Γ，秘鑰空間S，分配算法和恢復算法.

Shamir［1］和 Blakley［2］與1979年分別獨立提出了(t，n)門限秘密分享方案，通過該方案，n用戶中只要有t個及以上的人合作就能合成秘鑰，而少于t個用戶就得不到秘鑰的任何信息.當然，兩個方案都存在許多不足的地方，如1)秘密份額是一次性的，不能重復利用;2)秘鑰分發者的權利過大，有可能導致秘鑰分發者的欺騙，比如發送無效的份額;3)每次只能共享一個秘鑰，秘鑰的信息不夠大等.在兩個方案的基礎上，Asmuth和Bloom［3］在1983年提出的基于中國剩余定理的門限方案;Brlckell［4］等人在1991年提出了理想化的秘密共享方案;黃科華［5］結合單向函數和二元多項式的方案解決了秘鑰的一次性使用的問題，本文正是在此基礎上，利用中國剩余定理，提供了一個多秘密的分享方案，而且在這個方案中，引入可驗證的秘鑰機制，來避免秘鑰欺騙.

1 預備知識

1.1 陷門單向函數

陷門單項函數h(x)滿足以下兩個條件，(i)給定x，能夠容易地計算y=h(x);

(ii)給定y，計算x=h－1(y)是困難的，但是如果知道陷門，可以容易地計算出y.

陷門單向函數可以選擇離散對數函數或者RSA函數等.

1.2 中國剩余定理

設整數 m1，m2，…mn兩兩互質，對于任意整數 s1，s2，…sn，方程組:

2 基于二元多項式與中國剩余定理的多秘密分享方案

2.1 秘鑰生成和分發階段

設有n個用戶為P1，P2，…Pn.每個Pj自己選取一個向量作為自己的私鑰(且yij≠ymn，i≠m 或者 j≠ n)，并計算 h(yij)，i=0，1，2，…t，j=1，2，…n.其中h(x)為無碰撞陷門單向函數，由秘鑰分發者D選取并公布，陷門信息由D掌握.

設s1，si，…sn是需要分享的多個秘鑰，秘鑰分發者D選擇n個互質的整數 m1，m2，…mn，通過中國剩余定理得到modM的唯一解S.

D構造一個二元多項式f(x，y)，表達式如下:

并使得a00=S(常數項為秘鑰S)

D 計算 f(xi，yij)，i=0，1，2，…，t，j=1，2，3，…，n.并公布.

2.2 秘鑰的合成過程

不妨設 f(xi，yij)=Aij，i=0，1，2，…，t，j=1，2，3，…，n

三個月前，他們瞞著所有的人，寫了一份分手協議，分配了財產。但他們彼此各退一步，商定等孩子三年后上了大學，再公布于眾。按照協議規定，他們互不打探干涉對方的私生活，仍在一個屋檐下或者另租居所，不過，每月孩子回來的那天必須琴瑟和鳴夫唱婦隨。

t+1個用戶合作可以通過以下方式恢復二元多項式，取得S.

從公告牌中的 xi，(i=0，1，2，…，t)可以得出下列方程組:

即

t+1 個用戶可以拿出 yij0，yij1，…，yijt，

其中 0 ≤ j0，j1，…，jt(均為正整數)≤ n，i=0，1，2，…，t

代入(2)式可得:

(3)可以寫成方程組:

也即是以下的矩陣:

由(2)式可得下列方程組:

其中 j=0，1，2，…，t.

寫成矩陣即為:

由于xi≠xj，i≠j，所以系數矩陣為范德蒙矩陣，能夠解出唯一解:

因為能夠合成整個二元多項式，取得S.

取得S后，每個用戶可以再從公布的m1，m2，…mn中解出所有的秘鑰 s1，si，…sn.

3 分析

3.1 滿足門限性

從方案中可以看出，該方案為(t+1，n)門限方案，t+1個人合作可以順利恢復秘鑰，而少于t+1，就無法從方程組4(或者矩陣 5)中恢復出(Bi0，Bi1，…，Bit)，i=0，1，2，…，t，因而，也無法從方程組6(或者矩陣7)中恢復出系數(a0j，a1j，…，atj)，j=0，1，2，…，t，故不能得到密鑰 S.

3.2 多秘密分享

利用中國剩余定理，把多個秘密封裝成S進行分發，合成用戶可以通過公布的m1，m2，…mn取得多個秘鑰.

3.3 不需要安全信道和秘鑰可以多次使用

由于使用了陷門單向函數，所有的交流都可以在公用信道上達成，整個秘密共享的過程不需要任何的安全信道.而且，公布在外面的只是h(yij)，用戶的份額沒有泄露，所以份額可以多次使用.

3.4 防止分發者的欺騙

由于秘密份額是用戶自己選擇并發布的，所以任何用戶都可以通過公布的h(x)驗證分發者提供的份額是不是正確的.這限制了分發者的權利.

3.5 方便系統更新

當完成一次秘密分享以后，秘鑰分發者D只需要更新陷門單線函數h(x)即可.

4 結語

本文是文［5］的進一步改進，除了繼承文［5］的優點之外，該系統不需要安全信道，并且防止了秘鑰分發者D的欺騙，是可驗證的秘密分享方案.

［1］Shamir A.How to share a secret［J］.Communications of the ACM，1979，(11):612－613.

［2］Blakley G R.Safeguarding cryptographic keys［A］.Managing Requirements Knowledge，International Workshop on［C］.IEEE Computer Society，1899.

［3］Asmuth C，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory，1983，(2):208－210.

［4］Brickell E F，Davenport D M.On the classification of ideal secret sharing schemes［J］.Journal of Cryptology，1991，(2):123－134.

［5］黃科華，熱娜·艾合買提，張瑛瑛.基于單向函數與二元多項式的秘密分享方案［J］魯東大學學報(自然科學版)，2014，(3):223－227.