Othmane Nait-Hamoud
email: o_naithamoud@esi.dz

Tayeb Kenaza

Yacine Challal
email: y_challal@esi.dz

Certificateless Public Key Systems Aggregation: an enabling technique for 5G multi-domain security management and delegation

Keywords:

Network slicing is promising to provide the most cost-effective way of supporting 5G and beyond End-to-End (E2E) services in a multi-domain/mulit-tenant environment. However, security issues are expected to worsen. Indeed, a 5G E2E service could be provided among participation of multiple stakeholders deploying each its security mechanism, which would reduce the flexibility and efficiency that are supposed to characterize 5G services. Also, fierce competition for market share may lead some stakeholders to cheat in the processing of individuals' data and thus infringe on privacy, and undermine the trust between stakeholders. Public Key Cryptography is widely used where the main challenge is how to ensure the authenticity of cryptographic keys. Thus, a trusted third party is the most common way to assure binding a public-private key pair to the identity of the owner, where the word trusted differs from a public key scheme to another. In Public Key Infrastructure, the Certification Authority is trusted for not forging users' certificates. In Identity-Based Public Key Cryptography, the Private Key Generator is trusted for not decrypting entities' ciphertext, let alone forging their signatures. Similarly, in Certificateless Public Key Cryptography, the Key Generator Center (KGC) is trusted for not replacing entities' public keys. In this paper, we propose an aggregation of several Certificateless Public Key systems in a 5G multi-domain/multi-tenant environment to merge them into a virtual cryptosystem without requiring any sort of trustiness in KGCs. The only assumption is that KGCs do not collude through sharing their secret keys. We have put this new cryptosystem into concrete encryption, signature, and authenticated key agreement schemes, and proved their security against a new adversarial model based on new underlying computational and bilinear hardness assumptions about Diffie-Hellman problem in the random oracle model. We believe that this new cryptosystem enables and ensures a secure management of multi-domain/multi-tenant 5G E2E services. even if at most (n-1) KGCs do collude

Introduction

The 2G, 3G and then 4G generations of mobile telecommunication were part of a technological continuity and enhancement. However, the 5G is meant to be a real technological breakthrough and should act as a facilitator of the digitalization of the society, allowing the development of new use cases and services to finally reach a wide range of sectors such as energy, healthcare, media, industry and transport.

The network sharing paradigm was a powerful approach in the past generations of mobile telecommunication that helped Mobile Network Operators (MNO) in a cooperative way to accelerate coverage expansion, reduce deployment time, optimize resource utilization, and reduce Capital Expenditures (CAPEX) and Operational Expenditures (OPEX) costs. Naturally, network sharing has evolved and increasingly gained momentum paving the way to Network Slicing (NS) as a new key concept of on-demand multi-operator/multitenant advanced mobile networks to enable new business opportunities while overcoming the 5G new challenges.

NS is a technology that enables virtual networks created from combined heterogeneous network resources to be programmable over shared infrastructure, whether it be physi-cal, virtual or even both. This is to provide flexibly and efficiently heterogeneous services with a wide spectrum of requirements in terms of communication delays and throughput, network density and capacity, and computational and storage resources. These requirements were broadly grouped by 3GPP standard based on a set of Key Performance Indicators (KPIs) under four main categories: (1) Ultra-reliable and low-latency communications (URLLC), (2) Enhanced mobile broadband (eMBB), (3) Massive machine-type communications (mMTC), and (4) Vehicle-to-Anything (V2X) communications.

From a business point of view, NS gives the opportunity of operational and commercial separation of the mobile network infrastructure from 5G services. Indeed, the new 3GPP standard [START_REF] Gpp | Telecommunication management; Study on management and orchestration of network slicing for next generation network[END_REF] has defined, based on different operational responsibilities, new business roles to third parties other than the MNO that we will refer to as tenants. This will allow them to own, control, supervise and/or manage slices and services independently while respecting a predefined Service Level Agreement (SLA). Figure 1 presents roughly the 5G business models' sphere where the different stakeholders could build and provide, based on business models and performance characteristics, a set of End-to-End (E2E) services and innovative applications to consumers whether ondemand, opportunistically or on permanent basis, and this under the control of National Authorities.

The 5G E2E user services may draw physical resources (5G devices, radio access nodes, edge cloud nodes, core networks nodes and related links) from multiple tenants in a transparent way to the user [START_REF] Vaishnavi | Slicing Across Multiple Operators and Domains[END_REF]. However, with the expansion of 5G technologies enablers and the diversity of services provided in a multi-operator/multi-tenant environment, security issues are expected to worsen particularly among heterogeneous systems [START_REF] Murillo | Inspire-5gplus: intelligent security and pervasive trust for 5g and beyond networks[END_REF]. Thus, in addition to the need of security support of 5G E2E services involving multiple stakeholders, and knowing that risk can rarely be reduced to zero, it is imperative to define liability in case of security incident. This is of paramount importance, both for the end users who are increasingly sensitive to their privacy and even for tenants. This is to build trust and confidence between them, especially when rough competition to gain more market share could lead some operators to cheat and violate individuals' privacy.

Let's consider an example of a 5G E2E service namely the "wholesale connectivity concept" [START_REF] Behrad | 5g-ssaac: Slicespecific authentication and access control in 5g[END_REF]. It is gaining more attention to embed connectivity to devices where connectivity providers (e.g. MNO) sell connectivity to tenants (e.g. IoT connectivity Providers, Virtual MNO, etc.) which in turn provide it to their end-users with the additional services (e.g. traffic filtering, Intrusion detection Systems/Intrusion Prevention Systems) including delegated security mechanisms. Thus, these tenants will be allowed to locally deploy different security mechanisms (e.g. public key systems) according to their needs especially for applications with constrained devices [START_REF] Behrad | A new scalable authentication and access control mechanism for 5g-based iot[END_REF]. However, when a 5G E2E service involves multiple tenants, these security mechanisms would burden cellular systems, especially in the context of massive number of devices, and thus impact communication latency. That is, a 5G E2E service could be provided as a chain of interconnected slices in an ordered sequence [START_REF] Suárez | Managing secure inter-slice communication in 5g network slice chains[END_REF]. When these slices belong to several SPs, this leads to interaction between different public key systems [START_REF] Liu | Mutual heterogeneous signcryption schemes for 5g network slicings[END_REF] in inter-slice communication [START_REF] Sathi | A novel protocol for securing network slice component association and slice isolation in 5g networks[END_REF] under the supervision of the MNO. Figure 2 depicts broadly a 5G E2E service, whether it is an eMBB, an uRLLC, a mMTC, or a V2X communication, which can be provided to a User Equipment (UE). The service results from a configuration of a set of interconnected slices according to a prior SLA established between the involved SPs. As an example, the slices , and in Figure 2 supports the same E2E service, say a V2X-E2E service. They are set up by SP4, cooperatively with SP1 and SP2, according to its needs. Let be the slice provided to a category of User Equipment 1, and and be the slices provided to another category of 2. For the same category of 2, the concrete service may draw different resources, enabling options on the deployment. Thus, slice goes through 2-1, 3 -2 and 3 -4, and slice goes through S 2 -1, 4 -2 and 3 -4. We recall that a MNO, as connectivity provider, may at the same time be a SP competing the others which leads it to cheat for more profits.

For trustworthy and secure 5G networks, each pair of the involved slices should execute an authentication and key agreement protocol before an effective interconnection. Thus, a centralized entity (e.g. Management and Network Orchestrator (MANOr) belonging to the MNO) is required to perform a secure interconnection of slices for enabling a network slice to the end users. However, the flexibility and efficiency of NS made it possible to move toward a smart, au- tonomic and closed-loop architecture where security is important in delivering the intended business outcomes [START_REF] Etsi | Zero-touch network and Service Management (ZSM); Reference Architecture. Group Specification (GS)[END_REF]. Thus, there is a need to decentralize as much as possible the pairing of slices. This is to avoid disruption of the provided services in case of unavailability of the MANOr and to reduce latency in uRLLC scenarios on the one hand, and to avoid the single point of failure risk on the other. Besides, mobility in 5G sliced network has to be managed not only among radio access technologies but also among different slices [START_REF] Sajjad | Interslice mobility management in 5g: Motivations, standard principles, challenges and research directions[END_REF]. This should further complicate sliced communications from a security and even performance perspectives.

Therefore, we seek, through this paper, to define an aggregation mechanism for merging public key systems and for guaranteeing a single one that ensure security even in presence of malicious and active tenants. This is fourfold, i.e. to lighten the system from the known heavy security mechanisms, to secure distributed slices' pairing without requiring a central entity, to ensure inter-slice isolation, and to define liability in case of a security breach. The choice of the type of cryptography system will be discussed in section 1.2.

Public Key Cryptography

Public Key Infrastructure (PKI) is one of the main widelyused cryptosystems which bind public keys contained in certificates with respective identities through a process of registration and issuance of certificates at and by Certificate Authority (CA). Unfortunately, PKI suffers from some problems which can be summarized in (1) trust in CA, (2) burden due to certificate management, and (3) computational cost of certification verification. These problems are considered with more interest when PKI is deployed in resource constraint environments such as Device-to-Device (D2D) communications and IoT applications.

Identity-Based Public Key Cryptography (ID-PKC) [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF] was seen as a solution to the main PKI problem (i.e. dependency on CA) to authenticate an entity public key. ID-PKC cancels this dependency so that an entity's public key is calculated based on its identity. The private key, on the other hand, is generated by a Private Key Generator (PKG) based on a system-wide master key. Unfortunately the dependency on PKG introduces key escrow problem, since PKG may gain access to all entities' private keys and therefore break the confidentiality of their data and forge their signatures.

