# On the RCCA Security of Hybrid Signcryption for Internet of Things

Authors: Honglong Dai; Ding Wang; Jinyong Chang; Maozhi Xu
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

With the rapid development of the Internet of Things (IoT), a lot of sensitive information in our daily lives are now digitalized and open to remote access. The provision of security and privacy of such data would incur comprehensive cryptographic services and has raised wide concern. Hybrid signcryption schemes could achieve various kinds of cryptographic services (e.g., confidentiality, authenticity, and integrity) with much lower cost than the combination of separate traditional cryptographic schemes with each providing a single cryptographic service. Thus, hybrid signcryption schemes are very suitable for IoT environments where resources are generally very constrained (e.g., lightweight sensors and mobile phones). To ensure that the overall hybrid signcryption scheme provides adequate cryptographic service (e.g., confidentiality, integrity, and authentication), its parts of KEM (key encryption mechanism) and DEM (data encryption mechanism) must satisfy some security requirements. Chosen-ciphertext attack (CCA) security has been widely accepted as the golden standard requirement for general encryption schemes. However, CCA security appears too strong in some conditions. Accordingly, Canetti et al. (CRYPTO 2003) proposed the notion of replayable CCA security (RCCA) for encryption schemes, which is a strictly weaker security notion than CCA security and naturally more efficient. This new security notion has proved to be sufficient for most existing applications of CCA security, e.g., encrypted password authentication. This is particularly promising for IoT environments, where security is demanding, yet resources are constrained. In this paper, we examine the RCCA security of the well-known SKEM+DEM style hybrid signcryption scheme by Dent at ISC 2005. Meanwhile, we also examine the RCCA security of the Tag-SKEM+DEM style hybrid signcryption scheme by Bjorstad and Dent at PKC 2006. We rigorously prove that a hybrid signcryption scheme can achieve RCCA security if both its SKEM part and its DEM part satisfy some security assumptions.


---

## Body

## 1. Introduction

With the booming development of wireless technology, Internet of Things (IoT) has seen its proliferation in various applications such as personal health, government work, and battle surveillance. How to ensure security and privacy of the sensitive data in these security-critical applications is a challenging issue, because it would generally incur comprehensive cryptographic services. Hybrid signcryption schemes could achieve various kinds of cryptographic services (e.g., confidentiality, authenticity, and integrity) with much lower cost than the combination of separate traditional cryptographic schemes with each providing a single cryptographic service [1]. Thus, hybrid signcryption schemes are very suitable for IoT environments where resources are generally very constrained (e.g., lightweight sensors and mobile phones).The first signcryption scheme was proposed by Zheng [2] at CRYPTO’97. The notion of confidentiality for a signcryption scheme is analogous to an original encryption scheme, while the nonrepudiation service is analogous to a digital signature one [3]. Since then, various kinds of signcryption schemes have been suggested. At 2002, Lee [4] proposed identity-based signcryption; At AsiaCCS’08, Barbosa et al. [5] proposed certificateless signcryption. At IMACC’13, Nakano et al. [6] presented two generic constructions of signcryption in the standard model. At 2017, Li et al. [7] proposed a signcryption for cloud computing. At PQCrypto’18 Sato et al. [8] proposed lattice-based signcryption without random oracles. At the same time, Datta et al. [9] proposed the functional signcryption.In addition, a number of signcryption schemes have been proposed for the IoT environments (e.g., key establishment over ATM networks [10], defense against fragment duplication attack in 6LoWPAN networks [11], short signcryption scheme for IoT [12], and provably secure signcryption for IoT [13]). Belguith et al. [14] proposed privacy preserving attribute based signcryption for IoT.However, in the traditional signcryption schemes, the keyed encapsulation encryption is generally not made full use of, and the length of messages is always related to the signcryption scheme. Further, the major weakness of asymmetric encryption schemes is that the computational efficiency is worse than these symmetric ones [15]. Accordingly, the notion of hybrid signcryption is proposed. Hybrid signcryption uses a symmetric encryption scheme to improve the overall performance and flexibility of asymmetric signcryption. Hybrid signcryption can simultaneously combine the main advantages of a public key encryption and a digital signature scheme with much lower cost when compared with traditional schemes [1, 16]. As sensor nodes in IoT are resource-constrained (e.g., limited battery power) and deployed to run for years, hybrid cryptography is particularly suitable for data storage and transmission to achieve secure and efficient communication [17]. At 2004, Dent [15] proposed a formal composition model for hybrid signcryption, and this model covers Zheng’s scheme [2]. Later, Bjorstad et al. [18] proposed an improve signcryption scheme with tag-KEMs, Li et al. [19] proposed a certificateless hybrid signcryption scheme, and Zhou [20] proposed an improved certificateless hybrid signcryption scheme. Due to the usage of a symmetric encryption scheme to overcome the weakness and restricted message space of traditional asymmetric encryption schemes, these hybrid signcryption schemes can make the length of message independent of the security of the overall signcryption scheme.Secure encryption is one of the most fundamental tasks in cryptographic schemes, while CCA security has been widely accepted as the golden standard requirement for encryption schemes [21, 22]. However, chosen-ciphertext attack security appears to be too strong in many conditions; there exist many encryption schemes that are not CCA secure but still have practical applications [23]. Here we take a CCA secure public key encryption scheme PKE as example. We change it into a public key encryption scheme PKE’, which is equal to public key encryption scheme PKE except that this encryption oracle algorithm appends a bit 0 to each ciphertext and the decryption oracle algorithm of PKE’ discards this bit 0 of a ciphertext. Then, one naturally obtains a different ciphertext decrypted to the same message as the original one. However, this change takes no real consequence in most situation, because the modified scheme PKE′ appears to be as secure as the scheme PKE in most situations. This example is also used in [23].Accordingly, Canetti et al. [23] proposed the RCCA security notion at CRYPTO 2003. RCCA security is a strictly weaker security notion than CCA security, which has proved to be abundant for most cryptographic primitives, e.g., encrypted password authentication [24]. There are some studies (e.g., [23, 25]) about the RCCA security of hybrid cryptography, and there are also several studies (e.g., [2, 3, 15]) about the CCA security of hybrid signcryption. As far as we know, there is no work about examining the RCCA security of hybrid signcryption. To fill the gap, in this paper we consider the RCCA security of hybrid signcryption and show that hybrid signcryption can achieve RCCA security (rather than only CCA security) based on certain conditions.


### 1.1. Main Contributions

In this paper, we examine the RCCA security of the hybrid signcryption scheme Tag-SKEM+DEM [18] and the hybrid signcryption scheme SKEM+DEM [3]. We will show the following: (1) The hybrid signcryption scheme (SKEM+DEM) can be RCCA-secure if the scheme Tag-SKEM is RCCA-secure and the scheme DEM is RCCA-secure. (2) The hybrid encryption scheme (Tag-SKEM+DEM) can be RCCA-secure if the signcryption scheme Tag-SKEM is RCCA-secure and the scheme DEM is RCCA-secure. Although our results might be expected and somewhat straightforward, we concretely confirm such expectations with a formal proof. When giving our proof, we mainly use the hybrid game-based reduction technique presented in [26–28].


### 1.2. Related Works and Discussions

It is obvious that if the hybrid signcryption scheme is going to provide an integrity and authentication service, then its KEM part and DEM part must satisfy some kind of security criterion. Dent et al. [15] examined the CCA security of hybrid signcryption schemes (SKEM+DEM and Tag-SKEM+DEM). Chen et al. [27] examined the RCCA security for hybrid encryption scheme KEM+DEM. Cui et al. [29] gave two kinds of RKA-secure signcryption schemes. In 2017, Dai et al. [30] considered the ECCA security for hybrid encryptions Tag-KEM+DEM and KEM+Tag-DEM. Abe et al. [26] provided a hybrid encryption scheme Tag-KEM+DEM, and they presented a useful way to get CCA secure hybrid encryptions. Cramer et al. [31] have shown that the hybrid encryption scheme Tag-KEM+DEM is CCA secure if its KEM part is CCA secure and its DEM part is one-time secure.As, for the scheme Tag-SKEM+DEM, the ciphertext of scheme DEM is a tag of the scheme Tag-SKEM, one may think that the security assumption of scheme SKEM could be weakened to chosen plaintext attack (CPA) security when considering the RCCA security of signcryption. As it is impossible to make a simulation for the decryption oracle query for an adversary when the adversary attacks the hybrid signcryption, we leave it as an open problem that the security of scheme SKEM and DEM could be relaxed to a weaker security (e.g., CPA). One may also think that, with the RCCA security of Tag-KEM and one-time security of DEM, one can get the RCCA security of hybrid signcryption scheme Tag-KEM+DEM. However, the adversary cannot generate useful challenge ciphers if the adversary does not change the tag used for the scheme Tag-DEM. In this paper, when proving our results, we make a perfect simulation for the adversary, who initiates a IND-RCCA experiment to hybrid signcryption. We summarise the hybrid cryptology and their security in Table1.Table 1
The hybrid cryptology and their security notion∗.
Hybrid cryptology Security notion Reference KEM+DEM RCCA+RCCA⇒RCCA [27] KEM+DEM CCA+CCA⇒CCA [31] SKEM+DEM RCCA+RCCA⇒RCCA Section3.2 SKEM+DEM CCA+CCA⇒CCA [15] Tag-KEM+DEM CCA+one time security⇒CCA [32] Tag-KEM+DEM RCCA+RCCA⇒RCCA [27] Tag-SKEM+DEM CCA+CCA⇒CCA [15] Tag-SKEM+DEM RCCA+RCCA⇒RCCA Section3.4 ∗KEM: key encapsulation mechanism, DEM: data encapsulation mechanism.Organizations of the Paper. In Section 2, we review some basic notations and definitions. In Section 3 we review the definition of general hybrid signcryption scheme, SKEM+DEM and Tag–SKEM+DEM, and then we prove its RCCA security. In Section 4, we review our main conclusions.


