0 概述

随着现代科技的发展, 电子签名技术已广泛应用于人们的日常生活。环签名作为电子签名中的一种, 常用于电子现金、匿名电子投票、匿名举报和区块链应用等。环签名由密码学家RIVEST等人^[1]于2001年提出, 其与群签名一样, 都为签名者提供匿名性签名方案。在环签名中, 没有管理者只有环成员, 环成员之间彼此独立, 无需相互合作。在签名过程中, 签名者首先选定1个临时签名者集合, 签名者也包含在该集合中, 然后签名者利用自己的私钥和集合成员的公钥就可单独对消息进行签名。任何1位环成员都能代表集合对消息进行签名, 且验证签名只需集合成员的公钥、消息和签名, 无需签名者的私钥, 从而确保环签名的匿名性。研究人员采用不同安全模型提出多种环签名方案, 其安全性主要基于大整数因子化^[1-3]、离散对数^[4-5]和双线性配对^[6-8]等数论假设。随着量子计算机技术的进步, 大整数因子化和离散对数等问题可用Shor量子算法在概率多项式时间(Probabilistic Polynomial Time, PPT)内求解, 这给密码设置带来新的挑战, 上述环签名方案等传统安全保护方法在量子计算环境下已不再安全^[9]。

基于格的密码构造能抵抗量子攻击, 且格中主要为线性运算和模运算, 相较传统密码指数运算速度更快, 因此其有望成为后量子传统公钥替代者之一, 基于格的密码方案设计也成为学者们的研究热点^[10-11]。由于格中问题在一般情况和最坏情况下困难性相同, 因此格上任意实例的安全性都相同, 该特性吸引众多密码学家对基于格的环签名方案进行研究^[12-13]。2010年, CASH等人^[14]提出首个基于格的环签名方案, 并采用格基派生技术为环成员产生公私钥, 但是该方案签名长度较长, 计算费时不利于实施。2011年, WANG等人^[15]提出基于格的环签名新方案, 但该方案缺少标准模型下的安全性证明。2012年, 田苗苗等人^[16]利用GPV格点筛选算法^[11]提出一种基于格的环签名高效方案, 但如果将该方案中验证矩阵的l+2个公钥和环签名向量代入签名验证公式, 则敌手最多试(l+2)²次就可找到满足签名验证公式的公钥从而找到签名者, 因此该方案不具备匿名性。2018年, 热娜等人^[17]针对文献[15]方案中不满足不可伪造性的问题进行优化后, 提出基于格的环签名改进方案, 该方案在随机预言模型下证明满足环签名中的匿名性和不可伪造性, 并使用MP12陷门函数^[10]生成陷门。虽然该方案已证明具有安全性, 但是在随机预言模型下证明安全的方案在实际应用中有可能不安全, 且该方案的签名密钥和签名长度较长。

2012年, HOFHEINZ等人^[18-19]提出可编程哈希函数(Programmable Hash Function, PHF), 该函数是一种可模拟随机预言机某些可编程性质的特殊哈希函数^[20], 并利用可编程哈希函数分别构造了基于双线性映射和基于RSA算法的签名方案, 这2种方案具有更短的签名长度, 且从理论上更容易证明其安全性。传统可编程哈希函数的定义与构造都存在特定于DL群之间的代数结构问题, 这也是几乎所有已知可编程哈希函数均由DL问题构造的原因。2016年, ZHANG等人^[21]提出格上可编程哈希函数的概念, 利用格上可编程哈希函数重新构造了格上签名方案, 该方案继承了传统可编程哈希函数签名方案的优点, 改进了公钥过长的不足。虽然格和DL群之间代数结构差异较大, 传统可编程哈希函数定义看似不适合格, 且格上可编程哈希函数已超过传统可编程哈希函数的范围, 但由于格上可编程哈希函数继承了传统可编程哈希函数的概念, 并运用格上分区证明技巧^[21], 因此仍将其归类于可编程哈希函数。

