0 引言

现在广泛使用的密码方案，如RSA(Rivest-Shamir-Adleman)、Elgamal、椭圆曲线数字签名算法(Elliptic Curve Digital Signature Algorithm, ECDSA)，容易受到量子计算机的攻击威胁，使用其他密码系统代替现有的公钥密码系统已经非常迫切。在众多的抗量子密码体制中，基于编码的公钥密码体制被认为是最有希望的方案之一。

McEliece公钥密码^[1]是第一个基于编码的公钥密码体制，其安全性依赖于编码学当中的一般译码问题，这是一个NPC(Nondeterministic Polynomial Completeness)问题。与RSA方案相比，该密码体制能抵抗量子计算机攻击而且加解密速度快；但该方案也有很明显的弱点，一是它的公钥量太大，二是其信息率较低，大约只有50%^[2]。

针对原始McEliece体制的弱点，为了推动基于编码密码体制的应用，密码学家在减少McEliece密码的公钥量方面作了很多尝试。一个可行的办法是使用其他的编码代替原始方案中的Goppa码，其中低密度奇偶检验(Low-Density Parity-Check，LDPC)码受到了较多的关注^[3-5]。

随着量子计算机的快速发展，广泛使用的数字签名算法(Digital Signature Algorithm, DSA)签名和RSA签名也变得不安全，目前替代方案较少，例如基于哈希函数的签名。基于编码的签名是另一个能代替DSA签名和RSA签名的抗量子签名方案，目前高效的基于编码的签名方案较少，所以具有较大的研究空间。

2013年，Baldi提出了一个基于LDGM码的签名方案^[6]，在这之前，基于编码的签名方案主要是CFS签名^[7]及其相应的延伸方案。该方案具有易于实现和公钥量低的优点，克服了CFS签名方案的两个弱点：一是难于实现，即对于任意一个哈希值，把它作为一个伴随式不一定能译出相应的错误向量作为数字签名；二是签名的公钥量太大。

然而，Baldi提出的这个签名方案并不是可证明安全的。本文对基于LDGM码签名方案的密钥进行改造，并结合签密理论，提出了一个可证明安全的基于LDGM码的签密方案。安全性分析表明，方案满足随机预言模型下的适应性选择密文攻击下的不可区分性(INDistinguishability under Adaptive Chosen Ciphertext Attacks, IND-CCA2)安全和选择消息攻击下存在性不可伪造(Existential UnForgeability under Chosen Message Attacks, EUF-CMA)安全，并且密文量和公钥量比传统的“先加密后签名”有较大的下降。

1 预备知识

随着量子计算机的快速发展，基于大整数分解的密码体制如RSA和基于离散对数的密码体制如Elgamal的安全性受到了巨大的挑战。而基于编码的密码体制所基于的困难问题是NPC问题，具有抗量子攻击的天然优势。

1.1 困难性假设

线性码的一般译码问题(Genenral Decoding)：

输入：正整数n, k, t；一个二元[n, k]线性码C⊆F₂ⁿ，由其生成矩阵G∈F₂^k×n定义；一个向量c⊆F₂ⁿ。

问题：是否存在一个向量m⊆F₂^k，满足c=mG+e，且w(e)≤t？

伴随式译码问题(Syndrome Decoding)：输入：正整数n, k, t；一个二元[n, k]线性码C⊆F₂ⁿ，由其校验矩阵H∈F₂^r×n定义，其中r=n-k；一个向量s∈F₂^r。

问题：是否存在一个向量e⊆F₂ⁿ，满足He^T=s^T, 并且w(e)≤t？

这是编码问题中两个著名的NPC问题^[8]，基于编码密码体制的安全性可以归约到这两个困难问题上。

1.2 基于LDGM码的签名方案 1.2.1 LDGM码

LDGM码是一类特殊的编码，它和LDPC码有着紧密的联系，它们之间的区别在于LDGM码要求由稀疏的生成矩阵来定义，而对校验矩阵则没有稀疏的要求，LDPC码则刚好相反。LDGM码被应用于通信传输由来已久^[9]，当用于级联码方案时，可以实现很好的纠错能力^[10-11]。

码长为n，维度为k的LDGM码，其生成矩阵的形式为：

$ \boldsymbol{G} = \left[ {{\boldsymbol{I}_k}|\boldsymbol{D}} \right] $

其中：I_k为k×k阶单位矩阵，D是一个稀疏的k×r阶矩阵。按照这种方式定义的LDGM码是系统码，其校验矩阵为：

$ \boldsymbol{H} = \left[ {{\boldsymbol{D}^T}|{\boldsymbol{I}_r}} \right] $

