# IBE-Signal: Reshaping Signal into a MITM-Attack-Resistant Protocol

Authors: Shiqi Liu; Yan Shao; Hanbo Luo; Hong Di
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The Signal Protocol is one of the most popular privacy protocols today for protecting Internet chats and supports end-to-end encryption. Nevertheless, despite its many advantages, the Signal Protocol is not resistant to Man-In-The-Middle (MITM) attacks because a malicious server can distribute the forged identity-based public keys during the user registration phase. To address this problem, we proposed the IBE-Signal scheme that replaced the Extended Triple Diffie–Hellman (X3DH) key agreement protocol with enhanced Identity-Based Encryption (IBE). Specifically, the adoption of verifiable parameter initialization ensures the authenticity of system parameters. At the same time, the Identity-Based Signature (IBS) enables our scheme to support mutual authentication. Moreover, we proposed a distributed key generation mechanism that served as a risk decentralization to mitigate IBE’s key escrow problem. Besides, the proposed revocable IBE scheme is used for the revocation problem. Notably, the IND-ID-CPA security of the IBE-Signal scheme is proven under the random oracle model. Compared with the existing schemes, our scheme provided new security features of mutual authentication, perfect forward secrecy, post-compromise security, and key revocation. Experiments showed that the computational overhead is lower than that of other schemes when the Cloud Privacy Centers (CPCs) number is less than 8.


---

## Body

## 1. Introduction

Revelations of mass surveillance of communications have made consumers more privacy-aware. Scientists and developers have proposed security techniques for end-users even if they do not trust the service providers fully [1]. The Signal Protocol is a cryptographic protocol that secures the text messages of billions of people. It provides end-to-end encryption and is applied by secure communication tools such as WhatsApp, Facebook Messenger, and Microsoft Skype [2, 3]. The information of applications with the Signal Protocol and their monthly active users are shown in Table 1.Table 1
The information of applications and their monthly active users.
Software using the signal protocolStatistical deadlineMonthly active usersSignal [5]202140,000,000WhatsApp [6]20212,000,000,000Facebook messenger [7]20202,770,000,000Skype [8]2019300,000,000The Signal Protocol consists of two main subalgorithms, X3DH and Double Ratchet. X3DH generates many sets of ephemeral key pairs for each user in addition to the permanent keys. Then a shared key is created for users by combining ephemeral and permanent key pairs. The Double Ratchet algorithm contains two ratchets [4], the Diffie–Hellman ratchet and the Symmetric-key ratchet. The Symmetric-key ratchet uses the key derivation function (KDF) chain to derive new keys. It offers a previous-key-based key to encrypt each message and attempt to provide Perfect Forward Secrecy (PFS). Even if an attacker cracks the key of one message, the keys of previous messages cannot be derived inversely. The included Diffie–Hellman ratchet aims at ensuring Post-compromise Security (PCS). Therefore, the Double Ratchet algorithm satisfies both PFS and PCS. Neither the keys generated before the key K nor after can be calculated when K is compromised.Although having PFS and PCS, Signal Protocol cannot resist MITM attacks due to X3DH’s key distribution problem. Since there is no public key authentication in X3DH, the server can be an attacker against the system itself or a collaborator of the adversary.The developers did consider the shortcomings of Signal Protocol to protect against MITM attacks and made some refinements. So each chat has a unique safety number [9] that enables one to verify the security of messages and specific contacts. As shown in Figure 1, the safety number is a hash of identity generated locally by both communicators, usually in a QR code. If a safety number has been marked as verified, any change can be manually approved before sending a new message [9]. However, a better plan to prevent MITM attacks should be in advance, rather than doing detection when an attack has approached.Figure 1
Safety number in the signal application.It is unreasonable to believe that a server will duly alert when it is a potential attacker. Only the user actively verifies the safety number through a third-party channel is reliable. Schröder et al. [10] found that most users could not successfully verify each other’s safety numbers due to usability problems and incomplete mental models. Worsely, the Signal Protocol is not secure under a threat model with an untrusted server since much of the Signal Protocol’s functionality is on the server trusted premise.The existence of MITM attacks is essentially a lack of public-key authentication. We are considering replacing X3DH with Identity-Based Encryption (IBE) for improvement. IBE scheme is a public-key cryptosystem where any string representing the identity is a valid public key [11]. A user can generate a public key from a known unique identifier, such as a phone number. Then a trusted third-party server calculates the corresponding private key from the public key. This process eliminates the need to distribute the public key before exchanging encrypted data. The sender can generate the public key and encrypt the data simply by using the receiver’s unique identifier. Correspondingly, the receiver can generate the private key with the help of a trusted third-party server, the Private Key Generator (PKG).Blazy et al. [12] introduced IBS into the Signal Protocol to make it resistant to MITM attacks, but the problems [13–16] inherited in IBS/IBE are yet to be solved:The Authenticity of System Parameters Problem. In the BF-IBE scheme, the attacker can generate the public system parameters by himself to make the users mistakenly believe that the parameters are correct.One-Way Authentication Problem. Instant messaging protocols generally support mutual authentication, but BF-IBE only authenticates the recipient’s identity.Key Escrow Problem. The PKG generates the users’ private keys with the master key. For this reason, identity theft might occur since the PKG is available to sign any message with the users’ identities. Users may also slander the PKG for misusing their private keys for signing, which threatens the undeniability of the signature.Public Key Revocation Problem. A user can generate a new public-private key pair when his key is at risk or expire. However, the BF-IBE scheme is unavailable to revoke the user’s public key.


### 1.1. Our Contributions

Our advanced Signal Protocol has the following security features:Resist MITM attack. Our IBE-Signal scheme is resistant to MITM attacks by leveraging the IBE scheme. Furthermore, we fixed the problems inherited in IBS/IBE.The Authenticity of System Parameters. By introducing a verifiable parameter initialization technique, the public validation of parameters is guaranteed to ensure the correctness of parameters transmitted by the Key Generation Center (KGC) and Cloud Privacy Centers (CPCs).Mutual Authentication. Our IBE-Signal scheme supports mutual authentication by introducing an Identity-Based Signature (IBS).Secure Key Escrow. We used distributed key generation to solve the key escrow problem, inspired by the ESKI-IBE scheme proposed by Kumar et al. [17]. Moreover, we also used the KGC and the CPCs instead of one PKG. Compared with [17], we reduced the computational overhead since there is no need to negotiate parameters after an initial session.Resist User Slandering. The KGC and the CPCs own the master key share separately, which disenables an attacker from obtaining the complete key. Therefore, an attacker cannot decrypt the users’ ciphertexts or forge the users’ signatures, and users cannot defame the server for misusing their private key.Secure Key Issuing. The blind signature enables the KGC or the CPCs to issue the private key without seeing the actual information sent by the user.Key Revocation. We achieved efficient public key revocation by adopting Revocable IBE. This scheme proposed by Boldyreva et al. [18] is built on the Fuzzy IBE scheme and binary tree data structure.Perfect Forward Secrecy and Post‐compromise Security. Our scheme still retains the PFS and PCS of the Signal Protocol by introducing the concepts of session and connection in SSL protocol into our scheme and integrating the Double Ratchet algorithm into the CONNECTION part.IND-ID-CPA. We proved the IND-ID-CPA security of the IBE-Signal scheme under the random oracle model and the Bilinear Diffie–Hellman (BDH) assumption. With more powerful attackers, we gained a more compact reduction than [17] in a challenger-adversary game.


### 1.2. Related Work

The security proof of the Signal Protocol has always been a research hotspot. Cohn-Gordon et al. [19] analyzed the security of the Signal Protocol and other authenticated key exchange protocols. Van Dam [20] provided an automated analysis of the Signal Protocol. Frosch et al. [21] first proved that TextSecure (the predecessor of the Signal) achieves most of its claimed security goals if the key registration is secure. Alwen et al. [22] gave formal proof of the perfect forward secrecy and post-compromise security of the Signal Protocol. Cohn-Gordon et al. [1] analyzed the security of multistage key agreement protocols based on the Double Ratchet algorithm for the first time. In addition, Kobeissi et al. [23] verified the security of end-to-end cryptographic protocols like the Signal Protocol with automated tools.The Signal Protocol cannot resist MITM attacks when the key registration is insecure. There are many ways to resist MITM attacks. The traditional methods are Digital Signatures and Message Authentication Codes. Rivest and Shamir [24] proposed the interlock protocol to expose the eavesdropper of full-duplex communication. However, the interlock protocol increases the communication cost and is not suitable for half-duplex communication. Khader and Lai [25] proposed a method to resist MITM attacks in the Diffie–Hellman Key Exchange Protocol with the Geffe generator.The MITM attacks are due to the lack of public-key authentication, traditionally implemented by distributing public key certificates through the Public Key Infrastructure (PKI). In 1984, Shamir [15] proposed the IBE scheme to simplify the public key certificate management in the PKI. Boneh and Franklin [16] implemented a practical and functional IBE scheme, the BF-IBE scheme, based on bilinear pairings on elliptic curves in 2001. Goyal [26] introduced the Accountable Authority Identity-Based Encryption (A-IBE) scheme to reduce trust in the PKG as an effective solution for the key escrow problem. The A-IBE scheme was matured into the Black Box AIBE scheme by Goyal et al. [27]. Later, Garg et al. [28, 29] proposed the Registration-Based Encryption (RBE) scheme, aggregating the KGC and compactly compressing all users’ public keys into the master public key.


### 1.3. Organization

To begin, in Section2, we presented helpful preliminary information. Then, in Section 3, we detailed the construction of our approach. In Section 4, we analyzed the security features of the scheme. In Section 5, the IND-ID-CPA security of our scheme was proved. In Section 6, we analyzed the scheme’s performance and compared it with other schemes in performance and security. Finally, we concluded with comments on our work and limitations for future work in Section 7.


## 1.1. Our Contributions

Our advanced Signal Protocol has the following security features:Resist MITM attack. Our IBE-Signal scheme is resistant to MITM attacks by leveraging the IBE scheme. Furthermore, we fixed the problems inherited in IBS/IBE.The Authenticity of System Parameters. By introducing a verifiable parameter initialization technique, the public validation of parameters is guaranteed to ensure the correctness of parameters transmitted by the Key Generation Center (KGC) and Cloud Privacy Centers (CPCs).Mutual Authentication. Our IBE-Signal scheme supports mutual authentication by introducing an Identity-Based Signature (IBS).Secure Key Escrow. We used distributed key generation to solve the key escrow problem, inspired by the ESKI-IBE scheme proposed by Kumar et al. [17]. Moreover, we also used the KGC and the CPCs instead of one PKG. Compared with [17], we reduced the computational overhead since there is no need to negotiate parameters after an initial session.Resist User Slandering. The KGC and the CPCs own the master key share separately, which disenables an attacker from obtaining the complete key. Therefore, an attacker cannot decrypt the users’ ciphertexts or forge the users’ signatures, and users cannot defame the server for misusing their private key.Secure Key Issuing. The blind signature enables the KGC or the CPCs to issue the private key without seeing the actual information sent by the user.Key Revocation. We achieved efficient public key revocation by adopting Revocable IBE. This scheme proposed by Boldyreva et al. [18] is built on the Fuzzy IBE scheme and binary tree data structure.Perfect Forward Secrecy and Post‐compromise Security. Our scheme still retains the PFS and PCS of the Signal Protocol by introducing the concepts of session and connection in SSL protocol into our scheme and integrating the Double Ratchet algorithm into the CONNECTION part.IND-ID-CPA. We proved the IND-ID-CPA security of the IBE-Signal scheme under the random oracle model and the Bilinear Diffie–Hellman (BDH) assumption. With more powerful attackers, we gained a more compact reduction than [17] in a challenger-adversary game.


## 1.2. Related Work

The security proof of the Signal Protocol has always been a research hotspot. Cohn-Gordon et al. [19] analyzed the security of the Signal Protocol and other authenticated key exchange protocols. Van Dam [20] provided an automated analysis of the Signal Protocol. Frosch et al. [21] first proved that TextSecure (the predecessor of the Signal) achieves most of its claimed security goals if the key registration is secure. Alwen et al. [22] gave formal proof of the perfect forward secrecy and post-compromise security of the Signal Protocol. Cohn-Gordon et al. [1] analyzed the security of multistage key agreement protocols based on the Double Ratchet algorithm for the first time. In addition, Kobeissi et al. [23] verified the security of end-to-end cryptographic protocols like the Signal Protocol with automated tools.The Signal Protocol cannot resist MITM attacks when the key registration is insecure. There are many ways to resist MITM attacks. The traditional methods are Digital Signatures and Message Authentication Codes. Rivest and Shamir [24] proposed the interlock protocol to expose the eavesdropper of full-duplex communication. However, the interlock protocol increases the communication cost and is not suitable for half-duplex communication. Khader and Lai [25] proposed a method to resist MITM attacks in the Diffie–Hellman Key Exchange Protocol with the Geffe generator.The MITM attacks are due to the lack of public-key authentication, traditionally implemented by distributing public key certificates through the Public Key Infrastructure (PKI). In 1984, Shamir [15] proposed the IBE scheme to simplify the public key certificate management in the PKI. Boneh and Franklin [16] implemented a practical and functional IBE scheme, the BF-IBE scheme, based on bilinear pairings on elliptic curves in 2001. Goyal [26] introduced the Accountable Authority Identity-Based Encryption (A-IBE) scheme to reduce trust in the PKG as an effective solution for the key escrow problem. The A-IBE scheme was matured into the Black Box AIBE scheme by Goyal et al. [27]. Later, Garg et al. [28, 29] proposed the Registration-Based Encryption (RBE) scheme, aggregating the KGC and compactly compressing all users’ public keys into the master public key.


## 1.3. Organization

To begin, in Section2, we presented helpful preliminary information. Then, in Section 3, we detailed the construction of our approach. In Section 4, we analyzed the security features of the scheme. In Section 5, the IND-ID-CPA security of our scheme was proved. In Section 6, we analyzed the scheme’s performance and compared it with other schemes in performance and security. Finally, we concluded with comments on our work and limitations for future work in Section 7.


## 2. Preliminaries

We briefly introduced the background knowledge needed to read this paper, including Symmetric Bilinear Function, BDH Problem, X3DH Algorithm, BF-IBE Scheme, Hess’s IBS Scheme, and RIBE Scheme.


### 2.1. Notation

We defined a secure symmetric encryption algorithm asEnc. For EncM1,M2,M3,K, K is the key, and M1,M2,M3 are the messages to be encrypted. The symmetric decryption algorithm Dec and the signature algorithm Sign are given similar forms.


### 2.2. Symmetric Bilinear Function

Letq be a large prime, G1 is an additive group, and G2 is a multiplicative group of the same order q. Given a symmetric bilinear function from G1 to G2 as e:G1×G1⟶G2 and e satisfies the following properties:Bilinearity: ∀P,Q∈G1 and a,b∈Z, such that eaP,bQ=eP,Qab.Nondegeneracy: ∀P∈G1, such that eP,P≠1, that means the generator of G2 cannot be the identity element.Computability: ∀P,Q∈G1, there exists an effective algorithm to compute eP,Q.Symmetry: ∀P,Q∈G1, such that eP,Q=eQ,P.


### 2.3. BDH Problem