## 1.1. Main Contributions

In this paper, we examine the RCCA security of the hybrid signcryption scheme Tag-SKEM+DEM [18] and the hybrid signcryption scheme SKEM+DEM [3]. We will show the following: (1) The hybrid signcryption scheme (SKEM+DEM) can be RCCA-secure if the scheme Tag-SKEM is RCCA-secure and the scheme DEM is RCCA-secure. (2) The hybrid encryption scheme (Tag-SKEM+DEM) can be RCCA-secure if the signcryption scheme Tag-SKEM is RCCA-secure and the scheme DEM is RCCA-secure. Although our results might be expected and somewhat straightforward, we concretely confirm such expectations with a formal proof. When giving our proof, we mainly use the hybrid game-based reduction technique presented in [26–28].


## 1.2. Related Works and Discussions

It is obvious that if the hybrid signcryption scheme is going to provide an integrity and authentication service, then its KEM part and DEM part must satisfy some kind of security criterion. Dent et al. [15] examined the CCA security of hybrid signcryption schemes (SKEM+DEM and Tag-SKEM+DEM). Chen et al. [27] examined the RCCA security for hybrid encryption scheme KEM+DEM. Cui et al. [29] gave two kinds of RKA-secure signcryption schemes. In 2017, Dai et al. [30] considered the ECCA security for hybrid encryptions Tag-KEM+DEM and KEM+Tag-DEM. Abe et al. [26] provided a hybrid encryption scheme Tag-KEM+DEM, and they presented a useful way to get CCA secure hybrid encryptions. Cramer et al. [31] have shown that the hybrid encryption scheme Tag-KEM+DEM is CCA secure if its KEM part is CCA secure and its DEM part is one-time secure.As, for the scheme Tag-SKEM+DEM, the ciphertext of scheme DEM is a tag of the scheme Tag-SKEM, one may think that the security assumption of scheme SKEM could be weakened to chosen plaintext attack (CPA) security when considering the RCCA security of signcryption. As it is impossible to make a simulation for the decryption oracle query for an adversary when the adversary attacks the hybrid signcryption, we leave it as an open problem that the security of scheme SKEM and DEM could be relaxed to a weaker security (e.g., CPA). One may also think that, with the RCCA security of Tag-KEM and one-time security of DEM, one can get the RCCA security of hybrid signcryption scheme Tag-KEM+DEM. However, the adversary cannot generate useful challenge ciphers if the adversary does not change the tag used for the scheme Tag-DEM. In this paper, when proving our results, we make a perfect simulation for the adversary, who initiates a IND-RCCA experiment to hybrid signcryption. We summarise the hybrid cryptology and their security in Table1.Table 1
The hybrid cryptology and their security notion∗.
Hybrid cryptology Security notion Reference KEM+DEM RCCA+RCCA⇒RCCA [27] KEM+DEM CCA+CCA⇒CCA [31] SKEM+DEM RCCA+RCCA⇒RCCA Section3.2 SKEM+DEM CCA+CCA⇒CCA [15] Tag-KEM+DEM CCA+one time security⇒CCA [32] Tag-KEM+DEM RCCA+RCCA⇒RCCA [27] Tag-SKEM+DEM CCA+CCA⇒CCA [15] Tag-SKEM+DEM RCCA+RCCA⇒RCCA Section3.4 ∗KEM: key encapsulation mechanism, DEM: data encapsulation mechanism.Organizations of the Paper. In Section 2, we review some basic notations and definitions. In Section 3 we review the definition of general hybrid signcryption scheme, SKEM+DEM and Tag–SKEM+DEM, and then we prove its RCCA security. In Section 4, we review our main conclusions.


## 2. Preliminaries

In this section, we will review some useful notations and cryptographic primitives that will be used throughout this paper.Notations. We denote by 1λ the security parameter and write m←RM to denote the algorithm that picks an m randomly from the set M. PPT denotes probabilistic polynomial time. we write z←A(x,y,⋯) to denote the algorithm that runs algorithm A with inputs (x,y,⋯) and then outputs z. We define a function negl(λ) asnegligible: if for any constant c>0, there exits a k0∈Z, such that for all λ>k0, negl(λ)<λ-c.


### 2.1. RCCA Security Definition

P K E = ( G e n , E n c , D e c ) is a public key encryption (PKE) scheme that consists of three polynomial-time algorithms:(i)
Gen is key generation algorithm that inputs the security parameter λ and outputs a pair of public/private keys (pk,sk).(ii)
Enc is PPT encryption algorithm that encrypts a message m into a ciphertext c.(iii)
Dec is a deterministic decryption algorithm that decrypts a ciphertext c and outputs either message m or a reject symbol ⊥.Now, we define its RCCA security by describing the attack experiment between a challenger and an PPT adversaryA=(A1,A2) with the following experiment:(i)
Setup: The adversary A queries Gen algorithm: (pk,sk)←Gen(λ).(ii)
Stage 1: The adversary A1 queries a ciphertext c to Dec: m←Dec(sk,c), and adversary A1 responds with m.(iii)
Challenge stage: The adversary A1 queries a pair message (m0,m1) to Enc, where m0=m1, and then the challenger chooses a bit b←R0,1, computes the challenge cipher Enc(pk,mb)=c∗, and, finally, sends the challenge c∗ to A1.(iv)
Stage 2: The adversary A2 makes continuous queries c to Dec; here, we require that the cipher c is not identical to the challenge cipher c∗. The decryption algorithm runs m←Dec(sk,c). Finally, if m∈m0,m1, adversary A2 responds with text, or else adversary A2 responds with m or reject symbol ⊥.(v)
Guess stage: The adversary A outputs b′∈0,1.We letAdvPKE,AIND-RCCA(λ) = Prb=b′-1/2 in the above experiment.If for any PPT adversaryA, the function AdvPKE,AIND-RCCA(λ) is negligible, we believe that PKE=(Gen,Enc,Dec) is RCCA-secure.


### 2.2. Signcryption Key Encryption Mechanism (SKEM) and Its RCCA Security Notions

A signcryption key encryption mechanismSKEM=(KEM.GenS, KEM.GenR, KEM.Enc, KEM.Dec) is a asymmetric encryption scheme [3], which consists of the four algorithms with the following:(i)
SKEM.GenS is a PPT algorithm that inputs a security parameter 1λ and outputs the sender’s public/private key (skS,pks).(ii)
SKEM.GenR is a PPT algorithm that inputs a security parameter 1λ and outputs the receiver’s public/private key (skR,pkR).(iii)
SKEM.Enc is a PPT encryption algorithm that inputs the send’s private key skS and the receiver’s public key pkR and outputs (K,C); here, K is a symmetric key and C is the key encapsulation of K.(iv)
SKEM.Dec is a deterministic, polynomial-time decryption algorithm that inputs the sender’s public key pkS, a key encapsulation c, and the receiver’s private key skR and outputs either a key K or the error symbol ⊥.We now define its RCCA security by describing the attack experiment; this experiment is played by an adversaryA=(A1,A2) and the challenger:(i)
Setup: The challenger queries a key generation oracle SKEM.GenS(λ) and SKEM.GenR(λ). The key generation oracle SKEM.GenS runs (pkS,skS)←SKEM.GenS(λ) and the key generation oracle SKEM.GenS runs (pkR,skR)←SKEM.GenR(λ). Finally, the key generation oracle SKEM.GenS and SKEM.GenR sends (pkR,pkS) to adversary A.(ii)
Stage 1: The adversary A1 inputs (pkR,pkS) and makes queries to encapsulation oracle and decapsulation oracle. For every decapsulation oracle algorithm query, the adversary A1 submits a ciphertext ψ to decryption algorithm Dec: K←Dec(pkS,skR,ψ). Finally, responds the adversary A with K or ⊥.(iii)
Challenge stage: The challenger computes ψ∗←SKEM.Enc(skS,pkR,K1), chooses K0←RKK,σ←R0,1, where KK is the key space, K0=K1, and sends (Kσ,ψ∗) to adversary A1.(iv)
Stage 2: The adversary A2 inputs (pkR,pkS) and makes continuous queries ψ to SKEM.Dec. Here, we require that adversary A2 is not allowed to query (pkS,c∗) to SKEM.Dec. However, we admit that adversary A2 can query SKEM.Dec on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The decryption oracle algorithm responds with K←Dec(skR,pkS,ψ). Finally, if K∈K0,K1, A2 is responded with text, or else A2 is responded with K.(v)
Guess stage: In the end, A outputs a bit σ′∈0,1.In the attack experiment, we letAdvSKEM,AIND-RCCA(λ) = Prσ=σ′-1/2. If for any PPT adversary A, the function AdvSKEM,AIND-RCCA(λ) is negligible, we say the signcryption scheme SKEM=(SKEM.GenR,SKEM.GenR,SKEM.Enc,SKEM.Dec) is RCCA-secure.


### 2.3. Data Encryption Mechanism and Its IND-RCCA Security

A signcryption data encryption mechanismDEM is a symmetric encryption scheme, which consists of the following two algorithms: DEM.ENC, DEM.Dec.(i)
DEM.Enc:c←DEM.Enc(K,m); DEM.Enc is a polynomial-time encryption algorithm; DEM.Enc encrypts m by using a key K and outputs the corresponding ciphertext c.(ii)
DEM.Dnc:m←DEM.Dec(K,c); DEM.Dec is a polynomial-time decryption algorithm; it inputs ciphertext χ and decrypts the cipher c by using the same key K.We define itsIND–RCCA security by describing the attack experiment; this experiment is played by an adversary A=(A1,A2) and the challenger:(i)
Setup 1: The challenger chooses a key symmetric K←RKD.(ii)
Challenge stage: The adversary A queries (m0,m1) to DEM.Enc, m0=m1. The challenger chooses b←R0,1, computes the challenge cipher c∗←Enc(K,mb), and then sends the challenge cipher c∗ to adversary A.(iii)
Setup 2: The adversary A2 continues to make queries cipher c to Dec: m←Dec(c,K); here, c is not equal to the challenge cipher c∗. If m∈m0,m1, Dec responds to adversary A with text, or else Dec responds to adversary A with m.(iv)
Guess stage: In the end, the adversary A outputs b′∈{0,1}.We defineAdvDEM,AIND-RCCA(λ)=Prb=b′-1/2 in the above experiment.If for any PPT adversaryA, the function AdvDEM,A2IND-RCCA(λ) is negligible, the scheme DEM is IND–RCCA secure.


