ISSN 
下载: 
-
盲数字签名的概念是由文献[1]提出的，在这种机制中签名者并不知道他所签发消息的具体内容，也不能把签名过程和最终的签名对应起来。因此，盲数字签名可以很好的保护用户隐私，在电子支付、电子投票等领域得到广泛应用。在全盲数字签名中，签名者不知道最终签名的任何信息，这可能导致签名被恶意用户非法使用。为了解决该问题，文献[2]提出了部分盲数字签名的概念。这种机制产生的签名中嵌入了用户和签名者协商好的公共信息，可以很好地解决签名被非法使用的问题。
为了解决传统公钥密码机制中的证书问题，文献[3]提出了基于身份的公钥密码。在公钥密码中，用户的身份(如学号、电子邮件等)就是用户的公钥。因此可以解决传统公钥密码中的证书管理问题。在这种机制中，用户的私钥是由私钥生成中心(key generation center,KGC)通过用户的身份来生成的。因此密钥中心可以解密任何用户的密文，也可以伪造用户的签名。为了解决基于身份的公钥密码的密钥托管问题，文献[4]提出了无证书公钥密码机制。自此，科研人员提出了许多无证书密钥协商机制[5-7]和加密机制[8-9]。无证书部分盲签名作为一种非常重要的密码机制得到了广泛关注和研究。文献[10]提出了第一个无证书部分盲签名机制。为改进性能，文献[11-13]分别提出了一种改进的无证书部分盲签名机制。然而，上述无证书部分盲签名机制都需要双线性对运算。理论分析[14]和实验结果[15]表明：在相同安全性的条件下，执行一次双线性对操作的时间至少是椭圆曲线上点乘运算的十余倍。因此，不用双线性对运算的部分盲签名机制具有更好的性能。文献[16]提出了一个无需双线性对运算的无证书部分盲签名机制，同时在随机预言模型下证明了其安全性。
本文将文献[16]中的机制进行安全性分析。通过具体的攻击来证明他们的部分盲签名机制不能提供不可伪造性。因此，该机制并不能满足应用的需求。为了克服安全缺陷，本文提出了一种新的无证书部分盲签名机制，并在随机预言模型下证明其安全性。
-
设p和q是两大素数。E(Fp)是定义在有限域Fp上的椭圆曲线，G是由E(Fp)上的点构成的阶为n的加法群。设P是群G的基点，定义在椭圆曲线上的离散对数如下所述。
离散对数(discrete logarithm,DL)问题：对于给定G中的一个元素aP，计算$a\in Z_{q}^{*}$，其中a是一个未知的元素。
设A是一个多项式算法，定义它解决DL问题的优势为：
$$\text{Ad}{{\text{v}}^{\text{DL}}}(A)=\Pr [A(aP)=a|a\in Z_{q}^{*}]$$ DL假设：对于任意的多项式算法A，$\text{Ad}{{\text{v}}^{\text{DL}}}(A)$是可以忽略的。
-
无证书部分盲签名机制由4个算法组成[16]：系统建立算法、密钥产生算法、签名发布算法和签名验证算法。其中，签名发布算法又包括签名、盲化和去盲3个子算法：
1) 系统建立算法：输入安全参数，输出系统参数和密钥生成中心的主私钥x。
2) 密钥产生算法：输入系统参数，用户身份IDi，KGC生成用户的部分私钥yi和部分公钥Yi，用户选择私有秘密xi并生成私钥Si和公钥Pi。
3) 签名发布算法：输入系统参数，签名者私钥Si和消息m，签名者和请求者进行交互，依次完成签名、盲化和去盲3个子算法。最后，生成消息的签名σ。
4) 签名验证算法：输入系统参数、消息m、签名者身份IDi、签名者公钥 Pi 和和签名σ，用户通过该算法验证签名的合法性。
部分盲签名机制的部分盲性是指签名者不能把最终的签名结果和签名实例对应起来。 在攻击者A的攻击下，部分盲性的形式化定义如下：
1) 挑战者C执行系统参数建立算法，生成系统参数和主私钥，并把系统参数返回给攻击者。
2) 挑战者C选择随机数$b\in \{0,1\}$，然后让A对消息$({{m}_{b}},c)$进行部分盲签名，其中c 是C 和A 之间的协商信息。C执行去盲操作并把$({{m}_{b}},c)$的最终签名发送给A。
3)A输出对b的猜测${b}'$。
如果${b}'=b$，则称A赢得上述游戏。定义A赢得上述游戏的优势为$\text{Adv}(A)=|2\Pr [b={b}']-1|$。
定义 1 无证书部分盲签名机制的部分盲性
如果不存在攻击者A能够在概率多项式时间内以不可忽略的优势赢得上述游戏，则称无证书部分盲签名机制满足部分盲性。
在攻击者$A\in \text{ }\!\!\{\!\!\text{ }A1,A2\text{ }\!\!\}\!\!\text{ }$的攻击下，在概率多项式时间内，如果攻击者没有不可忽略的优势在此游戏中获胜，则称无证书部分盲签名机制在适应性选择消息攻击下具有不可伪造性。
在无证书部分盲签名机制的不可伪造安全中，有两种类型的攻击者：类型I攻击者(A1))和类型II攻击者(A2)。A1不知道KGC的主私钥，但他可以使用任意值替换用户的公钥。A2不能替换用户的公钥，但是他可以获取KGC的主私钥。对于一个攻击者$A\in \text{ }\!\!\{\!\!\text{ }A1,A2\text{ }\!\!\}\!\!\text{ }$来说，他可以进行以下查询：
Hash查询：输入任意消息M，挑战者C把M的哈希值返回给A 。
部分密钥查询：输入用户的身份份IDi，挑战者C把对应的部分密钥返回给A。
私有秘密查询：输入用户的身份IDi，挑战者C把对应的私有秘密返回给A。
公钥查询：输入用户的身份IDi，挑战者C把对应的公钥返回给A。
公钥替换查询：输入用户的身份IDi和一个新公钥，挑战者C利用新公钥替换用户原来的公钥。
签名发布查询：输入消息m、签名者身份，挑战者C生成签名σ，并把σ返回给A。
在攻击者$A\in \text{ }\!\!\{\!\!\text{ }A1,A2\text{ }\!\!\}\!\!\text{ }$的攻击下，签名机制的不可伪造性定义如下：
1) 挑战者C执行系统参数建立算法，生成系统参数和主私钥。C把系统参数返回给攻击者A，如果A是类型II攻击者，C把主私钥也返回给A。
2) 查询阶段，A执行Hash查询、部分密钥查询、私钥查询、公钥查询、用户公钥替换查询、部分盲签名查询和解密验证查询。如果A是类型II攻击者，则A能进行用户公钥替换查询。
3)A在用户身份IDi*下输入σ*签名。
称A赢得此游戏，当且仅当以下条件成立。
1) σ*是一个合法的签名。
2) 如果A是类型I攻击者，则A不能对IDi*进行过部分密钥查询和私钥查询; 如果A是类型II攻击者，则A不能对IDi*进行过私钥查询。
定义 2 无证书部分盲签名机制的不可伪造性
如果不存在攻击者A能够在概率多项式时间内以不可忽略的优势赢得上述游戏，则称无证书部分盲签名机制在适应性选择消息攻击下具有不可伪造性。
-
文献[16]中的无证书盲签名机制分为以下4个步骤：
1) 系统建立算法
输入安全参数k，KGC产生两大素数p和q和定义在有限域Fp上上的椭圆曲线E(Fp)。设G是由E(Fp)上的点组成的阶为q的加法群。 KGC选择G的一个基点P和3个安全Hash函数： ${{H}_{1}}:{{\{0,1\}}^{*}}\times G\to Z_{q}^{*}$，${{H}_{2}}:{{\{0,1\}}^{*}}\times {{\{0,1\}}^{*}}\times G\to Z_{q}^{*},{{H}_{3}}:{{\{0,1\}}^{*}}\to Z_{q}^{*}$。KGC随机选择主密钥$s\in Z_{q}^{*}$，计算${{P}_{\text{pub}}}=sP$，公开系统参数$\left( p,q,E({{F}_{p}}),G,P,{{P}_{\text{pub}}},{{H}_{1}},{{H}_{2}},{{H}_{3}} \right)$，保密主密钥s。
2) 密钥产生算法
签名者i把他的身份提交给KGC。收到后KGC生成随机数${{y}_{i}}\in Z_{q}^{*}$，计算${{Y}_{i}}={{y}_{i}}P$、${{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}})$和${{d}_{i}}={{y}_{i}}+s{{q}_{i}}$，并把部分私钥${{d}_{i}}$和部分公钥${{Y}_{i}}$返回给i。收到${{d}_{i}}$和${{Y}_{i}}$后，i生成随机数${{x}_{i}}\in Z_{q}^{*}$作为他的私有秘密，计算${{X}_{i}}={{x}_{i}}P$，输出私钥${{S}_{i}}=({{x}_{i}},{{d}_{i}})$和公钥${{P}_{i}}=({{X}_{i}},{{Y}_{i}})$。
3) 签名发布算法
在该算法中，用户和签名者通过执行交互协议来生成消息m的部分盲签名，其中c是双方共同协商的说明消息。用户和签名者之间的交互协议如下所述。
签名(阶段1)：签名者i生成随机数，计算R=rP并把R发送给用户。
盲化：用户生成两个随机数$\alpha ,\beta \in Z_{q}^{*}$，计算$z={{H}_{3}}(c)$、$L=\alpha R+\alpha \beta zP$、$h={{H}_{2}}(m,c,L)$和$u={{\alpha }^{-1}}h+\beta z$，最后把u发送给签名者i。
签名(阶段2)：签名者i计算$z={{H}_{3}}(c)$、$v=(r+u)/({{x}_{i}}+{{d}_{i}}+z)$，并把v发送给用户。
去盲：用户计算w=av，输出对消息(m,c)的部分盲签名(L,w)。
4) 签名验证算法
收到对消息(m,c)的部分盲签名(L,w)后，验证者计算${{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}})$和$h={{H}_{2}}(m,c,L)$，并验证等式$L+hP=w({{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}}+zP)$是否成立。如果等式成立，验证者接受签名，否则拒绝签名。
-
文献[16]在随机预言模型下证明所提出的机制是安全的。 本文将通过具体的攻击来证明他们的机制不能满足类型Ⅰ攻击者攻击下的不可伪造性。 设i为签名者，则他的私钥和公钥分别为${{S}_{i}}=({{x}_{i}},{{d}_{i}})$和${{P}_{i}}=({{X}_{i}},{{Y}_{i}})$，其中，${{Y}_{i}}={{y}_{i}}P,{{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}}),{{d}_{i}}={{y}_{i}}+s{{q}_{i}},{{X}_{i}}={{x}_{i}}P$。
设A1是类型Ⅰ的攻击者，则A1不知道系统主密钥，但可以随时查询用户公钥或替换合法用户的公钥。A1可以通过以下4个步骤伪造签名者i的签名：
1) A1生成随机数${{t}_{i}}\in Z_{q}^{*}$，计算$z={{H}_{3}}(c)$和${{{X}'}_{i}}={{t}_{i}}P-({{Y}_{i}}+{{q}_{i}}{{P}_{pub}}+zP)$。
2) A1利用${{P}_{i}}^{\prime }=({{{X}'}_{i}},{{Y}_{i}})$替换签名者i的公钥${{P}_{i}}=({{X}_{i}},{{Y}_{i}})$。
3) A1生成随机数${{l}_{i}}\in Z_{q}^{*}$，计算$L={{l}_{i}}P$、 $h={{H}_{2}}(m,c,L)$和$w=({{l}_{i}}+h)t_{i}^{-1}$。
4) A1输出(L,w)作为对消息(m,c)的部分盲签名。
因为，$L={{l}_{i}}P,w=({{l}_{i}}+h)t_{i}^{-1}$，可以得到：
$$\begin{matrix} w({{{{X}'}}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}}+zP)= \\ ({{l}_{i}}+h)t_{i}^{-1}({{t}_{i}}P-({{Y}_{i}}+{{q}_{i}}{{P}_{pub}}+zP)+ \\ {{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}}+zP)=({{l}_{i}}+h)t_{i}^{-1}{{t}_{i}}P= \\ ({{l}_{i}}+h)P=L+hP \\ \end{matrix}$$ (1) 因此有$w({{{X}'}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}}+zP)$和$L+hP$相等，于是A1伪造的签名(L,w)可以通过验证者的验证。 因此A1成功地伪造了一个合法签名。综上所述，文献[16]中的部分盲签名机制不能满足类型Ⅰ攻击者攻击下的不可伪造性。
-
新的无证书部分盲签名机制分为以下4个步骤：
1) 系统建立算法
输入安全参数k，KGC产生两大素数p 和q 和定义在有限域Fp上的椭圆曲线E(Fp)。设G是由E(Fp)上的点组成的阶为q的加法群。 KGC选择G的一个基点P和3个安全Hash函数： ${{H}_{1}}:{{\{0,1\}}^{*}}\times G\to Z_{q}^{*},{{H}_{2}}:{{\{0,1\}}^{*}}\times {{\{0,1\}}^{*}}\times G\to Z_{q}^{*},{{H}_{3}}:{{\{0,1\}}^{*}}\times {{\{0,1\}}^{*}}\times G\times G\times G\to Z_{q}^{*}$。KGC 随机选择主密钥$s\in Z_{q}^{*}$，计算${{P}_{\text{pub}}}=sP$，公开系统参数($p,q,E({{F}_{p}}),G,P,{{P}_{pub}},{{H}_{1}},{{H}_{2}},{{H}_{3}}$)，保密主密钥s。
2) 密钥产生算法
签名者i把他的身份IDi提交给KGC。收到IDi后，KGC生成随机数${{y}_{i}}\in Z_{q}^{*}$，计算${{Y}_{i}}={{y}_{i}}P$、${{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}})$和${{d}_{i}}={{y}_{i}}+s{{q}_{i}}$，并把部分私钥${{d}_{i}}$和部分公钥${{Y}_{i}}$返回给i。收到${{d}_{i}}$和${{Y}_{i}}$后，i生成随机数${{x}_{i}}\in Z_{q}^{*}$作为他的私有秘密，计算${{X}_{i}}={{x}_{i}}P$，输出私钥${{S}_{i}}=({{x}_{i}},{{d}_{i}})$和公钥${{P}_{i}}=({{X}_{i}},{{Y}_{i}})$。
3) 签名发布算法
在该算法中，用户和签名者通过执行交互协议来生成消息m的部分盲签名，其中c是双方共同协商的说明消息。用户和签名者之间的交互协议如下所述。
签名(阶段1)：签名者i生成随机数$r\in Z_{q}^{*}$，计算$R=rP$并把R发送给用户。
盲化：用户生成两个随机数$\alpha ,\beta \in Z_{q}^{*}$，计算$L=\alpha P+\beta R,h={{H}_{2}}(m,c,L)$和$u=h{{\beta }^{-1}}$，最后把u发送给签名者i。
签名(阶段2)：签名者计算${{k}_{i}}={{H}_{3}}(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}})$、$v=r-u({{k}_{i}}{{x}_{i}}+{{d}_{i}})$，并把v发送给用户。
去盲：用户计算$w=\beta v+\alpha $，输出对消息(m,c)的部分盲签名(h,w)。
4) 签名验证算法
收到对消息(m,c)的部分盲签名(h,w)后，验证者计算${{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}})$、${{k}_{i}}={{H}_{3}}(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}})$和$T=h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+wP$，并验证等式$h={{H}_{2}}(m,c,T)$是否成立。若成立则验证者接受签名，否则拒绝签名。
因为$L=\alpha P+\beta R,h={{H}_{2}}(m,c,L),u=h{{\beta }^{-1}},v=r-u({{k}_{i}}{{x}_{i}}+{{d}_{i}}),w=\beta v+\alpha $，因此可以得到：
$$\begin{matrix} T=h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+wP= \\ h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+(\beta v+\alpha )P= \\ h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})=h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+\beta R- \\ h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+\alpha P=\beta R+\alpha P=L \\ \end{matrix}$$ (2) $$h={{H}_{2}}(m,c,Q)={{H}_{2}}(m,c,T)$$ (3) 因此，本文的签名机制是正确的。
-
定理 1 本文提出的部分盲签名机制满足部分盲性。
证明：在本文的机制中使用了两个盲化因子$\alpha ,\beta \in Z_{q}^{*}$，并且这两个盲化因子是随机生成的。另外用户只把盲化后的消息u发给了签名者。因为H2是一个安全的哈希函数，因此签名者不能从哈希值$h={{H}_{2}}(m,c,L)$中恢复消息m。如果签名(h,w)是一个有效的签名，由$u=h{{\beta }^{-1}},w=\beta v+\alpha ,L=\alpha P+\beta R$可以得出存在唯一的$\beta =h{{u}^{-1}}$和唯一的$\alpha =w-h{{u}^{-1}}v$使得式(2)和式(3)成立。因此，盲化因子$\alpha ,\beta \in Z_{q}^{*}$在部分盲签名的生成中总是存在的。在定义1涉及的游戏中，由于盲化因子$\alpha $和$\beta $的存在，攻击者赢得游戏的优势是可以忽略的。因此本文提出的部分盲签名机制满足部分盲性。
定理 2 在适应性选择消息攻击下，改进的无证书部分盲签名机制具有不可伪造性。
上述定理可以由以下两个引理推出。
引理 1 在随机预言模型下，如果存在第Ⅰ类攻击者A1能够以不可忽略的概率$\varepsilon $伪造出合法的部分盲签名，则存在挑战者C能够以不可忽略的概率解决DL问题。
证明：给定DL问题实例(P,Q)，C的目的是利用A1计算出$a\in Z_{q}^{*}$使得Q = aP。首先，C产生系统参数$(p,q,E({{F}_{p}}),G,P,{{P}_{\text{pub}}},{{H}_{1}},{{H}_{2}},{{H}_{3}})$，并把它返回给A1，其中${{P}_{\text{pub}}}=Q$。随后，C随机选择IDI作为挑战身份，其中$1\le I\le {{q}_{{{H}_{1}}}}$。${{q}_{{{H}_{1}}}}$是A1进行H1查询的次数。C按照如下方式回答A1的查询。
H1查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{h}_{i}})$的列表L1。 收到A1对消息$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{h}_{i}})$的查询后，C首次查询$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{h}_{i}})$是否在L1中。如果在L1中，C把hi返回给A1。否则，C生成随机数${{h}_{i}}\in Z_{q}^{*}$，把$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{h}_{i}})$插入到L1中并返回hi。
H2查询：C维护格式为(m,c,L,h)的列表L2。收到A1对消息(m,c,L,h)的查询后，C首次查询在L2中是否存在(m,c,L,h)。若存在，C把h返回给A1。否则，C生成随机数$h\in Z_{q}^{*}$，把(m,c,L,h)插入到L2中并返回h。
H3查询：C维护格式为$(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}},h)$的列表L3。收到A1对消息$(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}})$的查询后，C首次查询在L3中$(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}},h)$是否存在。若存在，C把h返回给A1。否则，C生成随机数$h\in Z_{q}^{*}$，把$(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}},h)$插入到L3中并返回h。
部分密钥查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$的列表${{L}_{\text{par}}}$。如果$\text{I}{{\text{D}}_{i}}=\text{I}{{\text{D}}_{I}}$，则C退出仿真(事件E1)，否则C查询$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$是否在${{L}_{\text{par}}}$中。若存在，C把di返回给A1。否则C生成两个随机数${{d}_{i}},{{q}_{i}}\in Z_{q}^{*}$，计算${{Y}_{i}}={{d}_{i}}P-{{q}_{i}}Q$，把$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$和$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{q}_{i}})$分别加入到${{L}_{\text{par}}}$和L1中。最后，C返回di和Yi。
私有秘密查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$的列表${{L}_{\text{pri}}}$。C查询$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$是否在${{L}_{\text{pri}}}$中。若存在，C把xi返回给A1。否则，C进行部分密钥提取查询得到di，生成随机数${{x}_{i}}\in Z_{q}^{*}$，把 $(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$加入到${{L}_{\text{pri}}}$中并返回xi。
公钥查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$的列表${{L}_{\text{pub}}}$。收到A1对用户身份$\text{I}{{\text{D}}_{i}}$的查询后，C首次查询$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$是否在${{L}_{\text{pub}}}$中。若存在，C把$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$返回给A1。否则C查询${{L}_{\text{par}}}$和${{L}_{\text{pri}}}$，计算${{X}_{i}}={{x}_{i}}P$，并返回$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$。若${{L}_{\text{par}}}$和${{L}_{\text{pri}}}$中不存在相应的记录，且$\text{I}{{\text{D}}_{i}}\ne \text{I}{{\text{D}}_{I}}$，C生成3个随机数${{d}_{i}},{{h}_{i}},{{x}_{i}}\in Z_{q}^{*}$，计算${{X}_{i}}={{x}_{i}}P,{{Y}_{i}}={{d}_{i}}P-{{h}_{i}}Q$，把$\text{(I}{{\text{D}}_{i}},\bot ,{{x}_{i}})$、$(\text{I}{{\text{D}}_{i}},\bot ,{{Y}_{i}})$、$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$和$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{h}_{i}})$分别加入到${{L}_{\text{pri}}}$、${{L}_{\text{par}}}$、${{L}_{\text{pub}}}$和L1中，并返回$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$。
公钥替换查询：收到A1对消息$(\text{I}{{\text{D}}_{i}},{{{X}'}_{i}}={{{x}'}_{i}}P,{{{Y}'}_{i}}={{{y}'}_{i}}P)$的查询后，C首先查询$({{X}_{i}},{{Y}_{i}})$是否在${{L}_{\text{pub}}}$中。若不存在，C首先执行公钥提取查询。最后，C利用${{{X}'}_{i}}$和${{{Y}'}_{i}}$分别替换${{X}_{i}}$和${{Y}_{i}}$。
签名发布查询：收到A1对消息$(\text{I}{{\text{D}}_{i}},c,m)$的查询后，C产生随机数$h,w\in Z_{q}^{*}$，计算${{q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}},{{Y}_{i}})$、${{k}_{i}}={{H}_{3}}(c,\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}},{{P}_{\text{pub}}})$和$T=h({{k}_{i}}{{X}_{i}}+{{Y}_{i}}+{{q}_{i}}{{P}_{\text{pub}}})+wP$。C把$(m,c,T,h)$添加到L2中并输出$(h,w)$。
经过有界次查询后，A1以不可忽略的概率$\varepsilon $输出一个对消息$(\text{I}{{\text{D}}^{*}},c,m)$的签名$(\text{I}{{\text{D}}^{*}},c,m)$。如果${{\operatorname{ID}}^{*}}\ne \text{I}{{\text{D}}_{I}}$，则C停止仿真(事件E2)；否则同时改变H1、H2和H3，由分叉引理可知A1可以在多项式概率事件内生成另外3个有效的签名$({{h}_{2}},{{w}_{2}})$、$({{h}_{3}},{{w}_{3}})$和$({{h}_{4}},{{w}_{4}})$。则可以得到：
$$T={{h}_{j}}(k_{I}^{j}{{X}_{I}}+{{Y}_{I}}+q_{I}^{j}{{P}_{\text{pub}}})+{{w}_{j}}Pj=1,2,3,4$$ (4) 设$T=tP,{{X}_{I}}={{x}_{I}}P,{{Y}_{I}}={{y}_{I}}P$，则由上述等式可以得到：
$$t={{h}_{j}}(k_{I}^{j}{{x}_{I}}+{{y}_{I}}+q_{I}^{j}a)+{{w}_{j}}\bmod q$$ (5) 上述方程中有4个未知数，且相互线性独立，因此联立4个方程即可得到a的值，即C可以解决DL问题。
下面对C成功的概率进行分析。从上述模拟过程可以看出，只要E1和E2没有发生，则C即可解决DL问题。令${{q}_{\text{ppk}}}$表示A1进行部分私钥查询的次数。从上述模拟过程可知$\Pr [\overline{{{E}_{1}}}]\ge {{(1-\frac{1}{{{q}_{{{H}_{1}}}}})}^{{{q}_{\text{ppk}}}}}$，$\Pr [A1成功|\overline{{{E}_{1}}}]\ge \varepsilon $，$\Pr [\overline{{{E}_{\text{2}}}}\text{ }\!\!|\!\!\text{ }A1成功\wedge \overline{{{E}_{1}}}]\ge \frac{1}{{{q}_{{{H}_{1}}}}}$。因此可以得到C成功的概率为：
$$\begin{matrix} {\varepsilon }'=\Pr [\overline{{{E}_{1}}}\wedge A1成功\wedge \overline{{{E}_{2}}}]= \\ \Pr [\overline{{{E}_{1}}}]\Pr [A1成功|\overline{{{E}_{1}}}]\Pr [\overline{{{E}_{2}}}|A1成功\wedge \overline{{{E}_{1}}}]\ge \\ \frac{1}{{{q}_{{{H}_{1}}}}}{{(1-\frac{1}{{{q}_{{{H}_{1}}}}})}^{{{q}_{\text{ppk}}}}}\varepsilon \\ \end{matrix}$$ 引理 2 在随机预言模型下，如果存在第Ⅰ类攻击者A2能够以不可忽略的概率$\varepsilon $伪造出合法的部分盲签名，则存在挑战者C能够以不可忽略的概率解决DL问题。
证明：给定DL问题实例$(P,Q)$，C的目的是利用A2是计算出$a\in Z_{q}^{*}$使得$Q=aP$。首先C生成随机数$s\in Z_{q}^{*}$，产生系统参数$(p,q,E({{F}_{p}}),G,P,{{P}_{\text{pub}}}=sP,{{H}_{1}},{{H}_{2}},{{H}_{3}})$，并把主密钥s和系统参数返回给A2。随后，C随机选择$\text{I}{{\text{D}}_{I}}$作为挑战身份，其中$1\le I\le {{q}_{{{H}_{1}}}},{{q}_{{{H}_{1}}}}$是A2进行H1询的次数。C按照引理1中的方式对H1查询、H2查询、H3查询和签名发布查询进行回答。对于其它查询的回答如下所示。
部分密钥查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$的列表${{L}_{\text{par}}}$。C查询$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$是否在${{L}_{\text{par}}}$中。若存在，C把${{d}_{i}}$返回给A2。否则C生成两个随机数${{y}_{i}},{{q}_{i}}\in Z_{q}^{*}$，计算${{Y}_{i}}={{y}_{i}}P,{{d}_{i}}={{y}_{i}}+s{{q}_{i}}$，把$({{\operatorname{ID}}_{i}},{{d}_{i}},{{Y}_{i}})$和$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{q}_{i}})$分别加入到${{L}_{\text{par}}}$和L1中。最后，C返回${{d}_{i}}$和${{Y}_{i}}$。
私有秘密查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$的列表${{L}_{\text{pri}}}$。如果$\text{I}{{\text{D}}_{i}}=\text{I}{{\text{D}}_{I}}$，则C退出仿真(事件E2)，否则C查询$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$是否在${{L}_{\text{pri}}}$中。若存在，C把${{x}_{i}}$返回给A2。否则C进行部分密钥提取查询得到${{d}_{i}}$，生成随机数${{x}_{i}}\in Z_{q}^{*}$，把$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$加入到${{L}_{\text{pri}}}$中并返回${{x}_{i}}$。
公钥查询：C维护格式为$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$的列表${{L}_{\text{pub}}}$。收到A2对用户身份$\text{I}{{\text{D}}_{i}}$的查询后，C首次查询$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$是否在${{L}_{\text{pub}}}$中。若存在，C把$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$返回给A2。否则C查询 ${{L}_{\text{par}}}$和${{L}_{\text{pri}}}$，计算${{X}_{i}}={{x}_{i}}P$，并返回$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$。若${{L}_{\text{par}}}$和${{L}_{\text{pri}}}$中不存在相应的记录，且$\text{I}{{\text{D}}_{i}}\ne \text{I}{{\text{D}}_{I}}$，C生成3个随机数${{q}_{i}},{{x}_{i}},{{y}_{i}}\in Z_{q}^{*}$，计算${{X}_{i}}={{x}_{i}}P,{{Y}_{i}}={{y}_{i}}P,{{d}_{i}}={{y}_{i}}+s{{q}_{i}}$，把$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{x}_{i}})$、$(\text{I}{{\text{d}}_{i}},{{X}_{i}},{{Y}_{i}})$、$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$和$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{q}_{i}})$分别加入到${{L}_{\text{pri}}}$、${{L}_{\text{par}}}$、${{L}_{\text{pub}}}$和L1中，并返回$\text{P}{{\text{K}}_{i}}=({{X}_{i}},{{Y}_{i}})$；否则$\text{I}{{\text{D}}_{i}}\ne \text{I}{{\text{D}}_{I}}$，C生成两个随机数${{q}_{i}},{{y}_{i}}\in Z_{q}^{*}$，计算${{X}_{i}}=Q,{{Y}_{i}}={{y}_{i}}P,{{d}_{i}}={{y}_{i}}+s{{q}_{i}}$，把$(\text{I}{{\text{D}}_{i}},{{d}_{i}},\bot )$、$(\text{I}{{\text{D}}_{i}},{{d}_{i}},{{Y}_{i}})$、$(\text{I}{{\text{D}}_{i}},{{X}_{i}},{{Y}_{i}})$和$(\text{I}{{\text{D}}_{i}},{{Y}_{i}},{{q}_{i}})$分别加入到${{L}_{\text{pri}}}$、${{L}_{\text{par}}}$、${{L}_{\text{pub}}}$和L1中，并返回${{\operatorname{PK}}_{i}}=({{X}_{i}},{{Y}_{i}})$。
经过有界次查询后，A2以不可忽略的概率$\varepsilon $输出一个对消息$(\text{I}{{\text{D}}^{*}},c,m)$的签名$({{h}_{1}},{{w}_{1}})$。如果$\text{I}{{\text{D}}^{*}}\ne \text{I}{{\text{D}}_{I}}$，则C停止仿真(事件E2)；否则同时改变H1、H2和H3，由分叉引理可知A2可以在多项式概率事件内生成另外一个有效的签名$({{h}_{2}},{{w}_{2}})$。则可以得到：
$$\begin{align} & T={{h}_{j}}({{k}_{I}}{{X}_{I}}+{{Y}_{I}}+{{q}_{I}}{{P}_{\text{pub}}})+{{w}_{j}}P \\ & j=1,2 \\ \end{align}$$ (6) 设$T=tP$，则由式(16)可以得到：
$$t={{h}_{j}}(k_{I}^{j}a+{{y}_{I}}+q_{I}^{j}s)+{{w}_{j}}\bmod q$$ (7) 上述方程中有两个未知数t和a，且相互线性独立，因此联立两个方程即可得到a的值，即C可以解决DL问题。
下面对C成功的概率进行分析。从上述模拟过程可以看出，只要E1和E2没有发生，则C即可解决DL问题。令${{q}_{\text{sv}}}$表示A2进行私有秘密查询的次数。从上述模拟过程可知$\Pr [\overline{{{E}_{1}}}]\ge {{(1-\frac{1}{{{q}_{{{H}_{1}}}}})}^{{{q}_{\text{sv}}}}}$，$\Pr [A2成功|\overline{{{E}_{1}}}]\ge \varepsilon ,\Pr [\overline{{{E}_{\text{2}}}}\text{ }\!\!|\!\!\text{ }A2成功\wedge \overline{{{E}_{1}}}]\ge \frac{1}{{{q}_{{{H}_{1}}}}}$。因此可以得到C成功的概率为：
-
本节把新的无证书部分盲签名机制同文献[16]中的部分盲签名机制进行比较。这里Ts、Ta和Th分别表示椭圆曲线点乘、椭圆曲线点加和哈希函数的计算开销。文献[18]在Intel I7-4770协处理器上实现了椭圆曲线密码所需要的各种运算，其中操作系统是Windows 7，时钟频率为3.40 GHz，内存为4 GB。根据实现结果可知：Ts=0.442 ms，Ta=0.0018 ms，Th=0.0001 ms。
表 1 比较了本文的机制和文献[16]中机制的性能。可看出：执行一次本文的机制的签名算法和文献[16]的机制的签名算法都需要1.328 1 ms；执行一次本文的机制的验证算法需要1.773 6ms；执行一次本文的机制的验证算法需要1.775 5 ms，与文献[16]的机制相比，本文提出的机制具有更好的性能。另外文献[16]的机制不能抵抗第Ⅰ类攻击者的攻击。因此，本文的机制更适合应用的需要。
表 1 性能比较
签名/ms 验证/ms 文献[16] 3Ts+Ta+3Th≈1.3281 4Ts+4Ta+3Th≈1.7755 本文算法 3Ts+Ta+3Th≈1.3281 4Ts+3Ta+2Th≈1.7736
Certificateless Partially-Blind Signature Scheme with Provable Security
-
摘要: 针对现有无证书部分盲签名机制计算复杂度过高的问题，该文设计了一种高效的无证书部分盲签名机制。首先，分析了一个无证书部分盲签名机制的安全性；其次，利用椭圆曲线密码构造一种新的无证书部分盲签名机制；最后，在随机预言模型下证明提出的无证书部分盲签名机制是安全的。分析表明，提出的无证书部分盲签名机制不仅能解决以往机制中存在的安全性缺陷，而且具有更好的性能。Abstract: The high computation costs are required in existing certificateless partially-blind signature (CLPBS) schemes. In this paper, we first analyze the security of Shao et al.'s CLPBS scheme and then present a new CLPBS scheme based on the elliptic curve cryptography (ECC). The security analysis indicates that the proposed CLPBS scheme is provably secure in the random oracle model. Detailed analysis shows that the proposed CLPBS scheme not only addresses security weaknesses with previous schemes, but also has better performance.
-
Key words:
- bilinear pairing /
- certificateless /
- partially-blind signatures /
- random oracle model
-
[1] CHAUM D. Bind signature for untraceable payments[C]//Advances in Cryptology-Crypto'82.NewYork:Springer-Verlag, 1982:199-203. [2] ABE M, FUJISAKI E. How to date blind signatures[C]//Advances in Cryptology-Asiacrypt'96. Kyongju:Springer-Verlag, 1996:244-251. [3] SHAMIR A. Identity-based cryptosystem and signature scheme[C]//Advances in Cryptology-Crypto'84. Santa Barbara:Springer-Verlag, 1984:47-53. [4] RIYAMI A S, PATERSON K. Certificateless public key cryptography[C]//Advances in Cryptology-Asiacrypt'03. Taiwan, China:Springer-Verlag, 2003:452-473. [5] HE D, CHEN Y, CHEN J. A new two-round certificateless authenticated key agreement protocol without bilinear pairings[J]. Mathematical and Computer Modelling, 2011, 54(11):3143-3152. http://cn.bing.com/academic/profile?id=1999736026&encoded=0&v=paper_preview&mkt=zh-cn [6] HE D, SAHADEO P, CHEN J. An efficient certificateless two-party authenticated key agreement protocol[J]. Computers & Mathematics with Applications, 2012, 64(6):1914-1926. http://cn.bing.com/academic/profile?id=2074007885&encoded=0&v=paper_preview&mkt=zh-cn [7] SUN H, WEN Q, ZHANG H, et al. A novel pairing-free certificateless authenticated key agreement protocol with provable security[J]. Frontiers of Computer Science, 2013, 7(4):544-557. doi: 10.1007/s11704-013-2305-1 [8] DARIO C. Fully non-interactive onion routing with forward secrecy[J]. International Journal of Information Security, 2013, 12(1):33-47. doi: 10.1007/s10207-012-0185-2 [9] ZHANG G. Fuzzy certificateless identity-based encryption protocol from lattice[J]. Applied Mechanics and Materials, 2013, 380(2):2262-2266. http://cn.bing.com/academic/profile?id=2073623499&encoded=0&v=paper_preview&mkt=zh-cn [10] ZHANG L, ZHANG F. Certificateless partially blind signatures[C]//1st International Conference on Information Science and Engineering (ICISE). Nanjing:IEEE, 2009:2883-2886. [11] ZHANG L, ZHANG F, QIN B, et al. Provably-secure electronic cash based on certificateless partially-blind signatures[J]. Electronic Commerce Research and Applications, 2011, 10(5):545-552. doi: 10.1016/j.elerap.2011.01.004 [12] LIU J, ZHANG Z, SUN R, et al. Certificateless partially blind signature[C]//26th International Conference on Advanced Information Networking and Applications Workshops (WAINA). Fukuoka:IEEE, 2012:128-133. [13] LI F, ZHANG M, TAKAGI T. Identity-based partially blind signature in the standard model for electronic cash[J]. Mathematical and Computer Modelling, 2013, 58(1-2):196-203. doi: 10.1016/j.mcm.2012.07.009 [14] CHEN L, CHENG Z, SMART N P. Identity-based key agreement protocols from pairings[J]. Internal Journal of Information Security, 2007, 6(4):213-241. doi: 10.1007/s10207-006-0011-9 [15] HE H, CHEN J, HU J. An ID-based proxy signature schemes without bilinear pairings[J]. Annals of Telecommunications, 2011, 66(11-12):657-662. doi: 10.1007/s12243-011-0244-0 [16] 邵国金, 薛冰, 陈明. 基于椭圆曲线DLP问题的无证书部分盲签名机制[J]. 四川大学学报:工程科学版, 2012, 44(1):112-117. http://www.cnki.com.cn/Article/CJFDTOTAL-SCLH201201019.htm SHAO Guo-jin, XUE Bing, CHEN Ming. Certificateless partially blind signature scheme based on the elliptic curve discrete logarithm problem[J]. Journal of Sichuan University:Engineering Science Edition, 2012, 44(1):112-117. http://www.cnki.com.cn/Article/CJFDTOTAL-SCLH201201019.htm [17] POINTCHEVAL D, STERN J. Security arguments for digital signatures and blind signatures[J]. Journal of Cryptology, 2000, 13(3):361-396. doi: 10.1007/s001450010003 [18] HE D, ZEADALLY S, XU B, et al. An efficient identity-based conditional privacy-preserving authentication scheme for vehicular ad-hoc networks[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(12):2681-2691. doi: 10.1109/TIFS.2015.2473820 -