也具备系统码的形式，其中T表示对矩阵的转置，I_r是一个r×r阶的单位矩阵，r=n-k。

LDGM码的生成矩阵G的行重与列重相等，行与列当中元素“1”的个数很小(稀疏性要求)，并且任意两行或列之间对应位相同的“1”的个数不超过1(行列约束条件)。其生成矩阵G的行是k个长度为n，Hamming重量w_g < < n的线性无关的向量。

1.2.2 基于LDGM码的签名方案

Baldi等^[6]提出了第一个基于LDGM码的数字签名方案。该数字签名方案基于一个事实，即对于任意一个r维向量s，在一个系统码中，把它作为一个伴随式，总能找到一个错误向量与之相对应。这是因为系统码的校验矩阵总能写成系统的形式，即H=[P|I]。其中P是一个r×k阶矩阵，I是一个r维单位矩阵，所以任意的伴随式s可以利用H与错误向量e_s相乘得到，即He_s^T=s，其中e_s=[0_1×k|s^T]，0_1×k是一个k维零向量。

基于这个结论，文献[6]中的签名方案如下：

1) 选择一个公开的哈希函数，h:{0, 1}^*→F₂^r，将任意长度的消息m转化为一个r维向量s。

2) 签名者选择一个秘密的LDGM码C(n, k)，通过其稀疏矩阵G_k×n来定义，并计算出其相应的校验矩阵H。

3)  签名者选择两个可逆矩阵Q和S，其阶分别为r×r和n×n。H、Q和S均为私钥，其公钥为H′=Q^-1HS^-1。

4) 计算出s′=Qs，由于H是系统形式的，因此签名者很容易找到其相应的错误向量，设为e，满足He^T=s′。

5) 签名者随机选择码字c∈C，最终，得到签名:e′=(e+c)S^T。

6) 验证者计算H′e′^T=Q^-1HS^-1·S·(e^T+c^T)=Q^-1H·(e^T+c^T)=Q^-1He^T=Q^-1s′=s，将H′e′^T与h(m)作对比，若相等，则接受此消息，否则拒绝此消息。

该签名算法能克服CFS签名算法实现困难、公钥量大的缺点，同时又保留了基于编码密码系统的安全性，是抗量子密码系统的一个重大突破。

1.3 基于LDGM码签密的定义与安全模型

定义1  对于指定的安全参数1^k，一个签密算法包含以下3个步骤：

密钥生成(K_g): (pk, sk)←K_g(1^k)，使用安全参数k生成相应的公私钥对(pk, sk)。

签密(SC)：σ←SC(1^k, m, sk_S, pk_R)，一个概率多项式时间(Probabilistic Polynomial Time, PPT)算法，输入安全参数k.，消息m∈M，发送者私钥sk_S，接收者公钥pk_R，输出签密文。

解签密(De_SC)： ((m, s), Accept)/Reject←De_SC(1^k, σ, sk_R, pk_S)，包含以下两个阶段。

阶段1  输入k、签密文σ、sk_R，进行解签密，得到被签名的消息m，可验证的签名s(从σ中提取出来)。

阶段2  输入阶段1中得到的m和σ，用发送方公钥pk_S进行验证，输出Accept或者Reject。

基于LDGM码的签密方案的安全模型由机密性攻击游戏和不可伪造性攻击游戏组成。

定义2  机密性。如果不存在能以不可忽略的优势赢得以下游戏的PPT敌手$\mathscr{A}$，则一个签密方案在适应性选择密文攻击下具有不可区分性(IND-CCA2)： 1) 挑战者运行K_g生成一对密钥(sk_U，pk_U)，sk_U作为私钥，而将pk_U作为公钥发送给敌手$\mathscr{A}$，对于其他的用户U′，挑战者运行K_g算法生成相应的公私钥对(sk_U′, pk_U′)，并将它发送给敌手。

2) $\mathscr{A}$对以下的预言机进行多项式次数的访问：

签密预言机：$\mathscr{A}$选择一个消息m∈M和一个用户的公钥pk_R，访问签密预言机(由挑战者充当)以求得SC(m, sk_U, pk_R)。如果pk_R≠pk_U且pk_R是有效的，则返回相应的结果，否则输出错误符号“⊥”。

解签密预言机：$\mathscr{A}$产生一个签密文σ，并且访问预言机以求得De_SC(σ, sk_U, pk_S)的结果。如果解签密成功，并且签名和发送者的公钥是相对应的，则返回相应消息，否则输出错误符号“⊥”。