## 2.1. RCCA Security Definition

P K E = ( G e n , E n c , D e c ) is a public key encryption (PKE) scheme that consists of three polynomial-time algorithms:(i)
Gen is key generation algorithm that inputs the security parameter λ and outputs a pair of public/private keys (pk,sk).(ii)
Enc is PPT encryption algorithm that encrypts a message m into a ciphertext c.(iii)
Dec is a deterministic decryption algorithm that decrypts a ciphertext c and outputs either message m or a reject symbol ⊥.Now, we define its RCCA security by describing the attack experiment between a challenger and an PPT adversaryA=(A1,A2) with the following experiment:(i)
Setup: The adversary A queries Gen algorithm: (pk,sk)←Gen(λ).(ii)
Stage 1: The adversary A1 queries a ciphertext c to Dec: m←Dec(sk,c), and adversary A1 responds with m.(iii)
Challenge stage: The adversary A1 queries a pair message (m0,m1) to Enc, where m0=m1, and then the challenger chooses a bit b←R0,1, computes the challenge cipher Enc(pk,mb)=c∗, and, finally, sends the challenge c∗ to A1.(iv)
Stage 2: The adversary A2 makes continuous queries c to Dec; here, we require that the cipher c is not identical to the challenge cipher c∗. The decryption algorithm runs m←Dec(sk,c). Finally, if m∈m0,m1, adversary A2 responds with text, or else adversary A2 responds with m or reject symbol ⊥.(v)
Guess stage: The adversary A outputs b′∈0,1.We letAdvPKE,AIND-RCCA(λ) = Prb=b′-1/2 in the above experiment.If for any PPT adversaryA, the function AdvPKE,AIND-RCCA(λ) is negligible, we believe that PKE=(Gen,Enc,Dec) is RCCA-secure.


## 2.2. Signcryption Key Encryption Mechanism (SKEM) and Its RCCA Security Notions

A signcryption key encryption mechanismSKEM=(KEM.GenS, KEM.GenR, KEM.Enc, KEM.Dec) is a asymmetric encryption scheme [3], which consists of the four algorithms with the following:(i)
SKEM.GenS is a PPT algorithm that inputs a security parameter 1λ and outputs the sender’s public/private key (skS,pks).(ii)
SKEM.GenR is a PPT algorithm that inputs a security parameter 1λ and outputs the receiver’s public/private key (skR,pkR).(iii)
SKEM.Enc is a PPT encryption algorithm that inputs the send’s private key skS and the receiver’s public key pkR and outputs (K,C); here, K is a symmetric key and C is the key encapsulation of K.(iv)
SKEM.Dec is a deterministic, polynomial-time decryption algorithm that inputs the sender’s public key pkS, a key encapsulation c, and the receiver’s private key skR and outputs either a key K or the error symbol ⊥.We now define its RCCA security by describing the attack experiment; this experiment is played by an adversaryA=(A1,A2) and the challenger:(i)
Setup: The challenger queries a key generation oracle SKEM.GenS(λ) and SKEM.GenR(λ). The key generation oracle SKEM.GenS runs (pkS,skS)←SKEM.GenS(λ) and the key generation oracle SKEM.GenS runs (pkR,skR)←SKEM.GenR(λ). Finally, the key generation oracle SKEM.GenS and SKEM.GenR sends (pkR,pkS) to adversary A.(ii)
Stage 1: The adversary A1 inputs (pkR,pkS) and makes queries to encapsulation oracle and decapsulation oracle. For every decapsulation oracle algorithm query, the adversary A1 submits a ciphertext ψ to decryption algorithm Dec: K←Dec(pkS,skR,ψ). Finally, responds the adversary A with K or ⊥.(iii)
Challenge stage: The challenger computes ψ∗←SKEM.Enc(skS,pkR,K1), chooses K0←RKK,σ←R0,1, where KK is the key space, K0=K1, and sends (Kσ,ψ∗) to adversary A1.(iv)
Stage 2: The adversary A2 inputs (pkR,pkS) and makes continuous queries ψ to SKEM.Dec. Here, we require that adversary A2 is not allowed to query (pkS,c∗) to SKEM.Dec. However, we admit that adversary A2 can query SKEM.Dec on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The decryption oracle algorithm responds with K←Dec(skR,pkS,ψ). Finally, if K∈K0,K1, A2 is responded with text, or else A2 is responded with K.(v)
Guess stage: In the end, A outputs a bit σ′∈0,1.In the attack experiment, we letAdvSKEM,AIND-RCCA(λ) = Prσ=σ′-1/2. If for any PPT adversary A, the function AdvSKEM,AIND-RCCA(λ) is negligible, we say the signcryption scheme SKEM=(SKEM.GenR,SKEM.GenR,SKEM.Enc,SKEM.Dec) is RCCA-secure.


## 2.3. Data Encryption Mechanism and Its IND-RCCA Security

A signcryption data encryption mechanismDEM is a symmetric encryption scheme, which consists of the following two algorithms: DEM.ENC, DEM.Dec.(i)
DEM.Enc:c←DEM.Enc(K,m); DEM.Enc is a polynomial-time encryption algorithm; DEM.Enc encrypts m by using a key K and outputs the corresponding ciphertext c.(ii)
DEM.Dnc:m←DEM.Dec(K,c); DEM.Dec is a polynomial-time decryption algorithm; it inputs ciphertext χ and decrypts the cipher c by using the same key K.We define itsIND–RCCA security by describing the attack experiment; this experiment is played by an adversary A=(A1,A2) and the challenger:(i)
Setup 1: The challenger chooses a key symmetric K←RKD.(ii)
Challenge stage: The adversary A queries (m0,m1) to DEM.Enc, m0=m1. The challenger chooses b←R0,1, computes the challenge cipher c∗←Enc(K,mb), and then sends the challenge cipher c∗ to adversary A.(iii)
Setup 2: The adversary A2 continues to make queries cipher c to Dec: m←Dec(c,K); here, c is not equal to the challenge cipher c∗. If m∈m0,m1, Dec responds to adversary A with text, or else Dec responds to adversary A with m.(iv)
Guess stage: In the end, the adversary A outputs b′∈{0,1}.We defineAdvDEM,AIND-RCCA(λ)=Prb=b′-1/2 in the above experiment.If for any PPT adversaryA, the function AdvDEM,A2IND-RCCA(λ) is negligible, the scheme DEM is IND–RCCA secure.


## 3. The RCCA Security of Hybrid Signcryption Schemes

In this section, we will recall the definition of hybrid signcryption which is adapted by Dent and An [15, 33]. Some definitions include the verification algorithm, whose aim is to provide nonrepudiation. However, in their view, nonrepudiation is unnecessary for most cryptography applications and hence will not be discussed further. Next, we examine the RCCA security for hybrid signcryption and consider the outsider security (the adversary is third party, neither sender nor receiver) of hybrid signcryption, which is proposed by Dent in [3].


### 3.1. SKEM+DEM Hybrid Signcryption Scheme and Its Relaxing Chosen Cipher Attack Security

S K E M = ( S K E M . G e n S , S K E M . G e n R , S K E M . E n c , S K E M . D e c ) is signcryption key encapsulation mechanism, DEM=(DEM.Enc,DEM.Dec) is data encapsulation mechanism, and hybrid signcryption scheme SKEM+DEM=(signcrypt.Gen,signcrypt.Enc,signcrypt.Dec) can be constructed from SKEM and DEM as follows:(i)
signcrypt.Gen(1λ): It runs receiver’s key generation algorithm (pkR,skR)←SKEM.GenR(1λ) and runs sender’s key generation algorithm (pkS,skS)←SKEM.GenS(1λ), Finally, it outputs (pkS,skS) and (pkR,skR).(ii)
signcrypt.Enc(pk, m): signcrypt.Enc is a PPT algorithm that inputs the sender’s private key skS, a message m, and the receiver’s public key pkR. It chooses K←KD and computes χ←SKEM.Enc(skS,pkR,K); here KD is the signcryption scheme DEM’s key space. Then it computes ψ←DEM.EncK(m), and the resulting signcryption is c≔(χ,ψ).(iii)
signcrypt.Dec(sk, c): the signcrypt.Dec algorithm inputs the sender’s public key pkS, a cipher c, and the receiver’s private key skR. It then parses cipher c as ψ∥χ and runs K←TKEM.Dec(ψ,pkS,skR),m←DEM.DecK(χ). In the end, it outputs m or “reject” symbol ⊥.


### 3.2. The RCCA Security of Hybrid Signcryption Schemes

