INFORMATICA Informatica 1822-88440868-49520868-4952 Vilnius University INFOR600 10.15388/25-INFOR600 Research Article LRSC-AMRS: Leakage-Resilient and Seamlessly Compatible Anonymous Multi-Recipient Signcryption in Heterogeneous Public-Key Cryptographies TsengYuh-Minymtseng@cc.ncue.edu.tw∗

Y.-M. Tseng is currently the vice president and a professor in the Department of Mathematics, National Changhua University of Education, Taiwan. He is a member of IEEE Computer Society, IEEE Communications Society and the Chinese Cryptology and Information Security Association (CCISA). He has published over one hundred scientific journal papers on various research areas of cryptography, security and computer network. His research interests include cryptography, network security, computer network and leakage-resilient cryptography. He serves as an editor of several international journals.

 HoTing-Chieh

T.-C. Ho is currently pursuing the PhD degree with the Department of Mathematics, National Changhua University of Education, Changhua, Taiwan. Her research interests include applied cryptography, information security and leakage-resilience cryptography.

 HuangSen-Shan

S.-S. Huang received the PhD degree from the University of Illinois at Urbana–Champaign, Champaign, IL, USA, in 1997, under the supervision of Prof. B. C. Berndt. He is currently a Professor with the Department of Mathematics, National Changhua University of Education, Changhua, Taiwan. His research interests include number theory, cryptography, and leakage-resilient cryptography.

 Department of Mathematics, National Changhua University of Education, Changhua 500, Taiwan Corresponding author. 202511920253637377644202592025 © 2025 Vilnius University2025 Open access article under the CC BY license.

Anonymous multi-recipient signcryption (AMRS) is an important scheme of public-key cryptography (PKC) and applied for many modern digital applications. In an AMRS scheme, a broadcast management centre (BMC) may sign and encrypt a plaintext data (or file) to a set of multiple recipients. Meanwhile, only these recipients in the set can decrypt the plaintext data and authenticate the BMC while offering anonymity of their identities. In the past, some AMRS schemes based on various PKCs have been proposed. Recently, due to side-channel attacks, the existing cryptographic mechanisms could be broken so that leakage-resilient PKC resisting such attacks has attracted the attention of cryptographic researches. However, the work on the design of leakage-resilient AMRS (LR-AMRS) schemes is little and only suitable for multiple recipients under a single PKC. In this paper, the first leakage-resilient and seamlessly compatible AMRS (LRSC-AMRS) in heterogeneous PKCs is proposed. In the proposed scheme, multiple recipients can be members of two heterogeneous PKCs, namely, the public-key infrastructure PKC (PKI-PKC) or the certificateless PKC (CL-PKC). Also, we present a seamlessly compatible upgradation procedure from the PKI-PKC to the CL-PKC. The proposed scheme achieves three security properties under side-channel attacks, namely, encryption confidentiality, recipient anonymity and sender (i.e. BMC) authentication, which are formally shown by the associated security theorems. Finally, by comparing with related schemes, it is shown that the proposed LRSC-AMRS scheme is suitable for heterogeneous recipients and the computational cost of each recipient’s unsigncryption algorithm is constant O ( 1 ).

 leakage resilience multiple recipients anonymity encryption authentication heterogeneous public-key cryptographies 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.

The system architecture of an AMRS scheme in a PKC.

 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).

An illustration of the PKC upgradation from the PKI-PKC to the CL-PKC.

 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.

 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.

 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.

 Preliminaries Bilinear Pairing Group Set

Let G = ⟨ Q ⟩ and G e = ⟨ Q e ⟩, 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 e ˆ: G × G → G e . These parameters above form a bilinear pairing group set B P G S = { G , G e , e ˆ , p , Q , Q e } (Boneh and Franklin, 2001). The set BPGS possesses three properties as presented below.

Non-degenerating: e ˆ ( Q , Q ) = Q e ≠ 1.

Efficient computing: e ˆ ( a · Q , b · Q ) can be efficiently computed, for all a , b ∈ Z p ∗ .

Bilinear pairing: e ˆ ( a · Q , b · Q ) = e ˆ ( Q , Q ) a b = Q e a b , for all a , b ∈ Z p ∗ .

GBPG Model

Here, let us introduce a technique in proving security theorems for cryptographic schemes by using the set B P G S = { G , G e , 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 B P G S = { G , G e , e ˆ , p , Q , Q e }, namely, the addition in G, the multiplication in G e and the bilinear pairing mapping 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 B P G S = { G , G e , e ˆ , p , Q , Q e } has three operations O P 0 , O P e and O P b p that respectively denote the addition a · Q, the multiplication Q e a and the bilinear pairing mapping e ˆ ( a · Q , b · Q ) = Q e a b , for all a , b ∈ Z p ∗ . Also, there are two mapping functions ζ : Z p ∗ → Ω G and ζ e : Z p ∗ → Ω G e that are employed to encode all elements of G and G e to distinct bit-strings. Additionally, two output sets Ω G and Ω G e satisfy | Ω G | = | Ω G e | = p and Ω G ∩ Ω G e = ϕ, where | · | denotes the number of O P 0 , O P e and O P b p possess the following properties.

O P 0 ( ζ ( a ) , ζ ( b ) ) → ζ ( a + b mod p ).

O P e ( ζ e ( a ) , ζ e ( b ) ) → ζ e ( a + b mod p ).

O P b p ( ζ ( a ) , ζ ( b ) ) → ζ e ( a · b mod p ).

 It is worth mentioning that ζ ( 1 ) and ζ e ( 1 ) denote the group generators Q and Q e , respectively.

 Security Assumptions

In the set B P G S = { G , G e , 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 ∈ Z p ∗ , and given a · Q ∈ G or e ˆ ( Q , Q ) a ∈ G e , to compute a is hard.

Secure hash function (SHF) security assumption: For a secure hash function S H : { 0 , 1 } ∗ → { 0 , 1 } l with a fixed length l, it must satisfy one-way, weak-collision resistance and strong-collision resistance.

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 R V and Pb [ R V = r v ] denote a finite random variable (fixed-length secret key) and the probability of the event R V = r v, respectively. Also, two types of minimal entropies for single finite random variable are defined as follows.

Minimal entropy of R V: H ∞ ( R V ) = − log 2 ( max r v Pb [ R V = r v ] ) .

Conditionally minimal entropy of R V under the event E: H ˜ ∞ ( R V | E ) = − log 2 ( E [ max r v [ R V = r v | E ] ] ) .

To consider the entropy of single secret key (i.e. finite random variable R V) under a leakage function L F, 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 , … , R V n − 1 ), Galindo and Vivek (2013) obtained Lemma 2 below.

Let L F : R V → { 0 , 1 } γ be a leakage function of R V with a fixed-bit-length γ. Thus, we have H ˜ ∞ ( R V | L F ( R V ) ) ≧ H ∞ ( R V ) − γ.

Let M P ∈ Z p ∗ [ R V 0 , R V 1 , … , R V n − 1 ] be a multiple-variable polynomial with maximal degree d. For i = 0 , 1 , … , n − 1, let P D i be mutually independent probability distributions of R V i = r v i ← Z p ∗ such that both H ∞ ( P D i ) ≧ log p − γ and 0 ≦ γ ≦ log p. If γ < log p ( 1 − ϵ ) and ϵ is a positive decimal, the probability Pb [ M P ( R V 0 = r v 0 , R V 1 = r v 1 , … , R V n − 1 = r v n − 1 ) = 0 ] ≦ 2 γ ( d / p ) is negligible.

 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.

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
( SSK C A , SPK C A ) The system secret/public key pair of the CA
KGA The key generating authority (KGA) in the CL-PKC
( SSK K G A , SPK K G A ) The system secret/public key pair of the KGA
BMC The broadcast management centre (BMC) in the PKI-PKC
PKID B M C The identity of the BMC
( S K B M C , P K B M C ) The secret/public key pair of the BMC
CRTF B M C The certificate of the BMC
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 PKID r
CRTF r The certificate of PKID r
CLID r The identity of a recipient in the CL-PKC
( ISK r , IPK r ) The individual secret/public key pair of the recipient CLID r
( MSK r , MPK r ) The member secret/public key pair of the recipient CLID r
P D A plaintext data
E D An encrypted data
SEF / SDF The symmetric encrypting/decrypting functions
e d k SEF e d k ( ) / SDF e d k ( ), where e d k is an encrypting/decrypting key
SDHR A set of designated heterogeneous recipients, SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ], r = 1 , 2 , … , n }
BCS A broadcast ciphertext set generated by the BMC
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 ( SSK C A , SPK C A ) and ( SSK K G A , SPK K G A ), 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 PKID B M C decides the secret/public key pair ( S K B M C , P K B M C ) while conveying ( PKID B M C , P K B M C ) to the CA. The CA creates and sends back the certificate CRTF B M C .