GivenP,aP,bP,cPa,b,c∈Zq∗, compute eP,Pabc∈G2, where e is a bilinear function, P is the generator on G1, and G1, G2 are two groups of the same order q[30]. Assume the algorithm Α is used to solve the BDH problem:(1)PrΑP,aP,bP,cP=eP,Pabc≥ε.


### 2.4. X3DH Algorithm

X3DH [31] is a tripartite key negotiation protocol where the two communicating parties go through a server to achieve asynchronous encrypted communication.Figure2 shows the specific design of the protocol. First, Bob registers his public key bundle to the server. When Alice wants to establish communication with Bob, she retrieves Bob’s public key bundle from the server. Then, Alice verifies the prekey signature and performs four Diffie–Hellman key exchanges in the order shown in Figure 3. Finally, she generates the shared key SK. Bob similarly generates SK, decrypts the message M1 and Alice’s safety number SN, and encrypts the message M2 and the locally calculated safety number SN. The server forwards it to Alice.Figure 2
The X3DH.Figure 3
TheSK generation process.Figure4 shows an example when the protocol is subjected to a MITM attack by a malicious server Trudy. Both parties in the protocol can get the safety number forwarded to each other by the server. However, it is still impossible to determine whether there is a MITM attack based on direct comparison results. Through the original channel comparison, the safety number will still be tampered with by the man in the middle.Figure 4
A MITM attack in X3DH.


### 2.5. BF-IBE Scheme

The public key of the BF-IBE [16] scheme is determined by the identity, and a trusted third-party PKG generates the private key.Setup: Suppose k is the security parameter, q is a large prime of k-bits, G1 is an additive group, and G2 is a multiplicative group where the order of both groups is q, e:G1×G1⟶G2 is a bilinear mapping. P is a generator of G1, H1:0,1∗⟶G1∗ and H2:G2∗⟶0,1n are two hash functions where n is the length of the message to be encrypted. The PKG picks s∈Zq∗ as the master key and computes the public key Ppub=sP. PKG keeps the public system parameter param=q,G1,G2,e,n,P,Ppub,H1,H2 and the secret s.Key generation: The public key corresponding to ID∈0,1∗ is QID=H1ID. The PKG computes the private key SID=sQID.Encryption: The public key of the receiver is QID. To encrypt M∈0,1n, calculate r←RZq∗, g=eQID,Ppub∈G2∗, C=rP,M⊕H2gr.Decryption: For the given ciphertext C=U,V and the private key SID, the receiver can decrypt C as M=V⊕H2eSID,U.


### 2.6. Hess’s IBS Scheme

The signature scheme used in this paper is Hess’s IBS scheme [32], and Hess gives the security proof of their scheme under the random oracle model. The scheme reduces the number of bilinear pair operations and outperforms Shamir’s scheme [33] and Jae Cha’s scheme [34] in terms of efficiency.Setup: Suppose q is a large prime, G1 is an additive group, and G2 is a multiplicative group where the order of both groups is q, e:G1×G1⟶G2 is a bilinear mapping. P is a generator of G1, H1:0,1∗⟶G1∗ and H2:0,1∗×G2∗⟶Zq∗ are two hash functions. The PKG picks s∈Zq∗ as the master key and computes the public key Ppub=sP. The PKG keeps the system parameter param=q,G1,G2,e,P,Ppub,H1,H2 public and s secret.Key generation: After the identity verification passes, the PKG computes the public key Q=H1ID based on the ID and the corresponding private key D=sH1ID=sQ.Sign: m is the message that needs to be signed, the signer randomly selects k∈Zq∗ and P1∈G1∗, computes r=eP1,Pk, V=H2m,r, and U=VD+kP1. σ=U,V is the signature for m.Verify: After receiving the signature σ=U,V, the verifier computes r=eU,PeQ,−PpubV where Q=H1ID. When H2m,r=V holds, the signature is valid.


### 2.7. RIBE Scheme

To make the IBE algorithm support efficient public key revocation, Boldyreva [18] et al. proposed the RIBE scheme. Each user corresponds to two attributes: identity and validity time of the public key, and therefore corresponds to two keys in RIBE: the private key and the key update. The core of RIBE is that only having two private keys can decrypt the message, while the PKG cannot update the key update to the user whose public key has been revoked. We only present the basic definition of RIBE here. For more details, please consult [18].Setup: S1κ,n⟶pk,mk,rl,st: n is the number of users, pk is the public parameters, mk is the master key, rl is the revocation list, and st is the binary tree representing states.Private key generation: SKpk,mk,ω,st⟶skω,st: ω is the identity, skω is the private key, and the state st is updated by this function.Key update generation: KUpk,mk,t,rl,st⟶kut: t is the validity time and kut is the key update.Decryption key generation: DKskω,kut⟶dkω,tor⊥: If the identity ω is revoked, then the function outputs ⊥; else outputs the decryption key dkω,t.Encryption: Epk,ω,t,m⟶c: t is when the encryption occurs, m is the plaintext, and c is the ciphertext.Decryption: Ddkω,t,c⟶mor⊥: If the ciphertext c is invalid, the function outputs ⊥; else outputs the plaintext m.Revocation: Rω,t,rl,st⟶rl: ω is the identity to be revoked, t is the revocation time, and rl is updated by this function.


## 2.1. Notation

We defined a secure symmetric encryption algorithm asEnc. For EncM1,M2,M3,K, K is the key, and M1,M2,M3 are the messages to be encrypted. The symmetric decryption algorithm Dec and the signature algorithm Sign are given similar forms.


## 2.2. Symmetric Bilinear Function

Letq be a large prime, G1 is an additive group, and G2 is a multiplicative group of the same order q. Given a symmetric bilinear function from G1 to G2 as e:G1×G1⟶G2 and e satisfies the following properties:Bilinearity: ∀P,Q∈G1 and a,b∈Z, such that eaP,bQ=eP,Qab.Nondegeneracy: ∀P∈G1, such that eP,P≠1, that means the generator of G2 cannot be the identity element.Computability: ∀P,Q∈G1, there exists an effective algorithm to compute eP,Q.Symmetry: ∀P,Q∈G1, such that eP,Q=eQ,P.


## 2.3. BDH Problem

GivenP,aP,bP,cPa,b,c∈Zq∗, compute eP,Pabc∈G2, where e is a bilinear function, P is the generator on G1, and G1, G2 are two groups of the same order q[30]. Assume the algorithm Α is used to solve the BDH problem:(1)PrΑP,aP,bP,cP=eP,Pabc≥ε.


## 2.4. X3DH Algorithm

X3DH [31] is a tripartite key negotiation protocol where the two communicating parties go through a server to achieve asynchronous encrypted communication.Figure2 shows the specific design of the protocol. First, Bob registers his public key bundle to the server. When Alice wants to establish communication with Bob, she retrieves Bob’s public key bundle from the server. Then, Alice verifies the prekey signature and performs four Diffie–Hellman key exchanges in the order shown in Figure 3. Finally, she generates the shared key SK. Bob similarly generates SK, decrypts the message M1 and Alice’s safety number SN, and encrypts the message M2 and the locally calculated safety number SN. The server forwards it to Alice.Figure 2
The X3DH.Figure 3
TheSK generation process.Figure4 shows an example when the protocol is subjected to a MITM attack by a malicious server Trudy. Both parties in the protocol can get the safety number forwarded to each other by the server. However, it is still impossible to determine whether there is a MITM attack based on direct comparison results. Through the original channel comparison, the safety number will still be tampered with by the man in the middle.Figure 4
A MITM attack in X3DH.


## 2.5. BF-IBE Scheme

The public key of the BF-IBE [16] scheme is determined by the identity, and a trusted third-party PKG generates the private key.Setup: Suppose k is the security parameter, q is a large prime of k-bits, G1 is an additive group, and G2 is a multiplicative group where the order of both groups is q, e:G1×G1⟶G2 is a bilinear mapping. P is a generator of G1, H1:0,1∗⟶G1∗ and H2:G2∗⟶0,1n are two hash functions where n is the length of the message to be encrypted. The PKG picks s∈Zq∗ as the master key and computes the public key Ppub=sP. PKG keeps the public system parameter param=q,G1,G2,e,n,P,Ppub,H1,H2 and the secret s.Key generation: The public key corresponding to ID∈0,1∗ is QID=H1ID. The PKG computes the private key SID=sQID.Encryption: The public key of the receiver is QID. To encrypt M∈0,1n, calculate r←RZq∗, g=eQID,Ppub∈G2∗, C=rP,M⊕H2gr.Decryption: For the given ciphertext C=U,V and the private key SID, the receiver can decrypt C as M=V⊕H2eSID,U.


## 2.6. Hess’s IBS Scheme

The signature scheme used in this paper is Hess’s IBS scheme [32], and Hess gives the security proof of their scheme under the random oracle model. The scheme reduces the number of bilinear pair operations and outperforms Shamir’s scheme [33] and Jae Cha’s scheme [34] in terms of efficiency.Setup: Suppose q is a large prime, G1 is an additive group, and G2 is a multiplicative group where the order of both groups is q, e:G1×G1⟶G2 is a bilinear mapping. P is a generator of G1, H1:0,1∗⟶G1∗ and H2:0,1∗×G2∗⟶Zq∗ are two hash functions. The PKG picks s∈Zq∗ as the master key and computes the public key Ppub=sP. The PKG keeps the system parameter param=q,G1,G2,e,P,Ppub,H1,H2 public and s secret.Key generation: After the identity verification passes, the PKG computes the public key Q=H1ID based on the ID and the corresponding private key D=sH1ID=sQ.Sign: m is the message that needs to be signed, the signer randomly selects k∈Zq∗ and P1∈G1∗, computes r=eP1,Pk, V=H2m,r, and U=VD+kP1. σ=U,V is the signature for m.Verify: After receiving the signature σ=U,V, the verifier computes r=eU,PeQ,−PpubV where Q=H1ID. When H2m,r=V holds, the signature is valid.


## 2.7. RIBE Scheme

To make the IBE algorithm support efficient public key revocation, Boldyreva [18] et al. proposed the RIBE scheme. Each user corresponds to two attributes: identity and validity time of the public key, and therefore corresponds to two keys in RIBE: the private key and the key update. The core of RIBE is that only having two private keys can decrypt the message, while the PKG cannot update the key update to the user whose public key has been revoked. We only present the basic definition of RIBE here. For more details, please consult [18].Setup: S1κ,n⟶pk,mk,rl,st: n is the number of users, pk is the public parameters, mk is the master key, rl is the revocation list, and st is the binary tree representing states.Private key generation: SKpk,mk,ω,st⟶skω,st: ω is the identity, skω is the private key, and the state st is updated by this function.Key update generation: KUpk,mk,t,rl,st⟶kut: t is the validity time and kut is the key update.Decryption key generation: DKskω,kut⟶dkω,tor⊥: If the identity ω is revoked, then the function outputs ⊥; else outputs the decryption key dkω,t.Encryption: Epk,ω,t,m⟶c: t is when the encryption occurs, m is the plaintext, and c is the ciphertext.Decryption: Ddkω,t,c⟶mor⊥: If the ciphertext c is invalid, the function outputs ⊥; else outputs the plaintext m.Revocation: Rω,t,rl,st⟶rl: ω is the identity to be revoked, t is the revocation time, and rl is updated by this function.


## 3. Scheme Definition

We first define the threat model of our IBE-Signal scheme, then introduce the framework of the whole scheme, and finally present the scheme’s construction in two parts.


### 3.1. Threat Model

As shown in Figure5, our model uses one KGC, multiple CPCs, and one Key Authority to replace the single PKG in the BF-IBE model shown in Figure 6. The KGC sets most system parameters, and the CPCs also have the private key share for risk reduction. The Key Authority is fully trusted and only responsible for public key revocation. In addition, our public key revocation feature is optional, and if the user turns it off, the Key Authority will no longer serve him.Figure 5
The IBE-Signal scheme’s threat model.Figure 6
The BF-IBE scheme’s threat model.We assume that an ambitious adversary can collude with the KGC andn-1 CPCs. In other words, at least one CPC in our scheme is credible. Corrupt KGC/n-1 CPCs can assign the partial private key to any identity submitted by the adversary. The adversary can launch a chosen-plaintext attack and can finally select an ID∗ to challenge. We allow the adversary to retrieve the partial private key from the KGC and n-1 partial private keys from the CPCs in this case. Before and after the challenge, the adversary can choose a random ID to query where ID≠ID∗. Furthermore, we allow the adversary to retrieve the partial private key from the KGC and n partial private keys from the CPCs in this case. This process can be repeated polynomial bounded times.Even with these capabilities, the adversary has a negligible advantage against our IBE-Signal scheme.


### 3.2. The Framework of the IBE-Signal Scheme

Like the SSL protocol [35], our IBE-Signal scheme contains parts of the SESSION and the CONNECTION. The SESSION part refers to a collection of parameters and encryption keys generated through a handshake between two communicating parties. In contrast, the CONNECTION part refers to a subsequent session established after the SESSION part using the shared key RK. The SESSION part is more overhead than the CONNECTION part for the server. Once the SESSION part is established, a user can use a SESSION part context to create the CONNECTION part for the next time. This reduces the communication overhead of the protocol. The SESSION part consists of eight Probabilistic Polynomial-Time algorithms and can be described as SESSION==S,EKG,SI,E,DKG,D,V,R. The CONNECTION part consists of four Probabilistic Polynomial-Time algorithms and can be described merely as CONNECTION==SKG,E,RKG,D.TheSESSION part is shown in Figure 7, and the CONNECTION part is shown in Figure 8.Figure 7
TheSESSION part of the IBE-Signal scheme.Figure 8
TheCONNECTION part of the IBE-Signal scheme.


### 3.3. Scheme Construction

We present the scheme’s construction in two parts, theSESSION and the CONNECTION. Since the scheme uses many symbols, Table 2 provides a table of characters for the reader’s convenience.Table 2
Abbreviations and notations.
Abbreviations/notationsMeaningkSecure parameterqBig primeG1Additive group on an elliptic curve of the orderqG2Multiplicative group on an elliptic curve of the orderqe:G1×G1⟶G2Bilinear functionP,g,g2,h1,h2,h3Generator of the groupG1S0,P0,Y0The private key, the public key, and the shared public key of the KGCSi,Pi,Yii=1,2,...,nThe private key, the public key, and the shared public key of theith CPCYThe shared public key of the CPCn that equals to YnH1:0,1∗⟶G1∗A secure hash function that takes a string of any length as input and gives an element onG1H2:G2⟶0,1kA secure hash function that takes an element onG2 and gives a string of length kH3:0,1k⟶0,1kA secure hash function that takes a string of lengthk and gives a string of length kH4:0,1∗⟶ℤq∗A secure hash function that takes a string of any length and gives an element onℤq∗H5:0,1∗×G2∗⟶Zq∗A secure hash function that takes a string of any length and an element onG2 and gives an element on ℤq∗H6:0,1k×0,1k⟶0,1kA secure hash function that takes two strings of lengthk and gives a string of length kKDF:G1×0,1k⟶0,1kSecure key derivation function that takes an element onG1 and a string of length k and gives a string of length knuNumber of usersrlInitially empty revocation liststA binary tree with at leastnu leaf nodes representing statesτMinimum time intervalaThe private key of key authorityg1Part of the system parameter of key authority andg1=agparam1System parameter of the KGCparam2System parameter of the CPCsparam3System parameter of key authorityparamsThe final public parameter in the setup stepIDB∈0,1∗Identity of the receiverIDA∈0,1∗Identity of the senderQIDB∈G1∗Mapping ofIDB on G1QIDA∈G1∗Mapping ofIDA on G1SIDB∈G1∗The private key of the receiverSIDA∈G1∗The private key of the senderωMapping ofIDB on ℤq∗timeThe time when the encryption occurstMapping oftime on ℤq∗RootInputThe input of the root chain in the double ratchet algorithmrkRevocation keyRKThe input of the root chain in theCONNECTION part of the IBE-signal schemeekMessage key for the encryption of the first messagexBlinding factor in the private key issuance processTTimestamp used to prevent replay attacksT′Receiver’s local timeMThe message that needs to be signedσSignatureskωPrivate keys for revocationkutKey updates for revocationdkω,tRevocation key selected fromskω and kutPKBi,SKBiBob’s public and private keys in Diffie–Hellman key exchange inCONNECTION partPKAi,SKAiAlice’s public and private keys in Diffie–Hellman key exchange inCONNECTION partS_Sessioni_KjThejth message key of the sender in the ith sessionR_Sessioni_KjThejth message key of the receiver in the ith session


