# Cryptanalysis of a Certificateless Hybrid Signcryption Scheme and a Certificateless Encryption Scheme for Internet of Things

Authors: Shan Shan
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In wireless and mobile networks with limited storage and computing resources, certificateless cryptography has more advantages because of its low dependence on infrastructure and short security parameters. Recently, Gong et al. and Karati et al., respectively, proposed a new certificateless scheme in the Internet of Things environment, one of which is a certificateless hybrid signcryption scheme, and the other’s basis is a certificateless encryption scheme. Gong et al. and Karati et al. gave the formal security proof for their schemes, respectively. In this article, the attack algorithms against these two schemes are presented separately, thus proving that their schemes are insecure and not suitable for the Internet of Things environment.


---

## Body

## 1. Introduction

The primary problem to be solved in public key cryptography is how to certify the ownership of key pairs. In certificate-based public key infrastructure (PKI), a trusted third party called certificate authority (CA) issues certificates that provide a trusted link between the user’s identity and the public key based on digital signature technology. However, certificate management is very complex. Shamir [1] proposed the concept of an identity-based cryptosystem in 1984 to simplify certificate management issues. The main idea is that you can easily export a user’s public key from any string that corresponds to the user’s identifying information, such as name, phone number, and E-mail address. A private key generator (PKG) calculates the private keys using the master key and securely distributes these private keys to the users participating in the scheme. From an efficiency and convenience standpoint, an identity-based system may be a good alternative to a certificate-based system. But key escrow, which means the user’s private key is generated and known by PKG, is an inherent problem resulting in no authenticity and no privacy for the user in an identity-based system.As a variant of the identity-based cryptosystem, the concept of certificateless was proposed in 2003 to eliminate these problems simultaneously [2]. Each user in a certificateless scheme independently generates a secret key and gets another partial private key from the key generation center (KGC). Thus, each user’s secret consists of two parts, one obtained from a trusted third party (KGC) and one generated by the user himself. Certificateless scheme successfully solves the key escrow problem. In addition, this kind of scheme does not require the trusted third party to authenticate the corresponding public key ownership, which makes public key management very efficient. Because of these advantages, certificateless schemes have attracted wide attention and become one of the hot topics of public key cryptography. In recent years, certificateless signcryption [3, 4], certificateless hybrid signcryption [5, 6], certificateless multireceiver signcryption [7–9], certificateless generalized signcryption [10–14], and certificateless online/offline signcryption [15, 16] have been put forward one after another.In wireless and mobile networks with limited storage and computing resources, certificateless cryptography has more advantages because of its low dependence on infrastructure and short security parameters. However, while achieving low computational costs, many certificateless schemes proposed in the Internet of things environment [17–23] cannot simultaneously provide provable security. Kumar et al. [17] claimed that their newly proposed certificateless aggregate signature scheme is secure against both types of attackers. Zhan and Wang [24] proved that an attacker could forge a valid signature and valid aggregate signature. Lin et al. [25] pointed out that the certificateless signcryption (CL-SC) scheme proposed by Rastegari et al. [18] is insecure. Zhan et al. [26] analyzed a pairing-free CLAS scheme proposed in [20] and pointed out that the scheme is insecure. On this basis, to solve the security vulnerability, an improved scheme was proposed at the same time. Khan et al. [21] proposed a certificateless offline/online signature scheme. Unfortunately, their scheme is not secure against adaptive selective message attacks. Hussain et al. [27] proved that an adversary could forge a valid signature on a message by replacing a public key. Kasyoka et al. [28] showed the security vulnerabilities of Wei and Ma’s [19] signcryption scheme and proposed corresponding modifications to show how their scheme could be made more secure. Xu and Zeng [29] pointed out that the certificateless aggregate arbitrated signature scheme proposed by Lee et al. [22] is not secure for type-1 attackers that can replace user public keys. They also showed that Addobea et al.’s [23] offline-online certificateless signature scheme cannot achieve correctness. Therefore, the certificateless solution described above cannot be deployed in real Internet of things environment and mobile applications. Most of the schemes fail because the definition of the security model is not complete, and in the proving process, the adversary capability is not successfully reduced to solve difficult problems. There has been an ongoing effort in the Internet of things to make greater advances in security and performance.


### 1.1. Our Contributions

Recently, Gong et al. [30] and Karati et al. [31], respectively, proposed a new certificateless scheme in the Internet of things environment, one of which is a certificateless hybrid signcryption scheme, and the other’s basis is a certificateless encryption scheme. Their schemes were claimed to be secure, and the formal security was presented which reducing adversary capabilities in solving difficult problems. It is a pity that Gong et al.’s scheme and Karati et al.’s scheme are not secure in the case of internal attacks as shown in this paper. The attack algorithms against these two schemes are presented separately, thus proving that their schemes are insecure and not suitable for the Internet of things environment.


### 1.2. Paper Organization

In Section2, we give the cryptanalysis of Gong et al.’s scheme, and we give the cryptanalysis of Karati et al.’s certificateless encryption scheme for the industrial Internet of things in Section 3. Section 4 provides a conclusion.


## 1.1. Our Contributions

Recently, Gong et al. [30] and Karati et al. [31], respectively, proposed a new certificateless scheme in the Internet of things environment, one of which is a certificateless hybrid signcryption scheme, and the other’s basis is a certificateless encryption scheme. Their schemes were claimed to be secure, and the formal security was presented which reducing adversary capabilities in solving difficult problems. It is a pity that Gong et al.’s scheme and Karati et al.’s scheme are not secure in the case of internal attacks as shown in this paper. The attack algorithms against these two schemes are presented separately, thus proving that their schemes are insecure and not suitable for the Internet of things environment.