Key generating procedures of the LRSC-AMRS scheme.

Initial recipients: An initial recipient with identity PKID r decides the secret/public key pair ( S K r , P K r ) while conveying ( PKID r , P K r ) to the CA. The CA creates and sends back the certificate CRTF r .

New recipients: A new recipient with identity CLID r decides the individual secret/public key pair ( ISK r , IPK r ) while conveying ( CLID r , IPK r ) to the KGA. The KGA creates and sends back the member secret/public key pair ( MSK r , MPK r ).

The usages of the CMS and CUS algorithms in the LRSC-AMRS scheme.

Upgraded recipients: If an initial recipient with identity PKID r would like to upgrade to the CL-PKC, she/he renames PKID r to CLID r and ( PKID r , P K r ) to ( ISK r , IPK r ). Also, the upgraded recipient conveys ( CLID r , IPK r ) to the KGA. The KGA creates and sends back the member secret/public key pair ( MSK r , MPK r ).

In the LRSC-AMRS scheme, when the BMC would like to convey a plaintext data ( P D) to a set of designated heterogeneous recipients, namely, SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n }, the BMC carries out the Compatible multi-signcryption (CMS) algorithm to generate a broadcast ciphertext set BCS = CMS ( P D , SDHR , S K B M C ). If some PKID r or CLID r lies in the set SDHR, the recipient PKID r or CLID r performs the Compatible unsigncryption (CUS) algorithm to get and validate P D = CUS ( BCS , PKID B M C , S K r ) or P D = CUS ( BCS , PKID B M C , ISK r , MSK r ), respectively. Figure 4 depicts the usages of the CMS and 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, SSK C A and SSK K G A are initially separated into ( SSK C A , 0 , a , SSK C A , 0 , b ) and ( SSK K G A , 0 , a , SSKK G A , 0 , b ). Also, S K B M C , S K r , ISK r and MSK r are separated into ( S K B M C , 0 , a , S K B M C , 0 , b ), ( S K r , 0 , a , S K r , 0 , b ), ( ISK r , 0 , a , ISK r , 0 , b ) and ( MSK r , 0 , a , MSK r , 0 , b ). Finally, the syntax (framework) of the LRSC-AMRS scheme is presented in Definition 1. (<italic>Syntax</italic>)<italic>.</italic>

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 ( 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 HPSP, the CA decides the system secret/public key pair ( SSK C A , SPK C A ). Also, the CA separates SSK C A into two fragments ( SSK C A , 0 , a , SSK C A , 0 , b ) by the key refreshing procedure.

CL-PKC: By HPSP, the KGA decides the system secret/public key pair ( SSK K G A , SPK K G A ). Also, the KGA separates SSK K G A into two fragments ( SSK K G A , 0 , a , SSK K G A , 0 , b ) by the key refreshing procedure.

At the end of this phase, HPSP, SPK C A and SPK K G A 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:

In the PKI-PKC, the BMC or an initial recipient with identity PKID r first decides their own secret/public key pair ( S K B M C , P K B M C ) or ( S K r , P K r ) while separating S K B M C or S K r into ( S K B M C , 0 , a , S K B M C , 0 , b ) or ( S K r , 0 , a , S K r , 0 , b ), respectively. Also, they convey ( PKID B M C , P K B M C ) or ( PKID r , P K r ) to the CA, respectively.

Upon receiving ( PKID B M C , P K B M C ) or ( PKID r , P K r ), in the i-th round of this procedure, the CA first refreshes ( SSK C A , i − 1 , a , SSK C A , i − 1 , b ) to get ( SSK C A , i , a , SSK C A , i , b ) such that SSK C A = SSK C A , 0 , a · SSK C A , 0 , b = SSK C A , 1 , a · SSK C A , 1 , b = ⋯ = SSK C A , i − 1 , a · SSK C A , i − 1 , b = SSK C A , i , a · SSK C A , i , b . The CA then uses ( SSK C A , i , a , SSK C A , i , b ) to create and send back the certificate CRTF B M C or CRTF r to the BMC or the recipient PKID r , respectively.

CL-PKC:

In the CL-PKC, a new recipient with identity CLID r first decides the individual secret/public key pair ( ISK r , IPK r ) while separating ISK r into ( ISK r , 0 , a , ISK r , 0 , b ). Also, the recipient CLID r conveys ( CLID r , IPK r ) to the KGA.

Upon receiving ( CLID r , IPK r ), in the i-th round of this procedure, the KGA refreshes ( SSK K G A , i − 1 , a , SSK K G A , i − 1 , b ) to get ( SSK K G A , i , a , SSK K G A , i , b ) such that SSK K G A = SSK K G A , 0 , a · SSK K G A , 0 , b = SSK K G A , 1 , a · SSK K G A , 1 , b = ⋯ = SSK K G A , i − 1 , a · SSK K G A , i − 1 , b = SSK K G A , i , a · SSK K G A , i , b . The KGA then uses ( SSK K G A , i , a , SSK K G A , i , b ) to create and send back the member secret/public key pair ( MSK r , MPK r ) to the recipient CLID r .

Upon receiving ( MSK r , MPK r ), the recipient CLID r separates MSK r into ( MSK r , 0 , a , MSK r , 0 , b ). Finally, the recipient CLID r has the private key pair ( ISK r , MSK r ) and pubic key pair ( IPK r , MPK r ).

When an initial recipient with identity PKID r in the PKI-PKC would like to upgrade to the CL-PKC, she/he renames PKID r to CLID r and ( S K r , P K r ) to ( ISK r , IPK r ), respectively. The upgraded recipient CLID r then runs the steps (2) and (3) above to get the private key pair ( ISK r , MSK r ) and pubic key pair ( IPK r , MPK r ).

Compatible multi-signcryption (CMS) phase: When the BMC would like to convey a plaintext data ( P D) to a set of designated heterogeneous recipients, namely, SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n } in the j-th round of this procedure, the BMC carries out the CMS algorithm to generate a broadcast ciphertext set BCS by running the following steps.

The BMC refreshes ( S K B M C , j − 1 , a , S K B M C , j − 1 , b ) to get ( S K B M C , j , a , S K B M C , j , b ) such that S K B M C = S K B M C , 0 , a · S K B M C , 0 , b = S K B M C , 1 , a · S K B M C , 1 , b = ⋯ = S K B M C , j − 1 , a · S K B M C , j − 1 , b = S K B M C , j , a · S K B M C , j , b .

By taking P D and SDHR as input , the BMC generates BCS = CMS ( P D , SDHR , ( S K B M C , j , a , S K B M C , j , b ) ).

Compatible unsigncryption (CUS) phase: Upon receiving BCS, if the recipients PKID r in the PKI-PKC or the recipients CLID r in the CL-PKC lie in the set SDHR, they carry out the following procedures, respectively.

PKI-PKC: For the k-th round of this procedure, the recipient 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 · S K r , 0 , b = S K r , 1 , a · S K r , 1 , b = ⋯ = S K r , k − 1 , a · S K r , k − 1 , b = S K r , k , a · S K r , k , b . The recipient PKID r carries out the CUS algorithm to get and validate P D = CUS ( BCS , PKID B M C , ( S K r , k , a , S K r , k , b ) ).

CL-PKC: For the k-th round of this procedure, the recipient CLID r , respectively, refreshes ( ISK r , k − 1 , a , ISK r , k − 1 , b ) and ( MSK r , k − 1 , a , MSK r , k − 1 , b ) to get ( ISK r , k , a , ISK r , k , b ) and ( MSK r , k , a , MSK r , k , b ) such that ISK r = ISK r , 0 , a · ISK r , 0 , b = ISK r , 1 , a · ISK r , 1 , b = ⋯ = ISK r , k − 1 , a · ISK r , k − 1 , b = ISK r , k , a · ISK r , k , b and MSK r = MSK r , 0 , a · MSK r , 0 , b = MSK r , 1 , a · MSK r , 1 , b = ⋯ = MSK r , k − 1 , a · MSK r , k − 1 , b = MSK r , k , a · MSK r , k , b . The recipient CLID r carries out the CUS algorithm to get and validate P D = CUS ( BCS , PKID B M C , ( ISK r , k , a , ISK r , k , b ) , ( MSK r , k , a , MSK r , k , b ) ).

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 Δ f and Δ h denote the associated outputs of f and h, respectively. Hence, we have five pairs of leakage functions as defined below.

