签密方案(Signcryption Scheme, SC)^[1]是一个逻辑步骤内同时实现数字签名和公钥加密功能的非对称密码协议，其在有效提高签名和加密效率的同时，还能够提供保密性、认证性和完整性等安全性保障，是公钥密码体制下确保网络环境中多方通信安全的重要密码技术。

混合签密方案(Hybrid Signcryption Scheme, HSC)是在传统签密方案的基础上，通过引入对称加密体制的协议构件来进一步提升了协议的计算效率，从而解决了传统签密方案在长明文通信时效率不佳的问题^[2]。得益于此优势，近年所提出的签密方案^[3-8]实质均为混合签密方案。为了方便实例化混合签密方案，BJØRSTAD和DENT^[9]提出了带标签的签密密钥封装机制(Signcrytion tag Key Encapsulation Mechanism, SC-tag-KEM)，可通过“带标签的签密密钥封装机制+被动安全对称加密机制”(SC-tag-KEM+DEM)的构造来实例化混合签密方案。

混合签密方案的完整内部安全^[10]是指在多方内部安全模型下，混合签密方案同时达到适应性选择密文不可区分性(IND-CCA2)安全和选择报文攻击强存在性不可伪造(SUF-CMA)安全。当前，许多研究致力于实现完整内部安全的混合签密方案^{[3-4, 11]}。2013年，LI等^[11]基于签名后加密提出了一种签密方案，并声称其达到了完整内部安全，但实质上由于其未完整重用随机数，可通过解密后选取新鲜随机数重新加密的方式攻击其SUF-CMA安全，因此该方案并不具备完整内部安全。2014年，LU等^[12]基于文献[11]实现了混合签密方案，但认证性上仅达到了存在性不可伪造(EUF-CMA)安全，未达到完整内部安全。2018年，GÉRARD和MERCKX^[8]提出了基于格密码的后量子安全混合签密方案(SETLA)，但在加密算法设计上，误差分布的定义参数及误差参数均远超出既定限制范围，因此该协议不具备正确性。为解决上述正确性问题，刘镇等^[13]放弃了随机数重用方式，提出了一种签名后加密的签密方案，但该方案仅能达到EUF-CMA安全，同样不具备完整内部安全。2019年，YANG等^[14]提出了标准模型下的高效混合签密方案，但该方案的安全性仅达到了多方内部的IND-CCA2和EUF-CMA安全，无法达到完整内部安全。

为解决上述问题，本文主要基于SC-tag-KEM的通用构造，展开对完整内部安全的混合签密方案的相关研究。首先，提出了一种带标签的签密密钥封装机制(SC-tag-KEM)的通用构造方案(SCtK_std)，该方案通过数字签名构件绑定标签与密钥封装报文，进一步将得到的签名和临时密钥通过消息认证码进行外部信息绑定，从而在标准模型下可证明达到完整内部安全。然后，将SCtK_std方案应用在“SC-tag-KEM+DEM”的通用构造中，提出了可达完整内部安全的混合签密的通用构造方案(HSC_std)，并对其进行了安全性分析。

1.   预备知识

下面对本文的符号进行说明，并列举方案构造以及分析中使用到的密码学原语。

1.1   符号说明

对于函数negl(n)，如果对于任意的正多项式p(·)，皆存在正整数N，使得对于任意的λ>N, 皆有negl(n) < 1/p(λ), 则称negl(n)是可忽略函数。

对任意概率性多项式时间算法$\mathcal{A}$，a←$\mathcal{A}$(b)表示概率性多项式时间算法$\mathcal{A}$以元素b为输入，输出元素a。若$\mathcal{A}$为确定性多项式时间算法，则记为a=$\mathcal{A}$(b)。

对任意的集合$\mathcal{S}$，s←$\mathcal{S}$表示元素s随机抽取自集合$\mathcal{S}$的均匀分布；若D是在集合$\mathcal{S}$上的概率性分布，s←D则表示根据分布D，从集合$\mathcal{S}$中抽样一个元素s。

1.2   密钥封装机制

密钥封装机制(Key Encapsulation Mechanism, KEM)由以下4个算法构成：

(1) KEMSetup(1^λ)→prm：该算法以安全参数λ为输入，输出公共参数prm。

(2) KEMKeyGen(prm)→(pk, sk)：该算法以公共参数prm为输入，输出用户的公私密钥(pk, sk)。

(3) KEMEncap(prm, pk)→(K, C)：该算法输入公共参数prm和用户公钥pk，输出临时随机密钥K和对应该密钥的密钥封装报文C。

(4) KEMDecap(prm, sk, C)→K or ⊥：该算法输入公共参数prm、用户私钥sk和密钥封装报文C，输出密钥K或错误信息⊥。

称密钥封装机制KEM有正确性，当且仅当对prm←KEMSetup(1^λ)和任意(pk, sk)←KEMKeyGen(prm)、(K, C)←KEMEncap(prm, pk)，K=KEMDecap(prm, sk, C)以(1-negl(λ))的概率成立。

KEM的IND-CCA2安全则考虑由挑战者$\mathcal{C}$与攻击者$\mathcal{A}$按以下步骤进行安全游戏：

(1) 设置阶段：挑战者$\mathcal{C}$生成prm←KEMSetup(1^λ)，(pk, sk)←KEMKeyGen (pk, sk)，(K₀, C^*)←KEMEn-cap(prm, pk)，并且令K₁←$\mathcal{K}$_KEM，其中$\mathcal{K}$_KEM为临时密钥空间。随后，挑战者$\mathcal{C}$随机抛币b←{0, 1}，并返回(prm, pk, K_b, C^*)给攻击者$\mathcal{A}$，保留私钥sk。