## 1.2. Paper Organization

In Section2, we give the cryptanalysis of Gong et al.’s scheme, and we give the cryptanalysis of Karati et al.’s certificateless encryption scheme for the industrial Internet of things in Section 3. Section 4 provides a conclusion.


## 2. Cryptanalysis of Gong et al.’s Certificateless Hybrid Signcryption Scheme

Because of the limitation of symmetric cryptography, public key-based authentication technology has attracted extensive attention. It provides secure communication and accesses mechanism for various applications. Compared with single-factor or two-factor protocols, multifactor schemes have been proven to achieve higher security levels. Wang et al. [32–34] have made a series of representative achievements in multifactor authentication. However, in some applications, people have to strike a balance between availability and security and adopt single-factor technology to achieve authentication, such as digital signature and digital signcryption. Signcryption can provide confidentiality and authentication at the same time and is widely used in many applications where multiple security features are required. Gong et al.’s scheme is a concrete certificateless hybrid signcryption scheme.


### 2.1. Gong et al.’s Scheme

As shown below, their scheme includes five algorithms altogether: Setup, Extract-Partial-Private-Key, Generate-User-Keys, Signcrypt, and Unsigncrypt.


#### 2.1.1. Setup

KGC runs the following algorithms:(i)
Generate two distinct cyclic groupsG1 (an additive cyclic group with a generator P) and G2 (a multiplicative cyclic group) of prime order qq≥2γ. e is a bilinear map.(ii)
Choosesx∈RZq∗, computes Ppub=eP,Px.(iii)
Chooses one-way hash functions ash1:0,1∗⟶Zq∗, h2:0,1∗2×G1×G22⟶Zq∗, h3:Zq∗⟶Zq∗, h4:G2×Zq∗×G1⟶0,1n, h5:G1⟶Zq∗.(iv)
Finally, keepsx safely and outputs params=P,Ppub,G1,G2,q,e,n,hi,E,D as the system parameter.


#### 2.1.2. Extract-Partial-Private-Key

Given the identity informationui, to generate the corresponding partial private key di, KGC runs the following algorithms:(i)
ComputesQi=h1ui(ii)
Sets the partial private keydi←xh1ui


#### 2.1.3. Generate-User-Keys

The user choosesxi∈RZq∗ and computes Pi=eP,Pxi which is the public key and sets the full private key si=xi,di.


#### 2.1.4. Signcrypt

A senderuA runs the following algorithms to generate the ciphertext.(i)
Choosesr∈RZq∗(ii)
ComputesR=rP, y=PBxAh5R and z=h3QB⋅dA, where QB=h1uB(iii)
ComputesK=h4y,z,R and c=EncKm(iv)
Computesf=h2uA,uB,R,PA,PB and s=r⋅z/xA⋅f(v)
Outputsσ=c,R,s as the ciphertext


#### 2.1.5. Unsigncrypt

A receiveruB runs the following algorithms for unsigncryption.(i)
Computesy=PAxBh5R, z=h3QA⋅dB, QA=h1uA and K=h4y,z,R.(ii)
Computes messagem/⊥←DecKc. If output ⊥, uB refuses the message.(iii)
Computesf=h2uA,uB,R,PA,PB.(iv)
ChecksPAs⋅f=ezP,R holds or not. If it holds, uB get m, else uB refuses the message.


### 2.2. Cryptanalysis of Gong et al.’s Scheme

#### 2.2.1. Attack Algorithm 1 (Internal Attacks to the Unforgeability)

Once receives a valid signcryption textσ=c,R,s, the receiver can impersonate the sender to generate signcryption text for any message m′ sent to him. The attack algorithm is described as follows:(i)
Choosesr′∈RZq∗(ii)
ComputesR′=r′R, z=h3QA⋅dB, and f=h2uA,uB,R,PA,PB(iii)
Computesy′=PAxBh5R′, z′=h3QA⋅dB, where QA=h1uA(iv)
ComputesK′=h4y′,z′,R′(v)
Computesc′=EncK′m′(vi)
Computesf′=h2uA,uB,R′,PA,PB and s′=s⋅f/z⋅r′⋅z′/f′(vii)
Send the ciphertextσ′=c′,R′,s′ of message m′


#### 2.2.2. Correctness

The signcryption ciphertextσ′=c′,R′,s′ is validly related with m′ as shown in the following.SinceR′=r′R=r′⋅r⋅P, y′=PAxBh5R′=PBxAh5R′, z′=h3QA⋅dB=h3QB⋅dA, the receiver can compute m′=DecK′c′ where K′=h4y′,z′,R′.The equationPAs′⋅f′=ez′P,R′ always holds since(1)s′=s⋅fz⋅r′⋅z′f′,=r⋅zxA⋅f⋅fz⋅r′⋅z′f′,=r⋅r′⋅z′xA⋅f′,(2)PAs′⋅f′=eP,PxA⋅r⋅r′⋅z′xA⋅f′⋅f′=eP,Pr⋅r′⋅z′=ez′P,r⋅r′⋅P=ez′P,R′.Thus,σ′=c′,R′,s′ is a valid signcryption ciphertext.Any user can launch the attack after receiving a valid signcryption ciphertext sent to him, so the nonrepudiation and source authentication that should be satisfied by the digital signcryption scheme cannot be realized.