Certificate-Less Public Key Cryptography (CL-PKC) was introduced in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] as a trade-off between PKI and ID-PKC. CL-PKC now dispenses with the use of certificates and does not suffer from key escrow problem while enjoying both of PKI's and ID-PKC's properties. The user's private key generation in a CL-PKC system is a combination of two partial private keys, one from the user and the other from the Key Generation Center (KGC) which, unlike the PKG in ID-PKC, does not have the users' private keys. Unfortunately, the KGC armed with the master key is able to impersonate any legitimate entity by generating another publicprivate key pair on its behalf, thereby stealing the victim's sensitive information. The CL-PKC authors suppose that the KGC is not carrying out such an attack but at the same time suppose that this KGC could eavesdrop on user's ciphertexts ( --KGC). Formally, there are two types of adversaries against CL-PKC cryptosystems. In Type-I adversary model, the attacker is allowed to replace the user's public key in order to carry out an impersonation attack. In Type-II adversary model, the attacker, given the master key but not allowed to replace the user's public key, tries to mount an impersonation attack as well. In order to strengthen the --KGC model, a new Type-II adversary model ( --KGC) was proposed in [START_REF] Au | Malicious kgc attacks in certificateless cryptography[END_REF] where the KGC is assumed to generate its system-wide public-secret key pair maliciously so that can target a particular victim in addition to eavesdropping activity. In [START_REF] Dent | A survey of certificateless encryption schemes and security models[END_REF], a survey on security models of certificateless encryption schemes is presented.

Toward Public Key Systems aggregation

Security is important in NS to ensure safe and accurate operations that ensure each customer a fair share of resources that are preserved and free from errors. However, the heterogeneity of E2E services which are provided cooperatively by several SPs on the same infrastructure makes security guarantees more complex [START_REF] Olimid | 5g network slicing: A security overview[END_REF] for both end users and even SPs. Security threats of NS are detailed in [START_REF] Porambage | Security in Network Slicing[END_REF], [START_REF] Mathew | Network slicing in 5g and the security concerns[END_REF]. Aside from identifying the challenges related to NS security, little technical research has yet been published on security solutions for the E2E service security. The isolation of slices, privacy protection and management of trust between different stakeholders and slices are also most important. CL-PKC is the most suitable for NS since it ensures authenticity of users in a distributed environment by verifying authenticity of public keys. In this paper, we aim to aggregate Certificateless Public Key Systems into a virtual one to respond the above requirements, and this under a Security SLA (SSLA) and Trust SLA (TSLA) between stakeholders. More explicitly, these stakeholders could be each a KGC with its slices on one hand, and an aggregated KGC among others to create a logical one with common and interconnected slices on another hand. These slices will be able to authenticate each other in a completely secure and distributed manner. In the following we discuss the motivation behind our proposals dealing with the problem of trust within CL-PKC.

The escrow problem in ID-PKC calls into question the trust in the PKG. Equally problematic in CL-PKC, we call into question the trust in the KGC. More naturally, we consider in this paper a nastier KGC that might replace the user's public key. By contrast to CA's same action in PKI, detecting two public keys bind by that KGC to a victim's identity is not obvious, especially in a distributed environment and open networks (e.g., IoT, MTC, D2D, etc.) where the authentication of two entities opportunistically encountered will only be ensured by public keys presented by each. Besides, keys' revocation and renewal mechanisms further complicate the detection of that KGC's cheating activities. Thus, in certificateless cryptosystems, there is no way to ensure public keys authenticity under an active KGC assumption.

Furthermore, since CL-PKC is based on a master key to provide entities with their partial private keys, this would expose all the system security to the risks of single point of failure (SPF), such as compromising that master key through a physical attack or, like a phishing attack, an attacker can obtain users' sensitive information by disguising as a trustworthy KGC. Besides, we now live in an unrivaled and growing hyper connected world that there is a clear awareness of the magnitude of privacy issues that must be rigorously addressed in the different fields [START_REF] Lu | A survey on recent advances in vehicular network security, trust, and privacy[END_REF][START_REF] Kwansah Ansah | Privacy preservation of users in p2p e-payment system*[END_REF][START_REF] Sucasas | A signature scheme with unlinkable-yet-accountable pseudonymity for privacy-preserving crowdsensing[END_REF], where people are increasingly sensitive to their privacy and firm about the handling of their private data [START_REF] Han | A traceable and revocable ciphertextpolicy attribute-based encryption scheme based on privacy protection[END_REF][START_REF] Razak | Data anonymization using pseudonym system to preserve data privacy[END_REF][START_REF] Tsujio | A traceable and pseudonymous p2p information distribution system[END_REF]. Thus, conflicting security requirements and privacy issues gain more attention from researchers in the last years [START_REF] Alkubaisy | Towards detecting and mitigating conflicts for privacy and security requirements[END_REF][START_REF] Alkubaisy | A framework managing conflicts between security and privacy requirements[END_REF][START_REF] Paja | Managing security requirements conflicts in socio-technical systems[END_REF] and should be taken into account when designing a security solution.

Since security is impossible to provide under such a strong assumption with a single KGC, we seek to reuse the CL-PKC paradigm to reconstruct it in an environment supporting multiple KGCs which are not colluding and have a conflict of interest such as 5G E2E services in multi-Domain / multi-tenant environment. This was seen in particular as decentralization of responsibility among stakeholders to address the total mistrust of KGCs, and thus, to reassure users about their privacy. Besides, the proposed reconstruction may enable different CL-PKC systems to be compatible and work cooperatively on the one hand, and to resolve conflicts of security requirements on the other.

Solution Overview

Our solution still makes use of a trusted third party (TTP), which we name the Regulatory Authority (RA). However, the word trusted only concerns the parameters of a CL-PKC system without the system-wide public and master keys as it was traditionally done, it is mainly to overcome the problem of the --KGC. That is, RA will supply KGCs with the required parameters so that they can independently define their traditional CL-PKC systems with their own users on the one hand, and that by aggregating these parameters with others they can cooperatively build a new virtual CL-PKC system with common users on the other. This is possible if they agree on a common system-wide public key which will be the simple addition of their respective public keys, of which the corresponding system-wide master key (result of a simple addition of the KGCs' sub-master keys) will be virtual and implicitly defined. Consequently, this virtual master secret key remains unknown to all KGCs, and could only be disclosed if the involved KGCs disclose their respective sub-master keys, which we does not assume under the conflict of interest assumption. Now, with our aggregation approach, a nastier KGC who impersonates any entity by replacing its public key gains nothing useful. This is because it will not be able to compute the corresponding private key which is bound to the user secret value as well as to the sub-master keys of the rest of KGCs.

It is clear that replacing a public key is in itself an attack that can affect the entire system's security. This attack, known as Denial-of-Decryption (DoD) [START_REF] Liu | Self-generated-certificate public key cryptography and certificateless signature / encryption scheme in the standard model[END_REF], is similar to the so known Denial-of-Service (DoS) attack where the attacker, Carol, replaces Alice's public key by a fake one so that Bob uses Alice's identity and the fake public key to send an encrypted message to Alice. Conse-quently, Alice cannot decrypt the message while Bob is unaware of this. Obviously, all schemes in the literature that share the same key structure and generation procedures as that of Al-Riyami and Paterson [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] fail against such an attack, including ours. This attack is out of the scope of the paper since we are interested to ensure user's privacy against a KGC carrying out an impersonation attack irrespective of the trust a user has to place in the KGCs. Note that our construction (aggregation) could be applied to all schemes in the literature that share the same key structure and generation procedures as that of Al-Riyami and Paterson [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] including those facing the DoD attack [START_REF] Baek | Certificateless public key encryption without pairing[END_REF], [START_REF] Liu | Self-generated-certificate public key cryptography and certificateless signature / encryption scheme in the standard model[END_REF].

An adversarial model against several CL-PKC systems' aggregation

By completely mistrusting the KGC, we define a new type of adversary which we labeled informally --KGC. This adversary roughly fuse both Type-I and Type-II adversary models' capabilities within the virtual CL-PKC system resulting from the aggregation of several CL-PKC systems. In fact, we were faced with a dilemma to formally label our new adversary. That is, since informally the Type-I adversary and the Type-II adversary represent an outsider attacker and a --KGC, respectively, therefore our --KGC could be considered as a stronger form of Type-II adversary which, in addition to the possession of its sub-master secret key, is able to replace a user's public key. However, Type-I adversary is by definition in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] able of replacing a user's public key too while the system-wide master key remains totally inaccessible. Thus, the formal definition of the --KGC is almost the same as that of Type-I adversary except that the --KGC has access to part of the master secret key. Therefore and in order to resolve this dilemma, we labeled such an adversary Type-I + adversary, which in addition to setting up the CL-PKC system parameters maliciously and eavesdropping ciphertexts, binds another public key to an entity's identity to mount an impersonation attack. This means once we remove trust in the KGC the key escrow problem reappears under a new form in all of the previously proposed certificateless schemes.

For simplicity purposes, we consider in our study two not colluding KGCs and one of which is malicious and active. It is worth to note that even if both KGCs are malicious and active, our aggregation remains secure as long as both KGCs are not colluding. Furthermore, since we consider only one of the two KGCs to be malicious and active, this results in a more powerful security model, because if the two KGCs are malicious and active and do not collude, there will be two unsuccessful public key replacement attacks for a victim, which will increase the system misleading behavior.

Similarly to the original work in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] and according to [START_REF] Girault | Self-certified public keys[END_REF], the related primitives to our construction achieve trust level 2 whereas a PKI achieves a higher trust level 3. This is because detecting two valid certificates directly implies the misbehaving CA, whereas in our case as in the case of [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], the detection of two valid public keys bind to a user identity implies both the misbehaving user and KGC. An alternative technique has been proposed in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] which binds the public key of a user to his/her identity so that detecting two valid public keys implies only the misbehaving KGC. Therefore, the biding technique (BT) allows the associated primitives to reach trust level 3. We applied the same technique in section 5.1 so that our primitives also reach trust level 3. However, we emphasize that, unlike the scenario with one KGC as in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], our construction does not allow a malicious and active KGC that replaces a victim's public key with a fake one to compute the corresponding fake private key. This ensures user's privacy irrespective of the trust a user has to place in the KGCs.