Δ f C A , i = f C A , i ( SSK C A , i , a ) and Δ h C A , i = h C A , i ( SSK C A , i , b ) for the CA’s system secret key.

Δ f K G A , i = f K G A , i ( SSK K G A , i , a ) and Δ h K G A , i = h K G A , i ( SSK K G A , i , b ) for the KGA’s system secret key.

Δ f B M C , j = f B M C , j ( S K B M C , j , a ) and Δ h B M C , j = h B M C , j ( S K B M C , j , b ) for the BMC’s secret key.

Δ f PKID r , k = f P K I D r , k ( S K r , k , a ) and Δ h P K I D r , k = h PKID r , k ( S K r , k , b ) for the recipient PKID r ’s secret key.

Δ f CLID r , k = f CLID r , k ( ISK r , k , a , MSK r , 0 , a ) and Δ h CLID r , k = h CLID r , k ( ISK r , k , b , MSK r , 0 , b ) for the recipient 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 PKID r , as well as both ISK r and MSK r of any recipient CLID r .

A I is disallowed to acquire S K r ∗ of the target recipient PKID r ∗ , but it may acquire partial information of S K r ∗ by two leakage functions f PKID r , k and h PKID r , k .

A I is disallowed to acquire MSK r ∗ of the target recipient CLID r ∗ , but it may acquire partial information of MSK r ∗ by two leakage functions f CLID r , k and h CLID r , k defined above.

A I may acquire partial information of SSK C A by two leakage functions f C A , i and h C A , i .

A I may acquire partial information of SSK K G A by two leakage functions f K G A , i and h K G A , i .

Malicious KGA ( A II ): It is assumed that A II possesses the system secret key SSK K G A of the KGA.

A II may acquire S K r of any recipient PKID r , and both ISK r and MSK r of any recipient CLID r .

A II is disallowed to acquire S K r ∗ of the target recipient PKID r ∗ , but it may acquire partial information of S K r ∗ by f PKID r , k and h PKID r , k .

A II is disallowed to acquire ISK r ∗ of the target recipient CLID r ∗ , but it may acquire partial information of ISK r ∗ by f CLID r , k and h 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 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. (<italic>LRSC-EIND-CCA game</italic>)<italic>.</italic>

The LRSC-AMRS scheme achieves the encryption confidentiality if no PPT adversary A ( A I or A 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 HPSP, ( SSK C A , SPK C A ), and ( SSK K G A , SPK K G A ). If A is type of A II , SSK K G A is conveyed to A. Finally, HPSP, SPK C A and SPK K G A are publicly announced.

Query: A may adaptively request to C the following queries.

Secret key query ( PKID B M C / PKID r ): By PKID B M C or PKID r , C returns ( S K B M C , P K B M C ) or ( S K r , P K r ).

Certificate query (( PKID B M C , P K B M C )/( PKID r , P K r )): For the i-th request of this query, C refreshes ( S S K C A , i − 1 , a , S S K C A , i − 1 , b ) to get ( S S K C A , i , a , S S K C A , i , b ). By ( PKID B M C , P K B M C ) or ( PKID r , P K r ), C uses ( S S K C A , i , a , SSK C A , i , b ) to create and send back CRTF B M C or CRTF r to the BMC or the recipient PKID r , respectively.

Certificate leakage query (i, f C A , i , h C A , i ): For the i-th Certificate query, A may request this leakage query only once. C returns Δ f C A , i = f C A , i ( SSK C A , i , a ) and Δ h C A , i = h C A , i ( SSK C A , i , b ).

Individual secret key query ( CLID r ): By CLID r , C returns ( ISK r , IPK r ) if the Public key replacement query ( CLID r , ( I P K r ′ , M P K r ′ )) is never requested. Otherwise, C returns “failure”.

Member secret key query ( CLID r , IPK r ): For the i-th request of this query, C refreshes ( SSK K G A , i − 1 , a , SSK K G A , i − 1 , b ) to get ( SSK K G A , i , a , SSK K G A , i , b ). By ( CLID r , IPK r ), C uses ( SSK K G A , i , a , SSK K G A , i , b ) to create and send back ( MSK r , MPK r ).

Member secret key leakage query (i, f K G A , i , h K G A , i ): For the i-th Member secret key query, A may request this leakage query only once. C returns Δ f K G A , i = f K G A , i ( SSK K G A , i , a ) and Δ h K G A , i = h K G A , i ( SSK K G A , i , b ).

Public key replacement query ( CLID r , ( I P K r ′ , M P K r ′ )): C records this replacement.

Compatible multi-signcryption (CMS) query ( P D, SDHR, PKID B M C ): For the j-th request of this query, C refreshes ( S K B M C , j − 1 , a , S K B M C , j − 1 , b ) to get ( S K B M C , j , a , S K B M C , j , b ). By ( P D, SDHR), C uses ( S K B M C , j , a , S K B M C , j , b ) to create and send back BCS = CMS ( P D, SDHR, ( S K B M C , j , a , S K B M C , j , b )).

Compatible multi-signcryption (CMS) leakage query (j, f B M C , j , h B M C , j ): For the j-th Compatible multi-signcryption (CMS) query, A may request this leakage query only once. C returns Δ f B M C , j = f B M C , j ( S K B M C , j , a ) and Δ h B M C , j = h B M C , j ( S K B M C , j , b ).

Compatible unsigncryption (CUS) query ( PKID r / CLID r , BCS): For the k-th request of this query with PKID r or CLID r , C runs the following associated procedures.

For 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 P D = CUS ( BCS , PKID B M C , ( S K r , k , a , S K r , k , b ) ).

For CLID r , C refreshes ( ISK r , k − 1 , a , ISK r , k − 1 , b ) and ( MSK r , k − 1 , a , MSK r , k − 1 , b ), respectively, to get ( ISK r , k , a , ISK r , k , b ) and ( MSK r , k , a , MSK r , k , b ). C returns P D = CUS ( BCS, PKID B M C , ( ISK r , k , a , ISK r , k , b ), ( MSK r , k , a , MSK r , k , b ) ).

Compatible unsigncryption (CUS) leakage query ( k , ( f PKID r , k , h PKID r , k ) / ( f CLID r , k , h CLID r , k ) ): For the k-th Compatible unsigncryption (CUS) query with PKID r or CLID r . For PKID r , C sends back Δ f PKID r , k = f PKID r , k ( S K r , k , a ) and Δ h PKID r , k = h PKID r , k ( S K r , k , b ). For CLID r , C sends back Δ f CLID r , k = f CLID r , k ( ISK r , k , a , MSK r , 0 , a ) and Δ h CLID r , k = h CLID r , k ( ISK r , k , b , MSK r , 0 , b ).

Challenge: A conveys a plaintext data pair ( P D 1 , P D 2 ) and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n } to C. C selects a random value λ ∈ { 1 , 2 } and refreshes ( S K B M C , j − 1 , a , S K B M C , j − 1 , b ) to get ( S K B M C , j , a , S K B M C , j , b ). Finally, C generates and sends back BCS = CMS ( P D λ , SDHR, ( S K B M C , j , a , S K B M C , j , b )). In addition, the following two conditions must be satisfied.

For A I , it cannot request the Secret key query ( PKID r ) or Member secret key query ( CLID r , IPK r ), for r = 1 , 2 , … , n.

For A II , it cannot request the Secret key query ( PKID r ), Individual secret key query ( CLID r ) or Public key replacement query ( CLID r , ( I P K r ′ , M P K r ′ )), for r = 1 , 2 , … , n.

Guess: If A outputs λ ′ ∈ { 1 , 2 } and λ ′ = λ, it means that A wins the LRSC-EIND-CCA game and the associated advantage is A d v ( A ) = | Pb [ λ ′ = λ ] − 1 / 2 |.

(<italic>LRSC-RIND-CCA game</italic>)<italic>.</italic>