文献[21]指出在非齐次小整数解(Inhomogeneous Small Integer Solution, ISIS)假设下, 任何基于格上的可编程哈希函数均抗碰撞, 因此可直接应用于环签名方案。为缩短格上环签名方案的签名和密钥长度, 本文提出一种基于格上可编程哈希函数的环签名新方案, 利用可编程哈希函数的特殊性质和MP12陷门函数生成陷门, 将可编程哈希函数嵌入环签名的构造中, 并对本文方案在标准模型下自适应选择消息攻击的存在不可伪造性(Existential Unforgeability against Adaptive Chosen Messages Attack, EUF-CMA)安全进行分析。

1 预备知识 1.1 格

格是由线性无关向量构成的整系数组合。假设向量b₁, b₂, …, b_n属于ℝ^m且线性无关, 则向量b₁, b₂, …, b_n是格的1组格基, 记作B=[b₁, b₂, …, b_n]∈ℝ^m×n, 该格表示为:

$ \mathcal{L}\left( {{\mathit{\boldsymbol{b}}_1}, {\mathit{\boldsymbol{b}}_2}, \cdots , {\mathit{\boldsymbol{b}}_n}} \right)=\left\{ \sum\limits_{i=1}^{n}{{{x}_{i}}}{{\mathit{\boldsymbol{b}}_i}}\mid {{x}_{i}}\in \mathbb{Z}, 1\le i\le n \right\} $

(1)

其中:若m=n, 则称格$\mathcal{L}$(b₁, b₂, …, b_n)是满维的; 若A是n×m矩阵, 其列向量为b₁, b₂, …, b_m, 则格由格基B生成, 表示为:

$ {\mathcal{L}}(\mathit{\boldsymbol{B}}) = {\mathcal{L}}\left( {{\mathit{\boldsymbol{b}}_1}, {\mathit{\boldsymbol{b}}_2}, \cdots , {\mathit{\boldsymbol{b}}_m}} \right) = \left\{ {\mathit{\boldsymbol{B}}x\mid x \in {\mathbb{Z}^m}} \right\} $

(2)

1.2 格上的困难问题

本文基于格上的小整数解(Small Integer Solution, SIS)问题和非齐次小整数解问题这2种困难问题研究格上可编程哈希函数环签名方案的安全性。

定义1(SIS问题)  若q为整数, β(n)为安全参数为n的函数, 则矩阵A∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$, 矩阵A中元素取自${\mathbb{Z}}_q$的n×m矩阵中, m=poly(n), SIS_{q, β}问题是找到非零向量v∈${\mathbb{Z}}^m$使得Av=0 mod q成立且满足‖v‖≤β。

定义2(ISIS问题)  若q为整数, β(n)为安全参数为n的函数, 矩阵A∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$, m=poly(n)。向量y∈${\mathbb{Z}}_q^n$, ISIS_{q, β}问题是找到非零向量v∈${\mathbb{Z}}^m$使得Av=y mod q成立且要满足‖v‖≤β。

1.3 格上可编程哈希函数

哈希函数$\mathcal{H}:\mathcal{X}\to \mathbb{Z}_q^{n{\rm{ \times }}m}$为可编程哈希函数(u, v, β, γ, δ)－PHF, 如果存在PPT内的陷门密钥生成H.TrapGen算法和陷门计算H.TrapEval算法, 则给出均匀随机矩阵A∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$和公开的陷门矩阵B∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$, 其具有以下性质:

1) 句法。在PPT内算法(K′, td)←H.TrapGen(1^k, A, B)输出密钥K′和陷门td。对于任意输入的X∈$\mathcal{X}$, 由陷门算法(R_X, S_X)=H.TrapEval(td, K′, X)得到R_X∈${\mathbb{Z}}_q^{m{\rm{ \times }}m}$和S_X∈${\mathbb{Z}}_q^{n{\rm{ \times }}n}$, 则s₁(R_X)≤β和S_X∈I_n∪{0}在陷门td上且大概率生成密钥K′。