#### 2.2.3. Attack Algorithm 2 (Internal Attacks to the Master Secret Key)

As shown in the Extract-Partial-Private-Key algorithm, KGC generatesdi by computing Qi=h1ui and di←xh1ui.Sincex is a random element in Zq∗ and h1 is a hash function that maps strings to distinct elements in Zq∗, any partial private key holder can compute the master secret key x by x=di⋅h1−1ui∈Zq∗ directly. Any security of the whole system cannot be realized when the master secret key is leaked. Any user that receives a valid partial private key can launch the attack.


## 2.1. Gong et al.’s Scheme

As shown below, their scheme includes five algorithms altogether: Setup, Extract-Partial-Private-Key, Generate-User-Keys, Signcrypt, and Unsigncrypt.


### 2.1.1. Setup

KGC runs the following algorithms:(i)
Generate two distinct cyclic groupsG1 (an additive cyclic group with a generator P) and G2 (a multiplicative cyclic group) of prime order qq≥2γ. e is a bilinear map.(ii)
Choosesx∈RZq∗, computes Ppub=eP,Px.(iii)
Chooses one-way hash functions ash1:0,1∗⟶Zq∗, h2:0,1∗2×G1×G22⟶Zq∗, h3:Zq∗⟶Zq∗, h4:G2×Zq∗×G1⟶0,1n, h5:G1⟶Zq∗.(iv)
Finally, keepsx safely and outputs params=P,Ppub,G1,G2,q,e,n,hi,E,D as the system parameter.


### 2.1.2. Extract-Partial-Private-Key

Given the identity informationui, to generate the corresponding partial private key di, KGC runs the following algorithms:(i)
ComputesQi=h1ui(ii)
Sets the partial private keydi←xh1ui


### 2.1.3. Generate-User-Keys

The user choosesxi∈RZq∗ and computes Pi=eP,Pxi which is the public key and sets the full private key si=xi,di.


### 2.1.4. Signcrypt

A senderuA runs the following algorithms to generate the ciphertext.(i)
Choosesr∈RZq∗(ii)
ComputesR=rP, y=PBxAh5R and z=h3QB⋅dA, where QB=h1uB(iii)
ComputesK=h4y,z,R and c=EncKm(iv)
Computesf=h2uA,uB,R,PA,PB and s=r⋅z/xA⋅f(v)
Outputsσ=c,R,s as the ciphertext


### 2.1.5. Unsigncrypt

A receiveruB runs the following algorithms for unsigncryption.(i)
Computesy=PAxBh5R, z=h3QA⋅dB, QA=h1uA and K=h4y,z,R.(ii)
Computes messagem/⊥←DecKc. If output ⊥, uB refuses the message.(iii)
Computesf=h2uA,uB,R,PA,PB.(iv)
ChecksPAs⋅f=ezP,R holds or not. If it holds, uB get m, else uB refuses the message.


## 2.1.1. Setup

KGC runs the following algorithms:(i)
Generate two distinct cyclic groupsG1 (an additive cyclic group with a generator P) and G2 (a multiplicative cyclic group) of prime order qq≥2γ. e is a bilinear map.(ii)
Choosesx∈RZq∗, computes Ppub=eP,Px.(iii)
Chooses one-way hash functions ash1:0,1∗⟶Zq∗, h2:0,1∗2×G1×G22⟶Zq∗, h3:Zq∗⟶Zq∗, h4:G2×Zq∗×G1⟶0,1n, h5:G1⟶Zq∗.(iv)
Finally, keepsx safely and outputs params=P,Ppub,G1,G2,q,e,n,hi,E,D as the system parameter.


## 2.1.2. Extract-Partial-Private-Key

Given the identity informationui, to generate the corresponding partial private key di, KGC runs the following algorithms:(i)
ComputesQi=h1ui(ii)
Sets the partial private keydi←xh1ui


## 2.1.3. Generate-User-Keys

The user choosesxi∈RZq∗ and computes Pi=eP,Pxi which is the public key and sets the full private key si=xi,di.


## 2.1.4. Signcrypt

A senderuA runs the following algorithms to generate the ciphertext.(i)
Choosesr∈RZq∗(ii)
ComputesR=rP, y=PBxAh5R and z=h3QB⋅dA, where QB=h1uB(iii)
ComputesK=h4y,z,R and c=EncKm(iv)
Computesf=h2uA,uB,R,PA,PB and s=r⋅z/xA⋅f(v)
Outputsσ=c,R,s as the ciphertext


## 2.1.5. Unsigncrypt

A receiveruB runs the following algorithms for unsigncryption.(i)
Computesy=PAxBh5R, z=h3QA⋅dB, QA=h1uA and K=h4y,z,R.(ii)
Computes messagem/⊥←DecKc. If output ⊥, uB refuses the message.(iii)
Computesf=h2uA,uB,R,PA,PB.(iv)
ChecksPAs⋅f=ezP,R holds or not. If it holds, uB get m, else uB refuses the message.


## 2.2. Cryptanalysis of Gong et al.’s Scheme

### 2.2.1. Attack Algorithm 1 (Internal Attacks to the Unforgeability)

Once receives a valid signcryption textσ=c,R,s, the receiver can impersonate the sender to generate signcryption text for any message m′ sent to him. The attack algorithm is described as follows:(i)
Choosesr′∈RZq∗(ii)
ComputesR′=r′R, z=h3QA⋅dB, and f=h2uA,uB,R,PA,PB(iii)
Computesy′=PAxBh5R′, z′=h3QA⋅dB, where QA=h1uA(iv)
ComputesK′=h4y′,z′,R′(v)
Computesc′=EncK′m′(vi)
Computesf′=h2uA,uB,R′,PA,PB and s′=s⋅f/z⋅r′⋅z′/f′(vii)
Send the ciphertextσ′=c′,R′,s′ of message m′