#### 3.3.1.SESSION Part

Letk be the secure parameter. G is the algorithm to generate parameters of BDH, including a prime q, an additive group G1, a multiplicative group G2 of the same order q, and a bilinear function e:G1×G1⟶G2.Set upS1k⟶params,Si,a,rl,st, where i = 0, 1, …, n. Including the following three algorithms, as shown in Figure 9:(1)
KGC Setup1k⟶param1,S0. This algorithm is run by the KGC: (2)q,G1,G2,e←G,P←RG1,S0←RZq∗,Y0=P0=S0P,H1:0,1∗⟶G1∗,H2:G2⟶0,1k,H3:0,1k⟶0,1k,H4:0,1∗⟶ℤq∗,H5:0,1∗×G2∗⟶Zq∗,H6:0,1k×0,1k⟶0,1k,KDF:G1×0,1k⟶0,1k,whereP is a generator of group G1, S0 is the private key of the KGC, P0 is the public key of the KGC, and Y0 is the shared public key of the KGC. H1,H2,H3,H4,H5,H6,KDF are secure hash functions, k represents the length of the message key. The system parameter of the KGC param1=q,G1,G2,e,k,P,P0,Y0,H1,H2,H3,H4,H5,H6,KDF is public, while the private key of the KGC S0 is private.(2)
CPC Setupparam1⟶param2,Si, where i = 1, 2, …, n. This algorithm is run by the CPCs:Each CPCi chooses Si∈Zq∗ as the private key and computes Pi=SiP as the public key, where i = 1, 2, …, n, n is the number of the CPCs.Each CPCi computes Yi=SiYi−1 as the shared public key. Specially, we define Yn as Y. For example, the CPC1 can compute Y1 with the private key S1 and the shared public key Y0 of the KGC. We use this chain from the KGC to the CPCn to compute the shared public key Yi of each entity. It is important to emphasize that when the CPCi-1 sends Y0,...,Yi−1 to the CPCi, then the CPCi must verify the correctness of Y0,...,Yi−1. Take the CPC3 as an example. The CPC3 verifies Y2 by computing eY0,P1?=eY1,P and eY1,P2?=eY2,P. System parameter of the CPCiparam2=Pi,Yi is public while the private key of the CPCiSi is private, where i = 1, 2, …, n.(3)
Key Authority Setupparam1,nu⟶param3,a,rl,st. This algorithm is run by the Key Authority:(3)g=P,a←Rℤp∗,g1=ag,g2,h1,h2,h3←RG1∗,wherenu is the number of users, rl is the initially empty revocation list, and st is the perfect binary tree with nu (nu is even) or nu+1 (nu is odd) leaf nodes representing states. Let τ be the minimum time interval. System parameter of the Key Authority param3=g,g1,g2,h1,h2,h3,τ is public, while the private key of the Key Authority a is private. In addition, the following two operations are defined just as [18]. For x,i∈ℤ, set J⊆ℤ, the Lagrange coefficientΔi,Jx is defined as follows:(4)Δi,Jx=∏j∈J,j≠ix−ji−j.Forx∈ℤ, J⊆ℤ, g,h1,...,hJ∈G1,(5)Hg,J,h1,...,hJx=x2g∏i=1JΔi,Jxhi.In theSetup step, the final public parameter is params=param1,param2,param3.Encryption Key GenerationEKGparams,IDB,time⟶r,RK,ek,U,rc, including the following two algorithms:(1)
Encryption RootInput Generationparams,IDB⟶r,U,RootInput. This algorithm is run by the sender:Parseparams as H1,H2,P,Y,q,G1,e.(6)QIDB=H1IDB∈G1∗,r←RZq∗,U=rP,RootInput=H2eQIDB,Yr,whereIDB is the receiver’s identity, RootInput is the input of the root chain in the Double Ratchet algorithm.(2)
Encryption Revocation Key Generationparams,IDB,time⟶rk,rc. This algorithm is run by the sender:Parseparams as H3,H4,H6,q,k,g,g1,g2,h1,h2,h3,e.(7)ω=H4IDB∈ℤq∗,t=H4time∈ℤq∗,rk←R0,1k,z←Rℤq∗,c1=rk⋅eg1,g2z,c2=zg,cω=zHg2,J,h1,h2,h3ω,ct=zHg2,J,h1,h2,h3t,where time is the time when the encryption occurs andrk is the revocation key. Let J be 1,2,3 and rc be ω,t,cω,ct,c1,c2.In theEncryption Key Generation step, the final encryption key ek:(8)RK=H6RootInput,rk,ek=H3RK.SignSIparams,Si,IDA,T,M⟶σ, including the following two algorithms:(1)
Sender’s Private Key Generationparams,Si,IDA⟶SIDA, where i = 0, 1, …, n. The sender runs this algorithm and interacts with the KGC and the CPCs, as shown in Figure 10.Parseparams as q,e,P,Y,H1.The sender does the following steps:x←RZq∗, X=xP, QIDA=H1IDA, DIDA=xQIDA, where IDA is the sender’s identity and x is the blinding factor. We use the blind signature to protect the sender’s partial private key from being obtained by an attacker or server. The sender sends IDA,DIDA,X to the KGC. It should be noted that the sender must go through the corresponding identity authentication process, such as password authentication, to get the signed private key, whether interacting with the KGC or the CPCs. Since this is not our focus, this paper has no specific design.The KGC and the CPCs do the following steps: the KGC computesQIDA=H1IDA and verifies the correctness of eQIDA,X?=eDIDA,P. This ensures that the KGC is issuing the partial private key to IDA. The KGC computes D0=S0DIDA, X0=S0X and sends them to the sender. The sender sends IDA,Di−1,Xi−1 to the CPCi, the CPCi computes QIDA=H1IDA and verifies the correctness of eQIDA,Xi−1?=eDi−1,P, then calculates Di=SiDi−1, Xi=SiXi−1 and sends them to the sender where i = 1, 2, …, n. After the iterations, the sender can get Dn=SnSn−1...S0xQIDA. The sender extracts the private key by computing SIDA=x−1Dn, then verifies the correctness of eSIDA,P?=eQIDA,Y.(2)
Signature Generationparams,T,M,SIDA⟶σ. This algorithm is run by the sender:Parseparams as q,e,G1,P,H5.(9)b←RZq∗,O←RG1∗,R=eO,Pb,y=H5M‖T,R,F=ySIDA+bO,σ=F,y,whereT is the timestamp used to prevent replay attacks, M is the message that needs to be signed, and σ is the signature. In the SESSION part, M can be a fixed format message shown in Figure 11, such as “Hi! I’m Alice.” When Alice friends Bob, a notification is automatically sent when the initial session is established.EncryptEek,U,rc,T,M,σ⟶C. This algorithm is run by the sender:LetEnc be a secure symmetric encryption algorithm.(10)V=EncMTσ,ek,C=U,V,rc,whereC is the ciphertext sent to the receiver.Decryption Key GenerationDKGparams,a,Si,IDB,time,C,st,rl⟶RK,ek, including the following six algorithms:(1)
Receiver’s Private Key Generationparams,Si,IDB⟶SIDB. The receiver runs this algorithm and interacts with the KGC and the CPCs:The function is likeSender’s Private Key Generation, so we will not go over it here.(2)
Decryption RootInput Generationparams,SIDB,C⟶RootInput. This algorithm is run by the receiver:Parseparams as H2,e and C as U,V,rc.(11)RootInput=H2eSIDB,U.(3)
Revocation Private Keys Generationparams,a,IDB,st⟶skω,st. This algorithm is run by the Key Authority:Parseparams as q,H4,g,g2,h1,h2,h3.(12)ω=H4IDB∈ℤq∗.Select an empty leaf nodev from st and store ω in it. In addition, the Path function is defined as follows: the set of all nodes on the path from the leaf node to the root node, including that leaf node and the root node.(i)
∀i∈Pathv(ii)
ifaiisundefined,(iii)
thenai←RZq∗andstoreaiinnodei,(iv)
computeri←RZq∗,di=rig,(v)
Di=aiω+ag2+riHg2,J,h1,h2,h3ωAfter the above code is executed, we get theprivate keys for revocation skω=i,di,Dii∈Pathv and the updated state tree st.(4)
Revocation Key Updates Generationparams,a,time,rl,st⟶kut. This algorithm is run by the Key Authority:Parseparams as g,g2,h1,h2,h3.(13)t=H4time∈ℤq∗.TheKUNodes function is the same as in [18] and is shown in Figure 12:KUNodesst,rl,t:(i)
X,Y←∅,(ii)
∀vi,ti∈rl(iii)
ifti≤tthenaddPathvitoX(iv)
∀x∈X(v)
ifxl∉XthenaddxltoY(vi)
ifxr∉XthenaddxrtoY(vii)
ifY=∅thenaddroottoY(viii)
returnYThe following code is executed for the nodes that are output by theKUNodes function.(i)
∀j∈KUNodesst,rl,t(ii)
computerj←RZq∗,ej=rjg,(iii)
Ej=ajt+ag2+rjHg2,J,h1,h2,h3tThen we get the set of thekey updates for revocation kut=j,ej,Ejj∈KUNodesst,rl,t.(5)
Revocation Key Selectionskω,kut⟶dkω,tor⊥. This algorithm is run by the receiver:Parseskω as i,di,Dii∈Pathv and kut as j,ej,Ejj∈KUNodesst,rl,t.(i)
∀i,di,Di∈skω,j,ej,Ej∈kut(ii)
ifi=jthendkω,t=di,Di,ej,Ej(iii)
elsedkω,t=⊥(iv)
returndkω,t.(6)
Decryption Revocation Key Generationdkω,t,C⟶rk. This algorithm is run by the receiver:Parsedkω,t as di,Di,ei,Ei, C as U,V,rc and rc as ω,t,cω,ct,c1,c2.(14)rk=c1edi,cωeDi,c2t/t−ωeei,cteEi,c2ω/ω−t.In theDecryption Key Generation step, the final decryption key:(15)RK=H6RootInput,rk,ek=H3RK.DecryptDC,ek⟶T,M,σ. This algorithm is run by the receiver:ParseC as U,V,rc, V as EncMTσ,ek. Let Dec be a secure symmetric decryption algorithm.(16)M||T||σ=DecV,ek.VerifyVparams,σ,M,T,IDA,T′⟶true or false. This algorithm is run by the receiver:Parseparams as e,P,Y,H1,H5,τ, σ as F,y. Let T′ be the receiver’s local time.(17)QIDA=H1IDA,R=eF,PeQIDA,−Yy.(i)
ifH5M‖T,R==y&&T′−T≤τthenreturntrue(ii)
elsereturnfalse.RevocationRω,t,rl,st⟶rl. This algorithm is run by the Key Authority:(i)
∀v∈leafnodesinstwithω(ii)
addv,ttorl(iii)
returnrl.Figure 9
KGC Setup and CPC Setup of the IBE-Signal scheme.Figure 10
Sender’s Private Key Generation of the IBESignal scheme.Figure 11
In the signal application, messages are delivered when a session is established.Figure 12
TheKUNodes tree when node #7 is revoked.


#### 3.3.2.CONNECTION Part

In theCONNECTION part, we show how the first two messages are sent and received in the first session.Sender Key GenerationSKGparams,C,RK⟶S_Session1_K1,S_Session1_K2,PKB1,RK:Parseparams as q,P,KDF,H3, C as U,V,rc, U as rP,(18)SKB1←RZq∗,PKB1=SKB1P,DHkey_S_Session1=SKB1U=rSKB1P,RK=KDFDHkey_S_Session1,RK,S_Session1_K1=H3RK,S_Session1_K2=H3S_Session1_K1.EncryptEM1,M2,S_Session1_K1,S_Session1_K2,PKB1⟶C1,C2:LetEnc be a secure symmetric encryption algorithm.(19)C1=PKB1,EncM1,S_Session1_K1,C2=PKB1,EncM2,S_Session1_K2.Receiver Key GenerationRKGC1,r,RK⟶R_Session1_K1,R_Session1_K2,RK:ParseC1 as PKB1,EncM1,S_Session1_K1,(20)DHkey_R_Session1=rPKB1=rSKB1P,RK=KDFDHkey_R_Session1,RK,R_Session1_K1=H3RK,R_Session1_K2=H3R_Session1_K1.DecryptDC1,C2,R_Session1_K1,R_Session1_K2⟶M1,M2:LetDec be a secure symmetric encryption algorithm.(21)M1=DecEncM1,S_Session1_K1,R_Session1_K1,M2=DecEncM2,S_Session1_K2,R_Session1_K2.


## 3.1. Threat Model

As shown in Figure5, our model uses one KGC, multiple CPCs, and one Key Authority to replace the single PKG in the BF-IBE model shown in Figure 6. The KGC sets most system parameters, and the CPCs also have the private key share for risk reduction. The Key Authority is fully trusted and only responsible for public key revocation. In addition, our public key revocation feature is optional, and if the user turns it off, the Key Authority will no longer serve him.Figure 5
The IBE-Signal scheme’s threat model.Figure 6
The BF-IBE scheme’s threat model.We assume that an ambitious adversary can collude with the KGC andn-1 CPCs. In other words, at least one CPC in our scheme is credible. Corrupt KGC/n-1 CPCs can assign the partial private key to any identity submitted by the adversary. The adversary can launch a chosen-plaintext attack and can finally select an ID∗ to challenge. We allow the adversary to retrieve the partial private key from the KGC and n-1 partial private keys from the CPCs in this case. Before and after the challenge, the adversary can choose a random ID to query where ID≠ID∗. Furthermore, we allow the adversary to retrieve the partial private key from the KGC and n partial private keys from the CPCs in this case. This process can be repeated polynomial bounded times.Even with these capabilities, the adversary has a negligible advantage against our IBE-Signal scheme.


## 3.2. The Framework of the IBE-Signal Scheme

