门限解密算法
门限密码系统是在秘密分享方案的基础上构建出来的一种加密原语。在一个$(t,n)$的门限密码方案中，私钥被划分为$n$个份额，每个份额都被分配给不同的参与协议的服务器。加密者使用对应公钥加密消息$M$得到的密文$C$，至少需要$t \le n$个服务器参与解密。参与者使用自己的私钥份额对密文$C$解密得到一个解密份额，$Combiner$收集到$t$个参与者正确的份额后才能够恢复出正确的明文，而已知任何少于$t$份解密份额均不能获得原始明文的任何信息。从而能够在防止单点故障、实现权力分散等方面得到应用。
一个好的门限密码应该具有如下性质：
-
每个参与者都能够检测密文$C$的有效性。
-
$Combiner$能够检测参与者提交的解密份额的有效性，即能够识别成员中的欺骗者。
-
无法从部分解密中获得关于原始明文的任何信息。
一个非交互式的$(t,n)$门限解密方案由以下算法组成：
$\textbf{Setup}(\lambda,t,n)$：输入一个安全参数$\lambda$，和整数$t,n\in\textbf{poly}(\lambda)$($1\leq t\leq n$)，$n$表示参与协议的服务器数量，$t$表示门限。该算法输出$(PK,VK,SK)$，$PK$表示公钥，$SK=(SK_1,…,SK_n)$表示私钥份额的向量，$VK=(VK_1,…,VK_n)$表示验证密钥份额的向量。私钥份额$(i,SK_i)$分配给对应的每个参与协议的服务器$i$，验证密钥$VK_i$将用于检查使用$SK_i$部分解密得到的解密份额的有效性。
$\textbf{Encrypt}(PK,M)$：是一个随机的算法，输入公钥$PK$和明文$M$，输出密文$C$。
$\textbf{Ciphertext-Verify}(PK,C)$：输入公钥$PK$和密文$C$，如果$C$是关于$PK$的有效密文则输出$1$，否则输出$0$。
$\textbf{Share-Decrypt}(PK,i,SK_i,C)$：输入公钥$PK$，密文$C$，私钥份额$(i,SK_i)$，如果$Ciphertext-Verify(PK,C)=0$，则此算法输出特殊符号$(i,\perp)$。否则输出$i$的解密份额$\mu_{i}=\left(i, \hat{\mu}_{i}\right)$。
$\textbf{Share-Verify}(PK,VK_i,C,\mu_{i})$：输入公钥$PK$，验证密钥$VK_i$，密文$C$，待验证的解密份额$\mu_{i}=\left(i,\hat{\mu_i}\right)$。如果$\mu_{i}$是一个有效的解密份额，则输出1，如果是一个无效的解密份额$(i, \perp)$，则输出0。
$\textbf{Combine}(PK, \mathbf{VK}, C,{(\mu_{i}})_{i \in S})$：输入公钥$PK$，验证密钥$VK$，密文$C$，对于集合$S \subset${${1, \ldots, n}$}，且有$t=|S|$，$S$中每一个参与者输入各自的解密份额${(\mu_{i}})_{i \in S}$。如果该集合中的参与者提交了无效的解密份额，使得${Share-Verify}(PK,VK_i,C,\mu_{i})=0$，则算法输出$\perp$，否则输出明文$M$。
