算法设计

改进的SM2+NAPS

原来方案的缺点

改进之处

一个代理签名方案至少需要三种不同类型人的参与，即原始签名人，代理签名人(Agent)和代理签名的验证人

这篇文章分别用A,B,C代表上述三个身份

初始化参数：

椭圆曲线参数：$G$是椭圆曲线中阶为$n$的基点。

A私钥为$d_A\in[1.n-2]$,公钥为$P_A=d_AG$,私钥保密

$m_\omega$:授权证书信息（可以包含原始签名者和代理者的身份信息、代理签名者的权限等）

代理授权

B进行如下操作

用随机数生成器生成随机数$k_b\in[1,n-1]$,计算椭圆曲线上的点$G_b=k_bG$
B将$G_b$发送给A

A收到信息后进行如下操作

用随机数生成器生成随机数$k_a\in[1,n-1]$,计算椭圆曲线上的点$G_a=k_aG$
计算椭圆曲线上的另一个点$G_{ab}=(x_1,y_1)=k_aG_b$
计算$r_{ab}=x_1\pmod n$($r_{ab}=0$,重新计算)
计算$e_0=H(m_\omega||r_{ab})$
计算$s_A=$$k_a^{-1}(e_0+r_{ab}d_A)\pmod n$若$s_A=0$，返回第一步
A把（$m_\omega,G_a,G_{ab},s_A$）作为授权信息发送个B

其中$m_\omega$、$G_a$和$G_{ab}$公开，$s_A$秘密发送给B

授权验证+代理密钥生成

B收到授权信息后进行验证

3.计算椭圆曲线上另一个点$G’_{ab}=(x_2,y_2)=k_bG_a$

4.$e_0=H(m_\omega||r_{ab})$

5.计算$r’_{ab}=x_2 \pmod n$

若$s_AG_a≠r’_{ab}P_A+e_0G$拒绝委托

6.计算代理签名密钥$d_p=s_Ak_b^{-1}\pmod n$

NAPS初始化

B生成$d_p$后

1.加密密钥对:

随机选取$x_E\in [1,n-1]$,令$P_E=x_EG$.为本次委托的NAPS辅助ElGamal密钥对

2.每个地址的份额多项式：

对地址空间中每个$\tau=1,…,L$,随机选取系数$\rho_{\tau,1},…,\rho_{\tau,N-1}\in \mathbb{Z}_N^*$

$f_\tau(X)=d_p+\sum_{j=1}^{N-1}\rho_{\tau,j}X^j\pmod n$

3.系数的可验证加密：

对每个 $j=1,\dots,N-1$，随机选 $r_{\tau,j}\in[1,n-1]$，计算

$$C_{\tau,j}=(C_{\tau,j,1},,C_{\tau,j,2})=\big(r_{\tau,j}G,\ r_{\tau,j}P_E+\rho_{\tau,j}G_{ab}\big)$$

ElGamal加密所用基点与$d_p$对应公钥所用基点保持一致。

B公开${C_{\tau,j}}_{\tau\in[1,L],j\in[1,N-1]}$ and $P_E$

秘密保存${\rho_{\tau,j},r_{\tau,j}}$

代理签名生成

当B替代A对消息M进行签名时，使用的签名密钥四$d_p$过程如下

7.置$\overline{M}=Z_A||M$,其中$Z_A=H_{256}(ENTL_A||ID_A||a||b||x_G||y_G||x_A||y_A)$

8.计算$e=H(\overline{M})$

9.用随机数生成器生成随机数$k\in[1,n-1]$,计算($x_3,y_3$)=$kG_{ab}$

10.令$r=(e+x_3)\pmod n$若r=0或r+k=n则返回第8步

11.计算代理签名$s=(1+d_p)^{-1}(k-rd_P)\pmod n$若s=0返回第8步

NAPS部分

12.计算份额$z_\tau=f_{\tau}(p)=d_p+\sum_{j=1}^{N-1}\rho_{\tau,j}p^j\pmod n$

13.计算组和密文

$D=(D_1,D_2)=\sum_{j=1}^{N-1}p^jC_{\tau,j}=(R_\tau(p)G,R_\tau(p)P_E+(z_\tau-d_p)G_{ab})$

($R_\tau(p)=\sum_jp^jr_{\tau,j}$这个B掌握)

14.抵消未知项$D_2’=D_2+Q_p-z_\tau G_{ab}=R_\tau(p)P_E$

15.用Chaum-Pedersen型$\Sigma-$协议（Fiat-Shamir转化为非交互）证明