Like the SSL protocol [35], our IBE-Signal scheme contains parts of the SESSION and the CONNECTION. The SESSION part refers to a collection of parameters and encryption keys generated through a handshake between two communicating parties. In contrast, the CONNECTION part refers to a subsequent session established after the SESSION part using the shared key RK. The SESSION part is more overhead than the CONNECTION part for the server. Once the SESSION part is established, a user can use a SESSION part context to create the CONNECTION part for the next time. This reduces the communication overhead of the protocol. The SESSION part consists of eight Probabilistic Polynomial-Time algorithms and can be described as SESSION==S,EKG,SI,E,DKG,D,V,R. The CONNECTION part consists of four Probabilistic Polynomial-Time algorithms and can be described merely as CONNECTION==SKG,E,RKG,D.TheSESSION part is shown in Figure 7, and the CONNECTION part is shown in Figure 8.Figure 7
TheSESSION part of the IBE-Signal scheme.Figure 8
TheCONNECTION part of the IBE-Signal scheme.


## 3.3. Scheme Construction

We present the scheme’s construction in two parts, theSESSION and the CONNECTION. Since the scheme uses many symbols, Table 2 provides a table of characters for the reader’s convenience.Table 2
Abbreviations and notations.
Abbreviations/notationsMeaningkSecure parameterqBig primeG1Additive group on an elliptic curve of the orderqG2Multiplicative group on an elliptic curve of the orderqe:G1×G1⟶G2Bilinear functionP,g,g2,h1,h2,h3Generator of the groupG1S0,P0,Y0The private key, the public key, and the shared public key of the KGCSi,Pi,Yii=1,2,...,nThe private key, the public key, and the shared public key of theith CPCYThe shared public key of the CPCn that equals to YnH1:0,1∗⟶G1∗A secure hash function that takes a string of any length as input and gives an element onG1H2:G2⟶0,1kA secure hash function that takes an element onG2 and gives a string of length kH3:0,1k⟶0,1kA secure hash function that takes a string of lengthk and gives a string of length kH4:0,1∗⟶ℤq∗A secure hash function that takes a string of any length and gives an element onℤq∗H5:0,1∗×G2∗⟶Zq∗A secure hash function that takes a string of any length and an element onG2 and gives an element on ℤq∗H6:0,1k×0,1k⟶0,1kA secure hash function that takes two strings of lengthk and gives a string of length kKDF:G1×0,1k⟶0,1kSecure key derivation function that takes an element onG1 and a string of length k and gives a string of length knuNumber of usersrlInitially empty revocation liststA binary tree with at leastnu leaf nodes representing statesτMinimum time intervalaThe private key of key authorityg1Part of the system parameter of key authority andg1=agparam1System parameter of the KGCparam2System parameter of the CPCsparam3System parameter of key authorityparamsThe final public parameter in the setup stepIDB∈0,1∗Identity of the receiverIDA∈0,1∗Identity of the senderQIDB∈G1∗Mapping ofIDB on G1QIDA∈G1∗Mapping ofIDA on G1SIDB∈G1∗The private key of the receiverSIDA∈G1∗The private key of the senderωMapping ofIDB on ℤq∗timeThe time when the encryption occurstMapping oftime on ℤq∗RootInputThe input of the root chain in the double ratchet algorithmrkRevocation keyRKThe input of the root chain in theCONNECTION part of the IBE-signal schemeekMessage key for the encryption of the first messagexBlinding factor in the private key issuance processTTimestamp used to prevent replay attacksT′Receiver’s local timeMThe message that needs to be signedσSignatureskωPrivate keys for revocationkutKey updates for revocationdkω,tRevocation key selected fromskω and kutPKBi,SKBiBob’s public and private keys in Diffie–Hellman key exchange inCONNECTION partPKAi,SKAiAlice’s public and private keys in Diffie–Hellman key exchange inCONNECTION partS_Sessioni_KjThejth message key of the sender in the ith sessionR_Sessioni_KjThejth message key of the receiver in the ith session


### 3.3.1.SESSION Part

Letk be the secure parameter. G is the algorithm to generate parameters of BDH, including a prime q, an additive group G1, a multiplicative group G2 of the same order q, and a bilinear function e:G1×G1⟶G2.Set upS1k⟶params,Si,a,rl,st, where i = 0, 1, …, n. Including the following three algorithms, as shown in Figure 9:(1)
KGC Setup1k⟶param1,S0. This algorithm is run by the KGC: (2)q,G1,G2,e←G,P←RG1,S0←RZq∗,Y0=P0=S0P,H1:0,1∗⟶G1∗,H2:G2⟶0,1k,H3:0,1k⟶0,1k,H4:0,1∗⟶ℤq∗,H5:0,1∗×G2∗⟶Zq∗,H6:0,1k×0,1k⟶0,1k,KDF:G1×0,1k⟶0,1k,whereP is a generator of group G1, S0 is the private key of the KGC, P0 is the public key of the KGC, and Y0 is the shared public key of the KGC. H1,H2,H3,H4,H5,H6,KDF are secure hash functions, k represents the length of the message key. The system parameter of the KGC param1=q,G1,G2,e,k,P,P0,Y0,H1,H2,H3,H4,H5,H6,KDF is public, while the private key of the KGC S0 is private.(2)
CPC Setupparam1⟶param2,Si, where i = 1, 2, …, n. This algorithm is run by the CPCs:Each CPCi chooses Si∈Zq∗ as the private key and computes Pi=SiP as the public key, where i = 1, 2, …, n, n is the number of the CPCs.Each CPCi computes Yi=SiYi−1 as the shared public key. Specially, we define Yn as Y. For example, the CPC1 can compute Y1 with the private key S1 and the shared public key Y0 of the KGC. We use this chain from the KGC to the CPCn to compute the shared public key Yi of each entity. It is important to emphasize that when the CPCi-1 sends Y0,...,Yi−1 to the CPCi, then the CPCi must verify the correctness of Y0,...,Yi−1. Take the CPC3 as an example. The CPC3 verifies Y2 by computing eY0,P1?=eY1,P and eY1,P2?=eY2,P. System parameter of the CPCiparam2=Pi,Yi is public while the private key of the CPCiSi is private, where i = 1, 2, …, n.(3)
Key Authority Setupparam1,nu⟶param3,a,rl,st. This algorithm is run by the Key Authority:(3)g=P,a←Rℤp∗,g1=ag,g2,h1,h2,h3←RG1∗,wherenu is the number of users, rl is the initially empty revocation list, and st is the perfect binary tree with nu (nu is even) or nu+1 (nu is odd) leaf nodes representing states. Let τ be the minimum time interval. System parameter of the Key Authority param3=g,g1,g2,h1,h2,h3,τ is public, while the private key of the Key Authority a is private. In addition, the following two operations are defined just as [18]. For x,i∈ℤ, set J⊆ℤ, the Lagrange coefficientΔi,Jx is defined as follows:(4)Δi,Jx=∏j∈J,j≠ix−ji−j.Forx∈ℤ, J⊆ℤ, g,h1,...,hJ∈G1,(5)Hg,J,h1,...,hJx=x2g∏i=1JΔi,Jxhi.In theSetup step, the final public parameter is params=param1,param2,param3.Encryption Key GenerationEKGparams,IDB,time⟶r,RK,ek,U,rc, including the following two algorithms:(1)
Encryption RootInput Generationparams,IDB⟶r,U,RootInput. This algorithm is run by the sender:Parseparams as H1,H2,P,Y,q,G1,e.(6)QIDB=H1IDB∈G1∗,r←RZq∗,U=rP,RootInput=H2eQIDB,Yr,whereIDB is the receiver’s identity, RootInput is the input of the root chain in the Double Ratchet algorithm.(2)
Encryption Revocation Key Generationparams,IDB,time⟶rk,rc. This algorithm is run by the sender:Parseparams as H3,H4,H6,q,k,g,g1,g2,h1,h2,h3,e.(7)ω=H4IDB∈ℤq∗,t=H4time∈ℤq∗,rk←R0,1k,z←Rℤq∗,c1=rk⋅eg1,g2z,c2=zg,cω=zHg2,J,h1,h2,h3ω,ct=zHg2,J,h1,h2,h3t,where time is the time when the encryption occurs andrk is the revocation key. Let J be 1,2,3 and rc be ω,t,cω,ct,c1,c2.In theEncryption Key Generation step, the final encryption key ek:(8)RK=H6RootInput,rk,ek=H3RK.SignSIparams,Si,IDA,T,M⟶σ, including the following two algorithms:(1)
Sender’s Private Key Generationparams,Si,IDA⟶SIDA, where i = 0, 1, …, n. The sender runs this algorithm and interacts with the KGC and the CPCs, as shown in Figure 10.Parseparams as q,e,P,Y,H1.The sender does the following steps:x←RZq∗, X=xP, QIDA=H1IDA, DIDA=xQIDA, where IDA is the sender’s identity and x is the blinding factor. We use the blind signature to protect the sender’s partial private key from being obtained by an attacker or server. The sender sends IDA,DIDA,X to the KGC. It should be noted that the sender must go through the corresponding identity authentication process, such as password authentication, to get the signed private key, whether interacting with the KGC or the CPCs. Since this is not our focus, this paper has no specific design.The KGC and the CPCs do the following steps: the KGC computesQIDA=H1IDA and verifies the correctness of eQIDA,X?=eDIDA,P. This ensures that the KGC is issuing the partial private key to IDA. The KGC computes D0=S0DIDA, X0=S0X and sends them to the sender. The sender sends IDA,Di−1,Xi−1 to the CPCi, the CPCi computes QIDA=H1IDA and verifies the correctness of eQIDA,Xi−1?=eDi−1,P, then calculates Di=SiDi−1, Xi=SiXi−1 and sends them to the sender where i = 1, 2, …, n. After the iterations, the sender can get Dn=SnSn−1...S0xQIDA. The sender extracts the private key by computing SIDA=x−1Dn, then verifies the correctness of eSIDA,P?=eQIDA,Y.(2)
Signature Generationparams,T,M,SIDA⟶σ. This algorithm is run by the sender:Parseparams as q,e,G1,P,H5.(9)b←RZq∗,O←RG1∗,R=eO,Pb,y=H5M‖T,R,F=ySIDA+bO,σ=F,y,whereT is the timestamp used to prevent replay attacks, M is the message that needs to be signed, and σ is the signature. In the SESSION part, M can be a fixed format message shown in Figure 11, such as “Hi! I’m Alice.” When Alice friends Bob, a notification is automatically sent when the initial session is established.EncryptEek,U,rc,T,M,σ⟶C. This algorithm is run by the sender:LetEnc be a secure symmetric encryption algorithm.(10)V=EncMTσ,ek,C=U,V,rc,whereC is the ciphertext sent to the receiver.Decryption Key GenerationDKGparams,a,Si,IDB,time,C,st,rl⟶RK,ek, including the following six algorithms:(1)
Receiver’s Private Key Generationparams,Si,IDB⟶SIDB. The receiver runs this algorithm and interacts with the KGC and the CPCs:The function is likeSender’s Private Key Generation, so we will not go over it here.(2)
Decryption RootInput Generationparams,SIDB,C⟶RootInput. This algorithm is run by the receiver:Parseparams as H2,e and C as U,V,rc.(11)RootInput=H2eSIDB,U.(3)
Revocation Private Keys Generationparams,a,IDB,st⟶skω,st. This algorithm is run by the Key Authority:Parseparams as q,H4,g,g2,h1,h2,h3.(12)ω=H4IDB∈ℤq∗.Select an empty leaf nodev from st and store ω in it. In addition, the Path function is defined as follows: the set of all nodes on the path from the leaf node to the root node, including that leaf node and the root node.(i)
∀i∈Pathv(ii)
ifaiisundefined,(iii)
thenai←RZq∗andstoreaiinnodei,(iv)
computeri←RZq∗,di=rig,(v)
Di=aiω+ag2+riHg2,J,h1,h2,h3ωAfter the above code is executed, we get theprivate keys for revocation skω=i,di,Dii∈Pathv and the updated state tree st.(4)
Revocation Key Updates Generationparams,a,time,rl,st⟶kut. This algorithm is run by the Key Authority:Parseparams as g,g2,h1,h2,h3.(13)t=H4time∈ℤq∗.TheKUNodes function is the same as in [18] and is shown in Figure 12:KUNodesst,rl,t:(i)
X,Y←∅,(ii)
∀vi,ti∈rl(iii)
ifti≤tthenaddPathvitoX(iv)
∀x∈X(v)
ifxl∉XthenaddxltoY(vi)
ifxr∉XthenaddxrtoY(vii)
ifY=∅thenaddroottoY(viii)
returnYThe following code is executed for the nodes that are output by theKUNodes function.(i)
∀j∈KUNodesst,rl,t(ii)
computerj←RZq∗,ej=rjg,(iii)
Ej=ajt+ag2+rjHg2,J,h1,h2,h3tThen we get the set of thekey updates for revocation kut=j,ej,Ejj∈KUNodesst,rl,t.(5)
Revocation Key Selectionskω,kut⟶dkω,tor⊥. This algorithm is run by the receiver:Parseskω as i,di,Dii∈Pathv and kut as j,ej,Ejj∈KUNodesst,rl,t.(i)
∀i,di,Di∈skω,j,ej,Ej∈kut(ii)
ifi=jthendkω,t=di,Di,ej,Ej(iii)
elsedkω,t=⊥(iv)
returndkω,t.(6)
Decryption Revocation Key Generationdkω,t,C⟶rk. This algorithm is run by the receiver:Parsedkω,t as di,Di,ei,Ei, C as U,V,rc and rc as ω,t,cω,ct,c1,c2.(14)rk=c1edi,cωeDi,c2t/t−ωeei,cteEi,c2ω/ω−t.In theDecryption Key Generation step, the final decryption key:(15)RK=H6RootInput,rk,ek=H3RK.DecryptDC,ek⟶T,M,σ. This algorithm is run by the receiver:ParseC as U,V,rc, V as EncMTσ,ek. Let Dec be a secure symmetric decryption algorithm.(16)M||T||σ=DecV,ek.VerifyVparams,σ,M,T,IDA,T′⟶true or false. This algorithm is run by the receiver:Parseparams as e,P,Y,H1,H5,τ, σ as F,y. Let T′ be the receiver’s local time.(17)QIDA=H1IDA,R=eF,PeQIDA,−Yy.(i)
ifH5M‖T,R==y&&T′−T≤τthenreturntrue(ii)
elsereturnfalse.RevocationRω,t,rl,st⟶rl. This algorithm is run by the Key Authority:(i)
∀v∈leafnodesinstwithω(ii)
addv,ttorl(iii)
returnrl.Figure 9
KGC Setup and CPC Setup of the IBE-Signal scheme.Figure 10
Sender’s Private Key Generation of the IBESignal scheme.Figure 11
In the signal application, messages are delivered when a session is established.Figure 12
TheKUNodes tree when node #7 is revoked.


### 3.3.2.CONNECTION Part

