学习笔记：《Short Randomizable Signatures》中的安全性证明

原方案https://blog.csdn.net/jiongxv/article/details/125261870
注意区分随机预言机模型与标准预言机模型：https://blog.csdn.net/weixin_43137080/article/details/109595044
这篇文章中涉及的安全性证明是without random oracles but in the generic group model

Assumptions

EUF-CMA

签名方案的标准安全概念是在选择消息攻击(EUF-CMA) [GMR88]下的存在不可伪造性，这意味着即使获得了对签名oracle的访问权，也很难为从未向签名oracle请求的消息m输出有效的签名对$(m,\sigma )$。它被定义为挑战者$\mathcal{C}$和敌手$\mathcal{A}$之间的博弈：

如果没有概率多项式时间对手$\mathcal{A}$能以不可忽略的概率获胜，则签名方案是EUF-CMA安全的.

LRSW

到目前为止，一个经典的假设是所谓的LRSW [LRSW00]，它承认两个协议:

• issuing protocol:允许用户在消息$x$上获得签名$\sigma$，只需向签名者发送$x$的承诺即可
• proving protocol:允许用户以零知识的方式证明他对$x$承诺上的签名的知识。它们导致高效的匿名凭证

(LRSW Assumption) 设$\mathbb{G}$是素数阶p的循环群，有一个生成元g。对于$X=g^x$和$Y=g^y$，其中$x$和$y$是${\mathbb{Z}}_p$中的随机标量。我们在输入$m\in {\mathbb{Z}}_p$上定义oracle $\mathcal{O}(m)$，它选择一个随机$h\in \mathbb{G}$，输出三元组$T=(h,h^y,h^{x+mxy})$。给定$(X,Y)$和对这个oracle的无限访问，没有敌手可以有效地为一个新标量$m^{\ast }$生成这样的三元组，而不要求$\mathcal{O}$。

Assumption 1

(Assumption 1).设$(p,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,e)$为Type-3(非对称, ${\mathbb{G}}_1\ne {\mathbb{G}}_2$)的双线性组设置，$g$ (或$\tilde{g}$) 是${\mathbb{G}}_1$ (或${\mathbb{G}}_2$)的生成元。对于$(X=g^x,Y=g^y)$和$(\tilde{X}={\tilde{g}}^x,\tilde{Y}={\tilde{g}}^y),x,y\in {\mathbb{Z}}_p$, 在输入$m\in {\mathbb{Z}}_p$上定义oracle $\mathcal{O}(m)$，它选择一个随机$h\in {\mathbb{G}}_1$，输出元组$P=(h,h^{x+my})$。给定$(g,Y,\tilde{g},\tilde{X},\tilde{Y})$和对这个oracle的无限访问，没有敌手可以有效地为一个新标量$m^{\ast }$生成这样的元组，with $h\ne 1_{{\mathbb{G}}_1}$，而不要求$\mathcal{O}$。

可以注意到，使用pairing，可以检查敌手的输出，因为对$P=(P_1,P_2)$应该满足$e(P_1,\tilde{X}\cdot {\tilde{Y}}^m)=e(P_2,\tilde{g})$.
此外，$(X,Y)$足以回答oracle查询:在标量$m\in {\mathbb{Z}}_p$上，计算$(g^r,(X\cdot Y^m{)}^r)$。这需要每个查询进行3次幂运算，而知道$(x,y)$只需要在${\mathbb{G}}_1$中进行随机抽样和一次幂运算。

在某些情况下，一个较弱的假设就足够了，即不给敌手$Y$:

Assumption 2

