BLS签名方案

请注意，本文编写于 846 天前，最后修改于 578 天前，其中某些信息可能已经过时。

Abstract

打算做一个ZKP的门限签名方案，于是看一下现有的经典签名方案，这篇博客是BLS方案的论文$[1]$精读

文章在某些椭圆和超椭圆曲线上引入了一个基于计算Diffie-Hellman假设的短签名方案，签名长度是DSA签名的一半，具有相似的安全级别

文章设计了一个短签名方案，可用于由人输入签名或通过低带宽信道发送签名的系统

1 Introduction

在要求人工输入签名的环境中，需要短数字签名，例如，产品注册系统通常要求用户输入CD标签上提供的签名

一般来说，在低带宽通信环境中需要短签名，例如，在邮票上打印签名时需要短签名

目前，与它们提供的安全性相比，两种最常用的签名方案RSA和DSA提供了相对较长的签名，例如，模数为1024bit时，RSA签名的长度为1024bit，类似地，模数为1024bit时时，标准DSA签名的长度为320bit，DSA的椭圆曲线变体，如ECDSA，长度也为320bit长，320bit签名太长，无法由人工输入

本文提出了一种签名方案，其长度约为160bit，并提供类似于320bit的DSA签名的安全级别

假设计算Diffie-Hellman问题（CDH）在特征为3的有限域上的某些椭圆曲线上是困难的，则本文的签名方案在选择消息攻击（RO模型下）是安全的，不会出现存在伪造

生成签名为曲线上的简单乘法，使用曲线上的双线性配对来验证签名，本文的签名方案固有的使用了ECC的特征，因此在域$\mathbb F^*_p$上没有等价的方案

由于使用的曲线的特性，目前只能提供以下给定长度的特征，求解这些群中CDH问题的最著名算法需要特征为3的有限域上的离散对数，该域的大小在下表中最右侧的列给出（单位为bit）

第二行显示，本文的可以获得长度为154位的签名，其安全性相当于320位DSA或320位ECDSA，伪造154位签名的最著名算法需要在大小为923位的有限域或大小为151位的椭圆曲线组上求解CDH问题，在第3.5节中，我们概述了推广我们的技术和构建任意长度签名的方法

本文提出的签名方案使用CDH问题很难解决，但决策Diffie-Hellman问题（DDH）很容易解决的群，我们称这些群为Gap-Diffie-Hellman群，简称GDH群

2 Signature schemes based on Gap-Diffie-Hellman

本文提出了一个适用于任意Gap-Diffie-Hellman群的签名方案，该方案类似于Chaum和Pederson提出的不可否认签名方案

2.1 Gap Diffie-Hellman Groups（CDH groups）

考虑一个（乘法）循环群$G=<g>$，其中$p=|G|$为素数，对$G$上的三个问题比较感兴趣

Group Action（群行为）：给定$u,v\in G$，求$uv$
Decision Diffie-Hellman（决定性DH）：对于$a,b,c\in\mathbb Z^*_p$，给定$(g,g^a,g^b,g^c)$，求$c=ab$
Computational Diffie-Hellman（计算性DH）：对于$a,b\in\mathbb Z^*_p$，给定$(g,g^a,g^b)$，计算$g^{ab}$

Gap Diffie-Hellman Groups的定义如下

Definition 1：若群操作可在一个单位时间内计算，且决定性DH可在至多$\tau$个单位时间内计算，则称G为一个$\tau$-DH决定群
Definition 2：算法$\mathcal A$在群$G$上解决CDH问题的优势定义为
$$ Adv_{CDH_{\mathcal A}}\overset{def}{=}Pr[\mathcal A(g,g^a,g^b)=g^{ab}:a,b\stackrel{R}{\larr}\Z^*_p] $$
概率取决于$a,b$的选择和算法$\mathcal A$的掷币
同时记$\mathcal A(t,\epsilon)$表示算法$\mathcal A$在时间$t$内以$Adv_{CDH_{\mathcal A}}\geq\epsilon$的优势攻破CDH
Definition 3：若一个素数阶群$G$既是$\tau$-DH决定群，又不存在$\mathcal A(t,\epsilon)$算法，则称该群为$(\tau,t,\epsilon)$-GDH群

