原文教材 與 參考資料：
Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography[J].
該書項目位址（可以免費擷取）：http://toc.cryptobook.us/
部落格為對該書的學習筆記，并非原創知識，幫助了解，整理思路。
11.6 門限解密
門限解密提出的動機：
1. 密鑰伺服器存儲的sk, 如果遭受盜用攻擊，那麼将威脅所有在該伺服器存儲密鑰的使用者安全。
2. 如果将密鑰分割為若幹個部分，每次解密需要多個伺服器均等的參與解密，那麼如果有一方不參與解密，該解密過程将會失敗，這種方案易用性和時效性不強，是以并不現實。
3. 采用門限的方式，任何的達到門限的參與者就可以完成解密。
門限解密的系統模型如下：
需要使用combiner 将部分密文組合，進而解密所有的明文資訊，這最終達到了不在同一個處理器上恢複出全部的密鑰資訊，不過随着s的不斷增大，算法效率會降低，（例如SS的次數越高計算複雜度越高）
下面給出門限解密的形式化定義：
11.6.1 Shamir's secret sharing scheme
SS 秘密分享協定是第一個（t,n）門限秘密分享協定：
首先形式化的定義一個（t,n）門限秘密分享協定如下：
如果任意的兩個秘密值構造的份額組分布是相同的，則證明該秘密分享協定是安全的。
Shamir secret sharing :
該協定的核心是使用拉格朗日內插補點公式：
核心思想就是通過t個點來恢複出該最高指數為t-1的多項式，然後取f(0) = 秘密值，所有的點數為N個(N > t), 任意t個人可以使用他們自己的坐标完成秘密值的恢複。
11.6.2 EIGamal threshold decryption
EIGamal 門限加密方案使用系統公鑰和加密方的随機數作為對稱加密的私鑰生成元素，然後使用對稱加密來完成對明文的加密。這裡需要注意的是，該方案應當不能算作是一個KEM密鑰封裝機制，密鑰封裝指的是發送方使用接受方的公鑰對會話密鑰（對稱的）進行加密，随後雙方通過會話密鑰進行通信。
EIGamal 門限解密的算法流程如下：
安全性分析：
這裡證明了該門限解密方案是語義安全的，安全定理與證明過程如下：
首先設計實驗如下：
我們的目的是證明該門限解密方案是語義安全的，那麼直覺上我們就應該合理的聯想到如何把語義安全遊戲和該方案結合起來，依照我們先前的經驗，應該是語義安全敵手可以調用攻擊本方案的敵手A赢得SS挑戰遊戲，在進一步設計之前，我們首先确定攻擊本文方案的敵手A的具體攻擊能力：
1.按照秘密分享的安全性定義，敵手在擷取到t-1個門限份額時，依然不能夠獲得恢複秘密值的能力。是以，我們抽象這個敵手的能力為該敵手可以直接向其挑戰者擷取t-1個門限份額的能力, 并且敵手能夠詢問獲得t-1個部分密文的解密資訊，即敵手擷取所有的部分密文依然無法獲得解密m的資訊。
2.因為我們要證明該方案是語義安全的，對于語義安全而言，定義比較簡單敵手B能夠猜測正确他的挑戰者加密的是哪一條消息，即赢得了該遊戲即攻破語義安全實驗。
3.進一步，對于安全證明而言，我們需要将這個兩個安全需求聯系起來，直覺上如果敵手B能夠調用A，那麼這個聯系就直接的被建立了起來。
是以我們定義實驗如下：
敵手A具備兩個詢問能力：
安全性定理描述如下：
規約調用圖如下所示：
1. A 需要将其可以獲得的系統資訊包括t-1個門限的資訊發送給敵手B（應當預設這些資訊是公開的）。
2. B扮演A的挑戰者角色，A可以向B發起兩種詢問，一種是部分解密詢問，一種是解密猜測詢問。
3. 由B将解密猜測詢問發送給SS挑戰者，然後由SS挑戰者使用EIgamal加密公鑰進行加密，并将密文傳回，B再将該密文發送給敵手A。
4. B最終輸出A輸出的猜測比特。
此處的難點在于，如何讓B傳回給A相應的部分解密密文？這裡分為兩種情況。
第一種情況：對于t-1個解密私鑰，B是掌握的，直接運作解密算法即可得到t-1個部分密文。
第二種情況：因為少一個解密私鑰，但是我們依然需要給A這個缺少的部分密文，我們需要使用如下方法計算得到這個部分密文：
雖然B不知道alpha,但是B可以計算所有lamda的值，因為不知道其中的某個y, 是以B是無法獲得alpha的。
進一步，B通過以下的式子可以獲得唯一的不知道y的部分解密密文：
至少可以說是能夠通過驗證的密文c` = v^y。
綜上所述，如果本方案是語義安全的，那麼敵手A的優勢是可以忽略的。
另外此處可以進一步構造一個CDH敵手？答案是不可以，CDH假設要求是g^a,g^b,計算g^ab。