3) $\mathscr{A}$产生两个相同长度的明文(m₀, m₁)∈M，以及一个有效的私钥sk_S。挑战者选择一个随机数$b\xleftarrow{R}\left\{ {0,1} \right\}$并且计算签密文σ^*=SC(m_b, sk_S, pk_U)，将其发送给挑战者作为一个挑战密文。

4) $\mathscr{A}$对解签密预言机进行访问，但是不能询问σ^*的信息。

5) 最后，$\mathscr{A}$输出一比特b′，如果b′=b则敌手赢得游戏。$\mathscr{A}$的优势定义为$Ad{v^{ind - cca}}\left( A \right) = \Pr \left[ {b = b'} \right] - \frac{1}{2}$，b′=b的概率就是$\mathscr{A}$赢得游戏的概率。

定义3   不可伪造性。如果不存在PPT算法$\mathscr{F}$能以不可忽略的概率赢得以下挑战游戏，则称该签密方案在选择消息攻击下满足存在性不可伪造性(EUF-CMA)。

1) 前两步与机密性游戏类似。

2) 伪造算法$\mathscr{F}$产生一个签密文σ和一个有效的公私钥对(sk_R, pk_R)，如果满足以下条件，则赢得游戏：

①De_SC(σ, sk_R, pk_U)返回一个元组(m, s)，在用验证密钥pk_U对该元组进行验证时，它可以通过验证；

②σ不是签密预言机的输出。

2 基于LDGM码的签密方案

借鉴“一石二鸟”方案^[12]的设计思想，使用共用随机数的方法，提出本文的基于LDGM码的签密方案。

2.1 参数选择

安全参数设为($\mathscr{K}$)，使用以下的参数：

1) 选取一个[n, k, 2t+1]的二元LDGM码，其中n, k由安全参数$\mathscr{K}$决定，$t = \frac{{n - k}}{{1bn}}$。

2) 定义n′=n-k+1。

3) 抗碰撞的哈希函数$\mathscr{H}$:F₂^n′×n×F₂^n′×F₂ⁿ→{0, 1}^l和$\mathscr{G}$:F₂ⁿ×{0, 1}ⁿ×F₂^n′×n×F₂^n′×n→F₂^n′。

2.2 密钥生成

对于用户U，密钥生成包含以下步骤：

1) 选取二元(n, k, t)LDGM码生成矩阵G_k×n，并计算出相应的校验矩阵H_(n-k)×n。

2) 随机选取一个n×n阶置换矩阵P_U。

3) 选取b_U∈_R F₂ⁿ。

4) 随机选取H′_U∈F₂^(n-k)×n′，Q′_U∈F₂^n′×(n-k), Q′_U是满秩的，然后计算Q_U=H′_UQ′_U。

5) 选取一个向量a_U，使得H′_Ua_U^T=0。

6) 计算公钥${\boldsymbol{\tilde H}_u}$=Q′_UH_UP_U+a_U^Tb_U。${\boldsymbol{\tilde H}_u}$是一个n′×n阶矩阵。

私钥：H_U, P_U, Q_U, H′_U；公钥：${\boldsymbol{\tilde H}_u}$。

2.3 签密和解签密

SC(m, H_S, P_S, Q_S, H′_S, ${\boldsymbol{\tilde H}_R}$)：

对一个消息m∈{0, 1}ⁿ进行签密，发送方记为S，接收方记为R。

$\boldsymbol{r}\xleftarrow{R}F_2^n$且w(r)≤t；

m′₁←$\mathscr{G}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)；

m₁←H′_Sm₁^T；

s₁←P_S^TDecode_HS(Q_S^-1m₁^T)；

由于H_S是一个具有系统形式的LDGM码，因此，对于任意的Q_s^-1m₁，总能译码相应的错误向量，不需要进行重复的尝试，且有m′₁=H′_Ss₁^T。

U←${\boldsymbol{\tilde H}_R}$r^T；

V←m⊕$\mathscr{H}$(${\boldsymbol{\tilde H}_R}$, U, r)；

发送签密文σ=(U, V, s₁)。

De_SC(σ, H_R, P_R, Q_R, H′_R, ${\boldsymbol{\tilde H}_S}$)：

收到签密文之后，接收方R进行如下的操作：

U′←H′_RU^T；

r′←P_R^TDecode_HR(Q_R^-1U′^T)；

如果U≠${\boldsymbol{\tilde H}_R}$r′^T或w(s₁)>t，返回Reject；否则，m′←V⊕$\mathscr{H}$(${\boldsymbol{\tilde H}_R}$, U, r′)。

如果${\boldsymbol{\tilde H}_S}$s₁^T≠$\mathscr{G}$(r′, m′, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)，返回Reject，否则，返回明文m′。

2.4 正确性验证