2.2 The GDH Signature Scheme

GDH签名方案允许在任意消息$m\in \{0,1\}^*$上创建签名，签名$\sigma$是群$G$上的一个元素，基群$G$及其生成元为系统参数，记$G^*=G\backslash\{1\}$

签名方案包括三个算法$KeyGen,Sign,Verify$，并使用全域Hash函数$h:\{0,1\}^*\rarr G^*$，对方案的安全性分析会将Hash函数视为Random Oracle，3.3节中削弱了对全域Hash的要求

Key Generation：选择$x\stackrel {R}{\larr}\Z^*_p$，计算$v\larr g^x$，算法输出公钥为$PK=v$，私钥为$SK=x$
Signing：给定私钥$x$和消息$m\in \{0,1\}^*$，计算$h\larr h(m),\sigma\larr h^x$，算法输出签名值$\sigma\in G^*$
Verification：给定公钥$v$，消息$m$和签名值$\sigma$，计算$h\larr h(m)$，同时验证$(g,v,h,\sigma)$为一个合法的DH元组，若验证通过则输出$valid$（或者1），否则输出$invalid$（或者0）

注意到GDH签名是$G^*$上的元素，因此为了构建短签名，我们需要一个GDH群，其群元素可以以短的方式表示，构造这样的群具体可以看第三节

2.3 Security

本节证明了GDH签名方案在选择消息攻击下对存在伪造的安全性

Definition 4：伪造者伪造签名的算法记为$\mathcal F$，同时允许其访问签名预言机$S$，则算法$\mathcal F$的优势定义如下
$$ Adv_{Sig_{\mathcal F}}\stackrel{def}{=}Pr[Verify(PK,m,\sigma)=valid:(PK,SK)\stackrel{R}{\larr}KeyGen,(m,\sigma)\stackrel{R}{\larr}\mathcal F^S(PK)] $$
上述概率取决于密钥生成算法和伪造者的掷币

这里允许敌手自适应的查询签名预言机，其任意查询都可以（可能）取决于先前的任意查询，但是可能不会为先前查询预言机的消息发出签名，此外敌手还可以访问全域Hash函数（该Hash函数被视为Random Oracle）

Definition 5：若伪造者$\mathcal F$可以在至多时间$t$，对Hash函数发起至多$q_H$次请求和对签名预言机$S$发起至多$q_S$次请求，且有$Adv_{Sig_{\mathcal F}}\geq \epsilon$，则称$\mathcal F$以$(t,q_H,q_S,\epsilon)$攻破签名方案
Definition 6：若在自适应选择消息攻击中，不存在$(t,q_H,q_S,\epsilon)$的伪造者攻破$\mathcal F$，则称该方案对存在性伪造为$(t,q_H,q_S,\epsilon)$安全的

下面的定理表明GDH签名方案是安全的，原文的第4节给出了定理的证明

Theorem：记$G$为一个$(\tau,t',\epsilon')$-GDH群，群的阶为$p$，则称基于群$G$的Gap签名方案在自适应选择消息攻击下防止存在性伪造为$(t,q_H,q_S,\epsilon)$安全的，其中
$$ t\leq t'-2c_{\mathcal A}(\lg p)(q_H+q_S) \\\epsilon \geq 2e\cdot q_S \epsilon' $$
其中$c_{\mathcal A}$为一个小常数，$e$为自然对数

3 Building Gap-Diffie-Hellman groups with small representations

使用Weil配对，某些椭圆曲线可以用作GDH群，本节介绍域$\mathbb F_{3^l}$上的曲线$y^2=x^3+2x\pm1$

3.1 Elliptic Curves and the Weil Pairing

如果我们可以使用椭圆曲线构造具有大素数阶的群$G$，则椭圆曲线可以作为GDH签名方案的基础，在该群$G$上计算Diffie-Hellman是困难的，但DDH很容易

首先描述一下$E$的子群上CDH难解性的一个必要条件

Definition 7：记$p$为素数，$l$为正指数，$E$为$\mathbb F_{p^l}$上有$m$个点的曲线，记$P$为$E$上阶为$q$的点，且满足$q^2\nmid m$，若$p^l$在域$\mathbb F^*_p$中的阶为$\alpha(\alpha>0)$，则称子群$$具有安全乘数$\alpha$，换言之，若子群$$具有安全乘数$\alpha$，则
$$ q |(p^{l\alpha}-1) \ and \ q\nmid(p^{lk}-1) ,\forall k=1,2,...,\alpha-1 $$