We generalized our proposal and the related mathematical definition to malicious and active KGCs in section 5.2. The security of the generalized construction remain secure as long as (n-1) KGCs do not collude. Table 1 resumes comparison between the above PKC systems.

Contribution

In this paper, we construct a new certificateless cryptosystem to support two (or n) KGCs that do not collude at (most n-1) KGC collude, by aggregating their respective CL-PKC system parameters. We concrete our construction by proposing new certificateless encryption scheme (CL-PKE), certificateless signature scheme (CL-PKS) and certificateless authentication and key agreement scheme (CL-AKA). We provide formal proofs regarding the security of the proposed schemes against Type-I adversary, Type-II adversary, and a new and stronger adversary model (Type-I + adversary). The security of our schemes is based on the hardness assumption of new Computational and Bilinear Diffie-Hellman problems in the random oracle model. Finally, we present an alternative of CL-PKC system construction and a generalization to KGCs for these constructions.

Paper Organization

The rest of the paper is structured as follows. In Section 2, we present some preliminaries and review the outline of the original CL-PKE and adversary models. Section 3 presents our CL-PKC system construction and the proposed certificateless schemes (CL-PKE, CL-PKS, CL-AKA). The corresponding security models and the appropriate formal security analysis are presented in Section 4. We present an alternative construction and generalization of the proposed construction techniques in section 5. Finally, Section 6 concludes the paper.

Preliminaries

In this section we present necessary background definitions about bilinear map and computational problems on which rests security of the proposed schemes. Then, we Yes Yes 3

1 "TTP's misbehaving" means: the TTP does the other way round what a user trust the TTP not do.

2 according to definition of trust level in [START_REF] Girault | Self-certified public keys[END_REF].

briefly present the original CL-PKE scheme and its associated adversarial model.

Background Definitions

Throughout the paper, we use notations summarized in Table 2 and define a Bilinear Diffie-Hellman (BDH) parameter generator () as a randomized algorithm which takes as input the security parameter ⩾ 1 and outputs an additive cyclic group 1 , one generator of whom is , a multiplicative cyclic group 2 and a bilinear map ∶ 1 × 1 → 2 with the following properties:

1. Bilinearity: For all , , ∈ 1 and , ∈ ℤ we have ( ,

+ ) = ( , ). ( , ) and ( , ) = ( , ) = ( , ) = ( , ). 2. Non-degeneracy: ( , ) ≠ 1 2 .

Computability: can be computed efficiently.

By selecting uniformly and randomly elements , , of ℤ * , we introduce three computational problems on which relies the proposed schemes' security.

Computational Diffie-Hellman Problem (CDHP

): Given as input < , , >∈ 1 , compute . 2. Computational BDHP (CBDHP): Given as input < , , , >∈ 1 , output ( , ) ∈ 2 . 3. Generalized BDHP (GBDHP): Given as input < , , , >∈ 1 , output a pair < ∈ * 1 , ( , ) ∈ 2 >.
For further details and a comprehensive description of these mathematical problems, we refer to [START_REF] Cheon | Diffie-hellman problems and bilinear maps[END_REF]. From now on, we can define two new underlying problems closely related to the CDHP and the GBDHP which we entitled Specific CDHP (SCDHP), and Specific GBDHP (SGBDHP), respectively. We select uniformly and randomly elements 1 , 2 , , of ℤ * and compute = 1 + 2 .

1. SCDHP: Given as input < , , , 1 >∈ 1 , compute . 2. SGBDHP: Given as input < , , , , 1 >∈ 1 , output a pair < ∈ * 1 , ( , ) ∈ 2 >. Security statement: We assume there is no probabilistic algorithm in 1 able to solve the above hard problems in polynomial time with non-negligible probability.

Here we present a reminder concerning some security notions. Three security models are generally used to prove the security of an asymmetric encryption algorithms within a hypothetical game between a challenger (holding the secret key) and an attacker whose objective is to break security of that algorithm:

1. One-wayness: it is the simple notion of security which requires an attacker to recover entirely the plaintext from a ciphertext. 2. Indistinguishability : is stronger than the one-wayness security model since the attacker's goal is to distinguish which one of two plaintext messages that were chosen by the attacker himself was encrypted (as a challenge) by the challenger. There is two circumstances under which the attacker need to achieve this goal: Hash functions

{0, 1} * → * 1 2 2 → {0, 1} 3 {0, 1} × {0, 1} → ℤ * 4 {0, 1} → {0, 1} 5 {0, 1} * × 2 × 2 → ℤ * 6 {0, 1} * 2 × 3 1 × 2 × 4 1 → {0, 1}  Message space  = {0, 1}  Ciphertext space  = 1 × {0, 1}  Signature space  = 1 × ℤ * User 's identifier ∈ {0, 1} * User 's secret value ∈ ℤ * System parameters < 1 , 2 , , , , , , , ,  > ∈ {1, .., 6} •

Original CL-PKE Scheme and adversarial models

A certificateless cryptosystem is realized in two steps (Figure 3): (1) initialization, registration and keys setup step which is carried out by a KGC and users A and B, and (2) secure communication step supporting the main cryptographic operations, which is carried out between any two users opportunistically encountered without the KGC being present.

Figure 4 describes the original CL-PKE scheme [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. It is based on seven randomized algorithms, while respecting the notation of [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. In their adversarial model, CL-PKE authors define two types of adversaries (Figure 5):

• Type-I Adversary ( ): Such adversary may replace public key with value of its choice while both the KGC's master key and user 's partial private key are inaccessible to him.

• Type-II Adversary ( ): Such adversary is given the KGC's master key , thus knows the user 's partial private keys , but does not know the user private key and may not replace the user public key .

The restrictions made on Type-I and Type-II adversaries are:

1. Both adversaries are restricted to not extract the private key for the challenge identity at any time. 2. Both adversaries are restricted to not query decryption on the challenge message's ciphertext encrypted with the challenge identity's public key. 3.  may not choose the challenge identity if he has already made a partial private key extraction query and replaced the public key for that identity. 4.  may never replace public keys. Compared to the original models in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], Au et al. [START_REF] Au | Malicious kgc attacks in certificateless cryptography[END_REF] adversary models allow the adversary to compromise the target user private key in Type-I model and to replace non-target user's public keys in Type-II model (Figure 6). Thus, the restrictions become as follows:

1. As in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], both adversaries are restricted to not query decryption on the challenge message's ciphertext encrypted with the challenge identity's public key.

2.  is restricted to not extract the private key for the challenge identity at any time. However,  can do it contrary to what was restricted in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. 3.  cannot request the challenge identity's partial private key. 4. As in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF],  cannot replace public keys, but this time this restriction can only be enforced before the challenge ciphertext is received. Semantic security of a certificateless encryption scheme  in terms of indistinguishability under adaptive chosen ciphertext attack (IND-CCA) is defined using the following game between a no polynomially bounded adversary  and a challenger  such as  has a non-negligible advantage Adv() against :

• Setup: given ,  executes Setup algorithm to obtain and the system's master secret key which gives to  in case of a Type-II adversary. In case of Type-I adversary, is kept secret.

• Phase 1: Adversary  adaptively requests a sequence of queries to random oracles to which it is authorized to access (i.e. under the restrictions defined above whether for [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] or [START_REF] Au | Malicious kgc attacks in certificateless cryptography[END_REF] schemes.). Each query may concern security credentials for an entity or a decryption for a ciphertext.

• Challenge Phase:  chooses ℎ as the challenge identity and two messages 0 , 1 which submits to challenger . Then,  selects a bit ∈ {0, 1} at random, encrypts with ℎ 's public key and returns the resulting encryption * to .

• Phase 2:  makes further requests as in Phase 1 but under the same restrictions.

• Guess: Adversary  tries to distinguish the encrypted message by making a guess ′ ∈ {0, 1}, and wins the game if = ′ with advantage Adv()= 2( [ = ′ ] -1 2 ).

New CL-PKC System Construction With Two KGCs

In this section, we present an overview of our certificateless cryptosystem construction with two KGCs which are not colluding and then we formally define our new certificateless cryptosystem and the associated encryption, signature and authentication and key agreement schemes.

Overview

We seek to aggregate two sets of CL-PKC system parameters belonging to two different KGCs into a single one. In doing so, we build a new virtual KGC which we label the "Fogged KGC (F-KGC)" (Figure 7).

The proposed aggregation involves particularly the public keys of the concerned KGCs to obtain by a simple addition of that keys a new public key of the F-KGC whose master key which we label the "Fogged Master Key (FMK)" is indirectly calculated after a double registration process of users to the different KGCs, and a simple addition of their obtained public and private keys. Our approach seems simple albeit, one with far-reaching benefits, particularly regarding full mistrust on TTP. The misty KGC (F-KGC) acts as a virtual vault whose opening requires the possession of both KGCs' secret keys. The FMK does not exist physically and can only be disclosed when the two KGCs agree to exchange their respective master keys or in the case of a physical attack that must be conducted on the two KGCs to get their respective secret keys. This is to eliminate any trust in the KGCs so that we could resist the --KGC, and to eliminate the single point of failure. Furthermore, this approach can be useful to eliminate the conflicting security requirements as mentioned above and also to make possible compatibility between different networks to work cooperatively.

B A New Virtual KGC

CL-PKC

New Certificateless Cryptosystem Construction

Generally, a certificateless cryptosystem is specified by a common set of keys generation algorithms and additional cryptographic algorithms specific for each of encryption, signature and authentication and key agreement schemes. In our certificateless cryptosystem, we consider the same set of algorithms with the appropriate modifications.