In theCONNECTION part, we show how the first two messages are sent and received in the first session.Sender Key GenerationSKGparams,C,RK⟶S_Session1_K1,S_Session1_K2,PKB1,RK:Parseparams as q,P,KDF,H3, C as U,V,rc, U as rP,(18)SKB1←RZq∗,PKB1=SKB1P,DHkey_S_Session1=SKB1U=rSKB1P,RK=KDFDHkey_S_Session1,RK,S_Session1_K1=H3RK,S_Session1_K2=H3S_Session1_K1.EncryptEM1,M2,S_Session1_K1,S_Session1_K2,PKB1⟶C1,C2:LetEnc be a secure symmetric encryption algorithm.(19)C1=PKB1,EncM1,S_Session1_K1,C2=PKB1,EncM2,S_Session1_K2.Receiver Key GenerationRKGC1,r,RK⟶R_Session1_K1,R_Session1_K2,RK:ParseC1 as PKB1,EncM1,S_Session1_K1,(20)DHkey_R_Session1=rPKB1=rSKB1P,RK=KDFDHkey_R_Session1,RK,R_Session1_K1=H3RK,R_Session1_K2=H3R_Session1_K1.DecryptDC1,C2,R_Session1_K1,R_Session1_K2⟶M1,M2:LetDec be a secure symmetric encryption algorithm.(21)M1=DecEncM1,S_Session1_K1,R_Session1_K1,M2=DecEncM2,S_Session1_K2,R_Session1_K2.


## 3.3.1.SESSION Part

Letk be the secure parameter. G is the algorithm to generate parameters of BDH, including a prime q, an additive group G1, a multiplicative group G2 of the same order q, and a bilinear function e:G1×G1⟶G2.Set upS1k⟶params,Si,a,rl,st, where i = 0, 1, …, n. Including the following three algorithms, as shown in Figure 9:(1)
KGC Setup1k⟶param1,S0. This algorithm is run by the KGC: (2)q,G1,G2,e←G,P←RG1,S0←RZq∗,Y0=P0=S0P,H1:0,1∗⟶G1∗,H2:G2⟶0,1k,H3:0,1k⟶0,1k,H4:0,1∗⟶ℤq∗,H5:0,1∗×G2∗⟶Zq∗,H6:0,1k×0,1k⟶0,1k,KDF:G1×0,1k⟶0,1k,whereP is a generator of group G1, S0 is the private key of the KGC, P0 is the public key of the KGC, and Y0 is the shared public key of the KGC. H1,H2,H3,H4,H5,H6,KDF are secure hash functions, k represents the length of the message key. The system parameter of the KGC param1=q,G1,G2,e,k,P,P0,Y0,H1,H2,H3,H4,H5,H6,KDF is public, while the private key of the KGC S0 is private.(2)
CPC Setupparam1⟶param2,Si, where i = 1, 2, …, n. This algorithm is run by the CPCs:Each CPCi chooses Si∈Zq∗ as the private key and computes Pi=SiP as the public key, where i = 1, 2, …, n, n is the number of the CPCs.Each CPCi computes Yi=SiYi−1 as the shared public key. Specially, we define Yn as Y. For example, the CPC1 can compute Y1 with the private key S1 and the shared public key Y0 of the KGC. We use this chain from the KGC to the CPCn to compute the shared public key Yi of each entity. It is important to emphasize that when the CPCi-1 sends Y0,...,Yi−1 to the CPCi, then the CPCi must verify the correctness of Y0,...,Yi−1. Take the CPC3 as an example. The CPC3 verifies Y2 by computing eY0,P1?=eY1,P and eY1,P2?=eY2,P. System parameter of the CPCiparam2=Pi,Yi is public while the private key of the CPCiSi is private, where i = 1, 2, …, n.(3)
Key Authority Setupparam1,nu⟶param3,a,rl,st. This algorithm is run by the Key Authority:(3)g=P,a←Rℤp∗,g1=ag,g2,h1,h2,h3←RG1∗,wherenu is the number of users, rl is the initially empty revocation list, and st is the perfect binary tree with nu (nu is even) or nu+1 (nu is odd) leaf nodes representing states. Let τ be the minimum time interval. System parameter of the Key Authority param3=g,g1,g2,h1,h2,h3,τ is public, while the private key of the Key Authority a is private. In addition, the following two operations are defined just as [18]. For x,i∈ℤ, set J⊆ℤ, the Lagrange coefficientΔi,Jx is defined as follows:(4)Δi,Jx=∏j∈J,j≠ix−ji−j.Forx∈ℤ, J⊆ℤ, g,h1,...,hJ∈G1,(5)Hg,J,h1,...,hJx=x2g∏i=1JΔi,Jxhi.In theSetup step, the final public parameter is params=param1,param2,param3.Encryption Key GenerationEKGparams,IDB,time⟶r,RK,ek,U,rc, including the following two algorithms:(1)
Encryption RootInput Generationparams,IDB⟶r,U,RootInput. This algorithm is run by the sender:Parseparams as H1,H2,P,Y,q,G1,e.(6)QIDB=H1IDB∈G1∗,r←RZq∗,U=rP,RootInput=H2eQIDB,Yr,whereIDB is the receiver’s identity, RootInput is the input of the root chain in the Double Ratchet algorithm.(2)
Encryption Revocation Key Generationparams,IDB,time⟶rk,rc. This algorithm is run by the sender:Parseparams as H3,H4,H6,q,k,g,g1,g2,h1,h2,h3,e.(7)ω=H4IDB∈ℤq∗,t=H4time∈ℤq∗,rk←R0,1k,z←Rℤq∗,c1=rk⋅eg1,g2z,c2=zg,cω=zHg2,J,h1,h2,h3ω,ct=zHg2,J,h1,h2,h3t,where time is the time when the encryption occurs andrk is the revocation key. Let J be 1,2,3 and rc be ω,t,cω,ct,c1,c2.In theEncryption Key Generation step, the final encryption key ek:(8)RK=H6RootInput,rk,ek=H3RK.SignSIparams,Si,IDA,T,M⟶σ, including the following two algorithms:(1)
Sender’s Private Key Generationparams,Si,IDA⟶SIDA, where i = 0, 1, …, n. The sender runs this algorithm and interacts with the KGC and the CPCs, as shown in Figure 10.Parseparams as q,e,P,Y,H1.The sender does the following steps:x←RZq∗, X=xP, QIDA=H1IDA, DIDA=xQIDA, where IDA is the sender’s identity and x is the blinding factor. We use the blind signature to protect the sender’s partial private key from being obtained by an attacker or server. The sender sends IDA,DIDA,X to the KGC. It should be noted that the sender must go through the corresponding identity authentication process, such as password authentication, to get the signed private key, whether interacting with the KGC or the CPCs. Since this is not our focus, this paper has no specific design.The KGC and the CPCs do the following steps: the KGC computesQIDA=H1IDA and verifies the correctness of eQIDA,X?=eDIDA,P. This ensures that the KGC is issuing the partial private key to IDA. The KGC computes D0=S0DIDA, X0=S0X and sends them to the sender. The sender sends IDA,Di−1,Xi−1 to the CPCi, the CPCi computes QIDA=H1IDA and verifies the correctness of eQIDA,Xi−1?=eDi−1,P, then calculates Di=SiDi−1, Xi=SiXi−1 and sends them to the sender where i = 1, 2, …, n. After the iterations, the sender can get Dn=SnSn−1...S0xQIDA. The sender extracts the private key by computing SIDA=x−1Dn, then verifies the correctness of eSIDA,P?=eQIDA,Y.(2)
Signature Generationparams,T,M,SIDA⟶σ. This algorithm is run by the sender:Parseparams as q,e,G1,P,H5.(9)b←RZq∗,O←RG1∗,R=eO,Pb,y=H5M‖T,R,F=ySIDA+bO,σ=F,y,whereT is the timestamp used to prevent replay attacks, M is the message that needs to be signed, and σ is the signature. In the SESSION part, M can be a fixed format message shown in Figure 11, such as “Hi! I’m Alice.” When Alice friends Bob, a notification is automatically sent when the initial session is established.EncryptEek,U,rc,T,M,σ⟶C. This algorithm is run by the sender:LetEnc be a secure symmetric encryption algorithm.(10)V=EncMTσ,ek,C=U,V,rc,whereC is the ciphertext sent to the receiver.Decryption Key GenerationDKGparams,a,Si,IDB,time,C,st,rl⟶RK,ek, including the following six algorithms:(1)
Receiver’s Private Key Generationparams,Si,IDB⟶SIDB. The receiver runs this algorithm and interacts with the KGC and the CPCs:The function is likeSender’s Private Key Generation, so we will not go over it here.(2)
Decryption RootInput Generationparams,SIDB,C⟶RootInput. This algorithm is run by the receiver:Parseparams as H2,e and C as U,V,rc.(11)RootInput=H2eSIDB,U.(3)
Revocation Private Keys Generationparams,a,IDB,st⟶skω,st. This algorithm is run by the Key Authority:Parseparams as q,H4,g,g2,h1,h2,h3.(12)ω=H4IDB∈ℤq∗.Select an empty leaf nodev from st and store ω in it. In addition, the Path function is defined as follows: the set of all nodes on the path from the leaf node to the root node, including that leaf node and the root node.(i)
∀i∈Pathv(ii)
ifaiisundefined,(iii)
thenai←RZq∗andstoreaiinnodei,(iv)
computeri←RZq∗,di=rig,(v)
Di=aiω+ag2+riHg2,J,h1,h2,h3ωAfter the above code is executed, we get theprivate keys for revocation skω=i,di,Dii∈Pathv and the updated state tree st.(4)
Revocation Key Updates Generationparams,a,time,rl,st⟶kut. This algorithm is run by the Key Authority:Parseparams as g,g2,h1,h2,h3.(13)t=H4time∈ℤq∗.TheKUNodes function is the same as in [18] and is shown in Figure 12:KUNodesst,rl,t:(i)
X,Y←∅,(ii)
∀vi,ti∈rl(iii)
ifti≤tthenaddPathvitoX(iv)
∀x∈X(v)
ifxl∉XthenaddxltoY(vi)
ifxr∉XthenaddxrtoY(vii)
ifY=∅thenaddroottoY(viii)
returnYThe following code is executed for the nodes that are output by theKUNodes function.(i)
∀j∈KUNodesst,rl,t(ii)
computerj←RZq∗,ej=rjg,(iii)
Ej=ajt+ag2+rjHg2,J,h1,h2,h3tThen we get the set of thekey updates for revocation kut=j,ej,Ejj∈KUNodesst,rl,t.(5)
Revocation Key Selectionskω,kut⟶dkω,tor⊥. This algorithm is run by the receiver:Parseskω as i,di,Dii∈Pathv and kut as j,ej,Ejj∈KUNodesst,rl,t.(i)
∀i,di,Di∈skω,j,ej,Ej∈kut(ii)
ifi=jthendkω,t=di,Di,ej,Ej(iii)
elsedkω,t=⊥(iv)
returndkω,t.(6)
Decryption Revocation Key Generationdkω,t,C⟶rk. This algorithm is run by the receiver:Parsedkω,t as di,Di,ei,Ei, C as U,V,rc and rc as ω,t,cω,ct,c1,c2.(14)rk=c1edi,cωeDi,c2t/t−ωeei,cteEi,c2ω/ω−t.In theDecryption Key Generation step, the final decryption key:(15)RK=H6RootInput,rk,ek=H3RK.DecryptDC,ek⟶T,M,σ. This algorithm is run by the receiver:ParseC as U,V,rc, V as EncMTσ,ek. Let Dec be a secure symmetric decryption algorithm.(16)M||T||σ=DecV,ek.VerifyVparams,σ,M,T,IDA,T′⟶true or false. This algorithm is run by the receiver:Parseparams as e,P,Y,H1,H5,τ, σ as F,y. Let T′ be the receiver’s local time.(17)QIDA=H1IDA,R=eF,PeQIDA,−Yy.(i)
ifH5M‖T,R==y&&T′−T≤τthenreturntrue(ii)
elsereturnfalse.RevocationRω,t,rl,st⟶rl. This algorithm is run by the Key Authority:(i)
∀v∈leafnodesinstwithω(ii)
addv,ttorl(iii)
returnrl.Figure 9
KGC Setup and CPC Setup of the IBE-Signal scheme.Figure 10
Sender’s Private Key Generation of the IBESignal scheme.Figure 11
In the signal application, messages are delivered when a session is established.Figure 12
TheKUNodes tree when node #7 is revoked.


## 3.3.2.CONNECTION Part

In theCONNECTION part, we show how the first two messages are sent and received in the first session.Sender Key GenerationSKGparams,C,RK⟶S_Session1_K1,S_Session1_K2,PKB1,RK:Parseparams as q,P,KDF,H3, C as U,V,rc, U as rP,(18)SKB1←RZq∗,PKB1=SKB1P,DHkey_S_Session1=SKB1U=rSKB1P,RK=KDFDHkey_S_Session1,RK,S_Session1_K1=H3RK,S_Session1_K2=H3S_Session1_K1.EncryptEM1,M2,S_Session1_K1,S_Session1_K2,PKB1⟶C1,C2:LetEnc be a secure symmetric encryption algorithm.(19)C1=PKB1,EncM1,S_Session1_K1,C2=PKB1,EncM2,S_Session1_K2.Receiver Key GenerationRKGC1,r,RK⟶R_Session1_K1,R_Session1_K2,RK:ParseC1 as PKB1,EncM1,S_Session1_K1,(20)DHkey_R_Session1=rPKB1=rSKB1P,RK=KDFDHkey_R_Session1,RK,R_Session1_K1=H3RK,R_Session1_K2=H3R_Session1_K1.DecryptDC1,C2,R_Session1_K1,R_Session1_K2⟶M1,M2:LetDec be a secure symmetric encryption algorithm.(21)M1=DecEncM1,S_Session1_K1,R_Session1_K1,M2=DecEncM2,S_Session1_K2,R_Session1_K2.


## 4. Security Features’ Analysis

This paper selects two features to analyze in detail: resisting MITM attacks and supporting public key revocation.


### 4.1. Our IBE-Signal Scheme Can Resist MITM Attack

We discussed that MITM attacks cannot be implemented in both theSESSION part and the CONNECTION part.In theSESSION part, mutual authentication exists.To indicate the existence of mutual authentication in theSESSION part, we show a simplified version of our IBE-Signal protocol in Figure 13. Based on the characteristics of the IBE scheme, Alice can get Bob’s public key QIDB directly from Bob’s ID and then encrypt the message M by the public key QIDB. rP is a random challenge to Bob’s identity. The only way to get S_Session1_K1 is to have Bob’s private key, which encrypts message M1 as a response to the challenge rP. This completes the authentication of Bob and is resistant to replay attacks. Authentication of Alice is done by signature and timestamp and prevents replay attacks. A MITM attack is not possible when mutual authentication is established.In theCONNECTION part, launching a MITM attack is ineffective.Since we use the Diffie–Hellman ratchet in theCONNECTION part, an attacker can launch a MITM attack to hijack the session, as shown in Figure 14. However, both parties have a negotiated RK in the SESSION part, while the attacker has no RK. The attacker cannot calculate K1 and K2 and naturally cannot send the message PKT1,EncM1,K2.Figure 13
The simplified version of our IBE-Signal scheme.Figure 14
A MITM attack in theCONNECTION part.


### 4.2. Our IBE-Signal Scheme Supports Public Key Revocation