2) 正确性。对于(K′, td)←H.TrapGen(1^k, A, B), 所有X∈${\cal X}$及与其相关的(R_X, S_X)=H.TrapEval(td, K′, X)存在H_K′(X)=H.Eval(K′, X)=AR_X+S_XB。

3) 统计上更接近陷门密钥。对于全部密钥(K′, td)←H.TrapGen(1^k, A, B)和K←H.Gen(1^k), (A, K′)和(A, K)之间的统计距离最大为γ。

4) 分布均匀的隐藏矩阵。对于所有(K′, td)←H.TrapGen(1^k, A, B), 任意输入X₁, X₂, …, X_u, Y₁, Y₂, …, Y_v∈$\mathcal{X}$对于任意i, j有X_i≠Y_j, 使得(R_Xi, S_Xi)=H.TrapEval(td, K′, X_i)和(R_Yi, S_Yi)=H.TrapEval(td, K′, Y_i), 进而得到Pr[S_X1=S_X2=…=S_Xu=0∧S_Y1, S_Y2, …, S_Yv∈I_n]≥δ, 其中概率超过与K′同时产生的陷门td。

若γ可忽略而δ不可忽略, 则称该哈希函数为(u, v, β)-PHF; 若u为k中随机选取的多项式, 则称该哈希函数为(poly, v, β)-PHF。

1.4 环签名

环签名方案由KeyGen、Sign和Verify 3个概率多项式时间算法组成^[3]。

1) KeyGen(1ⁿ)算法。输入系统安全参数n, KeyGen算法为每位环成员生成其签名密钥sk_i和验证密钥vk_i。

2) Sign(sk_i, ℝ, M)算法。输入环成员集合ℝ、消息M以及签名者的签名密钥sk_i, Sign算法得到的输出是环成员集合ℝ对消息M的签名σ。

3) Verify(ℝ, M, v)算法。输入环成员集合ℝ、消息M以及签名σ, 若验证满足签名条件, 则Verify算法输出为1, 否则输出为0。

1.5 环签名安全模型

若环签名方案满足匿名性和不可伪造性2个条件, 则该环签名方案为安全的签名方案。

1) 匿名性。假设PPT内敌手A以优势P_adv=P_suc-1/2赢得游戏, P_suc为敌手A赢得此游戏的概率, 若得到的P_adv可忽略, 则该环签名方案满足匿名性。

(1) 输入系统安全参数k, 挑战者C运用陷门生成TrapGen(1ⁿ, 1^m, q, I_n)算法, 挑战者C将系统参数发送给敌手A。

(2) 敌手A对签名进行询问, 挑战者C将所得签名结果返回给敌手A, 挑战者C向敌手A提交消息M∈{0, 1}ⁿ、环成员集合ℝ和用户i₀、i₁的身份, 挑战者C随机选取b∈{0, 1}, 最终敌手A得到签名σ_b。

(3) 敌手A输出身份猜测b′。

2) 不可伪造性。假设PPT内敌手A赢得游戏的概率P_suc可忽略, 则称该环签名方案在选择子环和适应性选择消息攻击下具有不可伪造性。

(1) 建立系统(KeyGen(1^k))。输入系统安全参数k, 挑战者C采用陷门生成算法TrapGen(1ⁿ, 1^m, q, I_n)将公钥集合ℝ={vk₁, vk₂, …, vk_l}发送给敌手A, 而将其私钥sk_i保密。

(2) 签名询问(Sign Queries)。敌手A适应性选择子环ℝ={vk₁, vk₂, …, vk_l}和消息M∈{0, 1}ⁿ, 挑战者C运行Sign算法将结果σ返回给敌手A。

(3) 伪造签名(Forgery)。敌手A输出环签名(ℝ′, M′, σ′), 若验证(ℝ′, M′, σ′)为有效且未在签名询问中被询问, 则敌手A赢得该游戏, 伪造成功。