The LRSC-AMRS scheme achieves the recipient anonymity if no PPT adversary A ( A I or A 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 P D and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n + 1 } to C. C selects a random value λ ∈ { 1 , 2 } and sets SDHR ′ = { [ ( PKID λ , P K λ ) ‖ ( CLID λ , IPK λ , MPK λ ) ] , [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 3 , … , n + 1 }. Finally, C refreshes ( S K B M C , j − 1 , a , S K B M C , j − 1 , b ) to get ( S K B M C , j , a , S K B M C , j , b ), and generates and sends back BCS = CMS ( P D , SDHR ′ , ( S K B M C , j , a , S K B M C , j , b ) ). In addition, the following two conditions must be satisfied.

For A I , it cannot request the Secret key query ( PKID λ ) or Member secret key query ( CLID λ , IPK λ ), for λ = 1 and 2.

For A II , it cannot request the Secret key query ( PKID λ ), Individual secret key query ( CLID λ ) or Public key replacement query ( CLID λ , ( I P K λ ′ , M P K λ ′ ) ), for λ = 1 and 2.

Guess: If A outputs λ ′ ∈ { 1 , 2 } and λ ′ = λ, it means that A wins the LRSC-RIND-CCA game and the associated advantage is A d v ( A ) = | Pb [ λ ′ = λ ] − 1 / 2 |.

(<italic>LRSC-EU-ACMA game</italic>)<italic>.</italic>

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 BCS ′ for a plaintext data P D and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n }. For any recipients PKID r and CLID r in SDHR, if they may, respectively, carry out the CUS algorithm to get and validate P D = CUS ( BCS ′ , PKID B M C , ( S K r , k , a , S K r , k , b ) ) or P D = CUS ( BCS ′ , PKID B M C , ( ISK r , k , a , ISK r , k , b ), ( MSK r , k , a , MSK r , k , b ) ), then A wins the LRSC-EU-ACMA game. Note that A cannot request the Secret key query ( PKID B M C ).

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.

Initialization phase: By the bilinear pairing group set BPGS = { G , G e , e ˆ , p , Q , Q e } defined in previous section, the heterogeneously public system parameters ( HPSP) about the PKI-PKC and the CL-PKC are decided as HPSP = { G , G e , e ˆ , p , Q , Q e , A , B , S E F / S D F , S H 0 , S H 1 , S H 2 , S H 3 , S H 4 , S H 5 }, where A, B ∈ G, S E F / S D F are symmetric encrypting/decrypting functions, and S H 0 : { 0 , 1 } ∗ × G × G → { 0 , 1 } l , S H 1 : G → { 0 , 1 } l , S H 2 : G × G → { 0 , 1 } l , S H 3 , S H 4 : { 0 , 1 } l → { 0 , 1 } l and S H 5 : G × { 0 , 1 } ∗ → { 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 HPSP, the CA selects two random values s, t 0 ∈ Z p ∗ , and decides the system secret/public key pair ( SSK C A , SPK C A ), where SSK C A = s · Q and SPK C A = e ˆ ( Q , s · Q ). Also, the CA uses the key refreshing procedure to separate SSK C A into a pair of two fragments ( SSK C A , 0 , a , SSK C A , 0 , b ), where SSK C A , 0 , a = t 0 · Q and SSK C A , 0 , b = SSK C A − t 0 · Q.

CL-PKC: By HPSP, the KGA selects two random values u , v 0 ∈ Z p ∗ , and decides the system secret/public key pair ( SSK K G A , SPK K G A ), where SSK K G A = u · Q and SPK K G A = e ˆ ( Q, u · Q ). Also, the KGA uses the key refreshing procedure to separate SSK K G A into a pair of two fragments ( SSK K G A , 0 , a , SSK K G A , 0 , b ) , where SSK K G A , 0 , a = v 0 · Q and SSK K G A , 0 , b = SSK K G A − v 0 · Q.

At the end of this phase, HPSP, SPK C A and SPK K G A 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:

In the PKI-PKC, the BMC selects two random values w, x 0 ∈ Z p ∗ , and decides her/his own secret/public key pair ( S K B M C , P K B M C ) while separating S K B M C into ( S K B M C , 0 , a , S K B M C , 0 , b ), where S K B M C = w · Q, P K B M C = e ˆ ( Q, w · Q ), S K B M C , 0 , a = x 0 · Q and S K B M C , 0 , b = S K B M C − x 0 · Q. Also, for an initial recipient with identity PKID r , she/he selects two random values y, z 0 ∈ Z p ∗ , 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 · Q, P K r = e ˆ ( Q, y · Q ), S K r , 0 , a = z 0 · Q and S K r , 0 , b = S K r − z 0 · Q. Also, they convey ( PKID B M C , P K B M C ) or ( PKID r , P K r ) to the CA, respectively.

Upon receiving ( PKID B M C , P K B M C ) or ( PKID r , P K r ), the CA selects a random value t i ∈ Z p ∗ , and refreshes ( SSK C A , i − 1 , a , SSK C A , i − 1 , b ) to get ( SSK C A , i , a , SSK C A , i , b ), where SSK C A , i , a = SSK C A , i − 1 , a + t i · Q and SSK C A , i , b = SSK C A , i − 1 , b − t i · Q. By a leakage-resilient signature scheme (Tsai et al., 2022), the CA then uses ( SSK C A , i , a , SSK C A , i , b ) to create and send back the certificate CRTF B M C or CRTF r to the BMC or the recipient PKID r , respectively.

CL-PKC:

In the CL-PKC, a new recipient with identity CLID r selects two random values α, β 0 ∈ Z p ∗ , and decides the individual secret/public key pair ( ISK r , IPK r ) while separating ISK r into ( ISK r , 0 , a , ISK r , 0 , b ), where ISK r = α · Q, IPK r = e ˆ ( Q, α · Q ), ISK r , 0 , a = β 0 · Q and ISK r , 0 , b = ISK r − β 0 · Q. Also, the recipient CLID r conveys ( CLID r , IPK r ) to the KGA.

Upon receiving ( CLID r , IPK r ), the KGA selects a random value v i ∈ Z p ∗ , and refreshes ( SSK K G A , i − 1 , a , SSK K G A , i − 1 , b ) to get ( SSK K G A , i , a , SSK K G A , i , b ), where SSK K G A , i , a = SSK K G A , i − 1 , a + v i · Q and SSK K G A , i , b = SSK K G A , i − 1 , b − v i · Q. The KGA uses ( SSK K G A , i , a , SSK K G A , i , b ) to create and send back the member secret/public key pair ( MSK r , MPK r ) to the recipient CLID r by running the following steps.

Select a random value δ ∈ Z p ∗ .

Compute MPK r = δ · Q and C L T e m p i = SSK K G A , i , a + δ · ( A + θ · B ), where θ = S H 0 ( CLID r , IPK r , MPK r ).

Compute MSK r = C L T e m p i + SSK K G A , i , b .

Upon receiving ( MSK r , MPK r ), the recipient CLID r selects a random value γ 0 ∈ Z p ∗ , and separates MSK r into ( MSK r , 0 , a , MSK r , 0 , b ), where MSK r , 0 , a = γ 0 · Q and MSK r , 0 , b = MSK r − γ 0 · Q. Finally, the recipient CLID r has the private key pair ( ISK r , MSK r ) and pubic key pair ( IPK r , MPK r ).

When an initial recipient with identity PKID r in the PKI-PKC would like to upgrade to the CL-PKC, she/he renames PKID r to CLID r and ( S K r , P K r ) to ( ISK r , IPK r ), respectively. The upgraded recipient CLID r then runs the steps (2) and (3) above to get the private key pair ( ISK r , MSK r ) and pubic key pair ( IPK r , MPK r ).

Compatible multi-signcryption (CMS) phase: When the BMC would like to convey a plaintext data P D to a set of designated heterogeneous recipients, namely, SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n }, the BMC carries out the CMS algorithm to generate a broadcast ciphertext set BCS by running the following steps.

The BMC selects a random value x j ∈ Z p ∗ , and refreshes ( S K B M C , j − 1 , a , S K B M C , j − 1 , b ) to get ( S K B M C , j , a , S K B M C , j , b ), where S K B M C , j , a = S K B M C , j − 1 , a + x j · Q and S K B M C , j , b = S K B M C , j − 1 , b − x j · Q.

By taking P D and SDHR as input, the BMC generates BCS = CMS ( P D, SDHR, ( S K B M C , j , a , S K B M C , j , b ) ) by running the following steps.

Select an encrypting/decrypting key e d k ∈ { 0, 1 } l and generate an encrypted data E D = SEF e d k ( P D ).

Select a random value m ∈ Z p ∗ and compute M = m · Q.

For ( PKID r , P K r ) in SDHR, compute P C K r = ( P K r ) m and a common key C K r = S H 1 ( P C K r ).

