Information Sciences,2014

关于指定验证人签名方案的可委托性
本文将指定验证者签名方案分为三种类型，讨论了现有指定验证者签名方案、强指定验证者签名方案和通用指定验证者签名方案的可委托性以及有待研究的问题

介绍

• 指定验证人签名的提出：不具有传统签名的不可否认性
• 强指定验证者签名(SDVS)方案：指定验证者使用他的秘密密钥来验证指定给他的签名有效或无效。
  M. Jakobsson, K. Sako, R. Impagliazzo, Designated verifier proofs and their applications, in: Advances in Cryptology-Eurocrypt’96, LNCS, vol. 1070, Springer-Verlag, 1996, pp. 142–154.
• 将DVS的概念扩展到通用DVS (UDVS)方案，允许签名持有人将标准签名转换为指定签名，指定给他所选择的任何指定验证人。
  R. Steinfeld, H. Wang, J. Pieprzyk, Efficient extension of standard Schnorr/RSA signatures into universal designated-verifier signatures, in: PKC’04, LNCS, vol. 2947, Springer-Verlag, 2004, pp. 86–100

Lipmaa等人引入了指定验证者签名方案的一个新的安全概念——不可委托性:签名者和指定验证者都不能将签名权委托给任何第三方而不泄露自己的密钥。
H. Lipmaa, G. Wang, F. Bao, Designated verifier signature schemes: attacks, new security notions and a new construction, in: ICALP 2005, LNCS, vol. 3580, 2005, pp. 459–471.

定义

SDVS

$\mathrm{KeyGen}(1^k)\to (sk,pk)$
$\mathrm{DV}-\mathrm{Sign}(s{k}_S,m,p{k}_V)\to \tau$
$\mathrm{DV}-\mathrm{Verify}(s{k}_V,m,p{k}_S,\tau )\to 0/1$
$\mathrm{TranscriptSimulation}$持有其私钥$s{k}_V$的指定验证者总是可以产生与原始证明无法区分的相同分布的副本。

ID-based DVS

K e y G e n ( 1 k ) → p a r a m s : = { . . . , ( m s k , m p k ) } {\rm KeyGen}(1^k)\rightarrow params:=\{...,(msk,mpk)\} KeyGen(1k)→params:={...,(msk,mpk)}
$\mathrm{Extract}(msk,ID)\to S_{ID}$
$\mathrm{DV}-\mathrm{Sign}(S_{I{D}_S},m,I{D}_S,I{D}_V)\to \tau$
$\mathrm{DV}-\mathrm{Verify}(S_{I{D}_V},m,I{D}_S,I{D}_V,\tau )\to 0/1$
$\mathrm{TranscriptSimulation}$持有其私钥$S_{I{D}_V}$的指定验证者总是可以产生与原始证明无法区分的相同分布抄本。

UDVS

UDVS方案允许标准签名的任何持有者将签名指定给任何验证者。指定的验证者可以检查消息是否已由签名者签名，但无法让任何人相信这一事实。
$\mathrm{KeyGen}$、$\mathrm{TranscriptSimulation}$和DVS相同
$\mathrm{Sign}(s{k}_S,m)\to \sigma$
$\mathrm{Verify}(p{k}_S,m,\sigma )\to 0/1$
$\mathrm{Designation}(p{k}_S,p{k}_V,m,\sigma )\to \tau$
$\mathrm{U}-\mathrm{DV}-\mathrm{Verify}(s{k}_V,p{k}_S,p{k}_V,m,\tau )\to 0/1$

分类

1. DV-Sign和DV-Verify算法只依赖于签名者和指定验证者之间的一个公共值（如DH，双线性对DH），不使用任何其他机密信息。这类方案都是可委托的，公共值被透露给第三方T, T可以为{A,B}生成有效的指定验证者签名。
2. DV-Sign算法依赖于签名者的密钥以及签名者与指定验证者之间的公共值，或者只依赖于签名者的密钥。同时，DV-Verify算法依赖于通用值。为了防止可委托性，有必要使用公共价值之外的另一个秘密信息。
3. DV-Sign算法只依赖于签名者的密钥，DV-Verify算法依赖于指定验证者的密钥，而不使用签名者和指定验证者之间的公共值。

type-Ⅱ算法举例

签名依赖于签名者的密钥$s$和双线性对DH公共值$e(S_A,Q_B)=e(Q_A,S_B)$，验证依赖于通用值。因为签名中有明确不可分享的私钥存在，所以不能代替生成有效签名

• Kumar：DVS
  $(s,sP),(S_i:=s{Q}_i=s{H}_1(I{D}_i))$
  $\mathrm{Sign}:\sigma :=(U_1,U_2,U_3,V)=(r_1{Q}_B,r_2{Q}_A,r_1{r}_3{Q}_B,r_3{H}_2(m,e(S_A,r_2{Q}_B))+r_1^{-1}{S}_A)$
  $\mathrm{Verify}:H=H_2(m,e(U_2,S_B)),e(U_1,V)=e(U_3,H)e(S_B,Q_A)$