Theorem 1.
The hybrid signcryption scheme(SKEM+DEM) can be constructed from a signcryption scheme SKEM and a scheme DEM. If the signcryption scheme SKEM is IND–RCCA secure and the signcryption scheme DEM is IND–RCCA secure, then hybrid signcryption scheme (SKEM+DEM) can achieve IND–RCCA security. For every given PPT adversary A, there exist probabilistic adversary A1 and adversary A2, such that the following conclusion holds:(1)AdvSKEM+DEM,ARCCAλ≤2AdvSKEM,A1RCCAλ+AdvDEM,A2RCCAλ+qsKD.Here, we assume the adversaryA1 at most makes the qs queries to the encryption-decryption oracle, the running times of A1 and A2 are equal to that of adversary A, and KD is the signcryption scheme DEM’s key space.Proof. Fix adversary A and λ; A is a PPT IND–RCCA adversary, which attacks the hybrid signcryption scheme SKEM+DEM; then we proved the theorem by the following experiments.E x p e r i m e n t 0: This is an IND–RCCA experiment on the signcryption scheme SKEM+DEM, which is played by an adversary A=(A1,A2) and the challenger. (We denote by T0 the event of adversary A succeeding in this experiment.)(i)
Setup: The adversary A makes queries to key generation algorithm (pkR,skR)←SKEM.GenR(1λ) and makes queries to key generation algorithm (pkS,skS)←SKEM.GenS(1λ). Finally, it sends (pkR,pkS) to adversary A.(ii)
Stage 1: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries to decryption oracle algorithm. For adversary A′s decryption algorithm query c=(ψ,χ), the adversary A1 sends a cipher c=(ψ,χ) to the challenger C, and the challenger C runs decryption algorithm K←SKEM.Dec(ψ,pks,skR)m←DEM.DecK(χ). In the end, the challenger responds to A1 with m.(iii)
Challenge stage: The adversary A1 inputs (pkR,pkS) and queries (m0,m1) to an encryption oracle, and the challenger chooses K1←KD and chooses b∈{0,1}. Then the challenger computes χ←SKEM.Enc(skS,pkR,K1) and computes ψ←DEM.EncK(mb) the signcryption c≔(χ,ψ).(iv)
Stage 2: The adversary A2 inputs (pkRi,pkSi) and makes continuous queries c=(ψ,χ) to the challenger. Here, the adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle algorithm. But we admit that adversary A2 can make a query to the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The challenger runs decryption oracle K←SKEM.Dec(pkSi,skRi,ψ,χ) and m←DEM.DecKi(χ). If m∈m0,m1, the challenger responds to A2 with text or else responds to A2 with m.(v)
Guess stage: In the end, the adversary A outputs a guessing bit b′∈0,1.The following conclusion holds:(2)AdvSKEM+DEM,ARCCAλ=Prb=b′-12=PrT0-12.E x p e r i m e n t 1: We now modify experiment G0 to obtain a new experiment G1. These two experiments are identical except that we use a uniformly random key K0←RKD to compute the challenge cipher C∗=(χ∗,ψ∗) in step 3 of Game0; the challenge cipher C∗=(χ∗,ψ∗) is computed by the encryption algorithm SKEM.Enc(skS,pkR,K0) and ψ←DEM.EncK(m). To maintain consistency, the challenger should use the symmetric key K0 to answer the decryption oracle algorithm query (pkS,χ,.). Hence, the distinction between experiment G0 and experiment G1 mainly lies in how the scheme SKEM runs. (Denote by T1 the sign of the adversary A succeeding in this experiment.) We have the following conclusion.Lemma 2.
There is an adversaryA1, and its running time is equal to the running time of adversary A; the following conclusion holds:(3)PrT1-PrT0≤2AdvSKEM,A1RCCAλ+qsKD.Proof.
We prove the lemma by constructing an adversaryA1 who attacks the signcryption scheme SKEM. The adversary A1 simulates the environment for A, their interactions can be described as follows: (i)
Setup: The adversary A1 was given (pkS,pkR,Kσ), and the adversary A1 sent (pkS,pkR) to A.(ii)
Stage 1: The adversary A inputs (pkS,pkR) and makes some queries c to the decryption oracle: m←Dec(skR,pkS,c). Finally, A is reponded with m or reject symbol ⊥.(iii)
Challenge stage: The adversary A inputs (pkS,pkR) and queries (m0,m1) to an encryption oracle, m0=m1. The adversary A1 computes χ∗←SKEM.Enc(skS,pkR,K1) and computes ψ∗←DEM.EncK(mb), and finally the adversary A1 sends the challenge cipher c∗=(ψ∗,χ∗) to the adversary A.(iv)
Stage 2: The adversary A inputs (pkSi,pkRi) and makes queries c=(ψi,χi) to decryption oracle algorithm. Here, we require that A2 cannot query (pkS,c∗) to the decryption oracle algorithm. However, we admit that adversary A2 can query the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for C≠C∗. The adversary A1 runs (4)Ki←SKEM.DecpkSi,skRi,χi,ψi,m←DEM.DecKiψi.Finally, ifm∈m0,m1, A2 responds with text, or else A2 is responded with m.(v)
Guess stage: The adversary A outputs a guessing bit b′∈0,1 and A1 outputs σ′=b′ in the end.
This has completed the construction ofA1. By description, we can see that the adversary A1 played a perfectly simulated decryption for adversary A unless the cipher ψ∗ is decrypted to K1 and test is returned by the correct answer from the decryption oracle SKEM.Dec for every query. However, the probability of this event is 1/KD since in that case the key K1 is uniformly random and independent of the opinion of the adversary A1 for each such query. (i)
Ifσ=0, we can obtain that cipher χ is computed by a random key K0; meanwhile, the opinion of the adversary A is equal to that in Experiment0.(ii)
Ifσ=1, we can obtain that K1 is corresponding correct key embedded in the cipher ψ; meanwhile, the opinion of the adversary A is equal to that in Experiment1.
Thus,(5)AdvSKEM,A1RCCAλ=Prb=b′-12=PrT0-12=12Prσ′=1∣σ=1-Prσ′=1∣σ=0=12Prb=b′∣σ=1-Prb=b′∣σ=0≥12PrT0-PrT1-qsKD.
We can get the following conclusion:(6)PrT1-PrT0≤2AdvSKEM,A1RCCAλ+qsKD.
Lemma2 is proved.In the stage of experimentG1’s encryption and decryption oracle algorithms, we use a uniformly random key K0, so the challenger cipher ψ∗ is not be decrypted. From this point, we notice that the challenge cipher χ∗ is generated by using a random symmetric key K0 in experiment G1. Meanwhile, the other cipher χ=χ∗ is decrypted by using random key K0, which has no other role in experiment G1. Hence, in experiment G1, the adversary A plays an adaptive replayable chosen ciphertext attack against (RCCA) the signcryption scheme DEM in substance, so the following conclusion holds.Lemma 3.
There is a probabilistic adversaryA2, and its running time is equal to the running time of the adversary A, such that the following conclusion holds:(7)PrT1-12≤AdvDEM,A2RCCAλ.Proof.
The symmetric keyK0 was chosen uniformly, randomly, and independently, so the challenge cipher χ does not reveal related information about which message was encrypted. Hence, to gain success in experiment 2, the adversary must learn some information from the challenger cipher χ. We prove Lemma 3 by constructing a probabilistic adversary A2, who attacks the signcryption scheme DEM, and A2 provides an environment for the adversary A. Now, we describe their interactions:(i)
Setup: The adversary A2 runs receiver key generation algorithm (pkR,skR)←SKEM.GenR(1λ), runs sender key generation algorithm (pkS,skS)←SKEM.GenS(1λ), and sends (pkR,pkS) to A.(ii)
Stage 1: The adversary A inputs (pkR,pkS) and makes queries ciphertext c to a decryption oracle algorithm: K←SKEM.Dec(pkS,skR,χ), m←DEM.Dec(K,χ). If m=⊥, the decryption oracle algorithm responds to adversary A with m or reject symbol ⊥.(iii)
Challenge Stage: The adversary A inputs a public key pair (pkR,pkS) and sends (m0,m1) to the adversary A2. the adversary A2 chooses K1←RKD, runs ψ∗←SKEM.Enc(pkS,skR,K1), and sends the challenge c∗=(ψ∗,χ∗) to A. We notice that the symmetric key K1 was chosen as the encryption key of scheme DEM and embedded in cipher ψ∗, which is uniformly random and independent of each other.(iv)
Stage 2: The adversary inputs (pkR,pkS) and makes continuous queries c=(ψ,χ) to decryption oracle algorithm. Here, we require that adversary A2 cannot query (pkS,c∗) to the decryption oracle algorithm. However, we admit adversary A2 can make a query to the decryption oracle algorithm on (pkS′,C) for any cipher pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The adversary A2 uses the secret key skR to run the decryption oracle algorithm and answer the decryption query c=(ψ,χ) of adversary A with the following:
(a)
Ifψi=ψ∗, hence χi≠χ∗. Then The adversary A2 runs the decryption oracle K←SKEM.Dec(pkS,skR,χ). If K=⊥, the adversary A2 responds to A with ⊥ or else m←DEM.Dec(K,χ). If m∈{m0,m1}, the adversary A2 responds to A with text, or else A2 responds to A with m.(v)
Guess Stage: Finally, adversary A outputs a bit b′∈0,1 and A2 also outputs a bit b′.
This has completed the description of the adversaryA2. By our construction, it is obvious that the adversary A2 plays a perfectly simulated decryption for A, and whenever A gets success, so does A2. We have the following conclusion:(8)PrT1-12≤AdvDEM,A2RCCAλ.We can know that the advantage ofA in experiment0 is (9)AdvSKEM+DEM,ARCCAλ=PrT0-12≤2AdvSKEM,A1RCCAλ+AdvDEM,A2RCCAλ,which is negligible; we have proved Theorem 1.


### 3.3. The Hybrid Signcryption Scheme Tag-SKEM+DEM and Its RCCA Security