Once the user’s public key expires, the Key Authority will add it torl, and the KUNodes function will output a new point set. As shown in Figure 12, the set consisting of red dots is i,di,Dii∈Pathv and the set consisting of green dots is j,ej,Ejj∈KUNodesst,rl,t. The two sets have no intersection and thus cannot generate the revocation key dkω,t.Assume that the encryption time ist and the expiration time is t′. Formula 22 shows that the attacker cannot get rk using the old revocation key dkω,t, so the initial session cannot be established.(22)c1edi,cωeDi,c2t′/t′−ωeei,cteEi,c2ω/ω−t′=rk⋅eg1,g2zerig,zHg2,J,h1,h2,h3ωeaiω+ag2+riHg2,J,h1,h2,h3ω,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2+riHg2,J,h1,h2,h3t′,zgω/ω−t′=rk⋅eg1,g2zerig,zHg2,J,h1,h2,h3ωeaiω+ag2,zg⋅eriHg2,J,h1,h2,h3ω,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2,zg⋅eriHg2,J,h1,h2,h3t′,zgω/ω−t′=rk⋅eg1,g2z1eaiω+ag2,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2,zg⋅eriHg2,J,h1,h2,h3t′,zgω/ω−t′≠rk.


## 4.1. Our IBE-Signal Scheme Can Resist MITM Attack

We discussed that MITM attacks cannot be implemented in both theSESSION part and the CONNECTION part.In theSESSION part, mutual authentication exists.To indicate the existence of mutual authentication in theSESSION part, we show a simplified version of our IBE-Signal protocol in Figure 13. Based on the characteristics of the IBE scheme, Alice can get Bob’s public key QIDB directly from Bob’s ID and then encrypt the message M by the public key QIDB. rP is a random challenge to Bob’s identity. The only way to get S_Session1_K1 is to have Bob’s private key, which encrypts message M1 as a response to the challenge rP. This completes the authentication of Bob and is resistant to replay attacks. Authentication of Alice is done by signature and timestamp and prevents replay attacks. A MITM attack is not possible when mutual authentication is established.In theCONNECTION part, launching a MITM attack is ineffective.Since we use the Diffie–Hellman ratchet in theCONNECTION part, an attacker can launch a MITM attack to hijack the session, as shown in Figure 14. However, both parties have a negotiated RK in the SESSION part, while the attacker has no RK. The attacker cannot calculate K1 and K2 and naturally cannot send the message PKT1,EncM1,K2.Figure 13
The simplified version of our IBE-Signal scheme.Figure 14
A MITM attack in theCONNECTION part.


## 4.2. Our IBE-Signal Scheme Supports Public Key Revocation

Once the user’s public key expires, the Key Authority will add it torl, and the KUNodes function will output a new point set. As shown in Figure 12, the set consisting of red dots is i,di,Dii∈Pathv and the set consisting of green dots is j,ej,Ejj∈KUNodesst,rl,t. The two sets have no intersection and thus cannot generate the revocation key dkω,t.Assume that the encryption time ist and the expiration time is t′. Formula 22 shows that the attacker cannot get rk using the old revocation key dkω,t, so the initial session cannot be established.(22)c1edi,cωeDi,c2t′/t′−ωeei,cteEi,c2ω/ω−t′=rk⋅eg1,g2zerig,zHg2,J,h1,h2,h3ωeaiω+ag2+riHg2,J,h1,h2,h3ω,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2+riHg2,J,h1,h2,h3t′,zgω/ω−t′=rk⋅eg1,g2zerig,zHg2,J,h1,h2,h3ωeaiω+ag2,zg⋅eriHg2,J,h1,h2,h3ω,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2,zg⋅eriHg2,J,h1,h2,h3t′,zgω/ω−t′=rk⋅eg1,g2z1eaiω+ag2,zgt′/t′−ωerig,zHg2,J,h1,h2,h3teait′+ag2,zg⋅eriHg2,J,h1,h2,h3t′,zgω/ω−t′≠rk.


## 5. Security Proof

We first prove the correctness of the scheme, then introduce the security model, and subsequently show that the scheme is IND-ID-CPA secure.Theorem 1.
Our IBE-Signal scheme satisfied the correctness property.Proof.
To facilitate the proof, we distinguish the corresponding recipient symbols by adding “’”, e.g.RootInput and RootInput’.Lemma 1.
TheSESSION part satisfied the correctness property.Proof .
(23)RootInput′=H2eSIDB,U=H2eS0...SnQIDB,rP=H2eQIDB,S0...SnPr=H2eQIDB,Yr=RootInputrk′=c1edi,cωeDi,c2t/t−ωeei,cteEi,c2ω/ω−t=rk⋅eg1,g2z⋅erig,zHg2,J,h1,h2,h3ωeaiω+ag2+riHg2,J,h1,h2,h3ω,zgt/t−ω⋅erig,zHg2,J,h1,h2,h3teait+ag2+riHg2,J,h1,h2,h3t,zgω/ω−t=rk⋅eg1,g2z⋅erig,zHg2,J,h1,h2,h3ωeaiω+ag2,zg⋅eriHg2,J,h1,h2,h3ω,zgt/t−ω⋅erig,zHg2,J,h1,h2,h3teait+ag2,zg⋅eriHg2,J,h1,h2,h3t,zgω/ω−t=rk⋅eg1,g2z⋅1eaiω+ag2,zgt/t−ω⋅1eait+ag2,zgω/ω−t=rk⋅eg1,g2z⋅1eaiωg2,zg⋅eag2,zgt/t−ω⋅1eaitg2,zg⋅eag2,zgω/ω−t=rk⋅eg1,g2z⋅1eaig2,zgωt/t−ω⋅eag2,zgt/t−ω⋅1eaig2,zgtω/ω−t⋅eag2,zgω/ω−t=rk⋅eg1,g2z⋅1eaig2,zgωt/t−ω⋅eaig2,zgtω/ω−t⋅1eag2,zgt/t−ω⋅eag2,zgω/ω−t=rk⋅eg1,g2z⋅1eag2,zg=rk⋅eg1,g2z⋅1eg2,agz=rk⋅eg1,g2z⋅1eg2,g1z=rkMTσ=DecV,ek′=DecEncMTσ,ek,H3H6RootInput′,rk′=DecEncMTσ,ek,H3H6RootInput,rk=DecEncMTσ,ek,ek=MTσ.Lemma 2.
TheCONNECTION part satisfied the correctness property.Proof.
(24)M1=DecEncM1,S_Session1_K1,R_Session1_K1=DecEncM1,S_Session1_K1,H3KDFDHkey_R_Session1,RK=DecEncM1,S_Session1_K1,H3KDFrPKB1,RK=DecEncM1,S_Session1_K1,H3KDFrSKB1P,RK=DecEncM1,S_Session1_K1,H3KDFSKB1rP,RK=DecEncM1,S_Session1_K1,H3KDFSKB1U,RK=DecEncM1,S_Session1_K1,H3KDFDHkey_S_Session1,RK=DecEncM1,S_Session1_K1,S_Session1_K1=M1.Lemma 3.
TheSign&Verify part satisfied the correctness property.Proof.
(25)y′=H5M‖T,R′=H5M‖T,eF,PeQIDA,−Yy=H5M‖T,eySIDA+bO,PeQIDA,−Yy=H5M‖T,eySIDA,PebO,PeQIDA,−Yy=H5M‖T,eS0...SnQIDA,PyeO,PbeQIDA,−Yy=H5M‖T,eQIDA,YyeO,PbeQIDA,−Yy=H5M‖T,eO,Pb=H5M‖T,R=y.


### 5.1. Security Model

It should be noted that the proof of the IND-sRID-CPA security of the RIBE scheme is given in [18], so the revocation key rk is provided directly by the challenger in the Setup phase of our game. The next game describes the security model of our scheme:Setup. The challenger inputs a secure parameter κ and outputs public parameters params, revocation key rk, and private keys a and Si where i = 0, 1, 2, …, n. The challenger sends params and rk to the adversary. The challenger controls the following queries and can be queried by the adversary.H1queries: Given identity ID, the challenger runs these queries and gives QID.H2queries: Given Fj∈G2, the challenger runs these queries and gives Hj∈0,1κ.Phase 1. The adversary chooses an ID and sends queries of partial private keys of the ID. The challenger generates the partial private keys SIDi=∏h=0iShQIDi=0,1,...,n. and then sends them to the adversary.Challenge. The adversary outputs two plaintexts M0, M1 of equal length and the identity ID∗ intentionally to challenge. The only restriction is that ID∗ does not appear in any query in Phase 1. The adversary sends M0, M1 and ID∗ to the challenger. The challenger randomly chooses k as the honest CPC’s serial number and generates the partial private key SIDi∗=∏h=0,h≠kiShQID∗. The challenger randomly chooses a bit β←R0,1 and computes C∗=EncMβ,SID∗ where SID∗=∏h=0nShQID∗ then sends SIDi∗i=0,1,...,n,i≠k and C∗ to the adversary.Phase 2. The adversary sends queries of partial private keys of IDID≠ID∗ to the challenger. The challenger responds in the way of Phase 1.Guess. The adversary outputs his guess β′∈0,1. If β′=β, the adversary attacks the IBE-Signal scheme successfully.The adversary’s advantage is defined as the function of the safe parameterκ:(26)AdvA,IBE−SignalIND−ID−CPAκ=Prβ′=β−12.Theorem 2.
Assume H1 and H2 are random oracle models, and the BDH problem is infeasible to solve; our IBE-Signal scheme is semantically secure against IND-ID-CPA attack.Proof.
Expressly, assume the adversaryA can run at most qE>0 partial private key queries and qH2>0H2 queries. Assume A can break our scheme in polynomial time with probability εκ; there must be an adversary B that can solve the BDH problem with advantage at least ε′κ, where ε′κ≥2εκ/e1+qEqH2, e is the base of the natural logarithm.
Theorem2 reduces our IBE-Signal scheme to the BDH problem. To prove this reduction, firstly, we reduce the IBE-Signal scheme to a nonidentity-based encryption scheme BasicPub. Then, we reduce the BasicPub scheme to the BDH problem. The transitivity of the reduction is noticeable.Lemma 4.
AssumeH1 is a random oracle model from 0,1∗ to G1∗ and the adversary A attacks the IBE-Signal scheme with advantage εκ in the IND-ID-CPA game. Assume A can run at most qE>0 partial private key queries. There must be an adversary B that can attack BasicPub successfully with an advantage εκ/e1+qE in the IND-CPA game.Proof.
The challenger first constructs the BasicPub scheme.B attacks the BasicPub scheme by taking A as a subroutine.4.1. Establish the BasicPub scheme.The challenger generates public parameters of the BasicPub scheme.(27)Kpub=q,G1,G2,e,κ,k,P,Pi,Yi,QID,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk.And keeps the keya and the partial key Si private, where i = 0, 1, 2, …, n. The challenger sends Kpub to the adversary B.4.2.B partial private key queries.The challenger randomly choosesk as the honest CPC’s serial number, generates the partial private keys SIDi=∏h=0,h≠kiShQIDi=0,1,...,n,i≠k, and then sends them to B.the following 4.3–4.8 steps,B simulates A′s challenger to play IND-ID-CPA game with A.4.3. Establish the IBE-Signal scheme.B sends the IBE-Signal scheme’s public parameters(28)Kpub′=q,G1,G2,e,κ,k,P,Pi,Yi,H1,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk,toA. Since Kpub of the BasicPub scheme does not contain H1, B needs to construct a 4-tuple H1listIDj,QIDj,bj,coin to simulate A′s challenger.4.4.H1 queries.(i)
IfAqueriestheH1valuesofIDj,Bwill responds asfollows:(ii)
IfIDjalready existsinH1list,BrespondsQIDj∈G1∗.(iii)
Else,Brandomlychoosescoin←R0,1(iv)
andsetsPrcoin=0=δ,thenBchoosesbj←RZq∗,(v)
Ifcoin=0,computesQIDj=bjQID∈G1∗.(vi)
Else,computesQIDj=bjP∈G1∗.(vii)
BaddsIDj,QIDj,bj,cointoH1listandrespondsQIDjtoA.wherecoin=0 represents that B thinks A will challenge ID∗ in this query.4.5.A partial private key queries – Phase I.This step and step 4.7 can run at mostqE times in total. Assume A initiates a query on IDj to B and each round of the query is independent.(i)
BtakesIDj,QIDj,bj,coinfromH1list.(ii)
Ifcoin=0,Breportsanerrorandexits.(iii)
Else,BcomputesSIDij=bjYi=bj∏h=0iShP=∏h=0iShbjP=∏h=0iShQIDj,(iv)
andsendsSIDiji=0,1,...,n.toAasthepartialprivatekey.4.6. challenge.AssumeA challenges ID∗,M0,M1. B takes IDj,QIDj,bj,coin from H1list so that IDj=ID∗.(i)
Ifcoin=1,reportsanerrorandexits(ii)
Else,computesSIDij=bjSIDi=bj∏h=0,h≠kiShQID(iii)
=∏h=0,h≠kiShbjQID=∏h=0,h≠kiShQIDj(iv)
andsendsSIDiji=0,1,...,n,i≠ktoA(v)
BsendsM0,M1tothechallenger.(vi)
Thechallengerchoosesβ←R0,1andencryptsMβ,(vii)
thensendsC∗=U,V,rctoB.(viii)
BcomputesC∗=bj−1U,V,rcandsendsittoAashisresponse(29)eSID∗,bj−1U=eSnSn−1…S0bjQID,bj−1rP=eQID,SnSn−1…S0Pr=eQID,Yr.4.7.A partial private key queries–Phase II.Phase II is the same as Phase I.4.8. Guess.A outputs β′ as his guess and sends it to B. B sends β′ to the challenger as his guess.Assertion 1.
In the above reduction process, ifB does not exist, the simulation of B is complete.
From Assertion 1,A′s advantage in a simulated attack is equal to that in an actual attack, at least εκ. If A attacks the IBE-Signal scheme successfully in step 4.8, B can attack the BasicPub scheme successfully.
Since the probability ofB without interruption is 1−δqE in steps 4.5, 4.7, and δ in step 4.6. The advantage AdvBasicPub,BIND−CPAκ is at least 1−δqE⋅δ⋅εκ. Consider AdvBasicPub,BIND−CPAκ is the function of δ. It can be calculated that when δ=1/qE+1, AdvBasicPub,BIND−CPAκ reaches the maximum.(30)AdvBasicPub,BIND−CPAκmax=1−1qE+1qE1qE+1εκ>limqE⟶∞1−1qE+1qEεκqE+1=εκeqE+1.
Therefore, the advantage ofB is at least εκ/e1+qE.Lemma 5.
AssumeH2 is a random oracle model from G2 to 0,1κ. The adversary A attacks the BasicPub scheme with an advantage εκ and A can run at most qH2>0H2 queries. There must be an adversary B that can solve the BDH problem on G with an advantage 2εκ/qH2.Proof.
B already knows P,aP,bP,cP and intends to compute eP,Pabc∈G2 through the attack of A on the BasicPub scheme.5.1.B generates public parameters of the BasicPub scheme(31)Kpub=q,G1,G2,e,κ,k,P,Pi,Yi,QID,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk.Some parameters ofKpub are generated as follows: Let QID be bP. B randomly chooses k as the honest CPC’s serial number and generates Sii=0,1,...,n,i≠k, then computes Pk=aP, Pi=SiPi=0,1,...,n,i≠k, Yi=∏h=0iShPi=0,1,2,...,k−1, Yi=∏h=0,h≠kiShaP=∏h=0,h≠kiSh⋅aPi=k,k+1,...,n, and Y=Yn=∏h=0,h≠knSh⋅aP.5.2.H2 queries.B constructs a 2-tuple H2listFj,Hj. A can issue H2 queries at any time and at most qH2 times.(i)
IfFjalready existsinH2list,BrespondsH2Fj=Hj.(ii)
Else,randomlychoosesHj←R0,1κ,BrespondsH2Fj=Hj(iii)
andaddFj,HjintoH2list.5.3. Partial private key queries.B generates the partial private keys SIDi=∏h=0,h≠kiShQIDi=0,1,...,n,i≠k, then sends them to A.5.4. Challenge.A outputs M0, M1 to challenge. B randomly chooses β←R0,1 and sends C∗=U,V,rc to A. Let U be ∏h=0,h≠knSh−1⋅cP. To decrypt C∗, A should compute:(32)H2SID,U=H2∏h=0,h≠knSh⋅aQID,∏h=0,h≠knSh−1⋅cP=H2∏h=0,h≠knSh⋅a⋅bP,∏h=0,h≠knSh−1⋅cP=H2abP,cP=H2P,Pabc.A issues the H2 queries before decrypting C∗ and the BDH problem’s solution will be embedded in H2list.5.5. Guess.A outputs β′∈0,1. Meanwhile, B randomly chooses Fj,Hj from H2list and let Fj be the solution to the BDH problem.Assertion 2.
In the above simulation process, the simulation ofB is complete.Assertion 3.
LetΛ denotes the event: in the above simulation, A has issued the query H2eSID,U. Then, PrΛ≥2ε.Proof.
Obviously,Prβ′=β|¬Λ=1/2. We know Prβ′=β−1/2≥ε. So,(33)Prβ′=β,=Prβ′=β|¬ΛPr¬Λ+Prβ′=β|ΛPrΛ≤Prβ′=β|¬ΛPr¬Λ+PrΛ=12Pr¬Λ+PrΛ=121−PrΛ+PrΛ=12+12PrΛPrβ′=β≥Prβ′=β|¬ΛPr¬Λ=12Pr¬Λ=121−PrΛ=12−12PrΛε≤Prβ′=β−12≤12PrΛPrΛ≥2ε.
From Assertion 2 and Assertion 3,B solves the BDH problem with the probability at least 2ε/qH2.
From Lemma4, there is an adversary B′ that attacks the BasicPub scheme with the advantage of at least ε1=εκ/e1+qE. From Lemma 5, there is an adversary B that solves the BDH problem on G with the advantage of at least 2ε1/qH2=2εκ/e1+qEqH2.