To resist the --KGC attack [START_REF] Au | Malicious kgc attacks in certificateless cryptography[END_REF], we highlight the non-necessity to pick out the system-wide public key 0 among the system parameters , and to choose the secret key in the same algorithm as in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. Thus, we entrust system parameters generation (especially the random generator ) without 0 to a new and unique TTP, that we call Regulatory Authority (RA), rather than to the KGCs. For that, we have divided the algorithm of [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] into two algorithms: and whose execution will be formally carried out by RA and KGCs, respectively. It is worth to note that RA is not essential outside the assumption of --KGC since one of the two KGCs can execute both algorithms and thus generate . In other words, RA will provide the different KGCs with the appropriate parameters so that each can choose independently its system-wide public and secret keys.

In the following, we first define our algorithms into two steps: the system initialization step which includes Init and Setup algorithms, and the registration step which includes Set-Partial-Private-Key, Set-Secret-Value, Set-Private-Key, Set-Public-Key. Then, we define the main cryptographic algorithms specific for each of CL-PKE and CL-PKS schemes, namely: Encrypt and Decrypt algorithms in the former, Sign and Verify algorithms in the latter. Our CL-AKA scheme is specified, in addition to the initialization and registration algorithms, by Key Agreement algorithm.

System Initialization

Let RA be a regulation authority which provides different KGCs and users with authentic certificateless parameters describing the message space , ciphertext space  and signature space  additionally to appropriate hash functions 1 , 2 , 3 , 4 , 5 and 6 , a random generator ∈ 1 and a pairing map . By contrast with the original work [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF],

does not contain the public key 0 . Thus, RA executes the following algorithm.

Init: It takes a security parameter and runs a BDH parameter generator (1 ). It outputs initialization parameters =< 1 , 2 , , , , , , ,  >, ( ∈ {1, .., 6}) as a description of cycle groups 1 , 2 of order for a -bit prime , generator of 1 and 2 , pairing , hash functions ( ∈ {1, .., 6}), message space , ciphertext space , signature space , and a bit-length of plaintext.

Let 1 and 2 be two not colluding KGCs and which could have common users. Firstly, using , each KGC selects uniformly and randomly a sub-systemwide master key ∈ ℤ * and calculates their sub-master public keys 0 = ( ∈ {1, 2}). After exchanging their respective sub-system-wide public keys, they calculate the common public key 0 = 0 1 + 0 2 = ( 1 + 2 ) = which represents the system-wide public key of the new aggregated F-KGC whose corresponding FMK remains unknown for both KGCs, and publish the system parameters =< , 0 1 , 0 2 , 0 >. From now on, let be the system parameters of our new certificateless cryptosystem. KGCs execute the following algorithm.

Setup: It takes as input , it outputs subsystem-wide master key (which is kept secret) and subsystem-wide public key 0 ( ∈ {1, 2}) which is authentically published.

Registration

Let user with identifier be a common user to both KGCs. Based

1 =< = , 1 = 0 1 = 1 > 2 =< = , 2 = 0 2 = 2 > =< , 1 + 2 > =< , ( 1 + 2 ) > =< , > .
Set-partial-private-key: Executed by each ( ∈ {1, 2}), it takes as input , sub-systemwide master key and identifier . It outputs 's sub partial private key = , where = 1 ( ) ∈ * 1 , and transmits to through an authentic and secure channel.

Set-private-key: Executed by user , it takes as inputs:

, 's sub partial private keys ( ∈ {1, 2} and 's secret value . Then, it verifies the correctness of these sub partial private keys by checking if the equality

( ∑ 2 =1
, ) = ( , 0 ) holds. If not, it aborts the algorithm. Otherwise, it computes 's sub private keys 1 and 2 ∈ * 1 and then its private key as follows:

1 = 1 = 1 2 = 2 = 2 = 1 + 2 = ( 1 + 2 ) = .

Main Cryptography Algorithms

We present the main cryptography algorithms which are the building blocks for our CL-PKE, CL-PKS and CL-AKA schemes. For our CL-PKE, we present two versions of encryption scheme (BasicCL-PKE and CL-PKE schemes) as was done in the work of Al-Riyami and Paterson [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. That is, authors proposed a pair of encryption schemes (BasicCL-PKE and FullCL-PKE) where BasicCL-PKE was introduced only to serve as a warm-up for their main FullCL-PKE scheme and to be a tool in the proof of the FullCL-PKE scheme's security which was so complicated as stated by the authors themselves. Since our work is based mainly on the one of [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] we did the same so that our BasicCL-PKE is analogous to the BasicCL-PKE scheme of Al-Riyami and Paterson, and our main CL-PKE scheme is in turn analogous to their main FullCL-PKE scheme. The difference between the basic and full versions lies on the adaptation of Fujisaki-Okamoto padding technique [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] which was introduced in the basic version to add chosen ciphertext security to the full version.

Therefore, we present two algorithms BasicEncrypt and BasicDecrypt for our BasicCL-PKE scheme, and two algorithms Encrypt and Decrypt for our main CL-PKE scheme.

After being registered with our certificateless cryptosystem, users and can execute the following algorithms.

BasicEncrypt: User executes this algorithm to encrypt a message then send it to user possessing identity ∈ {0, 1} * and public key =< , >. First, checks 's public key validity by verifying that , ∈ * 1 and that the equality ( , 0 ) = ( , ) holds. If not, it cancels encryption. Second, the sender computes = 1 ( ) ∈ * 1 , and chooses a random ∈ ℤ * . Finally, it computes and sends the ciphertext: =< , >=< , ⊕ 2 ( ( , ) ) > BasicDecrypt: User executes this algorithm to decrypt a ciphertext =< , > using its private key . It computes and outputs a message:

′ = ⊕ 2 ( ( , )).
Encrypt: identical to BasicEncrypt algorithm. However, in the second step, chooses a random ∈ {0, 1} to calculate = 3 ( , ). Finally, it computes and sends the ciphertext:

=< , , > =< , ⊕ 2 ( ( , ) ), ⊕ 4 ( ) > .
Decrypt: User executes this algorithm to decrypt a ciphertext =< , , > using its private key . First, it computes: ′ = ⊕ 2 ( ( , )), then computes and outputs a message: ′ = ⊕ 4 ( ′ ). To verify the correctness of , it sets ′ = 3 ( ′ , ′ ) and test if equation = ′ holds. Sign: User executes this algorithm to send a signed message using its private key . First, It chooses ∈ ℤ * at random, and computes = ( , ) ∈ 2 . Then, sets = 5 ( , , ( , )) ∈ ℤ * , and computes = + ∈ 1 . Finally, it outputs the signature < , >.

Verify: User executes this algorithm to verify a signature < , > on a message from user with identity and public key =< , >. The algorithm checks the validity of , and computes ′ = ( , ) ( , -) .

If the equation = 5 ( , ′ , ( , )) holds, the signature is valid. Otherwise, it aborts.

Key Agreement: Any two registered users opportunistically encountered execute our CL-AKA scheme as follows. Firstly, they exchange their public keys for verification and authentication. Then, they establish a session key to secure their communications. Let users and with their respective pairs of public-private keys < , > and < , >, be the intended participants in the CL-AKA scheme. First, A and B select , ∈ ℤ * at random and calculate = and = , respectively. Then, they exchange their triplets < , , > and < , , >, and verify that the equality ( , 0 ) = ( , ) ( ∈ { , }) holds to check the validity of each others' public key. Finally, they might computes the following possible symmetric keys: Let be the session key as in [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF]:

1 = 1 = 1 = ( , + ) = ( , 0 ) ( + ) 2 = 2 = 2 = ( , 0 ) ( + )
= 6 ( , , , , 5 , 8 , , , 6 , 4 ).

Notice that BasicEncrypt and BasicDecrypt, and Encrypt and Decrypt algorithms are identical to the provably secure encryption and decryption algorithms and in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], respectively, and that Sign and Verify algorithms are also identical to those proved in [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF]. We did not place any reliance on the CL-PKS scheme introduced in [2] because of its insecurity as it was pointed out and proved in [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF]. Also, notice that Key agreement algorithm is identical to the provably secure certificateless two-party AKA protocol [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF].

BasicCL-PKE, CL-PKE, CL-PKS and CL-AKA Schemes

Formally, our BasicCL-PKE, CL-PKE, CL-PKS and CL-AKA schemes are specified by the above six common algo-rithms: Init, Setup, Set-Secret-Value, Partial-Private-Key-Extract, Set-Private-Key, Set-Public-Key, and the above seven additional algorithms: BasicEncrypt and BasicDecrypt for the BasicCL-PKE scheme, Encrypt and Decrypt for CL-PKE scheme, Sign and Verify algorithms for the CL-PKS scheme and finally Key agreement algorithm for CL-AKA scheme.

Security Modeling and Analysis

In this section, we present the security model of the new certificateless cryptosystem, in which we define the capabilities and restrictions of the Type-I + adversary during CL-PKE and CL-PKS games. Finally, we give tight formal security analysis for CL-PKE, CL-PKS and CL-AKA schemes.

Security Models

Firstly, we consider the same security model proposed in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] to show that the new aggregated certificateless cryptosystem is secure against both adversaries Type-I and Type-II considering only the F-KGC with its system-wide public key 0 and FMK . Secondly, we strengthen these adversary models to handle a new adversary model (Type-I + adversary) who can replace entities' public keys while having either the sub-system-wide master key 1 or 2 . Informally, Type-I + simulates a --KGC launching key replacement attack.

We define formally this new adversary for the encryption and signature schemes as follows (Figure 8). CL-PKE and CL-PKS Type-I + Adversary controls either the sub-systemwide master key 1 or 2 , thus controls the user's sub-partial private key 1 or 2 , and is allowed to replace user's public key , and to get access to either the user's sub-private key 1 or 2 . As the CL-PKE and CL-PKS games share the same set of oracles, in the following we define these oracles, and then define the ones specific for each of CL-PKE and CL-PKS games, namely: _ for the former, and _ for the latter. _ _ : Given an identity and public/secret key pair ( * , * ), then the original user public/secret key pair is replaced with ( * , * ). 5.