### 2.2.2. Correctness

The signcryption ciphertextσ′=c′,R′,s′ is validly related with m′ as shown in the following.SinceR′=r′R=r′⋅r⋅P, y′=PAxBh5R′=PBxAh5R′, z′=h3QA⋅dB=h3QB⋅dA, the receiver can compute m′=DecK′c′ where K′=h4y′,z′,R′.The equationPAs′⋅f′=ez′P,R′ always holds since(1)s′=s⋅fz⋅r′⋅z′f′,=r⋅zxA⋅f⋅fz⋅r′⋅z′f′,=r⋅r′⋅z′xA⋅f′,(2)PAs′⋅f′=eP,PxA⋅r⋅r′⋅z′xA⋅f′⋅f′=eP,Pr⋅r′⋅z′=ez′P,r⋅r′⋅P=ez′P,R′.Thus,σ′=c′,R′,s′ is a valid signcryption ciphertext.Any user can launch the attack after receiving a valid signcryption ciphertext sent to him, so the nonrepudiation and source authentication that should be satisfied by the digital signcryption scheme cannot be realized.


### 2.2.3. Attack Algorithm 2 (Internal Attacks to the Master Secret Key)

As shown in the Extract-Partial-Private-Key algorithm, KGC generatesdi by computing Qi=h1ui and di←xh1ui.Sincex is a random element in Zq∗ and h1 is a hash function that maps strings to distinct elements in Zq∗, any partial private key holder can compute the master secret key x by x=di⋅h1−1ui∈Zq∗ directly. Any security of the whole system cannot be realized when the master secret key is leaked. Any user that receives a valid partial private key can launch the attack.


## 2.2.1. Attack Algorithm 1 (Internal Attacks to the Unforgeability)

Once receives a valid signcryption textσ=c,R,s, the receiver can impersonate the sender to generate signcryption text for any message m′ sent to him. The attack algorithm is described as follows:(i)
Choosesr′∈RZq∗(ii)
ComputesR′=r′R, z=h3QA⋅dB, and f=h2uA,uB,R,PA,PB(iii)
Computesy′=PAxBh5R′, z′=h3QA⋅dB, where QA=h1uA(iv)
ComputesK′=h4y′,z′,R′(v)
Computesc′=EncK′m′(vi)
Computesf′=h2uA,uB,R′,PA,PB and s′=s⋅f/z⋅r′⋅z′/f′(vii)
Send the ciphertextσ′=c′,R′,s′ of message m′


## 2.2.2. Correctness

The signcryption ciphertextσ′=c′,R′,s′ is validly related with m′ as shown in the following.SinceR′=r′R=r′⋅r⋅P, y′=PAxBh5R′=PBxAh5R′, z′=h3QA⋅dB=h3QB⋅dA, the receiver can compute m′=DecK′c′ where K′=h4y′,z′,R′.The equationPAs′⋅f′=ez′P,R′ always holds since(1)s′=s⋅fz⋅r′⋅z′f′,=r⋅zxA⋅f⋅fz⋅r′⋅z′f′,=r⋅r′⋅z′xA⋅f′,(2)PAs′⋅f′=eP,PxA⋅r⋅r′⋅z′xA⋅f′⋅f′=eP,Pr⋅r′⋅z′=ez′P,r⋅r′⋅P=ez′P,R′.Thus,σ′=c′,R′,s′ is a valid signcryption ciphertext.Any user can launch the attack after receiving a valid signcryption ciphertext sent to him, so the nonrepudiation and source authentication that should be satisfied by the digital signcryption scheme cannot be realized.


## 2.2.3. Attack Algorithm 2 (Internal Attacks to the Master Secret Key)

As shown in the Extract-Partial-Private-Key algorithm, KGC generatesdi by computing Qi=h1ui and di←xh1ui.Sincex is a random element in Zq∗ and h1 is a hash function that maps strings to distinct elements in Zq∗, any partial private key holder can compute the master secret key x by x=di⋅h1−1ui∈Zq∗ directly. Any security of the whole system cannot be realized when the master secret key is leaked. Any user that receives a valid partial private key can launch the attack.


## 3. Cryptanalysis of Karati et al.’s Certificateless Encryption Scheme

In order to achieve more complex security goals, people often adopt the method of extending features on the basis of the general scheme. Karati et al.’s reliable data sharing protocol is based on a certificateless encryption scheme.


### 3.1. Karati et al.’s Scheme

As shown below, their scheme includes ten algorithms: Setup, Set-Secret-Value, Set-Public-Value, Set-Partial-Private-Key, Set-Full-Public-Key, Set-Full-Private-Key, Encrypt, Gen-TrapdoorTest-Trapdoor, and Decrypt.


#### 3.1.1. Setup

KGC runs the following algorithms.(i)
Generates three distinct cyclic groupsG1, G2, and G3, and e:G1×G2⟶G3 is a bilinear map(ii)
Chooses generatorg∈G1,h∈G2(iii)
ChoosesH1:0,1∗×G1×G2×G3⟶ℤp∗, H2:0,1∗⟶ℤp∗, and H3:G3⟶0,1n1+n2 for some n1 and n2, which are one-way hash functions(iv)
Computesg1=gxKGC for xKGC∈Rℤp∗(v)
KeepsMSK=xKGC safely and publishes params=p,g,g1,h,Hi