签密方案的验证思路是先用接收方的私钥解密出明文，再用发送方的公钥进行数据完整性认证。

1) 先验证m′₁=${\boldsymbol{\tilde H}_S}$s₁^T。

首先由s₁^T←P_S^TDecode_HS(Q_s^-1m₁^T)，可得Q_SH_SP_Ss₁^T=H′_Sm′₁^T; 对于m′₁=${\boldsymbol{\tilde H}_S}$s₁^T，两边同时左乘H′_S, 可得H′_S(Q′_SH_S P_S⊕a^Tb)s₁^T=H′_Sm′₁^T，这就是要验证的等式：

H′_S(Q′_SH_SP_S⊕a^Tb)s₁^T=(H′_SQ′_SH_SP_S⊕a^Tb)s₁^T=Q_SH_SP_Ss₁^T⊕H′_Sa^Tb s₁^T=Q_SH_SP_Ss₁^T(H′_Sa^T=0)=H′_Sm′₁^T    证毕。

2) 收到签密文后，先解密出随机向量r′，而后验证如果r′=r，则有U^T=′${\boldsymbol{\tilde H}_R}$r′^T。由U′←H′_RU^T和r′←P_R^T Decode_HR(Q_R^-1U′^T)，可得H_RP_Rr′^T=Q_R^-1H′_RU^T。如果U^T=${\boldsymbol{\tilde H}_R}$r′^T，则等价于Q_R^-1H′_RU^T=Q_R^-1H′${\boldsymbol{\tilde H}_R}$_Rr′^T, 而:

Q_R^-1H′_R${\boldsymbol{\tilde H}_R}$r′^T=Q_R^-1H′_R(Q′_RH_RP_R⊕a^Tb)r′^T=Q_R^-1(Q_RH_RP_R⊕H′_Ra^Tb)r′^T=(EH_RP_R⊕Q_R^-10b)r′^T=H_RP_Rr′^T

即如果U^T=${\boldsymbol{\tilde H}_R}$r′^T，则等价于H_RP_Rr′^T=Q_R^-1H′_RU^T成立，而上面已经证明这等式是成立的。    证毕。

3) 在解密出随机向量r′之后，就要可以利用公开的哈希函数进行简单的异或运算解密出明文m′，再验证${\boldsymbol{\tilde H}_S}$s₁^T=$\mathscr{G}$(r′, m′, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)。而根据签密过程可知$\mathscr{G}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)=m′₁，由1)可知m′₁=${\boldsymbol{\tilde H}_S}$s₁^T，如果m′=m，r=r′，则$\mathscr{G}$(r′, m′, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)=$\mathscr{G}$(r′, m′, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)=${\boldsymbol{\tilde H}_S}$s₁^T    证毕。

3 安全性证明

本方案的安全性证明以定义2和定义3所给出的安全模型为基础，并在随机预言机下进行证明。

定理1  机密性。如果伴随式译码(Syndrome Decoding, SD)是困难的，则在随机预言机模型下，本方案在适应性选择密文攻击下具有不可区分性，即能够满足IND-CCA2安全。

证明  通过一系列的挑战游戏Game0, Game1, …, 构造一个挑战者$\mathscr{C}$，以此进行证明。

用${q_{\mathscr{H}}}$, ${q_{\mathscr{G}}}$, ${q_{\mathscr{s}}}$, ${q_{\mathscr{u}}}$分别表示敌手$\mathscr{A}$访问$\mathscr{H}$预言机，$\mathscr{G}$预言机，签密预言机和解签密预言机的最大次数。需要证明敌手$\mathscr{A}$赢得游戏的优势，受到在随机预言机模型之下解决SD问题的优势的限制。

为了应对敌手对四个预言机的访问，建立四张表${\mathscr{G}^{{\text{list}}}}$, ${\mathscr{H}^{{\text{list}}}}$, σ^list和Λ。如果表中没有数值，则输出“⊥”。

1) ${\mathscr{G}^{{\text{list}}}}$包含一个元组((x, s), a)，由(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)索引得到。

2) ${\mathscr{H}^{{\text{list}}}}$由0, 1字符串ρ∈{0, 1}^l组成，由(${\boldsymbol{\tilde H}_R}$, U, r)索引得到，其中${\boldsymbol{\tilde H}_R}$和${\boldsymbol{\tilde H}_S}$是(n-k)×n阶的LDGM码的校验矩阵，U∈F₂^n-k，r∈F₂ⁿ，且w(r)≤t。

3) σ^list包含形如(m, σ=(U, V, s))的条目。

4) 表Λ包含的是特定随机向量r的目录，这些随机向量与(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)一一对应，相应的r记为r=Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)，应满足$\mathscr{G}$(m, Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$), ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)是可译码的伴随式。