众所周知，为了使得CDH在子群$$中是困难的，必须要存在安全乘数$\alpha$，使得这个子群很大，但是为了得到一个子群上高效的DDH算法，我们又需要$\alpha$不要太大

综上，构建短签名方案的问题在于，如何找到这个安全乘数$\alpha$，既能确保其足够大来满足安全性，又确保其不那么大以满足高效性

采用当前的安全参数$\alpha=6$时足以构建短签名，$\alpha$较大的椭圆曲线目前仍然是个开放问题，比如$\alpha=10$（具体可以看3.5节）

Discrete-log on elliptic curves

记$$为$E/\mathbb F_{p^l}$的阶为$q$的子群，安全乘数为$\alpha$，接下来简单介绍两个计算$$上DLOG的标准（两种DLOG攻击方法）

MOV攻击：Menezes，Okamoto，Vanstone三人提出，使用有效可计算的同态，将$$上DLOG问题映射到$\mathbb F_{p^l}$的扩域上，记该扩域为$\mathbb F_{p^{li}}$，要求该同态下$$的像为$\mathbb F_{p^{li}}^*$中一个阶为$q$的子群，从而可以得到$q|(p^{il}-1)$，根据定义有$i\geq \alpha$，因此通过MOV方法，至多可以将$$上的DLOG问题简化为$\mathbb F_{p^{l\alpha}}^*$的子群上的问题，因此，为了确保$$上DLOG问题的难解性，我们需要安全乘数$\alpha$足够大
Generic：一般的DLOG算法，比如BSGS或者Pollard Rho的期望运行时间为$O(\sqrt q)$，因此我们还需要确保$q$足够大

Decision Diffie-Hellman on elliptic curves

记$P\in E/F_{p^l}$为一个点，阶为$q$，假设子群$$的安全乘数为$\alpha$，假设$q\nmid(p^l-1)$，Balasubramanian和Koblitz$[2]$的结果表明，$E/F_{p^{l\alpha}}$中包含一个与$P$线性无关的点$Q$，该点$Q\in E/F_{p^{l\alpha}}$可被高效找到，注意到$P,Q$的线性无关性，因此可以用Weil对验证

对于两个线性无关的点$P\in E/F_{p^l},Q\in E/F_{p^{l\alpha}}$，阶均为$q$，利用Weil对可以构建DDH Oracle，具体如下

记$E[q]$表示由$P,Q$生成的关于$E/F_{p^{l\alpha}}$的子群，Weil对为一个映射$e:E[q]\times E[q]\rarr F^*_{p^{l\alpha}}$，映射满足下列特性

Identity（一致性）：给定$\forall R\in E[q],e(R,R)=1$
Bilinear（双线性性）：对于$\forall R_1,R_2\in E[q],\forall a,b\in \Z$，有$e(aR_1,bR_2)=e(R_1,R_2)^{ab}$
Non-degenerate（非退化性）：若$R\in E[q]$，且对于$\forall R'\in E[q]$，均有$e(R,R')=1$，则$R=\mathcal O$
Computable（可计算性）：对于$\forall R_1,R_2\in E[q]$，配对$e(R_1,R_2)$可高效计算

还有一点需要注意，若$R_1,R_2$是线性无关的，则$e(R_1,R_2)=1$

因此，对于线性无关且阶均为$q$的两个点$P,Q$，Weil对使得我们可以利用元组$(P,aP,Q,bQ)$来确定$a,b$是否满足$a\equiv b \ mod\ q$，也即

$$ a\equiv b \ mod\ q \Lrarr e(P,bQ)=e(aP,Q) $$

假设我们知道$$到$<Q>$的一个可计算的同态$\phi$，不难得到这样的$\phi$，满足对于$\forall a,\phi(aP)=axQ$，其中$xQ=\phi(P)$，此时Weil对允许我们利用元组$(P,aP,bP,cP)$来确定$a,b,c$是否满足$ab\equiv c \ mod \ q$，也即确定