(2) 查询阶段：攻击者$\mathcal{A}$向挑战者$\mathcal{C}$发起适应性选择密文查询C≠C^*；挑战者$\mathcal{C}$接收到查询密文C≠C^*后，调用KEMDecap (prm, sk, C)→K′ or ⊥，并将结果返回给攻击者$\mathcal{A}$。

(3) 猜测阶段：攻击者$\mathcal{A}$输出b′∈{0, 1}。若b′=b，则称攻击者$\mathcal{A}$获得游戏胜利。

定义1^[15]   (KEM的IND-CCA2安全)称密钥封装机制KEM具备IND-CCA2安全，当且仅当对任意的概率性多项式时间攻击者$\mathcal{A}$，在KEM的协议环境下执行KEM的IND-CCA2安全游戏，获得游戏胜利的优势概率为：

且该优势概率关于安全参数λ可忽略。

1.3   数字签名

数字签名方案(SignatureScheme, SIG)由以下4个算法构成：

(1) SIGSetup(1^λ)→prm：该算法以安全参数λ为输入，输出公共参数prm。

(2) SIGKeyGen (prm) → (pk, sk)：该算法以公共参数prm为输入，输出用户的公私密钥(pk, sk)。

(3) SIGSign (prm, sk, m)→σ：该算法输入公共参数prm、用户私钥sk和明文信息m，输出对应的数字签名信息σ。

(4) SIGVer (prm, pk, m, σ)→ $\top$ or ⊥：该算法输入公共参数prm、用户公钥pk、明文m和数字签名信息σ，输出接受信息$\top$或错误信息⊥。

称数字签名方案SIG具有正确性，当且仅当对prm←SIGSetup(1^λ)和任意的(pk, sk)←SIGKeyGen(prm) 及明文m，SIGVer(prm, pk, m, SIGSign(prm, sk, m))=$\top$成立的概率为(1-negl(λ))。

SIG的SUF-CMA安全游戏则考虑挑战者$\mathcal{C}$与攻击者$\mathcal{A}$按以下步骤进行安全游戏：

(1) 设置阶段：挑战者$\mathcal{C}$生成prm←SIGSetup(1^λ)，(pk, sk)←SIGKeyGen(prm)。挑战者$\mathcal{C}$生成列表$\mathcal{L}$_SIG，记录游戏中生成的签名和对应明文信息。随后，挑战者$\mathcal{C}$将(prm, pk)发送给攻击者$\mathcal{A}$，并保留私钥sk。

(2) 查询阶段：攻击者$\mathcal{A}$向挑战者$\mathcal{C}$发起适应性信息查询m。挑战者$\mathcal{C}$接收到查询明文m后，首先检查列表$\mathcal{L}$_SIG中是否存在m的签名信息σ。若有, 则返回σ给攻击者$\mathcal{A}$；否则, 调用SIGSign(prm, sk, m)→σ，并将(m, σ)记录到列表$\mathcal{L}$_SIG，将σ返回给攻击者$\mathcal{A}$。

(3) 输出阶段：攻击者$\mathcal{A}$输出(m^*, σ^*)，若SIGVer(prm, pk, m^*, σ^*)→$\top$，并且(m^*, σ^*) ∉ $\mathcal{L}$，则称攻击者$\mathcal{A}$获得游戏胜利。

定义2   ^[16] (SIG的SUF-CMA安全)：称数字签名方案SIG具备SUF-CMA安全，当且仅当对任意的概率性多项式时间攻击者$\mathcal{A}$，在SIG的协议环境下执行数字签名的SUF-CMA安全游戏，获得游戏胜利的优势概率为：

且该优势概率关于安全参数λ可忽略。

1.4   消息认证码

对称加密的消息认证码(Message Authentication Code, MAC)主要包含MACSign算法和MACVer算法。使用$\mathcal{K}$_M表示消息认证码的对称密钥空间，该空间通常取决于安全参数λ。对任意的对称密钥mk∈$\mathcal{K}$_M，明文消息τ∈{0, 1}^*，有MACVer(mk, σ=MACSign(mk, τ), τ)=$\top$以(1-negl(λ))的概率成立，称σ为明文消息τ关于对称密钥mk的消息认证码。

消息认证码的一次选择信息攻击安全：称攻击者$\mathcal{A}$对消息认证码MAC成功发起一次选择信息攻击，当且仅当其适应性选取消息τ并获得关于对称密钥mk的消息认证码σ=MACSign(mk, τ)后，成功构造出(σ^*, τ^*)，满足MACVer(mk, σ^*, τ^*)=$\top$。若任意多项式时间攻击者$\mathcal{A}$对消息认证码MAC成功发起一次选择信息攻击的优势概率关于安全参数λ可忽略，则称MAC是一次选择信息攻击安全。

消息认证码的One-to-One属性：称消息认证码MAC是One-to-One的，当且仅当对任意的mk∈$\mathcal{K}$_M，任意的明文消息τ∈{0, 1}^*，有且仅有唯一的消息认证码σ=MACSign (mk, τ)，满足MACVer(mk, σ, τ)=$\top$。

1.5   对称加密算法

使用$\mathcal{K}$_D表示对称加密算法的密钥空间。对称加密算法(Symmetric Mechanism, SYM)由以下2个算法构成：

(1) SYMENC(dk, m)→C：算法以对称密钥dk ∈$\mathcal{K}$_D和明文m为输入，输出密文C。

(2) SYMDEC(dk, C)→m：该算法以对称密钥dk ∈$\mathcal{K}$_D和密文C为输入, 输出明文m。

