0 引言

1997年，Zheng^[1]第一次提出了签密的概念，在签密方案中，由于签名和加密在一个逻辑步骤内实现，计算和通信效率得到了明显提高。2002年，Malone-Lee^[2]结合基于身份密码体制^[3]提出了基于身份的签密方案，方案在密钥管理上更为简便，计算和通信效率得到了提高，在实际应用中优势逐渐明显。2010年，张串绒等^[4]提出了具有较高效率的基于身份的签密方案S-IDSC (Short IDentity based SignCryption)，该方案在随机预言机模型下被证明是安全的，但是存在签名验证条件的特殊性缺陷。张宇等^[5]基于S-IDSC方案^[4]的签名验证条件的特殊性缺陷，对文献[4]中的方案进行了改进，并同时证明了其安全性, 此外，计算效率也得到了提高。

量子计算机的出现，使得上述基于传统数学困难问题如大整数分解、离散对数等问题的密码体制变得不再安全。格密码^[6]以其较高的运算速度，及具有抗量子攻击的优良特性，成为近几年密码学的研究热点之一, 尤其是2005年Regev^[7]提出了错误学习(Learning With Errors, LWE)困难问题，并将LWE问题困难性归约到标准格上困难性问题之后，基于格的密码体制得到了快速发展。结合基于身份的密码体制，众多基于格上困难问题的身份类密码体制被相继提出^[8-10]。2010年，Agrawal等^[8]提出了格上基于(分层)身份的加密方案，并将其扩展到标准模型下证明了安全性，提供了后面格基身份密码体制的框架。2012年，Li等^[11]基于格上困难问题构造了一个格基签密方案，方案具有基于格上快速计算特性，同时方案具有适应性选择密文攻击不可区分性(adaptive INDistinguishability Chosen-Ciphertext Attack, IND-CCA2)安全性和存在性不可伪造(Existentially UnForgeable Chosen-Message Attack, EUF-CMA)安全性。之后，Yan等^[12]使用Micciancio方案^[13]新的陷门生成算法，提出了标准模型下的格基签密方案，方案更加简单高效，并证明了其安全性。最近，Lu等^[14]提出了一个标准模型下的格基签密方案，加密过程基于LWE困难假设，而签名的困难性基于格上小整数解(Small Integer Solution, SIS)困难问题; 而上述的格基签密方案^{[11-12, 14]}存在的问题是均不能满足前向安全性。

前向安全的概念首先出现在Günther^[15]提出的密钥交换协议中，用于保护用户的私钥泄露的情况下，加密数据的安全性。2013年，Singh等^[16]基于格上困难问题，结合前向安全模型，构造了一个基于身份的前向安全的加密方案，随机预言机模型和标准模型下的方案均被证明是选择身份前向安全的。

本文结合基于身份的前向安全模型，构造了一个基于格上困难问题的前向安全的基于身份的签密方案。签密过程利用格基授权算法对用户的公私钥对进行更新，以达到前向安全。在签名过程使用原像采样算法，使得签名过程困难性基于SIS问题，并用包含签名信息的哈希值对明文进行对称加密，使得加密过程简单高效。方案在随机预言机模型被证明是适应性选择挑战身份和选择密文攻击不可区分性(adaptive INDistinguishiability selective IDentity and Chosen-Ciphertext Attack, IND-sID-CCA2)安全和强不可伪造选择消息攻击(strong UnForgeable Chosen-Message Attack, sUF-CMA)安全。同时，相比基于配对的签密方案^[3-5]，本文方案具有较高的计算效率和抗量子攻击特性；相比基于格的身份类签密方案，本文方案具有前向安全性，因此具有广阔的应用前景。

1 理论基础 1.1 格

格^[6]是一种特殊的代数结构，在几何学上又称为点格，是n维空间中规则排列的离散的无限点集。它的定义如下：