• Zhang-Mao：DVS
  $\mathrm{Sign}:\sigma :=(U_1,U_2,V)=(r_1{Q}_B,r_1{r}_2{Q}_B,r_2{H}_2(m,U_1,U_2)+r_1^{-1}{S}_A)$
  $\mathrm{Verify}:H=H_2(m,U_1,U_2),e(U_1,V)=e(U_2,H)e(S_B,Q_A)$

Type-Ⅰ DVS算法举例(涉及双线性DH型公共值)

可以用公共值代替生成有效签名

• Kang:DVS
  $\mathrm{Sign}:(U=r{Q}_A,\sigma :=H_2(m,e(S_A,r{Q}_B)))$
  $\mathrm{Verify}:\sigma =H_2(m,e(U,S_B))$
  Lee:DVS
  $\mathrm{Sign}:$random $x$,Timestamp $T_S,r=H_2(T_S),\delta =x{Q}_A,\sigma :=H_2(m,e(x{Q}_B,r{S}_A))$
  输出签名$(\delta ,T_S,\sigma )$
  $\mathrm{Verify}:r=H_2(T_S),\sigma =H_2(m,e(\delta ,r{S}_B))$

• Seo:UDVS
  $\mathrm{Sign}:(U=rP,V=r{P}_{pub}+h{S}_A),h=H_2(m,U)$
  $\mathrm{Designation}:(U,\tau :=e(V,Q_B))$
  $\mathrm{U}-\mathrm{DV}-\mathrm{Verify}:Q_A=H_1(I{D}_A),h=H_2(m,U),\tau =e(U+h{Q}_A,S_B)$

• Zhang:UDVS
  $\mathrm{Sign}:(U=r{Q}_A,V=(r+h)S_A),h=H_2(m,U)$
  $\mathrm{Designation}:(U,\tau :=e(V,Q_B))$
  $\mathrm{U}-\mathrm{DV}-\mathrm{Verify}:Q_A=H_1(I{D}_A),h=H_2(m,U),\tau =e(U+h{Q}_A,S_B)$

• Huang:UDVS
  $\mathrm{KeyGen}:$random u ′ , u : = { u 1 , . . . , u n } u',{\rm u}:=\{u_1,...,u_n\} u′,u:={u1​,...,un​},$m$位长为n,random $s{k}_A:=(x_A,y_A),p{k}_A:=(g^{x_A},g^{y_A})$
  S i g n : M ⊂ { 1 , . . . , n } {\rm Sign}:M\subset\{1,...,n\} Sign:M⊂{1,...,n}表示$m_i=1$的标号，$\sigma :=(U,V)=(g^{x_A{y}_A}(u^{\prime }{\prod }_{i\in M}{u}_i{)}^r,g^r)$
  $\mathrm{Designation}:W_1=e(U(u^{\prime }{\prod }_{i\in M}{u}_i{)}^{r^{\prime }},p{k}_{B_x})=e(g^{x_A{y}_A}(u^{\prime }{\prod }_{i\in M}{u}_i{)}^{r+r^{\prime }},p{k}_{B_x})$,$W_2=V\cdot g^{r^{\prime }}=g^{r+r^{\prime }}$,输出签名$\tau =(W_1,W_2)$
  $\mathrm{DV}-\mathrm{Verify}:W_1=e(p{k}_{A_x},p{k}_{A_y}{)}^{x_B}e(u^{\prime }{\prod }_{i\in M}{u}_i,W_2{)}^{x_B}$

Type-Ⅰ DVS算法举例(涉及DH型公共值)

• Steinfeld:UDVS
  $(x_A,y_A=g^{x_A})$
  $\mathrm{Sign}:$random $k,u=g^k,s=k+r\cdot x_A,r=H(m,u)$，输出$\sigma =(r,s)$
  $\mathrm{Designation}:\tau :=(u=g^s\cdot y_A^{-r},K=y_B^s)$
  $\mathrm{DV}-\mathrm{Verify}:r=H(m,u),K=(u\cdot y_A^r{)}^{x_B}$
• Lee–Chang：DVS
  $\mathrm{Sign}:r=g^k,s=k+x_{A}rmodq,t=H(m,y_B^s),\sigma :=(r,t)$
  $\mathrm{DV}-\mathrm{Verify}:t=H(m,(r\cdot y_A^r{)}^{x_B})$
• Islam and Biswas：SDVS
  $\mathrm{Sign}:U=r{P}_A=r{x}_{A}P,h=H(m,U),\sigma :=x_A(r+h)P_B$，签名$(U,\sigma )$
  $\mathrm{DV}-\mathrm{Verify}:h=H(m,U),\sigma :=x_B(U+h{P}_A)$

Delegatability攻击