(Assumption 2).设$(p,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,e)$为Type-3(非对称, ${\mathbb{G}}_1\ne {\mathbb{G}}_2$)的双线性组设置，$g$ (或$\tilde{g}$) 是${\mathbb{G}}_1$ (或${\mathbb{G}}_2$)的生成元。对于$(X={\tilde{g}}^x,Y={\tilde{g}}^y),x,y\in {\mathbb{Z}}_p$, 在输入$m\in {\mathbb{Z}}_p$上定义oracle $\mathcal{O}(m)$，它选择一个随机$h\in {\mathbb{G}}_1$，输出元组$P=(h,h^{x+my})$。给定$(\tilde{g},\tilde{X},\tilde{Y})$和对这个oracle的无限访问，没有敌手可以有效地为一个新标量$m^{\ast }$生成这样的元组， with $h\ne 1_{{\mathbb{G}}_1}$，而不要求$\mathcal{O}$。

证明假设成立

Theorem 4.在一般双线性群模型中，上述假设1(因此假设2)成立:在$q$ 次oracle查询和$q_G$ 次group-oracle查询之后，没有敌手能够为一个新的标量以好于$6(q+q_G{)}^2/p$的概率生成一个有效对.
Proof.
假设$r_i\in {\mathbb{Z}}_p^{\ast }$，第i次对$m_i$的查询返回$(h_i,t_i=h_i^{(x+y\cdot m_i)}),h_i=g^{r_i}$

我们必须首先证明敌手$\mathcal{A}$不能符号化地产生一个新的有效元组，然后证明偶然有效性是非常不可能的。
对于标量$m^{\ast }$上的输出元组$(h^{\ast },t^{\ast })$，由于$h^{\ast },t^{\ast }\in {\mathbb{G}}_1$，所以它们只能是之前的元组$(h_i,t_i),g,Y$的组合(没有任何${\mathbb{G}}_2$中的元素的帮助):它们是在${\mathbb{G}}_1$中通过对内部规则的oracle的查询构建的，所以我们知道$((u_{i,1},v_{i,1},u_{i,2},v_{i,2}{)}_i,(w_1,w_2),(w_1^{\prime },w_2^{\prime }))\in {\mathbb{Z}}_p^{4q+4}$满足:

因此，有新元组


新元组的有效性意味着$z^{\ast }=r^{\ast }(x+y\cdot m^{\ast })$，这导致：

为了使两个多变量多项式相等，两边应该出现相同的单项:

• 左边没有3次的单项式，所以对所有i，$v_{i,1}=0$
• 右边没有$r_i$的项，所以对所有i,$u_{i,2}=0$
• 右边没有常数项，所以$w_2=0$
• 左边没有$x$和$xy$的项，所以$w_1=0,w_1^{\prime }=0$:
  
• 右边没有$y$的项了，所以$w_2^{\prime }=0$:
  
• 对于所有的i,$x{r}_i$的系数相等：$v_{i,2}=u_{i,1}$，$y{r}_i$的系数：$v_{i,2}\cdot m_i=u_{i,1}\cdot m^{\ast }$
  因为$r^{\ast }\ne 0$(否则$h^{\ast }=1_{{\mathbb{G}}_1}$)，所以右边不等于0，$v_{i,2}=u_{i,1}\ne 0$，$m_i=m^{\ast }$，这不是新的标量。
  所以，敌手无法以符号化的方式为新标量生成有效的元组。

还需要评估偶然有效的概率：当两个不同的多项式涉及到对Oracle的回答时，得到相同的值。

• 由于oracle提供的元素与最多2阶多项式相关联(指被查询过的结果$(h_i,t_i)$的系数$u_{i_1},v_{i,1},u_{i,w},v_{i,2}$多项式)，
• 由于公共元素与最多1阶多项式相关联(指公共元素$Y,g$的系数$w_1,w_2,w_1^{\prime },w_2^{\prime }$多项式)，
• 从对不同组oracle的查询中得到的多项式最多3阶(因为配对查询)

(解释：公共元素就是group oracle，一阶表示只有一个变量，对应$q_G$个结果；同理，由oracle提供的元素2阶表示两个结果，对应$2q$；而前文所述pairing中$\tilde{g}$等其他组oracle查询的多项式是3阶)
设$q_G$为group-oracle查询的最大值，因此最多有$3+2q+q_G$多项式，所以最多$(3+2q+q_G{)}^2/2$对不同的多项式能求出相同的值.