定义1  一个n维的格Λ，是指由n个线性独立的向量b₁, b₂, …, b_n和整数的线性组合所形成的点的集合L(b₁, b₂, …, b_n)=$\left\{ {\sum\limits_{i \in [n]} {{\alpha _i}{\mathit{\boldsymbol{b}}_i}\left| {{\alpha _i} \in {\bf{Z}}} \right.} } \right\}$，其中向量b₁, b₂, …, b_n称作格Λ的一组基，记为B=[b₁, b₂, …, b_n]。

定义2  对于一个素数q，整数m、n，矩阵A∈Z_q^n×m，m维q-ary格定义为：

$ \begin{array}{l} \Lambda _q^ \bot (\mathit{\boldsymbol{A}}) = \{ \mathit{\boldsymbol{e}} \in {\mathit{Z}^m} s.t. {\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{e}} = 0(\bmod q)\} \\ \Lambda _q^u(\mathit{\boldsymbol{A}}) = \{ \mathit{\boldsymbol{e}} \in {\mathit{Z}^m} s.t. {\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{e}} = \mathit{\boldsymbol{u}}(\bmod q)\} \end{array} $

定义3  设ρ_s(x)为中心为0，标准差为s的n维高斯分布，即ρ_s(x)=exp (-π‖x‖²/s²)，那么对于格L，记ρ_s(L)=$\sum\limits_{\mathit{\boldsymbol{x}} \in L} {{\rho _s}(\mathit{\boldsymbol{x}})} $，当ρ_s(L)有界时，格L上的高斯分布定义为$\exists \mathit{\boldsymbol{y}} \in L, {D_{L, s}}(\mathit{\boldsymbol{y}}) = \frac{{{\rho _s}(\mathit{\boldsymbol{y}})}}{{{\rho _s}(L)}}$。

1.2 LWE困难问题及假设

LWE问题^[6]是Regev在2005年首次提出，其复杂性可有效归约到格上的最短独立向量问题(Shortest Independent Vector Problem, SIVP)和判定性最短向量问题(gap-Shortset Vector Problem, gap-SVP)困难问题。

定义4^[6]  设安全参数α>0，n>1，模数q>2n²，Z_q上的噪声概率分布$\bar{\Psi }=\left\{ \left\lceil \mathit{qx} \right\rfloor\rm{mod}\mathit{q}\left| \mathit{x}\sim \mathit{N}\left( \rm{0}, {{\alpha }^{\rm{2}}} \right) \right. \right\}$；随机选取均匀分布的向量s∈Z_qⁿ。设χ_α服从噪声概率分布${{{\mathit{\bar{\Psi }}}}_{\mathit{aq}}}$，保持向量不变，多次随机选取均匀分布的向量a∈Z_qⁿ和噪声e∈χ_α，输出(a, b=〈a, s〉+e)∈Z_qⁿ×Z_q，并将其分布记作A_{s, χα}(也称LWE分布)，整个运算过程均是模q操作。计算性LWE问题就是通过样本A_{s, χα}取样，通过(a, b=〈a, s〉+e)∈Z_qⁿ×Z_q计算，都能够以极大的概率输出s∈Z_qⁿ。

判定性LWE问题描述如下：

存在一个攻击者和R-LWE预言机O，预言机O包含两个采样算法O_$(随机均匀选取(a, b)∈U(Z_qⁿ×Z_q))和O_s(设定秘密s∈Z_qⁿ和选择均匀分布的a，计算(a, b=〈a, s〉+e)∈A_{s, χα})，攻击者向预言机O询问，O随机利用O_$或者O_s产生一些实例(a, b)∈U(Z_qⁿ×Z_q)返回给攻击者，如果能够准确分辨出实例来自O_$或O_s的优势Adv()=|Pr[A^O_S=1]-Pr[A^O_$=1]|是不可忽略的，那么就说能够解决判定性LWE问题。

1.3 格基授权算法