称对称加密方案SYM具有正确性，当且仅当对任意的密钥dk ∈$\mathcal{K}$_D、明文m, m=SYMDEC(dk, SYMENC(dk, m))以(1-negl(λ))的概率成立。

对称加密算法的IND-PA安全游戏如下：挑战者$\mathcal{C}$向攻击者$\mathcal{A}$发送安全参数λ，并随机生成对称密钥dk←$\mathcal{K}$_D；攻击者$\mathcal{A}$接收到安全参数λ后，选取明文m₀和m₁返回给挑战者$\mathcal{C}$；挑战者$\mathcal{C}$接收到(m₀, m₁)后，随机抛币b←{0, 1}，并返回C^* =SYMENC (dk, m_b)给攻击者$\mathcal{A}$；攻击者$\mathcal{A}$接收到C^*后，输出b′∈{0, 1}。若满足b′=b，则称攻击者$\mathcal{A}$获得游戏胜利。

定义3   ^[17] (对称加密算法的IND-PA安全)称对称加密方案SYM具备IND-PA安全，当且仅当对任意的概率性多项式时间攻击者$\mathcal{A}$，在SYM的协议环境下执行SYM的IND-PA安全游戏，获得游戏胜利的优势概率为：

且该优势概率关于安全参数λ可忽略。

1.6   密钥推导函数

使用$\mathcal{K}$_K表示密钥封装机制的密钥空间。密钥推导函数KDF₂: $\mathcal{K}$_K→$\mathcal{K}$_D×$\mathcal{K}$_M是确定性函数，其将输入的密钥K∈$\mathcal{K}$_K映射到密钥空间$\mathcal{K}$_D×$\mathcal{K}$_M作为输出，并且满足输出分布与$\mathcal{K}$_D×$\mathcal{K}$_M的均匀分布统计不可区分。称密钥推导函数KDF₂安全，当且仅当其对任意多项式时间攻击者$\mathcal{A}$，均有：

成立。

2.   SCtK_std方案

本节将提出一种带标签的签密密钥封装机制的通用构造方案(SCtK_std)，并进行安全性分析。

2.1   带标签的签密密钥封装机制

带标签的签密密钥封装机制的协议概念^[4]和安全模型^[17]的具体表述如下。

定义4^[4]   带标签的签密密钥封装机制(SCtK)由以下6个算法构成：

(1) SCtKSetup(1^λ)→prm：该算法以安全参数λ为输入，输出公共参数prm。

(2) SCtKKeyGen_S (prm) → (pk_S, sk_S)：该算法以公共参数prm为输入，输出用户的发送方公私密钥(pk_S, sk_S)。

(3) SCtKKeyGen_R (prm)→ (pk_R, sk_R)：该算法以公共参数prm为输入，输出用户的接收方公私密钥(pk_R, sk_R)。

(4) SCtKSym (prm, sk_S, pk_R) → (K, ω)：该算法输入公共参数prm、发送方私钥sk_S和接收方公钥pk_R，输出临时随机密钥K和中间状态信息ω。

(5) SCtKEncap (prm, sk_S, pk_R, ω, τ) →C：算法输入公共参数prm、发送方私钥sk_S、接收方公钥pk_R、中间状态信息ω和标签信息τ，输出带标签的签密密钥封装报文C。

(6) SCtKDecap (prm, sk_R, pk_S, C, τ) →K or⊥：该算法输入公共参数prm、接收方私钥sk_R、发送方公钥pk_S、签密密钥封装报文C和标签信息τ，输出密钥K或错误信息⊥。

称带标签的签密密钥封装机制SCtK具有正确性，当且仅当对任意的prm←SCtKSetup(1^λ)、(pk_S, sk_S)←SCtKKeyGen_S(prm)、(pk_R, sk_R)←SCtKKey-Gen_R(prm)、(K, ω)←SCtKSym(prm, sk_S, pk_R)及C←SCtKEncap(prm, sk_S, pk_R, ω, τ)，SCtKDecap(prm, sk_R, pk_S, C, τ)=K以(1-negl(λ))的概率成立。

定义5^[17]   (带标签的签密密钥封装机制的DM-IND-iCCA安全游戏)挑战者$\mathcal{C}$与攻击者$\mathcal{A}$按以下步骤进行安全游戏：

(1) 设置阶段：挑战者$\mathcal{C}$调用SCtKSetup(1^λ)→prm，SCtKKeyGen_R(prm)→(pk_R, sk_R), 将(prm, pk_R)发送给攻击者$\mathcal{A}$，并保留私钥sk_R。

阶段1：攻击者$\mathcal{A}$任意调用SCtKKeyGen_S(prm)→(pk_S, sk_S) 和任意发起适应性选择密文查询(pk_S, C, τ)；挑战者$\mathcal{C}$接收到(pk_S, C, τ)后，调用SCtKDecap(prm, sk_R, pk_S, C, τ)→K or⊥，并将结果返回给攻击者$\mathcal{A}$。

(2) 挑战阶段：攻击者$\mathcal{A}$适应性选取合法的发送方公私密钥(pk_S^*, sk_S^*)，将其发送给挑战者$\mathcal{C}$。挑战者$\mathcal{C}$接收到(pk_S^*, sk_S^*)后，调用SCtKSym(prm, sk_S^*, pk_R)→(K₀, ω^*)，并且令K₁←$\mathcal{K}$_SC-tag-KEM，其中$\mathcal{K}$_SC-tag-KEM为临时密钥空间。挑战者$\mathcal{C}$随后进行抛币b←{0, 1}，将K_b返回给攻击者$\mathcal{A}$。攻击者$\mathcal{A}$接收到K_b后，将适应性选取标签信息τ^*发送给挑战者$\mathcal{C}$。挑战者$\mathcal{C}$接收到标签信息τ^*后，进一步调用SCtKEncap prm, sk_S^*, pk_R, ω^*, τ^* →C^*，返回C^*给攻击者$\mathcal{A}$。