2 方案描述

本文方案中系统参数的生成：1, n, m′, v, q∈${\mathbb{Z}}$、β∈ℝ为安全参数$k = \left\lceil {{\rm{lb}}\;q} \right\rceil $中的多项式, 假设H=(H.Gen, H.Eval)为从{0, 1}¹到${\mathbb{Z}}_q^{n{\rm{ \times }}m}$的任意(1, ν, β)-PHF, 系统参数m=O(n  lb  n), m=m+m′且s>max(β, $\sqrt m $)·ω($\sqrt {{\rm{lb}}\;n} $)∈ℝ, 环签名方案SIG=(KeyGen, Sign, Verify)具体步骤如下:

1) KeyGen(1^k)。输入安全参数k, 和用MP12陷门生成算法^[10]计算得到(A_i, T_i)←TrapGen(1ⁿ, 1^m, q, I_n), 其中$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }\bar{m}}$, T_i∈$\mathbb{Z}_{q}^{\left( \bar{m}-nk \right)\text{ }\!\!\times\!\!\text{ }nk}$。随机选择A₀←$_{r}\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }nk}$和u←$_{\text{r}}\mathbb{Z}_{q}^{n}$, 计算K←H.Gen(1^k), 最终得到(vk_i, sk_i)=((A_i, A₀, u, K), T_i)。

2) Sign(sk_i, K, M)。假设ℝ={vk₁, vk₂, …, vk_l}为环成员集合, 给出私钥sk_i和消息M∈{0, 1}ⁿ, 随机选择t←_r{0, 1}¹, 计算A_{ℝ, M, t}=(A_ℝ‖(A₀+H(0‖t)G)+H_K(M))∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$以及H_K(M)=H.Eval(K, M)∈$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }nk}$, 其中A_ℝ=[A₁‖A₂‖…‖A_l]为环成员集合ℝ中有序串联的矩阵, 然后计算e←Sample(T_i, A_{ℝ, M, t}, I_n, u, s), 最终得到签名σ=(e, t)。

3) Verify(K, M, σ)。给出环成员集合ℝ、消息M和签名σ=(e, t), 计算A_{ℝ, M, t}=(A_ℝ‖(A₀+H(0‖t)G+H_K(M))∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$, 其中H_K(M)=H.Eval(K, M)∈$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }nk}$。如果满足‖e‖≤s·$\sqrt{m}$和A_{ℝ, M, t}e=u, 则输出为1, 否则输出为0。

T_i为敌手A的1个G陷门, 其通过零行填充可扩展到A_{ℝ, M, t}的1个G陷门, 且s₁(T_i)≤$\sqrt{m}$·ω($\sqrt{\text{lb}\ n}$)。由于s=Õ(n^2.5)>s₁(T_i)·ω($\sqrt{\text{lb}\ n}$), 向量e的输出通过SampleD得到, 而SampleD遵循满足A_{ℝ, M, t}e=u的${{D}_{{{\mathbb{Z}}^{m}}, s}}$分布, 因此, ‖e‖≤s·$\sqrt{m}$以极大概率成立, 说明本文环签名方案具有正确性。

3 安全性分析 3.1 匿名性分析

定理1  本文格上可编程哈希函数的环签名方案满足完全匿名性。

证明  对本文方案匿名性的证明过程如下:

1) 假设存在PPT内的敌手A和挑战者C, 挑战者C运用方案中的陷门生成TrapGen(1ⁿ, 1^m, q, I_n)算法, 输出公开验证密钥vk_i=(A_i, A₀, u, K)和签名私钥sk_i=T_i, 挑战者C将系统参数发送给敌手A。

2) 敌手A向挑战者C提出环成员集合ℝ和消息M∈{0, 1}ⁿ的签名询问, 挑战者C执行签名方案的签名步骤, 即执行Sign(sk_i, ℝ, M), 挑战者C将得到的签名结果返回给敌手A。