根据Schwartz-Zippel引理，$(3+2q+q_G{)}^2/2$个多项式的总概率上界为$3/p\times (3+2q+q_G{)}^2/2p$

$3(3+2q+q_G{)}^2/2p\le 6(q+q_G{)}^2/p$（放缩法）,可以忽略不计。
(Schwartz-Zippel引理)

方案的安全性

Single-Message Signature

• 已经证明了Assumption 2是成立的，即如果有方案满足assumption2，则没有敌手能够成功伪造；single message是完全符合Assumption 2的
• 对于single message方案的EUF-CMA，query部分返回对Sign的oracle查询结果；等同于assumption 2。
• 所以，single message方案是满足EUF-CMA的

Multi-Message Signature

把这个多消息签名方案的安全性依赖于单消息签名方案的安全性，依此类推，假设2。
Theorem 6
在上述假设2下，多消息签名方案满足EUF-CMA安全级别。
更准确地说，如果攻击者能够以$ϵ$的概率攻破多消息签名方案的EUF-CMA安全性，则在相同的运行时间和相同的签名查询次数内，存在攻击者攻破单消息签名方案的EUF-CMA安全性，且成功的概率大于$ϵ-q/p$
Proof.
假设$\mathcal{A}$是多消息签名方案的EUF-CMA安全性的敌手。针对单消息签名方案的EUF-CMA安全性，使用$\mathcal{A}$构造一个归约$\mathcal{R}$。后一场game的挑战者将用$\mathcal{C}$表示.

• Setup. $\mathcal{R}$从$\mathcal{C}$接收到一个公钥$\mathrm{p}{\mathrm{k}}^{\ast }$，其中包含签名方案的公共参数$pp$和$(\tilde{g},\tilde{X},\tilde{Y})$。它选择${\alpha }_j,{\beta }_j\leftarrow {\mathbb{Z}}_p,j=1,...,r$，令${\tilde{Y}}_j\leftarrow {\tilde{Y}}^{{\alpha }_j}{\tilde{g}}^{{\beta }_j}$。输出公钥$pk\leftarrow (\tilde{g},\tilde{X},{\tilde{Y}}_1,...,{\tilde{Y}}_r)$
• Queries. 当$\mathcal{A}$查询一个向量$M_i=(m_{i,1},...,m_{i,r})$上的签名时，$\mathcal{R}$首先向$\mathcal{C}$请求一个$m_i=\sum {\alpha }_j{m}_{i,j}$上的签名$\sigma =({\sigma }_1,{\sigma }_2)$ ，从而$e({\sigma }_1,\tilde{X}\cdot {\tilde{Y}}^{\sum {\alpha }_j{m}_{i,j}})=e({\sigma }_2,\tilde{g})$.接着，计算${\sigma }_2^{\prime }\leftarrow {\sigma }_2\cdot {\sigma }_1^{\sum {\beta }_j\cdot m_{i,j}}$并返回有效签名$({\sigma }_1,{\sigma }_2^{\prime })$给$\mathcal{A}$：
  
• Output. 最终，$\mathcal{A}$在向量$M^{\ast }=(m_1^{\ast },...,m_r^{\ast })$上输出签名$\sigma =({\sigma }_1,{\sigma }_2)$。签名$\sigma$是一个有效的伪造，如果:
  
  如果对于某些 i = { 1 , . . . , q } i=\{1,...,q\} i={1,...,q},$\sum {\alpha }_j{m}_j^{\ast }=\sum {\alpha }_j{m}_{i,j},\mathcal{R}$中止。
  否则，输出${\sigma }^{\ast }=({\sigma }_1^{\ast },{\sigma }_2^{\ast }):{\sigma }_1^{\ast }\leftarrow {\sigma }_1,{\sigma }_2^{\ast }\leftarrow {\sigma }_2\cdot {\sigma }_1^{-\sum {\beta }_j\cdot m_j^{\ast }},m^{\ast }\leftarrow \sum {\alpha }_j{m}_j^{\ast }$:
  
  因为消息$m^{\ast }$从未查询过，所以这是一个有效的伪造签名。
  分析：
