定义5.2 一个签密tag-KEM 由以下6个算法组成.

概率性参数生成算法,表示为Genc,输入一个安全参数1k,该算法输出所有的全局信息I 例如系统参数、hash函数族等.

发送者密钥概率生成算法,Gens,输入全局信息I,该算法输出发送者的公钥、私钥对(skS,pkS).

概率性接收者密钥生成算法,Genr,输入全局信息I,算法输出接收者的公钥、私钥对(skR,pkR).

概率性对称密钥生成算法,Sym.输入发送者的私钥skS 和接收者的公钥pkR,算法输出一个对称密钥K 连同一个中间状态信息ω.

概率性密钥封装算法,Encap,输入中间状态ω 和任意标签τ ,输出一个封装E.

密钥解封装算法,Decap,输入发送者公钥pkS ,接收者私钥skR,封装E 和标签τ,该算法或者输出一个对称密钥K 或者输出一个错误符号.

定义5.3 一个签密DEM包含两个多项式时间算法

Enc,输入消息m、对称密钥K,输出消息的一个密文C =EncK(m).

Dec,输入密文C 对称密钥K ,该算法或者输出消息m=DecK(C)或者输出一个解密失败的错误符号.

定义5.4 假设(Genc,Gens,Genr,Encap,Sym,Decap) 是一个签密tag-KEM,(Enc;Dec)是一个签密DEM,若对所有的安全参数k,签密tag-KEM输出的密钥长度刚好可以被用于签密DEM,则我们可以按照如下方式构造一个混合签密方案.

—由签密tag-KEM的密钥生成算法((Genc,Genr,Gens))产生签密的公钥、私钥.

—按照如下运算生成签密

1.计算(K,C1)=encrap(skS,pkR,m);2.计算C2 =EncK(m);

3.输出(C1,C2) —解签密:

1.K =Decap(pkS,skR,C1);

2.m=DecK(C2);

3.如果Decap算法输出合法则接受消息,否则拒绝它.一个安全的混合签密方案应该在选择密文攻击下保持不可区分性(IND-CCA2).为了给出IND-CCA2安全性的定义首先来定义混合签密的IND-CCA2 Game.该Game是一个由挑战者和包含三个阶段的攻击者A=(A1;A2,A3)构成的.[108]

定义5.5 给定安全参数k,混合签密的IND-CCA2Game如下运行：(www.daowen.com)

1.挑战者生成公开参数I = Genc(1k)、发送者密钥对(pkS;skS) 以及接收者密钥对(pkR;skR).

2.攻击者以(pkS,pkR) 为输入运行A1 .在此过程中,A1 可以进行对称密钥生成询问、封装询问、解封装询问A1 在最后终止时输出某些状态信息state1.

3.挑战者进行如下计算:

(a)令(K0;ω)=Sym(skS;pkR).

(b)随机生成具有和K0 相同长度的对称密钥K1.

(c)随机生成一个比特b ∈{0,1}.

4.攻击者以(Kb,state1)为输入执行A2 .在此过程中A2 依然可以进行与A1相同的询问.A2 停止时输出状态信息state2 和一个标签τ.

5.挑战者计算一个挑战封装E =Encap(ω;τ).

6.攻击者以E,state2 为输入运行A3.在此过程中,A3 依然可以进行和前两个阶段相同的询问,所不同的是A3 不能以E,state2 为输入询问解封装预言机.A23 终止时应该输出一个猜测比特b′.

攻击者赢得以上游戏当且仅当b=b′.攻击者在上述游戏中的优势定义为

定义5.6 一个签密tag-KEM 是IND-CCA2安全的,如果,任意PPT敌手A 赢得INDCCA2 game 的优势是关于安全参数1k 可忽略的.

为了实现消息的认证性,一个安全的签密tag-KEM还应该能够满足在选择消息攻击下的强不可伪造性.签密tag-KEM的强不可伪造性由以下sUF-CMA Game来定义,该游戏中包括挑战者和敌手双方.

定义5.7 sUF-CMA Game: 1.挑战者首先生成全局参数T I = Com(1k),发送者的密钥对(skS;pkS)=KeyS(I)以及接收者的密钥对(skR;pkR)=KeyR(I).

2.敌手A 接收(I,pkS,skR,pkR)并开始与挑战者的交互.在此过程中,A 可以进行对称密钥生成询问和密钥封装询问.A 在停止时应该生成一个封装E 以及一个标签τ .

如果E 和τ 能够被合法解封装并且标签τ 从未在封装询问中被询问过,则敌手胜出.敌手优势定义为敌手胜出的概率.

定义5.8 一个签密tag-KEM在选择消息攻击下是强不可伪造的（sUF-CMA）,如果任何PPT敌手在上述的sUF-CMA game中胜出的优势是可忽略的.

引理5.1 [108]一个利用签密tag-KEM+签密DEM构造的混合签密方案是IND-CCA2安全的,如果签密tag-KEM是IND-CCA2安全的而签密DEM是IND-PA安全的

引理5.2 [108]一个利用签密tag-KEM+签密DEM构造的混合签密方案是sUF-CMA的,如果签密tag-KEM是sUF-CMA安全的.