For ( CLID r , IPK r , MPK r ) in SDHR, compute CCK r , 0 = ( IPK r ) m , CCK r , 1 = ( SPK K G A · e ˆ ( MPK r , A + θ · B ) ) m and C K r = S H 2 ( CCK r , 0 , CCK r , 1 ), where θ = S H 0 ( CLID r , IPK r , MPK r ).

According to Steps (c) and (d) above, generate C r = S H 3 ( C K r ) ‖ ( S H 4 ( C K r ) ⊕ e d k ), for r = 1 , 2 , … , n.

Compute STemp = S K B M C , j , a + m · ( A + ρ · B ), where ρ = S H 5 ( M , C 1 , C 2 , … , C n , P D , E D ).

Generate a signature σ = STemp + S K B M C , j , b .

Set the broadcast ciphertext set BCS = ⟨ ( C 1 , C 2 , … , C n ) , M , E D , σ ⟩.

Compatible unsigncryption (CUS) phase: Upon receiving BCS = ⟨ ( C 1 , C 2 , … , C n ) , M , E D , σ ⟩, if the recipient PKID r in the PKI-PKC or the recipient CLID r in the CL-PKC lie in the set SDHR, they carry out the following procedures.

The recipients PKID r and CLID r run the associated computations, respectively.

PKI-PKC: The recipient PKID r selects a random value z k ∈ Z p ∗ , 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 · Q and S K r , k , b = S K r , k − 1 , b − z k · Q. The recipient PKID r computes P T 1 = e ˆ ( M, S K r , k , a ), P C K r = P T 1 · e ˆ ( M, S K r , k , b ) and C K r = S H 1 ( P C K r ).

CL-PKC: The recipient CLID r selects two random values β k , γ k ∈ Z p ∗ , and respectively refreshes ( ISK r , k − 1 , a , ISK r , k − 1 , b ) and ( MSK r , k − 1 , a , MSK r , k − 1 , b ) to get ( ISK r , k , a , ISK r , k , b ) and ( MSK r , k , a , MSK r , k , b ), where ISK r , k , a = ISK r , k − 1 , a + β k · Q, ISK r , k , b = ISK r , k − 1 , b − β k · Q, MSK r , k , a = MSK r , k − 1 , a + γ k · Q and MSK r , k , b = MSK r , k − 1 , b − γ k · Q. Also, the recipient CLID r computes C T 0 = e ˆ ( M, ISK r , k , a ), CCK r , 0 = C T 0 · e ˆ ( M, ISK r , k , b ), C T 1 = e ˆ ( M, MSK r , k , a ), CCK r , 1 = C T 1 · e ˆ ( M, MSK r , k , b ) and C K r = S H 2 ( CCK r , 0 , CCK r , 1 ).

According to Step (1) above, the recipient PKID r or CLID r obtains C K r , and computes S H 3 ( C K r ) and S H 4 ( C K r ).

Use S H 3 ( C K r ) in (2) to find C r while truncating S H 3 ( C K r ) from C r .

Get e d k by computing S H 4 ( C K r ) ⊕ ( S H 4 ( C K r ) ⊕ e d k ).

Get the plaintext data P D = SDF e d k ( E D ) and compute ρ = S H 5 ( M , C 1 , C 2 , … , C n , P D , E D ).

If e ˆ ( Q, σ ) = P K B M C · e ˆ ( M, A + ρ · B ) holds, output P D and “True”; otherwise, output “invalid”.

 Correctness:

The correctness about e ˆ ( Q , σ ) = P K B M C · e ˆ ( M , A + ρ · B ), C K r = S H 1 ( P C K r ) and C K r = S H 2 ( CCK r , 0 , CCK r , 1 ) in the LRSC-AMRS scheme is verified by the following equalities. e ˆ ( Q , σ ) = e ˆ ( Q , STemp + S K B M C , j , b ) = e ˆ ( Q , S K B M C , j , a + m · ( A + ρ · B ) + S K B M C , j , b ) = e ˆ ( Q , S K B M C + m · ( A + ρ · B ) ) = e ˆ ( Q , S K B M C ) · e ˆ ( M , A + ρ · B ) = P K B M C · e ˆ ( M , A + ρ · B ) . P C K r = P T 1 · e ˆ ( M , S K r , k , b ) = e ˆ ( M , S K r , k , a ) · e ˆ ( M , S K r , k , b ) = e ˆ ( m · Q , S K r , k , a + S K r , k , b ) = e ˆ ( Q , S K r ) m = ( P K r ) m . CCK r , 0 = C T 0 · e ˆ ( M , ISK r , k , b ) = e ˆ ( M , ISK r , k , a ) · e ˆ ( M , ISK r , k , b ) = e ˆ ( m · Q , ISK r , k , a + ISK r , k , b ) = e ˆ ( Q , ISK r ) m = ( IPK r ) m . CCK r , 1 = C T 1 · e ˆ ( M , MSK r , k , b ) = e ˆ ( M , MSK r , k , a ) · e ˆ ( M , MSK r , k , b ) = e ˆ ( m · Q , MSK r , k , a + MSK r , k , b ) = e ˆ ( Q , MSK r ) m = e ˆ ( Q , SSK K G A + δ · ( A + θ · B ) ) m = ( e ˆ ( Q , SSK K G A ) · e ˆ ( Q , δ · ( A + θ · B ) ) ) m = ( SPK K G A · e ˆ ( δ · Q , ( A + θ · B ) ) ) m = ( SPK K G A · e ˆ ( MPK r , ( A + θ · B ) ) ) m .

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).

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.