• query阶段，敌手$\mathcal{A}$经过q次查询，获得对于消息$M_i=(m_{i,1},...,m_{i,r})$的合法multi message签名；
• output阶段，先假设敌手$\mathcal{A}$能输出对于新消息$M^{\ast }=(m_1^{\ast },...,m_r^{\ast })$合法的multi message签名，再证明可以利用这组签名伪造single messge签名
• 命题：多消息伪造$\to$单消息伪造；逆否命题：单消息不可伪造$\to$多消息不可伪造
• 注意：如果出现$\sum {\alpha }_j{m}_j^{\ast }=\sum {\alpha }_j{m}_{i,j}$，表示用multi message组合而成的single message已经查询过了，不符合EUF-CMA的要求，所以中止这种巧合。

证明这种线性关系几乎不可能出现：

(要区分$\mathcal{R}$和$\mathcal{A}$的视角，${\alpha }_j$是由$\mathcal{R}$选择的，$\mathcal{A}$得到的公钥中包含${\alpha }_j$，分析这种“包含”是否导致公钥和${\alpha }_j$之间存在某种联系，即$\mathcal{A}$是否能从中获得某些知识)
设标量$y,\tilde{Y}={\tilde{g}}^y$，随机选择${\gamma }_j\leftarrow {\mathbb{Z}}_p,j=1,...,r$，设${\alpha }_j^{\prime }\leftarrow {\alpha }_j-{\gamma }_j,{\beta }_j^{\prime }\leftarrow {\beta }_j+y{\gamma }_j,j=1,...,r$，可以注意到：

因此，公钥是独立于实际的${\gamma }_j$的，因此没有揭示${\alpha }_j$的信息，这与仅依赖于oracle和公钥选择的${\sigma }_1$的签名是一样的。
因此，敌手的完整视图完全独立于${\alpha }_j$的视图。因此，$\mathcal{R}$中止的概率的上限（多项式Schwartz-Zippel引理）是$q\times 1/p=q/p$。
结论$\mathcal{R}$成功将攻破multi message签名规约到攻破single message签名的概率大于$ϵ-q/p$.证毕。

Sequential Aggregate Signature

在认证公钥设置中，我们将这个聚合签名方案的安全性依赖于单消息签名方案的安全性，依此类推假设2:

Theorem 7. 在上述假设2下，在认证公钥设置下，聚合签名方案达到EUF-CMA安全级别。更准确地说，如果攻击者能够破坏聚合签名方案的EUF-CMA安全性，则存在攻击单消息签名方案的EUF-CMA安全性的攻击者，在相同的运行时间和相同的签名查询次数内，以相同的概率成功。
Proof.
在认证公钥设置中，假设$\mathcal{A}$是聚合签名方案的EUF-CMA安全性的敌手。针对单消息签名方案的EUF-CMA安全性，使用$\mathcal{A}$构造一个归约$\mathcal{R}$。后一场game的挑战者将用$\mathcal{C}$表示.

• Setup. $\mathcal{R}$首先将密钥列表KeyList初始化为空。然后，从$\mathcal{C}$中获取一个公钥$\mathrm{pk}$，其中包含签名方案的公共参数$pp$和$(\tilde{g},\tilde{X},\tilde{Y})$
  • 请求$\mathcal{C}$在0上签名，返回$\tau =({\tau }_1,{\tau }_2)$使$e({\tau }_1,\tilde{X})=e({\tau }_2,\tilde{g})$ ,可以设置$g\leftarrow {\tau }_1$和$X\leftarrow {\tau }_2$
  • 将聚合签名方案的公共参数设为$(pp,g,X,\tilde{g},\tilde{X})$，并将${\mathrm{pk}}^{\ast }\leftarrow \tilde{Y}$发送给$\mathcal{A}$。在下面，$x^{\ast }$和$y^{\ast }$将表示(未知)标量，使$\tilde{X}={\tilde{g}}^{x^{\ast }}$（及$X=g^{x^{\ast }}$），$\tilde{Y}={\tilde{g}}^{y^{\ast }}$.因此，标量$y^{\ast }$是与$p{k}^{\ast }$相关联的未知密钥$s{k}^{\ast }$(注意$\mathcal{R}$可以请求$\mathcal{C}$的查询和公共信息，但并不知道single message的私钥等)。