$$ ab\equiv c \ mod \ q\Lrarr e(P,\phi(cP))=e(aP,\phi(bP)) $$

利用这个同态$\phi$，Weil对提供了一个DDH算法，注意到这个DDH算法需要对$F_{p^{l\alpha}}$上的点进行两次Weil对计算

3.2 A Special Supersingular Curve

利用3.1节介绍的方法，本节介绍在域$\mathbb F_{3^l}$上由曲线$y^2=x^3+2x\pm1$给出的超奇异椭圆曲线$E$导出的具有短表示的GDH群，然后展示这是唯一一个$\alpha=6$的超奇异椭圆曲线

MOV约化将$E/\mathbb F_{3^l}$中的DLOG问题映射到$\mathbb F^*_{3^{6l}}$，这意味着我们可以使用相对较小的$l$来做到短签名，但是安全性仍然取决于大型有限域中DLOG问题

接下来看两个简单的引理来描述这些曲线的行为（具体可以看原文的参考文献$[13,23]$）

Lemma 1：由$y^2=x^3+2x+1$定义的$\mathbb F_{3^l}$上的曲线$E^+$满足
$$ \#E^+/\mathbb F^{3^l}=\begin{cases} 3^l+1+\sqrt{3\cdot 3^l} ,l=\pm1 \ mod\ 12\\ 3^l+1-\sqrt{3\cdot 3^l} ,l=\pm5 \ mod\ 12 \end{cases} $$
由$y^2=x^3+2x-1$定义的$\mathbb F_{3^l}$上的曲线$E^-$满足
$$ \#E^-/\mathbb F^{3^l}=\begin{cases} 3^l+1-\sqrt{3\cdot 3^l} ,l=\pm1 \ mod\ 12\\ 3^l+1+\sqrt{3\cdot 3^l} ,l=\pm5 \ mod\ 12 \end{cases} $$

上述引理证明可以看$[13]$的第二节

接下来选择$E^+$或$E^-$，构造$\mathbb F_{3^l}$上具有$3^l+1+\sqrt{3\cdot 3^l}$个点的曲线（$E^+$中$l=\pm1 \ mod\ 12$，$E^-$中$l=\pm5 \ mod\ 12$）

Lemma 2：记$E为$由$y^2=x^3+2x+1$定义的$\mathbb F_{3^l}$上的曲线，其中$l=\pm1 \ mod\ 12$或$l=\pm5 \ mod\ 12$，则$\#(E/\mathbb F_{3^l}) |(3^{6l}-1)$

证明如下

Proof：由于$(x^6-1)=(x^3+1)(x^3-1)=(x-1)(x+1)(x^2+x+1)(x^2-x+1)$，因此$(x^2-x+1)|(x^6-1)$，具体而言若$x=3^l$，则$(3^{2l}-3^l+1)|(3^{6l}-1)$
根据前面提到的，我们知道$\#(E/\mathbb F_{3^l})=3^l+1\pm\sqrt{3\cdot 3^l}$，而$(3^l+1+\sqrt{3\cdot 3^l})(3^l+1-\sqrt{3\cdot 3^l})=3^{2l}-3^l+1$，因此$\#(E/\mathbb F_{3^l})|(3^{6l}-1)$，证毕

结合引理1和2，对于与$l$相关的值，曲线$E^+/\mathbb F_{3^l}$和$E^-/\mathbb F_{3^l}$的安全乘数最大为6（$\alpha |6)$，不过对于曲线的特定素子群，安全参数是否实际为6必须通过计算确定

Automorphism of $E^+/\mathbb F_{3^l}$and $E^-/\mathbb F_{3^l}$

对于满足$l=\pm1 \ mod\ 12$或$l=\pm5 \ mod\ 12$的$l$，计算$\mathbb F_{3^{6l}}$上的三个参数$u,r^+,r^-$，满足

$$ \begin{aligned} u^2=&-1\\ (r^+)^3+2r^+2=&0\\ (r^-)^3+2r^--2=&0 \end{aligned} $$

然后考虑下面这两个$\mathbb F_{3^{6l}}$上的映射

$$ \begin{aligned} &\phi^+(x,y)=(-x+r^+,uy)\\ &\phi^-(x,y)=(-x+r^-,uy) \end{aligned} $$