可委托性攻击:知道与密匙相关的一些值的对手可以在不知道签名者和验证者的密匙的情况下生成有效的签名。

对Type II DVS的攻击

假设$(D=r_1{Q}_B,D^{\prime }=r_1^{-1}{S}_A)$被泄露给第三方T，T可以生成DVS签名：

• Kumar：DVS
  random $r_2,r_3$，计算$U_1=D,U_2=r_2{Q}_A,U_3=r_{3}D$
  $S=e(D,D^{\prime }{)}^{r_2}=e(r_1{Q}_B,r_1^{-1}{S}_A{)}^{r_2}=e(Q_B,S_A{)}^{r_2},H=H_2(m,S)$
  $V=r_{3}H+D^{\prime }$
  输出签名$(U_1,U_2,U_3,V)$
• Zhang-Mao：DVS
  random $r_2$，计算$U_1=D,U_2=r_{2}D,H=H_2(m,U_1,U_2),V=r_{2}H+D^{\prime }$,输出签名$(U_1,U_2,V)$

对BDH-Type I DVS的攻击

假设BDH类公共值$D=e(S_A,Q_B)=e(Q_A,S_B)=e(Q_A,Q_B{)}^s$被泄露给第三方T，T可以生成DVS签名：

• Kang:$(U=r{Q}_A,\sigma :=H_2(m,D^r))$
  Lee:$r=H_2(T_S)$,random $x,\delta =x{Q}_A,\sigma :=H_2(m,e(x{Q}_B,r{S}_A))$,输出签名$(\delta ,T_S,\sigma )$
• Seo:$(U=rP,\tau =e(r{P}_{pub},Q_B)\cdot D^h),h=H_2(m,U)$
• Zhang: $(U=r{Q}_A,\tau =D^{r+h}),h=H_2(m,U)$
• Huang:
  假设$D=e(p{k}_{A_x},p{k}_{A_y}{)}^{x_B}$被泄露给第三方，T可以生成DVS签名：
  T选择random $k,W_2=g^k$
  $W_1=e(g^{x_A{y}_A}(u^{\prime }{\prod }_{i\in M}{u}_i{)}^k,p{k}_{B_x})=D\cdot e(u^{\prime }{\prod }_{i\in M}{u}_i,p{k}_{B_x}{)}^k$,输出签名$\tau =(W_1,W_2)$

除了可委托攻击，其中两个方案还是universally forgeable的，任何人都能伪造签名，敌手：
Kang：随机选择$r,U:=rP,\sigma :=H_2(m,e(r{P}_{pub},Q_B))$，验证等式：$\sigma =H_2(m,e(U,S_B))=H_2(m,e(rP,s{Q}_B))=H_2(m,e(r{P}_{pub},Q_B))$。
Lee：$r=H_2(T_S)$,random $x,,\delta :=xP,\sigma :=H_2(m,e(r{P}_{pub},x{Q}_B))$。签名满足验证等式：$,\sigma =H_2(m,e(\delta ,r{S}_B))=H_2(m,e(xP,rs{Q}_B))=H_2(m,e(r{P}_{pub},x{Q}_B))$。
二者都在没有任何额外信息的情况下伪造了签名。这类伪造攻击是由于这些方案在验证算法的输入中没有使用签名者的身份信息。

对DH-Type I DVS的攻击

这类攻击假设$D=y_B^{x_A}=g^{x_A{x}_B}$被泄露给第三方T：

• Steinfeld:
  random $k,u=g^k,r=H(m,u),K=y_B^k\cdot D^r$.验证 $K=(u\cdot y_A^r{)}^{x_B}=(y_B^k\cdot y_B^{r\cdot x_A})=y_B^k\cdot D^r$
• Lee–Chang：
  $r=g^k,t=H(m,y_B^k\cdot D^r)$.验证 $t=H(m,(r\cdot y_A^r{)}^{x_B})=H(m,y_B^k\cdot D^r)$
• Islam and Biswas：
  $U=r{P}_A,h=H(m,U),\sigma :=(r+h)\cdot D$.验证$\sigma =x_B(U+h{P}_A)=rD+hD$

总结

1. type I DVS 都是可委托的：因为只依赖于公共值，虽然这个值不一定泄露私钥。
2. 一部分typeⅡDVS，虽然不只依赖于公共值，仍然可能被可委托攻击。
3. 存在typte Ⅲ方案对于可委托攻击是安全的，作者给出了案例：non-delegatable SDVS
   缺陷：签名长度约为其他分布式交换机方案的3倍，且签名生成和验证效率均较低。
4. 设计短而高效的SDVS和UDVS方案仍然是一个开放的问题，可以证明对可委托性攻击是安全的。

根据安全参数和硬件平台的选择，配对计算所需的时间至少比椭圆曲线上的标量乘法慢2倍(最多10倍)。因此，如果在设计短签名方案时需要对，则应尽量减少对的计算次数