#### 3.1.2. Set-Secret-Value and Set-Public-Value

(i)
Choosesyi∈Rℤp∗ and sets secret-value SSi=yi(ii)
Generates public valuePVi=Pi1=hyi,Pi2=eg,h1/yi


#### 3.1.3. Set-Partial-Private-Key

KGC runs the following algorithms to generate the partial private key of devicei:(i)
Choosesβi∈Rℤp∗ and di∈Rℤp∗(ii)
ComputesPi3=gβi and αi=H1IDi,Pi3,Pi1,Pi2(iii)
Computesxi=1/αiβi+dixKGC and Di′=hxi(iv)
OutputsPPi=di,Pi3,Di′On receivingPPi securely, device i may check it by the equation ePi3αi⋅g1di,Di′=eg,h.


#### 3.1.4. Set-Full-Public-Key and Set-Full-Private-Key

The full public key of Devicei can be expressed as PKi=Pi1,Pi2,Pi3, and the full private key can be expressed as SKi=yi,di,Di=Di′1/yi.


#### 3.1.5. Encrypt

Given the messagemi and keyword wij∈0,1n3, a sender, whose private key is SKs, runs the following algorithms to generate a ciphertext sending to receiver R with public key PKr.(i)
Choosesu∈Rℤp∗ and σ∈R0,1n2(ii)
SetsCi=ci1=Pr3uαr,ci2=g1u,ci3=mi‖σ⊕H3Pr2u(iii)
Computesv=H1σ‖wij‖ys,g,h,Ps2, Φij=ϕij1,ϕij2, where ϕij1=g1⋅gH2wij‖αs‖αrv and ϕij2=Pr1vys(iv)
OutputsCi,Φij,θij for θij=H2mi‖σ‖wij


#### 3.1.6. Gen-Trapdoor

Given a tester’s private-public key pairt∈Rℤp∗,Pt1=h′,Pt2=eg,h1/t, receiver R runs the following algorithms to generate a trapdoor Γik=τik1,τik2.(i)
Computesv′=H1σ′‖wik‖yr,g,h,Pr2(ii)
Computesτik1=g1⋅gH2wik‖αs‖αrv′ and τik2=Ps1v′yr/H1αr,g,Pt1yr,Pr2 for σ′∈0,1n1


#### 3.1.7. Test-Trapdoor

The tester computesv′′=H1αr,g,Pr1t,Pr2 and retrieves Ci if the condition eϕij1,τik2v′′=eτik1,ϕij2 holds.


#### 3.1.8. Decrypt

Given a keywordwik, SKr=yr,dr,Dr, Ci, the receiver computes δ2=eci1ci2dr,Dr and δ1=mi‖σ=ci3⊕H3δ2. The first n1 bit of δ1 is returned as mi′ if θij=H2δ1‖wik.


### 3.2. Cryptanalysis of Karati et al.’s Scheme

To show the usability, Karati et al. defined their scheme asM,C,W,Γ-KDCLEKS. We noticed that if the sender sends a message directly without any keyword, M,C,⊥,⊥-KDCLEKS is a common certificateless encryption scheme, which can be marked as M,C-KDCLEKS.In this section, it will be shown that the encryption algorithmM,C-KDCLEKS is not secure under public-key replacement attacks launched by an adversary AI.


#### 3.2.1. Attack Algorithm 1 (Internal Attacks to the Partial Private Key)

Assume the following conditions a user declares his public value asPVj=Pj1=hyj,Pj2=eg,h1/yj. Once AI receives a valid partial private key PPi=di,Pi3,Di′, it can calculate and generate a partial private key for this user as follows:(1)
ComputePj3=Pi3αi and αj=H1IDj,Pj3,Pj1,Pj2(2)
Computedj=αj⋅di(3)
ComputeDj′=Di′1/αj


#### 3.2.2. Correctness

PPj=dj,Pj3,Dj′ is a valid partial private key related to public value PVj as shown in the following equation:(3)ePj3αj⋅g1dj,Dj′=ePi3αiαj⋅g1αj⋅di,Di′1/αj=egβiαi⋅g1di,hxi=egαiβi⋅gdixKGC,h1/αiβi+dixKGC=eg,h.Thus,PPj=dj,Pj3,Dj′ can always be accepted as a valid partial private key related to public value PVj. Any user that receives a valid partial private key can launch the attack. This means that the user’s partial private key can be forged, leading to the lack of availability.


#### 3.2.3. Attack Algorithm 2 (Internal Attacks to the Confidentiality)

OnceAI receives a valid Full-Public-Key PKi=Pi1,Pi2,Pi3 and corresponding Full-Private-Key SKi=yi,di,Di, he can decrypt the ciphertext of any user J with IDj through public key replacement attacks. The attack algorithm is described as follows:(1)
Select random parametery′∈Rℤp∗, and compute Pj1=Pi1y′=hyi⋅y′, Pj2=Pi21/y′=eg,h1/yi⋅y′ and Pj3=Pi3αi where αi=H1IDi,Pi3,Pi1,Pi2(2)
Replace the public key of userJ with the value PKj=Pj1,Pj2,Pj3On inputsparams and receiver J′ s public key PKJ with message mj∈0,1n1, the sender selects σ∈R0,1n2, u∈Rℤp∗ and sets Cj=cj1,cj2,cj3, where cj1=Pj3uαj, cj2=g1u, cj3=mj‖σ⊕H3Pj2u where αj=H1IDj,Pj3,Pj1,Pj2. Finally, the sender outputs Cj as the ciphertext.Given the ciphertextCj, AI can successfully decrypt it using the following algorithm:(1)
Computeαj=H1IDj,Pj3,Pj1,Pj2(2)
Computeyj=yi⋅y′, dj=αj⋅di, Dj=Di′1/αj⋅yi⋅y′(3)
Computeδ1=mj‖σ=cj3⊕H3δ2, where δ2=ecj1cj2dj,Dj