阶段2：攻击者$\mathcal{A}$与阶段1一致，可向挑战者$\mathcal{C}$发起任意的适应性选择密文查询pk_S, C, τ，要求pk_S, C, τ ≠(pk_S^*, C^*, τ^*)。

(3) 猜测阶段：攻击者$\mathcal{A}$输出b′∈ 0, 1。若b′=b，则称攻击者$\mathcal{A}$获得游戏胜利。

定义6   ^[17] (带标签的签密密钥封装机制的DM-IND-iCCA安全)称签密密钥封装机制SCtK具备DM-IND-iCCA安全，当且仅当对任意概率性多项式时间攻击者$\mathcal{A}$，在SCtK的协议环境下执行SC-tag-KEM的DM-IND-iCCA安全游戏，获得游戏胜利的优势概率为：

且该优势概率关于安全参数λ可忽略。

定义7^[17]   (带标签的签密密钥封装机制的DM-SUF-iCMA安全游戏)挑战者$\mathcal{C}$与攻击者$\mathcal{A}$按以下步骤进行安全游戏：

设置阶段：挑战者$\mathcal{C}$调用SCtKSetup(1^λ)→prm，SCtKKeyGen_S prm →(pk_S, sk_S)，保留私钥sk_S，将prm, pk_S发送给攻击者$\mathcal{A}$。挑战者$\mathcal{C}$生成列表$\mathcal{L}$, 以记录游戏中生成的签密密文和对应的封装密钥及中间状态信息。

查询阶段：攻击者$\mathcal{A}$可以任意调用SCtKKey-Gen_R prm → pk_R, sk_R，并适应性选取pk_R发送给挑战者$\mathcal{C}$；挑战者$\mathcal{C}$接收到pk_R后，调用SCtKSym(prm, sk_S, pk_R)→ (K, ω)，将K发送给攻击者$\mathcal{A}$，并等待其进一步返回适应性选取的标签信息τ；挑战者$\mathcal{C}$首先检查列表$\mathcal{L}$中是否有(pk_R, K, ω, τ)的匹配项(pk_R, K, ω, τ, C′)：若有，则返回C′；否则，调用SCtKEncap(prm, sk_S, pk_R, ω, τ)→C，并将C返回给攻击者$\mathcal{A}$且记录(pk_R, K, ω, τ, C)到列表$\mathcal{L}$当中。

输出阶段：攻击者$\mathcal{A}$输出(pk_R^*, sk_R^*, C^*, τ^*)，满足(pk_R^*, sk_R^*)为合法的接收方公私密钥。若SCTKDecap(prm, sk_R^*, pk_S, C^*, τ^*)=K^*≠⊥，并且(pk_R^*, K^*, τ^*, C^*) ∉ $\mathcal{L}$，则称攻击者$\mathcal{A}$获得游戏胜利。

定义8^[17]   (带标签的签密密钥封装机制的DM-SUF-iCMA安全)称带标签的签密密钥封装机制SCtK具备DM-SUF-iCMA安全，当且仅当对任意的概率性多项式时间攻击者$\mathcal{A}$，在SCtK的协议环境下执行DM-SUF-iCMA安全游戏，获得游戏胜利的优势概率为：

且该优势概率关于安全参数λ可忽略。

2.2   方案构造

定义密钥封装机制KEM=(KEMSetup, KEMKeyGen, KEMEncap, KEMDecap)，数字签名方案SIG=(SIGSetup, SIGSign, SIGVer)，信息认证码MAC=(MACSign, MACVer)，密钥推导函数KDF₂: $\mathcal{K}$_K→$\mathcal{K}$_D×$\mathcal{K}$_M，其中，$\mathcal{K}$_K、$\mathcal{K}$_D、$\mathcal{K}$_M分别为KEM、DEM、MAC密钥空间。标准模型下，带标签的签密密钥封装机制的通用构造方案(SCtK_std)如图 1所示。

图  1  带标签的签密密钥封装机制的通用构造方案(SCtK_std)

Figure  1.  The generic construction scheme (SCtK_std) of signcryption tag key encapsulation mechanism

下载: 全尺寸图片 幻灯片

2.3   安全性证明

定理1   密钥封装机制KEM具备IND-CCA2安全，数字签名方案SIG具备SUF-CMA安全，密钥推导函数KDF₂安全，信息认证码MAC满足一次选择信息攻击安全并具备One-to-One属性，则SCtK_std方案在标准模型下达到完整内部安全。

证明   完整内部安全包含DM-IND-iCCA安全和DM-SUF-iCMA安全，以下从这2个方面给出SCtK_std方案的具体安全性证明，其中省略了协议内部的公共环境参数prm。

(1) SCtK_std方案的DM-IND-iCCA安全证明。假设存在攻击者$\mathcal{A}$以不可忽略的优势概率成功攻击SCtK_std方案的DM-IND-iCCA安全，考虑以下的一系列安全游戏：

Game 0：该游戏为原始游戏，挑战者$\mathcal{C}$按SCtK_std方案本身与攻击者$\mathcal{A}$诚实地进行SC-tag-KEM的DM-IND-iCCA安全游戏，从而有：