• Join Query.
  当$\mathcal{A}$要求添加一个公钥$p{k}_i$时，认证过程包括对相关密钥$s{k}_i$的知识证明，允许$\mathcal{R}$提取它:它将$p{k}_i$存储在KeyList中，并将$(s{k}_i,p{k}_i)$存储在其自己的签名/验证密钥列表中，以供将来的模拟使用
• Signature Query.
  • 当$\mathcal{A}$请求将消息$m_i$聚合到公共密钥$(p{k}_{i,1},...,p{k}_{i,r_i})$下消息$(m_{i,1},...,m_{i,r_i})$上的聚合签名${\sigma }_i$上时，如果$r_i>0$, $\mathcal{R}$首先检查${\sigma }_i$的有效性，并在否定的情况下中止。
  • 请求$\mathcal{C}$在$m_i$上签名，返回$\sigma =({\sigma }_1,{\sigma }_2)$
  • 聚合签名中涉及的所有公钥必须事先经过认证，然后$\mathcal{R}$知道相关的密钥$(s{k}_{i,1},...,s{k}_{i,r_i})=(y_{i,1},...,y_{i,r_i})$:它随机选择一个$t\leftarrow {\mathbb{Z}}_p$并返回${\sigma }^{\prime }\leftarrow ({\sigma }_1^t,({\sigma }_2\cdot {\sigma }_1^{{\sum }_{j=1}^{r_i}{y}_{i,j}\cdot m_{i,j}}{)}^t)$。这个签名满足：
    
    它是在公钥$((p{k}_{i,j}{)}_i,p{k}_i^{\ast })$下，对向量$((m_{i,j}{)}_i,m_i)$的有效签名.

分析:(这是不是查询并生成合法聚合签名的过程？)
已知一个对单消息$m_i$的签名，$({\sigma }_1,{\sigma }_2={\sigma }_1^{x+y_i})$
根据聚合签名的原始定义，首先要构造一个将消息$m_i$聚合到公共密钥$(p{k}_{i,1},...,p{k}_{i,r_i})$下消息$(m_{i,1},...,m_{i,r_i})$上的聚合签名${\sigma }_i$:
- $j=0,{\sigma }_{i,0}=(g,X)$
- $j=1,{\sigma }_{i,1}=(g^{t_{i,1}},(X\cdot g^{y_{i,1}{m}_{i,1}}{)}^{t_{i,1}})$
- $j=2,{\sigma }_{i,2}=(g^{t_{i,1}{t}_{i,2}},(X\cdot g^{y_{i,1}{m}_{i,1}+y_{i,2}{m}_{i,2}}{)}^{t_{i,1}{t}_{i,2}})$
- …
- $j=r_i,{\sigma }_i=(g^{{\prod }_j{t}_{i,j}},(X\cdot g^{{\sum }_j{y}_{i,j}{m}_{i,j}}{)}^{{\prod }_j{t}_{i,j}})=$$({\sigma }_1,{\sigma }_1^{x+{\sum }_j{y}_{i,j}{m}_{i,j}})$（用${\sigma }_1$表示了$g^{{\prod }_j{t}_{i,j}}$）
- 那么后面也要变换：${\sigma }^{\prime }=({\sigma }_1^t,{\sigma }_2^{\prime })$，${\sigma }_2^{\prime }=({\sigma }_2\cdot {\sigma }_1^{y_i{m}_i}{)}^t=({\sigma }_1^{x+{\sum }_j{y}_{i,j}{m}_{i,j}}\cdot {\sigma }_1^{y_i{m}_i}{)}^t=({\sigma }_2^{m_i}\cdot {\sigma }_1^{{\sum }_j{y}_{i,j}{m}_{i,j}}{)}^t$