#### 3.2.4. Correctness

The decryption process is always successful as shown in the following equation:(4)δ2=ecj1cj2dj,Dj=ePi3u⋅αiαj⋅g1u⋅dj,Di′1/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCdj,hxi/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCαjdi,h1/βiαiαj+xKGCαjdiyi⋅y′=eg,hu/yi⋅y′=Pj2u.Thus,AI reveals mj‖σ=cj3⊕H3δ2 with probability 1. This attack can be launched by a user who receives any legal partial private key sent to him, and he can decrypt the ciphertext of any user through public key replacement attacks without knowing the master secret MSK. This means that any user’s public key can be replaced, and the message can be revealed by the attacker, leading to the lack of confidentiality.


## 3.1. Karati et al.’s Scheme

As shown below, their scheme includes ten algorithms: Setup, Set-Secret-Value, Set-Public-Value, Set-Partial-Private-Key, Set-Full-Public-Key, Set-Full-Private-Key, Encrypt, Gen-TrapdoorTest-Trapdoor, and Decrypt.


### 3.1.1. Setup

KGC runs the following algorithms.(i)
Generates three distinct cyclic groupsG1, G2, and G3, and e:G1×G2⟶G3 is a bilinear map(ii)
Chooses generatorg∈G1,h∈G2(iii)
ChoosesH1:0,1∗×G1×G2×G3⟶ℤp∗, H2:0,1∗⟶ℤp∗, and H3:G3⟶0,1n1+n2 for some n1 and n2, which are one-way hash functions(iv)
Computesg1=gxKGC for xKGC∈Rℤp∗(v)
KeepsMSK=xKGC safely and publishes params=p,g,g1,h,Hi


### 3.1.2. Set-Secret-Value and Set-Public-Value

(i)
Choosesyi∈Rℤp∗ and sets secret-value SSi=yi(ii)
Generates public valuePVi=Pi1=hyi,Pi2=eg,h1/yi


### 3.1.3. Set-Partial-Private-Key

KGC runs the following algorithms to generate the partial private key of devicei:(i)
Choosesβi∈Rℤp∗ and di∈Rℤp∗(ii)
ComputesPi3=gβi and αi=H1IDi,Pi3,Pi1,Pi2(iii)
Computesxi=1/αiβi+dixKGC and Di′=hxi(iv)
OutputsPPi=di,Pi3,Di′On receivingPPi securely, device i may check it by the equation ePi3αi⋅g1di,Di′=eg,h.


### 3.1.4. Set-Full-Public-Key and Set-Full-Private-Key

The full public key of Devicei can be expressed as PKi=Pi1,Pi2,Pi3, and the full private key can be expressed as SKi=yi,di,Di=Di′1/yi.


### 3.1.5. Encrypt

Given the messagemi and keyword wij∈0,1n3, a sender, whose private key is SKs, runs the following algorithms to generate a ciphertext sending to receiver R with public key PKr.(i)
Choosesu∈Rℤp∗ and σ∈R0,1n2(ii)
SetsCi=ci1=Pr3uαr,ci2=g1u,ci3=mi‖σ⊕H3Pr2u(iii)
Computesv=H1σ‖wij‖ys,g,h,Ps2, Φij=ϕij1,ϕij2, where ϕij1=g1⋅gH2wij‖αs‖αrv and ϕij2=Pr1vys(iv)
OutputsCi,Φij,θij for θij=H2mi‖σ‖wij


### 3.1.6. Gen-Trapdoor

Given a tester’s private-public key pairt∈Rℤp∗,Pt1=h′,Pt2=eg,h1/t, receiver R runs the following algorithms to generate a trapdoor Γik=τik1,τik2.(i)
Computesv′=H1σ′‖wik‖yr,g,h,Pr2(ii)
Computesτik1=g1⋅gH2wik‖αs‖αrv′ and τik2=Ps1v′yr/H1αr,g,Pt1yr,Pr2 for σ′∈0,1n1


### 3.1.7. Test-Trapdoor

The tester computesv′′=H1αr,g,Pr1t,Pr2 and retrieves Ci if the condition eϕij1,τik2v′′=eτik1,ϕij2 holds.


### 3.1.8. Decrypt

Given a keywordwik, SKr=yr,dr,Dr, Ci, the receiver computes δ2=eci1ci2dr,Dr and δ1=mi‖σ=ci3⊕H3δ2. The first n1 bit of δ1 is returned as mi′ if θij=H2δ1‖wik.


## 3.1.1. Setup

KGC runs the following algorithms.(i)
Generates three distinct cyclic groupsG1, G2, and G3, and e:G1×G2⟶G3 is a bilinear map(ii)
Chooses generatorg∈G1,h∈G2(iii)
ChoosesH1:0,1∗×G1×G2×G3⟶ℤp∗, H2:0,1∗⟶ℤp∗, and H3:G3⟶0,1n1+n2 for some n1 and n2, which are one-way hash functions(iv)
Computesg1=gxKGC for xKGC∈Rℤp∗(v)
KeepsMSK=xKGC safely and publishes params=p,g,g1,h,Hi