格基授权算法由Agrawal等^[17]提出，简单的格基授权算法在不改变维度的情况下，利用一个格及其陷门生成其他的格和陷门。格基授权算法如下：

定理1  任意给定矩阵A∈Z_q^n×m，格Λ^⊥(A)的一组基T_A∈Ζ^m×m，对于任意给定模q可逆的公共矩阵R∈Z_q^m×m，存在一个多项式时间算法，能够输出格Λ^⊥(B)⊆Z^m×m的一组基B∈Ζ^n×m及其陷门T_B∈Ζ^m×m。

BasisDel (A, R, T_A, σ)：

1)输入矩阵A∈Z_q^n×m，T_A∈Ζ^m×m，高斯参数σ∈R>0以及R←D_m×m∈Z_q^m×m；

2)定义B=AR^-1∈Z_q^n×m，输出Λ^⊥(B)的陷门T_B∈Ζ^m×m。

1.4 GPV签名

GPV签名^[19]由Gentry，Peikert，Vaikuntanathan在2008年STOC会议上提出，方案的安全性基于格上的小整数解(SIS)问题，GPV签名方案如下：

选取一个哈希函数H:{0, 1}^* → Z_qⁿ作为随机预言机。

系统建立(1ⁿ)：运行系统建立算法输出公共参数1ⁿ。

密钥生成(1ⁿ)：运行抗碰撞的原像采样陷门生成算法PSF.TrapGen (1ⁿ)，输出公私钥对(a, t)。

签名(sk=T, msg)：输入消息msg，首先检查存储列表L，如果(msg, σ_msg)在L中，输出σ_msg；否则计算y=H(msg)∈R_n，运行原像采样算法PSF.SamplePre (y, t)，输出签名σ_msg=x∈D_n。

验证(vk=a, msg, σ_msg=x)：验证算法计算y=H(msg)∈R_n，如果满足y=PSF.Eval (a, x)，则通过验证，否则输出⊥。

定理2  对于选取如下参数，m≥(5+3δ)n lb q，δ>0，s≥L·ω$\left( \sqrt{\rm{lb}\mathit{m}} \right)$，其中L=O$\left( \sqrt{\mathit{n}\rm{lb}\mathit{q}} \right)$。如果$\mathit{SI}{{\mathit{S}}_{\mathit{q}, \mathit{m}, 2\mathit{s}\sqrt{\mathit{m}}}}$是困难的，那么上述的签名方案可以达到强不可伪造选择消息攻击下的安全性(sUF-CMA)。

对于方案的安全性证明见参考文献[19]。

2 前向安全基于身份加密的形式化定义

前向安全的基于身份加密方案(Forward Secure Identity Based Encryption，FS-IBE)^[12]由以下5个算法构成：

系统建立(n, 1^λ, N)：输入系统参数n, 时间周期N和安全参数1^λ，输出加密的系统公钥MPK和主私钥MSK。

密钥生成(MPK, MSK, id)：输入系统公钥MPK，主私钥MSK和一个用户的身份标识id。输出相应用户身份的私钥SK_id。

密钥更新(MPK, SK_{id, i}, id‖i-1)：输入系统公钥MPK和第i-1时期的解密私钥SK_{id, i-1}，输出第i时期的解密私钥SK_{id, i}。

加密(MPK, id‖i, M)：输入系统公钥MPK，第i时期的公钥id‖i和待加密消息M，输出密文C。

解密(MPK, SK_{id, i}, C)：输入系统公钥MPK，解密私钥SK_{id, i}和密文C，输出明文消息M。

3 前向安全的格上基于身份签密方案

本章结合LWE困难问题基础上，利用格基授权算法构造了一个前向安全的签密方案。签密过程首先通过一个陷门生成函数生成主公私钥对; 然后利用格基授权算法进行用户的公私钥对的更新，以达到前向安全, 在签名过程使用原像采样算法，使得签名过程困难性基于SIS问题; 最后用包含签名信息的哈希值对明文进行对称加密，使得加密过程简单高效。方案具体由以下5个算法构成：