_ : Given an identity and a ciphertext ,  executes Decrypt algorithm to deliver the message . 6.

_ : Given an identity and a message ,  executes Sign algorithm to deliver the signature σ.

The restrictions made on such a Type-I + adversary are:

1.  may never extract the challenge identity's private key.



may not replace the challenge identity's public key if it had already extracted its partial private key.

In Phase 2 of CL-PKE game, 

may not request a decryption query on the challenge message's ciphertext encrypted with the challenge identity's public key. [START_REF] Alkubaisy | Towards detecting and mitigating conflicts for privacy and security requirements[END_REF]. In CL-PKS game,  cannot make a signature request on input ( ℎ , ℎ ) if ℎ 's public key is changed and ℎ 's partial private key is queried. Now, we present both CL-PKE and CL-PKS games as follows.

CL-PKE Game: Security of our certificateless encryption scheme follows from the following game between a no polynomially bounded adversary  and a challenger  such as  has a non-negligible advantage Adv( ) against  to win the following game:

• Setup: given , the challenger  executes the Init and twice the Setup algorithms to get the resulting system parameters and the two sub-system-wide public keys 0 1 and 0 2 , respectively.  gives to  the parameters , 0 1 , 0 2 and the system-wide public key 0 , such that 0 = 0 1 + 0 2 , in addition to one of the sub-system-wide master keys 1 or 2 .

• Phase 1: Adversary  adaptively requests a sequence of the following queries while respecting the above defined restrictions rules: a partial private key extraction query, a private key extraction query, a public key extraction query, a public key replacement query or a decryption query.

• Challenge Phase: considering the restrictions rules defined above,  chooses ℎ as the challenge identity and two messages 0 , 1 which submits to . Challenger  selects a bit ∈ {0, 1} at random, encrypts with ℎ 's current public key and returns the resulting encryption * to  . • Phase 2:  makes further requests as in Phase 1 but under the restrictions defined above.

• Guess: Finally, adversary  outputs a guess ′ ∈ {0, 1}

and wins the game if = ′ .  's advantage is defined to be Adv( )= 2( [ = ′ ] -1 2 ). CL-PKS Game: Security of our certificateless signature scheme follows from the following game between a no polynomially bounded adversary  and a challenger  such as  has a non-negligible advantage Adv() against  to win the following game:

• Setup: identical to that in CL-PKE game.

• Queries: Adversary  adaptively issues a sequence of requests similarly to those in CL-PKE game, but here it should issue a signature query rather than a decryption query.

• Response: Finally,  outputs a triple ( ℎ , ℎ , σ ℎ ) and wins the game if the signature σ ℎ of the message ℎ under the current ℎ 's public key is correct and the above restrictions are respected.

Security Analysis

The proof of CL-PKE scheme's security is closely modelled on the proof of Theorem 1 in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. Indeed, the proof strategy depends on the certificateless system parameters and the adversary's type. For standard Type-I and Type-II adversaries, we consider only the F-KGC system parameters, particularly the system-wide public key 0 and the FMK obtained from the CL-PKC systems' aggregation. In doing so, we can directly use Theorem 1 in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] to proof that our CL-PKE scheme which follows directly from the employment of the scheme [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] is secure against standard adversarial Type-I and Type-II models. For Type-I + adversary, we need to deal with the possibility that a Type-I + adversary, which knows either secret value 1 or 2 , can extract partial private keys and replace public keys. We adopt the same strategy as in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. First, we reduce our CL-PKE scheme's security to that of another CL-PKE algorithm (Hy-bridPub) in an extended IND-CPA model where an adversary may replace the public key provided by the challenger. To handle decryption queries, we use the same special purpose knowledge extractor algorithm defined in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. Second, we provide a reduction of the security to that of a second CL-PKE algorithm (BasicPub) against similarly an extended One-Way Encryption (OWE) model. From now on we can reduce security to the assumed hardness of the SGBDHP.

The proof of CL-PKS scheme's security is closely modeled on the proof of Theorem 1 in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], and Theorem 2 and Theorem 3 in [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF], but considers the Type-I + adversary capabilities. For Type-I and Type-II adversaries, we consider only the F-KGC system parameters. For Type-I + adversary, we have to handle the possibility that such an adversary, which knows either secret value 1 or 2 , may extract partial private keys as well as replace public keys. We apply the same strategy as in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] and [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF] with the appropriate modification.

The proof of CL-AKA scheme's security against standard adversarial Type-I and Type-II models is modelled on the proof of Theorem 1 and Theorem 2 in [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF]. For the Type-I + adversary, we will look to proof our CL-AKA security against such an adversary in future work. Now we define BasicPub and HybridPub, two public key encryption schemes to utilize them as tools in security proofs for our CL-PKE scheme. We define also the appropriate adversaries for each.

Two Public Key Encryption Schemes

1) BasicPub

It consists of four algorithms:

• Init: It is identical to that of our CL-PKE.

• Setup: It takes as input , picks a random ∈ * 1 and random 1 , 2 and ∈ ℤ * . Sets

0 1 = 1 , 0 2 = 2 , 0 = 0 1 + 0 2 , = , 1 = 0 1 , 2 = 0 2 , = 1 + 2 = ( 1 + 2 ) and = 1 + 2 = ( 1 + 2 ) . It outputs < 1 , 2 , , , , 0 1 , 0 2 , 0 , , 1 , 2 ,
, , 2 > and as a public and private key, respectively. • Encrypt: Considering the public key of our Ba-sicPub, this algorithm is identical to that of BasicPub in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. • Decrypt: Considering the public key of our Ba-sicPub, this algorithm is identical to that of BasicPub in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF].

2) HybridPub

It also consists of four algorithms:

• Init: It is identical to that of our BasicPub.

• Setup: It is identical to that of our BasicPub, except that the ciphertext space is now  = 1 × {0, 1} 2 and the public key is < 1 , 2 , , , , 0 1 , 0 2 , 0 , , 1 , 2 , , , 2 , 3 , 4 >. • Encrypt: Considering the public key of our Hy-bridPub, this algorithm is identical to that of Hybrid-Pub in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. • Decrypt: Considering the public key of our Hy-bridPub, this algorithm is identical to that of Hybrid-Pub in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF].

Corresponding Adversaries

We specify adversaries corresponding to the above encryption schemes having in mind an attacker who can replace users' public keys while having the value either 1 or 2 .

A Type-I + One Way Encryption (OWE) adversary against our BasicPub algorithm is almost identical to the Type-I adversary against BasicPub defined in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], except that the adversary is given the value either 1 or 2 .

A Type-I + IND-CCA adversary against our HybridPub is almost identical to the Type-I IND-CCA adversary defined in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], except that the adversary is playing against our public key encryption scheme and is also given the value either 1 or 2 .

A Type-I + IND-CPA adversary against our HybridPub is identical to that defined above, except that the adversary can not make decryption queries. Lemma 1. Our CL-PKE scheme is semantically IND-CCA secure against standard Type-I and Type-II adversaries in the random oracle model under the CBDHP, and the GB-DHP assumptions, respectively.

Proof. The proof follows directly from Theorem 1 in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] considering of course only the F-KGC system parameters, particularly the system-wide public key 0 = 0 1 + 0 2 and the FMK = 1 + 2 obtained from the CL-PKC systems' aggregation.

Lemma 2. Suppose that ( ∈ {1, .., 4}) are random oracles and that there exists an IND-CCA Type-I + adversary  against our CL-PKE with advantage while running in time t, making queries to and making decryption queries. Then, there exists a Type-I + adversary algorithm  against HybridPub running in time + (( 3 + 4 ) ′ ) and having advantage at least ∕ 1 , where ′ denotes the execution time of the BasicCL-PKE encryption algorithm and

1-⩽ ( 3+ 4)⋅ ( + ( 3 + 4 ) ′ , 2)+ ( + (( 3 + 4 ) ′ ) + 3 -1 + 2 -+1 ), where ( , ′
) is the highest advantage of Type-I + OWE adversary against Ba-sicPub operating in time T and making ′ hash queries to 2 , and ( ) is the highest advantage of any algorithm running in time T to solve GBDHP.

Proof. Suppose that a Type-I + IND-CCA adversary  running in time , making queries to ( ∈ {1, .., 4}) and making decryption queries, has advantage against our CL-PKE scheme. Then we can construct a Type-I + IND-CCA adversary  against HybridPub, while assuming that challenger  for that game is available to .

Adversary  selects an index I uniformly at random where (1⩽I⩽ 1 ) to build a Type-I + IND-CPA adversary against HybridPub. Let ,  0 and  1 be the events that  chooses as the challenge identity ℎ , the oracle _ _ _ is queried on entity , and the oracle _ _ is queried on entity , respectively. If  0 does occur after  1 had already occurred, then adversary  will lose the game. If  does occur then the probability that  wins the game will be dependent on the one of  .

First, challenger  supplies adversary  with a public key which is equal to < 1 , 2 , , , , 0 1 , 0 2 , 0 , , 1 , 2 , , , 2 , 3 , 4 > and either the value 1 or 2 such that 0 1 = 1 , 0 2 = 2 and 0 = 0 1 + 0 2 . Then, adversary  performs with help of  the following IND-CPA attack against the key .  simulates the CL-PKE's Init and Setup algorithms for  by making available =< 1 , 2 , , , , 0 1 , 0 2 , 0 , 1 , 2 , 3 , 4 > and either the value 1 or 2 to  . The random oracles , ( ∈ {1, .., 4}), may be issued by  at any time during its attack, where 1 is controlled by . These are treated as follows:

1 queries:  creates an initially-empty list

′ , ′ 1 , ′ 2 , ′ >.
Decryption Queries: Since  is mounting IND-CPA attack, then  cannot passes the decryption queries to challenger  to reply. Thus,  uses the same knowledge extractor algorithm  [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] to respond decryption queries.

Challenge Phase: Once Phase 1 is complete,  picks ℎ as the challenge identity, provided that  has already queried 1 on ℎ and neither a private key extraction on ℎ nor a public key replacement after a partial private key extraction on that identity has been requested. Then,  chooses two challenge messages 0 , 1 . There are two cases:

1-If ℎ ≠ then  aborts.

2-Otherwise,  passes challenge messages 0 and 1 to challenger .

At this point,  selects a random ∈ {0, 1}, makes use of HybridPub to encrypty under , and responds with the challenge ciphertext ′ =< ′ , ′ , ′ >.  sets * =< -1 ′ , ′ , ′ > as the CL-PKE encryption of for identity under public key < , > which passes in turn to  . Let < ℎ , ℎ > denotes the ℎ 's public key in the challenge phase.

Phase 2: As in Phase 1,  continues to respond to  's requests, while respecting the restrictions rules on  's behaviour.

Guess: Finally,  should make a guess ′ for which will be also the 's guess for . Recall that  is limited by the time and the number of queries to random oracle as well as by the number of decryption queries. If one of these limitations is not respected then  should abort  and output a random guess. We discuss both 's and  's behaviors in this simulation game. We assume that all decryptions made by  are correct. If  does not abort  , then 's replies are evenly and independently distributed as in the real attack. Therefore,  will have the same view as in the real attack and advantage 2( [ = ′ ] -1∕2) ⩾ . Now, given the successful of  in performing all decryptions, we need to calculate the probability that  does not abort the game.  may abort the simulation for one of three reasons:

1. Because  replaced the public key of the entity after had been already extracted the partial private key on that entity. 2. Because  queried a private key extraction on . 3. Or because  's choice of ℎ was different to .

Let  ,  2 and  3 , be the events corresponding to the above three reasons, respectively. We have [ ] = [ 1 | 0 ],  3 = ¬ and  ⇒ ¬ 2 . Since  's choice of the challenge identity is made from amongst the responses for 1 queries of 1 and given that  selects index uniformly at random from the set of 1 indices , then [] = 1∕ 1 . Thus, we have:

[ aborts] = [ ∨  2 ∨  3 ] [ does not abort] = [¬ ∧ ¬ 2 ∧ ] = [¬ |] ⋅ [] = 1 1 ⋅ [¬ 1 | 0 ∧ ] = 1 1 .
The last equality follows from  's restriction to not replace 's public key after had extracted 's partial private key.

From the Lemma 9 in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], the algorithm  may reply successfully to  's decryption queries with probability at least , which is bounded as stated in this lemma. Fi- Proof. Let  be a Type-I + OWE adversary against Ba-sicPub which has advantage , makes 2 queries to random oracle 2 and runs in time . We will construct from  an algorithm  that is able to solve the SGBDHP with help of  . Suppose algorithm  is given < , , , , 2 > as inputs, such that = ( 1 + 2 ) with random choices of 1 and 2 , and that , 1 , , ∈ ℤ * remains unknown to . In order to create the public key < 1 , 2 , , , , 0 1 , 0 2 , 0 , , 0 1 ,

0 2 , , , 2 > for  ,  picks ∈ ℤ * at random, sets 0 = , 0 2 = 2 , 0 1 = 0 -0 2 = 1 , = , = 0 and =
, then gives this public key and 2 to  .  will have the choice to replace the components < , > to < ′ , ′ >.  then verifies if the equation ( ′ , 0 ) = ( ′ , ) holds. If not,  aborts and thus  has lose the game. Otherwise,  computes = , picks ∈ {0, 1} at random and gives =< , > to  .

It is worth to note that the (unknown) private key for the public key

< ′ = ′ , ′ = ′ ( 1 + 2 ) > for a value ′ is ′ ( 1 + 2 )
and thereby the (unknown) decryption of is will have the same view as in a real attack. Now, we define  as the event where the random oracle 2 is queried on ′ during the simulation of ,  as the event where the components < ′ , ′ > are valid, and as the probability that  occurs. Thus, we get

= ⊕ 2 ( ( , ′ ) ( 1 + 2 ) ) = ⊕ 2 ( ′ )
= [( ′ = ) ∧ ] = [( ′ = ) ∧ |] []+ [( ′ = ) ∧ |¬] [¬] ≤ + 1 2 (1 -).
At the end of the simulation, Adversary  will have a view that does not rely on the 's value. This is because 2 has not been queried on input ′ . Thus, we get ≥ -1 2 . As  outputs < ′ , > where is selected from the 2 list at random, then 's success probability is at least ∕ 2 .

Theorem 5. Our CL-PKE scheme is semantically IND-CCA secure against standard Type-I and Type-II adversaries and the new Type-I + adversary in the random oracle model under the CBDHP, the GBDHP, and the SGBDHP assumptions, respectively.

Lemma 6. Our CL-PKS scheme is unforgeable against standard Type-I and Type-II adversaries in the random oracle model under the CDHP assumption.

Proof. Considering the F-KGC system parameters ( 0 and ) obtained from the CL-PKC systems' aggregation, we can directly use Theorem 3 and Theorem 2 in [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF] to proof that our CL-PKS scheme which follows directly from the employment of the CL-PKS scheme [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF] is secure against standard adversarial Type-I and Type-II models, respectively. Lemma 7. Our CL-PKS scheme is unforgeable against standard Type-I + adversary in the random oracle model under the SCDHP assumption.

Proof. Let  be a Type-I + forger that breaks our CL-PKS scheme under chosen message attack. We show how to construct an algorithm  as a SCDH attacker interacting with  to solve the SCDHP. Suppose  is given < , , , 2 > as inputs such that = ( 1 + 2 ) with random choices of 1 and 2 , and that , 1 , ∈ ℤ * remains unknown to .