## 3.1.2. Set-Secret-Value and Set-Public-Value

(i)
Choosesyi∈Rℤp∗ and sets secret-value SSi=yi(ii)
Generates public valuePVi=Pi1=hyi,Pi2=eg,h1/yi


## 3.1.3. Set-Partial-Private-Key

KGC runs the following algorithms to generate the partial private key of devicei:(i)
Choosesβi∈Rℤp∗ and di∈Rℤp∗(ii)
ComputesPi3=gβi and αi=H1IDi,Pi3,Pi1,Pi2(iii)
Computesxi=1/αiβi+dixKGC and Di′=hxi(iv)
OutputsPPi=di,Pi3,Di′On receivingPPi securely, device i may check it by the equation ePi3αi⋅g1di,Di′=eg,h.


## 3.1.4. Set-Full-Public-Key and Set-Full-Private-Key

The full public key of Devicei can be expressed as PKi=Pi1,Pi2,Pi3, and the full private key can be expressed as SKi=yi,di,Di=Di′1/yi.


## 3.1.5. Encrypt

Given the messagemi and keyword wij∈0,1n3, a sender, whose private key is SKs, runs the following algorithms to generate a ciphertext sending to receiver R with public key PKr.(i)
Choosesu∈Rℤp∗ and σ∈R0,1n2(ii)
SetsCi=ci1=Pr3uαr,ci2=g1u,ci3=mi‖σ⊕H3Pr2u(iii)
Computesv=H1σ‖wij‖ys,g,h,Ps2, Φij=ϕij1,ϕij2, where ϕij1=g1⋅gH2wij‖αs‖αrv and ϕij2=Pr1vys(iv)
OutputsCi,Φij,θij for θij=H2mi‖σ‖wij


## 3.1.6. Gen-Trapdoor

Given a tester’s private-public key pairt∈Rℤp∗,Pt1=h′,Pt2=eg,h1/t, receiver R runs the following algorithms to generate a trapdoor Γik=τik1,τik2.(i)
Computesv′=H1σ′‖wik‖yr,g,h,Pr2(ii)
Computesτik1=g1⋅gH2wik‖αs‖αrv′ and τik2=Ps1v′yr/H1αr,g,Pt1yr,Pr2 for σ′∈0,1n1


## 3.1.7. Test-Trapdoor

The tester computesv′′=H1αr,g,Pr1t,Pr2 and retrieves Ci if the condition eϕij1,τik2v′′=eτik1,ϕij2 holds.


## 3.1.8. Decrypt

Given a keywordwik, SKr=yr,dr,Dr, Ci, the receiver computes δ2=eci1ci2dr,Dr and δ1=mi‖σ=ci3⊕H3δ2. The first n1 bit of δ1 is returned as mi′ if θij=H2δ1‖wik.


## 3.2. Cryptanalysis of Karati et al.’s Scheme

To show the usability, Karati et al. defined their scheme asM,C,W,Γ-KDCLEKS. We noticed that if the sender sends a message directly without any keyword, M,C,⊥,⊥-KDCLEKS is a common certificateless encryption scheme, which can be marked as M,C-KDCLEKS.In this section, it will be shown that the encryption algorithmM,C-KDCLEKS is not secure under public-key replacement attacks launched by an adversary AI.


### 3.2.1. Attack Algorithm 1 (Internal Attacks to the Partial Private Key)

Assume the following conditions a user declares his public value asPVj=Pj1=hyj,Pj2=eg,h1/yj. Once AI receives a valid partial private key PPi=di,Pi3,Di′, it can calculate and generate a partial private key for this user as follows:(1)
ComputePj3=Pi3αi and αj=H1IDj,Pj3,Pj1,Pj2(2)
Computedj=αj⋅di(3)
ComputeDj′=Di′1/αj


### 3.2.2. Correctness

PPj=dj,Pj3,Dj′ is a valid partial private key related to public value PVj as shown in the following equation:(3)ePj3αj⋅g1dj,Dj′=ePi3αiαj⋅g1αj⋅di,Di′1/αj=egβiαi⋅g1di,hxi=egαiβi⋅gdixKGC,h1/αiβi+dixKGC=eg,h.Thus,PPj=dj,Pj3,Dj′ can always be accepted as a valid partial private key related to public value PVj. Any user that receives a valid partial private key can launch the attack. This means that the user’s partial private key can be forged, leading to the lack of availability.


### 3.2.3. Attack Algorithm 2 (Internal Attacks to the Confidentiality)

OnceAI receives a valid Full-Public-Key PKi=Pi1,Pi2,Pi3 and corresponding Full-Private-Key SKi=yi,di,Di, he can decrypt the ciphertext of any user J with IDj through public key replacement attacks. The attack algorithm is described as follows:(1)
Select random parametery′∈Rℤp∗, and compute Pj1=Pi1y′=hyi⋅y′, Pj2=Pi21/y′=eg,h1/yi⋅y′ and Pj3=Pi3αi where αi=H1IDi,Pi3,Pi1,Pi2(2)
Replace the public key of userJ with the value PKj=Pj1,Pj2,Pj3On inputsparams and receiver J′ s public key PKJ with message mj∈0,1n1, the sender selects σ∈R0,1n2, u∈Rℤp∗ and sets Cj=cj1,cj2,cj3, where cj1=Pj3uαj, cj2=g1u, cj3=mj‖σ⊕H3Pj2u where αj=H1IDj,Pj3,Pj1,Pj2. Finally, the sender outputs Cj as the ciphertext.Given the ciphertextCj, AI can successfully decrypt it using the following algorithm:(1)
Computeαj=H1IDj,Pj3,Pj1,Pj2(2)
Computeyj=yi⋅y′, dj=αj⋅di, Dj=Di′1/αj⋅yi⋅y′(3)
Computeδ1=mj‖σ=cj3⊕H3δ2, where δ2=ecj1cj2dj,Dj


