算法 1 TrapGen^[13]

此算法输入参数n,q,m，输出两个矩阵(A,T)，其中A服从Z_q^n×m上的均匀分布，T∈Z^m×m满足AT=0(modq)且T中的每个列向量具有较小长度。

算法 2 BasisDel^[14]

此算法输入算法1中的(A,T)，R←D^m×m服从Z^m×m上的高斯分布，高斯参数为σ，输出两个矩阵，其中(B,T_B)，B=AR^-1(modq),BT_B=0(modq)且T_B中的每个列向量具有较小长度。

算法 3 SamplePre^[13]

此算法输入算法1中的(A,T)，v=Z_qⁿ，和σ >0，输出e∈Z^m满足Ae = v(modq)且 $\left\| {\bf{e}} \right\| \leqslant \sigma \sqrt m $ 。

算法 4 SampleRwithBasis^[14]

此算法输入矩阵A∈Z_q^n×m，输出3个矩阵(R,B,T_B)，其中R←D^m×m，B = AR^-1(modq)，BT=0(modq)且T_B中的每个列向量具有较小长度。

定义 1 LWE^[13]

带错学习问题(learning with errors problem,LWE)描述如下：给定二元组(A∈Z_q^n×m，A^Tv + e(mod q))，其中e服从某个适当的概率分布，求解v∈Z_qⁿ。

定义 2 ISIS^[13]

非齐次小整数问题(inhomogeneous small integer solution problem,ISIS)描述如下：对于β > 0，和二元组(A∈Z_q^n×m，y∈Z_qⁿ)，寻找非零的短向量e∈Z^m，使得Ae = y(mod q)且 $\left\| e \right\| < \beta $ 。

定义 3 GPV签名^[13]

GPV签名方案如下构建：对安全参数n，q = poly(n)，m≥5nlg q，高斯参数σ > 0，和碰撞稳固的hash函数 $H:{\left\{ {0,1} \right\}^{n + l}} \to {\Bbb Z}_q^n$ ，

1) 密钥生成：运行算法TrapGen(n,q,m)生成(A,T)，A为验证公钥，T为签名私钥。

2) 签名算法：输入签名私钥T，消息 $\varpi \in {\left\{ {0,1} \right\}^l}$ 。随机选择ζ ∈{0,1}ⁿ，运行算法SamplePre $(A,T,H(\varpi ,\zeta ),\sigma )$ 获得e∈Z^m。输出(ζ ,e)作为消息 $\varpi $ 的签名。

3) 验证算法：输入消息 $\varpi $ 和签名(ζ ,e)，如果 $Ae = H(\varpi ,\zeta )$ 且 $\left\| e \right\| \leqslant \sigma \sqrt m $ ，则接受签名；否则拒绝。

在ISIS问题难解性假设下，GPV签名在适应性选择消息攻击下是存在性不可伪造的，也就是EUF-CMA安全的。

1) 系统设置：此算法由PKG(private key generator)执行。输入安全参数n，输出主密钥msk和系统参数params。保密msk，公开params。

2) PKC密钥生成：PKI系统中的每个用户执行这个算法生成自己的公钥pk和私钥sk。

3) IBC密钥生成：算法由PKG执行，输入是用户身份id，输出是身份id的私钥sk。

4) 签密算法：算法由消息的发送者完成，输入为params，发送者的私钥sk_s，接收者的身份id，消息 $\varpi $ ，输出密文C。

5) 解签密算法：算法由消息的接收者完成，输入为params，接收者的私钥sk_id，发送者的公钥pk_s，密文C，输出消息 $\varpi $ 或终止符号⊥。

此外，算法必须满足正确性，如果C =Signcrypt(sk_s ,id, $\varpi $ )，则有 $\varpi $ = Unsigncrypt(sk_id,pk_s,C)

定义 4 如果任何多项式有界的敌手A在如下的和挑战者C的游戏中胜出的概率都是可忽略的，则称类型1的异构签密方案具有适应性选择密文攻击下的不可区分性，即是IND-HSC-CCA2安全的。

1) 初始阶段：C运行系统设置，生成系统参数params；并运行PKC密钥生成算法获得发送者的公钥pk_s和私钥sk_s，一并发送给A。

2) 阶段1：A可以执行多项式有界次数的如下查询，C负责应答。

① IBC密钥查询：

A选择一个身份id发送给C，C运行IBC密钥生成算法得到身份id的私钥sk_id，返回给A。

② 解签密查询：

