0 概述

1983年, CHAUM D用盲签名方案来构建电子现金系统^[1], 在这种机制中, 签名者并不知道他所签发文件的具体内容, 也无法将签名过程和最终的签名相对应。盲签名作为一种特殊的数字签名, 其因具有盲性的特点, 可保障签署信息的匿名性, 被广泛应用于电子现金、电子投票、电子票据保护等方面^[2-3]。随着微电子技术和无线网络的发展, 上述应用场景中会配置许多超低功耗的微型无线设备, 由于此类设备普遍存在计算能力弱、传输能力受限和传输不稳定等缺点, 因此适合使用短签名方案。自从短签名方案^[4]被提出以来, 目前多数相关研究与分析^[5-7]都是围绕文献[4]基础方案展开, 或根据具体应用场景在其基础上构造特定方案^[8-9]。此外, 文献[10]提出一种可恢复消息的盲签名方案, 其中原消息无需随签名发送, 可有效缩短签名长度。

相对于普通盲签名方案, 短盲签名的构造比较困难, 难点在于为保证签名的长度较短不能增加额外的辅助验证信息。本文针对使用低功耗无线设备进行数据签名和交互传输的移动环境, 通过简化盲化和签名过程, 提出一种可证安全的短盲签名方案。

1 基础知识

定义1  双线性对

在双线性映射中, 令k为一个安全参数, q为一个k bit素数, G₁是由P生成的阶为素数q的循环加法群, Q∈G₁, G₂是有相同阶q的循环乘法群, 则双线性映射e:G₁×G₁→G₂满足以下性质:

1) 双线性性:对于任意a, b∈ $ \mathbb{Z} $_q^*, 有e(aP, bQ)=e(P, Q)^ab。

2) 非退化性:e(P, Q)≠1。

3) 易计算性:存在有效算法计算e(P, Q)。

定义2  计算性Diffie-Hellman(Computational Diffie-Hellman, CDH)问题

已知G₁为由g生成的q阶循环加法群, 未知随机数a, b∈ $ \mathbb{Z} $_q^*, 给定ag∈G₁和bg∈G₁, 求解abg是困难的。

定义3  安全模型

如果不存在概率多项式时间算法(敌手A)以一个不可忽略的优势在图 1所示的游戏中获胜, 则称盲签名在适应性选择消息和身份攻击下是存在性不可伪造的。

2 短盲签名方案的构造

本文提出的短盲签名方案具体描述如下:

1) 系统参数建立。给定安全参数k, 选择2个阶都为素数的群G₁和G₂(其中G₁的生成元为g)、双线性映射e:G₁×G₁→G₂, 以及安全的抗碰撞哈希函数H:{0, 1}^*→G₁, 公布系统参数{k, G₁, G₂, g, H}。

2) 用户私钥生成。系统密钥管理中心为每个用户秘密选择随机数x∈ $ \mathbb{Z} $_q^*作为私钥, 计算y=xg作为公钥, 将x通过安全渠道发送给用户, 公开用户公钥y。以下假设签名者为A, 用户身份为ID_A, 密钥对为(x_A, y_A), 签名消息持有者为B。A给由B提供的消息m进行签名。

3) 消息盲化。B计算h=H(ID_A, y_A, m), 随机选择2个秘密值u, v∈ $ \mathbb{Z} $_q^*, 计算V=vg, λ=uh+V, 将λ发送给A。

4) 签名。A计算S₁=x_Aλ, 将S₁发送给B。

5) 脱盲。B计算S₂=S₁－vy_A, S=u^－1S₂, 则S为最终A对消息m的签名。

6) 验证。任何第三方对消息签名对(m, S), 计算h=H(ID_A, y_A, m), 验证等式e(S, g)=e(h, y_A), 等式成立则接受签名, 否则拒绝签名。正确性验证过程如下:

$ \begin{aligned} e(S, g)=& e\left(u^{-1} S_{2}, g\right)=e\left(u^{-1}\left(S_{1}-v y_{\mathrm{A}}\right), g\right)=\\ & e\left(u^{-1}\left(x_{\mathrm{A}} \lambda-v y_{\mathrm{A}}\right), g\right)=\\ & e\left(u^{-1}\left(x_{\mathrm{A}}(u h+V)-v y_{\mathrm{A}}\right), g\right)=\\ & e\left(u^{-1}\left(x_{\mathrm{A}}(u h+V)-v x_{\mathrm{A}}\right) g, g\right)=\\ & e\left(u^{-1}\left(x_{\mathrm{A}} u h\right) g\right)=e\left(x_{\mathrm{A}} h, g\right)=e\left(h, x_{\mathrm{A}} g\right)=e\left(h, y_{\mathrm{A}}\right) \end{aligned} $

3 安全性证明 3.1 盲性证明

定理1  本文方案满足盲性^[1]。

证明  对于任意给定的有效签名(m, S)和签名阶段中产生的中间值(λ, V, h, S₁, S₂), 总存在唯一的一对盲化因子u, v∈ $ \mathbb{Z} $_q^*。

给定签名(m, S)和中间值(λ, V, h, S₁, S₂), u、v满足:

$ {\lambda = uh + V} $

(1)

$ {S = {u^{ - 1}}{S_2}, {S_2} = {S_1} - v{y_{\rm{A}}}, {S_1} = {x_{\rm{A}}}\lambda } $

(2)

$ {V = vg} $

(3)

由式(3)可知v=log_gV∈ $ \mathbb{Z} $_q^*是唯一存在的, 再由式(1)可知u=log_h(λ－V)∈$ \mathbb{Z} $_q^*也是唯一存在的。

以下证明u、v满足式(2)中所有等式。由双线性对的不可退化性可知S₂=S₁－vy_A⇔e(S₂, y_A)=e(S₁－vy_A, y_A), 因此, 只需证明u、v满足等式e(S₂, y_A)=e(S₁－vy_A, y_A)。

因为(m, S)是有效签名, 所以有:

$ e(S, g) = e\left( {h, {y_{\rm{A}}}} \right) = e\left( {{u^{ - 1}}{S_2}, g} \right) $

(4)

$ e\left( {{x_{\rm{A}}}\mu h, g} \right) = e\left( {{S_2}, g} \right) $

(5)

$ \begin{array}{l} e\left( {{S_1} - v{y_{\rm{A}}}, {y_{\rm{A}}}} \right) =& e\left( {{x_{\rm{A}}}\lambda - v{x_{\rm{A}}}g, {y_{\rm{A}}}} \right) = \\ &e\left( {{x_{\rm{A}}}(\mu h + vg) - v{x_{\rm{A}}}g, {y_{\rm{A}}}} \right){\rm{ = }}\\ &e\left( {{x_{\rm{A}}}uh, {y_{\rm{A}}}} \right) = e\left( {{S_2}, {y_{\rm{A}}}} \right) \end{array} $

(6)

通过攻击者Alice和用户Bob间的挑战游戏证明消息的不可区分性。游戏过程如下:

S0:运行系统参数建立和密钥生成算法, 发送相应参数给攻击者Alice和用户Bob, Alice掌握签名私钥。

S1:Alice随机选择等长的消息m₀和m₁发给Bob。

S2:Bob随机选择一个比特值c∈{0, 1}, 运行盲化算法生成盲化消息h_c=H(ID_A, y_A, m_c)和h_1－c=H(ID_A, y_A, m_1－c), 随机选择2组秘密值u_c, v_c∈ $ \mathbb{Z} $_q^*和u_1－c, v_1－c∈ $ \mathbb{Z} $_q^*, 计算V_c=v_cg, λ_c=u_ch_c+V_c, V_1－c=v_1－cg, λ_1－c=u_1－ch_1－c+V_1－c, 将λ_c和λ_1－c按照随机顺序先后发送给Alice请求签名。