## 5.1. Security Model

It should be noted that the proof of the IND-sRID-CPA security of the RIBE scheme is given in [18], so the revocation key rk is provided directly by the challenger in the Setup phase of our game. The next game describes the security model of our scheme:Setup. The challenger inputs a secure parameter κ and outputs public parameters params, revocation key rk, and private keys a and Si where i = 0, 1, 2, …, n. The challenger sends params and rk to the adversary. The challenger controls the following queries and can be queried by the adversary.H1queries: Given identity ID, the challenger runs these queries and gives QID.H2queries: Given Fj∈G2, the challenger runs these queries and gives Hj∈0,1κ.Phase 1. The adversary chooses an ID and sends queries of partial private keys of the ID. The challenger generates the partial private keys SIDi=∏h=0iShQIDi=0,1,...,n. and then sends them to the adversary.Challenge. The adversary outputs two plaintexts M0, M1 of equal length and the identity ID∗ intentionally to challenge. The only restriction is that ID∗ does not appear in any query in Phase 1. The adversary sends M0, M1 and ID∗ to the challenger. The challenger randomly chooses k as the honest CPC’s serial number and generates the partial private key SIDi∗=∏h=0,h≠kiShQID∗. The challenger randomly chooses a bit β←R0,1 and computes C∗=EncMβ,SID∗ where SID∗=∏h=0nShQID∗ then sends SIDi∗i=0,1,...,n,i≠k and C∗ to the adversary.Phase 2. The adversary sends queries of partial private keys of IDID≠ID∗ to the challenger. The challenger responds in the way of Phase 1.Guess. The adversary outputs his guess β′∈0,1. If β′=β, the adversary attacks the IBE-Signal scheme successfully.The adversary’s advantage is defined as the function of the safe parameterκ:(26)AdvA,IBE−SignalIND−ID−CPAκ=Prβ′=β−12.Theorem 2.
Assume H1 and H2 are random oracle models, and the BDH problem is infeasible to solve; our IBE-Signal scheme is semantically secure against IND-ID-CPA attack.Proof.
Expressly, assume the adversaryA can run at most qE>0 partial private key queries and qH2>0H2 queries. Assume A can break our scheme in polynomial time with probability εκ; there must be an adversary B that can solve the BDH problem with advantage at least ε′κ, where ε′κ≥2εκ/e1+qEqH2, e is the base of the natural logarithm.
Theorem2 reduces our IBE-Signal scheme to the BDH problem. To prove this reduction, firstly, we reduce the IBE-Signal scheme to a nonidentity-based encryption scheme BasicPub. Then, we reduce the BasicPub scheme to the BDH problem. The transitivity of the reduction is noticeable.Lemma 4.
AssumeH1 is a random oracle model from 0,1∗ to G1∗ and the adversary A attacks the IBE-Signal scheme with advantage εκ in the IND-ID-CPA game. Assume A can run at most qE>0 partial private key queries. There must be an adversary B that can attack BasicPub successfully with an advantage εκ/e1+qE in the IND-CPA game.Proof.
The challenger first constructs the BasicPub scheme.B attacks the BasicPub scheme by taking A as a subroutine.4.1. Establish the BasicPub scheme.The challenger generates public parameters of the BasicPub scheme.(27)Kpub=q,G1,G2,e,κ,k,P,Pi,Yi,QID,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk.And keeps the keya and the partial key Si private, where i = 0, 1, 2, …, n. The challenger sends Kpub to the adversary B.4.2.B partial private key queries.The challenger randomly choosesk as the honest CPC’s serial number, generates the partial private keys SIDi=∏h=0,h≠kiShQIDi=0,1,...,n,i≠k, and then sends them to B.the following 4.3–4.8 steps,B simulates A′s challenger to play IND-ID-CPA game with A.4.3. Establish the IBE-Signal scheme.B sends the IBE-Signal scheme’s public parameters(28)Kpub′=q,G1,G2,e,κ,k,P,Pi,Yi,H1,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk,toA. Since Kpub of the BasicPub scheme does not contain H1, B needs to construct a 4-tuple H1listIDj,QIDj,bj,coin to simulate A′s challenger.4.4.H1 queries.(i)
IfAqueriestheH1valuesofIDj,Bwill responds asfollows:(ii)
IfIDjalready existsinH1list,BrespondsQIDj∈G1∗.(iii)
Else,Brandomlychoosescoin←R0,1(iv)
andsetsPrcoin=0=δ,thenBchoosesbj←RZq∗,(v)
Ifcoin=0,computesQIDj=bjQID∈G1∗.(vi)
Else,computesQIDj=bjP∈G1∗.(vii)
BaddsIDj,QIDj,bj,cointoH1listandrespondsQIDjtoA.wherecoin=0 represents that B thinks A will challenge ID∗ in this query.4.5.A partial private key queries – Phase I.This step and step 4.7 can run at mostqE times in total. Assume A initiates a query on IDj to B and each round of the query is independent.(i)
BtakesIDj,QIDj,bj,coinfromH1list.(ii)
Ifcoin=0,Breportsanerrorandexits.(iii)
Else,BcomputesSIDij=bjYi=bj∏h=0iShP=∏h=0iShbjP=∏h=0iShQIDj,(iv)
andsendsSIDiji=0,1,...,n.toAasthepartialprivatekey.4.6. challenge.AssumeA challenges ID∗,M0,M1. B takes IDj,QIDj,bj,coin from H1list so that IDj=ID∗.(i)
Ifcoin=1,reportsanerrorandexits(ii)
Else,computesSIDij=bjSIDi=bj∏h=0,h≠kiShQID(iii)
=∏h=0,h≠kiShbjQID=∏h=0,h≠kiShQIDj(iv)
andsendsSIDiji=0,1,...,n,i≠ktoA(v)
BsendsM0,M1tothechallenger.(vi)
Thechallengerchoosesβ←R0,1andencryptsMβ,(vii)
thensendsC∗=U,V,rctoB.(viii)
BcomputesC∗=bj−1U,V,rcandsendsittoAashisresponse(29)eSID∗,bj−1U=eSnSn−1…S0bjQID,bj−1rP=eQID,SnSn−1…S0Pr=eQID,Yr.4.7.A partial private key queries–Phase II.Phase II is the same as Phase I.4.8. Guess.A outputs β′ as his guess and sends it to B. B sends β′ to the challenger as his guess.Assertion 1.
In the above reduction process, ifB does not exist, the simulation of B is complete.
From Assertion 1,A′s advantage in a simulated attack is equal to that in an actual attack, at least εκ. If A attacks the IBE-Signal scheme successfully in step 4.8, B can attack the BasicPub scheme successfully.
Since the probability ofB without interruption is 1−δqE in steps 4.5, 4.7, and δ in step 4.6. The advantage AdvBasicPub,BIND−CPAκ is at least 1−δqE⋅δ⋅εκ. Consider AdvBasicPub,BIND−CPAκ is the function of δ. It can be calculated that when δ=1/qE+1, AdvBasicPub,BIND−CPAκ reaches the maximum.(30)AdvBasicPub,BIND−CPAκmax=1−1qE+1qE1qE+1εκ>limqE⟶∞1−1qE+1qEεκqE+1=εκeqE+1.
Therefore, the advantage ofB is at least εκ/e1+qE.Lemma 5.
AssumeH2 is a random oracle model from G2 to 0,1κ. The adversary A attacks the BasicPub scheme with an advantage εκ and A can run at most qH2>0H2 queries. There must be an adversary B that can solve the BDH problem on G with an advantage 2εκ/qH2.Proof.
B already knows P,aP,bP,cP and intends to compute eP,Pabc∈G2 through the attack of A on the BasicPub scheme.5.1.B generates public parameters of the BasicPub scheme(31)Kpub=q,G1,G2,e,κ,k,P,Pi,Yi,QID,H2,H3,H4,H5,H6,KDF,g,g1,g2,h1,h2,h3,τ,rk.Some parameters ofKpub are generated as follows: Let QID be bP. B randomly chooses k as the honest CPC’s serial number and generates Sii=0,1,...,n,i≠k, then computes Pk=aP, Pi=SiPi=0,1,...,n,i≠k, Yi=∏h=0iShPi=0,1,2,...,k−1, Yi=∏h=0,h≠kiShaP=∏h=0,h≠kiSh⋅aPi=k,k+1,...,n, and Y=Yn=∏h=0,h≠knSh⋅aP.5.2.H2 queries.B constructs a 2-tuple H2listFj,Hj. A can issue H2 queries at any time and at most qH2 times.(i)
IfFjalready existsinH2list,BrespondsH2Fj=Hj.(ii)
Else,randomlychoosesHj←R0,1κ,BrespondsH2Fj=Hj(iii)
andaddFj,HjintoH2list.5.3. Partial private key queries.B generates the partial private keys SIDi=∏h=0,h≠kiShQIDi=0,1,...,n,i≠k, then sends them to A.5.4. Challenge.A outputs M0, M1 to challenge. B randomly chooses β←R0,1 and sends C∗=U,V,rc to A. Let U be ∏h=0,h≠knSh−1⋅cP. To decrypt C∗, A should compute:(32)H2SID,U=H2∏h=0,h≠knSh⋅aQID,∏h=0,h≠knSh−1⋅cP=H2∏h=0,h≠knSh⋅a⋅bP,∏h=0,h≠knSh−1⋅cP=H2abP,cP=H2P,Pabc.A issues the H2 queries before decrypting C∗ and the BDH problem’s solution will be embedded in H2list.5.5. Guess.A outputs β′∈0,1. Meanwhile, B randomly chooses Fj,Hj from H2list and let Fj be the solution to the BDH problem.Assertion 2.
In the above simulation process, the simulation ofB is complete.Assertion 3.
LetΛ denotes the event: in the above simulation, A has issued the query H2eSID,U. Then, PrΛ≥2ε.Proof.
Obviously,Prβ′=β|¬Λ=1/2. We know Prβ′=β−1/2≥ε. So,(33)Prβ′=β,=Prβ′=β|¬ΛPr¬Λ+Prβ′=β|ΛPrΛ≤Prβ′=β|¬ΛPr¬Λ+PrΛ=12Pr¬Λ+PrΛ=121−PrΛ+PrΛ=12+12PrΛPrβ′=β≥Prβ′=β|¬ΛPr¬Λ=12Pr¬Λ=121−PrΛ=12−12PrΛε≤Prβ′=β−12≤12PrΛPrΛ≥2ε.
From Assertion 2 and Assertion 3,B solves the BDH problem with the probability at least 2ε/qH2.
From Lemma4, there is an adversary B′ that attacks the BasicPub scheme with the advantage of at least ε1=εκ/e1+qE. From Lemma 5, there is an adversary B that solves the BDH problem on G with the advantage of at least 2ε1/qH2=2εκ/e1+qEqH2.


## 6. Performance Evaluation

We mainly evaluated the performance of our scheme from the computational overhead and the security features. To facilitate the calculation of overhead, we implemented it by calculating and combining cryptographic operations, which is also adopted in [17, 36–39]. Moreover, the implementation of the IBE-Signal scheme was based on OpenSSL v1.1.1f and the Type-A curve of the PBC library and was performed on a Dell Inspiron 7580 with Intel Core i7-8565U CPU (1.80 GHz) and 16 GB memory, running Ubuntu 64-bit Linux (v20.04.4 LTS). For the pairing-based scheme, to achieve the 1,024-bit RSA level security, we used the Tate pairing defined over the supersingular elliptic curve E/FP:y2=x3+x with embedding degree 2, where q is a 160-bit Solinas prime q=2159+217+1 and p a 512-bit prime satisfying p+1=12qr. For the ECC-based schemes, to achieve the same security level, we employed the ECC group on Koblitz elliptic curve y2=x3+ax2+b defined on F2163 with a=1 and b a 163-bit random prime.


### 6.1. The Computational Overhead of Our Scheme