A选择一个接收者身份id和一个密文C发送给C。C运行IBC密钥生成算法得到身份id的私钥sk_id，然后运行解签密算法Unsigncrypt(sk_id ,pk_s,C)，将运行结果返回给A。

3) 挑战阶段：阶段1由A宣告终止，同时A选择两个相同长度的明文 ${\varpi _1},{\varpi _2}$ 和接收者身份id₀(要求id₀未被查询过密钥)，将其发送给C。C随机选择b∈{0,1}，计算C₀ =Signcrypt(sk_s ,id₀ , ${\varpi _b}$ )，将其返回给A。

4) 阶段2：A继续执行阶段1中的操作，除了不能查询id₀的私钥，不能对(id₀ ,C₀ )执行解签密查询。

5) 猜测阶段：A输出对b的猜测b'。如果b'=b，A赢得游戏。

A在游戏中的优势为Adv(A ) =丨2Pr[b′ = b]^-1丨，其中Pr[b′= b]表示b' = b的概率。

定义 5 如果任何多项式有界的敌手F在如下的和挑战者C的游戏中胜出的概率都是可忽略的，则称类型1的异构签密方案具有适应性选择消息攻击下的存在不可伪造性，也就是EUF-HSC-CMA安全的。

1) 初始阶段：C运行系统设置，获得主密钥msk和系统参数params。同时运行PKC密钥生成算法，获得发送者的公钥pk^s和私钥sk_s。C将msk、params和pk_s发送给F。

2) 攻击阶段：F执行多项式有界次数的签密查询。在签密查询中，F选择一个接收者的身份id和一个消息 $\varpi $ 给C。C执行签密算法Signcrypt(sk_s ,id, $\varpi $ )，将其结果返回给F。

3) 伪造阶段：F生成一个接收者身份 id₀和一个新的密文C₀。如果身份id₀和密文C0满足如下条件：

① Unsigncrypt(sk0 ,pk0 ,C₀)返回某个消息 $\varpi $ ₀而不是终止符号⊥；

② F没有询问过关于 $\varpi $ ₀和id₀的签密查询；则称F赢得了游戏。

F的优势为他赢得游戏的概率。

1) 系统设置

输入安全参数n，对q = poly(n)，m≥5nlg q ，PKG运行算法TrapGen(n,q,m)生成(A,T)，A为主公钥，T为主私钥。

令l是消息的长度，选择3个碰撞稳固的hash函数 H₁ : {0,1}^*→ D^m×n，H₂: {0,1}ⁿ⁺¹→ Z_qⁿ，H₃: {0,1}^*→{0,1}^l。

${\sigma _1} = {m^{3/2}}\omega \left( {{{\log }^2}m} \right),{\sigma _2} = {m^{2.5}}\omega \left( {\sqrt {\log m} } \right)$ 。则系统参数：

params =( n,q,m,l,σ₁,σ₂,A,H₁,H₂,H₃)，主私钥msk = T。

2) PKC密钥生成

每个用户S运行算法TrapGen(n,q,m)生成(A_s, T_s)，A_s为公钥，T_s为私钥。

3) IBC密钥生成

对用户份id∈{0,1}^*，PKG计算R = H _l (id)。

运行算法BasisDel(A,T,R,σ₁ )产生(A_id ,T_id )，其中A_id = AR^-1(mod q)，T_id为用户身份id的私钥。

4) 签密算法

发送者S要发送消息 $\varpi $ ∈{0,1}^l给身份为id的接收者，设发送者S的公钥为A_S，私钥为T_S，则发送者S如下操作：

① 随机选择 $\zeta \in {\left\{ {0,1} \right\}^n},v \in {\Bbb Z}_q^n$ 。

② 令 $e = SamplePre({A_s},{T_s},{H_2}(\varpi ,\zeta ),{\sigma _2})$ 。

③ 计算A_id=AH_l(id)^-1(mod q)。

④ 令c_l=A_id^Tv+e,c₂= $\varpi \oplus $ H₃(v,e)。

输出C = (ζ ,c₁,c₂)作为密文传输。

5) 解签密算法

身份为id的接收者收到密文C = (ζ ,c₁,c₂)，设他的私钥为T_id，则解签密操作如下：

① 利用T_id从c_l=A_id^Tv+e中恢复v和e。

② 令 $\varpi = {c_2} \oplus $ H₃ (v,e)。

③ 验证A_s e = H₂( $\varpi ,\xi $ )和 $\left\| e \right\| \leqslant {\sigma _2}\sqrt m $ 是否成立。若都成立，接收消息 $\varpi $ ；否则，拒绝。