S3:Alice分别计算S_{1, c}=x_Aλ_c和S_{1, 1－c}=x_Aλ_1－c, 将S_{1, c}和S_{1, 1－c}先后发送给Bob。

S4:Bob利用(u_c, v_c)、(u_1－c, v_1－c)和脱盲算法得到2组最终的消息签名对(m_c, S_c)和(m_1－c, S_1－c), 并先后发送给Alice。

S5:Alice输出一个对比特值c的猜测值c^′∈{0, 1}。

下面分析Alice正确猜对c的概率。因为盲化因子(u_c, v_c)、(u_1－c, v_1－c)是在 $ \mathbb{Z} $_q^*上均匀随机选取的, 选取的过程完全独立于m_c和m_1－c, 而盲化过程是可逆线性仿射变换且每次盲化因子是独立随机选取的, 所以盲化因子(u_c, v_c)、(u_1－c, v_1－c)完全独立于最终消息签名对(m_c, S_c)、(m_1－c, S_1－c)。从Alice的视角观察, 其分布也是相同的, 并且完全独立于c。由于c是随机均匀选取的, (m_c, S_c)和(m_1－c, S_1－c)对于c在计算上具有不可区分性, 因此Alice正确猜对c的概率是1/2, 即攻击者Alice无法以不可忽略的优势猜对c。

综上所述, 盲化因子u、v在签名过程中是随机选取的, 由于求解u、v都面临椭圆曲线上离散对数问题, 因此本文签名方案满足盲性。

3.2 随机预言机模型下的安全性证明

定理2  本文方案在随机预言机模型和CDH困难问题假设下, 可以抵抗适应性选择消息攻击下的存在性伪造攻击。

引理1  假定存在一个适应性选择消息和身份的攻击算法$ \mathfrak{R} $, 在多项式时间t内以不可忽略的优势ε攻破了本文方案, 记q_H、t_H分别为询问H预言机的次数和一次询问所需时间, q_s、t_s分别为签名询问的次数和一次询问所需时间, 则存在概率多项式时间算法C, 在时间t′＜t+(q_st_s+2q_Ht_H)内以不可忽略的优势$ \varepsilon^{\prime} \geqslant\left(\varepsilon-\frac{1}{2^{k}}\right)\left(1-\frac{1}{q_{\mathrm{H}}}\right)^{q_{\mathrm{s}}} \frac{1}{q_{\mathrm{H}}} $解决CDH问题。

证明  假定给C一个CDH困难问题的实例为:给定ag∈G₁和bg∈G₁, 要输出CDH问题的一个解abg。

C的目标是通过调用算法$ \mathfrak{R} $来解决上述困难问题实例, 游戏中假定$ \mathfrak{R} $不会对预言机发起2次相同的询问。

设定挑战身份ID的公钥为y=ag, 挑战消息为m^*, C在系统初始化后公布系统参数{k, G₁, G₂, g, H}, 将系统参数和y发送给$ \mathfrak{R} $。

1) H询问:C维护一个由数组(m_i, d_i, h_i)组成的列表, 当$ \mathfrak{R} $向C提交(ID, y, m)的H询问时, 查询列表L, 如果L中存在记录(m, d, h), 则返回相应的h给$ \mathfrak{R} $, 否则:

(1) 如果m≠m^*, 则随机选择一个d∈ $ \mathbb{Z} $_q^*, 计算h=dg, C在将其作为H(ID, y, m)的值返回给$ \mathfrak{R} $的同时, 将(m, d, h)保存到列表L中。

(2) 如果m=m^*, 则C将bg作为H(ID, y, m)的值返回给$ \mathfrak{R} $的同时, 将(m, ⊥, bg)保存到列表L中, 其中“⊥”表示空。

2) 签名询问:当$ \mathfrak{R} $向C提交一个关于m的签名询问时:

(1) 当m=m^*时, C返回“⊥”, 记此事件为E₁。

(2) 当m≠m^*时, C从L中恢复数组列表(m, d, h), 随机选择u, v∈ $ \mathbb{Z} $_q^*, 计算V=vg, λ=uh+V, S₁=udy+vy, S₂=S₁－vy, S=u^－1S₂返回给$ \mathfrak{R} $, 容易验证C返回的签名满足验证等式e(S, g)=e(h, y)。

经过适应性询问后, $ \mathfrak{R} $终止询问, 输出一个消息m且满足最终验证等式的消息/签名对(m, S^*)。如果m≠m^*, 则伪造失败, 记此事件为E₂; 否则, m=m^*, C从列表L中恢复数组(m^*, ⊥, bg), 因为签名验证等式e(S^*, g)=e(h^*, y)成立, 所以等式e(S^*, g)=e(bg, ag)=e(abg, g)成立。

由此, C成功地计算出S^*=abg, 并输出S^*作为CDH问题的一个实例的解答。以下分析C成功解决困难问题的时间和优势:

1) 对于H的询问的答案是均匀且独立分布在$ \mathbb{Z} $_q^*内的, 并且答案是有效的。

2) 只有当事件E₁、E₂不发生时, 最终的伪造签名才是有效的。

3) 如果事件E₁、E₂都不发生, 则C能解决CDH问题的一个实例。在签名询问阶段, 若m=m^*, 即E₁事件发生, 因为H询问共有q_H次, 所以问到目标挑战消息m^*的概率为$ \operatorname{Pr}\left(E_{1}\right)=\frac{1}{q_{\mathrm{H}}} $, 共进行q_s次独立的签名询问, 而由于每次询问是相互独立不相关的, 因此E₁事件不发生的概率为$ \operatorname{Pr}\left(\neg E_{1}\right)= \left(1-\frac{1}{q_{\mathrm{H}}}\right)^{q_{\mathrm{s}}}$; 在签名伪造阶段, 只有当伪造的消息是挑战消息m^*的签名时才能解决困难问题的实例, 即E₂事件不发生, 因此, E₂事件不发生的概率为$\operatorname{Pr}\left(\neg E_{2}\right)=\frac{1}{q_{\mathrm{H}}} $。综上可得事件E₁、E₂都不发生的概率为: $ \operatorname{Pr}\left(\neg E_{1} \wedge \neg E_{2}\right)=\left(1-\frac{1}{q_{\mathrm{H}}}\right)^{q_{\mathrm{s}}} \cdot \frac{1}{q_{\mathrm{H}}} $。

当$ \mathfrak{R} $没有询问H而伪造了一个有效的签名时, 这种模拟是存在漏洞的, 其发生的概率为$ \frac{1}{2^k} $(其中k为安全参数), 因此, C在该游戏中的一个优势下界为$ \varepsilon^{\prime} \geqslant\left(\varepsilon-\frac{1}{2^{k}}\right)\left(1-\frac{1}{q_{\mathrm{H}}}\right)^{q_{\mathrm{s}}} \frac{1}{q_{\mathrm{H}}} $, 运行时间的一个上界为t′＜t+(q_st_s+2q_Ht_H)。因此, 攻击者在概率多项式时间t^′内以一个不可忽略的概率ε^′成功解决了一个CDH问题实例, 这与CDH问题的难解性矛盾。因此, 由引理1即证定理2, 即本文方案在随机预言机模型和CDH困难问题假设下, 在适应性选择消息攻击下是存在性不可伪造的。

4 效率分析与代码实现 4.1 效率分析

将本文方案与相关典型的签名方案进行效率对比^[11], 如表 1所示, 其中, M表示G₁中的标量乘, P表示双线性对运算, E表示G₂中的幂乘运算, I表示$ \mathbb{Z} $_q^*中的求逆运算, H表示散列运算。