Game 1：在本次游戏中，挑战者$\mathcal{C}$在游戏最开始阶段选取K←$\mathcal{K}$_K。进入挑战阶段后, 挑战者$\mathcal{C}$生成(*, C^*)←KEMEncap pk_R，(dk₀, mk) ∶ =KDF₂(K)，dk₁←$\mathcal{K}$_D，随后抛币b∈{0, 1}，返回K_b给攻击者$\mathcal{A}$，等待其返回标签信息τ^*；在攻击者$\mathcal{A}$返回标签信息τ^*后，挑战者$\mathcal{C}$执行σ₁^*←SIGSign(sk_S, (C^*‖τ^*‖pk_R))，并进一步依据mk计算σ₂^*=MACSign(mk, (σ₁^*, pk_S))，返回((C^*, σ₁^*, σ₂^*), τ^*)给攻击者$\mathcal{A}$。对攻击者$\mathcal{A}$发起适应性查询(pk_S^′, (C′, σ′₁, σ′₂), τ′)，若C′=C^*，则挑战者$\mathcal{C}$将使用K为其执行解密预言机。

除K的选取方式不同外，Game 0和Game 1完全一致。此时若存在攻击者$\mathcal{A}$，其在Game 0和Game 1中进行SC-tag-KEM的DM-IND-iCCA安全游戏的获胜优势分别为ε₀和ε₁，且获胜优势的差距是不可忽略的: |ε₀-ε₁|>negl($\mathcal{A}$)，则以攻击者$\mathcal{A}$为子算法, 可构造区分器$\mathcal{D}$用于攻击KEM的IND-CCA2安全。

区分器$\mathcal{D}$的构造过程：令攻击者$\mathcal{A}$为获得游戏胜利的优势概率不可忽略的多项式时间攻击者，并在SCtK_std协议环境下进行DM-IND-iCCA安全游戏。以攻击者$\mathcal{A}$为子算法，按如下步骤可构造多项式时间攻击者$\mathcal{A}$_KEM，以攻击KEM的IND-CCA2安全：

① 攻击者$\mathcal{A}$_KEM在KEM的协议环境下进行IND-CCA2安全游戏，在游戏的设置阶段接收到挑战者$\mathcal{C}$_KEM发送的挑战报文(pk, K_b, C^*)。

② 攻击者$\mathcal{A}$_KEM开始模拟DM-IND-iCCA安全游戏，将接收到的公钥pk作为设置阶段的pk_R发送给攻击者$\mathcal{A}$。

③ 进入DM-IND-iCCA安全游戏的阶段1。此时，攻击者$\mathcal{A}$将发起适应性查询(pk_S, (C, σ₁, σ₂), τ)，要求返回SCtKDecap (sk_R, pk_S, C, σ₁, σ₂, τ)。

④ 攻击者$\mathcal{A}$_KEM将首先调用SIGVer(pk_S, (C‖τ‖pk_R), σ₁)来验证签名的合法性，若输出为⊥，则返回⊥。否则，继续验证C=C^*是否成立: 若成立，则输出abort事件，结束本次游戏；否则，向挑战者$\mathcal{C}$_KEM发起适应性查询C。若返回结果为K而不为空，则攻击者$\mathcal{A}$_KEM将计算(dk, mk)=KDF₂(K)，并验证MACVer(mk, (σ₁ pk_S))：若输出为$\top$，则返回dk；否则，返回⊥。此处abort事件的发生意味着攻击者在正式获得挑战密文前已访问到挑战密文，该事件发生的概率是可忽略的。

⑤ 进入DM-IND-iCCA安全游戏的挑战阶段。此时，攻击者$\mathcal{A}$发送(pk_S^*, sk_S^*)给攻击者$\mathcal{A}$_KEM。攻击者$\mathcal{A}$_KEM根据其本身的挑战报文(pk, K_b, C^*)，计算(dk₀, mk^*) =KDF₂(K_b)，dk₁←$\mathcal{K}$_D，并随机抛币c∈{0, 1}，将dk_c返回给攻击者$\mathcal{A}$。在攻击者$\mathcal{A}$返回标签信息τ^*后，攻击者$\mathcal{A}$_KEM调用SCtKEncap(sk_S^*, pk_R, (mk^*, c^*), τ^*)→((C^*, σ₁^*, σ₂^*), τ^*)，返回((C^*, σ₁^*, σ₂^*), τ^*)给攻击者$\mathcal{A}$。

⑥ 进入DM-IND-iCCA安全游戏的阶段2。对攻击者$\mathcal{A}$发起的适应性查询(pk″_S, (C″, σ″₁, σ″₂), τ″)≠(pk_S^*, (C^*, σ₁^*, σ₂^*), τ^*)，攻击者$\mathcal{A}$_KEM首先验证签名σ₁^″的合法性，若验证失败则返回⊥。对C″≠C^*，攻击者$\mathcal{A}$_KEM向挑战者$\mathcal{C}$_KEM发起适应性查询c″，若返回结果为K″而不为空，则计算(dk″, mk″)= KDF₂(K″)，并验证MACVer(mk″, (σ₁^″, pk_s^″))=σ₂^″是否成立。若成立，则返回dk″，否则返回⊥。而在C″=C^*的情况下，攻击者$\mathcal{A}$_KEM令(dk″, mk″)=KDF₂ (K_b)，若验证MACVer (mk″, (σ₁^″, pk_s^″))=σ₂^″通过，则返回dk″，否则返回⊥。

⑦ 进入DM-IND-iCCA安全游戏的猜测阶段。攻击者$\mathcal{A}$输出c′∈{0, 1}。若c=c′，则攻击者$\mathcal{A}$_KEM输出b=0；否则，输出b=1。