### 3.2.4. Correctness

The decryption process is always successful as shown in the following equation:(4)δ2=ecj1cj2dj,Dj=ePi3u⋅αiαj⋅g1u⋅dj,Di′1/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCdj,hxi/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCαjdi,h1/βiαiαj+xKGCαjdiyi⋅y′=eg,hu/yi⋅y′=Pj2u.Thus,AI reveals mj‖σ=cj3⊕H3δ2 with probability 1. This attack can be launched by a user who receives any legal partial private key sent to him, and he can decrypt the ciphertext of any user through public key replacement attacks without knowing the master secret MSK. This means that any user’s public key can be replaced, and the message can be revealed by the attacker, leading to the lack of confidentiality.


## 3.2.1. Attack Algorithm 1 (Internal Attacks to the Partial Private Key)

Assume the following conditions a user declares his public value asPVj=Pj1=hyj,Pj2=eg,h1/yj. Once AI receives a valid partial private key PPi=di,Pi3,Di′, it can calculate and generate a partial private key for this user as follows:(1)
ComputePj3=Pi3αi and αj=H1IDj,Pj3,Pj1,Pj2(2)
Computedj=αj⋅di(3)
ComputeDj′=Di′1/αj


## 3.2.2. Correctness

PPj=dj,Pj3,Dj′ is a valid partial private key related to public value PVj as shown in the following equation:(3)ePj3αj⋅g1dj,Dj′=ePi3αiαj⋅g1αj⋅di,Di′1/αj=egβiαi⋅g1di,hxi=egαiβi⋅gdixKGC,h1/αiβi+dixKGC=eg,h.Thus,PPj=dj,Pj3,Dj′ can always be accepted as a valid partial private key related to public value PVj. Any user that receives a valid partial private key can launch the attack. This means that the user’s partial private key can be forged, leading to the lack of availability.


## 3.2.3. Attack Algorithm 2 (Internal Attacks to the Confidentiality)

OnceAI receives a valid Full-Public-Key PKi=Pi1,Pi2,Pi3 and corresponding Full-Private-Key SKi=yi,di,Di, he can decrypt the ciphertext of any user J with IDj through public key replacement attacks. The attack algorithm is described as follows:(1)
Select random parametery′∈Rℤp∗, and compute Pj1=Pi1y′=hyi⋅y′, Pj2=Pi21/y′=eg,h1/yi⋅y′ and Pj3=Pi3αi where αi=H1IDi,Pi3,Pi1,Pi2(2)
Replace the public key of userJ with the value PKj=Pj1,Pj2,Pj3On inputsparams and receiver J′ s public key PKJ with message mj∈0,1n1, the sender selects σ∈R0,1n2, u∈Rℤp∗ and sets Cj=cj1,cj2,cj3, where cj1=Pj3uαj, cj2=g1u, cj3=mj‖σ⊕H3Pj2u where αj=H1IDj,Pj3,Pj1,Pj2. Finally, the sender outputs Cj as the ciphertext.Given the ciphertextCj, AI can successfully decrypt it using the following algorithm:(1)
Computeαj=H1IDj,Pj3,Pj1,Pj2(2)
Computeyj=yi⋅y′, dj=αj⋅di, Dj=Di′1/αj⋅yi⋅y′(3)
Computeδ1=mj‖σ=cj3⊕H3δ2, where δ2=ecj1cj2dj,Dj


## 3.2.4. Correctness

The decryption process is always successful as shown in the following equation:(4)δ2=ecj1cj2dj,Dj=ePi3u⋅αiαj⋅g1u⋅dj,Di′1/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCdj,hxi/αj⋅yi⋅y′=egu⋅βiαiαj+xKGCαjdi,h1/βiαiαj+xKGCαjdiyi⋅y′=eg,hu/yi⋅y′=Pj2u.Thus,AI reveals mj‖σ=cj3⊕H3δ2 with probability 1. This attack can be launched by a user who receives any legal partial private key sent to him, and he can decrypt the ciphertext of any user through public key replacement attacks without knowing the master secret MSK. This means that any user’s public key can be replaced, and the message can be revealed by the attacker, leading to the lack of confidentiality.


## 4. Conclusion

Gong et al. gave a formal security proof in the random oracle model, and Karati et al. proved their scheme is secure against adversaries. Unfortunately, we noticed that in Gong et al.’s scheme, internal users can forge the signcryption ciphertext sent to them, the nonrepudiation and source authentication that should be satisfied by the digital signcryption scheme cannot be realized. The more serious is that any partial private key holder can directly calculate the master secret key, which leads to the failure to implement security features. Any user who obtains a partial private key in Karati et al.’s basic certificateless encryption scheme can either forge the partial private key of another user or replace the public key of another user to decrypt the ciphertext. Therefore, their solutions are insecure and not suitable for the Internet of things environment.



---

*Source: 6174031-2022-07-13.xml*