由表 1可以看出:在签名和验证签名的总效率方面, 本文方案与BLS短签名方案^[4]基本相同, 与其他方案相比效率较高; 在签名长度方面, 选择阶为160 bit的椭圆曲线上的群和双线性对映射^[16], 本文方案的签名长度为160 bit, 与BLS短签名方案^[4]基本相同, 与文献[4, 15]方案的签名长度相同, 而与文献[10, 12-14]签名方案相比长度较短。

4.2 关键代码实现

本文以斯坦福大学研究人员开发的一个开源C语言库(Pairing-based Cryptography library, PBC)为基础, 在操作系统为64位Windows 7, CPU为Intel i7-7700 3.6 GHz, 主板为华硕H270, 内存为金士顿DDR4 2 400 MHz的实验基准测试环境中实现本文方案。

本文方案首先对消息进行哈希处理, 再随机选择2个秘密值u, v∈ $ \mathbb{Z} $_q^*, 计算V=vg和λ=uh+V, 以此进行盲化处理。盲化处理的部分代码如下:

//盲化处理

sign_start=clock();

element_t h, u, v, V, r, uh;

charm[50]="SignMessagexpp20180218163438";

element_init_G1(h, pairing);

strcat(m, IDUi);

element_from_hash(h, m, strlen(m));

element_init_Zr(u, pairing);

element_init_Zr(v, pairing);

element_init_G1(V, pairing);

element_init_G1(r, pairing);

element_init_G1(uh, pairing);

printf("签名消息:\n%s\n\n", m);

element_random(u); //选择随机数u

element_random(v); //选择随机数v

element_mul(U, u, g); //计算U=u*g;

element_mul(uh, u, h); //计算uh=u*h;

element_add(r, uh, V); //计算r=u*h+V;

对盲化后的消息进行签名, 生成消息m的签名S的代码。图 2为对消息“SignMessagexpp201802 18163438”签名后的结果。

对盲化后的签名进行脱盲处理, 具体代码如下所示, 其中S为消息m的签名。

//脱盲处理

element_init_G1(S2, pairing);

element_init_G1(temp, pairing);

element_mul(temp1, v, yA); //temp1=v^yA

element_sub(S2, S1, temp1);//计算S2=S1-v*yA;

element_init_Zr(w, pairing);

element_init_Zr(inv_u, pairing);

element_invert(inv_u, u); //求u的逆

//输出最终签名S

element_init_G1(S, pairing);

element_mul(S, inv_u, S2);//计算S=U^-1*S2;

sign_end=clock(); //结束计时

element_printf("S = %B\n", S);

第三方验证消息签名对(m, S)的代码如下所示, 验证结果如图 3所示。

//验证签名

element_t left, right;

verify_start=clock();

element_init_GT(left, pairing); //等式左边

element_init_GT(right, pairing); //等式右边

element_pairing(left, S, g);

element_pairing(right, h, yA);

verify_end=clock(); //运行耗时

double verifyTime=difftime(verify_end, verify_start);

element_printf("e(S, g)=\n%B\n", left);

element_printf("e(h, yA)=\n%B\n\n", right);

//左右比较

if (!element_cmp(left, right))

printf("验证成功!\n\n\n"); //左右相同

printf("待签名消息m:%s \n", m);

printf("消息长度:%d \n", strlen(m));

printf("签名生成耗时:%f ms\n", signTime);

5 结束语

本文提出一种短盲签名方案, 并在随机预言机模型和CDH问题假设下, 证明该方案在适应性选择消息上是存在性不可伪造的。与典型盲签名方案相比, 本文方案签名长度短, 签名和盲化过程计算简单, 适合在带宽受限且使用超低功耗设备的环境下进行数据签名、验证以及交互传输。下一步将在文献[17-18]研究基础上, 把短签名方案应用于基于便携式设备的电子票据安全交互协议中, 实现对电子票据的匿名保护。