3) 敌手A适应性选择询问用户i < l的相应私钥, 挑战者C返回B_i。

4) 挑战者C向敌手A提交消息M∈{0, 1}ⁿ、环成员集合ℝ和用户i₀、i₁的身份, 挑战者C随机选取b∈{0, 1}, 输入i_b对应的私钥T_b, 并执行Sample(T_i, A_{ℝ, M, t}, I_n, u, s)算法得到签名σ_b返回给敌手A。

5) 敌手A输出身份猜测b′。

上述匿名性证明过程中用户i₀、i₁的签名分别为σ₁、σ₂, 由于σ₁和σ₂为从D_{Λu^⊥(Aℝ, M, t), S}中利用高斯抽样算法得到, 具有相同分布且两者之间的统计距离可忽略不计, σ₁和σ₂不可区分, 敌手A赢得该游戏的优势可忽略, 因此本文方案满足完全匿名性。

3.2 不可伪造性分析

为对本文方案进行不可伪造性分析，将系统参数设置为：1, m, n, q, v∈${\mathbb{Z}}$为安全参数k的多项式, 适应地选择1=O(lb n)和v=ω(lb n), 如果存在概率多项式时间内的伪造者F以不可忽略的概率ε进行Q=poly(n)次签名查询, 则会打破本文格上可编程哈希函数的环签名方案的EUF-CMA安全性。采用算法B解决上述ISIS_{q, m, β}问题, 其中概率至少为ε′≥$\frac{\varepsilon }{{{{16.2}^1}n{\mathit{\boldsymbol{v}}^2}}} - {\mathop{\rm negl}\nolimits} (k) = \frac{\varepsilon }{{Q \cdot \tilde O(n)}}$。

证明  对本文方案不可伪造性的证明过程如下:

给出算法B的结构并模拟伪造者F的攻击环境, 有至少$\frac{\varepsilon }{{\tilde O({n^2})}}$的概率解决ISIS_{q, m, β}问题。首先采用算法B随机选择向量t′←_r{0, 1}¹, 伪造者F输出带标签的伪造签名t^*=t′, 然后模拟EUF-CMA游戏如下:

1) 密钥生成(KeyGen)。给出ISIS_{q, m, β}问题的挑战实例(A_i, u)∈$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }\bar{m}}$×$\mathbb{Z}$_qⁿ, 计算环成员集合ℝ中有序串联的矩阵A_ℝ=[A₁‖A₂‖…‖A_l], (K′, td)←H.TrapGen(1^k, A_ℝ, G)。采用算法B随机选取T₀←$_{r}{{\left( {{D}_{\mathbb{Z}_{\cdot }^{{\bar{m}}}, \omega (\sqrt{1\text{b}\ n})}} \right)}^{nk}}$, 计算A₀=A_ℝℝT₀-H(0‖t′)G, 并输出vk=(A_i, A₀, u, K′), 保密(T₀, td)。

2) 签名过程(Signing)。给出消息M, 通过算法B随机地选取标签t←_r{0, 1}¹, 如果t被用来回答超过v个消息的签名, 则算法B中止, 否则计算(T_M, S_M)=H.TrapEval(td, K′, M), 得到A_{ℝ, M, t}=(A_ℝ‖(A₀+H(0‖t)G)+H_K′(M))=(A_ℝ‖A_ℝ(T₀+T_M)+(H(0‖t)-H(0‖t′)+S_M)G)。由于S_M=bI_n=H(b‖0), 其中b∈{-1, 0, 1}, 因此存在Ŝ=H(0‖t)-H(0‖t′)+S_M=H(b‖(t-t′))。算法B需区分以下情况:

(1) t≠t′或者t=t′∧b≠0。在该情况下, Ŝ可逆, ${\hat{T}}$=T₀+T_M对于A_{ℝ, M, t}是1个G陷门。由于s₁(T₀)≤$\sqrt{m}\cdot \omega \left( \sqrt{\text{lb}\ n} \right)$且s₁(T_M)≤Õ(n^2.5), 因此s₁(${\hat{T}}$)≤Õ(n^2.5), 计算e←SampleD(${\hat{T}}$, A_{ℝ, M, t}, Ŝ, u, s), 最终得到签名σ=(e, t)。若设置合适的s=Õ(n^2.5)≥s₁(${\hat{T}}$)·$\omega \left( \sqrt{\text{lb}\ n} \right)$, 则算法B以不可忽略的概率生成消息M的有效签名。

(2) t=t′∧b=0:算法B停止。

3) 伪造(Forge)。在进行最多Q次签名询问后, 伪造者F输出消息M^*∈{0, 1}ⁿ的伪造签名σ^*=(e^*, t^*), 从而有‖e^*‖≤$s\sqrt{m}\cdot $和A_{ℝ, M^*, t^*}e^*=u, 其中A_{ℝ, M^*, t^*}=(A_ℝ‖(A₀+H(0‖t^*)G)+H_K(M^*))∈${\mathbb{Z}}_q^{n{\rm{ \times }}m}$。通过算法B计算(T_M^*, S_M^*)=H.TrapEval(td, K′, M^*), 如果t^*≠t′或者S_M^*≠0, 则算法B中止模拟。此外, 存在A_{ℝ, M^*, t^*}=(A_ℝ‖A_ℝ(T₀+T_M^*))=(A_ℝ‖A_ℝ${\hat{T}}$), 其中${\hat{T}}$=T₀+T_M^*, 最终算法B输出ê=(I_m‖${\hat{T}}$)e^*作为解决方案。

由ISIS_{q, m, β}问题的定义可知(A_i, u)均匀分布于$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }\bar{m}}\text{ }\!\!\times\!\!\text{ }\mathbb{Z}_{q}^{n}$。由于T₀←_r${{\left( {{D}_{{{\mathbb{Z}}^{{\bar{m}}}}, \omega \left( \sqrt{\text{lb}\ n} \right)}} \right)}^{nk}}$, 因此得到A₀∈$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }nk}$在统计上接近$\mathbb{Z}_{q}^{n\text{ }\!\!\times\!\!\text{ }nk}$。此外, 模拟密钥K′在统计上接近真实密钥K, 因此, 模拟验证密钥vk的分布在统计上接近真实验证密钥。

假设全部消息M₁, M₂, …, M_u在回答签名查询时, 通过算法B使用相同标签t=t′, 对于i∈{1, 2, …, u}使得(T_Mi, S_Mi)=H.TrapEval(td, K′, M_i), 给出2个条件:1)某些标签t用于回答超过v个消息的签名; 2)S_Mi对于某些i∈{1, 2, …, u}不可逆, 当S_M^*≠0或者t^*≠t成立时, 模拟过程中止。

伪造者F最多进行Q=poly(n)次签名询问, 选择1=O(lb  n)得到$\frac{Q}{{{2}^{1}}}\le \frac{1}{2}$。对于每个签名消息, 算法B会随机选择标签t←_r{0, 1}¹, 且用任何标签t回答超过v个消息的签名概率小于${Q^2} \cdot {\left( {\frac{Q}{{{2^1}}}} \right)^\mathit{\boldsymbol{v}}}$, 设置的v=ω(lb  n)可忽略不计, 且算法B用相同标签t=t′回答u≥v消息的签名概率可忽略。在u≤v的条件下, 对于i∈{1, 2, …, u}和S_M^*=0, S_Mi为可逆且概率至少为δ=$\frac{1}{{16n{\mathit{\boldsymbol{v}}^2}}}$-negl(k)。t′为随机选择且隐藏于伪造者F中, Pr[t^*=t′]的概率至少为$\frac{1}{{{2^1}}}$-negl(k)。因此, 若伪造者F能在真实游戏中以ε概率成功攻击本文方案的EUF-CMA安全, 则伪造者F会以至少(ε-${Q^2} \cdot {\left( {\frac{Q}{{{2^1}}}} \right)^\mathit{\boldsymbol{v}}}$)·δ·($\frac{1}{{{2^1}}}$-negl(k))=$\frac{\varepsilon }{{{2^1} \cdot 16n{v^2}}}$-negl(k)=$\frac{\varepsilon }{{Q \cdot \tilde O(n)}}$的概率在模拟游戏中输出伪造的(M^*, e^*)。