1)系统初始化。

参数设置：n为2的幂且n≥8，q为素数且q≥5，q=poly(n)。m=$\left\lceil \rm{6}\mathit{n}\rm{lb}\mathit{q} \right\rceil $，$\mathit{\tilde{L}}=\mathit{O}\left( \sqrt{\mathit{n}\rm{lb}\mathit{q}} \right)$，高斯参数μ, $\mathit{\sigma }\ge \mathit{\tilde{L}}\cdot \mathit{\omega }\left( \sqrt{\rm{lb}\mathit{m}} \right)$。加密的时间周期长度N。

①输入系统的安全参数n，q，运行算法TrapGen (n, q)生成一个矩阵A∈Z_q^n×m和格Λ_q^⊥(A)对应的陷门基T∈Z_q^m×m。

②选取哈希函数H₀:{0, 1}^* → {0, 1}ⁿ，H₁:{0, 1}^* → {0, 1}^m×m，抗碰撞的哈希函数H₂:{0, 1}^* → {0, 1}^l。

③随机选取2N个高斯参数σ₀, σ₁, …, σ_N-1, μ₀, μ₁, …, μ_N-1，主密钥为MSK=T₀由私钥生成器(Private Key Generator，PKG)掌握，A为公共参数。

2)私钥生成。

①对于一个时间周期的任意一个时间点i∈[N]={0, 1, …, λ}，输入用户的身份标识为id，定义如下矩阵A_{id, 0}=AR_{id, 0}^-1∈Z_q^n×m，其中R_{id, 0}=H₁(id, 0)∈Z_q^m×m。

②运行算法BasisDel (A, R_{id, 0}, T, σ₀)，产生一个陷门SK_{id, 0}∈Z_q^m×m，运行算法SamplePre (A_{id, 0}, SK_{id, 0}, 0, σ₀)，输出私钥T_{id, 0}∈Z_q^m，即用户在第0时期的密钥。

3)密钥更新。

①输入用户在第i-1时期的密钥T_{id, i-1}，计算用户计算第i时期的密钥，计算A_{id, i}=AR_{id, i}^-1∈Z_q^n×m，其中R_{id, i}=H₁(id, i)H₁(id, i-1)…H₁(id, 0)∈Z_q^m×m。

②设置R_i=H₁(id, i)∈Z_q^m×m，运行算法BasisDel (A_{id, i-1}, R_i, SK_{id, i-1}, σ_i)，输出SK_{id, i}∈Z_q^m×m。运行算法SamplePre (A_{id, i}, SK_{id, i}, 0, σ)，输出私钥T_{id, i}∈Z_q^m，发送者和接收者的公私钥对分别为(A_{id, i, s}, T_{id, i, s})，(A_{id, i, r}, T_{id, i, r})。

4)签密。

①选取需要加密的消息m∈{0, 1}^l，选取一个向量r∈{0, 1}^l。

②运行算法δ←SamplePre (A_{id, i, r}, T_{id, i, r}, H₀(m, i, r), μ_i)，输出签名δ。

③随机选取一个均匀分布的向量s∈Z_qⁿ，计算密文

c=m⊕H₂(s, δ)

④计算u=A_{id, i, r}^T·s + δ。输出签密文(c, r, u)。

5)解签密。

输入签密文(c, r, u)

①利用陷门T_{id, i, r}，计算出s和δ。

②计算m=H₂(s, δ)⊕c。

③验证等式A_{id, i, s}^T·δ=H₀(m, i, r):如果相等，说明签密文是合法的; 否则，拒绝接收签密文。

在①中，输入接收者的私钥T_{id, i, r}，由于(A_{id, i, r}, u=A_{id, i, r}^T·s + δ)对于短向量签名δ是一个LWE实例，进行如下计算：