The LRSC-EIND-CCA game is played by a PPT adversary A ( A I or A 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 HPSP = { G , G e , e ˆ , p , Q , Q e , A , B , S E F / S D F , S H 0 , S H 1 , S H 2 , S H 3 , S H 4 , S H 5 }. Also, C decides ( SSK C A , SPK C A ) of the CA and ( SSK K G A , SPK K G A ) of the KGA. If A is type of A II , SSK K G A is conveyed to A. Finally, HPSP, SPK C A and SPK K G A are publicly announced. Meanwhile, C sets five lists L T 0 , L T e , L T P K I , L T C L and L T CMS as follows.

L T 0 is set to log the i-th element of G by the pair ( Ψ G i , Ω G i ), where Ψ G i and Ω G i denote a multi-variate polynomial and the corresponding bit string. Initially, C adds ( Ψ Q, Ω G 1 ), ( Ψ A, Ω G 2 ), ( Ψ B, Ω G 3 ), ( Ψ SSK C A , Ω G 4 ) and ( Ψ SSK K G A , Ω G 5 ) to L T 0 . Here, there is an auto-converting procedure between Ψ G i and Ω 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 ( Ψ G E i , Ω G E i ), where Ψ G E i and Ω G E i denote a multi-variate polynomial and the corresponding bit string. Initially, C adds ( Ψ Q e , Ω G E 1 ), ( Ψ SPK C A , Ω G E 2 ) and ( Ψ SPK K G A , Ω G E 3 ) to L T e . Here, there is an auto-converting procedure between Ψ G E i and Ω G E i for any queries in the Query.

L T P K I is set to log the secret/public key pairs of the BMC and a recipient with identity PKID r in the PKI-PKC by the tuples ( PKID B M C , Ψ S K B M C , Ψ P K B M C ) and ( PKID r , Ψ S K r , Ψ P K r ), respectively.

L T C L is set to log the individual secret/public and member secret/public key pairs of a recipient with identity CLID r in the CL-PKC by the tuple ( CLID r , Ψ ISK r , Ψ IPK r , Ψ MSK r , Ψ MPK r ).

L T CMS is set to log the details of Compatible multi-signcryption (CMS) algorithm by the tuple ( Ψ M, Ψ P C K r /( Ψ CCK r , 0 , Ψ CCK r , 1 ), e d k) for each recipient PKID r / CLID r in the set SDHR.

Query: A may adaptively request to C the following queries at most q times.

O P 0 query ( Ω G i , Ω G j , Operator): By converting Ω G i and Ω G j in L T 0 , C first gets the corresponding Ψ G i and Ψ G j . If Operator = “ + ”, C computes Ψ G k = Ψ G i + Ψ G j . If Operator = “ − ”, C computes Ψ G k = Ψ G i − Ψ G j . Finally, C adds ( Ψ G k , Ω G k ) in L T 0 .

O P e query ( Ω G E i , Ω G E j , Operator): By converting Ω G E i and Ω G E j in L T e , C first gets the corresponding Ψ G E i and Ψ G E j . If Operator = “ × ”, C computes Ψ G E k = Ψ G E i + Ψ G E j . If Operator = “ / ”, C computes Ψ G E k = Ψ G E i − Ψ G E j . Finally, C adds ( Ψ G E k , Ω G E k ) in L T e .

O P b p query ( Ω G i , Ω G j ): By converting Ω G i and Ω G j in L T 0 , C first gets the corresponding Ψ G i and Ψ G j . Also, C computes Ψ G E k = Ψ G i · Ψ G j and adds ( Ψ G k , Ω G k ) in L T e .

Secret key query ( PKID B M C / PKID r ): By PKID B M C / PKID r , C searches ( PKID B M C / PKID r , Ψ S K B M C / Ψ S K r , Ψ P K B M C / Ψ P K r ) in L T P K I . If found, C returns ( Ω S K B M C / Ω S K r , Ω P K B M C / Ω P K r ) by converting Ψ S K B M C / Ψ S K r in L T 0 and Ψ P K B M C / Ψ P K r in L T e . If not found, C picks a new variate Ψ S K B M C or Ψ S K r in G, and computes Ψ P K B M C = Ψ Q · Ψ S K B M C or Ψ P K r = Ψ Q · Ψ S K r . Also, C adds ( PKID B M C / PKID r , Ψ S K B M C / Ψ S K r , Ψ P K B M C / Ψ P K r ) in L T P K I . Meanwhile, C adds ( Ψ S K B M C / Ψ S K r , Ω S K B M C / Ω S K r ) in L T 0 and ( Ψ P K B M C / Ψ P K r , Ω P K B M C / Ω P K r ) in L T e , and returns ( Ω S K B M C / Ω S K r , Ω P K B M C / Ω P K r ).

Certificate query ( ( PKID B M C , Ω P K B M C ) / ( PKID r , Ω P K r ) ): For the i-th request of this query, C refreshes ( Ψ SSK C A , i − 1 , a , Ψ SSK C A , i − 1 , b ) to get ( Ψ SSK C A , i , a , Ψ SSK C A , i , b ). By ( PKID B M C , Ω P K B M C ) or ( PKID r , Ω P K r ), C uses ( Ψ SSK C A , i , a , Ψ SSK C A , i , b ) to create and send back CRTF B M C or CRTF r to the BMC or the recipient PKID r , respectively.

Certificate leakage query (i, f C A , i , h C A , i ): For the i-th Certificate query, A may request this leakage query only once. C returns Δ f C A , i = f C A , i ( Ψ SSK C A , i , a ) and Δ h C A , i = h C A , i ( Ψ SSK C A , i , b ).

Individual secret key query ( CLID r ): By CLID r , C searches ( CLID r , Ψ ISK r , Ψ IPK r , Ψ MSK r , Ψ MPK r ) in L T C L . If found, C returns ( Ω ISK r , Ω IPK r ) by converting Ψ ISK r in L T 0 and Ψ IPK r in L T e . If not found, C picks a new variate Ψ ISK r in G, and computes Ψ IPK r = Ψ Q · Ψ ISK r . Also, C adds ( CLID r , Ψ ISK r , Ψ IPK r , − , − ) in L T C L . Meanwhile, C adds ( Ψ ISK r , Ω ISK r ) in L T 0 and ( Ψ IPK r , Ω IPK r ) in L T e , and returns ( Ω ISK r , Ω IPK r ).

Member secret key query ( CLID r , IPK r ): By CLID r , C searches ( CLID r , Ψ ISK r , Ψ IPK r , Ψ MSK r , Ψ MPK r ) in L T C L . If found, C returns ( Ω MSK r , Ω MPK r ) by converting Ψ MSK r in L T 0 and Ψ MPK r in L T e . If not found and for the i-th request of this query, C first refreshes ( Ψ SSK K G A , i − 1 , a , Ψ SSK K G A , i − 1 , b ) to get ( Ψ SSK K G A , i , a , Ψ SSK K G A , i , b ). C then picks two new variates Ψ MPK r and Ψ θ in G, and computes Ψ MSK r = Ψ SSK K G A + Ψ MPK r · ( Ψ A + Ψ θ · Ψ B). Also, C adds ( CLID r , Ψ ISK r , Ψ IPK r , Ψ MSK r , Ψ MPK r ) in L T C L . Meanwhile, C adds ( Ψ MPK r , Ω MPK r ), ( Ψ θ, Ω θ) and ( Ψ MSK r , Ω MSK r ) in L T 0 , and returns ( Ω MSK r , Ω MPK r ).

Member secret key leakage query (i, f K G A , i , h K G A , i ): For the i-th Member secret key query, A may request this leakage query only once. C returns Δ f K G A , i = f K G A , i ( Ψ SSK K G A , i , a ) and Δ h K G A , i = h K G A , i ( Ψ SSK K G A , i , b ).

Public key replacement query ( CLID r , ( Ω I P K r ′ , Ω M P K r ′ )): By converting Ω I P K r ′ and Ω M P K r ′ in L T 0 , C first gets the corresponding Ψ I P K r ′ and Ψ M P K r ′ . C modifies ( CLID r , −, Ψ I P K r ′ , −, Ψ M P K r ′ ) in L T C L .

Compatible multi-signcryption (CMS) query ( P D, SDHR, PKID B M C ): For the j-th request of this query, C refreshes ( Ψ S K B M C , j − 1 , a , Ψ S K B M C , j − 1 , b ) to get ( Ψ S K B M C , j , a , Ψ S K B M C , j , b ). By ( P D, SDHR), C uses ( Ψ S K B M C , j , a , Ψ S K B M C , j , b ) to create and send back BCS = CMS ( P D, SDHR, ( Ψ S K B M C , j , a , Ψ S K B M C , j , b ) ) as follows.

Select an encrypting/decrypting key e d k ∈ { 0 , 1 } l and generate an encrypted data E D = SEF e d k ( P D ).

Pick two new variates Ψ M and Ψ θ in G.

For ( PKID r , P K r ) in SDHR, compute Ψ P C K r = Ψ M · Ψ P K r and C K r = S H 1 ( Ω P C K r ), where Ω P C K r is the associated bit string of Ψ P C K r .

For ( CLID r , IPK r , MPK r ) in SDHR, compute Ψ CCK r , 0 = Ψ M · Ψ IPK r , Ψ CCK r , 1 = Ψ M · ( Ψ SPK K G A + Ψ MPK r · ( Ψ A + Ψ θ · Ψ B ) ) and C K r = S H 2 ( Ω CCK r , 0 , Ω CCK r , 1 ), where Ω CCK r , 0 and Ω CCK r , 1 are the associated bit strings of Ψ CCK r , 0 and Ψ CCK r , 1 .

According to Steps (c) and (d) above, generate C r = S H 3 ( C K r ) ‖ ( S H 4 ( C K r ) ⊕ e d k ), for r = 1 , 2 , … , n.

Pick a new variate Ψ ρ in G, and compute Ψ σ = Ψ S K B M C + Ψ M · ( Ψ A + Ψ ρ · Ψ B ).

Set BCS = ⟨ ( C 1 , C 2 , … , C n ), Ω M, E D, Ω σ ⟩, where Ω M and Ω σ are the associated bit strings of Ψ M and Ψ σ.

Compatible multi-signcryption (CMS) leakage query (j, f B M C , j , h B M C , j ): For the j-th Compatible multi-signcryption (CMS) query, A may request this leakage query only once. C returns Δ f B M C , j = f B M C , j ( Ψ S K B M C , j , a ) and Δ h B M C , j = h B M C , j ( Ψ S K B M C , j , b ).

Compatible unsigncryption (CUS) query ( PKID r / CLID r , BCS): For the k-th request of this query with PKID r or CLID r , C runs the following associated procedures.

For 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 then computes Ψ P C K r = Ψ M · ( Ψ Q · Ψ S K r ) and uses ( Ψ M, Ψ P C K r ) to find ( Ψ M, Ψ P C K r , e d k) in L T CMS to get P D = SDF e d k ( E D ). If Ψ Q · Ψ σ = Ψ P K B M C + Ψ Q · ( Ψ M · ( Ψ A + Ψ ρ · Ψ B ) ) holds, output P D and “True”; otherwise, output “invalid”.

For CLID r , C respectively refreshes ( Ψ ISK r , k − 1 , a , Ψ ISK r , k − 1 , b ) and ( Ψ MSK r , k − 1 , a , Ψ MSK r , k − 1 , b ) to get ( Ψ ISK r , k , a , Ψ ISK r , k , b ) and ( Ψ MSK r , k , a , Ψ MSK r , k , b ). C then computes Ψ CCK r , 0 = Ψ M · ( Ψ Q · Ψ ISK r ), Ψ CCK r , 1 = Ψ M · ( Ψ Q · Ψ SSK K G A + Ψ Q · Ψ MSK r · ( Ψ A + Ψ θ + Ψ B ) ) and uses ( Ψ M, Ψ CCK r , 0 , Ψ CCK r , 1 ) to find ( Ψ M, ( Ψ CCK r , 0 , Ψ CCK r , 1 ), e d k) in L T CMS to get P D = SDF e d k ( E D ). If Ψ Q · Ψ σ = Ψ P K B M C + Ψ Q · ( Ψ M · ( Ψ A + Ψ ρ · Ψ B ) ) holds, output P D and “True”; otherwise, output “invalid”.

Compatible unsigncryption (CUS) leakage query ( k , ( f PKID r , k , h PKID r , k ) / ( f CLID r , k , h CLID r , k ) ): For the k-th Compatible unsigncryption (CUS) query with PKID r or CLID r , C runs the associated procedures, respectively. For PKID r , C sends back Δ f PKID r , k = f PKID r , k ( Ψ S K r , k , a ) and Δ h PKID r , k = h PKID r , k ( Ψ S K r , k , b ). For CLID r , C sends back Δ f CLID r , k = f CLID r , k ( Ψ ISK r , k , a , Ψ MSK r , 0 , a ) and Δ h CLID r , k = h CLID r , k ( Ψ ISK r , k , b , Ψ MSK r , 0 , b ).

Challenge: A conveys a plaintext data pair ( P D 1 , P D 2 ) and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n } to C. C selects a random value λ ∈ { 1, 2 } and refreshes ( Ψ S K B M C , j − 1 , a , Ψ S K B M C , j − 1 , b ) to get ( Ψ S K B M C , j , a , Ψ S K B M C , j , b ). Finally, C generates and sends back BCS = CMS ( P D λ , SDHR, PKID B M C ). In addition, the two conditions presented in Definition 2 must be satisfied.