• Output.
  $\mathcal{A}$最终在公钥$(p{k}_1,...,p{k}_r)$下的消息$(m_1^{\ast },...,m_r^{\ast })$上输出一个聚合签名$\sigma =({\sigma }_1,{\sigma }_2)$。当满足以下条件时，聚合签名σ是一个有效的伪造:
  
  1代表$e({\sigma }_1,\tilde{X}\cdot \prod p{k}_j^{m_j^{\ast }})=e({\sigma }_2,\tilde{g})$
  2代表$\mathcal{R}$知道所有$y_j$满足$p{k}_j={\tilde{g}}^{y_j},j=1,...,r$且$p{k}_j\ne p{k}^{\ast }$
  3代表在$1,...,r$中有一个唯一的$j^{\ast }$,$p{k}_{j^{\ast }}$，对应未查询过的$m_{j^{\ast }}$
  (下面构造single message的伪造)
  $\mathcal{R}$可以计算${\sigma }^{\ast }=({\sigma }_1^{\ast }\leftarrow {\sigma }_1,{\sigma }_2^{\ast }\leftarrow {\sigma }_2\cdot {\prod }_{j\ne j^{\ast }}{\sigma }_1^{-y_j\cdot m_j^{\ast }})$满足：
  
  分析:(这是不是构造了一个有效的单消息签名伪造？)
  $$\begin{array}{rl}{\sigma }^{\ast }& =({\sigma }_1^{\ast }\leftarrow {\sigma }_1,{\sigma }_2^{\ast }\leftarrow {\sigma }_2\cdot \prod _{j\ne j^{\ast }}{\sigma }_1^{-y_j\cdot m_j^{\ast }})\\ & =({\sigma }_1,{\sigma }_1^{x+{\sum }_{j\ne j^{\ast }}p{k}_j{m}_j^{\ast }+p{k}_{j^{\ast }}{m}_{j^{\ast }}^{\ast }}\cdot {\sigma }_1^{{\sum }_{j\ne j^{\ast }}-y_j\cdot m_j^{\ast }})\\ & =({\sigma }_1,{\sigma }_1^{x+p{k}_{j^{\ast }}{m}_{j^{\ast }}^{\ast }})\end{array}$$
  是构造了一个有效的未查询过的单消息签名。

但是必须另外证明签名查询是用${\sigma }^{\prime }\leftarrow ({\sigma }_1^t,({\sigma }_2\cdot {\sigma }_1^{{\sum }_{j=1}^{r_i}{y}_{i,j}\cdot m_{i,j}}{)}^t)$正确模拟的，$\sigma =({\sigma }_1,{\sigma }_2)$是在$p{k}^{\ast }$下$m_1$的签名，$t$是一个随机标量，而真正的签名应该是${\sigma }^{\prime }\leftarrow ({\sigma }_{i,1}^t,({\sigma }_{i,2}\cdot {\sigma }_{i,1}^{y\cdot m}{)}^t)$，其中${\sigma }_i=({\sigma }_{i,1},{\sigma }_{i,2})$是公钥$(p{k}_{i,1},...,p{k}_{i,r_i})$下消息$(m_{i,1},...,m_{i,r_i})$上的有效签名(或当$r=0$时${\sigma }_i=(g,X)$)， $t$是一个随机标量。

但可以注意到，在这两种情况下，${\sigma }_1^{\prime }$是${\mathbb{G}}_1^{\ast }$中的一个随机元素，而${\sigma }_2^{\prime }$是满足$e({\sigma }_2^{\prime },\tilde{g})=e({\sigma }_1^{\prime },\tilde{X}\cdot {\prod }_{j=1}^{r_i}p{k}_{i,j}^{m_{i,j}}\cdot p{k}^{m_i})$的唯一元素。因此，完美的模拟。
结论：多消息伪造$\to$单消息伪造；逆否命题：单消息不可伪造$\to$多消息不可伪造