分析上述区分器$\mathcal{D}$。在abort事件不发生的情况下：当攻击者$\mathcal{A}$_KEM获取到的K_b为对应C^*的真实密钥K₀时，攻击者$\mathcal{A}$的实际游戏环境实质为Game 0；反之，当K_b为随机密钥K₁时，攻击者$\mathcal{A}$的游戏环境实质为Game 1。因此, Game 0和Game 1之间，在攻击者$\mathcal{A}$获得游戏胜利的优势概率差距不可忽略的情况下，若攻击者$\mathcal{A}$猜测正确，则可认为攻击者$\mathcal{A}$_KEM当前获取到的K_b是真实密钥K₀，否则可认为是随机密钥K₁。从而，攻击者$\mathcal{A}$_KEM可通过不可忽略的优势概率成功攻击KEM的IND-CCA2安全。此外，上述区分器$\mathcal{D}$的abort事件取决于密文C^*的取值空间$\mathcal{M}$_C以及攻击者$\mathcal{A}$在DM-IND-iCCA安全游戏阶段1的可查询次数q₁，从而

Game 2 : 该游戏与Game 1基本一致, 除挑战者$\mathcal{C}$在游戏最开始阶段不随机选取$K \leftarrow \mathcal{K}_K$, 而是选取$\mathrm{dk}_0 \times \mathrm{mk} \leftarrow \mathcal{K}_{\mathrm{D}} \times \mathcal{K}_{\mathrm{M}}$。进人挑战阶段, 挑战者$\mathcal{C}$生成$\left(*, C^*\right) \leftarrow$ KEMEncap $\left(\mathrm{pk}_{\mathrm{R}}\right), \mathrm{dk}_1 \leftarrow \mathcal{K}$, 随机抛币$b \in$ $\{0, 1\}$后, 返回$\mathrm{dk}_b$给攻击者$\mathcal{A}$。等待攻击者$\mathcal{A}$返回适应性选取的标签信息$\tau^*$后, 挑战者$\mathcal{C}$根据攻击者$\mathcal{A}$适应性选取的发送方公私密钥$\left(\mathrm{pk}_{\mathrm{S}}^*, \mathrm{sk}_{\mathrm{S}}^*\right)$, 生成$\sigma_1^* \leftarrow \operatorname{SIGSign}\left(\mathrm{sk}_S, \left(C^*\left\|_\tau{ }^*\right\| \mathrm{pk}_{\mathrm{R}}\right)\right)$和$\sigma_2^*:=\operatorname{MACSign}\left(\sigma_1^*\right.$, $\left.\mathrm{pk}_{\mathrm{s}}^*\right) \text {, 返回}\left(\left(C^*, \sigma_1^*, \sigma_2^*\right), \tau^*\right) \text {给攻击者} \mathcal{A}_{\circ} \text {对攻击}$者$\mathcal{A}$发起的适应性查询$\left(\mathrm{pk}_{\mathrm{S}}^{\prime}, \left(C^{\prime}, \sigma_1^{\prime}, \sigma_2^{\prime}\right), \tau^{\prime}\right)$, 若$C^{\prime}=C^*$, 则挑战者$\mathcal{C}$根据$\mathrm{dk}_0 \times \mathrm{mk}$为其执行解密预言机。

因此，若密钥推导函数安全，则攻击者视角的Game 1和Game 2完全一致；否则, 可构造区分器来区分该密钥推导函数的输出分布，从而得到：

Game 3 : 该游戏与Game 2基本一致, 除攻击者$\mathcal{A}$在阶段2向挑战者$\mathcal{C}$发起适应性查询$\left(\mathrm{pk}_{\mathrm{S}}, \left(C, \sigma_1\right.\right.$, $\left.\sigma_2\right), \tau$) 时, 若$C=C^*$, 则挑战者$\mathcal{C}$直接返回$\perp$。此时在Game 3中, 攻击者无法再获取任何有关挑战报文中$C^*$的有利信息, 即使其构造了有关挑战报文$C^*$的新鲜签密报文, 均只能获得信息$\perp$, 从而

接下来, 对Game 2和Game 3之间攻击者$\mathcal{A}$的优势概率进行绑定。注意到在Game 2中, 密钥$\mathrm{dk} \times$ $\mathrm{m k} \leftarrow \mathcal{K}_{\mathrm{D}} \times \mathcal{K}_{\mathrm{M}}$已达到真随机。假设Game 2和Game 3之间的优势概率丢失不可忽略, 则攻击者$\mathcal{A}$必然对根据挑战报文$\left(\left(C^*, \sigma_1{ }^*, \sigma_2{ }^*\right), \tau^*\right)$构造的新鲜的签密报文$\left(\left(C^*, \sigma_1^{* \prime}, \sigma_2^{* \prime}\right), \tau^{* \prime }\right)$成功发起了预言机查询, 对该过程进行分析:

Game 2中的攻击者$\mathcal{A}$本身具备签名私钥, 因此必然可构造出对应$\left(C^*, \tau^*\right)$的签名$\sigma_1^{* \prime}$。然而, 对于消息认证码$\sigma_2{ }^{* \prime}$, 对应的MAC密钥$\mathrm{mk}$是随机选取的并且与$C^*$完全独立, 攻击者$\mathcal{A}$无法从$\left(C^*, \sigma_1^*\right)$中获取任意构造$\sigma_2^{*{ }^*}$的有利信息。此时, 攻击者$\mathcal{A}$在仅有消息$\tau^*=\left(\sigma_1^* \| \mathrm{pk}_{\mathrm{S}}\right)$和$\sigma_2^*=\mathrm{MAC}-$ $\operatorname{Sign}\left(\mathrm{mk}, \left(\sigma_1^* \| \mathrm{pk}_{\mathrm{S}}^*\right)\right)$的情况下构造了新消息$\tau^*=$ $\left(\sigma_1^* \| \mathrm{pk}_{\mathrm{s}}\right)$以及关于$\mathrm{mk}$的合法MAC标签$\sigma_2^{* \prime}$, 等于成功发起了对MAC的一次选择信息攻击。