Table3 shows the time taken for the cryptographic operations involved in this paper. We define the overhead of modular multiplication as TM, the overhead of modular inversion as TI, the overhead of two elliptic curve points addition as TA, the overhead of elliptic curve scalar point multiplication as TS, the overhead of exponentiation as TE, the overhead of one-to-one hash mapping as THα, the overhead of two-to-one hash mapping as THβ, the overhead of bilinear pairing as TP, and the overhead of encryption or decryption of the 1 KB size message using AES-128 at CTR mode as TAES−128. From [17], we have obtained TI=11.60TM and THα=29.00TM. Then, we calculated the overheads of TM=0.13ms, THβ=15.63ms, and TAES−128=3.48ms separately. In [40], TA=0.12TM, TS=29.00TM, and TE=240.00TM have been given. It has been given in [39] that the overhead of bilinear pairing TP=3.00TS=87.00TM.Table 3
Computational overhead of operations.
NotationsDefinitionInTMTime (ms)TMModular multiplication1.00TM≈0.13TIModular inversion11.60TM≈1.51TATwo elliptic curve points addition0.12TM≈0.02TSElliptic curve scalar point multiplication29.00TM≈3.77TEExponentiation240.00TM≈31.2THαOne-to-one hash mapping29.00TM≈3.77THβTwo-to-one hash mapping120.23TM≈15.63TPBilinear pairing87.00TM≈11.31TAES−128Encryption or decryption of the 1 KB size message using AES-128 at CTR mode26.77TM≈3.48As shown in Table4, we calculated the number of operations and the computational overhead of each subalgorithm of the IBE-Signal scheme according to Table 3. Among them, the CPCs are selected as ten, and the number of users is selected as 1 billion. The overhead of the SESSION part of our scheme is 3206.45 ms. However, the SESSION part only runs when the two opposing parties communicate for the first time, so a computational overhead of 3 seconds is acceptable. After the SESSION part is established, the CONNECTION part takes only 57.07 ms. Further, if the communication parties are not in the first message in each round of session, the computational overhead can be reduced to 14.5 ms.Table 4
Computational overhead of the subalgorithms in our scheme IBE-Signal forn=10, the number of the CPCs and nu=1,000,000,000, and the number of users.
PhasesOperationsTime(ms)SESSIONSetupKGC setupTS3.77CPC setupnn−1/2TP+nTS546.65Key authority setupTS3.77Encryption key generationEncryption RootInput generation2THα+TS+TP+TE53.82Encryption revocation key generation3THα+TP+TE+,12TS+6TM+THβ.115.47SignSender’s private key generationTI+2n+5TS+,n+2THα+n+2TP276.72Signature generationTP+TE+THβ+2TS+TA65.7EncryptEncryptTAES−1283.48Decryption key generationReceiver’s private key generationTI+2n+5TS+,n+2THα+n+2TP276.72Decryption RootInput generationTP+THα15.08Revocation private keys generation⌈log2nu+1⌉7TS+3TM+THα833.95Revocation key updates generation⌈log2nu⌉7TS+3TM+THα807.17Revocation key selection00Decryption revocation key generation2TM+2TI+4TP,+2TE+THα+THβ130.32DecryptDecryptTAES−1283.48VerifyVerifyTHα+2TP+TM+TE+THβ73.35RevocationRevocation00SESSION total12+6⌈log2nu⌉TM+4TI+TA+34+5n+14⌈log2nu⌉TS+,6TE+2n+14THα+4THβ+nn+3/2+14TP+2TAES−1283206.45CONNECTIONSender key generation2TS+THα+THβorTHα26.94EncryptTAES−1283.48Receiver key generationTS+THα+THβorTHα23.17DecryptTAES−1283.48CONNECTION total3Ts+2THα+2THβ+2TAES−12857.07Total12+6⌈log2nu⌉TM+4TI+TA+37+5n+14⌈log2nu⌉TS+,6TE+2n+16THα+6THβ+nn+3/2+14TP+4TAES−1283263.52The number of CPCsn is essential in determining the system's computational overhead. Theoretically, the more the number of the CPCs, the lower the risk of the key escrow problem, but the computational overhead also increases. In Figure 15, we show the relationship between the computational overhead of each subalgorithm and n from 1 to 10. Among them, the computational overhead of three subalgorithms CPC Setup, Sender’s Private Key Generation, and Receiver’s Private Key Generation increases as n increases. In addition to the number of the CPCs, the computational overhead of the two subalgorithms Revocation Private Keys Generation and Revocation Key Updates Generation is related to the number of users nu. We give the overhead trend as nu grows in Figure 16, where nu grows from 1 million to 1 billion. Considering the monthly active users in Table 1, we set the number of users to 1 billion. Furthermore, the algorithm’s time complexity is OlogN due to a binary tree structure. This results in a computational overhead of only about 800 ms, even with a billion users.Figure 15
The computational overhead of each subalgorithm of the IBE-Signal scheme.Figure 16
The computational overhead ofRevocation Private Keys Generation and Revocation Key Updates Generation.


### 6.2. Comparison of the Computational Overhead with Other Schemes

In Table5 and Figure 17, we compare the computational overhead between our scheme and other schemes. Moreover, the comparison mainly focuses on the two stages of Setup and Key Extraction. As shown in Figure 17, the SESSION part overhead of our scheme is lower than the Kumar et al. scheme [17] when the number of the CPCs is less than 8. Even if there are less than 8 CPCs, they can already provide sufficient private key distribution protection. Moreover, the CONNECTION part of our scheme is a constant function for n. Our scheme runs the CONNECTION part in most cases, so our scheme is still competitive in computational overhead.Table 5
The computational overhead of our scheme and other schemes.
SchemesSetup and key extractionTimeKumar and Chand [17]4n+6TP+TS+THα≈60.32n+94.25Chen et al. [41]3+nTS+2+nTA≈3.79n+11.35Chen et al. [42]4n+7TS+TA≈15.16n+26.53Li et al. [43]2+nTS+nTA+TP≈3.79n+18.85Our scheme.TI+3n+7TS+n+2THα+n2+n+4/2TP≈5.655n2+20.735n+58.06Figure 17
Comparison of the computational overhead with other schemes.


### 6.3. Comparison of the Security Features with Other Schemes

Table6 compares our scheme with other schemes in terms of security features. We define Resilient to the Key Escrow Problem as RKEP, Resilient to the Secure Key Issuing Problem as RSKIP, Resilient to the User Slandering Problem as RUSP, Support Mutual Authentication as SMA, Support Perfect Forward Secrecy as SPFS, Support Post‐compromise Security as SPCS, and Support Key Revocation as SKR. The KGC cannot directly generate private keys for users in our scheme, so the scheme has the RKEP feature. The blind signature enables the KGC or the CPCs to issue the private key without seeing the actual information sent by the user, which provides the RSKIP feature for the scheme. The CPCs have a master key slice, which spreads the risk of private key distribution and provides the RUSP feature. Furthermore, we provide the SMA feature by introducing IBS. Since our CONNECTION part is based on the Double Ratchet algorithm, we provide both the SPFS feature and the SPCS feature. Finally, we introduce the Revocable IBE to provide the SKR feature.Table 6
Comparison of the security features between our scheme and other schemes.
SchemesRKEPRSKIPRUSPSMASPFSSPCSSKRKumar and Chand [17]✓✓✓✗✗✗✗Chen et al. [41]✓✗✗✗✗✗✗Chen et al. [42]✓✓✗✗✗✗✗Li et al. [43]✓✗✗✗✗✗✗Boldyreva et al. [18]✗✗✗✗✗✗✓Our scheme✓✓✓✓✓✓✓


## 6.1. The Computational Overhead of Our Scheme

Table3 shows the time taken for the cryptographic operations involved in this paper. We define the overhead of modular multiplication as TM, the overhead of modular inversion as TI, the overhead of two elliptic curve points addition as TA, the overhead of elliptic curve scalar point multiplication as TS, the overhead of exponentiation as TE, the overhead of one-to-one hash mapping as THα, the overhead of two-to-one hash mapping as THβ, the overhead of bilinear pairing as TP, and the overhead of encryption or decryption of the 1 KB size message using AES-128 at CTR mode as TAES−128. From [17], we have obtained TI=11.60TM and THα=29.00TM. Then, we calculated the overheads of TM=0.13ms, THβ=15.63ms, and TAES−128=3.48ms separately. In [40], TA=0.12TM, TS=29.00TM, and TE=240.00TM have been given. It has been given in [39] that the overhead of bilinear pairing TP=3.00TS=87.00TM.Table 3
Computational overhead of operations.
NotationsDefinitionInTMTime (ms)TMModular multiplication1.00TM≈0.13TIModular inversion11.60TM≈1.51TATwo elliptic curve points addition0.12TM≈0.02TSElliptic curve scalar point multiplication29.00TM≈3.77TEExponentiation240.00TM≈31.2THαOne-to-one hash mapping29.00TM≈3.77THβTwo-to-one hash mapping120.23TM≈15.63TPBilinear pairing87.00TM≈11.31TAES−128Encryption or decryption of the 1 KB size message using AES-128 at CTR mode26.77TM≈3.48As shown in Table4, we calculated the number of operations and the computational overhead of each subalgorithm of the IBE-Signal scheme according to Table 3. Among them, the CPCs are selected as ten, and the number of users is selected as 1 billion. The overhead of the SESSION part of our scheme is 3206.45 ms. However, the SESSION part only runs when the two opposing parties communicate for the first time, so a computational overhead of 3 seconds is acceptable. After the SESSION part is established, the CONNECTION part takes only 57.07 ms. Further, if the communication parties are not in the first message in each round of session, the computational overhead can be reduced to 14.5 ms.Table 4
Computational overhead of the subalgorithms in our scheme IBE-Signal forn=10, the number of the CPCs and nu=1,000,000,000, and the number of users.
PhasesOperationsTime(ms)SESSIONSetupKGC setupTS3.77CPC setupnn−1/2TP+nTS546.65Key authority setupTS3.77Encryption key generationEncryption RootInput generation2THα+TS+TP+TE53.82Encryption revocation key generation3THα+TP+TE+,12TS+6TM+THβ.115.47SignSender’s private key generationTI+2n+5TS+,n+2THα+n+2TP276.72Signature generationTP+TE+THβ+2TS+TA65.7EncryptEncryptTAES−1283.48Decryption key generationReceiver’s private key generationTI+2n+5TS+,n+2THα+n+2TP276.72Decryption RootInput generationTP+THα15.08Revocation private keys generation⌈log2nu+1⌉7TS+3TM+THα833.95Revocation key updates generation⌈log2nu⌉7TS+3TM+THα807.17Revocation key selection00Decryption revocation key generation2TM+2TI+4TP,+2TE+THα+THβ130.32DecryptDecryptTAES−1283.48VerifyVerifyTHα+2TP+TM+TE+THβ73.35RevocationRevocation00SESSION total12+6⌈log2nu⌉TM+4TI+TA+34+5n+14⌈log2nu⌉TS+,6TE+2n+14THα+4THβ+nn+3/2+14TP+2TAES−1283206.45CONNECTIONSender key generation2TS+THα+THβorTHα26.94EncryptTAES−1283.48Receiver key generationTS+THα+THβorTHα23.17DecryptTAES−1283.48CONNECTION total3Ts+2THα+2THβ+2TAES−12857.07Total12+6⌈log2nu⌉TM+4TI+TA+37+5n+14⌈log2nu⌉TS+,6TE+2n+16THα+6THβ+nn+3/2+14TP+4TAES−1283263.52The number of CPCsn is essential in determining the system's computational overhead. Theoretically, the more the number of the CPCs, the lower the risk of the key escrow problem, but the computational overhead also increases. In Figure 15, we show the relationship between the computational overhead of each subalgorithm and n from 1 to 10. Among them, the computational overhead of three subalgorithms CPC Setup, Sender’s Private Key Generation, and Receiver’s Private Key Generation increases as n increases. In addition to the number of the CPCs, the computational overhead of the two subalgorithms Revocation Private Keys Generation and Revocation Key Updates Generation is related to the number of users nu. We give the overhead trend as nu grows in Figure 16, where nu grows from 1 million to 1 billion. Considering the monthly active users in Table 1, we set the number of users to 1 billion. Furthermore, the algorithm’s time complexity is OlogN due to a binary tree structure. This results in a computational overhead of only about 800 ms, even with a billion users.Figure 15
The computational overhead of each subalgorithm of the IBE-Signal scheme.Figure 16
The computational overhead ofRevocation Private Keys Generation and Revocation Key Updates Generation.


## 6.2. Comparison of the Computational Overhead with Other Schemes

In Table5 and Figure 17, we compare the computational overhead between our scheme and other schemes. Moreover, the comparison mainly focuses on the two stages of Setup and Key Extraction. As shown in Figure 17, the SESSION part overhead of our scheme is lower than the Kumar et al. scheme [17] when the number of the CPCs is less than 8. Even if there are less than 8 CPCs, they can already provide sufficient private key distribution protection. Moreover, the CONNECTION part of our scheme is a constant function for n. Our scheme runs the CONNECTION part in most cases, so our scheme is still competitive in computational overhead.Table 5
The computational overhead of our scheme and other schemes.
SchemesSetup and key extractionTimeKumar and Chand [17]4n+6TP+TS+THα≈60.32n+94.25Chen et al. [41]3+nTS+2+nTA≈3.79n+11.35Chen et al. [42]4n+7TS+TA≈15.16n+26.53Li et al. [43]2+nTS+nTA+TP≈3.79n+18.85Our scheme.TI+3n+7TS+n+2THα+n2+n+4/2TP≈5.655n2+20.735n+58.06Figure 17
Comparison of the computational overhead with other schemes.


## 6.3. Comparison of the Security Features with Other Schemes

Table6 compares our scheme with other schemes in terms of security features. We define Resilient to the Key Escrow Problem as RKEP, Resilient to the Secure Key Issuing Problem as RSKIP, Resilient to the User Slandering Problem as RUSP, Support Mutual Authentication as SMA, Support Perfect Forward Secrecy as SPFS, Support Post‐compromise Security as SPCS, and Support Key Revocation as SKR. The KGC cannot directly generate private keys for users in our scheme, so the scheme has the RKEP feature. The blind signature enables the KGC or the CPCs to issue the private key without seeing the actual information sent by the user, which provides the RSKIP feature for the scheme. The CPCs have a master key slice, which spreads the risk of private key distribution and provides the RUSP feature. Furthermore, we provide the SMA feature by introducing IBS. Since our CONNECTION part is based on the Double Ratchet algorithm, we provide both the SPFS feature and the SPCS feature. Finally, we introduce the Revocable IBE to provide the SKR feature.Table 6
Comparison of the security features between our scheme and other schemes.
SchemesRKEPRSKIPRUSPSMASPFSSPCSSKRKumar and Chand [17]✓✓✓✗✗✗✗Chen et al. [41]✓✗✗✗✗✗✗Chen et al. [42]✓✓✗✗✗✗✗Li et al. [43]✓✗✗✗✗✗✗Boldyreva et al. [18]✗✗✗✗✗✗✓Our scheme✓✓✓✓✓✓✓


## 7. Conclusion

We have proposed the IBE-Signal scheme to reshape the Signal into a MITM-attack-resistant protocol. Our scheme provides more security features (such as Perfect Forward Secrecy, Post‐compromise Security, and Key Revocation) than other schemes. Furthermore, experiments show that our scheme has less computational overhead when the number of the CPCs is less than 8. Moreover, we proved that our scheme is IND-ID-CPA secure under the random oracle model, even if only one CPC is credible. We increased the attackers’ capabilities in the proofs: some partial private keys ofID∗ can still be queried in the challenge phase. In the future, we will transform the IND-ID-CPA secure scheme into IND-ID-CCA secure scheme using the Fujisaki-Okamoto method [44].



---

*Source: 8653453-2022-07-21.xml*