因为A_idT_id=0(mod q)，所以有：

因为矩阵T_id和向量e都只有足够小的数值作为分量， $T_{{\text{id}}}^{\text{T}}e(\bmod q) = T_{{\text{id}}}^{\text{T}}e$ ，则(T_id^T)^-1T_id^Te=e。

进而，A_id^T=c₁ - e(mod q)，高斯消元法解线性方程组可得v。又c₂= $\varpi \oplus $ H₃ (v,e)，所以 $\varpi = {c_2} \oplus $ H₃ (v,e)。

因e=SamplePre (A_S,T_S,H₂( $\varpi ,\xi $ ),σ₂)，由算法3的定义，A_Se=H₂ ( $\varpi ,\xi $ )和 $\left\| e \right\| \leqslant {\sigma _2}\sqrt m $ 成立。

综上，解签密算法是正确的。

定理 1 IND-HSC-CCA2安全性

在LWE问题难解性假设下，方案作为类型1异构签密体制是IND-HSC-CCA2安全的。

证明：挑战者C有一个LWE问题的实例(A₀,C₀=A₀^Tv₀+e₀)，如果存在敌手A能够以不可忽略的概率ε攻击方案作为类型1异构签密体制的IND-HSC-CCA2安全性，则C求解LWE问题实例的解v₀的概率ε'≥1/Q₁ε-(Q₂Q_u)/2ⁿ⁺¹，其中Q₁是H₁查询的次数，Q₂是H₂查询的次数，Q_u是解签密查询的次数。挑战者C和敌手A之间的交互如下。

1) 初始阶段：C抽取R₀ ←D^m×m，令，A=A₀R₀同时运行PKC密钥生成算法获得发送者S的公钥A_s和私钥T_s。C将A，A_s和T_s发送给A。

2) 阶段1：A可执行多项式有界次数的如下查询，且默认hash查询在其他查询之前，C负责应答。

①H₁(id_i)查询：

如果是第i₀次查询，把(id₀,R₀,A₀,⊥)存在H₁列表中，返回R₀。否则，运行算法SampleRwithBasis(A)，得R_i和T_i，把(id_i,R_i,A_i=AR_i^-1,T_i)存在H₁列表中，返回R_i。

② H₂( $\varpi $ _i,ζ_i)查询：

随机选取h_2i∈Z_qⁿ，把( $\varpi $ _i,ζ_i,h_2i)存在H₂列表中，返回h_2i。

③ H₃(v_i,e_i)查询：

随机选取h_3i∈{0,1}^l，把(v_i,e_i,h_3i)存在H₃列表中，返回h_3i。

④ IBC密钥查询(id_i)：

遍历H_l列表查找(id_i,R_i,A_i,T_i),返回T_i.

⑤ 解签密查询(id_i,C_i=(ζ_i,c_li,c_2i))：

遍历H_l列表查找(id_i,R_i,A_i,T_i)，若T_i≠⊥，执行方案的解签密算法；若T_i=⊥，遍历H₂和H₃列表寻找( $\varpi $ _i,ζ_i,h_2i)和(v_i,e_i,h_3i)，满足c_li=A_i^Tv_i+e_i,c_2i= ${\varpi _i} \oplus $ h_3i。如果这样的三元组不存在，返回⊥并终止。如果这样的三元组存在，而且满足A_se_i=h_2i和 $\left\| {{e_i}} \right\| \leqslant {\sigma _2}\sqrt m $ ，返回 ${\varpi _i}$ 作为解签密的结果。否则，返回⊥并终止。

3) 挑战阶段：阶段1由A宣告终止，同时A选择两个相同长度的明文 ${\varpi _1},{\varpi _2}$ 和接收者身份id^*，将其发送给C。如果id* ≠ id₀，返回⊥并终止。否则，C随机选择ζ^*∈{0,1}ⁿ，c₂^*∈{0,1}ⁿ，c₂^*∈{0,1}^l令c₁^*=c₀，将C^*=(ζ^*,c₀,c₂^*)返回给A。

4) 阶段2：A执行阶段1的操作，除了不能查询id₀的私钥，不能对(id₀,C^*)执行解签密查询。

5) 猜测阶段：A输出对b的猜测b'。

最后，C查询H₃列表寻找(v^*,e^*,h₃^*)，它满足如下条件：存在( ${\varpi ^ * }$ ,ζ^*,h₂^*)在列表H₂中，且满足c₀= A₀^Tv^* + e^*，c₂^*= ${\varpi ^ * } \oplus $ h₃^*，A_se^* =h₂^*和 $\left\| {{e^ * }} \right\| \leqslant {\sigma _2}\sqrt m $ 。如果这样的元组存在，C输出v^*作为LWE问题实例的解。否则，输出⊥并终止。