Firstly,  selects an index I uniformly at random (1⩽I⩽ Theorem 9. In the sense of Theorem 1 in [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF], our CL-AKA scheme is a secure certificateless two-party authentication and key agreement protocol against standard Type-I and Type-II adversaries in the random oracle model under the CDHP and the BDHP assumptions, respectively and has the perfect forward secrecy property in the sense of Theorem 2 in [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF].

Proof. We consider only the F-KGC system parameters, particularly the system-wide public key 0 and the FMK obtained from the CL-PKC systems' aggregation. Thus, we can directly use Theorem 1 and Theorem 2 in [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF] to proof that our CL-AKA scheme which follows directly from the employment of the CL-AKA scheme [START_REF] Zhang | Simulatable certificateless two-party authenticated key agreement protocol[END_REF] is secure against standard adversarial Type-I and Type-II models and has the perfect forward secrecy property, respectively.

Resolving Conflicting Security Requirements

Generally, a conflict between security and privacy requirements arises, for example, when anonymity and traceability are simultaneously required of a unique central authority, where anonymity refers to the incapacity to link an entity's identity in the system to its real identity, which is the exact opposite for traceability. So is authentication versus anonymity, authentication versus unlinkability [START_REF] Bleumer | Encyclopedia of Cryptography and Security[END_REF], etc. In our certificateless cryptosystem, we solved such conflicting security requirements through decentralization of responsibility between several stakeholders to respond to the full mistrust assumption regarding an active TTP.

To project the proposed CL-PKC systems' aggregation in the field, we sketch the following framework as an example. As of May 2018, the General Data Protection Regulation (GDPR) entered into application so that there is now one set of data protection rules for all companies operating in the European Union, and this, wherever they are based. Under the GPDR, stronger rules on data protection mean that people have more control over their sensitive data on one hand, and businesses benefit from a level playing field on another hand. However, even if stakeholders may satisfy these rules, this would go no way towards quenching their thirst into violating individuals' privacy. In other words, it is not yet entirely clear whether and how these rules are applied in an equivalently robust manner in the field. Now with this research, RA can concrete the GDPR's rules in practice. Indeed, RA could be a registration entity which provides user its pseudo-identity and keeps its real identity secret. Thus, the involved KGCs have not access to the 's real identity, hence anonymity is guaranteed. However, this anonymity remains conditional such that we could trace misbehaving users in the system. Traceability is guaranteed cooperatively by RA and KGCs to detect misbehaving entities through their pseudo-identities. Further security mechanisms can be incorporated to our certificateless cryptosystems aggregation so that the KGCs could report security violation to RA if such a violation necessitates to reveal the real identity of a user.

In [START_REF] Hamoud | A new certificateless system construction for multiple key generator centers to secure device-to-device communications[END_REF], a scenario was presented to analyze the construction of our new CL-PKC system and associated schemes, where a foreign cellular network operator and D2D service provider cooperate through a set of D2D domain applications under government supervision. Here, the government supervision can be carried out through RA while each of the cellular network operator and D2D service provider has its KGC. It should be noted that even RA could have its KGC, thereby participate in the aggregation process. Besides, our approach may help find alternative business models, solve pricing issues in D2D communications [START_REF] Tehrani | Device-todevice communication in 5g cellular networks: challenges, solutions, and future directions[END_REF] and make compatible existing CL-PKC systems for eventual cooperation between them.

Another relevant area that may benefit from our approach is the healthcare industry (or healthcare systems), especially in the context of the fifth generation wireless technology for digital cellular networks (5G). Here too, conflicting security requirements are raised acutely in Mobile-Health applications with multiple stakeholders (patients, physicians, employers, insurance companies, pharmaceutical firms, mobile operators and government). Our approach can therefore contribute to built solid healthcare security frameworks as in [START_REF] Yazdinejad | Decentralized authentication of distributed patients in hospital networks using blockchain[END_REF][START_REF] Edemacu | Collaborative ehealth privacy and security: An access control with attribute revocation based on obdd access structure[END_REF][START_REF] Qiu | Secure health data sharing for medical cyber-physical systems for the healthcare 4.0[END_REF][START_REF] Maroc | Cloud services security evaluation for multi-tenants[END_REF].

An Alternative CL-PKC systems' Aggregation Technique and Generalization

In this section we show that our CL-PKC systems' aggregation can be carried out with the same alternative key generation technique proposed in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. Also, we present a generalization of the proposed aggregation techniques to KGCs, where ⩾ 3, rather than just two KGCs.

An Alternative Aggregation Technique

In the original scheme [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF], it was assumed up to a point that the KGC does not replace the users' public keys and issues only one copy of each entity's partial private key to the correct recipient. Consequently, the user public key generation and the user partial private key generation are carried out independently by the user and the KGC, respectively. However, this allows user to create from its partial private key , and different secret values more than one public key. In the interest of ensuring non-repudiation, especially in the CL-PKS scheme, authors proposed a simple technique that binds an entity 's identifier and public key. This is possible if an entity first sets its secret value to calculate its public key =< , >. Then, the KGC calculates = ( | ) rather than = ( ) in the partial private key generation algorithm. By doing so, the related schemes achieve trust level 3 since the detection of two working public keys for a user's identity implies existence of two private keys which are based on two partial private keys binding that identity to the public keys concerned. Thus, it is evident that only the KGC is responsible for generating the two partial private keys.

That will be no different here regarding Type-I + adversary in our system model. That is, even if the pair of publicprivate key is generated to bind an entity's public key to its identity, the scheme in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] still suffers from --KGC's key replacement attack. Whether or not such misbehaviour on the part of the KGC is detected, security is crucial and should be guaranteed. This is because the cheating KGC is able to compute the fake private key corresponding to the fake public key and learn therefore about user's sensitive information.

It should be remembered that our aim is to ensure user's privacy irrespective of the trust a user has to place in the KGC. Thus, our CL-PKC systems' aggregation, too, supports such an alternative technique. However, although a malicious and active KGC out of 1 and 2 (say 1 ) is able to compute a valid fake public key ′ based on attacker's arbitrary value ′ , it is unable to compute the corresponding fake private key ′ . This is because if it computes a fake sub-public key ′ 2 as if it is issued from 2 , the resulting fake public key will be:

′ = ′ 1 + ′ 2 =< ′ , ′ > =< ′ , ′ 1 + ′ 2 >
and the equality ( ′ , 0 ) = ( ′ , ) holds which results in an authentic fake public key ′ . However, since the sub-partial private key 2 is kept secret, 1 is unable to compute the corresponding fake private key ′ even if the authentic sub-private key 2 is disclosed. This is because:

′ = ′ 1 + 2 = ′ 1 + 2 ! = ′ ( 1 + 2 )

Note that this adversary may compute the fake public key

′ without changing the sub-public key ′ 2 which is issued from 2 , as follows:

′ = ′ 1 + 2 =< ′ , ′ > =< ′ , ′ 1 + 2 > =< ′ , ′ 0 1 + 0 2 >
It is clear that the verification of the authenticity of this key fails when checking the equality ( ′ , 0 ) = ( ′ , ) since two random values (i.e. and ′ ) are present in ′ .

In a nutshell, the malicious and active KGC will get nothing useful after carrying out an impersonation attack unlike what it would have gained without aggregation. This is because the partial private key = 1 + 2 is bound to 's secret value , 1 's sub-master secret keys 1 and 2 's sub-master secret keys 2 . According to the terminology of [START_REF] Girault | Self-certified public keys[END_REF], our schemes achieve also trust level 3 comparing to traditional PKI and original CL-PKC schemes [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF]. But here, the trust made on a TTP is roughly reduced to zero, since users do not invest any level of trust in a KGC as they would in [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] or in a CA in traditional PKI. In our proposal, users do not need to trust the two KGCs to actively propagate false public keys, but they need only to trust them not to do so in collusion, and this by exploiting their conflict of interest.

With the binding technique, our aggregation is carried out as follows. When initializing the system (in the setup algorithm), the common system-wide public key will be calculated by both 1 and 2 as equal to 0 = 1 0 1 = 2 0 2 = ( 1 2 ) = . Notice that the corresponding FMK = 1 2 is calculated implicitly and still remains unknown for both KGCs.

Similarly to what was proposed above, user registers with two KGCs. However, should firstly fix its secret value , and then setup and transmit its public key to both KGCs which, in turn, should calculate and transmit, separately, 's sub partial private keys ( 1 = 1 and

=

. The rest of algorithms (i.e. Encrypt, Decrypt, Sign, Verify and Key agreement) remain unchanged. Now, we must lay out the mathematical problems on which security of our schemes rests:

• SCDHP: Given as input < , , , 1 >∈ 1 where = 1 ⋅ 2 and 1 , 2 , ∈ ℤ * are uniformly and randomly chosen, compute . • SGBDHP: Given as input < , , , , 1 >∈ 1 where = 1 ⋅ 2 and 1 , 2 , , ∈ ℤ * are uniformly and randomly chosen, output a pair < ∈ * 1 , ( , ) ∈ 2 >. Assuming that the hash function 1 is a random oracle, our alternative CL-PKC systems' aggregation in place allows us to claim that Theorem 5, Theorem 8 and Theorem 9 still apply for our CL-PKE, CL-PKS and CL-AKA schemes, respectively.

Informally, thanks to our CL-PKC systems' aggregation techniques proposed in this paper, whether = 1 + 2 or = 1 ⋅ 2 , knowledge of a piece of the secret does not allow a cheating KGC to replace a public key for an entity.

Besides, the obtained secret does not exist physically, so that the virtual KGC defined by the aggregation of two KGCs does not suffer from the single point of failure.

CL-PKC systems' Aggregation Generalization

Up to this point, we have only considered two KGCs. Now we generalize the two proposed aggregation techniques (namely AT1 for the basic one (Subsection 3.2) and AT2 for the alternative one (Subsection 5.1) to KGCs, where ⩾ 2. But before that, we must generalize the appropriate mathematical problems (i.e. SCDHP and SGBDHP) for both aggregation techniques as follows:

• SCDHP: Given as input We claim that Theorem 5, Theorem 8 and Theorem 9 still apply for CL-PKE, CL-PKS and CL-AKA schemes, respectively, which result from each CL-PKC systems aggregation's generalization.

Conclusion

NS is a key concept to provide E2E services in the 5G and beyond systems. Security is more complex to ensure when E2E services are provided cooperatively by multiple SPs in a distributed environment, with at least one SP considered malicious and active. Public Key Cryptography is a fundamental security solution in digital world. It underpins various cryptosystems such as PKI, ID-PKC and CL-PKC. These cryptosystems relies on a TTP and are generally only secure against passive adversaries (i.e. TTP) who are limited to eavesdropping communications between users. In this paper, we presented a new construction of a certificateless cryptosystem against a new and a stronger adversarial model that concentrates both Type-I and Type-II adversaries capabilities, named Type-I + adversary. The new construction should support multiple concurrent KGCs which are not colluding. This is to (1) eliminate trust made on KGCs, hence to overcome privacy issues against active KGCs attacks, (2) to allow different CL-PKC systems to be compatible and to work cooperatively, and (3) to resolve the security requirements conflicts. We made concrete this construction by proposing new encryption (CL-PKE), signature (CL-PKS) and authentication and key agreement (CL-AKA) schemes. We showed that these schemes are secure against the new adversary model as well as the two standard adversaries, as long as the new underlying problems closely related to the Computational Diffie-Hellman and Bilinear Diffie-Hellman Problems are hard. This new construction would make a considerable contribution to secure distributed communication systems and can be applied to all schemes in the literature that share the same key structure and generation procedures as that of [START_REF] Al-Riyami | Certificateless public key cryptography[END_REF].

Figure 1 :

 1 Figure 1: 5G Business Models' Sphere and Stakeholders.

Figure 2 :

 2 Figure 2: 5G E2E Services in Multi-Domain Environment

  IND-CPA: which stands for INDistinguishability of Chosen Plaintext Attack, and means that the attacker is allowed to be given the encryption of any message of his/her choice. In this model, several encryption of the same plaintext should result in randomized ciphertexts so that if the attacker encrypt the two plaintexts would not be able to compare those with the received challenge. • IND-CCA: which stand for INDistinguishability of Chosen Ciphertext Attack, and means that the attacker is allowed to be given the decryption of any ciphertext of his/her choice except the challenge. In this model, the ciphertext should be tamper-proof so that if the attacker alter the challenge in a predictable way and then try to get the decryption of this altered challenge will gain nothing useful. It should be noted that IND-CCA model is stronger than IND-CPA model.

  Initialization, registration, and keys setup. CL-AKA and secure communications. (Encrypt-Decrypt and/or Sign-Verify)

Figure 3 :

 3 Figure 3: Main idea of a CL-PKC system.

Figure 4 :

 4 Figure 4: Basic scheme of CL-PKE.

Figure 5 :

 5 Figure 5: Type-I and Type-II Adversary models proposed by Al-Riyami and Paterson. Changed

Figure 6 :

 6 Figure 6: Type-I and Type-II Adversary models proposed by Au et al. Changed

Figure 7 :

 7 Figure 7: Two CL-PKC systems aggregation.

  = 7 = ( , ) . ( , ) = ( , ) . ( , ) 8 = 8 = 8 = ( 0 + ,

Figure 8 :

 8 Figure 8: Type-I + Adversary model.

2 = 2 ) 1 2 = 2 1 = 1 2

 2122 to each other, where = ( | ). Finally, they setup and transmit 's partial private key = to , bearing in mind that it is not necessary any more to keep 1 , 2 , and secrets. This is because .............................. Based on its partial private key, user calculates its private key to be equal to = = 1 2

1 1

 11 < , , , 1 , 2 , ..., -1 >∈ 1 , 2 , ..., , ∈ ℤ * are uniformly and randomly chosen, compute . • SGBDHP: Given as input < , , , , 1 , 2 , ..., -1 >∈ 1 , 2 , ..., , , ∈ ℤ * are uniformly and randomly chosen, output a pair < ∈ * 1 , ( , ) ∈ 2 >. Similarly to what was presented in the two proposed CL-PKC systems' aggregation techniques (i.e. AT1 and AT2), we will aggregate the public keys of KGCs (i.e. 0 1 = 1 ,0 2 = 2 ,..., 0 =) to the common public key 0 of the F-KGC: remains unknown for all KGCs.The 's public key will be: =< , 0 >. As for its partial private key and private key, they will be equal to:

Table 1

 1 Comparison between PKC systems

								The TTP
	Works	PKC Systems	TTP	A user needs only trust:	BT	TTP's misbehaving 1 detection	Trust level 2	is able to the fake compute	SPF
								private key
	[34]	One ID-PKC system	PKG	the PKG not abuse its knowledge of problem). a user's private key in performing eavesdropping attacks (escrow	-	No	1	Yes	Yes
				the CA not to issue new certificate
	-	One PKI	CA	binding a fake and valid public key	-	Yes	3	Yes	Yes
				and the user's identity.
		One		the KGC not to use a fake and valid	No	No	2
	[2]	CL-PKC	KGC	public key bind to the user's identity				Yes	Yes
		system		(impersonation attack).	Yes Yes	3
		Several			No	No	2
	Our	CL-PKC systems'	n KGCs					No	No
		aggregation

the n KGCs not collude in using a fake and valid public key bind to the user's identity. In other words, a user does not need to trust the n KGCs to actively propagate fake public keys even if at most (n-1) KGCs collude.

Table 2

 2 Notations and Definitions.

	Notation Meaning	Definition
		Security parameter	⩾ 1
		Large prime order	-
		Bit-length of plain-texts	≈	2
	1 2	Additive group Multiplicative group	of order
		Pairing map	∶ 1 × 1 → 2
		Random generator	∈ 1
	1

  Executed by user , it takes as inputs and 's secret value . Firstly, it checks that the equality 0 = 0 1 + 0 2 holds. If not, it aborts the algorithm. Otherwise, it calculates 's sub public keys

	on system parameters	(particularly
	KGCs' sub-master public keys 0 1 , 0 2 ), user sets up two pairs of public-private key ( 1 , 1 ) and ( 2 , 2 ) which aggregates into one pair of public-private key ( , ) where
	= give the appropriate algorithms. 1 + 2 and = 1 +	2 . In the following, we
	Set-secret-value: Executed by user , it takes as
	inputs 's identifier	∈ {0, 1} * and	. It outputs
	a random secret value	∈ ℤ * .
	Set-public-key: 1 and 2 , and then the aggregated public key , > as follows:	=<

   passes in turn such queries to  and creates two lists 3 =< σ, , 3, > and 4 =< σ ′ , 4, > for 's replies. Phase 1: We assume in this phase that  has already queried the appropriate random oracle 1 on identity when makes one of the following series of requests on that identity to : Partial Private Key Extraction: There are two cases: 1. If ≠ , then  replies with 0 . 2. If = , then  replies with 2 or 1 . Recall that  is given either 1 or 2 , thereby can make partial private key extraction queries too for himself. . 2. If = and  has already replied a Partial Private Key Extraction query for then  aborts. Otherwise  makes a request to its challenger  to replace the public key components < , 1 , 2 , > in with new values <

	ples < When 	, , , , , queries 1 on	1 ,	1 of tu-1 + 2 . , there are three cases: 2 , > where =
	1-If 2-If from ℤ * , adds the entry < ∈ 1 , then  responds with 1 ( ) = . ∉ at random 1 and = , then  picks , , , ⊥, ,
	0 1 , 0 2 , > to 3-If ∉ dom from ℤ * , adds < 1 and outputs 1 ( ) = 1 and ≠ , then  picks and at ran-. , , , , ,
	0 1 , is worth to note that  can compute the private key for 0 2 , 0 > to 1 and outputs 1 ( ) =	. It
	which is equal to ( 1 + 2 )	=	=	0 .
	2 queries: Adversary  passes any random oracle 2
	query made by 	to  to answer.
	Private Key Extraction: Suppose that	's public key
	has not been replaced. There are two cases:
	1. If ≠ , then  returns	0 .
	2. If = , then  aborts.
	Request for Public Key:  accesses to the list returns < , 1 , 2 , >. Replace Public Key: Suppose that the new public key's 1 and
	components < ′ , ′ 1 cases:	, ′ 2	, ′ > are valid. There are two
	1. If ≠ , then  accesses the list current values ,	1 and replaces the

3 & 4 queries: 1 , 2 , with new values ′ , ′ 1 , ′ 2 , ′

  nally, we can see that can  wins the game against Hybrid-Pub with advantage at least ∕ 1 during ( )+ ⋅ () = + (( 3 + 4 ) ′ ) where ′ is the execution time of the encryption algorithm BasicCL-PKE . Suppose that 3 and 4 are random oracles and that there exists a Type-I + IND-CPA adversary  against HybridPub which makes 4 queries to 4 and has advantage . Then there exists a Type-I + OWE adversary  against Suppose that a Type-I + IND-CPA adversary  running in time and making 4 queries to 4 , has advantage against HybridPub. Then we can construct a Type-I + OWE adversary  against BasicPub, while assuming that a challenger  for that game is available to .  begins by supplying  with a public key < 1 , 2 , , , , 0 1 , 0 2 , 0 , , 1 , 2 , , , 2 > and the value either 1 or 2 . Then in turn,  creates =< 1 , 2 , , , , 0 1 , 0 2 , 0 , , 1 , 2 , , , 2 , 3 , 4 > as a public key for HybridPub which delivers to  in addition to one of the secrets 1 or 2 . We assume that both 3 and 4 are random oracles controlled by . The rest of the proof is almost identical to that of Lemma 3 in[START_REF] Al-Riyami | Certificateless public key cryptography[END_REF] and thus we omitted. Suppose that 2 is a random oracle and that there exists a Type-I + OWE adversary  against BasicPub making 2 queries to 2 and having advantage . Then there exists an algorithm  which is able to solve the SGB-

	Lemma 3. BasicPub running in time O(time( )) with advantage at
	least ∕( 3 + 4 ).
	Proof. Lemma 4. DHP running in time O(time( )) with advantage at least
	2( -1∕2 )∕ 2 .

  , where = ( , ) ∈ 2 denotes the CBDHP's solution. Hence the SGBDHP's solution < ′ , ′ > follows from examining  's choice of public key and 2 queries.  simulates  's 2 queries by maintaining a list 2 of pairs < , 2, >. To respond to an 2 query ,  begins  replies with the corresponding 2, . Otherwise,  picks ∈ {0, 1} randomly and adds < , > to 2 . Finally,  should output a guess ′ for the 's decryption. If 2 = ∅ then  outputs a random pair from 1 × 2 . Otherwise,  selects randomly a pair < , 2, >∈ 2 and outputs the solution < ′ , > to the SGBDHP. It is clear that through 's simulation, 

	by verifying if	=	for some	∈	1 . If it holds,

), where 1 denotes the maximum number of queries to the random oracle 1 . Then,  creates a public key < 1 ,

, ,

, , 0 1 , 0 2 , 0 , , 0 1 , 0 2 , , 1 , 2 > for  while choosing randomly ∈ ℤ * , setting = , = 0 , 0 = , 0 2 = 2 , 0 1 = 0 -0 2 = 1 , then gives this public key and 2 to  . Here 1 and 2 are random oracles that will be controlled by .

 may request the random oracle 1 and 5 during its attack which are treated as follows:

1 queries: Algorithm  creates an empty list

0 , which can be computed by .

5 queries: For each query ( , , ( , )) made by  ,  picks ∈ ℤ * at random and return it to  as reply.

We assume in this phase that  has already queried the appropriate random oracle 1 on identity when makes during the simulation one of the following requests for an entity: public key extraction request, a public key replacement request, a partial private key extraction request, a private key extraction request or a signature request.

 replies to these requests, except the signature one, exactly as it does in the proof of Lemma 2. Note that it can be easily seen that the replies of  to random oracle queries are evenly and independently distributed as in the real attack. The replies to the requests of  are valid, as long as  does not abort (i.e if  requests a replacement of a public key for the entity when  has already replied a Partial Private Key Extraction query for ).  can also make a signature query ( , ( , )) to the signing oracle whose secret key is associated with on any message associated to a public key < , > of its choice. This signature query is replied by  as follows: Pick up ∈ 1 and ∈ ℤ * at random, compute = ( , ) ( , -) , set = 5 ( , , ( , )) and return ( , ) as the requested signature which is identically seen as the one in the real attack.

At the end of the attack,  outputs a forgery ( , ( , ), , ( , )) after had using, as in [START_REF] Huang | On the security of certificateless signature schemes from asiacrypt 2003[END_REF], the forking technique formalized in [START_REF] Pointcheval | Security proofs for signature schemes[END_REF]. If ( ≠ )  aborts the simulation with probability of 1∕ 1 . Otherwise,  replays  with the same random tape but different choice of the hash function 5 to get another forgery ( , ( ′ , ′ ), , ( , )). From these two forgeries and since ( , ) and ( ′ , ′ ) are valid signatures on the message ,  gets

Finally,  can compute the SCDH challenge .

Theorem 8. Our CL-PKS scheme is unforgeable against standard Type-I and Type-II adversaries, and the new Type-I + adversary in the random oracle model under the CDHP and the SCDHP assumptions.