Definition 4 (signcryption scheme Tag-SKEM).
A signcryption schemeTag–KEM=(GenR,GenS,Tag–KEM.Enc,Tag–KEM.Dec) consists of the following three algorithms:(i)
Tag–KEM.GenS(1λ):Tag–KEM.GenS(1λ) is a PPT algorithm that inputs a security parameter 1λ and outputs a pair of public/private keys (skS,pkS).(ii)
Tag–KEM.GenR(1λ):TKEM.GenS(1λ) is a PPT algorithm that inputs a security parameter 1λ and outputs a pair of public/private keys (skR,pkR).(iii)
An encryption algorithmTag–KEM.Enc: It runs (ω,K)←Tag–KEM.Key(pkR,skS). Tag–KEM.Key(·) is a PPT algorithm that inputs the private key of sender skS and public key of receiver pkR and outputs one-time key K and Intermediate state information ω. Choose r←R0,1λ and compute ψ←TKEM.Enc(ω,r,pkR,skS,τ). Tag–KEM.Enc is a PPT algorithm that encrypts the key K (embedded in ω) into cipher ψ along with a tag τ∈T and returns a cipher ψ; here, τ is called a tag.(iv)
An decryption algorithmTag–KEM.Dec:K←Tag–KEM.Dec(pkS,skR,ψ,τ). TKEM.Dec is a deterministic decryption verification algorithm for a signcryption cipher, which inputs the receiver’s private key skR, the cipher c, the sender’s public key pkS, and a tag τ; the decryption oracle Tag–KEM.Dec returns a key K or reject symbol ⊥.Definition 5 (hybrid signcryption scheme Tag-SKEM+DEM).
The signcryption scheme(10)Tag–SKEM=GenR,GenS,TKEM.Enc,TKEM.Decis a asymmetric encryption scheme and the signcryption scheme DEM=(DEM.Enc,DEM.Dec) is a corresponding symmetric encryption scheme [18].Then the hybrid signcryption scheme(11)Tag–SKEM+DEM=Gen,signcrypt,unsigncryptcan be constructed as follows:(i)
Key generation algorithmGen(1λ): GenR(1λ) is a probabilistic receiver’s key generation algorithm that inputs a 1λ and outputs the receiver’s public/private key pair (pkR,skR); we write this as (pkR,skR)←GenR(1λ). GenS(1λ) is a probabilistic receiver key generation algorithm, which takes a as input a security parameter 1λ and as output a receiver’s public/private key pair (pkS,skS); we write this as (pkS,skS)←GenS(1λ).(ii)
An encryption algorithmsigncrypt:Tag–SKEM.Key(·) is a probabilistic algorithm that inputs the receiver’s public key pkS and outputs a symmetric key K∈KD and the internal state information ω, (ω,K)←Tag–SKEM.Key(pkS). Here KD is the scheme DEM’s key space. Then choose r←R0,1λ and compute χ←DEM.EncK(m), ψ←Tag–SKEM.Enc(pkS,skR,ω,r,χ). Finally, output the signcrypt cipher c=(ψ,χ).(iii)
A decryption algorithmunsigncrypt: First, it parses the cipher c to obtain ψ∥χ. Next, it computes K←Tag–SKEM.Dec(skR,pkR,ψ,χ) to obtain a symmetric key K and computes m←DEM.DecK(χ). Finally, it outputs the message m or “reject” symbol ⊥.


### 3.4. The RCCA Security of Hybrid Signcryption Scheme Tag-SKEM+DEM

Theorem 6.
The hybrid signcryption scheme(Tag–SKEM+DEM) is constructed from a scheme Tag–SKEM and a scheme DEM. If the signcryption scheme Tag–SKEM is IND–RCCA secure and the signcryption scheme DEM is IND–RCCA secure, then the hybrid signcryption scheme (Tag–SKEM+DEM) is also IND–RCCA secure. For every PPT adversary A, there are probabilistic adversary A1 and adversary A2, whose running times are essentially equal to that of adversary A, such that for all λ≥0, the following holds.(12)AdvTag-SKEM+DEM,ARCCAλ≤2AdvTag-KEM,A1RCCAλ+AdvDEM,A2RCCAλ+qsKD.Here, we assume the adversary at most makes theqs queries to the encryption-decryption oracle algorithm and KD is the scheme DEM’s key space.Proof. We prove the theorem by constructing a PPT adversary A who attacks the hybrid signcryption scheme Tag–SKEM+DEM with the following experiments. (We denote by Ti the event of the adversary A succeeding in the i-th game.)E x p e r i m e n t 0: This is the IND–RCCA experiment on the signcryption scheme Tag- SKEM+DEM, and this experiment is played between an adversary A and the challenger as follows:(i)
Setup: The adversary queries a key generation oracle. The challenger runs receiver key generation algorithm (pkR,skR)←Tag–SKEM.GenR(1λ), runs sender key generation algorithm (pkS,skS)←Tag–SKEM.GenS(1λ), and responds to the adversary A with (pkR,pkS).(ii)
Stage 1: The adversary A inputs (pkR,pkS) and makes continuous queries to decryption oracle algorithm. The adversary A sends a cipher c to the decryption oracle algorithm, and the decryption oracle algorithm runs K←Tag–SKEM.Dec(pkS,skR,χ,ψ), m←DEM.Dec(K,χ). If m=⊥, the decryption oracle algorithm responds to A1 with ⊥ or else responds to A1 with m.(iii)
Challenge stage: The adversary A1 inputs a public key pair (pkR,pkS) and queries (m0,m1) to an encryption oracle algorithm, and then the challenger runs (ω,K)←Tag–SKEM.Key(pkRskS), K∈KD. Then the challenger computes DEM.EncK(m0)=χ∗, Tag–SKEM.Enc(pkR,skS,ω,χ∗)=ψ∗ and sends the challenge cipher c∗=(ψ∗,χ∗) to the adversary A1.(iv)
Stage 2: The adversary A2 inputs a public key pair (pkRi,pkSi) and makes continuous queries c=(ψ,χ) to the challenger. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle. However, we admit that adversary A2 can make a query to the decryption oracle on (pkS′,C) for any public key pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The challenger runs decryption oracle. (13)K←Tag–SKEM.DecskRi,pkSi,ψ,χ,m←DEM.DecKχFinally, ifm∈m0,m1, A2 responds with text, or else A2 responds with m.(v)
Guess stage: In the end, the adversary A outputs a guess bit b′∈0,1.Naturally, the following holds:(14)AdvTag-SKEM+DEM,ARCCAλ=PrT0-12=Prb=b′-12.E x p e r i m e n t 1: We now modify Experiment0 to obtain a new Experiment1; this experiment is equal to the above experiment except that we just use a random key K0←RKD to encrypt the message m0 in step 3 of experiment0; hence, we get the following conclusion.Lemma 7.
There exists a probabilistic adversaryA1, and its running time is equal to that of adversary A, such that the following conclusion holds:(15)PrT1-PrT0≤AdvTag-SKEM,A1RCCAλ+qsKD.Here, we assume the adversary at most makes theqs queries to the encryption-decryption oracle algorithm.Proof.
We prove the lemma by constructing an adversaryA1 who attacks signcryption scheme Tag-SKEM. The adversary A1 simulates an environment for adversary A; their interactions can be described as follows: (i)
Stage 1: The adversary A2 was given (pkR,pkS,Kσ), and at the same time, (pkR,pkS) was sent to adversary A.(ii)
Stage 2: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries c to a decryption oracle algorithm Dec. The decryption oracle algorithm runs m←Dec(pkS,skR,c). Finally, if m=⊥, A responds with m or reject symbol ⊥.(iii)
Stage 3: The adversary A inputs a pair public key (pkR,pkS) and queries (m0,m1) to the encryption oracle, m0=m1. The adversary A1 requires the encryptions oracle of scheme Tag-SKEM to obtain (Kσ,ψ∗). The adversary A1 chooses b∈0,1 and computes DEM.EncS(Kσ,mb)=χ∗. Finally, the adversary A1 sends challenge cipher c∗=(ψ∗,χ∗) to the adversary A.(iv)
Stage 4: The adversary A inputs (pkRi,pkSi) and makes continuous calls c=(ψi,χi) to decryption oracle query. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle algorithm. However, we admit that adversary A2 can make a query to the decryption oracle on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The adversary A1 runs its own decryption oracle Tag–SKEM.Dec(pkS,skR,.) to answer the adversary A’s decryption query as follows:
(a)
If⊥ is returned, then the adversary A1 responds to A with ⊥.(b)
If⊥ is returned and χi≠χ∗, then A1 uses Kσ to decrypt the cipher χ.
(1)
Ifm0 or m0 is returned, then the adversary A1 responds to A with text.(2)
Otherwise,A1 responds to A with the result.(c)
Iftest is returned and cipher χi=χ∗, then the adversary A1 responds to A with text.(d)
IfK1 is returned, then the adversary uses K1 to decrypt the cipher χ.
(1)
Ifm0 or m0 is returned, then the adversary A1 responds to adversary A with text.(2)
Otherwise,A1 responds to adversary A with the result.(v)
Stage 5: In the end, the adversary A outputs a guess bit b′∈0,1, and A1 outputs a bit σ′=b′.
This has completed the description ofA1; it is clear that the adversary A1 plays a perfectly simulated decryption for A unless the cipher ψ∗ is decrypted to K1 and test is returned by the correct answer from the decryption oracle Tag–SKEM.Dec for every query. However, the probability of this event is 1/KD since in that case the key K1 is random and independent of the opinion of the adversary A1 for each such query. (i)
Ifσ=0, we can know that random key K0 is used for computing the cipher χ and the view of A is identical to that in Experiment0. Accordingly, Prb′=b∣σ=0=Pr[T2].(ii)
Ifσ=1, we can know that the key K1 is the correct key embedded in the cipher ψ and the view of A is equal to that in Experiment1. Accordingly, Prb′=b∣σ=1-PrT1≤qD/KD.
Thus,(16)AdvTag-SKEM,A1RCCAλ=Pr⁡T0-12=Prb=b′-12=12Prσ′=1∣σ=1-Prσ′=1∣σ=0=12Prb=b′∣σ=1-Prb=b′∣σ=0≥12PrT0-PrT1-qdKD.
Hence,(17)PrT1-PrT0≤2AdvTag-SKEM,A1RCCAλ+qsKD.Lemma2 is proved. Next, we show that the adversary A playing Experiment1 essentially conducts an IND-RCCA attack on the signcryption scheme DEM; we claim the following.Lemma 8.
There is a probabilistic adversaryA2, and its running time is equal to that of A, and the following conclusion holds:(18)PrT2-12≤AdvDEM,A2RCCAλ.Proof.
This can be shown by constructing an adversaryA2 who attacks the signcryption scheme DEM. The adversary A2 simulates the environment for adversary A; their interactions can be described as follows:(i)
Stage 1: The adversary A2 queries receiver’s key generation algorithm (pkR,skR)←Tag–SKEM.GenR(1λ), queries sender’s key generation algorithm (pkS,skS)←Tag–SKEM.GenS(1λ), and sends a public key pair (pkR,pkS) to A.(ii)
Stage 2: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries c to a decryption oracle algorithm: m←Dec(skR,pkS,c). In the end, adversary A is responded with m or reject symbol ⊥.(iii)
Stage 3: The adversary A inputs a pair public key (pkR,pkS) and sends (m0,m1) to the adversary A2; A2 queries (m0,m1) to the encryption oracle algorithm and then receives a challenge ciphertext χ∗. A2 runs (ω,K1)←Tag–SKEM.Key(pkR,skS) and then computes the following. (19)Tag–SKEM.Encpkω,χ∗=ψ∗In the end, the adversaryA2 submits the challenger cipher c∗=(ψ∗,χ∗) to adversary A.(iv)
Stage 4: The adversary A inputs a public key pair (pkRi,pkSi) and makes continuous queries c=(ψi,χi) to decryption oracle algorithm. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle. However, we admit that the adversary A2 is admitted to query the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The adversary A2 uses (pkSi,skRi) to decrypt the cipher c=(ψi,χi). The adversary A2 runs the decryption oracle. (20)Ki←Tag–SKEM.DecpkS,skR,ψi,χi,m←DEM.DecKiχiThe adversaryA2 answers A’s decryption query c=(ψi,χi) with the following:
(a)
IfKi=⊥, then A2 responds to A with ⊥.(b)
IfKi=K1 and χ=χ∗, then A2 responds to A with ′text′.(c)
IfKi=K1 and χ≠χ∗, then A2 responds to A with m.(d)
IfKi≠K1, then A2 uses Ki to decrypt the cipher χ.
(1)
Ifm∈m0,m1, then adversary A2 sends ′text′ to adversary A.(2)
Otherwise, adversaryA2 sends m to adversary A.Here, we notice that the keyK0 chosen by the signcryption scheme DEM’s encryption oracle and embedded in the cipher χ∗ is randomly chosen and independent.(v)
Stage 5: In the end, the adversary A outputs b′∈0,1, and the adversary A also outputs σ′=b′.
We have described the construction of the adversaryA2. A2 plays a perfect simulation Experiment for A; the view of A is equal to that in Experiment0 and Experiment1; hence, we have (21)PrT1-12≤AdvDEM,A2RCCAλ.Putting all the facts together, we have the following conclusion:(22)PrT0-12-PrT1-12≤AdvTag-SKEM+DEM,ARCCAλ+qsKDAdvTag-SKEM+DEM,ARCCAλ≤2AdvTag-SKEM,A1RCCAλ+qsKD+AdvTag-DEM,A2CCAλ.We have proved Theorem6.