设E是如下事件：A在游戏中查询了H₃(v^*,e^* )。如果游戏完美地模拟了真实的攻击，E在游戏中发生的概率就和它在真实攻击中发生的概率是一样的。

在真实的攻击中。

Pr[b′ = b]≤Pr[b′ = b |⌉E]Pr[⌉E]+ Pr[E] =Pr[b′ = b |⌉E](1- Pr[E]) + Pr[E] =1/2 +1/2·Pr[E]

因此，ε = |2Pr[b′= b]^-1|≤Pr[E]。

下面考虑游戏不能完美地模拟真实攻击的情况。这实际上是合法的密文在解签密查询中被拒绝的情况。对H₃列表中的每一个(v_i,e_i,h_3i)，存在着唯一的( $\varpi $ _i,ζ_i,h_2i,)与之对应，因此拒绝合法密文的概率不超过Q₂/2^n+l。

此外，id^*=id₀的概率为1/Q₁。所以，ε′≥1/Q₁·ε-(Q₂Q_u)/2_n+1。如果ε是不可忽略的，则ε'也是不可忽略的。这与LWE问题的难解性相矛盾。因此，在LWE问题难解性假设下，能够以不可忽略的概率攻击方案作为类型1异构签密体制的IND-HSC- CCA2安全性的敌手A是不存在的。所以，在LWE问题难解性假设下，方案作为类型1异构签密体制是IND-HSC-CCA2安全的。

定理 2 EUF-HSC-CMA安全性

在ISIS问题难解性假设下，方案作为类型1异构签密体制是EUF-HSC-CMA安全的。

证明：假设存在敌手F以不可忽略的优势ε攻击方案的EUF-HSC-CMA安全性，就会存在挑战者C，他能够借助F的攻击能力来攻击GPV签名方案的EUF-CMA安全性。C和F之间的交互如下。

1) 初始阶段：C获得GPV签名方案的验证公钥A₀∈Z_q^n×m。他运行TrapGen算法生成(A,T)，A为主公钥，T为主私钥。C将A₀和(A,T)发送给F。

2) 攻击阶段：F可以执行多项式有界次数的签密查询，C负责给出合理的应答。在签密查询中，F提交一个接收者的身份id _j和一个消息 $\varpi $ _j给C。C对消息 $\varpi $ _j运行GPV签名查询得,(ζ_j, e_j)。他随机选择v_j∈Z_qⁿ，计算A_j=AH_l(id_j)^-1，c_lj=A_j^Tv_j+e_j和c_2j= ${\varpi _j} \oplus $ H₃(v_j,e_j)，返回C_j=(ζ_j,c_lj,c_2j)给F。

3) 伪造阶段：F提供一个接收者的身份id^*和一个新的合法密文C^*=(ζ^*,c_l^*，c₂^*),返回给C。

C如下操作得到一个新的合法的GPV签名：

1) 计算R^*=H₁(id^*)，运行算法BasisDel (A,T,R^*,σ₁)产生(A^*,T^*)。

2) 输入(A^*,T^*)，对密文C^*(ζ^*,c₁^*,c₂^*)运行解签密算法获得明文 $\varpi $ ^*和相应的e^*，则(ζ^*,e^*)就是对消息 $\varpi $ ^*的合法伪造，即满足A₀e^*=H₂(( $\varpi $ ^*,ζ^*)和 $\left\| {{e^ * }} \right\| \leqslant {\sigma _2}\sqrt m $ 。

由以上过程可以看出，如果F伪造合法密文的概率ε是不可忽略的，则C伪造合法的GPV签名的概率也是不可忽略的。而由文献^[13]，在ISIS问题难解性假设下，GPV签名是EUF-CMA安全的。因此，能够以不可忽略的优势攻击方案的EUF-HSC-CMA安全性的敌手F是不存在的。所以，在ISIS问题难解性假设下，方案是EUF-HSC-CMA安全的。

结合格上签密方案和固定维数的格基代理技术，构造了第一个格上的类型1异构签密方案，第一次实现了抗量子攻击的异构签密。方案使用了随机预言机模型来完成安全性证明，构造标准模型下的量子安全的异构签密，是进一步的研究方向。

本文得到廊坊师范学院博士基金(LSLB201408)的资助，在此表示感谢。