$ \begin{align} & \mathit{\boldsymbol{T}}_{_{\mathit{id,i,r}}}^{\rm{T}}\mathit{\boldsymbol{u}}=\mathit{\boldsymbol{T}}_{_{\mathit{id,i,r}}}^{\rm{T}}(\mathit{\boldsymbol{A}}_{_{\mathit{id,i,r}}}^{\rm{T}}\cdot \mathit{\boldsymbol{s}}+\mathit{\delta })\rm{mod }\mathit{q}\rm{=} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \mathit{\boldsymbol{T}}_{_{\mathit{id,i,r}}}^{\rm{T}}\mathit{\boldsymbol{A}}_{_{\mathit{id,i,r}}}^{\rm{T}}\cdot \mathit{\boldsymbol{s}}+\mathit{\boldsymbol{T}}_{_{\mathit{id,i,r}}}^{\rm{T}}\mathit{\delta }\rm{mod}\mathit{q}=\mathit{\boldsymbol{T}}_{_{\mathit{id,i,r}}}^{\rm{T}}\mathit{\delta }\rm{mod}\mathit{q} \\ \end{align} $

由于T_{id, i, r}^T和δ中的项目都很小，T_{id, i, r}^TA_{id, i, r}^T=0，因此向量T_{id, i, r}^Tδ中的每个项目也都比q小得多，所以有T_{id, i, r}^Tδ mod q=T_{id, i, r}^Tδ，因此我们可以通过计算(T_{id, i, r}^T)^-1T_{id, i, r}^Tu mod q=(T_{id, i, r}^T)^-1T_{id, i, r}^Tδ得到签名δ，从而计算得到向量s。

4 方案分析 4.1 安全性分析

方案的安全性分析通过以下两个定理证明，定理3证明了方案的加密过程满足了IND-sID-CCA2安全，定理4证明了方案的签名过程满足sUF-CMA安全。

定理3  在随机预言机模型下，如果存在敌手以不可忽略的概率ε(至少进行q_Hj(j=0, 1, 2)次哈希询问，进行q_e次私钥提取询问，进行q_s次签密询问，进行q_u次解签密询问)赢得IND-sID-CCA2游戏，那么必然存在一个算法，可以在多项式时间内破解LWE问题实例。

证明  证明上述前向安全的基于身份签密方案在随机预言机模型下的语义安全性。证明如果存在多项式时间内的敌手可以以优势破解本文的签密方案，那么必然存在一个多项式时间内的敌手可以以不可忽略的优势破解LWE问题。假设存在这样一个敌手在与挑战者的交互游戏中能够以ε′的优势赢得游戏，挑战者是一个对于消息m的LWE问题(A_{id, i, r}, u=A_{id, i, r}^T·s + δ)的实例。

初始化  敌手宣布攻击的目标身份id^*，挑战者运行Setup算法，并将公开系统参数和id^*对应的公钥pk_r=${\mathit{\boldsymbol{\bar{A}}}}$发送给敌手。

阶段一  敌手以适应性地执行多项式数量级界以下的哈希询问H₀，H₁和H₂，私钥提取询问，签密询问以及解签密询问。挑战者保留三个模拟哈希预言机的列表L₀、L₁和L₂，询问如下：

1)私钥提取询问：敌手输入身份id^*，运行私钥提取算法，得到身份id^*对应的私钥sk。

2)H₀询问：对于H(m_j, i, r_j)询问，1≤j≤q_H，0≤i≤N-1，挑战者首先检查哈希函数H₀是否等于预先定义的输入(m_j, r_j)的值:如果是，则返回预先定义的值; 否则，挑战者随机选取一个h_1j∈R_n，将(m_j, r_j, h_1j)插入列表L₀，然后将h_1j返回给敌手。