Game0  这是标准的IND-CCA2挑战游戏。通过运行方案中的密钥生成算法，生成私钥(Q_U, H_U, P_U, H′_U), 其中H_U←LDGM(n, t)，公钥为${\boldsymbol{\tilde H}_U}$=Q′_UH_UP_U⊕a_Ub_U^T。将${\boldsymbol{\tilde H}_U}$发送给敌手$\mathscr{A}$，$\mathscr{A}$能够访问$\mathscr{H}$预言机和$\mathscr{G}$预言机。签密预言机和解签密预言机的功能如方案所述。以X₀表示$\mathscr{A}$赢得Game0的事件。可见在提出的方案中，Game0能够完美地运行IND-CCA2挑战游戏，$\Pr \left[ {{X_0}} \right] - 1/2 = Adv_{\mathscr{A}}^{ind - cca}\left( {n,k} \right)$。

Game1  在这个游戏中，对哈希预言机$\mathscr{G}$和$\mathscr{H}$进行模拟。两个预言机的模拟如下。

对于$\mathscr{G}$预言机形如(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)的访问，分为两种情况，取决于r=Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)是否成立。对预言机的模拟如下所示：

输入：一个元组(m, r, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)。

输出：一个伴随式x。

if r≠Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)then

    if s₁≠⊥then

        ${\boldsymbol{s}_1}\xleftarrow{R}F_2^n$

        x←${\boldsymbol{\tilde H}_S}$s₁^T

        ${\mathscr{G}^{{\text{list}}}}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)←((x, ⊥), s₁)

    end

    return $\mathscr{G}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)=x

else

    if x=⊥then

        ${s_1}\xleftarrow{R}F_2^n$, w(s₁)=t

        x←${\boldsymbol{\tilde H}_S}$s₁^T

        ${\mathscr{G}^{{\text{list}}}}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)←((x, s₁), s₁)

    end

    return $\mathscr{G}$(r, m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_S}$)=x

end

对于预言机$\mathscr{H}$形如(${\boldsymbol{\tilde H}_R}$, U, r)的访问，挑战者在H^list当中搜寻(${\boldsymbol{\tilde H}_R}$, U, r)的值。如果找到，则从列表中返回相应的值；否则返回一个随机字符串$\rho \xleftarrow{R}{\left\{ {0,1} \right\}^l}$，并且在${\mathscr{H}^{{\text{list}}}}$当中记录元组((${\boldsymbol{\tilde H}_R}$, U, r), ρ)。用X₁代表事件$\mathscr{A}$赢得Game1。当在Game1中模拟这两个预言机时，预言机的输出分布和Game0保持不变(即保持随机性)。因此Pr[X₁]=Pr[X₀]。

Game2  模拟签密预言机，过程如下：

输入：元组(m, ${\boldsymbol{\tilde H}_R}$, H_U)。

输出：一个签密文σ=(U, V, s₁)。

if Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$)=⊥then

    $r\xleftarrow{R}F_2^n$, w(t)≤t，Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$)←⊥

end

((x, s₁), s₁)←$\mathscr{G}$(Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$), m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$)

if (s₁=⊥) then abort

else

    r←Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$)，Λ(m, ${\boldsymbol{\tilde H}_R}$, ${\boldsymbol{\tilde H}_U}$)←⊥，U=${\boldsymbol{\tilde H}_R}$r^T

    V=m⊕$\mathscr{H}$(${\boldsymbol{\tilde H}_R}$, U, r)

end

Return σ=(U, V, s₁)。

s₁其实是在公钥${\boldsymbol{\tilde H}_U}$之下对消息m的签名，因此，可得$\left| {\Pr \left[ {{X_1}} \right] - \Pr \left\{ {{X_2}} \right\}} \right| \leqslant \frac{{{q_s}}}{{\left( {\begin{array}{*{20}{c}} n \\ t \end{array}} \right)}}$，其中X₂表示A赢得本游戏。

Game3  模拟解签密预言机。对(s₁, U, V, ${\boldsymbol{\tilde H}_U}$, ${\boldsymbol{\tilde H}_S}$)进行询问，过程如下：

1) 挑战者在表${\mathscr{H}^{{\text{list}}}}$中搜寻使得${\boldsymbol{\tilde H}_U}$λ^T=U成立的元组(${\boldsymbol{\tilde H}_U}$, U, λ)。如果找到，则输出相应的向量X。如果不存在，则令λ=⊥, 并从哈希预言机中给出相应的输出作为X。

2) m′←V⊕X。