这里有一个引理

Lemma 3：令$l=\pm1 \ mod\ 12$或$l=\pm5 \ mod\ 12$，记$\phi^+$为$E^+/\mathbb F_{3^l}$上的自同构，$\phi^-$为$E^-/\mathbb F_{3^l}$上的自同构，若$P$为$E^+/\mathbb F_{3^l}$（或$E^-/\mathbb F_{3^l}$）上阶为$q$的点，则$\phi^+(P)$（或$\phi^-(P)$）为一个与$P$线性无关的阶为$q$的点

具体证明看Silverman$[22]$的第326页

这个引理说明了，对于任何这些曲线上的$q$阶点$P$，适当的自同构允许我们解决前两节提到的$G=$上的DDH问题

3.3 Hashing onto Elliptic Curves

CDH签名方案需要一个Hash函数$h:\{0,1\}^*\rarr G^*$，其中$G$为GDH群，这里需要使用一个ECC曲线的子群作为这个GDH群，由于很难构建直接hash到椭圆曲线子群上的Hash函数，因此需要稍微放宽对Hash的要求

记$E/\mathbb F_{p^l}$为一个由$y^2=f(x)$定义的阶为$m$的曲线，记$P\in E/\mathbb F_{p^l}$为曲线上一点，阶为$q$，满足$q^2\nmid m$，用$G=$作为这个GDH子群来实现GDH签名方案

假设有一个Hash函数$h':\{0,1\}^*\rarr\mathbb F_{p^l}\times \{0,1\}$，这个Hash函数可利用标准密码学Hash函数来构建（在$h'$的安全性分析中将其视为Random Oracle）

然后介绍一个确定性算法：$MapToGroup$，来将$\{0,1\}^*$Hash到$G^*$（这里还需要固定一个小参数$I=\lceil \log_2\log_2(1/\delta) \rceil$，其中$\delta$为错误概率界的某个期望，看不懂没关系，不会影响理解）

