《密码协议》课程笔记（5） 门限密码协议
门限密码
- 动机：有时候，只有一方控制的访问是不可取的（密钥的所有权仅属于一方是不合理的），因此密钥的所有权需要分布给多方（群签名、给一个组织发消息）
- 门限密码：面向组的密码学，在多个参与方中分发密码。例如，10个人有数字签名私钥，但签名需要7人以上的参与——秘密共享方案是基础
秘密共享方案
将秘密分成多份，有足量的份数时，秘密可以被重建，否则不能重构秘密或其中任何部分——
(t,l)秘密分享方案将一个秘密分割为l份，至少t个才能重构，t称为断点（breaking point）类似多项式：多项式f的阶为
t-1，则需要t个多项式上的点才能确定f(0)一旦t个人通信，恶意内部人员可以获得密钥——需要一个能解密和签名但不泄露密钥的系统
（举了一个例子说明了）将一个比特串直接分成两块或更多块不是共享秘密的安全方法，并且不适用于长度为1的串
- 对于秘密比特$s$，选择一个随机的比特$r$，并设置shares $s_1=s\bigoplus r$，$s_2=r$，此时$s_1$和$s_2$不会泄露$s$，并且$s_1\bigoplus s_2=s$
- 如果$r$是均匀分布的，则$Pr(s_1=0)=Pr(r=s)=1/2$（r和s独立，并且r=1和r=0概率均为1/2），因此$s_1$和$s_2$都是均匀分布（$s_2=r$）
- 进一步，可以随机选择$l-1$个比特$r_i$，计算$s_1=s\bigoplus r_1\bigoplus … \bigoplus r_{l-1},s_2=r_1,…,s_l=r_{l-1}$
具有参与者$P_1,…,P_l$的秘密共享方案包含：分发协议（一个协议使得deal D分享一个秘密s，每个参与者获得一个share $s_i$），重建协议（一个协议使得秘密s能够通过任何一组合格参与者的秘密片段恢复，这里参与者是$P_1,…,P_l$的子集）——所有这种子集构成的集合称为access structure
安全需求（满足安全需求的秘密共享方案称为perfect）
- 符合条件的参与者集可以通过shares确定s
- 不符合条件的参与者集都不能通过shares确定关于s的任何信息
(t,l)门限密码
access structure定义为：
shamir’s threshold scheme：
$F_p$为p阶有限域，$p>l$，分享的秘密$s\in Z_p$
秘密分发：分发者D选择一个$t$阶随机多项式$a(x)\in_R Z[x]$，$a(0)=s$，分发$s_i=a(i),i=1,..,n$
秘密重构：利用拉格朗日插值法恢复
是perfect的（少于t人参与重构时，任何$a(0)$都是可能的）
只能抵抗被动攻击（如果分发者发给参与者的碎片是不正确的，参与者无法察觉，并且如果重构时某个参与者唯一不用正确的碎片，他可以从其他参与者的正确碎片恢复秘密），安全性依赖于方案中各方诚实执行协议，诚实执行后不合格参与者不能推断出关于秘密的信息
抵御主动攻击的秘密共享方案——可验证的秘密共享（verifiable secret sharing, VSS）方案——抵御主动攻击：分发时，分发者向部分或全部参与者发送不正确的碎片，并且重构时，参与者提交不正确的碎片
Feldman’s VSS
shamir方案的推广；$p$为大素数，$
$为p阶循环群，$s\in Z_p$ 分发：
分发者选取一个多项式$a(x)=s+a_1x+…+a_{t-1}x^{t-1},a_j\in Z_p$，将$s_i=a(i)$分发给参与者，计算并广播承诺$B_j=g^{a_j},0\leq j<t$
参与者验证下式是否成立，以检查分发者是否诚实
重建：执行shamir门限秘密分享方案即可；如果少于t个参与者能够重构原始秘密，意味着$s=log_gh$被求解，因此离散对数问题是困难的假设下，少于t个参与者不能计算秘密——计算安全
Pedersen‘s VSS
shamir+承诺，信息论安全（由于是Pederson commitment）
$
$为素数p阶循环群，h为群里的随机元素，因此没人知道离散对数$log_gh$ 分发：
- 分发者随机选择两个多项式：$a(x)=a_0+a_1x+…+a_{t-1}x^{t-1},a_j\in Z_p$和$b(x)=b_0+b_1x+…+b_{t-1}x^{t-1},b_j\in Z_p$，$a_0=s$，碎片$s_i=(a(i),b(i))$
- 分发者广播承诺值$C_j=g^{a_j}h^{b_j}$
重建：
参与者验证：
执行shamir门限秘密分享的重构算法，以恢复秘密
方案中，承诺与秘密相关的只有$C_0=g^sh^{b_0}$，而对任意的$\hat s\in Z_p$，都有唯一的$\hat b\in Z_p$使得$C_0=g^{\hat s}h^{\hat b}$，因此$C_0$没有泄露s的任何信息
如果分发者知道$log_gh$，则可以作弊