Guess: If A outputs λ ′ ∈ { 1, 2 } and λ ′ = λ, it means that A wins the LRSC-EIND-CCA game and the associated advantage is A d v ( A ) = | Pb [ λ ′ = λ ] − 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 | ≦ 3 q. For L T 0 , in the Compatible multi-signcryption (CMS) query, Ψ 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 Ψ G E k = Ψ G i · Ψ G j of the Q p f query.

In the following, let A d v ( A I − w o ) be the advantage of A I without requesting any leakage queries and A d v ( A I − w o ) = Pb [ A I − w o ] + | Pb [ λ ′ = λ ] − 1 / 2 |, which are defined and computed as follows.

Pb [ A I − w o ]: 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 ( Ψ G i , Ω G i ) consist of c kinds of variates. Thus, c random values v t ∈ Z p ∗ (for t = 1 , 2 , … , c) are randomly chosen. For any two polynomials Ψ G i and Ψ G j in L T 0 , we compute Ψ G k = Ψ G i − Ψ G j . If Ψ G k ( v 1 , v 2 , … , 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 ( γ = 0) is leaked to adversaries, the probability of Ψ G k ( v 1 , v 2 , … , v c ) = 0 is at most 4 / p. Also, for L T 0 , there are | L T 0 | 2 pairs of ( Ψ G i , Ψ G j ). Therefore, the collision probability on L T 0 is | L T 0 | 2 ( 4 / p ). By similar computation, the collision probability on L T e is | L T e | 2 ( 8 / p ). Hence, we have Pb [ A I − w o ] = | L T 0 | 2 ( 4 / p ) + | L T e | 2 ( 8 / p ) ≦ ( 8 / p ) ( | L T 0 | + | L T e | ) 2 ≦ 128 q 2 / p .

Pb [ λ ′ = λ ]: It represents the probability of λ ′ = λ in the Guess. Since no partial information ( γ = 0) is leaked to adversaries, we have Pb [ λ ′ = λ ] ≦ 1 / 2.

 By the computations above, we have A d v ( A I − w o ) = Pb [ A I − w o ] + | Pb [ λ ′ = λ ] − 1 / 2 | ≦ 128 q 2 / p .

Let A d v ( 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 γ bits of each secret key SSK C A , SSK K G A , S K B M C , ISK r or MSK r . Based on A d v ( A I − w o ), we have A d v ( A I ) ≦ A d v ( A I − w o ) · 2 2 γ ≦ ( 128 q 2 / p ) · 2 2 γ = O ( ( q 2 / p ) · 2 2 γ ) . By Lemma 2, A d v ( A I ) = O ( ( q 2 / p ) · 2 2 γ ) is negligible if γ < log p ( 1 − ϵ ). For the advantage A d v ( A II ) of the adversary A II , we have A d v ( A II ) = O ( ( q 2 / p ) · 2 2 γ ) by similar evaluation.  □

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.

The LRSC-RIND-CCA game is played by a PPT adversary A ( A I or A 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 P D and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n + 1 } to C. C selects a random value λ ∈ { 1 , 2 } and sets SDHR ′ = { [ ( PKID γ , P K γ ) ‖ ( CLID γ , IPK γ , MPK γ ) ] , [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 3 , … , n + 1 }. Finally, C refreshes ( Ψ S K B M C , j − 1 , a , Ψ S K B M C , j − 1 , b ) to get ( Ψ S K B M C , j , a , Ψ S K B M C , j , b ), and generates and sends back BCS = CMS ( P D, SDHR ′ , PKID B M C ). In addition, the two conditions presented in Definition 3 must be satisfied.

Guess: If A outputs λ ′ ∈ { 1, 2 } and λ ′ = λ, it means that A wins the LRSC-RIND-CCA game and the associated advantage is A d v ( A ) = | Pb [ λ ′ = λ ] − 1 / 2 |.

By a similar evaluation in the proof of Theorem 1, we have A d v ( A I ) = O ( ( q 2 / p ) · 2 2 γ ) and A d v ( A II ) = O ( ( q 2 / p ) · 2 2 γ ). By Lemma 2, both A d v ( A I ) and A d v ( A II ) are negligible if γ < log p ( 1 − ϵ ).  □

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.

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.

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 ( PKID B M C ) because A would like to impersonate the SMC to generate a valid broadcast ciphertext set BCS ′ .

Forgery: A forges and sends C a broadcast ciphertext set BCS ′ for a plaintext data P D and SDHR = { [ ( PKID r , P K r ) ‖ ( CLID r , IPK r , MPK r ) ] , r = 1 , 2 , … , n }. For any recipients PKID r and CLID r in SDHR, if they may, respectively, carry out the CUS algorithm to get and validate P D = CUS ( BCS ′ , PKID B M C , ( S K r , k , a , S K r , k , b ) ) and P D = CUS ( BCS ′ , PKID B M C , ( ISK r , k , a , ISK r , k , b ), ( MSK r , k , a , MSK r , k , b ) ), it means that A wins the LRSC-EU-ACMA game.

 In the following, let A d v ( A w o ) be the advantage of A without requesting any leakage queries and A d v ( A w o ) = Pb [ A w o ] + Pb [ Valid-forging ], which are defined and computed as follows.

Pb [ A w o ]: 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 Pb [ A I − w o ] in the proof of Theorem 1, we have Pb [ A w o ] ≦ 128 q 2 / p.

Pb [ Valid-forging ]: It represents the probability of forging a valid tuple BCS ′ = ⟨ ( C 1 , C 2 , … , C n ) , Ω M ′ , E D , Ω σ ′ ⟩ in the Forgery. C gets Ψ M ′ and Ψ σ ′ by converting Ω M ′ and Ω σ ′ in L T 0 . Since BCS ′ is valid, the equality Ψ Q · Ψ σ ′ = Ψ P K B M C + Ψ Q · Ψ M ′ · ( Ψ A + Ψ ρ · Ψ B ) must hold. Thus, we have a multiple-variable polynomial Ψ M P = Ψ Q · Ψ σ ′ − ( Ψ P K B M C + Ψ Q · Ψ M ′ · ( Ψ A + Ψ ρ · Ψ B ) ) = 0. By Lemma 2, since Ψ M P is an element of L T e with the maximal degree 8, we have Pb [ Valid-forging ] = 8 / p.

 By the computations of Pb [ A w o ] and Pb [ Valid-forging ] above, we have A d v ( A w o ) = Pb [ A w o ] + Pb [ Valid-forging ] ≦ 128 q 2 / p + 8 / p = O ( q 2 / p ) .

Let A d v ( 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 γ bits of each secret key SSK C A or S K B M C . Based on A d v ( A w o ), we have A d v ( A ) ≦ A d v ( A w o ) · 2 2 γ = O ( ( q 2 / p ) · 2 2 γ ) . By Lemma 2, A d v ( A ) = O ( ( q 2 / p ) · 2 2 γ ) is negligible if γ < log p ( 1 − ϵ ).  □

 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 I P ( x ) = ∏ r = 1 n ( x − C K r ) + e d k ( mod p ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 + x n , where n denotes the number of recipients and e d k is the encrypting/decrypting key. By the interpolation polynomial I P ( x ), each authorized recipient I D r uses her/his secret key to get e d k = I P ( C K r ) and decrypts the plaintext data P D. 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.

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 O ( n ) O ( 1 ) 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 O ( n ) O ( 1 ) Yes Yes

Computation notations and time ( m s) 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 b p Bilinear pairing mapping ≈ 20.1 ≈ 96.2
T m e Multiplication in G or exponentiation in G e ≈ 6.4 ≈ 30.7

The required computation costs and time ( m s) 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 b p + ( 3 n + 4 ) T m e ≈ 418.6 ≈ 1990.6 ≈ 3955.6
The CUS phase performed on a mobile device 6 T b p + 3 T m e ≈ 669.3 ≈ 669.3 ≈ 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 CLID r is greater than that for a recipient PKID r . Therefore, we consider the required time for multiple recipients CLID r , where r = 1 , 2 , … , 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.

 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.

It is the first LRSC-AMRS scheme suitable for heterogeneous PKCs.

Multiple recipients in the LRSC-AMRS scheme can be initial recipients in the PKI-PKC, or new and upgraded recipients in the CL-PKC.

Since adversaries are allowed to continuously acquire partial information of secret keys for multiple rounds, the LRSC-AMRS scheme possesses unbounded leakage resilience.

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.

 Acknowledgements

The authors would like to appreciate anonymous reviewers for their valuable comments and suggestions on this paper that have resulted in the improvement of quality, completeness and readability. This research was partially supported by National Science and Technology Council, Taiwan, under contract no. NSTC113-2221-E-018-024-MY2.

 References Biham, E., Carmeli, Y., Shamir, A. (2008). Bug attacks. In: Advances in Cryptology – CRYPTO’08, LNCS, Vol. 5157, pp. 221–240. Boneh, D., Franklin, M. (2001). Identity-based encryption from the Weil pairing. In: Advances in Cryptology – CRYPTO’01, LNCS, Vol. 2139, pp. 213–229. Boneh, D., Boyen, X., Goh, E.J. (2005). Hierarchical identity-based encryption with constant size ciphertext. In: Advances in Cryptology – EUROCRYPT’05, LNCS, Vol. 3494, pp. 440–456. Brumley, D., Boneh, D. (2005). Remote timing attacks are practical. Computer Networks, 48(5), 701–716. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A. (2008). Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1), 97–139. Dong, C., Zhang, J. (2024). On the security of multi-receiver certificateless generalized signcryption scheme for WBANs. IEEE Transactions on Dependable and Secure Computing, 21(4), 4302–4303. ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4), 469–472. Galindo, D., Vivek, S. (2013). A practical leakage-resilient signature scheme in the generic group model. In: Selected Areas in Cryptography, SAC’12, LNCS, Vol. 7707, pp. 50–65. Ho, T.-C., Tseng, Y.-M., Huang, S.-S. (2024). Leakage-resilient hybrid signcryption in heterogeneous public-key systems. Informatica, 35(1), 131–154. Kiltz, E., Pietrzak, K. (2010). Leakage resilient Elgamal encryption. In: Advances in Cryptology – ASIACRYPT’10, LNCS, Vol. 6477, pp. 595–612. Kim, T., Jang, J., Jeon, G., Kim, J. (2024). Investigating driver preferences for traffic information using digital signage and road surface holograms. KSCE Journal of Civil Engineering, 28, 1475–1488. Lal, S., Kushwah, P. (2009). Anonymous ID-based signcryption scheme for multiple receivers. IACR Cryptology ePrint Archive, Article-ID 345. Li, H., Wu, C., Pang, L. (2022). Completely anonymous certificateless multi-receiver signcryption scheme with sender traceability. Journal of Information Security and Applications, 71, 103384. Li, X., Gong, Y., Huang, K., Niu, Z. (2023). Over-the-air integrated sensing, communication, and computation in IoT networks. IEEE Wireless Communications, 30(1), 32–38. Miller, V.S. (1985). Use of elliptic curves in cryptography. In: Advances in Cryptology – CRYPTO’85, LNCS, Vol. 218, pp. 417–426. Park, Y., Zhang, Y. (2022). Technology readiness and technology paradox of unmanned convenience store users. Journal of Retailing and Consumer Services, 65, 102523. Pang, L., Gao, L., Li, H., Wang, Y. (2015). Anonymous multi-receiver ID-based signcryption scheme. IET information Security, 9(3), 194–201. Pang, L., Kou, M., Wei, M., Li, H. (2018). Efficient anonymous certificateless multi-receiver signcryption scheme without bilinear pairings. IEEE Access, 6, 78123–78135. Pang, L., Kou, M., Wei, M., Li, H. (2019). Anonymous certificateless multi-receiver signcryption scheme without secure channel. IEEE Access, 7, 84091–84106. Peng, A.-L., Tseng, Y.-M., Huang, S.-S. (2021). An efficient leakage-resilient authenticated key exchange protocol suitable for IoT devices. IEEE Systems Journal, 15(4), 5343–5354. Rivest, R.L., Shamir, A., Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. Shamir, A. (1984). Identity-based cryptosystems and signature schemes. In: Advances in Cryptology – CRYPTO’84, LNCS, Vol. 196, pp. 47–53. Shen, J., Gui, Z., Chen, X., Zhang, J., Xiang, Y. (2022). Lightweight and certificateless multi-receiver secure data transmission protocol for wireless body area networks. IEEE Transactions on Dependable and Secure Computing, 19(3), 1464–1475. Tsai, T.-T., Tseng, Y.-M., Huang, S.-S., Xie, J.-Y., Hung, Y.-H. (2022). Leakage-resilient anonymous multi-recipient signcryption under a continual leakage model. IEEE Access, 10, 104636–104648. Tseng, Y.-M., Huang, S.-S., Tsai, T.-T., Chuang, Y.-H., Hung, Y.-H. (2022). Leakage-resilient revocable certificateless encryption with an outsourced revocation authority. Informatica, 33(1), 151–179. Tseng, Y.-M., Ho, T.-C., Tsai, T.-T., Huang, S.-S. (2024). AHMRE-SCST: lightweight anonymous heterogeneous multi-recipient encryption with seamlessly compatible system transformation for IoT devices. IEEE Internet of Things Journal, 11(17), 28508–28525. Wang, H., Zhang, Y., Qin, B. (2012). Analysis and improvements of two identity based anonymous signcryption schemes for multiple receivers. In: Proceedings of IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, pp. 1057–1062. Wang, Q., He, M., Zheng, X. (2016). Privacy-preserving communication for vehicular with multi-receiver conditionally anonymous ring signcryption. In: Proceedings of 3rd International Conference on Materials Engineering, Manufacturing Technology and Control, pp. 496–501. Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Chou, W.-C. (2018). Leakage-resilient certificateless key encapsulation scheme. Informatica, 29(1), 125–155. Wu, J.-D., Tseng, Y.-M., Huang, S.-S. (2019). An identity-based authenticated key exchange protocol resilient to continuous key leakage. IEEE Systems Journal, 13(4), 3968–3979. Xie, J.-Y., Tseng, Y.-M., Huang, S.-S. (2023). Leakage-resilient anonymous multi-receiver certificateless encryption resistant to side-channel attacks. IEEE Systems Journal, 17(2), 2674–2685. Xiong, H., Qin, Z. (2015). Revocable and scalable certificateless remote authentication protocol with anonymity for wireless body area networks. IEEE Transactions on Information Forensics and Security, 10(7), 1442–1455. Zhang, B., Xu, Q. (2010). An ID-based anonymous signcryption scheme for multiple receivers secure in the standard model. In: Proceedings of Advances in Computer Science and Information Technology, LNCS, Vol. 6059, pp. 15–27.