第13章秘密共享方案

報告人：

孫宗臣1ppt課件有些場合，秘密不能由一個人獨自擁有，必須由兩人或多人同時參與才能打開秘密，這時都需要將秘密分給多人掌管，而且必須有一定人數(shù)的掌管秘密的人同時到場才能恢復這一秘密，這種技術就稱為秘密分割(SECRETSPLITTING)，也稱為秘密共享(SECRETSHARING)。例如：導彈控制發(fā)射開啟核按鈕重要場所通行檢驗等為了實現(xiàn)上述意義上的秘密共享，人們引入了門限方案(THRESHOLDSCHEME)的一般概念2/13.1引言2ppt課件秘密分割門限方案的定義定義1設秘密S被分成N個部分信息，每一部分信息稱為一個子密鑰或影子(SHAREORSHADOW)，由一個參與者持有，使得：①由K個或多于K個參與者所持有的部分信息可重構S②由少于K個參與者所持有的部分信息則無法重構S

則稱這種方案為(K,N)－秘密分割門限方案，K稱為方案的門限值。極端的情況下是(N,N)－秘密分割門限方案，此時用戶必須都到場才能恢復密鑰3/13.1引言3ppt課件如果一個參與者或一組未經(jīng)授權的參與者在猜測秘密S時，并不比局外人猜秘密時有優(yōu)勢，即③由少于K個參與者所持有的部分秘密信息得不到秘密S的任何信息則稱這個方案是完善的，即(K,N)－秘密分割門限方案是完善的攻擊者除了試圖恢復秘密外，還可能從可靠性方面進行攻擊，如果他能阻止多于N-K個人參與秘密恢復，則用戶的秘密就難于恢復所以(K,N)門限的安全性在于既要防止少于K個人合作恢復秘密，又要防止對T個人的攻擊而阻礙秘密的恢復當N=2T+1時K=T=(N-1)/2的取值最佳秘密分割應該由可信第三方執(zhí)行，或者托管設備完成。4/13.1引言4ppt課件13.1引言秘密的分割

假設是一個(K,N)門限方案選取一個K－1次多項式F(X)＝A0+A1X+…+AK-1XK-1該多項式有K個系數(shù)令A0=F(0)=S，即把常數(shù)項指定為待分割的秘密其它K－1個系數(shù)可隨機選取顯然，對于該多項式，只要知道該多項式的K個互不相同的點的函數(shù)值F(XI)(I=1,2,…,K)，就可恢復F(X)生成N個子秘密任取N個不同的點XI(I=1,…,N)并計算函數(shù)值F(XI)(I=1,…,N)則(XI,F(XI)),I=1,…,N,即為分割的N個子秘密顯然，這N個子秘密中的任意K個子秘密即可重構F(X)，從而可得秘密S5/5ppt課件13.2SHAMIR門限方案SHAMIR門限方案基于多項式的LAGRANGE插值公式插值：數(shù)學分析中的一個基本問題已知一個函數(shù)(X)在K個互不相同的點的函數(shù)值(XI)(I=1,2,…,K)，尋求一個滿足F(XI)＝(XI)(I=1,2,…,K)的函數(shù)F(X)來逼近(X)，F(xiàn)(X)稱為(X)的插值函數(shù)，也稱插值多項式LAGRANGE插值：已知(X)在K個互不相同的點的函數(shù)值(XI)(I=1,2,…,K)，可構造K-1次LAGRANGE插值多項式顯然，如果將函數(shù)(X)就選定F(X)，則差值多項式剛好完全恢復了多項式(X)＝F(X)6/6ppt課件13.2SHAMIR門限方案根據(jù)上述的思想，在有限域GF(Q)上實現(xiàn)上述方案，即可得到SHAMIR秘密分割門限方案（1）秘密的分割設GF(Q)是一有限域，其中Q是一個大素數(shù)，滿足QN＋1秘密S是在GF(Q)\{0}上均勻選取的一個隨機數(shù)，表示為SRGF(Q)\{0}令S等于常系數(shù)A0其它K-1個系數(shù)A1,A2,…,AK-1的選取也滿足AIRGF(Q)\{0}(I=1,…,K-1)在GF(Q)上構造一個K-1次多項式F(X)＝A0+A1X+…+AK-1XK-1N個參與者記為P1,P2,…,PN，其中PI分配到的子密鑰為（I,F(I)）7/7ppt課件13.2SHAMIR門限方案(2)秘密的恢復如果任意K個參與者PI1,PI2,…,PIK(1I1<I2<…<IKN)要想得到秘密S，可使用它們所擁有的K個子秘密{(IL,F(IL))|L=1,…,K}構造如下的線性方程組A0＋A1(I1)＋…＋AK-1(I1)K-1=F(I1)A0＋A1(I2)＋…＋AK-1(I2)K-1=F(I2)……A0＋A1(IK)＋…＋AK-1(IK)K-1=F(IK)（13-1）8/8ppt課件13.2SHAMIR門限方案因為IL(L=1,…,K)均不相同，所以可由LAGRANGE插值公式構造如下的多項式：F(X)＝從而可得秘密S＝F(0)然而參與者僅需知道F(X)的常數(shù)項F(0)而無需知道整個多項式F(X)，所以令X＝0，僅需以下表達式就可以求出S：S=