从而，将攻击者$\mathcal{A}$在Game 2和Game 3之间的概率优势丢失绑定到MAC的一次选择信息攻击安全上，即：

最终可得到：

(2) $\mathrm{SCtK}_{\mathrm{std}}$方案的DM-SUF-iCMA安全证明。$\mathrm{SCtK}_{\text {std }}$方案本质仍为加密后签名的结构, 对于接收方内部敌手$\mathcal{A}$获取到的任意的签密报文$\left(\left(C, \sigma_1\right.\right.$, $\left.\left.\sigma_2\right), \tau\right)$, 可通过对$C$解签密来获取对应$\sigma_2$的MAC密钥$\mathrm{mk}$。但在MAC的One-to-One属性情况下, 若其成功构造出新鲜的合法签密报文来攻击DM-SUFiCMA安全, 则必然生成了新鲜的合法签名$\sigma_1^{\prime}$, 以此可攻击数字签名方案SIG的SUF-CMA安全。从而以攻击者$\mathcal{A}$为子算法, 可构造对签名方案SIG的多项式时间攻击者$\mathcal{A}_{\mathrm{SIG}}$。

构造过程：以攻击者$\mathcal{A}$为子算法，构造概率性多项式时间攻击者$\mathcal{A}$_SIG，对签名方案SIG的SUF-CMA安全发起攻击：

(1) 攻击者$\mathcal{A}$_SIG在SIG的协议环境下进行SUF-CMA安全游戏，在该游戏的设置阶段接收到挑战者$\mathcal{C}$_SIG发送的公钥pk。

(2) 攻击者$\mathcal{A}$_SIG开始模拟DM-SUF-iCMA安全游戏且与攻击者$\mathcal{A}$进行交互，并将公钥pk作为该游戏设置阶段的pk_S发送给攻击者$\mathcal{A}$。

(3) 进人DM-SUF-iCMA安全游戏的查询阶段。对攻击者$\mathcal{A}$适应性选取的接收方公钥$\mathrm{pk}_{\mathrm{R}}$, 攻击者$\mathcal{A}_{\text {SIG }}$调用$\mathrm{K M E n c a p}\left(\mathrm{pk}_{\mathrm{R}}\right) \rightarrow(K, C)$, 生成$(\mathrm{dk}, \mathrm{mk})=$ $\mathrm{KDF}_2(K)$, 设置中间状态信息$\omega=(\mathrm{mk}, C)$, 返回$\mathrm{dk}$给攻击者$\mathcal{A}$, 并等待其后续查询。在接收到攻击者$\mathcal{A}$适应性选择的标签信息$\tau$后, 攻击者$\mathcal{A}_{\text {SIG }}$根据标签信息$\tau$、中间信息$\omega=(\mathrm{mk}, C)$和接收方公钥$\mathrm{pk}_{\mathrm{R}}$, 向息$\sigma_2=\operatorname{MACSign}\left(\mathrm{mk}, \left(\sigma_1, \mathrm{pk}_{\mathrm{S}}\right)\right)$, 返回$\left(C, \sigma_1, \sigma_2\right)$给攻击者$\mathcal{A}_{\text {。 }}$

(4) 进人DM-SUF-iCMA安全游戏的输出阶段。此时, 攻击者$\mathcal{A}$输出针对$\mathrm{SCtK}_{\mathrm{std}}$方案的DM-SUF-iCMA安全的伪装报文$\left(\mathrm{pk}_{\mathrm{R}}^*, \mathrm{sk}_{\mathrm{R}}^*, \left(C^*, \sigma_1^*, \sigma_2^*\right), \tau^*\right)$, 攻击者$\mathcal{A}_{\mathrm{SIG}}$直接令$m=\left(C^*\left\|_\tau{ }^*\right\| \mathrm{pk}_{\mathrm{R}}^*\right)$, 将$\left(m^*, \sigma_1^*\right)$返回给挑战者$\mathcal{C}_{\mathrm{SIG} \text { 。 }}$

对上述构造过程进行分析可以看到, 攻击者$\mathcal{A}_{\mathrm{SIG}}$完美模拟了$\mathrm{SCtK}_{\mathrm{std}}$方案的DM-SUF-iCMA安全游戏并与攻击者$\mathcal{A}$进行交互。假设攻击者$\mathcal{A}$成功攻击了$\mathrm{SCtK}_{\text {std }}$方案的DM-SUF-iCMA安全, 则对其最终返回的伪造报文$\left(\mathrm{pk}_{\mathrm{R}}^*, \mathrm{sk}_{\mathrm{R}}^*, \left(C^*, \sigma_1^*, \sigma_2^*\right), \tau^*\right)$进行分析: 若此前末向挑战者$\mathcal{C}_{\mathrm{SIG}}$查询过信息$m=$ $\left(C^*\left\|_\tau{ }^*\right\| \mathrm{pk}_{\mathrm{R}}^*\right)$的签名信息, 则攻击者$\mathcal{A}_{\mathrm{SIG}}$可成功攻击$\mathrm{SIG}$的$\mathrm{SUF}-\mathrm{CMA}$安全; 若此前向挑战者$\mathcal{C}_{\mathrm{SIG}}$查询过信息$m$的签名信息, 则根据密钥封装机制的正确性、密钥推导函数的确定性和MAC的One-to-One属性, 攻击者$\mathcal{A}$必然构造了信息$m=\left(C^*\left\|_\tau{ }^*\right\|_{\mathrm{pk}_{\mathrm{R}}}{ }^*\right)$的新鲜签名, 则攻击者$\mathcal{A}_{\mathrm{SIG}}$同样可成功攻击$\mathrm{SIG}$的SUF-CMA安全。