## 3.1. SKEM+DEM Hybrid Signcryption Scheme and Its Relaxing Chosen Cipher Attack Security

S K E M = ( S K E M . G e n S , S K E M . G e n R , S K E M . E n c , S K E M . D e c ) is signcryption key encapsulation mechanism, DEM=(DEM.Enc,DEM.Dec) is data encapsulation mechanism, and hybrid signcryption scheme SKEM+DEM=(signcrypt.Gen,signcrypt.Enc,signcrypt.Dec) can be constructed from SKEM and DEM as follows:(i)
signcrypt.Gen(1λ): It runs receiver’s key generation algorithm (pkR,skR)←SKEM.GenR(1λ) and runs sender’s key generation algorithm (pkS,skS)←SKEM.GenS(1λ), Finally, it outputs (pkS,skS) and (pkR,skR).(ii)
signcrypt.Enc(pk, m): signcrypt.Enc is a PPT algorithm that inputs the sender’s private key skS, a message m, and the receiver’s public key pkR. It chooses K←KD and computes χ←SKEM.Enc(skS,pkR,K); here KD is the signcryption scheme DEM’s key space. Then it computes ψ←DEM.EncK(m), and the resulting signcryption is c≔(χ,ψ).(iii)
signcrypt.Dec(sk, c): the signcrypt.Dec algorithm inputs the sender’s public key pkS, a cipher c, and the receiver’s private key skR. It then parses cipher c as ψ∥χ and runs K←TKEM.Dec(ψ,pkS,skR),m←DEM.DecK(χ). In the end, it outputs m or “reject” symbol ⊥.


## 3.2. The RCCA Security of Hybrid Signcryption Schemes