3)H₁询问：对于在周期N内的任意时间，敌手可以适应性地对任意的身份id^*进行H₁哈希询问。挑战者检查哈希函数H₁是否等于预先定义的值：如果是，则返回预先定义的值；否则，挑战者随机选取一个R_{id, i, j}←D_m×m∈Z_q^m×m，将(id_j, i_j, R_{id, i, j})插入列表L₁，然后返回给敌手。

4)H₂询问：对于H₂(s_j, δ_j)询问，1≤j≤q_H2，挑战者首先检查哈希函数H₂是否等于预先定义的输入(s_j, δ_j)的值。如果是，则返回预先定义的值，否则，挑战者随机选取一个h_2j∈{0, 1}^m，将(s_j, δ_j, h_2j)插入列表L₂，然后返回给敌手。

5)签密询问：敌手输入一系列接收者身份id_k(k=1, 2, …, l)，发送者身份id_s和一个明文消息m，挑战者计算sk_idk=KeyExtract (id_k)和(c, r, u)=Signcrypt (M, sk_{id, s}, id_{k, r})，并将(c, r, u)发送给敌手。

6)解签密询问：敌手输入一系列接收者身份id_j(j=1, 2, …, l)，发送者身份id_s和一个签密文组(c, r, u)，将发送者的公私钥对(pk_r, sk_s)产生的签密文组(c, r, u)提交作为一个解签密询问，挑战者执行如下操作：

首先检查列表L₂，寻找元组(s_j, δ_j, h_2j)，是否有使得$u={{\mathit{\boldsymbol{\bar{A}}}}^{T}}\cdot {{s}_{j}}+{{\delta }_{j}}$以及相对应的元素h_2i，m_j=c⊕h_2j，在列表中存在元组(m_j, r_j, h_1j):如果不存在这样的元组，输出⊥; 否则，挑战者进一步检查f_pks(δ_j)=h_1j是否成立，如果等式成立，将m_j返回给敌手，否则，输出⊥。

挑战  经过阶段一的询问之后，敌手选择两个长度的相等的密文m₀，m₁和两个身份id_s，id_r，然后发送给挑战者。挑战者随机选择两个二进制字符串r^*←{0, 1}^m和c^*←{0, 1}^m，设u^*=${\bar{u}}$，将挑战密文组(c^*, r^*, u^*)发送给敌手。

阶段二  敌手可以和阶段一一样进行多项式数量级界以下的适应性询问，不同的是不能对相同发送者id_s的私钥sk_s^*产生的密文(c^*, r^*, u^*)进行解签密询问。但是敌手可以对不同发送者的公私钥对(pk_s^*, sk_s^*)生成的挑战密文(c^*, r^*, u^*)进行解签密询问。容易知道，敌手并不能确定是一个发送者私钥sk_s和接收者的公钥pk_r对应的签密文合法性，除非敌手对哈希值H₂$(\mathit{\boldsymbol{\bar{s}}}, \mathit{\boldsymbol{\bar{ }\!\!\delta\!\!\rm{ }}})$进行询问。如果这样的话，无论敌手的模拟观点如何完美，求解LWE问题将仅依赖于列表L₂。

猜测  敌手输出一个结果b′，挑战者只需检查(s_j, δ_j, h_2j)元组形式的列表L₂。对于列表L₂中的每一项，挑战者检查$\mathit{\boldsymbol{u}}={{{\mathit{\boldsymbol{\bar{A}}}}}^{T}}\cdot {{\mathit{\boldsymbol{s}}}_{\mathit{j}}}+{{\mathit{\boldsymbol{ }}\!\!\delta\!\!\rm{ }}_{\mathit{j}}}$是否成立:如果等式成立，挑战者停止并输出s_j作为LWE问题的解; 如果没有这样的方程满足等式，挑战者停止并输出“失败”。