因此，在数字签名方案SIG本身具备SUF-CMA安全的情况下，SCtK_std方案是具备DM-SUF-iCMA安全的。

综上，SCtK_std方案在标准模型下可证明满足DM-IND-iCCA安全和DM-SUF-iCMA安全，进而达到完整内部安全。证毕。

3.   HSC_std方案

本节将SCtK_std方案应用在“SC-tag-KEM+DEM”的通用构造当中，提出了一种可达完整内部安全的混合签密的通用构造方案(HSC_std)，并进行安全性分析。

定义9^[9]   (签密方案，SC)完整的SC方案由以下5个算法构成：

(1) SCSetup(1^λ)→prm：该算法以安全参数λ为输入，输出公共参数prm。

(2) SCKeyGen_S (prm) → (pk_S, sk_S)：该算法以公共参数prm为输入，输出用户的发送方公私密钥(pk_S, sk_S)。

(3) SCKeyGen_R (prm) → (pk_R, sk_R)：该算法以公共参数prm为输入，输出用户的接收方公私密钥(pk_R, sk_R)。

(4) SCSC(prm, $\left.\mathrm{sk}_{\mathrm{S}}, \mathrm{pk}_{\mathrm{R}}, m\right) \rightarrow C$ : 该算法实现签密功能, 输人公共参数prm、发送方私钥$\mathrm{sk}_{\mathrm{S}}$、接收方公钥$\mathrm{pk}_{\mathrm{R}}$和明文$m$, 输出签密密文$C_{\text {。 }}$

(5) SCUSC (prm, sk_R, pk_S, c) →m or⊥：该算法实现解签密功能，输入公共参数prm、接收方私钥sk_R、发送方公钥pk_S和签密密文c，输出明文m或错误信息⊥。

称签密方案SC具有正确性，当且仅当对prm←SCSetup (1^λ)和任意的(pk_S, sk_S)←SCKeyGen_S(prm)，(pk_R, sk_R)←SCKeyGen_R(prm)，明文m和签密密文c←SCSC(prm, sk_S, pk_R, m)，SCUSC(sk_R, pk_S, prm, c)=m以(1-negl(λ))的概率成立。

3.1   通用构造方案

定义密钥封装机制KEM=(KEMSetup, KEMKey-Gen, KEMEncap, KEMDecap)，数字签名方案SIG=(SIGSetup, SIGKeyGen, SIGSign, SIGVer)，信息认证码MAC=(MACSign, MACVer)，对称加密算法SYM=(SYMENC, SYMDEC)，密钥推导函数KDF₂: $\mathcal{K}$_K→$\mathcal{K}$_D×$\mathcal{K}$_M，其中，$\mathcal{K}$_D为临时密钥空间，$\mathcal{K}$_M为MAC密钥空间。标准模型下，可达完整内部安全的混合签密的通用构造方案HSC_std如图 2所示。

图  2  可达完整内部安全的混合签密的通用构造方案(HSC_std)

Figure  2.  The generic construction scheme (HSC_std) of hybrid signatures with full insider security

下载: 全尺寸图片 幻灯片

3.2   安全性分析

HSC_std方案是基于文献[14]提出的混合签密通用构造方案，该方案的安全性基于定理1和以下引理。

引理1^[9]   若混合签密方案SC基于带标签的签密密钥封装机制SC-tag-KEM和数据封装机制DEM进行构造，并且SC-tag-KEM达到IND-CCA2安全，DEM达到IND-PA安全，则混合签密方案SC达到IND-CCA2安全。

引理2^[9]   若混合签密方案SC基于带标签的签密密钥封装机制SC-tag-KEM和数据封装机制DEM进行构造，且SC-tag-KEM达到SUF-CMA安全, 则混合签密方案SC达到SUF-CMA安全。

因此，只需选取达到IND-CCA2安全和SUF-CMA安全的SC-tag-KEM以及满足IND-PA安全的DEM作为混合签密方案HSC_std的底层协议构件，根据定理1、引理1和引理2，即可证明HSC_std方案达到了完整内部安全。

4.   结论

本文在不重用随机数的情况下提出了一种带标签的签密密钥封装机制的通用构造方案(SCtK_std)，该方案通过使用SIG构件绑定了标签和密钥的外部信息，在标准模型下达到完整内部安全。然后，结合SCtK_std方案与“SC-tag-KEM+ DEM”通用构造^[9]，提出了可达完整内部安全的混合签密通用构造方案(HSC_std)，并进行了安全性分析。结果表明：HSC_std方案具备了多方内部安全模型下的IND-CCA2安全和SUF-CMA安全，进而达到了完整内部安全。同时，由于模块化构造时所使用的构件具有多种成熟的实现方案，使得HSC_std方案具备较好的通用性和实用性。

然而，相对于经典计算攻击者，量子攻击者不仅具有更强的计算能力，还具有更强的问询能力。SCtK_std方案在安全性证明时所使用的安全模型为Chiba^[17]的动态多方内部安全模型，该模型并未考虑量子攻击者的量子叠加态问询能力，因此，SCtK_std方案也未被证明能有效抵抗量子攻击。所以，在后量子安全模型下来分析混合签密方案的安全性是下一步研究工作的重点。