，（可以預計算不需保密）9/9/方案的完善性分析如果K-1個參與者想獲得秘密S，他們可構造出由K-1個方程構成的線性方程組，其中有K個未知量對GF(Q)中的任一值S0，可設F(0)＝S0，再加上上述的K-1個方程就可得到K個方程，并由LAGRANGE插值公式得出F(X)。因此對每一S0GF(Q)都有一個惟一的多項式滿足13-1方程組所以已知K-1個子密鑰得不到關于秘密S的任何信息，因此這個方案是完善的。10/13.2SHAMIR門限方案10ppt課件【例8－1】設門限K=3，份額數(shù)為N=5，模值Q=19，待分割的秘密S=11，隨機選取A1=2，A2=7，可構造多項式F(X)=(7X2+2X+11)MOD19將秘密分割成5份分別計算F(1)=(7×12+2×1+11)MOD19＝1

F(2)=(7×22+2×2+11)MOD19＝5

F(3)=(7×32+2×3+11)MOD19＝4F(4)=(7×42+2×4+11)MOD19＝17F(5)=(7×52+2×5+11)MOD19＝6得5個子密鑰。11/13.2SHAMIR門限方案11ppt課件13.2SHAMIR門限方案秘密的恢復如果知道其中的3個子密鑰,如F(2)=5，F(xiàn)(3)＝4，F(xiàn)(5)＝6，就可重構F(X)，事實上我們可直接根據(jù)差值公式計算S=F(0)12/12/89ppt課件13.2SHAMIR門限方案簡化的（T,T）門限方案：D秘密的選取（獨立隨機選?。┲械腡-1個元素，記為

，D計算，對于，D把共享的值發(fā)給。13ppt課件中國剩余定理，又稱孫子定理設m1,m2,…,mk是k個兩兩互素的正整數(shù)，m=m1m2…mk,Mi(i=1,…,k)滿足m=miMi，則同余式組x=b1(modm1)x=b2(modm2)…x=bk(modmk)有唯一解：x=M1M1b1+M2M2b2+…+MkMkbk(modm)其中MiMi=1modmi

(i=1,2,…,k)14/(補充)基于中國剩余定理的門限方案14ppt課件1.參數(shù)的選擇設m1<m2<…<mn是n個大于1的整數(shù)，滿足(mi,mj)＝1(對任意的i，j，i≠j)，及兩兩互素，和m1m2…mk>mnmn-1…mn-k+2注意這里的條件m1<m2<…<mn是必須的，在此條件下，m1m2…mk>mnmn-1…mn-k+2表明最小的k個數(shù)的乘積也比最大的k-1個數(shù)的乘積大顯然，m1,m2,…,mn中任意k個數(shù)的乘積都比m1m2…mk大15/(補充)基于中國剩余定理的門限方案15ppt課件2.秘密的分割設s是待分割的秘密數(shù)據(jù)，令s滿足mnmn-1…mn-k+2<s<m1m2…mk即s比最大的k-1個數(shù)的成績大，同時比最小的k個數(shù)的乘積小從而：對任意k個數(shù)的乘積T，s＝smodT，模運算不起作用而任意k-1個數(shù)的乘積R有smodR在數(shù)值上不等于s16/(補充)基于中國剩余定理的門限方案16/為了分發(fā)秘密，計算m=m1m2…mn然后計算si=s(modmi)(i=1,2,…,n)以(si,mi,m)作為一個子秘密集合{(si,mi,m)}i=1n即構成了一個(k,n)門限方案17/(補充)基于中國剩余定理的門限方案17/秘密的恢復對任取的k個參與者，不失一般性，設這k個參與者為P1…Pk中，每個參與則Pi計算Mi＝m/mi，Ni＝Mi-1(modmi)，yi=siMiNi結(jié)合起來根據(jù)中國剩余定理可求得s＝由于任意k個或k個以上的模數(shù)相乘都比s大，它們恢復出來的s必然相同，而少于k個參與者則不行18/(補充)基于中國剩余定理的門限方案18/13.3訪問結(jié)構和一般的秘密共享定義：在W

個參與者（記為集合P）中共享密鑰K的方法稱為是實現(xiàn)訪問結(jié)構的一個完善的秘密共享方案，如果滿足以下兩個條件：（1）對于一個授權的參與者子集，如果把他們的共享集中到一起，那么就可以確定密鑰K的值。

（2）對于一個未授權的參與者子集，如果把他們的共享集中到一起，那么他們也不能確定關于K值的任何信息。如果且，則，我們稱訪問結(jié)構滿足單調(diào)性（本章假設均為單調(diào)）19ppt課件13.3訪問結(jié)構和一般的秘密共享設是一個訪問結(jié)構，稱是一個最小授權子集，如果對于任何滿足和