根据分析，要想攻克s_j可以通过m_j=c⊕h_2j，或通过$\mathit{\boldsymbol{u}}={{{\mathit{\boldsymbol{\bar{A}}}}}^{T}}\cdot {{\mathit{\boldsymbol{s}}}_{\mathit{j}}}+{{\mathit{\boldsymbol{ }}\!\!\delta\!\!\rm{ }}_{\mathit{j}}}$。解决$\mathit{\boldsymbol{u}}={{{\mathit{\boldsymbol{\bar{A}}}}}^{T}}\cdot {{\mathit{\boldsymbol{s}}}_{\mathit{j}}}+{{\mathit{\boldsymbol{ }}\!\!\delta\!\!\rm{ }}_{\mathit{j}}}$，就是解决LWE问题，又LWE是困难问题，因此唯有破获问题H₂(s, δ)，设置ASK_H2为询问(s_j, δ_j, h_2j)哈希值事件。所以有:

$ \begin{align} & \rm{Pr}[\mathit{b}=\mathit{b}']\le \rm{Pr}[\mathit{b}=\mathit{b}'|\mathit{As}{{\mathit{k}}_{{{\mathit{H}}_{\rm{2}}}}}]\rm{Pr}[\mathit{As}{{\mathit{k}}_{{{\mathit{H}}_{\rm{2}}}}}]+ \\ & \rm{Pr}[\mathit{As}{{\mathit{k}}_{{{\mathit{H}}_{\rm{2}}}}}]=\frac{\rm{1}}{\rm{2}}+\frac{\rm{1}}{\rm{2}}\rm{Pr}[\mathit{As}{{\mathit{k}}_{{{\mathit{H}}_{\rm{2}}}}}] \\ \end{align} $

由于H₂是安全的哈希函数，因此赢得游戏的概率2Pr[b=b′]-1=Pr[Ask_H2]可忽略不计，因此本文方案可以达到IND-sID-CCA2安全。

定理4  在随机预言机模型下，如果存在一个敌手可以以一个不可忽略的概率ε₁(至少进行q_Hi(i=0, 1, 2)次哈希询问，进行q_e次私钥提取询问，进行q_s次签密询问，进行q_u次解签密询问)赢得强不可伪造选择消息攻击(sUF-CMA)游戏，那么必然存在一个算法可以在多项式时间内破解GPV签名方案，即破解SIS问题实例。

证明  假设存在一个敌手能够在多项式时间内攻破上述方案，即能够伪造一个签名，那么必然存在一个多项式时间内的算法能在GPV签名方案中伪造一个签名。敌手和挑战者之间的交互游戏如下：

初始化  敌手宣布攻击的目标身份id^*，挑战者运行Setup算法，设置发送者的公钥pk_s^*=A_s^*，将接收者的公钥A_r^*发送给敌手。

询问阶段  敌手以适应性地执行多项式数量级界以下的哈希询问H₀、H₁和H₂，以及签密询问。挑战者保留三个模拟哈希预言机的列表L₀，L₁和L₂，哈希询问和签密询问如下：

1)H₀询问：对于H₀(m_j, i, r_j)询问，1≤j≤q_H，0≤i≤N-1，挑战者首先检查哈希函数H₀是否等于预先定义的输入(m_j, r_j)的值。如果是，则返回预先定义的值，否则，挑战者设置δ_j=SampleDom (1ⁿ)，将(m_j, r_j, δ_j, ${{\mathit{f}}_{{{{\mathit{\bar{A}}}}_{\mathit{s}}}}}$(δ_j))插入列表L₀，然后将${{\mathit{f}}_{{{{\mathit{\bar{A}}}}_{\mathit{s}}}}}$(δ_j)返回给敌手。其模拟过程与GPV签名方案一样。

2)H₁询问：对于在周期N内的任意时间，敌手可以适应性地对任意的身份id^*进行哈希询问。挑战者检查哈希函数H₁是否等于预先定义的值:如果是，则返回预先定义的值; 否则，挑战者随机选取一个R_{id, i, j}←D_m×m∈Z_q^m×m，将(id_j, i_j, R_{id, i, j})插入列表L₁，然后返回给敌手。