3) 挑战者在表${\mathscr{G}^{{\text{list}}}}$中搜寻使得${\boldsymbol{\tilde H}_U}$λ^T=U或λ=⊥成立的元组。如果这样的元组没有找到，则将其添加到列表中。

4) 挑战者验证${\boldsymbol{\tilde H}_U}$s₁^T$\underline{\underline ?} $$\mathscr{G}$(λ₁, m′, ${\boldsymbol{\tilde H}_U}$, ${\boldsymbol{\tilde H}_S}$)。如果成立且${\boldsymbol{\tilde H}_U}$λ^T=U，则挑战者返回m′。如果成立但λ=⊥，则引用失败，挑战者终止提供服务。如果所有条件都不成立，则挑战者返回“⊥”作为拒绝无效签密文的信号。

在上述的游戏中，如果挑战者终止服务，则表明敌手伪造了一个签密文并且没有对哈希预言机进行询问。因此，挑战者终止服务的概率为q_d/2^l。这个情况不会在Game2中出现。因此，对于事件X₃，可以得到：

$ \left| {\Pr \left[ {{X_3}} \right] - \Pr \left\{ {{X_2}} \right\}} \right| \leqslant {q_d}/{2^l} $

Game4  挑战密钥生成算法。敌手可以获得除了U之外所有用户的私钥。因此，对于其他的用户，密钥生成如方案所示，并将其传送给敌手。对于用户U，$\mathscr{C}$选择私钥H_U=R。公钥为${\boldsymbol{\tilde H}_U}$=R′，其中R′^T=[R^T|z^T]。把验证密钥${\boldsymbol{\tilde H}_U}$发送给敌手$\mathscr{A}$。可以得到：

$ \left| {\Pr \left[ {{X_3}} \right] - \Pr \left\{ {{X_4}} \right\}} \right| \leqslant negl\left( n \right) $

其中X₄表示$\mathscr{A}$赢得Game4。

Game5  挑战密文。挑战者选取消息m_b，按照如下操作进行挑战，这有助于敌手破解SD问题的实例。挑战者希望找到r∈F₂ⁿ，且w(r)≤t，使得Rr^T=Rs^T。挑战者生成挑战密文：

1) $\mathscr{C}$选择U^*=s′，其中s′^T=[s^T|s_c]，s_c是随机生成的一个比特。

2) 敌手询问$\mathscr{H}$，$\mathscr{C}$选择一个特殊的符号Δ，随机生成一个向量y并将其记录在${\mathscr{H}^{{\text{list}}}}$之中。对于敌手询问$\mathscr{G}$，$\mathscr{C}$再次使用Δ，同时给出一个可译码的伴随式，并记录在${\mathscr{G}^{{\text{list}}}}$当中。

3) 挑战者$\mathscr{C}$置V=m_b⊕y。

同样地，挑战者需要通过以下的方式来改变对哈希函数询问的应答:

1) 对$\mathscr{H}$预言机，询问(${\boldsymbol{\tilde H}_U}$, ${\boldsymbol{\tilde H}_U}$s^T, r)，当${\boldsymbol{\tilde H}_U}$r^T≠${\boldsymbol{\tilde H}_U}$s^T时，返回一个随机值。如果${\boldsymbol{\tilde H}_U}$r^T=U^*，且w(r)≤t，则返回y的值，并用r代替元组当中的Δ。

2) 对$\mathscr{G}$预言机，询问(m, r, ${\boldsymbol{\tilde H}_U}$, ${\boldsymbol{\tilde H}_S}$)，当${\boldsymbol{\tilde H}_U}$r^T=U^*且m=m_b时输出x，否则输出随机的伴随式。

如果用X₅表示敌手$\mathscr{A}$赢得Game5，可得对于R，一个PPT敌手解决一个伴随式译码问题(SD)实例的优势Adv_C^SD(n, k)满足|Pr[X₄]-Pr[X₅]|≤Adv_C^SD(n, k)。

Game6  挑战密文。在这个游戏中，挑战者$\mathscr{C}$再次改变生成密文的方法。对于密文，生成U和s的过程与以前的游戏是一样的，但是更改生成V的方法。挑战者$\mathscr{C}$令V=z，其中$z\xleftarrow{R}{\left\{ {0,1} \right\}^l}$。至此，挑战密文的生成都是完全随机的。但是，在Game5中，密文生成是随机的，因为我们使用一个随机向量对消息进行盲化处理。因此，密文空间的分布并没有发生改变，即Pr[X₅]=Pr[X₆]，X₆表示敌手赢得Game6这个事件。因此，敌手猜测出比特b取值的概率是Pr[X₆]=1/2。