$MapToGroup_{h'}$：算法定义了$h:\{0,1\}^*\rarr G^*$如下
给定消息$M\in \{0,1\}^*$，令$i\larr 0$
计算$(x,b)\larr h'(i||M)\in\mathbb F_{p^l}\times \{0,1\}$
若$f(x)$为$\mathbb F_{p^l}$上的二次剩余，则
记$y_0,y_1\in \mathbb F_{p^l}$为$f(x)$的两个根，以$b\in\{0,1\}$区分这两个根，同时将$y_0,y_1$视为$\mathbb F_{p^l}$上度为$l-1$的多项式（这这么做是确保将这两个数视为$[0,p]$上的整数时，$y_0$中的常数项不会大于$y_0$中的常数项），然后令点$\widetilde P_M\in E/\mathbb F_{p^l}$的坐标为$\widetilde P_M=(x,y_b)$
计算$P_M=(m/q)\widetilde P_M$，此时$P_M\in G$，若$P_M\in G^*$，则输出$MapToGroup_{h'}(M)=P_M$并结束算法
否则$i\larr i+1$，若$i=2^I$，结束算法并报错，否则跳转至步骤2

选择适当大的$I$可以将错误概率降低至任意小，对于每个$i$而言，$h'(i||M)$计算得到$G^*$中的点的概率约为$0.5$（具体概率取决于选择的Random Oracle $h'$），因此$h'$调用次数的期望为2次，对于给定消息$M$而言，其不可Hash的概率（也即上述算法报错的概率）为$1/2^{2^I}\leq \delta$

曲线Hash简单来说就是将得到的哈希值作为点的$ x $值寻找椭圆曲线上的对应点，但是根据ECC的性质，一个$x$值会对应两个点$(x,y)$和$(x,-y)$，因此上述这个$MapToGroup$算法实际上只有大约一半的概率（取决于$h'$）找到这个点，为了防止算法失败，我们可以在消息$M$前面附上一个计数器$i$（也即第二步中的$i$），若某次迭代中失败了就累加计数器，直到找到位置，这样一来提高了算法的正确性

Lemma 4：假设GDH签名方案在子群$G$中，且采用随机Hash函数$h:\{0,1\}^*\rarr G^*$下是$(t,q_H,q_S,\epsilon)$安全的，则Hash函数$h$由$MapToGroup_{h'}$计算时，$h$为$(t-2^Iq_H\lg m,q_H,q_S,\epsilon)$安全的（其中$h':\{0,1\}^*\rarr\mathbb F_{p^l}\times \{0,1\}$）

证明可以看原文$[1]$

3.4 A concrete short signature scheme

前几节内容介绍了使用GDH群的具体签名方案，该GDH群来自由$y^2=x^3+2x\pm1$定义的曲线$E/\mathbb F_{3^l}$，这些曲线的一些实例化可以看下表

需要注意这些实例化中都限制了$l$为素数，以避免Weil-descent攻击$[3,4]$

如3.3节所介绍的，使用$MapToGroup_{h'}$算法将任意串映射到$E$上阶为$q$的点和一个单比特

接下来看如何用上一节介绍的$MapToGroup$来构建具体的签名方案

Key generation：给定表1中任意一个$l$值，记$E/\mathbb F_{3^l}$为该$l$值对应的曲线，记$q$为曲线的阶的因数分解中最大的素数，记$P\in E/\mathbb F_{3^l}$为阶为$q$的点，随机选择$x\in _R\Z^*_q$，计算$R\larr xP$，输出公钥$PK=(l,q,P,R)$，私钥$SK=x$
Signing：对于消息$M\in \{0,1\}^*$，利用$MapToGroup_{h'}$将其映射到点$P_M=$，然后计算$S_M\larr xP_M$，输出签名值$\sigma$为$S_M$的$x$坐标，也即$\sigma\in\mathbb F_{3^l}$
Verification：给出公钥$PK=(l,q,P,R)$、消息$M$和签名值$\sigma$，验证过程如下
找到一个阶为$q$的点$S\in E/\mathbb F_{3^l}$，且该点的$x$坐标为$\sigma$，$y$坐标为$F_{3^l}$中的某个值，若不存在此点，则结束算法并拒绝签名值
利用Weil对，在曲线$E/\mathbb F_{3^{6l}}$上计算$u\larr e(P,\phi(S)),v\larr e(R,\phi(h(M))))$，其中$\phi$为Lemma 3中提到的自同构
若有$u=v$或$u^{-1}=v$，则接受签名，否则拒绝签名

注意到$(\sigma,y),(\sigma,-y)$都是$E/\mathbb F_{3^{l}}$上的点，这两个点中的任何一个都可以是签名算法中用于生成该签名值得点$S_M$，根据椭圆曲线的特性，有$(\sigma,y)=-(\sigma,-y)$也在曲线上，因此根据Weil对，有$e(P,\phi(-S))=e(P,\phi(S))^{-1}$ ,因此当$u=v$时，意味着$(P,R,h(M),S)$是一个DH元组，而$u^{-1}=v$意味着$(P,R,h(M),-S)$是一个DH元组

方案简单来说就是先利用$MapToGroup_{h'}$计算曲线Hash，然后再对得到的曲线上的点乘上私钥，得到的新的点的横坐标就是签名值

这里有一个引理

Lemma 5：若$E/\mathbb F_{3^l}$为表1中的一条曲线，$q$为$\#E$的最大素因子，$P$为$E$上阶为$q$的点，且$G=$上不存在$(t_0,\epsilon_0)$攻破CDH的算法，令$h':\{0,1\}^*\rarr\mathbb F_{3^l}\times \{0,1\}$为一Random Oracle，则上述签名方案在选择消息攻击下进行存在性伪造的敌手为$(t,q_H,q_S,\epsilon)$安全的，其中
$$ t\leq t_0-2c_{\mathcal A}(\lg q)(q_H+q_S)-2^Iq_H\lg m-2\tau,\epsilon\geq2e\cdot q_S\epsilon $$
其中$c_{\mathcal A}$为一个小常数，$e$为自然对数

上述引理简单来说就是能够在选择消息攻击下进行存在伪造的攻击者（在随机预言模型中）也能够攻破$E/\mathbb F_{3^l}$中的DH问题，证明可以看原文$[1]$

3.5 An open problem:short signatures with high security

3.4节中，作者建议使用$\mathbb F_{3^l}^*$上的超奇异曲线来构建一个短签名方案，该曲线上的DLOG问题的安全性与$\mathbb F_{3^{6l}}^*$相当，不过一味的使用超奇异曲线不一定可以确保安全，使用其他曲线或超椭圆曲线可能可以达到更高的安全乘数

3.2节中介绍了$\mathbb F_{3^l}$上$E^+$和$E^-$曲线的安全乘数至高为6，但这也是任何超奇异曲线能达到的最大值（原文参考文献$[15,23]$），在$\alpha$值稍高的（非超奇异）椭圆曲线上实例化GDH签名方案将会增加验证需要的工作量，但同时也可以提高在比较签名位长度下MOV攻击的安全性

考虑一个具有$m$个点的曲线$E/\mathbb F_{p^l}$和一个大素数$q$，满足$q|m$，考虑一个阶为$q$，安全参数为$\alpha$的子群和两个线性无关的阶为$q$的点$P\in E/\mathbb F_{p^l},Q\in E/\mathbb F_{p^{l\alpha}}$

根据$[2]$中，若假设$q\nmid (p^l-1)$，则此类与$P$线性无关的点$Q$必然存在，此时此类曲线无需存在一个$$和$<Q>$之间的自同构映射，因此可以稍微修改一下Gap签名方案，将这两个群一起使用

根据前面提到的内容，使用Weil配对，可以通过元组$(P,aP,Q,bQ)$来确定是否有$a=b$，此时称为DDH问题的补（co-Decision Diffie Hellman problem），显然这个补问题也是易于计算的：对于给定的元组$(P,Q,aQ)$，计算$aP$

具体的（基于co-gap）变体签名方案如下

Key Generation：令$P\in E/\mathbb F_{p^l},Q\in E/\mathbb F_{p^{l\alpha}}$为两个线性无关的阶为$q$的点，选择$x\stackrel{R}{\larr}\Z^*_p$，计算$R\larr xQ$，输出公钥$PK=(E/\mathbb F_{p^l},q,Q,R)$，私钥$SK=x$
Signing：对于$SK=x$和消息$M\in \{0,1\}^*$，利用$MapToGroup_{h'}$将其映射到点$P_M=$，然后计算$S_M\larr xP_M$，输出签名值$\sigma$为$S_M$的$x$坐标，也即$\sigma\in\mathbb F_{p^l}$
Verification：对于公钥$PK=(l,q,P,R)$、消息$M$和签名值$\sigma$，令$S$为$\mathbb F_{p^l}$上阶为$q$的点，其$x$坐标为$\sigma$，$y$坐标为某个$y\in \mathbb F_{p^l}$（若不存在这样的点，则结束算法并拒绝签名值），计算$u\larr e(Q,S),v\larr e(R,h(M))$，若有$u=v$或$u^{-1}=v$，则接收签名，否则拒绝签名

和3.4节类似，验证阶段的测试确保$(P,R,h(M),S)$或$(P,R,h(M),-S)$是一个合法的co-Diffie-Hellman元组

由于$R\in E/\mathbb F_{p^{l\alpha}}$是一个很长的元素，因此公钥很长，但是签名值$\sigma\in\mathbb F_{p^l}$相对较短，该方案可以做到没有敌手可以以$(t,\epsilon)$攻破co-Decision Diffie Hellman problem

上述方案的问题在于构造$\alpha$值较大的曲线，比如$\alpha=10$，目前构建$\alpha=10$的曲线簇仍然是一个开放问题

Galbraith构造了具有“大”安全乘数的高亏格超奇异曲线，比如超奇异曲线$y^2+y=x^5+x^3$具有$\mathbb F_{2^l}$上的安全乘数12，由于亏格为2的曲线的雅可比矩阵上的一点由$\mathbb F_{2^l}$上的两个值表示，因此最后得到的签名长度为$2l$比特，这意味着我们可以在有限域$\mathbb F_{2^{12l}}$中安全地计算CDH并得到长度为$2l$的签名

签名长度和有限域次数之间的因子6与椭圆曲线情况相同，因此，这种亏格为2的曲线并没有提高签名的安全性，但在签名长度方面比表1中给出的更具多样性，由于该曲线是在特征为2的域上定义的，因此比在特征为3的域上定义的曲线更适合计算

Galbraith证明了亏格为2的超奇异曲线的雅可比矩阵的最大安全乘数为12，因此，亏格为2的超奇异曲线不会给出具有更高安全性的短签名，能否建立一个亏格为3的超椭圆曲线族，以提供更高安全性的短签名，这是一个悬而未决的问题

4 Proof of Security Theorem

安全性理论证明，没看，以后再看

5 Experimental results

程序运行在GNU/Linux的1 GHz奔腾III计算机上，结果如下

总结

BLS等人提出了一个基于Weil配对的短签名方案，整个方案很简洁，签名值只是有限域上的一个元素（基于DLOG的DSA的签名值为两个元素），而且签名值长度仅为154位，安全性与320位的DSA相当

此外，文中还提到了几个点，一个是采用$\mathbb F_{3^{l}}$上的曲线$y^2=x^3+2x\pm1$时，MOV攻击将该曲线中的CDH问题映射为$\mathbb F_{3^{6l}}$中的CDH问题

另一个是BLS方案的安全性可归约到大小约为$2^{923}$的有限域中求解Diffie-Hellman问题

文中还讨论了安全乘数$\alpha$的大小问题和超奇异曲线的问题，超奇异曲线的安全乘数至高为6，为了做到更高的安全性，是否有非超奇异的曲线来构造此类签名方案

后记

主要是想做一个基于zkp的门限签名方案，然后之前看了Bulletproof的范围证明和聚合，感觉挺好用的

其实Schnorr，DSA，BLS等签名方案都支持签名聚合，但是自己一直在想怎么将ZKP用进去

或许是学的一知半解，或许是看的paper太少了还没有头绪，感觉有点焦虑

慢慢琢磨吧，还是得多看多学多记

References

$[1]$ Dan Boneh, Ben Lynn, Hovav Shacham:Short Signatures from the Weil Pairing. J. Cryptol. 17(4): 297-319 (2004)

$[2]$ R. Balasubramanian and N. Koblitz. The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm. Journal of Cryptology, 11(2):141–145, 1998.

$[3]$ S. Galbraith and N. P. Smart. A Cryptographic Application of Weil Descent. In M. Walker, editor, Cryptology and Coding, volume 1746 of LNCS, pages 191–200. Springer-Verlag, 1999.

$[4]$ P. Gaudry, F. Hess, and N. P. Smart. Constructive and Destructive Facets of Weil Descent on Elliptic Curves. Technical Report CSTR-00-016, Department of Computer Science, University of Bristol, 2000.

BLS签名

Abstract

1 Introduction

2 Signature schemes based on Gap-Diffie-Hellman

2.1 Gap Diffie-Hellman Groups（CDH groups）

2.2 The GDH Signature Scheme

2.3 Security

3 Building Gap-Diffie-Hellman groups with small representations

3.1 Elliptic Curves and the Weil Pairing

Discrete-log on elliptic curves

Decision Diffie-Hellman on elliptic curves

3.2 A Special Supersingular Curve

Automorphism of $E^+/\mathbb F_{3^l}$and $E^-/\mathbb F_{3^l}$

3.3 Hashing onto Elliptic Curves

3.4 A concrete short signature scheme

3.5 An open problem:short signatures with high security

4 Proof of Security Theorem

5 Experimental results

总结

后记

References

添加新评论

评论列表

BLS签名方案

Abstract

1 Introduction

2 Signature schemes based on Gap-Diffie-Hellman

2.1 Gap Diffie-Hellman Groups（CDH groups）

2.2 The GDH Signature Scheme

2.3 Security

3 Building Gap-Diffie-Hellman groups with small representations

3.1 Elliptic Curves and the Weil Pairing

Discrete-log on elliptic curves

Decision Diffie-Hellman on elliptic curves

3.2 A Special Supersingular Curve

Automorphism of $E^+/\mathbb F_{3^l}$and $E^-/\mathbb F_{3^l}$

3.3 Hashing onto Elliptic Curves

3.4 A concrete short signature scheme

3.5 An open problem:short signatures with high security

4 Proof of Security Theorem

5 Experimental results

总结

后记

References

精读Groth16算法

RSA门限签名方案

添加新评论

评论列表