Theorem 1.
The hybrid signcryption scheme(SKEM+DEM) can be constructed from a signcryption scheme SKEM and a scheme DEM. If the signcryption scheme SKEM is IND–RCCA secure and the signcryption scheme DEM is IND–RCCA secure, then hybrid signcryption scheme (SKEM+DEM) can achieve IND–RCCA security. For every given PPT adversary A, there exist probabilistic adversary A1 and adversary A2, such that the following conclusion holds:(1)AdvSKEM+DEM,ARCCAλ≤2AdvSKEM,A1RCCAλ+AdvDEM,A2RCCAλ+qsKD.Here, we assume the adversaryA1 at most makes the qs queries to the encryption-decryption oracle, the running times of A1 and A2 are equal to that of adversary A, and KD is the signcryption scheme DEM’s key space.Proof. Fix adversary A and λ; A is a PPT IND–RCCA adversary, which attacks the hybrid signcryption scheme SKEM+DEM; then we proved the theorem by the following experiments.E x p e r i m e n t 0: This is an IND–RCCA experiment on the signcryption scheme SKEM+DEM, which is played by an adversary A=(A1,A2) and the challenger. (We denote by T0 the event of adversary A succeeding in this experiment.)(i)
Setup: The adversary A makes queries to key generation algorithm (pkR,skR)←SKEM.GenR(1λ) and makes queries to key generation algorithm (pkS,skS)←SKEM.GenS(1λ). Finally, it sends (pkR,pkS) to adversary A.(ii)
Stage 1: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries to decryption oracle algorithm. For adversary A′s decryption algorithm query c=(ψ,χ), the adversary A1 sends a cipher c=(ψ,χ) to the challenger C, and the challenger C runs decryption algorithm K←SKEM.Dec(ψ,pks,skR)m←DEM.DecK(χ). In the end, the challenger responds to A1 with m.(iii)
Challenge stage: The adversary A1 inputs (pkR,pkS) and queries (m0,m1) to an encryption oracle, and the challenger chooses K1←KD and chooses b∈{0,1}. Then the challenger computes χ←SKEM.Enc(skS,pkR,K1) and computes ψ←DEM.EncK(mb) the signcryption c≔(χ,ψ).(iv)
Stage 2: The adversary A2 inputs (pkRi,pkSi) and makes continuous queries c=(ψ,χ) to the challenger. Here, the adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle algorithm. But we admit that adversary A2 can make a query to the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The challenger runs decryption oracle K←SKEM.Dec(pkSi,skRi,ψ,χ) and m←DEM.DecKi(χ). If m∈m0,m1, the challenger responds to A2 with text or else responds to A2 with m.(v)
Guess stage: In the end, the adversary A outputs a guessing bit b′∈0,1.The following conclusion holds:(2)AdvSKEM+DEM,ARCCAλ=Prb=b′-12=PrT0-12.E x p e r i m e n t 1: We now modify experiment G0 to obtain a new experiment G1. These two experiments are identical except that we use a uniformly random key K0←RKD to compute the challenge cipher C∗=(χ∗,ψ∗) in step 3 of Game0; the challenge cipher C∗=(χ∗,ψ∗) is computed by the encryption algorithm SKEM.Enc(skS,pkR,K0) and ψ←DEM.EncK(m). To maintain consistency, the challenger should use the symmetric key K0 to answer the decryption oracle algorithm query (pkS,χ,.). Hence, the distinction between experiment G0 and experiment G1 mainly lies in how the scheme SKEM runs. (Denote by T1 the sign of the adversary A succeeding in this experiment.) We have the following conclusion.Lemma 2.
There is an adversaryA1, and its running time is equal to the running time of adversary A; the following conclusion holds:(3)PrT1-PrT0≤2AdvSKEM,A1RCCAλ+qsKD.Proof.
We prove the lemma by constructing an adversaryA1 who attacks the signcryption scheme SKEM. The adversary A1 simulates the environment for A, their interactions can be described as follows: (i)
Setup: The adversary A1 was given (pkS,pkR,Kσ), and the adversary A1 sent (pkS,pkR) to A.(ii)
Stage 1: The adversary A inputs (pkS,pkR) and makes some queries c to the decryption oracle: m←Dec(skR,pkS,c). Finally, A is reponded with m or reject symbol ⊥.(iii)
Challenge stage: The adversary A inputs (pkS,pkR) and queries (m0,m1) to an encryption oracle, m0=m1. The adversary A1 computes χ∗←SKEM.Enc(skS,pkR,K1) and computes ψ∗←DEM.EncK(mb), and finally the adversary A1 sends the challenge cipher c∗=(ψ∗,χ∗) to the adversary A.(iv)
Stage 2: The adversary A inputs (pkSi,pkRi) and makes queries c=(ψi,χi) to decryption oracle algorithm. Here, we require that A2 cannot query (pkS,c∗) to the decryption oracle algorithm. However, we admit that adversary A2 can query the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for C≠C∗. The adversary A1 runs (4)Ki←SKEM.DecpkSi,skRi,χi,ψi,m←DEM.DecKiψi.Finally, ifm∈m0,m1, A2 responds with text, or else A2 is responded with m.(v)
Guess stage: The adversary A outputs a guessing bit b′∈0,1 and A1 outputs σ′=b′ in the end.
This has completed the construction ofA1. By description, we can see that the adversary A1 played a perfectly simulated decryption for adversary A unless the cipher ψ∗ is decrypted to K1 and test is returned by the correct answer from the decryption oracle SKEM.Dec for every query. However, the probability of this event is 1/KD since in that case the key K1 is uniformly random and independent of the opinion of the adversary A1 for each such query. (i)
Ifσ=0, we can obtain that cipher χ is computed by a random key K0; meanwhile, the opinion of the adversary A is equal to that in Experiment0.(ii)
Ifσ=1, we can obtain that K1 is corresponding correct key embedded in the cipher ψ; meanwhile, the opinion of the adversary A is equal to that in Experiment1.
Thus,(5)AdvSKEM,A1RCCAλ=Prb=b′-12=PrT0-12=12Prσ′=1∣σ=1-Prσ′=1∣σ=0=12Prb=b′∣σ=1-Prb=b′∣σ=0≥12PrT0-PrT1-qsKD.
We can get the following conclusion:(6)PrT1-PrT0≤2AdvSKEM,A1RCCAλ+qsKD.
Lemma2 is proved.In the stage of experimentG1’s encryption and decryption oracle algorithms, we use a uniformly random key K0, so the challenger cipher ψ∗ is not be decrypted. From this point, we notice that the challenge cipher χ∗ is generated by using a random symmetric key K0 in experiment G1. Meanwhile, the other cipher χ=χ∗ is decrypted by using random key K0, which has no other role in experiment G1. Hence, in experiment G1, the adversary A plays an adaptive replayable chosen ciphertext attack against (RCCA) the signcryption scheme DEM in substance, so the following conclusion holds.Lemma 3.
There is a probabilistic adversaryA2, and its running time is equal to the running time of the adversary A, such that the following conclusion holds:(7)PrT1-12≤AdvDEM,A2RCCAλ.Proof.
The symmetric keyK0 was chosen uniformly, randomly, and independently, so the challenge cipher χ does not reveal related information about which message was encrypted. Hence, to gain success in experiment 2, the adversary must learn some information from the challenger cipher χ. We prove Lemma 3 by constructing a probabilistic adversary A2, who attacks the signcryption scheme DEM, and A2 provides an environment for the adversary A. Now, we describe their interactions:(i)
Setup: The adversary A2 runs receiver key generation algorithm (pkR,skR)←SKEM.GenR(1λ), runs sender key generation algorithm (pkS,skS)←SKEM.GenS(1λ), and sends (pkR,pkS) to A.(ii)
Stage 1: The adversary A inputs (pkR,pkS) and makes queries ciphertext c to a decryption oracle algorithm: K←SKEM.Dec(pkS,skR,χ), m←DEM.Dec(K,χ). If m=⊥, the decryption oracle algorithm responds to adversary A with m or reject symbol ⊥.(iii)
Challenge Stage: The adversary A inputs a public key pair (pkR,pkS) and sends (m0,m1) to the adversary A2. the adversary A2 chooses K1←RKD, runs ψ∗←SKEM.Enc(pkS,skR,K1), and sends the challenge c∗=(ψ∗,χ∗) to A. We notice that the symmetric key K1 was chosen as the encryption key of scheme DEM and embedded in cipher ψ∗, which is uniformly random and independent of each other.(iv)
Stage 2: The adversary inputs (pkR,pkS) and makes continuous queries c=(ψ,χ) to decryption oracle algorithm. Here, we require that adversary A2 cannot query (pkS,c∗) to the decryption oracle algorithm. However, we admit adversary A2 can make a query to the decryption oracle algorithm on (pkS′,C) for any cipher pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The adversary A2 uses the secret key skR to run the decryption oracle algorithm and answer the decryption query c=(ψ,χ) of adversary A with the following:
(a)
Ifψi=ψ∗, hence χi≠χ∗. Then The adversary A2 runs the decryption oracle K←SKEM.Dec(pkS,skR,χ). If K=⊥, the adversary A2 responds to A with ⊥ or else m←DEM.Dec(K,χ). If m∈{m0,m1}, the adversary A2 responds to A with text, or else A2 responds to A with m.(v)
Guess Stage: Finally, adversary A outputs a bit b′∈0,1 and A2 also outputs a bit b′.
This has completed the description of the adversaryA2. By our construction, it is obvious that the adversary A2 plays a perfectly simulated decryption for A, and whenever A gets success, so does A2. We have the following conclusion:(8)PrT1-12≤AdvDEM,A2RCCAλ.We can know that the advantage ofA in experiment0 is (9)AdvSKEM+DEM,ARCCAλ=PrT0-12≤2AdvSKEM,A1RCCAλ+AdvDEM,A2RCCAλ,which is negligible; we have proved Theorem 1.


## 3.3. The Hybrid Signcryption Scheme Tag-SKEM+DEM and Its RCCA Security

Definition 4 (signcryption scheme Tag-SKEM).
A signcryption schemeTag–KEM=(GenR,GenS,Tag–KEM.Enc,Tag–KEM.Dec) consists of the following three algorithms:(i)
Tag–KEM.GenS(1λ):Tag–KEM.GenS(1λ) is a PPT algorithm that inputs a security parameter 1λ and outputs a pair of public/private keys (skS,pkS).(ii)
Tag–KEM.GenR(1λ):TKEM.GenS(1λ) is a PPT algorithm that inputs a security parameter 1λ and outputs a pair of public/private keys (skR,pkR).(iii)
An encryption algorithmTag–KEM.Enc: It runs (ω,K)←Tag–KEM.Key(pkR,skS). Tag–KEM.Key(·) is a PPT algorithm that inputs the private key of sender skS and public key of receiver pkR and outputs one-time key K and Intermediate state information ω. Choose r←R0,1λ and compute ψ←TKEM.Enc(ω,r,pkR,skS,τ). Tag–KEM.Enc is a PPT algorithm that encrypts the key K (embedded in ω) into cipher ψ along with a tag τ∈T and returns a cipher ψ; here, τ is called a tag.(iv)
An decryption algorithmTag–KEM.Dec:K←Tag–KEM.Dec(pkS,skR,ψ,τ). TKEM.Dec is a deterministic decryption verification algorithm for a signcryption cipher, which inputs the receiver’s private key skR, the cipher c, the sender’s public key pkS, and a tag τ; the decryption oracle Tag–KEM.Dec returns a key K or reject symbol ⊥.Definition 5 (hybrid signcryption scheme Tag-SKEM+DEM).
The signcryption scheme(10)Tag–SKEM=GenR,GenS,TKEM.Enc,TKEM.Decis a asymmetric encryption scheme and the signcryption scheme DEM=(DEM.Enc,DEM.Dec) is a corresponding symmetric encryption scheme [18].Then the hybrid signcryption scheme(11)Tag–SKEM+DEM=Gen,signcrypt,unsigncryptcan be constructed as follows:(i)
Key generation algorithmGen(1λ): GenR(1λ) is a probabilistic receiver’s key generation algorithm that inputs a 1λ and outputs the receiver’s public/private key pair (pkR,skR); we write this as (pkR,skR)←GenR(1λ). GenS(1λ) is a probabilistic receiver key generation algorithm, which takes a as input a security parameter 1λ and as output a receiver’s public/private key pair (pkS,skS); we write this as (pkS,skS)←GenS(1λ).(ii)
An encryption algorithmsigncrypt:Tag–SKEM.Key(·) is a probabilistic algorithm that inputs the receiver’s public key pkS and outputs a symmetric key K∈KD and the internal state information ω, (ω,K)←Tag–SKEM.Key(pkS). Here KD is the scheme DEM’s key space. Then choose r←R0,1λ and compute χ←DEM.EncK(m), ψ←Tag–SKEM.Enc(pkS,skR,ω,r,χ). Finally, output the signcrypt cipher c=(ψ,χ).(iii)
A decryption algorithmunsigncrypt: First, it parses the cipher c to obtain ψ∥χ. Next, it computes K←Tag–SKEM.Dec(skR,pkR,ψ,χ) to obtain a symmetric key K and computes m←DEM.DecK(χ). Finally, it outputs the message m or “reject” symbol ⊥.


## 3.4. The RCCA Security of Hybrid Signcryption Scheme Tag-SKEM+DEM

