前言
想做一个基于zkp的门限签名方案，因此需靠看一下之前的门限签名怎么做的，然后想一下怎么用zkp
概述
$(l,k)$-门限签名简单来说在一个$l$个参与方的集合中，允许任意数量为$k$的参与方生成签名的协议，若参与方数量少于$k$，则无法生成有效的签名，且即便少于$k$个参与方的子集被攻破且共谋，也不可以伪造一个合法的签名值，该性质也被称为不可伪造性（non-forgeability）
此外门限方案还应该具备鲁棒性（rubost），也即若某些参与方被攻破时，这些参与方不能阻止仍然诚实的参与方生成签名值
门限签名方案的概念已被广泛研究，但是先前的方案都存在下列问题
- 即便在Random Oracle模型中也没有较为严格的安全性证明
- 签名共享生成和（或）验证为交互性的，也即需要网络环境同步
- 单个签名共享的大小与参与方的数量呈线性关系
为了纠正这种情况，本文提出了一种新的阈值RSA签名方案，该方案具有以下特性
- 假设RSA问题是困难的，方案在Random Oracle模型下是不可伪造的且具有鲁棒性
- 签名共享生成与验证完全非交互
- 单个签名共享大小的界为常数乘RSA模数
本文考虑了一个更精细的阈值签名方案的概念，其中一个阈值$t$表示最大被攻破参与方数，另一个阈值$k$表示最小平方的大小，若特定消息已被签名，则意味着至少有$k-t$个未被攻破的参与方认证该签名
之前对门限签名方案的研究总是（显示或隐式）假设$k=t+1$，本文研究了推广的模型，也即$k\geq t+1$，若未被攻破的参与方不一定承认他们签名的内容，但希望能够证明他们中的许多人已经认证了特定的签名，则这种推广后的模型非常有用（比如说$k=l-t$且$t<l/3$的设置在异步网络的拜占庭共识协议中对于减少消息大小很有用）
本文采用静态corruption模型：敌手必须在攻击开始时选择需要攻击的参与方，这与先前对门限签名的研究一致（都显示或隐式的假设在静态corruption模型分析）
本文提出了两个协议，Protocol 1仅假设标准RSA签名时安全的，此时需要利用Random Oracle增强鲁棒性，Protocol 2也用了RO模型，但是更简单和高效
1 System model and security requirements
The participants
假设有一个数量为$l$的参与方集合（以$1,...,l$标记），一个可信处理方（dealer）和一个敌手，此外还有签名验证算法，共享验证算法和共享组合算法
系统参数为两个，$t$表示被攻破的参与方数量，$k$表示得到合法签名所需的共享签名数，要求$k\geq t+1,l-t\geq k$
The action
游戏开始时，敌手在参与方集合中选择$t$个玩家的子集进行攻击
在处理阶段，处理方生成一个公钥$PK$和一系列共享私钥$SK_1,...,SK_l$，验证密钥$VK_1,...,VK_l$，敌手可以得到被攻破的参与方的公钥、共享私钥和验证密钥
处理阶段后，敌手对其需要签名的消息向其他未被攻破的参与发发起签名请求，根据这样的请求，参与方输出给定消息的签名共享
Robustness and combining shares
签名验证算法：以消息、签名值和公钥作为输入，并输出是否接受该签名值
签名共享验证算法：以消息，第$i$个参与方的签名共享、$PK,VK,VK_i$作为输入，并输出是否接受该签名值
共享组合算法：以消息、$k$个关于该消息的合法签名共享、公钥和（可能需要的）验证密钥作为输入，并输出是否接受该签名值
Non-forgeability
若游戏结束时，敌手对未作为签名请求提交给至少$k− t$个未被攻破的参与方的消息上输出了一个合法的签名值，则称敌手伪造了一个签名
若敌手的伪造签名行为在计算上不可行，我们说门限签名方案是不可伪造的
Discussion
我们的模型明确要求签名共享的生成和验证是完全非交互的
注意到系统中的两个独立的参数$t$和$k$，之前对门限签名的研究只处理了$k=t+1$的情况，此类情况下的不可伪造性只是要求：若没有要求未被攻破的参与方签名，则签名是伪造的
本文讨论了当$k>t+1$时实现不可伪造性比当$k=t+1$时更难，为了简单起见，接下来从$k=t+1$的情况开始
2 Protocol 1:a very simple RSA threshold scheme
接下来介绍Protocol 1
The dealer
处理方随机选择两个长度相等的大素数（512 bit或更长），记为$p,q$，满足$p=2q'+1,q=2p'+1$，且$gcd(p',q')=1$，模数$n=pq$
记$m=p'q'$，处理方选择RSA公共指数$e$，满足$e>l$，然后处理方计算$d\in \Z$，满足$de\equiv 1 \ mod \ m$（注意这里和RSA不同，模数不是$\phi(n)$）
接下来令$a_0=d$，对于所有的$1\leq i\leq k-1$，随机选择$a_i\in_R\{0,...,m-1\}$，之后定义多项式$f(X)=\sum^{k-1}_{i=0}a_iX^i\in \Z[X]$
然后对于$1\leq i\leq l$，处理方计算第$i$个参与方的私钥$s_i$如下
$$ s_i=f(i)\ mod \ m\tag1 $$
记$Q_n$为$\Z^*_n$中的平方构成的子群，处理方随机选择$v\in_R Q_n$，对于$1\leq i\leq l$，计算$v_i=v^{s_i}\in Q_n$，然后令验证公钥$VK=v$，各个参与方的验证密钥为$VK_i=v_i$
Some preliminary observations
注意到$\Z^*_n\simeq \Z_m\times \Z_2\times\Z_2$，若令$J_n$表示元素$x\in \Z^*_n$中雅可比符号为1的元素构成的集合（也即$J_n=\{x|x\in \Z^*_n\wedge(\frac{x}{n})=1\}$），此时有$Q_n\sub J_n\sub \Z^*_n$（$Q_n\sub J_n$是因为$Q_n$为$\Z^*_n$中的平方构成的子群），此外还可以知道$Q_n$为阶为$m$的循环群，$J_n$为阶为$2m$的循环群，且$-1\in J_n\backslash Q_n$
一般而言，我们需要确保所有群计算在$Q_n$中，相应的指数计算在$\Z_m$中，因为$m=p'q'$没有小的素因子，所以这不难做到
由于处理方随机选择，我们可以假设$v$是$Q_n$的生成元（尽管这个事件发生的概率可忽略不计），因此$v_i$完全由$s_i \ mod \ m$决定
对于集合$\{0,...,l\}$中任意大小为$k$的子集而言，多项式$f(X) \ mod \ m$在这些子集中的点的取值唯一确定了的$f(X) \ mod \ m$系数，这也意味$f(X) \ mod \ m$确定了集合$\{0,...,l\}$中其他点的值（$f(X)$是阶为$k-1$的多项式，因此$k$个点可以唯一确定这个多项式，换言之，这个多项式对应的范德蒙行列式与$m$互素，因此该范德蒙行列式对应的矩阵在模$m$下可逆）
因此对于集合$\{1,...,l\}$中任意大小为$k-1$的子集，对于这些子集中的点，多项式$f(X) \ mod \ m$的取值相互独立且是一致均匀分布的
接下来记$\Delta=l!$，对于集合$\{0,...,l\}$中任意大小为$k$的子集$S$，对于任意$i\in \{0,...,l\}\backslash S,j\in S$，定义$\lambda^S_{i,j}$如下
$$ \lambda^S_{i,j}=\Delta\frac{\prod_{j'\in S\backslash\{j\}}(i-j')}{\prod_{j'\in S\backslash\{j\}}(j-j')}\in \Z\tag2 $$
这些值由拉式插值法得到，且显然是整数，因为分母可以整除$j!(l-j)!$，意味着其可以整除$l!$，此外，根据拉式插值法，可以得到
$$ \Delta \cdot f(i)=\sum_{j\in S} \lambda^S_{i,j}\cdot f(j) \ mod \ m\tag3 $$
Valid signatures
接下来描述合法的签名的形式，这里需要一个Hash函数$H:\{0,1\}^*\rarr\Z^*_n$，对于消息$M$，若$x=H(M)$，则存在$M$的合法签名值$y\in\Z^*_n$，满足$y^e=x$（标准RSA签名形式）
Generating a signature share
接下来介绍如何对消息$M$生成一个签名共享
令$x=H(M)$，第$i$个参与方的签名共享计算如下
$$ x_i=x^{2\Delta s_i}\in Q_n\tag4 $$
同时再计算一个正确性证明，正确性证明是一个基于$\widetilde x$的$x^2_i$的DLOG，首先$\widetilde x$计算如下（其和基于$v$的$v_i$DLOG类似，两个的指数上都有$s_i$）
$$ \widetilde x=x^{4\Delta}\tag5 $$
这样一来我们可以通过Hash函数来创建挑战，从而将协议变为非交互式的（这也是方案中需要Random Oracle的地方）
接下来记函数$L(n)$表示$n$的比特长度，$H'$为输出长度为$L_1$的Hash函数（$L_1$为安全参数，比如$L_1=128$），构建证明的正确性时，第$i$个参与方选择一个随机整数$r\in _R\{0,...,2^{L(n)+2L_1}-1\}$，然后计算
$$ \begin{aligned} v'&=v^r\\ x'&=\widetilde x^r\\ c&=H'(v,\widetilde x,v_i,x^2_i,v',x')\\ z&=s_ic+r \end{aligned} $$
然后得到正确性证明为$(z,c)$，验证正确性证明需要计算
$$ c=H'(v,\widetilde x,v_i,x^2_i,v^zv_i^{-c},\widetilde x^zx_i^{-2c}) $$
这里有一个点，采用$x^2_i$计算而不是$x_i$的原因在于尽管$x_i$是二次的，但是并不好验证，为了确保在群$Q_n$上计算，因此需要确保可靠性
Combining shares
假设我们已经有了关于集合$S=\{i_1,...,i_k\}\sub \{1,...,l\}$的合法共享，接下来令$x=H(M)\in Z^*_n$，同时假设$x^2_{i_j}=x^{4\Delta s_{i_j}}$，则组合共享如下
$$ w=x_{i_1}^{2\lambda^S_{0,i_1}}...x_{i_k}^{2\lambda^S_{0,i_k}} $$
其中$\lambda^S_{0,i_k}$为式(2)定义的那个，根据式(3)，有$w^e=x^{e'}$，其中
$$ e'=4\Delta^2\tag6 $$
又由于$gcd(e',e)=1$，因此利用扩展欧式算法可以得到$e'a+eb=1$，然后令$y=w^ax^b$，就可以得到$y^e=x$
3 Security analysis of Protocol 1
先看一个定理
- Theorem 1：对于$k=t+1$，将$H'$视为Random Oracle，若假设标准RSA签名方案为安全的，则Protocol 1为一个安全的门限签名（满足鲁棒性和不可伪造性）
接下来看一下，在有权访问RSA的签名预言机时如何模拟对手的视图（只有当敌手要求一个正常的参与方提供签名共享时才使用）
令$i_1,...,i_{k-1}$为被攻破的参与方，根据前面提到的，对于所有的$1\leq i\leq l$，有$s_i\equiv f(i) \ mod \ m$，以及$a_0=d\equiv f(0)\ mod \ m$
为了模拟敌手的视图，我们只需从集合$\{0,...,\lfloor n/4 \rfloor-1\}$中随机选择属于被攻破的参与方的集合$s_{i_j}$，根据前面的定义，被攻破的参与者的共享密钥是集合$\{0,...,m-1\}$中的一个随机数，因此我们有
$$ \frac{n}{4}-m=\frac{p'+q'}{2}+\frac{1}{4}=O(n^{0.5}) $$
上述计算可以得到这个一个结论：集合$\{0,...,\lfloor n/4 \rfloor-1\}$与集合$\{0,...,m-1\}$之间的统计距离为$O(n^{-0.5})$
因此，一旦选择了值$s_{i_j}$，意味着模$m$下正常的参与方的私钥$s_i$也就确定了，但是由于DLOG的困难性，这个值并不能被轻易的算出来
不过对于给定$x,y\in\Z_n^*$，满足$y^e=x$，很容易计算第$i$个被攻破的参与方的$x_i=x^{2\Delta s_i}$如下
$$ x_i=y^{2(\lambda^S_{i,0}+e(\lambda^S_{i,i_1}s_{i_1}+...+\lambda^S_{i,i_{k-1}}s_{i_{k-1}}{}))} $$
其中$S=\{0,i_1,...,i_{k-1}\}$，和式(3)一致
利用上述式子，我们可以计算$v,v_1,...,v_l$，同时可以根据标准RSA签名来生成任意签名共享值$x_i$（这里也说明了为什么将共享值$x_i$定义为$x^{2\Delta s_i}$而非$x^{2s_i}$的原因）
接下来看正确性证明，正确性证明可以调用散列函数$H'$来得到合理性和统计零知识性（具体不证明）
首先考虑合理性，正确性证明中需要的是敌手无法以大于可忽略的概率为一个错误的共享值构造一个合法的正确性证明，假设$x,x_i$和正确性证明$(z,c)$给定，则根据前面提到的，有$c=H'(v,\widetilde x,v_i,x^2_i,v',x')$，满足$\widetilde x=x^{4\Delta},v'=v^zv_i^{-c},x'=\widetilde x^zx_i^{-2c}$，不难验证$v,\widetilde x,v_i,x^2_i,v',x'$都在$Q_n$中
由于前面假设了$v$是群$Q_n$的生成元，因此存在整数$\alpha,\beta,\gamma,\delta$，满足
$$ \begin{aligned} \widetilde x&=v^\alpha\\ v_i&=v^{s_i}\\ x^2_i&=v^\beta\\ v'&=v^\gamma\\ x'&=v^\delta \end{aligned} $$
此外还有
$$ \begin{aligned}z-cs_i&\equiv \gamma \ mod \ m\ (a) \\ z\alpha-c\beta&\equiv \delta \ mod\ m\ (b)\end{aligned} $$
式(a)乘$\alpha$再减去式(b)，得
$$ c(\beta-s_i\alpha)\equiv a\gamma-\delta \ mod \ m\tag7 $$
此时当且仅当下式成立时，共享才是正确的
$$ \beta \equiv s_i\alpha \ mod \ m\tag8 $$
若式$(8)$对模$m$不成立，则也对模$p'$和模$q'$也一定不成立，因此式$(7)$唯一确定了$c$是模这些素数的其中一个，但在RO模型中，$c$的分布是均匀的，与Hash函数输入无关，因此上述概率发生的概率可忽略不计
另一点，考虑零知识可模拟性，我们可以在不知道$s_i$的情况下，构建一个模拟器来模拟敌手的视图，该视图包含了敌手请求RO时Random Oracle在这些点的取值，因此模拟器可以完全控制RO，每当敌手请求RO时，若RO先前在该给定点未定义，则模拟器会将其定义为随机值，并在任何情况下都会将该值返回给敌手（这里和RSA-FDH的EUF-CMA安全归约类似）
当一个被攻破的敌手需要为给定的$x,x_i$生成正确性证明时，模拟器随机选择$c\in_R\{0,...,2^{L_1}-1\},z\in_R\{0,...,2^{L(n)+2L_1}-1\}$，然后令RO在$(v,\widetilde x,v_i,x^2_i,v^zv_i^{-c},\widetilde x^zx_i^{-2c})$处的取值为$c$即可（模拟器先前在该点未定义的概率可忽略，因此可以随意定义），然后证明即为$(z,c)$，不难证明由模拟器生成的分布在统计上接近完美（接近与真是协议执行时同分布）
对于合理性而言，我们得到了门限签名方案的鲁棒性，而从零知识和上述论点出发，假设标准RSA签名方案是安全的，即在自适应选择消息攻击下存在不可伪造性，从而Protocol 1是一个不可伪造的门限签名方案
最后一个假设可以进一步证明（假设见$[BR93]$）：在$H$为Random Oracle模型中，该假设遵循RSA假设，也即给定随机的$x\in_R\Z^*_n$，难以计算$y$，满足$y^e=x$
4 Protocol 2:modification and security analysis when $k\geq t+1$
接下来看Protocol 2，并分析在$k\geq t+1$时的安全性
在对Protocol 2的分析中，需要利用Random Oracle，因为充分利用RO可以获得比Protocol 1更简单高效的方案
具体Protocol 2对Protocol 1的修改如下
区别于式(1)，处理方计算共享密钥$s_i$时如下
$$ s_i=f(i)\Delta^{-1} \ mod \ m $$
然后需要在验证密钥$VK$中加入一个元素$u\in \Z^*_n$，满足其Jacobi符号为$-1$（也即$(u|n)=-1$，Jacobi符号可以高效计算，因此随机选择一个$u$进行判断即可）
接下来是修改共享生成算法，具体如下，令$\hat x=H(M)$，然后计算$x$如下（圆括号代表Jacobi符号，这个方法可以强制$x$的Jacobi符号为1）
$$ x=\begin{cases} \hat x , \ if\ (\hat x|n) =1\\ \hat xu^e,\ if\ (\hat x|n)=-1 \end{cases} $$
除了使用新的$x$以外，共享生成，验证，组合算法均和Protocol 1相同
此外还进行了下列简化，对于式(4-6)中定义的$x_i,\widetilde x,e'$，对其重新定义如下
$$ x_i=x^{2s_i},\widetilde x=x^4,e'=4 $$
这样一来就做到了在Protocol 2中的共享生成和组合算法消除了对$\Delta$的计算和使用
原始的共享组合算法需要计算$y^e=x$，若有$x=\hat xu^e$，我们可以用$u$除以$y$，从而可以得到$H(M)$的$e$次根（不过这样的结果是会得到标准的RSA签名）
完整Protocol 2如下
先看两个假设
- The RSA assumption：给定随机的$x\in_R\Z^*_n$，难以计算$y^e=x$
- The Decision Diffie-Hellman（DDH） assumption：给定随机的$g,h\in_R Q_n$，给定元组$(g^a,h^b)$，难以判断是否有$a\equiv b \ mod \ m$
这里将DDH假设更深入一下，对于$h\in_R Q_n,a,b\in \Z_m,c\in \{0,1\}$，定义
$$ F(h,a,b,c)=\begin{cases}h^a,\ if \ c=0\\ h^b,\ if \ c=1 \end{cases} $$
DDH说的是对于随机的$g\in_R Q_n$以及给定的$(g,h,g^a,F(h,a,b,c))$，难以计算$c$
这里需要注意的是，这是一个平均案例复杂性假设，通过标准的“随机自约化”参数$[Sta96，NR97]$，在前提$g,h$为$Q_n$的生成元，且$gcd(a-b,m)\notin \{p',q'\}$时，该假设相当于最坏情况下的复杂性假设（DDH在这里只是一个合理的假设，因为群Qn没有小的素因子$[Sho97]$）
通过标准的“混合”论证（见$[NR97]$），上述DDH假设等效于：下列两个分布$(a)$和$(b)$计算上不可区分
$$ \begin{aligned} (a):&(g,g^{a_1},...,g^{a_s};h,h^{a_1},...,h^{a_s})\\ (b):&(g,g^{a_1},...,g^{a_s};h,h^{b_1},...,h^{b_s}) \end{aligned} $$
其中$s$为任意小的数，$g,h\in_R Q_n$，$a_i,b_i$为模$m$下的随机数，（可以使用DDH的随机自可约性来证明相同的等价性，具体可以看$[Sho99]$或$[BBM00]$）
- Theorem 2：对于Random Oracle：$H$和$H'$，在RSA和DDH假设下，Protocol 2为安全门限签名方案，对于$k\geq t+1$满足鲁棒性和不可伪造性，进一步的，当$k=t+1$时，安全性只要求RSA假设（无需DDH假设）
鲁棒性和Protocol 1类似，这里着重关注证明的不可伪造性
由于$k>t+1$时需要DDH假设，这意味着某些诚实的参与方可以生成关于目标消息得共享，因此需要DDH假设来”虚拟（dummy）“共享，$H$视为Random Oracle可以允许模拟器按照它的意愿输出$H$的值，因此这些输出具有正确的分布
The simulator
这里文章还讨论了三个不同的模拟器，用于证明安全性，后续可能会更新，具体可以看原文
总结
总的来说是一个比较妙的门限签名方案，而且很简洁，方案没有什么太多余的东西
文章给出了两种协议，第二个协议改进了共享密钥的形式，从而消除了对$\Delta$的计算
不过第二个协议在$k\geq t+1$时的安全性比第一个协议多依赖一个DDH假设，而且两个协议都是在Random Oracle下的可证明安全
后记
主要是要写点做点东西才想着要看这个，一个非常简洁的门限签名方案
中间$\lambda$那里卡了一下没太看懂，自己数学水平不到家的问题，不过整体的证明生成和验证还是比较妙的
这周看了两个门限签名的方案，感觉看出点门道来了，接下来就是思考怎么把zkp用进去了
References
$[1]$ Victor Shoup:Practical Threshold Signatures. EUROCRYPT 2000: 207-220