的集合A都有。的最小授權集合記為，稱為的基。在（T,W）門限訪問結(jié)構的情況中，基恰好是由所有T個參與者的所有子集組成。定義：子集是最大的非授權子集，如果對于所有的，都有。

20ppt課件13.3.1單調(diào)電路構造設我們得到布爾公式算法：單調(diào)電路構造（C）當存在線使得未定義時，循環(huán)以下操作：找到C的一個門G使得已經(jīng)被定義，其中是G的輸出線，但是對于G的任意出入線來說，都沒定義過。

（1）如果G是一個“或”門，那么對于G的每一個輸入線W，

（2）否則，令G的輸入線是，獨立的選擇中的個元素，記為

FORDO21ppt課件例題A

非授權子集13.3.1單調(diào)電路構造22ppt課件變成合取范式：例題B定理：設C是任意的單調(diào)布爾電路，則單調(diào)電路的構造可產(chǎn)生一個能夠?qū)崿F(xiàn)訪問結(jié)構的完善秘密共享方案。（略）13.3.1單調(diào)電路構造非授權子集23ppt課件假設是一個訪問結(jié)構并且是分發(fā)規(guī)則的集合。我們稱是一個實現(xiàn)訪問結(jié)構

的完善秘密共享方案，如果下面兩個性質(zhì)：對于任何的授權子集，不存在兩個分發(fā)準則和，其中使得（即對于授權子集B中的參與者，共享的任何分發(fā)都可以確定密鑰K的值）對于任何非授權子集和任何共享的分發(fā)，有下式成立

對于任意（即對于非授權的子集B，給定共享的分發(fā),K上的條件概率分布和K上的先驗概率分布是相同的。換句話說，B的共享的分發(fā)沒有提供關于K值的任何信息）13.3.2單調(diào)電路構造(正式定義)24ppt課件定義：假設我們有一個實現(xiàn)訪問結(jié)構的完善秘密共享方案。的信息率定義為比率（注意，表示所有可能收到的共享集合：當然，）。方案的信息率記為并定義為例題：，（）因此例題：

所以。我們更傾向于方案一，其信息率高些。13.4信息率和高效方案的構造25ppt課件定理13.2：設C是任意的單調(diào)布爾電路，則存在一個實現(xiàn)訪問結(jié)構的完善秘密共享方案，其信息率是其中是C中帶有輸入線的根數(shù)。可以看出，shamir門限方案的信息率是1，下面會證明這是一個最優(yōu)值。相比之下，使用析取范式的布爾電路實現(xiàn)的（t,w）門限方案的信息率是，當這是一個非常低的值（因此是不佳的）定理13.3：對于實現(xiàn)一個訪問結(jié)構的任何完善的秘密共享方案，都有。13.4信息率和高效方案的構造26ppt課件設是一個訪問結(jié)構，是上所有d元組組成的向量空間，假設存在函數(shù)滿足性質(zhì)話句話說，向量可以表示為中向量的線性組合當且僅當B是一個授權子集。對于給定的訪問結(jié)構，只要我們找到滿足該性質(zhì)的向量的集合，那么就可以建立相應的秘密共享方案，這個方案被稱為Brickell秘密共享方案。13.4.1向量空間構造27ppt課件密碼體制13.3

Brickel秘密共享方案輸入：滿足上述性質(zhì)的向量初始化階段對于，D把向量給D，這些向量公開。共享分發(fā)假設D想要共享密鑰K。D定義，并且他秘密的選擇中的d-1個元素對于，D計算，其中對于，D把的值作為共享分發(fā)給。

13.4.1向量空間構造28ppt課件定理13.4假設滿足性質(zhì)，則分法規(guī)則，的集合組成了一個實現(xiàn)訪問結(jié)構的理想秘密共享方案。證明：首先，我們證明如果B是一個授權子集，那么B中參與者能夠計算K。因為

所以我們將其寫成其中每個。的共享是，其中

是由D選定的未知向量，并且.由內(nèi)積運算的線性性，可得

13.4.1向量空間構造29ppt課件如果B不是授權子集，假設對于某個，B假設。我們證明這樣的猜測和她們所擁有的信息是一致的。我們用表示子空間的維數(shù)考慮方程組：這是一個含有個未知量的線性方程組，因為則這個方程組是相容的，系數(shù)矩陣的秩是，解空間的維數(shù)為

（對任意的值這樣在每個恰好有個分發(fā)規(guī)則，這和B共享的可能分發(fā)是一致的。有

13.4.1向量空間構造（詳解參考例題13.8）30ppt課件定理13.5假設是一個完整的多劃分圖，則存在一個理想秘密共享方案實現(xiàn)了參與者V上的基為E

上的訪問結(jié)構。13.4.1向量空間構造31ppt課件32ppt課件33ppt課件定義13.5設是一個訪問結(jié)構，是分布規(guī)則的集合，則稱是實現(xiàn)訪問結(jié)構的一個完善的秘密共享方案，如果滿足以下兩個條件：對于任何參與者的授權子集，。對于