Theorem 6.
The hybrid signcryption scheme(Tag–SKEM+DEM) is constructed from a scheme Tag–SKEM and a scheme DEM. If the signcryption scheme Tag–SKEM is IND–RCCA secure and the signcryption scheme DEM is IND–RCCA secure, then the hybrid signcryption scheme (Tag–SKEM+DEM) is also IND–RCCA secure. For every PPT adversary A, there are probabilistic adversary A1 and adversary A2, whose running times are essentially equal to that of adversary A, such that for all λ≥0, the following holds.(12)AdvTag-SKEM+DEM,ARCCAλ≤2AdvTag-KEM,A1RCCAλ+AdvDEM,A2RCCAλ+qsKD.Here, we assume the adversary at most makes theqs queries to the encryption-decryption oracle algorithm and KD is the scheme DEM’s key space.Proof. We prove the theorem by constructing a PPT adversary A who attacks the hybrid signcryption scheme Tag–SKEM+DEM with the following experiments. (We denote by Ti the event of the adversary A succeeding in the i-th game.)E x p e r i m e n t 0: This is the IND–RCCA experiment on the signcryption scheme Tag- SKEM+DEM, and this experiment is played between an adversary A and the challenger as follows:(i)
Setup: The adversary queries a key generation oracle. The challenger runs receiver key generation algorithm (pkR,skR)←Tag–SKEM.GenR(1λ), runs sender key generation algorithm (pkS,skS)←Tag–SKEM.GenS(1λ), and responds to the adversary A with (pkR,pkS).(ii)
Stage 1: The adversary A inputs (pkR,pkS) and makes continuous queries to decryption oracle algorithm. The adversary A sends a cipher c to the decryption oracle algorithm, and the decryption oracle algorithm runs K←Tag–SKEM.Dec(pkS,skR,χ,ψ), m←DEM.Dec(K,χ). If m=⊥, the decryption oracle algorithm responds to A1 with ⊥ or else responds to A1 with m.(iii)
Challenge stage: The adversary A1 inputs a public key pair (pkR,pkS) and queries (m0,m1) to an encryption oracle algorithm, and then the challenger runs (ω,K)←Tag–SKEM.Key(pkRskS), K∈KD. Then the challenger computes DEM.EncK(m0)=χ∗, Tag–SKEM.Enc(pkR,skS,ω,χ∗)=ψ∗ and sends the challenge cipher c∗=(ψ∗,χ∗) to the adversary A1.(iv)
Stage 2: The adversary A2 inputs a public key pair (pkRi,pkSi) and makes continuous queries c=(ψ,χ) to the challenger. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle. However, we admit that adversary A2 can make a query to the decryption oracle on (pkS′,C) for any public key pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The challenger runs decryption oracle. (13)K←Tag–SKEM.DecskRi,pkSi,ψ,χ,m←DEM.DecKχFinally, ifm∈m0,m1, A2 responds with text, or else A2 responds with m.(v)
Guess stage: In the end, the adversary A outputs a guess bit b′∈0,1.Naturally, the following holds:(14)AdvTag-SKEM+DEM,ARCCAλ=PrT0-12=Prb=b′-12.E x p e r i m e n t 1: We now modify Experiment0 to obtain a new Experiment1; this experiment is equal to the above experiment except that we just use a random key K0←RKD to encrypt the message m0 in step 3 of experiment0; hence, we get the following conclusion.Lemma 7.
There exists a probabilistic adversaryA1, and its running time is equal to that of adversary A, such that the following conclusion holds:(15)PrT1-PrT0≤AdvTag-SKEM,A1RCCAλ+qsKD.Here, we assume the adversary at most makes theqs queries to the encryption-decryption oracle algorithm.Proof.
We prove the lemma by constructing an adversaryA1 who attacks signcryption scheme Tag-SKEM. The adversary A1 simulates an environment for adversary A; their interactions can be described as follows: (i)
Stage 1: The adversary A2 was given (pkR,pkS,Kσ), and at the same time, (pkR,pkS) was sent to adversary A.(ii)
Stage 2: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries c to a decryption oracle algorithm Dec. The decryption oracle algorithm runs m←Dec(pkS,skR,c). Finally, if m=⊥, A responds with m or reject symbol ⊥.(iii)
Stage 3: The adversary A inputs a pair public key (pkR,pkS) and queries (m0,m1) to the encryption oracle, m0=m1. The adversary A1 requires the encryptions oracle of scheme Tag-SKEM to obtain (Kσ,ψ∗). The adversary A1 chooses b∈0,1 and computes DEM.EncS(Kσ,mb)=χ∗. Finally, the adversary A1 sends challenge cipher c∗=(ψ∗,χ∗) to the adversary A.(iv)
Stage 4: The adversary A inputs (pkRi,pkSi) and makes continuous calls c=(ψi,χi) to decryption oracle query. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle algorithm. However, we admit that adversary A2 can make a query to the decryption oracle on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any C≠C∗. The adversary A1 runs its own decryption oracle Tag–SKEM.Dec(pkS,skR,.) to answer the adversary A’s decryption query as follows:
(a)
If⊥ is returned, then the adversary A1 responds to A with ⊥.(b)
If⊥ is returned and χi≠χ∗, then A1 uses Kσ to decrypt the cipher χ.
(1)
Ifm0 or m0 is returned, then the adversary A1 responds to A with text.(2)
Otherwise,A1 responds to A with the result.(c)
Iftest is returned and cipher χi=χ∗, then the adversary A1 responds to A with text.(d)
IfK1 is returned, then the adversary uses K1 to decrypt the cipher χ.
(1)
Ifm0 or m0 is returned, then the adversary A1 responds to adversary A with text.(2)
Otherwise,A1 responds to adversary A with the result.(v)
Stage 5: In the end, the adversary A outputs a guess bit b′∈0,1, and A1 outputs a bit σ′=b′.
This has completed the description ofA1; it is clear that the adversary A1 plays a perfectly simulated decryption for A unless the cipher ψ∗ is decrypted to K1 and test is returned by the correct answer from the decryption oracle Tag–SKEM.Dec for every query. However, the probability of this event is 1/KD since in that case the key K1 is random and independent of the opinion of the adversary A1 for each such query. (i)
Ifσ=0, we can know that random key K0 is used for computing the cipher χ and the view of A is identical to that in Experiment0. Accordingly, Prb′=b∣σ=0=Pr[T2].(ii)
Ifσ=1, we can know that the key K1 is the correct key embedded in the cipher ψ and the view of A is equal to that in Experiment1. Accordingly, Prb′=b∣σ=1-PrT1≤qD/KD.
Thus,(16)AdvTag-SKEM,A1RCCAλ=Pr⁡T0-12=Prb=b′-12=12Prσ′=1∣σ=1-Prσ′=1∣σ=0=12Prb=b′∣σ=1-Prb=b′∣σ=0≥12PrT0-PrT1-qdKD.
Hence,(17)PrT1-PrT0≤2AdvTag-SKEM,A1RCCAλ+qsKD.Lemma2 is proved. Next, we show that the adversary A playing Experiment1 essentially conducts an IND-RCCA attack on the signcryption scheme DEM; we claim the following.Lemma 8.
There is a probabilistic adversaryA2, and its running time is equal to that of A, and the following conclusion holds:(18)PrT2-12≤AdvDEM,A2RCCAλ.Proof.
This can be shown by constructing an adversaryA2 who attacks the signcryption scheme DEM. The adversary A2 simulates the environment for adversary A; their interactions can be described as follows:(i)
Stage 1: The adversary A2 queries receiver’s key generation algorithm (pkR,skR)←Tag–SKEM.GenR(1λ), queries sender’s key generation algorithm (pkS,skS)←Tag–SKEM.GenS(1λ), and sends a public key pair (pkR,pkS) to A.(ii)
Stage 2: The adversary A inputs a public key pair (pkR,pkS) and makes continuous queries c to a decryption oracle algorithm: m←Dec(skR,pkS,c). In the end, adversary A is responded with m or reject symbol ⊥.(iii)
Stage 3: The adversary A inputs a pair public key (pkR,pkS) and sends (m0,m1) to the adversary A2; A2 queries (m0,m1) to the encryption oracle algorithm and then receives a challenge ciphertext χ∗. A2 runs (ω,K1)←Tag–SKEM.Key(pkR,skS) and then computes the following. (19)Tag–SKEM.Encpkω,χ∗=ψ∗In the end, the adversaryA2 submits the challenger cipher c∗=(ψ∗,χ∗) to adversary A.(iv)
Stage 4: The adversary A inputs a public key pair (pkRi,pkSi) and makes continuous queries c=(ψi,χi) to decryption oracle algorithm. Here, we require that adversary A2 is not admitted to query (pkS,c∗) to the decryption oracle. However, we admit that the adversary A2 is admitted to query the decryption oracle algorithm on (pkS′,C) for any pkS′≠pkSi and on (pkSi,C) for any cipher C≠C∗. The adversary A2 uses (pkSi,skRi) to decrypt the cipher c=(ψi,χi). The adversary A2 runs the decryption oracle. (20)Ki←Tag–SKEM.DecpkS,skR,ψi,χi,m←DEM.DecKiχiThe adversaryA2 answers A’s decryption query c=(ψi,χi) with the following:
(a)
IfKi=⊥, then A2 responds to A with ⊥.(b)
IfKi=K1 and χ=χ∗, then A2 responds to A with ′text′.(c)
IfKi=K1 and χ≠χ∗, then A2 responds to A with m.(d)
IfKi≠K1, then A2 uses Ki to decrypt the cipher χ.
(1)
Ifm∈m0,m1, then adversary A2 sends ′text′ to adversary A.(2)
Otherwise, adversaryA2 sends m to adversary A.Here, we notice that the keyK0 chosen by the signcryption scheme DEM’s encryption oracle and embedded in the cipher χ∗ is randomly chosen and independent.(v)
Stage 5: In the end, the adversary A outputs b′∈0,1, and the adversary A also outputs σ′=b′.
We have described the construction of the adversaryA2. A2 plays a perfect simulation Experiment for A; the view of A is equal to that in Experiment0 and Experiment1; hence, we have (21)PrT1-12≤AdvDEM,A2RCCAλ.Putting all the facts together, we have the following conclusion:(22)PrT0-12-PrT1-12≤AdvTag-SKEM+DEM,ARCCAλ+qsKDAdvTag-SKEM+DEM,ARCCAλ≤2AdvTag-SKEM,A1RCCAλ+qsKD+AdvTag-DEM,A2CCAλ.We have proved Theorem6.


## 4. Conclusion

We have examined theRCCA security of two representative hybrid signcryption schemes, i.e., SKEM+DEM [3] and Tag–SKEM+DEM [18], in this paper. We proved that the hybrid signcryption scheme SKEM+DEM is RCCA-secure if the signcryption scheme SKEM is RCCA-secure and the signcryption scheme DEM is RCCA-secure. Meanwhile, we showed that the hybrid encryption scheme Tag–SKEM+DEM can be RCCA-secure if the signcryption scheme Tag–SKEM is RCCA-secure and the scheme DEM is RCCA-secure.



---

*Source: 8646973-2018-11-12.xml*