3)H₂询问：对于H₂(s_j, δ_j)询问，1≤j≤q_H2，挑战者首先检查哈希函数H₂是否等于预先定义的输入(s_j, δ_j)的值:如果是，则返回预先定义的值; 否则，挑战者随机选取h_2j∈{0, 1}^m，将(s_j, δ_j, h_2j)插入列表L₂，然后将h_2j返回给敌手。

4)签密询问：如果敌手将发送者的公私钥对(pk_s, sk_s)产生的签名(r, δ)提交作为一个签密询问，挑战者运行签密预言机得到(r, δ)作为对消息的签密询问。然后挑战者将(m, r, δ, ${{\mathit{f}}_{{{{\mathit{\bar{A}}}}_{\mathit{s}}}}}$(δ))插入到列表L₁，最后挑战者随机选取一个向量s∈Z_q^m并计算c=H₂(s, δ)⊕m(H₂的值取自预言机模拟算法)和u=pk_r^T·s + δ，将签密文(c, r, u)发送给敌手。

伪造过程：敌手输出接收者的公私钥对和新的合法签密文(c^*, r^*, u^*)。挑战者操作如下：

1)利用接收者的私钥pk_r^*和u^*密文，计算得到s^*和δ^*。

2)恢复出明文消息m^*=H₂(s^*, δ^*)⊕c^*。

3)输出签名(r^*, δ^*)作为消息m^*在GPV方案中的伪造签名。

由于签密文(c^*, r^*, u^*)是合法的，因此有${{\mathit{f}}_{{{{\mathit{\bar{A}}}}_{\mathit{s}}}}}$(δ^*)=H₀(m^*, i, r^*)，即(r^*, δ^*)是对消息m^*在GPV方案中的合法签名。由于GPV签名方案在随机预言机模型下是sUF-CMA安全的，因此本文方案在随机预言机模型下同样是sUF-CMA安全的。

此外，本文方案还满足前向安全性。假设时间段0≤j < i≤N-1，用户在时间i并不能获得签密文(c, r, u)。同时在时间段i中用户将消息H₀(m, i, r)发送给签名者，签名者运行算法SamplePre (A_{id, i, s}, sk_{id, i, s}, H₀(m, i, r), μ_i)，产生签名δ且满足A_{id, i, s}·δ=H₀(m, i, r)，而用户只能通过BasisDel (A, R_{id, 0}, T, σ₀)和BasisDel (A_{id, i-1}, R_i, SK_{id, i-1}, σ_i)得到解密密钥，并且A_{id, i, s}·δ≠H₀(m, i, r)，所以本文方案满足前向安全性。

4.2 性能分析

由于基于格上的签密算法只包含群上的加法和乘法，相对于传统的基于配对的签密方案，不涉及复杂的配对和大整数运算，计算效率有很大的提高。与其他格上的签密方案相比，具有基于身份的密钥管理优势，且能满足前向安全性。在密文扩展率方面，参见表 1。本文方案由于采用了文献[18]方案中的方法，将签名消息作为LWE加密中的错误项，所以本文方案在密文扩展率也有优势。

5 结语

近年来，格密码的一些优越性能逐渐被人们开发并利用，基于格的密码方案也得到了快速发展。本文对基于格上的签密方案进行了研究，利用基于LWE困难问题和前向安全模型构造了一个格上可证明安全的前向安全的基于身份的签密方案。由于方案中的运算大多为格上有限域的加法和乘法运算，因此运算速度较快，效率较高，同时，本文方案还具有抗量子计算机攻击的优点。此外，由于本文方案是在随机预言机模型下实现的，下一步的工作是将方案进一步扩展到标准模型下，改进和实现更加高效实用的签密方案。