综上所述，$Ad{v^{ind - cca2}}\left( {\mathscr{A}} \right) \leqslant \frac{{{q_s}}}{{\left( {\begin{array}{*{20}{c}} n \\ t \end{array}} \right)}} + \frac{{{q_d}}}{{{2_t}}} + \frac{{Adv_c^{SD}}}{2}$，也就是说敌手破解机密性的优势受到了伴随式译码问题的限制，方案满足IND-CCA2安全。

定理2  不可伪造性。如果伴随式译码问题是NPC问题，则在随机预言机模型下，基于LDGM码的签密方案可归约到SD问题，在适应性选择消息攻击下满足不可伪造性(即满足EUF-CMA安全)。

证明  同样通过构造攻击游戏来证明不可伪造性。用${q_{\mathscr{G}}}$，q_s分别表敌手访问$\mathscr{G}$预言机和签密预言机的最大次数。我们将要证明敌手伪造签密文的优势相当于给定一个随机线性码，解决伴随式译码问题。

为了记录哈希询问和签名询问，建立列表${\mathscr{G}^{{\text{list}}}}$、σ^list、t和Λ。如果列表中没有相应的值，则输出“⊥”。

1) ${\mathscr{G}^{{\text{list}}}}$包含元组((x, s), a)，由(r, m)索引得到。

2) 签名列表σ^list包含形如(m, σ=(s, r))的记录。

3) 表Λ包含的是特定随机向量r的目录，这些随机向量与(m, r)一一对应，相应的r记为r=Λ(m)，应满足$\mathscr{G}$(m, Λ(m))是可译码的伴随式。

Game0  挑战者根据EUF-CMA游戏来运行实际的方案。公私钥对通过运行密钥生成算法取得，私钥(Q_S, H_S, P_S, H′_S)，其中H←LDGM(n, k)，公钥${\boldsymbol{\tilde H}_S}$=Q′_SH_SP_S⊕a^Tb，将公钥_S发送给敌手$\mathscr{F}$。$\mathscr{F}$可以访问哈希预言机$\mathscr{G}$。签密预言机如机密性证明描述所示。记Pr=[X₀]Succ^euf-cms($\mathscr{F}$)。

Game1  模拟哈希预言机。在这个游戏中，模拟预言机$\mathscr{G}$。

对$\mathscr{G}$询问元组(m, r)，有两种情况，取决于r∈Λ(m)是否成立：

输入：一个元组(m, r)。

输出：一个伴随式x。

if r≠Λ(m) then

    if s=⊥ then

        ${\boldsymbol{s}_1}\xleftarrow{R}F_2^n$

        x←${\boldsymbol{\tilde H}_S}$s₁^T

        s←⊥ ${\mathscr{G}^{{\text{list}}}}$(m, r)←((x, s), s₁)

    end

    return $\mathscr{G}$(m, r)=x

else

    if x=⊥then

        $\boldsymbol{s}\xleftarrow{R}F_2^n$, w(t)=t

        x←${\boldsymbol{\tilde H}_S}$s₁^T

        s←s₁，${\mathscr{G}^{{\text{list}}}}$(m, r)←((x, s), s₁)

    end

    return $\mathscr{G}$(m, r)=x

end

当在Game1中模拟预言机时，预言机输出的分布和Game1中的输出分布相同。因此Pr[X₁]=Pr[X₀]。

Game2  模拟签名预言机。签密预言机的模拟如下：

输入：长为l的消息m。

输出：一个签名σ=(s₁, r)。

if Λ(m)=⊥ then

    $r\xleftarrow{R}F_2^n$

    Λ(m)←r

end

((x, s₁), s₁)←$\mathscr{G}$(m, Λ(m))

if (s₁=⊥) then abort

else

r←Λ(m)

Λ(m)←⊥

return σ=(s₁, r)

根据验证算法，由签名预言机生成的签名是有效的，因此满足${\boldsymbol{\tilde H}_S}$s₁^T=$\mathscr{G}$(m, r), w(s₁)≤t。

在游戏2中，当访问到某些r被赋值为Λ(m)的元组(m, r)时，会发生碰撞，这种事件发生的概率为q_S/2ⁿ。用X₂表示敌手$\mathscr{F}$赢得该游戏，则Pr[X₁]-Pr[X₂]≤q_S/2ⁿ。

Game3  改变密钥生成算法。将伴随式译码问题需要求解的校验矩阵R，作为私钥即H=R。公钥是${\boldsymbol{\tilde H}}$=R′，其中R′^T=[R^T|z^T]，z∈_R F₂ⁿ。将验证密钥发送给敌手$\mathscr{F}$，挑战者$\mathscr{C}$保持其余的私钥不变。