$\exists \omega:D_1=\omega G\land D_2’=\omega P_E $,($\omega=R_\tau(p)$)得到证明$\pi$

16.代理签名为$(m_\omega,G_a,G_{ab},r,s,\tau,p.z_\tau,\pi)$

代理签名的验证

验证者C进行如下操作

NAPS部分验证

1.$D=\sum_{J=1}^{N-1}p^jC_{\tau,j}=(D_1,D_2)$直接计算可获得

$D_2’=D_2+Q_p-z_\tau G_{ab}=R_\tau(p)P_E$

2.验证$\pi$ （NIZK）

SM2代理签名验证

4.检验$r’\in[1,n-1]$和$s’\in[1,n-1]$是否成立

5.置$\overline{M’}=Z_A||M’$,计算$e’=H(M’)$

6.计算$r_{ab}=x_1\pmod n$

7.计算$e_0’=H(m_\omega||r_{ab})$

8.计算$t=(r’+s’)\pmod n$若t=0验证不通过

9.计算椭圆曲线点$X=(x_3’,y_3’)=s’G_{ab}+tr_{ab}P_A+te_0’G$,计算$R=(e’+x_3’)\pmod n$当且仅当$R=r’$时接受签名

密钥提取

同一地址$\tau$下出现$N$份不同载荷$p_1,…,p_N$的有效次代理签名，任何人可用拉格朗日插值提取代理密钥

$d_p=f_\tau(0)=\sum_{i=1}^Nz_i\prod_{k=1,k≠i}^N \frac{-p_k}{p_i-p_k}\pmod n$

NAPS机制

NAPS定义；

$d_p=s_Ak_b^{-1}\pmod n$满足C类签名方案定义

class C:

NIZK

需要证明的陈述：存在$\omega$使得$D_1=\omega G$且$D_2’=\omega P_E$

交互式$\Sigma$-协议

$x=(G,P_E,D_1,D_2’);\omega=R_\tau(p)$

commitment

$B$随机选$k\in \mathbb{Z}_n^*$,计算$a_1=kG,a_2=kP_E$将($a_1,a_2$)发送给验证者
challenge

验证者随机选$c\in \mathbb{Z}_n^*$,发送给$B$
response

B计算$s_\pi=(k+c\cdot\omega)\pmod n$发送$s_\pi$

Verify:

$s_\pi G?=a_1+cD_1,s_\pi P_E?=a_2D_2’$

Fiat-Shamir变化去交互化

即把challenge替换为（哈希函数生成挑战），即可去掉交互

在随机预言机模型ROM下保持可靠性（依赖分叉引理）与零知识证明

a)随机选$k\in\mathbb{Z}_n^*$,计算$a_1=kG,a_2=kP_E$

b)计算挑战$c_\pi=H(G,P_E,D_1,D_2’,a_1,a_2)\pmod n$($H$为哈希函数，建模为随机预言机)

c)计算响应$s_\pi=(k+c_\pi R_\tau(p))\pmod n$

d)输出$\pi=(c_\pi,s_\pi)$(无需传输$a_1,a_2$)

verify:

a)$a_1’=s_\pi G-c_\pi D_1,a_2’=s_\pi P_E-c_\pi D_2’$

b)验证$c_\pi ?=H(G,P_E,D_1,D_2’,a_1’,a_2’)$,成立则接受

安全性分析

满足

EUF-CMA

安全模型：签名询问预言机对同一地址$\tau$至多接受一次查询。敌手$\mathcal{A}$可对不同地址自适应签名，最终对未查询过（$*\tau,*p,M^*$）

wDSE

若攻击者（或诚实审计者）拿到同一地址$τ $下N 份不同载荷$p1,…,pN$ 的全部通过验证的代理签名，则用拉格朗日插值算出的$d _p’$，以压倒性概率等于真实的$dp$。

分叉引理

提供了一种巧妙的方法：允许我们通过概率分析将签名方案的安全性规约到已知的数学难题。

通俗理解为，你想证明一把锁的安全性，不用尝试所有得到开锁方法，二十证明只要能开这把锁就能解开数学界公认的无解难题

在随机预言模型ROM中尤为重要，把哈希函数看作一个神奇的预言机，每次查询都会得到完全随机响应。敌手可以任意查询这个预言机，但最终必须输出一个有效签名。（分叉引理核心思想：如果敌手伪造签名，那么我们可以通过重放预言机的响应，让敌手在相同输入下产生两个不同签名，从而破解底层难题）