证明ê=(I_m‖${\hat{\mathbb{R}}}$)e^*能有效解决ISIS_{q, m, β}问题的例证(A, u)如下:通过签名方案中验证算法的条件得到A_{ℝ, M^*, t^*}e^*=u和‖e^*‖≤$s\sqrt{m}$, 由于s₁(T₀)≤$\sqrt{m}\cdot \omega \left( \sqrt{\text{lb}\ n} \right)$和s₁(T_M^*)≤β=Õ(n^2.5), 因此‖ê‖≤Õ(n^2.5)·$s\sqrt{m}$=Õ(n^5.5)=β, 证明完毕。

4 效率分析

本文利用格上可编程哈希函数的特殊性质设计出一种在标准模型下可证明安全性的环签名方案, 并以验证密钥长度、签名密钥长度、签名长度以及基于格上的困难问题作为方案效率评价指标, 将本文方案与文献[15-17]中格上同类型环签名方案进行对比, 结果如表 1所示。

在计算验证密钥长度、签名密钥长度和签名长度时, 文献[15]方案和文献[16]方案采用随机矩阵陷门函数^[11], 而本文方案和文献[17]方案采用G矩阵陷门函数^[10], 该陷门函数在生成过程中不涉及代价较高的矩阵求逆操作, 计算复杂度相当于2个随机矩阵的1次乘运算, 陷门生成过程较简单。此外, 由于陷门采用原像采样算法, 该算法支持并行运算且输入项为小整数, 对离散空间需求较低, 因此本文方案的验证密钥长度、签名密钥长度、签名长度均小于文献[15]方案和文献[16]方案。此外, 文献[15]方案和文献[16]方案的陷门参数${\hat{m}}$≥5n lb q, 而本文方案由于安全参数$k=\left\lceil \text{lb}\ q \right\rceil $取值很小, m′为k中的整数且m=O(n lb q), 其中m=m+m′, 对比发现本文方案的m小于文献[15]方案和文献[16]方案的${\hat{m}}$, 因此本文方案具有更短的验证密钥、签名密钥和签名。本文方案将可编程哈希函数应用到环签名的签名构造中, 存在m≥ω≥n, 因此本文方案的验证密钥比文献[17]方案更长, 但其签名密钥长度和签名长度均短于文献[17]方案。对于方案安全性基于格上的困难问题, 由表 1可知, 文献[15-17]方案的安全性取决于格上的SIS问题, 而本文方案的安全性取决于ISIS问题, SIS和ISIS问题的困难性分别基于格中最短矢量问题(SVP)和最近矢量问题(CVP), SVP和CVP是非确定性多项式(Nondeterministic Polynominal, NP)难问题, 且在PPT内为归约关系。由上述分析可知, 本文方案的效率高于文献[15-17]方案。

5 结束语

格上可编程哈希函数能模拟随机预言机部分可编程性质, 通过格上分区证明方式直接应用于签名构造和安全性验证。本文提出一种新的格上可编程哈希函数环签名方案, 利用MP12陷门函数生成陷门, 将可编程哈希函数应用到环签名构造中, 进而形成验证密钥、签名密钥和签名。分析结果表明, 该方案所得签名和密钥较其他格上环签名方案更短, 且在标准模型下满足EUF-CMA安全要求。后续将研究如何在保持签名密钥和签名长度不变的情况下, 缩短验证密钥长度并提高效率, 同时考虑将本文方案推广到基于身份的环签名方案中, 以得到更短的签名和密钥。