1 Introduction
With the popularity of the Internet and wireless networks, a large number of cryptographic mechanisms have been proposed to ensure information/communication security for various applications based on public-key cryptography (PKC). Indeed, the most popular PKC today is still the public-key-infrastructure (PKI) PKC (PKI-PKC) (Rivest et al., 1978; ElGamal, 1985; Miller, 1985). In the PKI-PKC, each member has a secret/public key pair and there is a certificate authority (CA) who is responsible to generate and manage the associated certificates of all members’ public keys. However, the PKI-PKC requires a complex PKI architecture to maintain the validity of these certificates. In 2001, Boneh and Franklin (2001) realized Shamir’s identity (ID)-based concept (Shamir, 1984) to propose the ID-PKC. However, in the ID-PKC, there is a secret key generator (SKG) who is responsible to generate all members’ secret keys, so that the SKG knows these secret keys which incurs a key escrow problem. Now, the usage of the certificateless PKC (CL-PKC) has attracted the attention of researchers because it has neither certificate management nor key escrow problems.
For the mentioned PKCs (i.e. the PKI-PKC, the ID-PKC and the CL-PKC) above, all secret keys must be completely protected from leakage of any partial information. However, by side-channel attacks (Brumley and Boneh, 2005; Biham et al., 2008), an adversary could acquire partial information of secret keys participated in the computations of cryptographic mechanisms. Eventually, via continuous leakage, the existing cryptographic mechanisms based on these PKCs mentioned above could be broken. The designs of leakage-resilient (LR) cryptographic mechanisms resisting side-channel attacks have attracted the attention of cryptographic researches who have proposed many LR cryptographic mechanisms (Kiltz and Pietrzak, 2010; Galindo and Vivek, 2013; Wu et al., 2018, 2019; Peng et al., 2021; Tseng et al., 2022; Xie et al., 2023).
Anonymous multi-recipient signcryption (AMRS) is an important scheme of PKCs and applied for many modern digital applications, e.g. over-the-air (OTA) applications (Li et al., 2023), unmanned chain stores (Park and Zhang, 2022) and digital signages (Kim et al., 2024). In an AMRS scheme, there are a trusted authority, a broadcast management centre (BMC) and many recipients. The BMC and recipients first obtain their secret/public key pairs by interacting with the trusted authority. Also, the BMC may sign and encrypt a plaintext data (or file) to generate a broadcast ciphertext set (BCS), and convey the BCS to a set of multiple recipients via Internet. Meanwhile, only these recipients in the set can decrypt the plaintext data and authenticate the BMC while offering anonymity for their identities. The system architecture of an AMRS scheme in a PKC is depicted in Fig. 1.
1.1 Motivation
To our best knowledge, all the existing AMRS schemes are only suitable for multiple recipients under a single PKC and will be reviewed later. Here, let us consider the situation of the PKC upgradation as follows. When the original PKC (e.g. the PKI-PKC) is converted and upgraded to another new PKC (e.g. the CL-PKC), some recipients in the PKI-PKC are possibly not upgraded to the CL-PKC successfully. This situation, in the AMRS scheme, would result in three kinds of recipients, namely, initial (i.e. non-upgraded) recipients in the PKI-PKC, upgraded and new recipients in the CL-PKC, as illustrated in Fig. 2. Indeed, for the PKC upgradation, it is important to ensure that non-upgraded recipients can still use the original cryptographic functionalities (Ho et al., 2024; Tseng et al., 2024). However, the existing AMRS schemes are unsuitable for such heterogeneous PKCs. Additionally, the work on the design of leakage-resilient AMRS (LR-AMRS) schemes is little and only suitable for multiple recipients under a single PKC. Our aim of this paper is to propose the first leakage-resilient and seamlessly compatible AMRS (LRSC-AMRS) suitable for multiple recipients under two heterogeneous PKCs (i.e. the PKI-PKC and the CL-PKC).
1.2 Related Work
Here, the revolutions of AMRS and leakage-resilient AMRS (LR-AMRS) schemes based on different PKCs (i.e. the PKI-PKC, the ID-PKC and the CL-PKC) are reviewed.
Based on the PKI-PKC, Wang et al. (2016) employed the ring signcryption technique to propose the first PKI-AMRS scheme. Also, Tsai et al. (2022) used the concepts of both the LR encryption scheme in Kiltz and Pietrzak (2010) and the LR signature scheme in Galindo and Vivek (2013) to integrate multi-recipient scenario to propose the first PKI-LR-AMRS scheme based on the PKI-PKC. The PKI-LR-AMRS scheme not only possesses the functionalities and security properties of an AMRS scheme, but also permits an adversary to continuously acquire partial information of secret keys participated in the computations. Nevertheless, these AMRS schemes based on the PKI-PKC require a complex PKI architecture to maintain the validity of recipients’ certificates.
Based on the ID-PKC, Lal and Kushwah (2009) proposed the first ID-AMRS scheme, which employed the Lagrange interpolation polynomial technique to embed multiple recipients’ identities to achieve anonymity between these recipients. To achieve robust security, Zhang and Xu (2010) proposed an improved ID-AMRS scheme in the standard model. However, Wang et al. (2012) demonstrated that these two schemes (Lal and Kushwah, 2009; Zhang and Xu, 2010) cannot achieve anonymity because an authorized recipient can check whether other recipients are authorized. Furthermore, Pang et al. (2015) proposed a new ID-AMRS scheme based on the ID-PKC, which achieves the anonymity of both the sender and recipients. Nevertheless, these AMRS schemes based on the ID-PKC still inherit the key escrow problem.
Based on the CL-PKC, Pang et al. (2018) proposed the first CL-AMRS scheme. Also, Pang et al. (2019) proposed a new CL-AMRS scheme, which achieves the anonymity of both the sender and recipients. Moreover, to achieve a sender’s anonymity and traceability, Li et al. (2022) presented a new CL-AMRS scheme. For wireless body area networks, Shen et al. (2022) proposed a lightweight CL-AMRS scheme. Unfortunately, Dong and Zhang (2024) pointed out that Shen et al.’s scheme suffers from forgery attacks.
1.3 Techniques and Contributions
By the related work mentioned above, all the existing AMRS schemes are only suitable for multiple recipients under a single PKC (i.e. the PKI-PKC, the ID-PKC or the CL-PKC) and are unsuited for multiple recipients under heterogeneous PKCs. Also, among them, only Tsai et al.’s PKI-LR-AMRS scheme (2022) can withstand side-channel attacks and possess unbounded leakage resilience. We will adopt the same multiplicative blinding technique (Kiltz and Pietrzak, 2010; Galindo and Vivek, 2013; Tsai et al., 2022) to refresh secret keys in our proposed scheme. In this multiplicative blinding technique, each secret key is initially separated into two fragments. Before a secret key is participated in computations, the associated two fragments must be refreshed while remaining the corresponding public key unchanged. For achieving unbounded leakage resilience, a leakage-resilient cryptographic scheme must possess two pre-conditions, namely, bounded leakage of single computation and computation leakage. Indeed, due to the multiplicative blinding technique, any two leaked partial information of a secret key are mutually independent so that it achieves independent leakage property. Also, by the independent leakage property, the total leakage information of secret keys is unbounded.
By extending the syntaxes and security games of the PKI-LR-AMRS scheme (Tsai et al., 2022) in the PKI-PK and the leakage-resilient anonymous multi-recipient encryption (CL-LR-AMRE) scheme (Xie et al., 2023) in the CL-PKC, a new syntax and three security games of our proposed LRSC-AMRS scheme are demonstrated, respectively, to define the associated framework and three security properties, namely, encryption confidentiality, recipient anonymity and sender (i.e. BMC) authentication. In the generic bilinear pairing group (GBPG) model (Boneh et al., 2005), based on two security assumptions of the discrete logarithm (DL) and secure hash function (SHF), we will use three security theorems, respectively, to prove the three security properties. Finally, by comparing with the related schemes, our LRSC-AMRS scheme has four merits as follows. (1) It is the first LRSC-AMRS scheme suitable for heterogeneous PKCs. (2) Multiple recipients in the LRSC-AMRS scheme can be initial recipients in the PKI-PKC, or new and upgraded recipients in the CL-PKC. (3) Adversaries are allowed to continuously acquire partial information of secret keys for multiple rounds, the LRSC-AMRS scheme possesses unbounded leakage resilience. (4) The computational cost of the unsigncryption algorithm is constant.
1.4 Paper Structure
The remaining sections are organized as follows. Section 2 introduces four preliminaries. In Section 3, the new syntax and three security games of the LRSC-AMRS scheme are demonstrated to define the associated framework and three security properties, respectively. The LRSC-AMRS scheme is proposed in Section 4. Section 5, based on three security games, three theorems are formally shown. The comparisons and performance analysis between the LRSC-AMRS scheme and some related schemes are demonstrated in Section 6. In Section 7, conclusions are given.
2 Preliminaries
2.1 Bilinear Pairing Group Set
Let $G=\langle Q\rangle $ and ${G_{e}}=\langle {Q_{e}}\rangle $, respectively, denote an addition group and a multiplication group with the same prime order p, where Q and ${Q_{e}}$ are the associated group generators. Also, there exists a bilinear pairing mapping $\hat{e}$: $G\times G\to {G_{e}}$. These parameters above form a bilinear pairing group set $BPGS=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$ (Boneh and Franklin, 2001). The set BPGS possesses three properties as presented below.
2.2 GBPG Model
Here, let us introduce a technique in proving security theorems for cryptographic schemes by using the set $BPGS=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$, namely, the generic bilinear pairing group (GBPG) model (Boneh et al., 2005). The GBPG model is embedded in the adversary games of security theorems that are played by adversaries (querier) and a challenger (responder). When adversaries would like to perform all operations in the set $BPGS=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$, namely, the addition in G, the multiplication in ${G_{e}}$ and the bilinear pairing mapping $\hat{e}$, they must issue the corresponding queries (oracles) to the challenger. Upon receiving these queries, the challenger then responds the associated computation results. It is worth mentioning that all elements of G and ${G_{e}}$ are encoded into distinct bit strings by two random mappings. Also, adversaries can issue the other queries of adversary games for security properties possessed in a cryptographic scheme. At the end of an adversary game in the GBPG model, if adversaries can find collisions on G or ${G_{e}}$, the discrete logarithm (DL) security assumption defined below on G or ${G_{e}}$ will be broken.
In adversary games, the set $BPGS=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$ has three operations $O{P_{0}}$, $O{P_{e}}$ and $O{P_{bp}}$ that respectively denote the addition $a\cdot Q$, the multiplication ${{Q_{e}}^{a}}$ and the bilinear pairing mapping $\hat{e}(a\cdot Q,b\cdot Q)={{Q_{e}}^{ab}}$, for all $a,b\in {{Z_{p}}^{\ast }}$. Also, there are two mapping functions $\zeta :{{Z_{p}}^{\ast }}\to \Omega G$ and ${\zeta _{e}}:{{Z_{p}}^{\ast }}\to \Omega {G_{e}}$ that are employed to encode all elements of G and ${G_{e}}$ to distinct bit-strings. Additionally, two output sets $\Omega G$ and $\Omega {G_{e}}$ satisfy $|\Omega G|=|\Omega {G_{e}}|=p$ and $\Omega G\cap \Omega {G_{e}}=\phi $, where $|\cdot |$ denotes the number of $O{P_{0}}$, $O{P_{e}}$ and $O{P_{bp}}$ possess the following properties.
It is worth mentioning that $\zeta (1)$ and ${\zeta _{e}}(1)$ denote the group generators Q and ${Q_{e}}$, respectively.
2.3 Security Assumptions
In the set $BPGS=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$, two security assumptions of our LRSC-AMRS scheme are defined below.
-
– Discrete logarithm (DL) security assumption: For an unknown $a\in {Z_{p}^{\ast }}$, and given $a\cdot Q\in G$ or $\hat{e}{(Q,Q)^{a}}\in {G_{e}}$, to compute a is hard.
-
– Secure hash function (SHF) security assumption: For a secure hash function $SH:{\{0,1\}^{\ast }}\to {\{0,1\}^{l}}$ with a fixed length l, it must satisfy one-way, weak-collision resistance and strong-collision resistance.
2.4 Leakage Security of Secret Keys
To measure the leakage security of secret keys due to side-channel attacks, we employ the entropy values of these secret keys to evaluate their security impact. In the entropy, a fixed-length secret key is viewed as a finite random variable. Let $RV$ and $\text{Pb}[RV=rv]$ denote a finite random variable (fixed-length secret key) and the probability of the event $RV=rv$, respectively. Also, two types of minimal entropies for single finite random variable are defined as follows.
To consider the entropy of single secret key (i.e. finite random variable $RV$) under a leakage function $LF$, Dodis et al. (2008) derived an inequality between two types of minimal entropies (Lemma 1). For multiple fixed-length secret keys (e.g. finite random variables $R{V_{0}},R{V_{1}},\dots ,R{V_{n-1}}$), Galindo and Vivek (2013) obtained Lemma 2 below.
Lemma 1.
Let $LF:RV\to {\{0,1\}^{\gamma }}$ be a leakage function of $RV$ with a fixed-bit-length γ. Thus, we have ${\widetilde{H}_{\infty }}(RV|LF(RV))\geqq {H_{\infty }}(RV)-\gamma $.
Lemma 2.
Let $MP\in {Z_{p}^{\ast }}[R{V_{0}},R{V_{1}},\dots ,R{V_{n-1}}]$ be a multiple-variable polynomial with maximal degree d. For $i=0,1,\dots ,n-1$, let $P{D_{i}}$ be mutually independent probability distributions of $R{V_{i}}=r{v_{i}}\gets {Z_{p}^{\ast }}$ such that both ${H_{\infty }}(P{D_{i}})\geqq \log p-\gamma $ and $0\leqq \gamma \leqq \log p$. If $\gamma \lt \log p(1-\epsilon )$ and ϵ is a positive decimal, the probability $\textit{Pb}[MP(R{V_{0}}=r{v_{0}},R{V_{1}}=r{v_{1}},\dots ,R{V_{n-1}}=r{v_{n-1}})=0]\leqq {2^{\gamma }}(d/p)$ is negligible.
3 Syntax (Framework) and Adversary Model of the LRSC-AMRS Scheme
In this section, we present the syntax (framework) and adversary model of the leakage-resilient and seamlessly compatible anonymous multi-recipient signcryption (LRSC-AMRS) scheme in heterogeneous public-key cryptographies. For convenience, we first present the denotations of several symbols in Table 1.
Table 1
Denotations of symbols.
| Symbols | Denotations |
| PKC | Public-key cryptography |
| PKI-PKC | Public-key infrastructure PKC |
| CL-PKC | Certificateless PKC |
| CA | The certificate authority (CA) in the PKI-PKC |
| $({\textit{SSK}_{CA}},{\textit{SPK}_{CA}})$ | The system secret/public key pair of the CA |
| KGA | The key generating authority (KGA) in the CL-PKC |
| $({\textit{SSK}_{KGA}},{\textit{SPK}_{KGA}})$ | The system secret/public key pair of the KGA |
| BMC | The broadcast management centre (BMC) in the PKI-PKC |
| ${\textit{PKID}_{BMC}}$ | The identity of the BMC |
| $(S{K_{BMC}},P{K_{BMC}})$ | The secret/public key pair of the BMC |
| ${\textit{CRTF}_{BMC}}$ | The certificate of the BMC |
| ${\textit{PKID}_{r}}$ | The identity of a recipient in the PKI-PKC |
| $(S{K_{r}},P{K_{r}})$ | The secret/public key pair of the recipient ${\textit{PKID}_{r}}$ |
| ${\textit{CRTF}_{r}}$ | The certificate of ${\textit{PKID}_{r}}$ |
| ${\textit{CLID}_{r}}$ | The identity of a recipient in the CL-PKC |
| $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$ | The individual secret/public key pair of the recipient ${\textit{CLID}_{r}}$ |
| $({\textit{MSK}_{r}},{\textit{MPK}_{r}})$ | The member secret/public key pair of the recipient ${\textit{CLID}_{r}}$ |
| $PD$ | A plaintext data |
| $ED$ | An encrypted data |
| $\textit{SEF}/\textit{SDF}$ | The symmetric encrypting/decrypting functions |
| $edk$ | ${\textit{SEF}_{edk}}()/{\textit{SDF}_{edk}}()$, where $edk$ is an encrypting/decrypting key |
| $\textit{SDHR}$ | A set of designated heterogeneous recipients, $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})]$, $r=1,2,\dots ,n\}$ |
| $\textit{BCS}$ | A broadcast ciphertext set generated by the BMC |
3.1 Syntax (Framework)
The LRSC-AMRS scheme consists of two PKCs, namely, the PKI-PKC and the CL-PKC. The CA is responsible for managing the BMC and initial recipients in the PKI-PKC. Also, the KGA is responsible for managing new and upgraded recipients in the CL-PKC. The CA and the KGA first decide their system secret/public key pairs $({\textit{SSK}_{CA}},{\textit{SPK}_{CA}})$ and $({\textit{SSK}_{KGA}},{\textit{SPK}_{KGA}})$, respectively. The key generating procedures for the BMC and three types of recipients are described in the following and also depicted in Fig. 3.
-
• The BMC: The BMC with identity ${\textit{PKID}_{BMC}}$ decides the secret/public key pair $(S{K_{BMC}},P{K_{BMC}})$ while conveying $({\textit{PKID}_{BMC}},P{K_{BMC}})$ to the CA. The CA creates and sends back the certificate ${\textit{CRTF}_{BMC}}$.
-
• Initial recipients: An initial recipient with identity ${\textit{PKID}_{r}}$ decides the secret/public key pair $(S{K_{r}},P{K_{r}})$ while conveying $({\textit{PKID}_{r}},P{K_{r}})$ to the CA. The CA creates and sends back the certificate ${\textit{CRTF}_{r}}$.
-
• New recipients: A new recipient with identity ${\textit{CLID}_{r}}$ decides the individual secret/public key pair $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$ while conveying $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$ to the KGA. The KGA creates and sends back the member secret/public key pair $({\textit{MSK}_{r}},{\textit{MPK}_{r}})$.
-
• Upgraded recipients: If an initial recipient with identity ${\textit{PKID}_{r}}$ would like to upgrade to the CL-PKC, she/he renames ${\textit{PKID}_{r}}$ to ${\textit{CLID}_{r}}$ and $({\textit{PKID}_{r}},P{K_{r}})$ to $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$. Also, the upgraded recipient conveys $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$ to the KGA. The KGA creates and sends back the member secret/public key pair $({\textit{MSK}_{r}},{\textit{MPK}_{r}})$.
In the LRSC-AMRS scheme, when the BMC would like to convey a plaintext data ($PD$) to a set of designated heterogeneous recipients, namely, $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$, the BMC carries out the Compatible multi-signcryption (CMS) algorithm to generate a broadcast ciphertext set $\textit{BCS}=\textit{CMS}(PD,\textit{SDHR},S{K_{BMC}})$. If some ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$ lies in the set $\textit{SDHR}$, the recipient ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$ performs the Compatible unsigncryption (CUS) algorithm to get and validate $PD=\textit{CUS}(\textit{BCS},{\textit{PKID}_{BMC}},S{K_{r}})$ or $PD=\textit{CUS}(\textit{BCS},{\textit{PKID}_{BMC}},{\textit{ISK}_{r}},{\textit{MSK}_{r}})$, respectively. Figure 4 depicts the usages of the $\textit{CMS}$ and $\textit{CUS}$ algorithms in the LRSC-AMRS scheme. For resisting side-channel attacks, the key refreshing procedure (Kiltz and Pietrzak, 2010; Galindo and Vivek, 2013; Tsai et al., 2022) is used to realize leakage resilient property. For each secret/public key pair in the scheme, the secret key is separated into two fragments which must be refreshed before they are used to some computations in the proposed scheme. Also, the associated public key remains unchanged. Hence, ${\textit{SSK}_{CA}}$ and ${\textit{SSK}_{KGA}}$ are initially separated into (${\textit{SSK}_{CA,0,a}}$, ${\textit{SSK}_{CA,0,b}}$) and $({\textit{SSK}_{KGA,0,a}},{\textit{SSKK}_{GA,0,b}})$. Also, $S{K_{BMC}}$, $S{K_{r}}$, ${\textit{ISK}_{r}}$ and ${\textit{MSK}_{r}}$ are separated into $(S{K_{BMC,0,a}},S{K_{BMC,0,b}})$, $(S{K_{r,0,a}},S{K_{r,0,b}})$, $({\textit{ISK}_{r,0,a}},{\textit{ISK}_{r,0,b}})$ and $({\textit{MSK}_{r,0,a}},{\textit{MSK}_{r,0,b}})$. Finally, the syntax (framework) of the LRSC-AMRS scheme is presented in Definition 1.
Definition 1 (Syntax).
An LRSC-AMRS scheme in two heterogeneous PKCs (including the PKI-PKC and the CL-PKC) has four phases.
-
– Initialization phase: Firstly, the heterogeneously public system parameters ($\textit{HPSP}$) of both the PKI-PKC and the CL-PKC are decided. Also, the CA in the PKI-PKC and the KGA in the CL-PKC decide their own secret/public pairs as follows.
-
• PKI-PKC: By $\textit{HPSP}$, the CA decides the system secret/public key pair $({\textit{SSK}_{CA}},{\textit{SPK}_{CA}})$. Also, the CA separates ${\textit{SSK}_{CA}}$ into two fragments $({\textit{SSK}_{CA,0,a}},{\textit{SSK}_{CA,0,b}})$ by the key refreshing procedure.
-
• CL-PKC: By $\textit{HPSP}$, the KGA decides the system secret/public key pair $({\textit{SSK}_{KGA}},{\textit{SPK}_{KGA}})$. Also, the KGA separates ${\textit{SSK}_{KGA}}$ into two fragments $({\textit{SSK}_{KGA,0,a}},{\textit{SSK}_{KGA,0,b}})$ by the key refreshing procedure.
-
-
– At the end of this phase, $\textit{HPSP}$, ${\textit{SPK}_{CA}}$ and ${\textit{SPK}_{KGA}}$ are publicly announced.
-
– Key generating phase: In the PKI-PKC, the CA is responsible for managing the BMC and initial recipients. Also, in the CL-PKC, the KGA is responsible to managing the upgraded and new recipients. The associated key generating procedures are presented as follows.
-
• PKI-PKC:
-
(1) In the PKI-PKC, the BMC or an initial recipient with identity ${\textit{PKID}_{r}}$ first decides their own secret/public key pair $(S{K_{BMC}},P{K_{BMC}})$ or $(S{K_{r}},P{K_{r}})$ while separating $S{K_{BMC}}$ or $S{K_{r}}$ into $(S{K_{BMC,0,a}},S{K_{BMC,0,b}})$ or $(S{K_{r,0,a}},S{K_{r,0,b}})$, respectively. Also, they convey $({\textit{PKID}_{BMC}},P{K_{BMC}})$ or $({\textit{PKID}_{r}},P{K_{r}})$ to the CA, respectively.
-
(2) Upon receiving $({\textit{PKID}_{BMC}},P{K_{BMC}})$ or $({\textit{PKID}_{r}},P{K_{r}})$, in the i-th round of this procedure, the CA first refreshes $({\textit{SSK}_{CA,i-1,a}},{\textit{SSK}_{CA,i-1,b}})$ to get $({\textit{SSK}_{CA,i,a}},{\textit{SSK}_{CA,i,b}})$ such that ${\textit{SSK}_{CA}}={\textit{SSK}_{CA,0,a}}\cdot {\textit{SSK}_{CA,0,b}}={\textit{SSK}_{CA,1,a}}\cdot {\textit{SSK}_{CA,1,b}}=\cdots ={\textit{SSK}_{CA,i-1,a}}\cdot {\textit{SSK}_{CA,i-1,b}}={\textit{SSK}_{CA,i,a}}\cdot {\textit{SSK}_{CA,i,b}}$. The CA then uses $({\textit{SSK}_{CA,i,a}},{\textit{SSK}_{CA,i,b}})$ to create and send back the certificate ${\textit{CRTF}_{BMC}}$ or ${\textit{CRTF}_{r}}$ to the BMC or the recipient ${\textit{PKID}_{r}}$, respectively.
-
-
• CL-PKC:
-
(1) In the CL-PKC, a new recipient with identity ${\textit{CLID}_{r}}$ first decides the individual secret/public key pair $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$ while separating ${\textit{ISK}_{r}}$ into $({\textit{ISK}_{r,0,a}},{\textit{ISK}_{r,0,b}})$. Also, the recipient ${\textit{CLID}_{r}}$ conveys $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$ to the KGA.
-
(2) Upon receiving $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$, in the i-th round of this procedure, the KGA refreshes $({\textit{SSK}_{KGA,i-1,a}},{\textit{SSK}_{KGA,i-1,b}})$ to get $({\textit{SSK}_{KGA,i,a}},{\textit{SSK}_{KGA,i,b}})$ such that ${\textit{SSK}_{KGA}}={\textit{SSK}_{KGA,0,a}}\cdot {\textit{SSK}_{KGA,0,b}}={\textit{SSK}_{KGA,1,a}}\cdot {\textit{SSK}_{KGA,1,b}}=\cdots ={\textit{SSK}_{KGA,i-1,a}}\cdot {\textit{SSK}_{KGA,i-1,b}}={\textit{SSK}_{KGA,i,a}}\cdot {\textit{SSK}_{KGA,i,b}}$. The KGA then uses $({\textit{SSK}_{KGA,i,a}},{\textit{SSK}_{KGA,i,b}})$ to create and send back the member secret/public key pair $({\textit{MSK}_{r}},{\textit{MPK}_{r}})$ to the recipient ${\textit{CLID}_{r}}$.
-
(3) Upon receiving $({\textit{MSK}_{r}},{\textit{MPK}_{r}})$, the recipient ${\textit{CLID}_{r}}$ separates ${\textit{MSK}_{r}}$ into $({\textit{MSK}_{r,0,a}},{\textit{MSK}_{r,0,b}})$. Finally, the recipient ${\textit{CLID}_{r}}$ has the private key pair $({\textit{ISK}_{r}},{\textit{MSK}_{r}})$ and pubic key pair $({\textit{IPK}_{r}},{\textit{MPK}_{r}})$.
-
-
When an initial recipient with identity ${\textit{PKID}_{r}}$ in the PKI-PKC would like to upgrade to the CL-PKC, she/he renames ${\textit{PKID}_{r}}$ to ${\textit{CLID}_{r}}$ and $(S{K_{r}},P{K_{r}})$ to $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$, respectively. The upgraded recipient ${\textit{CLID}_{r}}$ then runs the steps (2) and (3) above to get the private key pair $({\textit{ISK}_{r}},{\textit{MSK}_{r}})$ and pubic key pair $({\textit{IPK}_{r}},{\textit{MPK}_{r}})$.
-
-
– Compatible multi-signcryption (CMS) phase: When the BMC would like to convey a plaintext data ($PD$) to a set of designated heterogeneous recipients, namely, $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{2.5pt}r=1,2,\dots ,n\}$ in the j-th round of this procedure, the BMC carries out the CMS algorithm to generate a broadcast ciphertext set $\textit{BCS}$ by running the following steps.
-
(1) The BMC refreshes $(S{K_{BMC,j-1,a}},S{K_{BMC,j-1,b}})$ to get $(S{K_{BMC,j,a}},S{K_{BMC,j,b}})$ such that $S{K_{BMC}}=S{K_{BMC,0,a}}\cdot S{K_{BMC,0,b}}=S{K_{BMC,1,a}}\cdot S{K_{BMC,1,b}}=\cdots =S{K_{BMC,j-1,a}}\cdot S{K_{BMC,j-1,b}}=S{K_{BMC,j,a}}\cdot S{K_{BMC,j,b}}$.
-
(2) By taking $PD$ and $\textit{SDHR}$ as input , the BMC generates $\textit{BCS}=\textit{CMS}(PD,\textit{SDHR},(S{K_{BMC,j,a}},S{K_{BMC,j,b}}))$.
-
-
– Compatible unsigncryption (CUS) phase: Upon receiving $\textit{BCS}$, if the recipients ${\textit{PKID}_{r}}$ in the PKI-PKC or the recipients ${\textit{CLID}_{r}}$ in the CL-PKC lie in the set $\textit{SDHR}$, they carry out the following procedures, respectively.
-
• PKI-PKC: For the k-th round of this procedure, the recipient ${\textit{PKID}_{r}}$ first refreshes $(S{K_{r,k-1,a}},S{K_{r,k-1,b}})$ to get $(S{K_{r,k,a}},S{K_{r,k,b}})$ such that $S{K_{r}}=S{K_{r,0,a}}\cdot S{K_{r,0,b}}=S{K_{r,1,a}}\cdot S{K_{r,1,b}}=\cdots =S{K_{r,k-1,a}}\cdot S{K_{r,k-1,b}}=S{K_{r,k,a}}\cdot S{K_{r,k,b}}$. The recipient ${\textit{PKID}_{r}}$ carries out the $\textit{CUS}$ algorithm to get and validate $PD=\textit{CUS}(\textit{BCS},{\textit{PKID}_{BMC}},(S{K_{r,k,a}},S{K_{r,k,b}}))$.
-
• CL-PKC: For the k-th round of this procedure, the recipient ${\textit{CLID}_{r}}$, respectively, refreshes $({\textit{ISK}_{r,k-1,a}},{\textit{ISK}_{r,k-1,b}})$ and $({\textit{MSK}_{r,k-1,a}},{\textit{MSK}_{r,k-1,b}})$ to get $({\textit{ISK}_{r,k,a}},{\textit{ISK}_{r,k,b}})$ and $({\textit{MSK}_{r,k,a}},{\textit{MSK}_{r,k,b}})$ such that ${\textit{ISK}_{r}}={\textit{ISK}_{r,0,a}}\cdot {\textit{ISK}_{r,0,b}}={\textit{ISK}_{r,1,a}}\cdot {\textit{ISK}_{r,1,b}}=\cdots ={\textit{ISK}_{r,k-1,a}}\cdot {\textit{ISK}_{r,k-1,b}}={\textit{ISK}_{r,k,a}}\cdot {\textit{ISK}_{r,k,b}}$ and ${\textit{MSK}_{r}}={\textit{MSK}_{r,0,a}}\cdot {\textit{MSK}_{r,0,b}}={\textit{MSK}_{r,1,a}}\cdot {\textit{MSK}_{r,1,b}}=\cdots ={\textit{MSK}_{r,k-1,a}}\cdot {\textit{MSK}_{r,k-1,b}}={\textit{MSK}_{r,k,a}}\cdot {\textit{MSK}_{r,k,b}}$. The recipient ${\textit{CLID}_{r}}$ carries out the $\textit{CUS}$ algorithm to get and validate $PD=\textit{CUS}(\textit{BCS},{\textit{PKID}_{BMC}},({\textit{ISK}_{r,k,a}},{\textit{ISK}_{r,k,b}}),({\textit{MSK}_{r,k,a}},{\textit{MSK}_{r,k,b}}))$.
-
3.2 Adversary Model
By extending the adversary models of the PKI-LR-AMRS scheme (Tsai et al., 2022) in the PKI-PKC and the CL-LR-AMRE scheme (Xie et al., 2023) in the CL-PKC, we define the adversary model of the LRSC-AMRS scheme in two heterogeneous PKCs (including the PKI-PKC and the CL-PKC) in this section.
As mentioned earlier, to measure the leakage security of secret keys due to side-channel attacks, we employ the entropy values of these secret keys to evaluate their security impact. Also, we have cited two results (i.e. Lemmas 1 and 2) about the entropies of secret keys under leakage functions. Here, we define two leakage functions f and h for the two fragments of each secret key in the proposed scheme, where $\Delta f$ and $\Delta h$ denote the associated outputs of f and h, respectively. Hence, we have five pairs of leakage functions as defined below.
-
– $\Delta {f_{CA,i}}={f_{CA,i}}({\textit{SSK}_{CA,i,a}})$ and $\Delta {h_{CA,i}}={h_{CA,i}}({\textit{SSK}_{CA,i,b}})$ for the CA’s system secret key.
-
– $\Delta {f_{KGA,i}}={f_{KGA,i}}({\textit{SSK}_{KGA,i,a}})$ and $\Delta {h_{KGA,i}}={h_{KGA,i}}({\textit{SSK}_{KGA,i,b}})$ for the KGA’s system secret key.
-
– $\Delta {f_{BMC,j}}={f_{BMC,j}}(S{K_{BMC,j,a}})$ and $\Delta {h_{BMC,j}}={h_{BMC,j}}(S{K_{BMC,j,b}})$ for the BMC’s secret key.
-
– $\Delta {f_{\textit{PKID}r,k}}={f_{PKIDr,k}}(S{K_{r,k,a}})$ and $\Delta {h_{PKIDr,k}}={h_{\textit{PKID}r,k}}(S{K_{r,k,b}})$ for the recipient ${\textit{PKID}_{r}}$’s secret key.
-
– $\Delta {f_{\textit{CLID}r,k}}={f_{\textit{CLID}r,k}}({\textit{ISK}_{r,k,a}}$, ${\textit{MSK}_{r,0,a}})$ and $\Delta {h_{\textit{CLID}r,k}}={h_{\textit{CLID}r,k}}({\textit{ISK}_{r,k,b}}$, ${\textit{MSK}_{r,0,b}})$ for the recipient ${\textit{CLID}_{r}}$’s individual and member secret keys.
In the adversary model of the proposed LRSC-AMRS scheme, there are two types of adversaries whose abilities and restrictions are presented as follows.
-
– Illegal recipient $({A_{I}})$:
-
• ${A_{I}}$ may acquire $S{K_{r}}$ of any recipient ${\textit{PKID}_{r}}$, as well as both ${\textit{ISK}_{r}}$ and ${\textit{MSK}_{r}}$ of any recipient ${\textit{CLID}_{r}}$.
-
• ${A_{I}}$ is disallowed to acquire $S{K_{r}^{\ast }}$ of the target recipient ${\textit{PKID}_{r}^{\ast }}$, but it may acquire partial information of $S{K_{r}^{\ast }}$ by two leakage functions ${f_{\textit{PKID}r,k}}$ and ${h_{\textit{PKID}r,k}}$.
-
• ${A_{I}}$ is disallowed to acquire ${\textit{MSK}_{r}^{\ast }}$ of the target recipient ${\textit{CLID}_{r}^{\ast }}$, but it may acquire partial information of ${\textit{MSK}_{r}^{\ast }}$ by two leakage functions ${f_{\textit{CLID}r,k}}$ and ${h_{\textit{CLID}r,k}}$ defined above.
-
• ${A_{I}}$ may acquire partial information of ${\textit{SSK}_{CA}}$ by two leakage functions ${f_{CA,i}}$ and ${h_{CA,i}}$.
-
• ${A_{I}}$ may acquire partial information of ${\textit{SSK}_{KGA}}$ by two leakage functions ${f_{KGA,i}}$ and ${h_{KGA,i}}$.
-
-
– Malicious KGA $({A_{\textit{II}}})$: It is assumed that ${A_{\textit{II}}}$ possesses the system secret key ${\textit{SSK}_{KGA}}$ of the KGA.
-
• ${A_{\textit{II}}}$ may acquire $S{K_{r}}$ of any recipient ${\textit{PKID}_{r}}$, and both ${\textit{ISK}_{r}}$ and ${\textit{MSK}_{r}}$ of any recipient ${\textit{CLID}_{r}}$.
-
• ${A_{\textit{II}}}$ is disallowed to acquire $S{K_{r}^{\ast }}$ of the target recipient ${\textit{PKID}_{r}^{\ast }}$, but it may acquire partial information of $S{K_{r}^{\ast }}$ by ${f_{\textit{PKID}r,k}}$ and ${h_{\textit{PKID}r,k}}$.
-
• ${A_{\textit{II}}}$ is disallowed to acquire ${\textit{ISK}_{r}^{\ast }}$ of the target recipient ${\textit{CLID}_{r}^{\ast }}$, but it may acquire partial information of ${\textit{ISK}_{r}^{\ast }}$ by ${f_{\textit{CLID}r,k}}$ and ${h_{\textit{CLID}r,k}}$.
-
In the LRSC-AMRS scheme, we employ three games, respectively, to model three security properties, namely, encryption confidentiality, recipient anonymity and sender (i.e. BMC) authentication. The encryption confidentiality is modelled by the encryption indistinguishability game under chosen-ciphertext attacks (LRSC-EIND-CCA game) while the recipient anonymity is modelled by the recipient indistinguishability game under chosen-ciphertext attacks (LRSC-RIND-CCA game). Also, the sender (i.e. the BMC) authentication is modelled by the existential unforgeability game under adaptive chosen-message attacks (LRSC-EU-ACMA game). Three games are, respectively, presented in Definitions 2, 3 and 4 below, which are played by a probabilistic polynomial-time (PPT) adversary A (${A_{I}}$ or ${A_{\textit{II}}}$) and a challenger C. It is worth mentioning that adversaries (including illegal recipient and malicious KGA) are allowed to continuously acquire partial information of secret keys for multiple rounds. By the key refreshing procedure (Kiltz and Pietrzak, 2010; Galindo and Vivek, 2013; Tsai et al., 2022), any two leaked partial information of a secret key are mutually independent.
Definition 2 (LRSC-EIND-CCA game).
The LRSC-AMRS scheme achieves the encryption confidentiality if no PPT adversary A (${A_{I}}$ or ${A_{\textit{II}}}$) with a non-negligible advantage wins the LRSC-EIND-CCA game as shown below.
-
– Setup: By running the Initialization phase of the LRSC-AMRS scheme, the challenger C sets $\textit{HPSP}$, (${\textit{SSK}_{CA}}$, ${\textit{SPK}_{CA}}$), and (${\textit{SSK}_{KGA}}$, ${\textit{SPK}_{KGA}}$). If A is type of ${A_{\textit{II}}}$, ${\textit{SSK}_{KGA}}$ is conveyed to A. Finally, $\textit{HPSP}$, ${\textit{SPK}_{CA}}$ and ${\textit{SPK}_{KGA}}$ are publicly announced.
-
– Query: A may adaptively request to C the following queries.
-
• Secret key query $({\textit{PKID}_{BMC}}/{\textit{PKID}_{r}})$: By ${\textit{PKID}_{BMC}}$ or ${\textit{PKID}_{r}}$, C returns ($S{K_{BMC}}$, $P{K_{BMC}}$) or ($S{K_{r}}$, $P{K_{r}}$).
-
• Certificate query ((${\textit{PKID}_{BMC}}$, $P{K_{BMC}}$)/(${\textit{PKID}_{r}}$, $P{K_{r}}$)): For the i-th request of this query, C refreshes ($S{S_{KCA,i-1,a}}$, $S{S_{KCA,i-1,b}}$) to get ($S{S_{KCA,i,a}}$, $S{S_{KCA,i,b}}$). By (${\textit{PKID}_{BMC}}$, $P{K_{BMC}}$) or (${\textit{PKID}_{r}}$, $P{K_{r}}$), C uses ($S{S_{KCA,i,a}}$, ${\textit{SSK}_{CA,i,b}}$) to create and send back ${\textit{CRTF}_{BMC}}$ or ${\textit{CRTF}_{r}}$ to the BMC or the recipient ${\textit{PKID}_{r}}$, respectively.
-
• Certificate leakage query (i, ${f_{CA,i}}$, ${h_{CA,i}}$): For the i-th Certificate query, A may request this leakage query only once. C returns $\Delta {f_{CA,i}}={f_{CA,i}}({\textit{SSK}_{CA,i,a}})$ and $\Delta {h_{CA,i}}={h_{CA,i}}({\textit{SSK}_{CA,i,b}})$.
-
• Individual secret key query (${\textit{CLID}_{r}}$): By ${\textit{CLID}_{r}}$, C returns (${\textit{ISK}_{r}}$, ${\textit{IPK}_{r}}$) if the Public key replacement query (${\textit{CLID}_{r}}$, ($IP{K^{\prime }_{r}}$, $MP{K^{\prime }_{r}}$)) is never requested. Otherwise, C returns “failure”.
-
• Member secret key query (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$): For the i-th request of this query, C refreshes (${\textit{SSK}_{KGA,i-1,a}}$, ${\textit{SSK}_{KGA,i-1,b}}$) to get (${\textit{SSK}_{KGA,i,a}}$, ${\textit{SSK}_{KGA,i,b}}$). By (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$), C uses (${\textit{SSK}_{KGA,i,a}}$, ${\textit{SSK}_{KGA,i,b}}$) to create and send back (${\textit{MSK}_{r}}$, ${\textit{MPK}_{r}}$).
-
• Member secret key leakage query (i, ${f_{KGA,i}}$, ${h_{KGA,i}}$): For the i-th Member secret key query, A may request this leakage query only once. C returns $\Delta {f_{KGA,i}}={f_{KGA,i}}({\textit{SSK}_{KGA,i,a}})$ and $\Delta {h_{KGA,i}}={h_{KGA,i}}({\textit{SSK}_{KGA,i,b}})$.
-
• Public key replacement query (${\textit{CLID}_{r}}$, ($IP{K^{\prime }_{r}}$, $MP{K^{\prime }_{r}}$)): C records this replacement.
-
• Compatible multi-signcryption (CMS) query ($PD$, $\textit{SDHR}$, ${\textit{PKID}_{BMC}}$): For the j-th request of this query, C refreshes ($S{K_{BMC,j-1,a}}$, $S{K_{BMC,j-1,b}}$) to get ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$). By ($PD$, $\textit{SDHR}$), C uses ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$) to create and send back $\textit{BCS}=\textit{CMS}(PD$, $\textit{SDHR}$, ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$)).
-
• Compatible multi-signcryption (CMS) leakage query (j, ${f_{BMC,j}}$, ${h_{BMC,j}}$): For the j-th Compatible multi-signcryption (CMS) query, A may request this leakage query only once. C returns $\Delta {f_{BMC,j}}={f_{BMC,j}}(S{K_{BMC,j,a}})$ and $\Delta {h_{BMC,j}}={h_{BMC,j}}(S{K_{BMC,j,b}})$.
-
• Compatible unsigncryption (CUS) query (${\textit{PKID}_{r}}/{\textit{CLID}_{r}}$, $\textit{BCS}$): For the k-th request of this query with ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$, C runs the following associated procedures.
-
(1) For ${\textit{PKID}_{r}}$, C refreshes $(S{K_{r,k-1,a}},S{K_{r,k-1,b}})$ to get $(S{K_{r,k,a}},S{K_{r,k,b}})$. C returns $PD=\textit{CUS}(\textit{BCS},{\textit{PKID}_{BMC}},(S{K_{r,k,a}},S{K_{r,k,b}}))$.
-
(2) For ${\textit{CLID}_{r}}$, C refreshes $({\textit{ISK}_{r,k-1,a}},{\textit{ISK}_{r,k-1,b}})$ and $({\textit{MSK}_{r,k-1,a}},{\textit{MSK}_{r,k-1,b}})$, respectively, to get $({\textit{ISK}_{r,k,a}},{\textit{ISK}_{r,k,b}})$ and (${\textit{MSK}_{r,k,a}}$, ${\textit{MSK}_{r,k,b}}$). C returns $PD=\textit{CUS}(\textit{BCS}$, ${\textit{PKID}_{BMC}}$, (${\textit{ISK}_{r,k,a}}$, ${\textit{ISK}_{r,k,b}}$), (${\textit{MSK}_{r,k,a}}$, ${\textit{MSK}_{r,k,b}}))$.
-
-
• Compatible unsigncryption (CUS) leakage query $(k,({f_{\textit{PKID}r,k}},{h_{\textit{PKID}r,k}})/({f_{\textit{CLID}r,k}},{h_{\textit{CLID}r,k}}))$: For the k-th Compatible unsigncryption (CUS) query with ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$. For ${\textit{PKID}_{r}}$, C sends back $\Delta {f_{\textit{PKID}r,k}}={f_{\textit{PKID}r,k}}(S{K_{r,k,a}})$ and $\Delta {h_{\textit{PKID}r,k}}={h_{\textit{PKID}r,k}}(S{K_{r,k,b}})$. For ${\textit{CLID}_{r}}$, C sends back $\Delta {f_{\textit{CLID}r,k}}={f_{\textit{CLID}r,k}}({\textit{ISK}_{r,k,a}}$, ${\textit{MSK}_{r,0,a}})$ and $\Delta {h_{\textit{CLID}r,k}}={h_{\textit{CLID}r,k}}({\textit{ISK}_{r,k,b}}$, ${\textit{MSK}_{r,0,b}})$.
-
-
– Challenge: A conveys a plaintext data pair ($P{D_{1}}$, $P{D_{2}}$) and $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$ to C. C selects a random value $\lambda \in \{1,2\}$ and refreshes ($S{K_{BMC,j-1,a}}$, $S{K_{BMC,j-1,b}}$) to get ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$). Finally, C generates and sends back $\textit{BCS}=\textit{CMS}(P{D_{\lambda }}$, $\textit{SDHR}$, ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$)). In addition, the following two conditions must be satisfied.
-
1. For ${A_{I}}$, it cannot request the Secret key query (${\textit{PKID}_{r}}$) or Member secret key query $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$, for $r=1,2,\dots ,n$.
-
2. For ${A_{\textit{II}}}$, it cannot request the Secret key query (${\textit{PKID}_{r}}$), Individual secret key query (${\textit{CLID}_{r}}$) or Public key replacement query (${\textit{CLID}_{r}}$, ($IP{K^{\prime }_{r}}$, $MP{K^{\prime }_{r}}$)), for $r=1,2,\dots ,n$.
-
-
– Guess: If A outputs ${\lambda ^{\prime }}\in \{1,2\}$ and ${\lambda ^{\prime }}=\lambda $, it means that A wins the LRSC-EIND-CCA game and the associated advantage is $Adv(A)=|\text{Pb}[{\lambda ^{\prime }}=\lambda ]-1/2|$.
Definition 3 (LRSC-RIND-CCA game).
The LRSC-AMRS scheme achieves the recipient anonymity if no PPT adversary A (${A_{I}}$ or ${A_{\textit{II}}}$) with a non-negligible advantage wins the LRSC-RIND-CCA game as shown below.
-
– Setup and Query are the same as those of Definition 2.
-
– Challenge: A conveys a plaintext data $PD$ and $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n+1\}$ to C. C selects a random value $\lambda \in \{1,2\}$ and sets ${\textit{SDHR}^{\prime }}=\{[({\textit{PKID}_{\lambda }},P{K_{\lambda }})\| ({\textit{CLID}_{\lambda }},{\textit{IPK}_{\lambda }},{\textit{MPK}_{\lambda }})],[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=3,\dots ,n+1\}$. Finally, C refreshes ($S{K_{BMC,j-1,a}}$, $S{K_{BMC,j-1,b}}$) to get ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$), and generates and sends back $\textit{BCS}=\textit{CMS}(PD,{\textit{SDHR}^{\prime }},(S{K_{BMC,j,a}},S{K_{BMC,j,b}}))$. In addition, the following two conditions must be satisfied.
-
1. For ${A_{I}}$, it cannot request the Secret key query (${\textit{PKID}_{\lambda }}$) or Member secret key query (${\textit{CLID}_{\lambda }}$, ${\textit{IPK}_{\lambda }}$), for $\lambda =1$ and 2.
-
2. For ${A_{\textit{II}}}$, it cannot request the Secret key query $({\textit{PKID}_{\lambda }})$, Individual secret key query $({\textit{CLID}_{\lambda }})$ or Public key replacement query $({\textit{CLID}_{\lambda }},(IP{K^{\prime }_{\lambda }},MP{K^{\prime }_{\lambda }}))$, for $\lambda =1$ and 2.
-
-
– Guess: If A outputs ${\lambda ^{\prime }}\in \{1,2\}$ and ${\lambda ^{\prime }}=\lambda $, it means that A wins the LRSC-RIND-CCA game and the associated advantage is $Adv(A)=|\text{Pb}[{\lambda ^{\prime }}=\lambda ]-1/2|$.
Definition 4 (LRSC-EU-ACMA game).
The LRSC-AMRS scheme achieves the BMC authentication if no PPT adversary A (i.e. impersonating the BMC) with a non-negligible advantage wins the LRSC-EU-ACMA game as shown below.
-
– Setup and Query are the same as those of Definition 2.
-
– Forgery: A forges and sends C a broadcast ciphertext set ${\textit{BCS}^{\prime }}$ for a plaintext data $PD$ and $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$. For any recipients ${\textit{PKID}_{r}}$ and ${\textit{CLID}_{r}}$ in $\textit{SDHR}$, if they may, respectively, carry out the $\textit{CUS}$ algorithm to get and validate $PD=\textit{CUS}({\textit{BCS}^{\prime }}$, ${\textit{PKID}_{BMC}}$, $(S{K_{r,k,a}}$, $S{K_{r,k,b}}))$ or $PD=\textit{CUS}({\textit{BCS}^{\prime }}$, ${\textit{PKID}_{BMC}}$, $({\textit{ISK}_{r,k,a}}$, ${\textit{ISK}_{r,k,b}})$, $({\textit{MSK}_{r,k,a}}$, ${\textit{MSK}_{r,k,b}}))$, then A wins the LRSC-EU-ACMA game. Note that A cannot request the Secret key query $({\textit{PKID}_{BMC}})$.
4 The Proposed LRSC-AMRS Scheme
According to the syntax presented in Definition 1, the proposed LRSC-AMRS scheme in two heterogeneous PKCs (including the PKI-PKC and the CL-PKC) has four phases that are presented as follows.
Correctness:
-
– Initialization phase: By the bilinear pairing group set $\textit{BPGS}=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}}\}$ defined in previous section, the heterogeneously public system parameters ($\textit{HPSP}$) about the PKI-PKC and the CL-PKC are decided as $\textit{HPSP}=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}},A,B,SEF/SDF,S{H_{0}},S{H_{1}},S{H_{2}},S{H_{3}},S{H_{4}},S{H_{5}}\}$, where A, $B\in G$, $SEF/SDF$ are symmetric encrypting/decrypting functions, and $S{H_{0}}:{\{0,1\}^{\ast }}\times G\times G\to {\{0,1\}^{l}}$, $S{H_{1}}:G\to {\{0,1\}^{l}}$, $S{H_{2}}:G\times G\to {\{0,1\}^{l}}$, $S{H_{3}}$, $S{H_{4}}:{\{0,1\}^{l}}\to {\{0,1\}^{l}}$ and $S{H_{5}}:G\times {\{0,1\}^{\ast }}\to {\{0,1\}^{l}}$ are six secure hash functions. Also, the CA in the PKI-PKC and the KGA in the CL-PKC decide their own secret/public pairs as follows.
-
• PKI-PKC: By $\textit{HPSP}$, the CA selects two random values s, ${t_{0}}\in {Z_{p}^{\ast }}$, and decides the system secret/public key pair (${\textit{SSK}_{CA}}$, ${\textit{SPK}_{CA}}$), where ${\textit{SSK}_{CA}}=s\cdot Q$ and ${\textit{SPK}_{CA}}=\hat{e}(Q,s\cdot Q)$. Also, the CA uses the key refreshing procedure to separate ${\textit{SSK}_{CA}}$ into a pair of two fragments $({\textit{SSK}_{CA,0,a}},{\textit{SSK}_{CA,0,b}})$, where ${\textit{SSK}_{CA,0,a}}={t_{0}}\cdot Q$ and ${\textit{SSK}_{CA,0,b}}={\textit{SSK}_{CA}}-{t_{0}}\cdot Q$.
-
• CL-PKC: By $\textit{HPSP}$, the KGA selects two random values $u,{v_{0}}\in {Z_{p}^{\ast }}$, and decides the system secret/public key pair (${\textit{SSK}_{KGA}}$, ${\textit{SPK}_{KGA}}$), where ${\textit{SSK}_{KGA}}=u\cdot Q$ and ${\textit{SPK}_{KGA}}=\hat{e}(Q$, $u\cdot Q)$. Also, the KGA uses the key refreshing procedure to separate ${\textit{SSK}_{KGA}}$ into a pair of two fragments $({\textit{SSK}_{KGA,0,a}},{\textit{SSK}_{KGA,0,b}})$ , where ${\textit{SSK}_{KGA,0,a}}={v_{0}}\cdot Q$ and ${\textit{SSK}_{KGA,0,b}}={\textit{SSK}_{KGA}}-{v_{0}}\cdot Q$.
-
-
– At the end of this phase, $\textit{HPSP}$, ${\textit{SPK}_{CA}}$ and ${\textit{SPK}_{KGA}}$ are publicly announced.
-
– Key generating phase: In the PKI-PKC, the CA is responsible for managing the BMC and initial recipients. Also, in the CL-PKC, the KGA is responsible for managing upgraded and new recipients. The associated key generating procedures are presented as follows.
-
• PKI-PKC:
-
(1) In the PKI-PKC, the BMC selects two random values w, ${x_{0}}\in {Z_{p}^{\ast }}$, and decides her/his own secret/public key pair ($S{K_{BMC}}$, $P{K_{BMC}}$) while separating $S{K_{BMC}}$ into ($S{K_{BMC,0,a}}$, $S{K_{BMC,0,b}}$), where $S{K_{BMC}}=w\cdot Q$, $P{K_{BMC}}=\hat{e}(Q$, $w\cdot Q)$, $S{K_{BMC,0,a}}={x_{0}}\cdot Q$ and $S{K_{BMC,0,b}}=S{K_{BMC}}-{x_{0}}\cdot Q$. Also, for an initial recipient with identity ${\textit{PKID}_{r}}$, she/he selects two random values y, ${z_{0}}\in {Z_{p}^{\ast }}$, and decides her/his own secret/public key pair ($S{K_{r}}$, $P{K_{r}}$) while separating $S{K_{r}}$ into ($S{K_{r,0,a}}$, $S{K_{r,0,b}}$), where $S{K_{r}}=y\cdot Q$, $P{K_{r}}=\hat{e}(Q$, $y\cdot Q)$, $S{K_{r,0,a}}={z_{0}}\cdot Q$ and $S{K_{r,0,b}}=S{K_{r}}-{z_{0}}\cdot Q$. Also, they convey (${\textit{PKID}_{BMC}}$, $P{K_{BMC}}$) or (${\textit{PKID}_{r}}$, $P{K_{r}}$) to the CA, respectively.
-
(2) Upon receiving (${\textit{PKID}_{BMC}}$, $P{K_{BMC}}$) or (${\textit{PKID}_{r}}$, $P{K_{r}}$), the CA selects a random value ${t_{i}}\in {Z_{p}^{\ast }}$, and refreshes (${\textit{SSK}_{CA,i-1,a}}$, ${\textit{SSK}_{CA,i-1,b}}$) to get (${\textit{SSK}_{CA,i,a}}$, ${\textit{SSK}_{CA,i,b}}$), where ${\textit{SSK}_{CA,i,a}}={\textit{SSK}_{CA,i-1,a}}+{t_{i}}\cdot Q$ and ${\textit{SSK}_{CA,i,b}}={\textit{SSK}_{CA,i-1,b}}-{t_{i}}\cdot Q$. By a leakage-resilient signature scheme (Tsai et al., 2022), the CA then uses (${\textit{SSK}_{CA,i,a}}$, ${\textit{SSK}_{CA,i,b}}$) to create and send back the certificate ${\textit{CRTF}_{BMC}}$ or ${\textit{CRTF}_{r}}$ to the BMC or the recipient ${\textit{PKID}_{r}}$, respectively.
-
-
• CL-PKC:
-
(1) In the CL-PKC, a new recipient with identity ${\textit{CLID}_{r}}$ selects two random values α, ${\beta _{0}}\in {Z_{p}^{\ast }}$, and decides the individual secret/public key pair $({\textit{ISK}_{r}},{\textit{IPK}_{r}})$ while separating ${\textit{ISK}_{r}}$ into (${\textit{ISK}_{r,0,a}}$, ${\textit{ISK}_{r,0,b}}$), where ${\textit{ISK}_{r}}=\alpha \cdot Q$, ${\textit{IPK}_{r}}=\hat{e}(Q$, $\alpha \cdot Q)$, ${\textit{ISK}_{r,0,a}}={\beta _{0}}\cdot Q$ and ${\textit{ISK}_{r,0,b}}={\textit{ISK}_{r}}-{\beta _{0}}\cdot Q$. Also, the recipient ${\textit{CLID}_{r}}$ conveys (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$) to the KGA.
-
(2) Upon receiving $({\textit{CLID}_{r}},{\textit{IPK}_{r}})$, the KGA selects a random value ${v_{i}}\in {Z_{p}^{\ast }}$, and refreshes (${\textit{SSK}_{KGA,i-1,a}}$, ${\textit{SSK}_{KGA,i-1,b}}$) to get $({\textit{SSK}_{KGA,i,a}},{\textit{SSK}_{KGA,i,b}})$, where ${\textit{SSK}_{KGA,i,a}}={\textit{SSK}_{KGA,i-1,a}}+{v_{i}}\cdot Q$ and ${\textit{SSK}_{KGA,i,b}}={\textit{SSK}_{KGA,i-1,b}}-{v_{i}}\cdot Q$. The KGA uses (${\textit{SSK}_{KGA,i,a}}$, ${\textit{SSK}_{KGA,i,b}}$) to create and send back the member secret/public key pair (${\textit{MSK}_{r}}$, ${\textit{MPK}_{r}}$) to the recipient ${\textit{CLID}_{r}}$ by running the following steps.
-
(a) Select a random value $\delta \in {Z_{p}^{\ast }}$.
-
(b) Compute ${\textit{MPK}_{r}}=\delta \cdot Q$ and $CLTem{p_{i}}={\textit{SSK}_{KGA,i,a}}+\delta \cdot (A+\theta \cdot B)$, where $\theta =S{H_{0}}({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})$.
-
(c) Compute ${\textit{MSK}_{r}}=CLTem{p_{i}}+{\textit{SSK}_{KGA,i,b}}$.
-
-
(3) Upon receiving (${\textit{MSK}_{r}}$, ${\textit{MPK}_{r}}$), the recipient ${\textit{CLID}_{r}}$ selects a random value ${\gamma _{0}}\in {Z_{p}^{\ast }}$, and separates ${\textit{MSK}_{r}}$ into $({\textit{MSK}_{r,0,a}},{\textit{MSK}_{r,0,b}})$, where ${\textit{MSK}_{r,0,a}}={\gamma _{0}}\cdot Q$ and ${\textit{MSK}_{r,0,b}}={\textit{MSK}_{r}}-{\gamma _{0}}\cdot Q$. Finally, the recipient ${\textit{CLID}_{r}}$ has the private key pair (${\textit{ISK}_{r}}$, ${\textit{MSK}_{r}}$) and pubic key pair (${\textit{IPK}_{r}}$, ${\textit{MPK}_{r}}$).
-
-
When an initial recipient with identity ${\textit{PKID}_{r}}$ in the PKI-PKC would like to upgrade to the CL-PKC, she/he renames ${\textit{PKID}_{r}}$ to ${\textit{CLID}_{r}}$ and ($S{K_{r}}$, $P{K_{r}}$) to (${\textit{ISK}_{r}}$, ${\textit{IPK}_{r}}$), respectively. The upgraded recipient ${\textit{CLID}_{r}}$ then runs the steps (2) and (3) above to get the private key pair (${\textit{ISK}_{r}}$, ${\textit{MSK}_{r}}$) and pubic key pair (${\textit{IPK}_{r}}$, ${\textit{MPK}_{r}}$).
-
-
– Compatible multi-signcryption (CMS) phase: When the BMC would like to convey a plaintext data $PD$ to a set of designated heterogeneous recipients, namely, $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$, the BMC carries out the $\textit{CMS}$ algorithm to generate a broadcast ciphertext set $\textit{BCS}$ by running the following steps.
-
(1) The BMC selects a random value ${x_{j}}\in {Z_{p}^{\ast }}$, and refreshes ($S{K_{BMC,j-1,a}}$, $S{K_{BMC,j-1,b}}$) to get ($S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}$), where $S{K_{BMC,j,a}}=S{K_{BMC,j-1,a}}+{x_{j}}\cdot Q$ and $S{K_{BMC,j,b}}=S{K_{BMC,j-1,b}}-{x_{j}}\cdot Q$.
-
(2) By taking $PD$ and $\textit{SDHR}$ as input, the BMC generates $\textit{BCS}=\textit{CMS}(PD$, $\textit{SDHR}$, $(S{K_{BMC,j,a}}$, $S{K_{BMC,j,b}}))$ by running the following steps.
-
(a) Select an encrypting/decrypting key $edk\in \{0$,$1{\}^{l}}$ and generate an encrypted data $ED={\textit{SEF}_{edk}}(PD)$.
-
(b) Select a random value $m\in {Z_{p}^{\ast }}$ and compute $M=m\cdot Q$.
-
(c) For (${\textit{PKID}_{r}}$, $P{K_{r}}$) in $\textit{SDHR}$, compute $PC{K_{r}}={(P{K_{r}})^{m}}$ and a common key $C{K_{r}}=S{H_{1}}(PC{K_{r}})$.
-
(d) For (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$, ${\textit{MPK}_{r}}$) in $\textit{SDHR}$, compute ${\textit{CCK}_{r,0}}={({\textit{IPK}_{r}})^{m}}$, ${\textit{CCK}_{r,1}}=({\textit{SPK}_{KGA}}\cdot \hat{e}({\textit{MPK}_{r}}$, $A+\theta \cdot B){)^{m}}$ and $C{K_{r}}=S{H_{2}}({\textit{CCK}_{r,0}}$, ${\textit{CCK}_{r,1}})$, where $\theta =S{H_{0}}({\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$, ${\textit{MPK}_{r}})$.
-
(e) According to Steps (c) and (d) above, generate ${C_{r}}=S{H_{3}}(C{K_{r}})\| (S{H_{4}}(C{K_{r}})\oplus edk)$, for $r=1,2,\dots ,n$.
-
(f) Compute $\textit{STemp}=S{K_{BMC,j,a}}+m\cdot (A+\rho \cdot B)$, where $\rho =S{H_{5}}(M,{C_{1}},{C_{2}},\dots ,{C_{n}},PD,ED)$.
-
(g) Generate a signature $\sigma =\textit{STemp}+S{K_{BMC,j,b}}$.
-
(h) Set the broadcast ciphertext set $\textit{BCS}=\langle ({C_{1}},{C_{2}},\dots ,{C_{n}}),M,ED,\sigma \rangle $.
-
-
-
– Compatible unsigncryption (CUS) phase: Upon receiving $\textit{BCS}=\langle ({C_{1}},{C_{2}},\dots ,{C_{n}}),M,ED,\sigma \rangle $, if the recipient ${\textit{PKID}_{r}}$ in the PKI-PKC or the recipient ${\textit{CLID}_{r}}$ in the CL-PKC lie in the set $\textit{SDHR}$, they carry out the following procedures.
-
(1) The recipients ${\textit{PKID}_{r}}$ and ${\textit{CLID}_{r}}$ run the associated computations, respectively.
-
• PKI-PKC: The recipient ${\textit{PKID}_{r}}$ selects a random value ${z_{k}}\in {Z_{p}^{\ast }}$, and refreshes ($S{K_{r,k-1,a}}$, $S{K_{r,k-1,b}}$) to get ($S{K_{r,k,a}}$, $S{K_{r,k,b}}$), where $S{K_{r,k,a}}=S{K_{r,k-1,a}}+{z_{k}}\cdot Q$ and $S{K_{r,k,b}}=S{K_{r,k-1,b}}-{z_{k}}\cdot Q$. The recipient ${\textit{PKID}_{r}}$ computes $P{T_{1}}=\hat{e}(M$, $S{K_{r,k,a}})$, $PC{K_{r}}=P{T_{1}}\cdot \hat{e}(M$, $S{K_{r,k,b}})$ and $C{K_{r}}=S{H_{1}}(PC{K_{r}})$.
-
• CL-PKC: The recipient ${\textit{CLID}_{r}}$ selects two random values ${\beta _{k}}$, ${\gamma _{k}}\in {Z_{p}^{\ast }}$, and respectively refreshes (${\textit{ISK}_{r,k-1,a}}$, ${\textit{ISK}_{r,k-1,b}}$) and (${\textit{MSK}_{r,k-1,a}}$, ${\textit{MSK}_{r,k-1,b}}$) to get (${\textit{ISK}_{r,k,a}}$, ${\textit{ISK}_{r,k,b}}$) and (${\textit{MSK}_{r,k,a}}$, ${\textit{MSK}_{r,k,b}}$), where ${\textit{ISK}_{r,k,a}}={\textit{ISK}_{r,k-1,a}}+{\beta _{k}}\cdot Q$, ${\textit{ISK}_{r,k,b}}={\textit{ISK}_{r,k-1,b}}-{\beta _{k}}\cdot Q$, ${\textit{MSK}_{r,k,a}}={\textit{MSK}_{r,k-1,a}}+{\gamma _{k}}\cdot Q$ and ${\textit{MSK}_{r,k,b}}={\textit{MSK}_{r,k-1,b}}-{\gamma _{k}}\cdot Q$. Also, the recipient ${\textit{CLID}_{r}}$ computes $C{T_{0}}=\hat{e}(M$, ${\textit{ISK}_{r,k,a}})$, ${\textit{CCK}_{r,0}}=C{T_{0}}\cdot \hat{e}(M$, ${\textit{ISK}_{r,k,b}})$, $C{T_{1}}=\hat{e}(M$, ${\textit{MSK}_{r,k,a}})$, ${\textit{CCK}_{r,1}}=C{T_{1}}\cdot \hat{e}(M$, ${\textit{MSK}_{r,k,b}})$ and $C{K_{r}}=S{H_{2}}({\textit{CCK}_{r,0}}$, ${\textit{CCK}_{r,1}})$.
-
-
(2) According to Step (1) above, the recipient ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$ obtains $C{K_{r}}$, and computes $S{H_{3}}(C{K_{r}})$ and $S{H_{4}}(C{K_{r}})$.
-
(3) Use $S{H_{3}}(C{K_{r}})$ in (2) to find ${C_{r}}$ while truncating $S{H_{3}}(C{K_{r}})$ from ${C_{r}}$.
-
(4) Get $edk$ by computing $S{H_{4}}(C{K_{r}})\oplus (S{H_{4}}(C{K_{r}})\oplus edk)$.
-
(5) Get the plaintext data $PD={\textit{SDF}_{edk}}(ED)$ and compute $\rho =S{H_{5}}(M,{C_{1}},{C_{2}},\dots ,{C_{n}},PD,ED)$.
-
(6) If $\hat{e}(Q$, $\sigma )=P{K_{BMC}}\cdot \hat{e}(M$, $A+\rho \cdot B)$ holds, output $PD$ and “True”; otherwise, output “invalid”.
-
The correctness about $\hat{e}(Q,\sigma )=P{K_{BMC}}\cdot \hat{e}(M,A+\rho \cdot B)$, $C{K_{r}}=S{H_{1}}(PC{K_{r}})$ and $C{K_{r}}=S{H_{2}}({\textit{CCK}_{r,0}}$, ${\textit{CCK}_{r,1}})$ in the LRSC-AMRS scheme is verified by the following equalities.
\[\begin{aligned}{}\hat{e}(Q,\sigma )& =\hat{e}(Q,\textit{STemp}+S{K_{BMC,j,b}})\\ {} & =\hat{e}\big(Q,S{K_{BMC,j,a}}+m\cdot (A+\rho \cdot B)+S{K_{BMC,j,b}}\big)\\ {} & =\hat{e}\big(Q,S{K_{BMC}}+m\cdot (A+\rho \cdot B)\big)\\ {} & =\hat{e}(Q,S{K_{BMC}})\cdot \hat{e}(M,A+\rho \cdot B)\\ {} & =P{K_{BMC}}\cdot \hat{e}(M,A+\rho \cdot B).\end{aligned}\]
\[\begin{aligned}{}PC{K_{r}}& =P{T_{1}}\cdot \hat{e}(M,S{K_{r,k,b}})\\ {} & =\hat{e}(M,S{K_{r,k,a}})\cdot \hat{e}(M,S{K_{r,k,b}})\\ {} & =\hat{e}(m\cdot Q,S{K_{r,k,a}}+S{K_{r,k,b}})\\ {} & =\hat{e}{(Q,S{K_{r}})^{m}}\\ {} & ={(P{K_{r}})^{m}}.\end{aligned}\]
\[\begin{aligned}{}{\textit{CCK}_{r,0}}& =C{T_{0}}\cdot \hat{e}(M,{\textit{ISK}_{r,k,b}})\\ {} & =\hat{e}(M,{\textit{ISK}_{r,k,a}})\cdot \hat{e}(M,{\textit{ISK}_{r,k,b}})\\ {} & =\hat{e}(m\cdot Q,{\textit{ISK}_{r,k,a}}+{\textit{ISK}_{r,k,b}})\\ {} & =\hat{e}{(Q,{\textit{ISK}_{r}})^{m}}\\ {} & ={({\textit{IPK}_{r}})^{m}}.\end{aligned}\]
\[\begin{aligned}{}{\textit{CCK}_{r,1}}& =C{T_{1}}\cdot \hat{e}(M,{\textit{MSK}_{r,k,b}})\\ {} & =\hat{e}(M,{\textit{MSK}_{r,k,a}})\cdot \hat{e}(M,{\textit{MSK}_{r,k,b}})\\ {} & =\hat{e}(m\cdot Q,{\textit{MSK}_{r,k,a}}+{\textit{MSK}_{r,k,b}})\\ {} & =\hat{e}{(Q,{\textit{MSK}_{r}})^{m}}\\ {} & =\hat{e}{\big(Q,{\textit{SSK}_{KGA}}+\delta \cdot (A+\theta \cdot B)\big)^{m}}\\ {} & ={\big(\hat{e}(Q,{\textit{SSK}_{KGA}})\cdot \hat{e}\big(Q,\delta \cdot (A+\theta \cdot B)\big)\big)^{m}}\\ {} & ={\big({\textit{SPK}_{KGA}}\cdot \hat{e}\big(\delta \cdot Q,(A+\theta \cdot B)\big)\big)^{m}}\\ {} & ={\big({\textit{SPK}_{KGA}}\cdot \hat{e}\big({\textit{MPK}_{r}},(A+\theta \cdot B)\big)\big)^{m}}.\end{aligned}\]
5 Security Analysis
In Definitions 2, 3 and 4, we have employed three games (i.e. LRSC-EIND-CCA, LRSC-RIND-CCA and LRSC-EU-ACMA) to model three security properties of the LRSC-AMRS scheme, namely, encryption confidentiality, recipient anonymity and sender (i.e. BMC) authentication. Under the GBPG model presented in Section 2.2, we will use three theorems, respectively, to prove the three security properties based on two security assumptions of the discrete logarithm (DL) and secure hash function (SHF).
Theorem 1.
In the GBPG model, based on the DL and SHF security assumptions, the LRSC-AMRS scheme achieves the encryption confidentiality in the LRSC-EIND-CCA game.
Proof.
The LRSC-EIND-CCA game is played by a PPT adversary A (${A_{I}}$ or ${A_{\textit{II}}}$) and a challenger C, and consists of Setup, Query, Challenge and Guess as shown below.
-
– Setup: By running the Initialization phase of the LRSC-AMRS scheme, the challenger C sets $\textit{HPSP}=\{G,{G_{e}},\hat{e},p,Q,{Q_{e}},A,B,SEF/SDF,S{H_{0}},S{H_{1}},S{H_{2}},S{H_{3}},S{H_{4}},S{H_{5}}\}$. Also, C decides (${\textit{SSK}_{CA}}$, ${\textit{SPK}_{CA}}$) of the CA and (${\textit{SSK}_{KGA}}$, ${\textit{SPK}_{KGA}}$) of the KGA. If A is type of ${A_{\textit{II}}}$, ${\textit{SSK}_{KGA}}$ is conveyed to A. Finally, $\textit{HPSP}$, ${\textit{SPK}_{CA}}$ and ${\textit{SPK}_{KGA}}$ are publicly announced. Meanwhile, C sets five lists $L{T_{0}}$, $L{T_{e}}$, $L{T_{PKI}}$, $L{T_{CL}}$ and $L{T_{\textit{CMS}}}$ as follows.
-
• $L{T_{0}}$ is set to log the i-th element of G by the pair ($\Psi {G_{i}}$, $\Omega {G_{i}}$), where $\Psi {G_{i}}$ and $\Omega {G_{i}}$ denote a multi-variate polynomial and the corresponding bit string. Initially, C adds ($\Psi Q$, $\Omega {G_{1}}$), ($\Psi A$, $\Omega {G_{2}}$), ($\Psi B$, $\Omega {G_{3}}$), ($\Psi {\textit{SSK}_{CA}}$, $\Omega {G_{4}}$) and ($\Psi {\textit{SSK}_{KGA}}$, $\Omega {G_{5}}$) to $L{T_{0}}$. Here, there is an auto-converting procedure between $\Psi {G_{i}}$ and $\Omega {G_{i}}$ for any queries in the Query.
-
• $L{T_{e}}$ is set to log the i-th element of ${G_{e}}$ by the pair ($\Psi G{E_{i}}$, $\Omega G{E_{i}}$), where $\Psi G{E_{i}}$ and $\Omega G{E_{i}}$ denote a multi-variate polynomial and the corresponding bit string. Initially, C adds ($\Psi {Q_{e}}$, $\Omega G{E_{1}}$), ($\Psi {\textit{SPK}_{CA}}$, $\Omega G{E_{2}}$) and ($\Psi {\textit{SPK}_{KGA}}$, $\Omega G{E_{3}}$) to $L{T_{e}}$. Here, there is an auto-converting procedure between $\Psi G{E_{i}}$ and $\Omega G{E_{i}}$ for any queries in the Query.
-
• $L{T_{PKI}}$ is set to log the secret/public key pairs of the BMC and a recipient with identity ${\textit{PKID}_{r}}$ in the PKI-PKC by the tuples (${\textit{PKID}_{BMC}}$, $\Psi S{K_{BMC}}$, $\Psi P{K_{BMC}}$) and (${\textit{PKID}_{r}}$, $\Psi S{K_{r}}$, $\Psi P{K_{r}}$), respectively.
-
• $L{T_{CL}}$ is set to log the individual secret/public and member secret/public key pairs of a recipient with identity ${\textit{CLID}_{r}}$ in the CL-PKC by the tuple (${\textit{CLID}_{r}}$, $\Psi {\textit{ISK}_{r}}$, $\Psi {\textit{IPK}_{r}}$, $\Psi {\textit{MSK}_{r}}$, $\Psi {\textit{MPK}_{r}}$).
-
• $L{T_{\textit{CMS}}}$ is set to log the details of Compatible multi-signcryption (CMS) algorithm by the tuple ($\Psi M$, $\Psi PC{K_{r}}$/($\Psi {\textit{CCK}_{r,0}}$, $\Psi {\textit{CCK}_{r,1}}$), $edk$) for each recipient ${\textit{PKID}_{r}}/{\textit{CLID}_{r}}$ in the set $\textit{SDHR}$.
-
-
– Query: A may adaptively request to C the following queries at most q times.
-
• $O{P_{0}}$ query ($\Omega {G_{i}}$, $\Omega {G_{j}}$, $\textit{Operator}$): By converting $\Omega {G_{i}}$ and $\Omega {G_{j}}$ in $L{T_{0}}$, C first gets the corresponding $\Psi {G_{i}}$ and $\Psi {G_{j}}$. If $\textit{Operator}=“+\text{''}$, C computes $\Psi {G_{k}}=\Psi {G_{i}}+\Psi {G_{j}}$. If $\textit{Operator}=“-\text{''}$, C computes $\Psi {G_{k}}=\Psi {G_{i}}-\Psi {G_{j}}$. Finally, C adds ($\Psi {G_{k}}$, $\Omega {G_{k}}$) in $L{T_{0}}$.
-
• $O{P_{e}}$ query ($\Omega G{E_{i}}$, $\Omega G{E_{j}}$, $\textit{Operator}$): By converting $\Omega G{E_{i}}$ and $\Omega G{E_{j}}$ in $L{T_{e}}$, C first gets the corresponding $\Psi G{E_{i}}$ and $\Psi G{E_{j}}$. If $\textit{Operator}=“\times \text{''}$, C computes $\Psi G{E_{k}}=\Psi G{E_{i}}+\Psi G{E_{j}}$. If $\textit{Operator}=“/\text{''}$, C computes $\Psi G{E_{k}}=\Psi G{E_{i}}-\Psi G{E_{j}}$. Finally, C adds ($\Psi G{E_{k}}$, $\Omega G{E_{k}}$) in $L{T_{e}}$.
-
• $O{P_{bp}}$ query ($\Omega {G_{i}}$, $\Omega {G_{j}}$): By converting $\Omega {G_{i}}$ and $\Omega {G_{j}}$ in $L{T_{0}}$, C first gets the corresponding $\Psi {G_{i}}$ and $\Psi {G_{j}}$. Also, C computes $\Psi G{E_{k}}=\Psi {G_{i}}\cdot \Psi {G_{j}}$ and adds ($\Psi {G_{k}}$, $\Omega {G_{k}}$) in $L{T_{e}}$.
-
• Secret key query $({\textit{PKID}_{BMC}}/{\textit{PKID}_{r}})$: By ${\textit{PKID}_{BMC}}/{\textit{PKID}_{r}}$, C searches $({\textit{PKID}_{BMC}}/{\textit{PKID}_{r}},\Psi S{K_{BMC}}/\Psi S{K_{r}},\Psi P{K_{BMC}}/\Psi P{K_{r}})$ in $L{T_{PKI}}$. If found, C returns ($\Omega S{K_{BMC}}/\Omega S{K_{r}}$, $\Omega P{K_{BMC}}/\Omega P{K_{r}}$) by converting $\Psi S{K_{BMC}}/\Psi S{K_{r}}$ in $L{T_{0}}$ and $\Psi P{K_{BMC}}/\Psi P{K_{r}}$ in $L{T_{e}}$. If not found, C picks a new variate $\Psi S{K_{BMC}}$ or $\Psi S{K_{r}}$ in G, and computes $\Psi P{K_{BMC}}=\Psi Q\cdot \Psi S{K_{BMC}}$ or $\Psi P{K_{r}}=\Psi Q\cdot \Psi S{K_{r}}$. Also, C adds (${\textit{PKID}_{BMC}}/{\textit{PKID}_{r}}$, $\Psi S{K_{BMC}}/\Psi S{K_{r}}$, $\Psi P{K_{BMC}}/\Psi P{K_{r}}$) in $L{T_{PKI}}$. Meanwhile, C adds ($\Psi S{K_{BMC}}/\Psi S{K_{r}}$, $\Omega S{K_{BMC}}/\Omega S{K_{r}}$) in $L{T_{0}}$ and ($\Psi P{K_{BMC}}/\Psi P{K_{r}}$, $\Omega P{K_{BMC}}/\Omega P{K_{r}}$) in $L{T_{e}}$, and returns ($\Omega S{K_{BMC}}/\Omega S{K_{r}}$, $\Omega P{K_{BMC}}/\Omega P{K_{r}}$).
-
• Certificate query $(({\textit{PKID}_{BMC}},\Omega P{K_{BMC}})/({\textit{PKID}_{r}},\Omega P{K_{r}}))$: For the i-th request of this query, C refreshes ($\Psi {\textit{SSK}_{CA,i-1,a}}$, $\Psi {\textit{SSK}_{CA,i-1,b}}$) to get ($\Psi {\textit{SSK}_{CA,i,a}}$, $\Psi {\textit{SSK}_{CA,i,b}}$). By (${\textit{PKID}_{BMC}}$, $\Omega P{K_{BMC}}$) or (${\textit{PKID}_{r}}$, $\Omega P{K_{r}}$), C uses ($\Psi {\textit{SSK}_{CA,i,a}}$, $\Psi {\textit{SSK}_{CA,i,b}}$) to create and send back ${\textit{CRTF}_{BMC}}$ or ${\textit{CRTF}_{r}}$ to the BMC or the recipient ${\textit{PKID}_{r}}$, respectively.
-
• Certificate leakage query (i, ${f_{CA,i}}$, ${h_{CA,i}}$): For the i-th Certificate query, A may request this leakage query only once. C returns $\Delta {f_{CA,i}}={f_{CA,i}}(\Psi {\textit{SSK}_{CA,i,a}})$ and $\Delta {h_{CA,i}}={h_{CA,i}}(\Psi {\textit{SSK}_{CA,i,b}})$.
-
• Individual secret key query (${\textit{CLID}_{r}}$): By ${\textit{CLID}_{r}}$, C searches (${\textit{CLID}_{r}}$, $\Psi {\textit{ISK}_{r}}$, $\Psi {\textit{IPK}_{r}}$, $\Psi {\textit{MSK}_{r}}$, $\Psi {\textit{MPK}_{r}}$) in $L{T_{CL}}$. If found, C returns ($\Omega {\textit{ISK}_{r}}$, $\Omega {\textit{IPK}_{r}}$) by converting $\Psi {\textit{ISK}_{r}}$ in $L{T_{0}}$ and $\Psi {\textit{IPK}_{r}}$ in $L{T_{e}}$. If not found, C picks a new variate $\Psi {\textit{ISK}_{r}}$ in G, and computes $\Psi {\textit{IPK}_{r}}=\Psi Q\cdot \Psi {\textit{ISK}_{r}}$. Also, C adds $({\textit{CLID}_{r}},\Psi {\textit{ISK}_{r}},\Psi {\textit{IPK}_{r}},-,-)$ in $L{T_{CL}}$. Meanwhile, C adds ($\Psi {\textit{ISK}_{r}}$, $\Omega {\textit{ISK}_{r}}$) in $L{T_{0}}$ and ($\Psi {\textit{IPK}_{r}}$, $\Omega {\textit{IPK}_{r}}$) in $L{T_{e}}$, and returns ($\Omega {\textit{ISK}_{r}}$, $\Omega {\textit{IPK}_{r}}$).
-
• Member secret key query (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$): By ${\textit{CLID}_{r}}$, C searches (${\textit{CLID}_{r}}$, $\Psi {\textit{ISK}_{r}}$, $\Psi {\textit{IPK}_{r}}$, $\Psi {\textit{MSK}_{r}}$, $\Psi {\textit{MPK}_{r}}$) in $L{T_{CL}}$. If found, C returns ($\Omega {\textit{MSK}_{r}}$, $\Omega {\textit{MPK}_{r}}$) by converting $\Psi {\textit{MSK}_{r}}$ in $L{T_{0}}$ and $\Psi {\textit{MPK}_{r}}$ in $L{T_{e}}$. If not found and for the i-th request of this query, C first refreshes ($\Psi {\textit{SSK}_{KGA,i-1,a}}$, $\Psi {\textit{SSK}_{KGA,i-1,b}}$) to get ($\Psi {\textit{SSK}_{KGA,i,a}}$, $\Psi {\textit{SSK}_{KGA,i,b}}$). C then picks two new variates $\Psi {\textit{MPK}_{r}}$ and $\Psi \theta $ in G, and computes $\Psi {\textit{MSK}_{r}}=\Psi {\textit{SSK}_{KGA}}+\Psi {\textit{MPK}_{r}}\cdot (\Psi A+\Psi \theta \cdot \Psi B$). Also, C adds (${\textit{CLID}_{r}}$, $\Psi {\textit{ISK}_{r}}$, $\Psi {\textit{IPK}_{r}}$, $\Psi {\textit{MSK}_{r}}$, $\Psi {\textit{MPK}_{r}}$) in $L{T_{CL}}$. Meanwhile, C adds ($\Psi {\textit{MPK}_{r}}$, $\Omega {\textit{MPK}_{r}}$), ($\Psi \theta $, $\Omega \theta $) and ($\Psi {\textit{MSK}_{r}}$, $\Omega {\textit{MSK}_{r}}$) in $L{T_{0}}$, and returns ($\Omega {\textit{MSK}_{r}}$, $\Omega {\textit{MPK}_{r}}$).
-
• Member secret key leakage query (i, ${f_{KGA,i}}$, ${h_{KGA,i}}$): For the i-th Member secret key query, A may request this leakage query only once. C returns $\Delta {f_{KGA,i}}={f_{KGA,i}}(\Psi {\textit{SSK}_{KGA,i,a}})$ and $\Delta {h_{KGA,i}}={h_{KGA,i}}(\Psi {\textit{SSK}_{KGA,i,b}})$.
-
• Public key replacement query (${\textit{CLID}_{r}}$, ($\Omega IP{K^{\prime }_{r}}$, $\Omega MP{K^{\prime }_{r}}$)): By converting $\Omega IP{K^{\prime }_{r}}$ and $\Omega MP{K^{\prime }_{r}}$ in $L{T_{0}}$, C first gets the corresponding $\Psi IP{K^{\prime }_{r}}$ and $\Psi MP{K^{\prime }_{r}}$. C modifies (${\textit{CLID}_{r}}$, −, $\Psi IP{K^{\prime }_{r}}$, −, $\Psi MP{K^{\prime }_{r}}$) in $L{T_{CL}}$.
-
• Compatible multi-signcryption (CMS) query ($PD$, $\textit{SDHR}$, ${\textit{PKID}_{BMC}}$): For the j-th request of this query, C refreshes ($\Psi S{K_{BMC,j-1,a}}$, $\Psi S{K_{BMC,j-1,b}}$) to get ($\Psi S{K_{BMC,j,a}}$, $\Psi S{K_{BMC,j,b}}$). By ($PD$, $\textit{SDHR}$), C uses ($\Psi S{K_{BMC,j,a}}$, $\Psi S{K_{BMC,j,b}}$) to create and send back $\textit{BCS}=\textit{CMS}(PD$, $\textit{SDHR}$, $(\Psi S{K_{BMC,j,a}}$, $\Psi S{K_{BMC,j,b}}))$ as follows.
-
(a) Select an encrypting/decrypting key $edk\in {\{0,1\}^{l}}$ and generate an encrypted data $ED={\textit{SEF}_{edk}}(PD)$.
-
(b) Pick two new variates $\Psi M$ and $\Psi \theta $ in G.
-
(c) For (${\textit{PKID}_{r}}$, $P{K_{r}}$) in $\textit{SDHR}$, compute $\Psi PC{K_{r}}=\Psi M\cdot \Psi P{K_{r}}$ and $C{K_{r}}=S{H_{1}}(\Omega PC{K_{r}})$, where $\Omega PC{K_{r}}$ is the associated bit string of $\Psi PC{K_{r}}$.
-
(d) For (${\textit{CLID}_{r}}$, ${\textit{IPK}_{r}}$, ${\textit{MPK}_{r}}$) in $\textit{SDHR}$, compute $\Psi {\textit{CCK}_{r,0}}=\Psi M\cdot \Psi {\textit{IPK}_{r}}$, $\Psi {\textit{CCK}_{r,1}}=\Psi M\cdot (\Psi {\textit{SPK}_{KGA}}+\Psi {\textit{MPK}_{r}}\cdot (\Psi A+\Psi \theta \cdot \Psi B))$ and $C{K_{r}}=S{H_{2}}(\Omega {\textit{CCK}_{r,0}}$, $\Omega {\textit{CCK}_{r,1}})$, where $\Omega {\textit{CCK}_{r,0}}$ and $\Omega {\textit{CCK}_{r,1}}$ are the associated bit strings of $\Psi {\textit{CCK}_{r,0}}$ and $\Psi {\textit{CCK}_{r,1}}$.
-
(e) According to Steps (c) and (d) above, generate ${C_{r}}=S{H_{3}}(C{K_{r}})\| (S{H_{4}}(C{K_{r}})\oplus edk)$, for $r=1,2,\dots ,n$.
-
(f) Pick a new variate $\Psi \rho $ in G, and compute $\Psi \sigma =\Psi S{K_{BMC}}+\Psi M\cdot (\Psi A+\Psi \rho \cdot \Psi B)$.
-
(g) Set $\textit{BCS}=\langle ({C_{1}},{C_{2}},\dots ,{C_{n}})$, $\Omega M$, $ED$, $\Omega \sigma \rangle $, where $\Omega M$ and $\Omega \sigma $ are the associated bit strings of $\Psi M$ and $\Psi \sigma $.
-
-
• Compatible multi-signcryption (CMS) leakage query (j, ${f_{BMC,j}}$, ${h_{BMC,j}}$): For the j-th Compatible multi-signcryption (CMS) query, A may request this leakage query only once. C returns $\Delta {f_{BMC,j}}={f_{BMC,j}}(\Psi S{K_{BMC,j,a}})$ and $\Delta {h_{BMC,j}}={h_{BMC,j}}(\Psi S{K_{BMC,j,b}})$.
-
• Compatible unsigncryption (CUS) query (${\textit{PKID}_{r}}/{\textit{CLID}_{r}}$, $\textit{BCS}$): For the k-th request of this query with ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$, C runs the following associated procedures.
-
(1) For ${\textit{PKID}_{r}}$, C refreshes ($\Psi S{K_{r,k-1,a}}$, $\Psi S{K_{r,k-1,b}}$) to get ($\Psi S{K_{r,k,a}}$, $\Psi S{K_{r,k,b}}$). C then computes $\Psi PC{K_{r}}=\Psi M\cdot (\Psi Q\cdot \Psi S{K_{r}})$ and uses ($\Psi M$, $\Psi PC{K_{r}}$) to find ($\Psi M$, $\Psi PC{K_{r}}$, $edk$) in $L{T_{\textit{CMS}}}$ to get $PD={\textit{SDF}_{edk}}(ED)$. If $\Psi Q\cdot \Psi \sigma =\Psi P{K_{BMC}}+\Psi Q\cdot (\Psi M\cdot (\Psi A+\Psi \rho \cdot \Psi B))$ holds, output $PD$ and “True”; otherwise, output “invalid”.
-
(2) For ${\textit{CLID}_{r}}$, C respectively refreshes ($\Psi {\textit{ISK}_{r,k-1,a}}$, $\Psi {\textit{ISK}_{r,k-1,b}}$) and ($\Psi {\textit{MSK}_{r,k-1,a}}$, $\Psi {\textit{MSK}_{r,k-1,b}}$) to get ($\Psi {\textit{ISK}_{r,k,a}}$, $\Psi {\textit{ISK}_{r,k,b}}$) and ($\Psi {\textit{MSK}_{r,k,a}}$, $\Psi {\textit{MSK}_{r,k,b}}$). C then computes $\Psi {\textit{CCK}_{r,0}}=\Psi M\cdot (\Psi Q\cdot \Psi {\textit{ISK}_{r}})$, $\Psi {\textit{CCK}_{r,1}}=\Psi M\cdot (\Psi Q\cdot \Psi {\textit{SSK}_{KGA}}+\Psi Q\cdot \Psi {\textit{MSK}_{r}}\cdot (\Psi A+\Psi \theta +\Psi B))$ and uses ($\Psi M$, $\Psi {\textit{CCK}_{r,0}}$, $\Psi {\textit{CCK}_{r,1}}$) to find ($\Psi M$, ($\Psi {\textit{CCK}_{r,0}}$, $\Psi {\textit{CCK}_{r,1}}$), $edk$) in $L{T_{\textit{CMS}}}$ to get $PD={\textit{SDF}_{edk}}(ED)$. If $\Psi Q\cdot \Psi \sigma =\Psi P{K_{BMC}}+\Psi Q\cdot (\Psi M\cdot (\Psi A+\Psi \rho \cdot \Psi B))$ holds, output $PD$ and “True”; otherwise, output “invalid”.
-
-
• Compatible unsigncryption (CUS) leakage query $(k,({f_{\textit{PKID}r,k}},{h_{\textit{PKID}r,k}})/({f_{\textit{CLID}r,k}},{h_{\textit{CLID}r,k}}))$: For the k-th Compatible unsigncryption (CUS) query with ${\textit{PKID}_{r}}$ or ${\textit{CLID}_{r}}$, C runs the associated procedures, respectively. For ${\textit{PKID}_{r}}$, C sends back $\Delta {f_{\textit{PKID}r,k}}={f_{\textit{PKID}r,k}}(\Psi S{K_{r,k,a}})$ and $\Delta {h_{\textit{PKID}r,k}}={h_{\textit{PKID}r,k}}(\Psi S{K_{r,k,b}})$. For ${\textit{CLID}_{r}}$, C sends back $\Delta {f_{\textit{CLID}r,k}}={f_{\textit{CLID}r,k}}(\Psi {\textit{ISK}_{r,k,a}}$, $\Psi {\textit{MSK}_{r,0,a}})$ and $\Delta {h_{\textit{CLID}r,k}}={h_{\textit{CLID}r,k}}(\Psi {\textit{ISK}_{r,k,b}}$, $\Psi {\textit{MSK}_{r,0,b}})$.
-
-
– Challenge: A conveys a plaintext data pair ($P{D_{1}}$, $P{D_{2}}$) and $\textit{SDHR}=\{[({\textit{PKID}_{r}}$, $P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$ to C. C selects a random value $\lambda \in \{1$, $2\}$ and refreshes ($\Psi S{K_{BMC,j-1,a}}$, $\Psi S{K_{BMC,j-1,b}}$) to get ($\Psi S{K_{BMC,j,a}}$, $\Psi S{K_{BMC,j,b}}$). Finally, C generates and sends back $\textit{BCS}=\textit{CMS}(P{D_{\lambda }}$, $\textit{SDHR}$, ${\textit{PKID}_{BMC}})$. In addition, the two conditions presented in Definition 2 must be satisfied.
-
– Guess: If A outputs ${\lambda ^{\prime }}\in \{1$, $2\}$ and ${\lambda ^{\prime }}=\lambda $, it means that A wins the LRSC-EIND-CCA game and the associated advantage is $Adv(A)=|\text{Pb}[{\lambda ^{\prime }}=\lambda ]-1/2|$.
As mentioned earlier, in the GBPG model, if adversaries can find collisions on G or ${G_{e}}$, the discrete logarithm (DL) security assumption on G or ${G_{e}}$ will be broken. For computing the collision probability, the total amount of elements and maximal polynomial degrees of $L{T_{0}}$ and $L{T_{e}}$ are counted as follows. In each query in the Query, at most 3 elements are added in $L{T_{0}}$ or $L{T_{e}}$. Since A may adaptively request to C all kinds of queries at most q times, $|L{T_{0}}|+|L{T_{e}}|\leqq 3q$. For $L{T_{0}}$, in the Compatible multi-signcryption (CMS) query, $\Psi {\textit{CCK}_{r,1}}$ has at most degree 4. Since the maximal degree of $L{T_{0}}$ is 4, the maximal degree of $L{T_{e}}$ is 8 by $\Psi G{E_{k}}=\Psi {G_{i}}\cdot \Psi {G_{j}}$ of the ${Q_{pf}}$ query.
In the following, let $Adv({A_{I-wo}})$ be the advantage of ${A_{I}}$ without requesting any leakage queries and $Adv({A_{I-wo}})=\mathrm{Pb}[{A_{I-wo}}]+|\mathrm{Pb}[{\lambda ^{\prime }}=\lambda ]-1/2|$, which are defined and computed as follows.
By the computations above, we have
-
■ $\mathrm{Pb}[{A_{I-wo}}]$: It represents the probability of finding collisions on $L{T_{0}}$ or $L{T_{e}}$ (i.e. G or ${G_{e}}$). For $L{T_{0}}$, assume that all elements ($\Psi {G_{i}}$, $\Omega {G_{i}}$) consist of c kinds of variates. Thus, c random values ${v_{t}}\in {Z_{p}^{\ast }}$ (for $t=1,2,\dots ,c$) are randomly chosen. For any two polynomials $\Psi {G_{i}}$ and $\Psi {G_{j}}$ in $L{T_{0}}$, we compute $\Psi {G_{k}}=\Psi {G_{i}}-\Psi {G_{j}}$. If $\Psi {G_{k}}({v_{1}},{v_{2}},\dots ,{v_{c}})=0$, we say that a collision in $L{T_{0}}$ is found. By Lemma 2, since the maximal degree of $L{T_{0}}$ is 4 and no partial information ($\gamma =0$) is leaked to adversaries, the probability of $\Psi {G_{k}}({v_{1}},{v_{2}},\dots ,{v_{c}})=0$ is at most $4/p$. Also, for $L{T_{0}}$, there are $\left(\genfrac{}{}{0pt}{}{|L{T_{0}}|}{2}\right)$ pairs of ($\Psi {G_{i}}$, $\Psi {G_{j}}$). Therefore, the collision probability on $L{T_{0}}$ is $\left(\genfrac{}{}{0pt}{}{|L{T_{0}}|}{2}\right)(4/p)$. By similar computation, the collision probability on $L{T_{e}}$ is $\left(\genfrac{}{}{0pt}{}{|L{T_{e}}|}{2}\right)(8/p)$. Hence, we have
-
■ $\mathrm{Pb}[{\lambda ^{\prime }}=\lambda ]$: It represents the probability of ${\lambda ^{\prime }}=\lambda $ in the Guess. Since no partial information ($\gamma =0$) is leaked to adversaries, we have $\mathrm{Pb}[{\lambda ^{\prime }}=\lambda ]\leqq 1/2$.
Let $Adv({A_{I}})$ be the advantage of the adversary ${A_{I}}$ with requesting four leakage queries (including Certificate leakage query, Member secret key leakage query, Compatible multi-signcryption leakage query and Compatible unsigncryption leakage query) in the Query. By the key refreshing procedure, any two leaked partial information of a secret key are mutually independent. Thus, ${A_{I}}$ gains at most $2\gamma $ bits of each secret key ${\textit{SSK}_{CA}}$, ${\textit{SSK}_{KGA}}$, $S{K_{BMC}}$, ${\textit{ISK}_{r}}$ or ${\textit{MSK}_{r}}$. Based on $Adv({A_{I-wo}})$, we have
\[ Adv({A_{I}})\leqq Adv({A_{I-wo}})\cdot {2^{2\gamma }}\leqq \big(128{q^{2}}/p\big)\cdot {2^{2\gamma }}=O\big(\big({q^{2}}/p\big)\cdot {2^{2\gamma }}\big).\]
By Lemma 2, $Adv({A_{I}})=O(({q^{2}}/p)\cdot {2^{2\gamma }})$ is negligible if $\gamma \lt \log p(1-\epsilon )$. For the advantage $Adv({A_{\textit{II}}})$ of the adversary ${A_{\textit{II}}}$, we have $Adv({A_{\textit{II}}})=O(({q^{2}}/p)\cdot {2^{2\gamma }})$ by similar evaluation. □Theorem 2.
In the GBPG model, based on the DL and SHF security assumptions, the LRSC-AMRS scheme achieves the recipient anonymity in the LRSC-RIND-CCA game.
Proof.
The LRSC-RIND-CCA game is played by a PPT adversary A (${A_{I}}$ or ${A_{\textit{II}}}$) and a challenger C, and consists of Setup, Query, Challenge and Guess as shown below.
-
– Setup and Query are the same as those in the proof of Theorem 1.
-
– Challenge: A conveys a plaintext data $PD$ and $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n+1\}$ to C. C selects a random value $\lambda \in \{1,2\}$ and sets ${\textit{SDHR}^{\prime }}=\{[({\textit{PKID}_{\gamma }},P{K_{\gamma }})\| ({\textit{CLID}_{\gamma }},{\textit{IPK}_{\gamma }},{\textit{MPK}_{\gamma }})],[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=3,\dots ,n+1\}$. Finally, C refreshes ($\Psi S{K_{BMC,j-1,a}}$, $\Psi S{K_{BMC,j-1,b}}$) to get ($\Psi S{K_{BMC,j,a}}$, $\Psi S{K_{BMC,j,b}}$), and generates and sends back $\textit{BCS}=\textit{CMS}(PD$, ${\textit{SDHR}^{\prime }}$, ${\textit{PKID}_{BMC}})$. In addition, the two conditions presented in Definition 3 must be satisfied.
-
– Guess: If A outputs ${\lambda ^{\prime }}\in \{1$, $2\}$ and ${\lambda ^{\prime }}=\lambda $, it means that A wins the LRSC-RIND-CCA game and the associated advantage is $Adv(A)=|\mathrm{Pb}[{\lambda ^{\prime }}=\lambda ]-1/2|$.
Theorem 3.
In the GBPG model, based on the DL and SHF security assumptions, the LRSC-AMRS scheme achieves the BMC authentication in the LRSC-EU-ACMA game.
Proof.
The LRSC-EU-ACMA game is played by a PPT adversary A (i.e. impersonating the BMC) and a challenger C, and consists of Setup, Query and Forgery as shown below.
In the following, let $Adv({A_{wo}})$ be the advantage of A without requesting any leakage queries and $Adv({A_{wo}})=\mathrm{Pb}[{A_{wo}}]+\mathrm{Pb}[\text{Valid-forging}]$, which are defined and computed as follows.
By the computations of $\mathrm{Pb}[{A_{wo}}]$ and $\mathrm{Pb}[\text{Valid-forging}]$ above, we have
-
– Setup: It is identical with the Setup phase in the proof of Theorem 1.
-
– Query: A may adaptively request to C all queries at most q times, except for the Secret key query (${\textit{PKID}_{BMC}}$) because A would like to impersonate the SMC to generate a valid broadcast ciphertext set ${\textit{BCS}^{\prime }}$.
-
– Forgery: A forges and sends C a broadcast ciphertext set ${\textit{BCS}^{\prime }}$ for a plaintext data $PD$ and $\textit{SDHR}=\{[({\textit{PKID}_{r}},P{K_{r}})\| ({\textit{CLID}_{r}},{\textit{IPK}_{r}},{\textit{MPK}_{r}})],\hspace{0.1667em}r=1,2,\dots ,n\}$. For any recipients ${\textit{PKID}_{r}}$ and ${\textit{CLID}_{r}}$ in $\textit{SDHR}$, if they may, respectively, carry out the $\textit{CUS}$ algorithm to get and validate $PD=\textit{CUS}({\textit{BCS}^{\prime }}$, ${\textit{PKID}_{BMC}}$, $(S{K_{r,k,a}}$, $S{K_{r,k,b}}))$ and $PD=\textit{CUS}({\textit{BCS}^{\prime }}$, ${\textit{PKID}_{BMC}}$, $({\textit{ISK}_{r,k,a}}$, ${\textit{ISK}_{r,k,b}})$, $({\textit{MSK}_{r,k,a}}$, ${\textit{MSK}_{r,k,b}}))$, it means that A wins the LRSC-EU-ACMA game.
-
■ $\mathrm{Pb}[{A_{wo}}]$: It represents the probability of finding collisions on $L{T_{0}}$ or $L{T_{e}}$ (i.e. G or ${G_{e}}$). By the same arguments of $\mathrm{Pb}[{A_{I-wo}}]$ in the proof of Theorem 1, we have $\mathrm{Pb}[{A_{wo}}]\leqq 128{q^{2}}/p$.
-
■ $\mathrm{Pb}[\text{Valid-forging}]$: It represents the probability of forging a valid tuple ${\textit{BCS}^{\prime }}=\langle ({C_{1}},{C_{2}},\dots ,{C_{n}}),\Omega {M^{\prime }},ED,\Omega {\sigma ^{\prime }}\rangle $ in the Forgery. C gets $\Psi {M^{\prime }}$ and $\Psi {\sigma ^{\prime }}$ by converting $\Omega {M^{\prime }}$ and $\Omega {\sigma ^{\prime }}$ in $L{T_{0}}$. Since ${\textit{BCS}^{\prime }}$ is valid, the equality $\Psi Q\cdot \Psi {\sigma ^{\prime }}=\Psi P{K_{BMC}}+\Psi Q\cdot \Psi {M^{\prime }}\cdot (\Psi A+\Psi \rho \cdot \Psi B)$ must hold. Thus, we have a multiple-variable polynomial $\Psi MP=\Psi Q\cdot \Psi {\sigma ^{\prime }}-(\Psi P{K_{BMC}}+\Psi Q\cdot \Psi {M^{\prime }}\cdot (\Psi A+\Psi \rho \cdot \Psi B))=0$. By Lemma 2, since $\Psi MP$ is an element of $L{T_{e}}$ with the maximal degree 8, we have $\mathrm{Pb}[\text{Valid-forging}]=8/p$.
Let $Adv(A)$ be the advantage of A with requesting two kinds of leakage queries (including Certificate leakage query and Compatible multi-signcryption leakage query) in the Query. By the key refreshing procedure, any two leaked partial information of a secret key are mutually independent. Thus, A gains at most $2\gamma $ bits of each secret key ${\textit{SSK}_{CA}}$ or $S{K_{BMC}}$. Based on $Adv({A_{wo}})$, we have
\[ Adv(A)\leqq Adv({A_{wo}})\cdot {2^{2\gamma }}=O\big(\big({q^{2}}/p\big)\cdot {2^{2\gamma }}\big).\]
By Lemma 2, $Adv(A)=O(({q^{2}}/p)\cdot {2^{2\gamma }})$ is negligible if $\gamma \lt \log p(1-\epsilon )$. □6 Comparisons and Performance Analysis
Table 2 below lists the comparisons between our LRSC-AMRS scheme and some related AMRS schemes (Wang et al., 2016; Tsai et al., 2022; Wang et al., 2012; Pang et al., 2015, 2018; Li et al., 2022) in terms of PKC, group, time complexity of multi-signcryption, time complexity of unsigncryption, leakage resilience and heterogeneous recipients. Two PKI-AMRS schemes in Wang et al. (2016), Tsai et al. (2022) and two ID-AMRS schemes in Wang et al. (2012), Pang et al. (2015) are implemented under the BP group. Two CL-AMRS schemes in Pang et al. (2018), Li et al. (2022) are constructed under the elliptic curve (EC) group and enjoy better performance than the constructions under the bilinear pairing (BP) group. It is worth mentioning that Tsai et al.’s scheme (2022) is the first AMRS with leakage resilience property. The point is that our scheme is not only suitable for multiple recipients under two heterogeneous PKCs (i.e. the PKI-PKC and the CL-PKC), but also possesses leakage resilience property.
Additionally, five schemes (Wang et al., 2016, 2012; Pang et al., 2015, 2018; Li et al., 2022) employ the Lagrange interpolation polynomial technique to achieve anonymity between these recipients. In these schemes, a sender constructs and broadcasts an interpolation polynomial $IP(x)={\textstyle\prod _{r=1}^{n}}(x-C{K_{r}})+edk(\mathrm{mod}\hspace{0.1667em}p)={c_{0}}+{c_{1}}x+\cdots +{c_{n-1}}{x^{n-1}}+{x^{n}}$, where n denotes the number of recipients and $edk$ is the encrypting/decrypting key. By the interpolation polynomial $IP(x)$, each authorized recipient $I{D_{r}}$ uses her/his secret key to get $edk=IP(C{K_{r}})$ and decrypts the plaintext data $PD$. Therefore, the required time complexities of multi-signcryption and unsigncryption are $O({n^{2}})$ and $O(n)$, respectively. By the Compatible multi-signcryption (CMS) and Compatible unsigncryption (CUS) algorithms presented in Section 4, the required time complexities are $O(n)$ and $O(1)$, respectively.
Table 2
Comparisons between our LRSC-AMRS scheme and some previously related AMRS schemes.
| Schemes | PKC | Group | Time complexity of multi-signcryption | Time complexity of unsigncryption | Leakage resilience | Heterogeneous recipients |
| Wang et al.’s | ||||||
| scheme (2016) | PKI-PKC | BP | $O({n^{2}})$ | $O(n)$ | No | No |
| Tsai et al.’s | ||||||
| scheme (2022) | PKI-PKC | BP | $\boldsymbol{O}\boldsymbol{(}\boldsymbol{n}\boldsymbol{)}$ | $\boldsymbol{O}\boldsymbol{(}\mathbf{1}\boldsymbol{)}$ | Yes | No |
| Wang et al.’s | ||||||
| scheme (2012) | ID-PKC | BP | $O({n^{2}})$ | $O(n)$ | No | No |
| Pang et al.’s | ||||||
| scheme (2015) | ID-PKC | BP | $O({n^{2}})$ | $O(n)$ | No | No |
| Pang et al.’s | ||||||
| scheme (2018) | CL-PKC | EC | $O({n^{2}})$ | $O(n)$ | No | No |
| Li et al.’s | ||||||
| scheme (2022) | CL-PKC | EC | $O({n^{2}})$ | $O(n)$ | No | No |
| Our scheme | PKI-PKC CL-PKC | BP | $\boldsymbol{O}\boldsymbol{(}\boldsymbol{n}\boldsymbol{)}$ | $\boldsymbol{O}\boldsymbol{(}\mathbf{1}\boldsymbol{)}$ | Yes | Yes |
Table 3
Computation notations and time ($ms$) of two time-consuming operations on a PC and a mobile device.
| Notation | Meaning | Computation time on a PC | Computation time on a mobile device |
| ${T_{bp}}$ | Bilinear pairing mapping | $\approx 20.1$ | $\approx 96.2$ |
| ${T_{me}}$ | Multiplication in G or exponentiation in ${G_{e}}$ | $\approx 6.4$ | $\approx 30.7$ |
Table 4
The required computation costs and time ($ms$) for the CMS and the CUS phases.
| Phase | Computational costs | $n=10$ | $n=50$ | $n=100$ |
| The CMS phase performed on a PC | $n{T_{bp}}+(3n+4){T_{me}}$ | $\approx 418.6$ | $\approx 1990.6$ | $\approx 3955.6$ |
| The CUS phase performed on a mobile device | $6{T_{bp}}+3{T_{me}}$ | $\approx 669.3$ | $\approx 669.3$ | $\approx 669.3$ |
In the following, we present the required computation costs and time of the proposed LRSC-AMRS scheme on a PC and a mobile device. Based on the computational simulations in Xiong and Qin (2015), Table 3 lists the computational notations and the associated computation time of two time-consuming operations on a PC and a mobile device, where the PC is equipped with a 3 GHz Pentium CPU under the MS Windows and the mobile device is equipped with a 624 MHz PXA270 CPU under a Linux system. It is worth mentioning that the adopted bilinear pairing group set has a 1024-bit RSA security level. Indeed, the required computation cost for a recipient ${\textit{CLID}_{r}}$ is greater than that for a recipient ${\textit{PKID}_{r}}$. Therefore, we consider the required time for multiple recipients ${\textit{CLID}_{r}}$, where $r=1,2,\dots ,n$. Table 4 demonstrates the required computation costs and time for the compatible multi-signcryption (CMS) and the compatible unsigncryption (CUS) phases in the proposed LRSC-AMRS scheme. By Table 4, the performance of the proposed LRSC-AMRS scheme is suitable for a PC and a mobile device.
7 Conclusions and Future Work
In this paper, the first LRSC-AMRS scheme suitable for heterogeneous PKCs (PKI-PKC and CL-PKC) has been proposed. As mentioned earlier, the LRSC-AMRS scheme must possess three security properties, namely, encryption confidentiality, recipient anonymity and sender (i.e. BMC) authentication, which have been modelled by the LRSC-EIND-CCA, LRSC-RIND-CCA and LRSC-EU-ACMA games, respectively. In the three games, adversaries (including illegal recipient and malicious KGA) are allowed to continuously acquire partial information of secret keys for multiple rounds. In the GBPG model, based on the DL and SHF security assumptions, three theorems have been shown that the LRSC-AMRS scheme achieves three security properties against adversaries. By comparing with the related schemes, the LRSC-AMRS scheme has four merits as listed below.
-
(1) It is the first LRSC-AMRS scheme suitable for heterogeneous PKCs.
-
(2) Multiple recipients in the LRSC-AMRS scheme can be initial recipients in the PKI-PKC, or new and upgraded recipients in the CL-PKC.
-
(3) Since adversaries are allowed to continuously acquire partial information of secret keys for multiple rounds, the LRSC-AMRS scheme possesses unbounded leakage resilience.
-
(4) The computational cost of the unsigncryption algorithm is constant $O(1)$.
Finally, let us point out possible future work. Due to the practical realization of quantum computers, post-quantum cryptography has attracted the attention of researchers. As far as we know, there exists no quantum-resistant AMRS scheme. Therefore, to propose a post-quantum AMRS scheme is an interesting topic. Furthermore, it is more practical to propose a post-quantum AMRS scheme suitable for recipients in heterogeneous PKCs.