Game4  在这个游戏中，挑战者改变赢得游戏的条件。挑战者首先选择$c\xleftarrow{R}\left\{ {1,2, \cdots ,qs + {q_{\mathscr{G}}} + 1} \right\}$。除了满足上述条件之外(前面游戏给出的条件)，如果在对预言机$\mathscr{G}$进行第c次询问时，成功进行了伪造，则$\mathscr{F}$赢得了游戏。这种情况发生的概率为1/(q_S+${q_{\mathscr{G}}}$+1)。用X₄表示$\mathscr{F}$赢得Game4，则：

$ \Pr \left[ {{X_4}} \right] = \frac{{\Pr \left[ {{X_3}} \right]}}{{{q_s} + {q_{\mathscr{G}}} + 1}}. $

Game5  在这个游戏中，挑战者更改随机预言机，为了在第c次询问时获得一个随机伴随式c′=R′s^T(w(s)≥t)。用X₅表示敌手$\mathscr{F}$赢得本游戏，由于哈希预言机的输出分布和游戏4中的输出分布一样，因此，Pr[X₅]=Pr[X₄]。用s^*表示伪造者输出的签名。可见s^*是对应于Rs^T的伴随式，有Pr[X₅]≤Adv_C^SD(n, k)。

综合以上5个攻击游戏，可得：

$ Suc{c^{{\text{euf}} - {\text{cma}}}}\left( {\mathscr{F}} \right) \leqslant {q_s}/{2^n} + \left( {qs + {q_{\mathscr{G}}} + 1} \right)Adv_C^{SD}\left( {n,k} \right). $

因此，敌手伪造签名的概率受到挑战者求解伴随式译码问题的限制，这意味着只要相应的伴随式译码问题是难以求解的，签名是不可伪造的，即满足EUF-CMA安全。

4 效率分析

本方案使用低密度生成矩阵码(LDGM)进行签名，能同时保证消息的机密性和完整性，比传统的先签名后加密的方法效率更高。签密方案的设计主要在于其中的签名部分，本方案的签名部分使用的是LDGM码，与使用Goppa码的CFS签名相比，可以直接译码，不需要多次尝试即可译出相应的错误向量作为签名；而且密钥量得到了很大的降低，签密在保证机密性和可认证性方面使用的是相同的一个密钥对，可以减少先签名后加密带来的密钥量增加。

1) 签名计算复杂度。

签名的基本思路是将明文的哈希值当作一个伴随式(校验子)，对其进行译码，找出相对应的错误向量，将其作为签名。由于CFS签名方案使用的是Goppa码，因此平均需要进行t!次译码尝试，才能找到可译码的伴随式，而本签名方案使用基于LDGM码的签名算法，对任意的伴随式都可以直接译出相对应的错误向量，因此，仅需进行1次译码操作。

2) 数据量。

在CFS签名方案中，为了使伪造攻击的计算复杂度达到O(2⁸⁰)，需要使用的Goppa码码长为n=2²¹，校验位r=21×10=210，于是每位用户的公钥量为1 152 KB^[6]；而在本方案中，为了达到相同的安全级别，每位用户所需要的公钥的公钥量为117 KB^[6]。因此，本方案的数据量大大减少。

目前在基于编码的密码体系中，为了同时保证消息机密性和完整性，所使用的是先签名后加密的方法，即先使用CFS签名再使用McEliece加密。表 1是就数据量进行比较的结果。

就签密和解签密运算量，与“一石二鸟”方案^[12]和SCS方案^[13]进行对比，其中，E为模指数运算，H为哈希函数运算，S为对称加(解)密运算，M为矩阵乘运算，D为快速译码算法运算，r为“一石二鸟”方案选取的参数，方案的比较结果如表 2所示。

上述方案中，哈希运算的计算量很小，运算量主要集中在模指数运算、对称加解密和矩阵乘法运算上。在计算机上，矩阵运算速度要远远高于模幂运算。若选取(524，1 024)的矩阵，幂为16、模为1 024 b的模指数，矩阵乘法运算量约为模指数的1/47。因此，本方案比“一石二鸟”和SCS方案^[13]计算效率更高。

5 结语

基于编码的公钥密钥具有抗量子攻击的特性，量子计算机的快速发展使它备受关注。本文的基于LDGM码的签密方案是在随机预言机模型下构造的，计算机复杂度和数据量有大幅度的降低。但是，设计出标准模型下可证明安全的方案是运用方案的必要条件。并且，基于编码的密码体制将信道编码和加密紧密结合在一起，与通信技术有本质的联系，如何在标准模型下设计可证明安全的签密方案，并应用到移动智能设备上是值得研究的课题。