# A Short Server-Aided Certificateless Aggregate Multisignature Scheme in the Standard Model

Authors: Viet Cuong Trinh
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Aggregate signature scheme allows each signer to sign a different message and then all those signatures are aggregated into a single short signature. In contrast, multisignature scheme allows multisigners to jointly sign only one message. Aggregate multisignature scheme is a combination of both aforementioned signature schemes, where signers can choose to generate either a multisignature or an aggregate signature. This combination scheme has many concrete application scenarios such as Bitcoin blockchain, Healthcare, Multicast Acknowledgment Aggregation, and so on. On the other hand, to deal with the problems of expensive certificates in certified public key cryptography and key escrow in identity-based cryptography, the notion ofcertificateless public key cryptography has been introduced by Riyami and Paterson at Asiacrypt’03. In this paper, we propose the first certificateless aggregate multisignature scheme that achieves the constant-size of signature and is secure in the standard model under a generalization of the Diffie-Hellman exponent assumption. In our scheme, however, the signature is generated with the help of the authority.


---

## Body

## 1. Introduction

Certificateless Cryptography.In public key cryptography, a public key is just a random number, to certify that a public key belongs to a specific user we need to provide for this public key a certificate. Public Key Infrastructure (PKI) was introduced for such purpose; however implementing such PKI in the real world requires using a lot of resources since we need to provide, maintain, and revoke a large amount of certificates. Shamir [1] came up with an idea that if a public key is an identity of a specific user (official email address, for example), there is no need to certify this public key; this leads to the introducing of the notion of identity-based cryptography. However, since each identity is mapped to an arbitrary given fixed number, the public key is an arbitrary given fixed number. In traditional public key cryptosystems such as RSA or ElGamal, given such public key, user cannot generate the corresponding secret key. In all identity-based cryptosystems, user’s secret key is in fact generated by a private key generator (PKG) who knows the master key of the system; this leads to the fact that PKG knows all secret keys of users in the system; this problem is so-called key escrow problem. To deal with the problems of providing, maintaining, and revoking a large amount of certificates in traditional PKI and key escrow in identity-based cryptography, the notion ofcertificateless public key cryptography has been introduced by Riyami and Paterson at Asiacrypt’03 [2]. In a certificateless cryptosystem, the user’s full secret key includes two parts: the first part is a partial secret key generated by PKG from master key and user’s identity; the second part is a secret value chosen by user himself/herself. Due to the fact that user’s public key is still associated with user’s identity and the user’s full secret key includes a secret value chosen by user himself/herself, there is no need to use certificate to certify user’s public key and PKG does not know the user’s full secret key.Certificateless signature scheme was first introduced in [2] and then has been deeply studied in [6–15] to name a few. Regarding the certificateless signature schemes secured in the standard model, there are currently two approaches to construct. First, using the Waters’ hash function [8, 9] or Yum-Lee generic transformations [6, 7], the advantage of this approach is that the resulting schemes can be secure under standard assumptions. However, due to using Waters’ hash function or Yum-Lee generic transformations, these schemes suffer relatively large public parameters and heavy computing time. Second, using direct approach [14, 15], which leads to quite efficient resulted schemes (constant-size of both public parameters and signature, as well as efficient computing time); however these schemes are only secure under strong assumptions (generalization of the Diffie-Hellman exponent assumption, GDDHE assumption), although GDDHE assumption introduced by Boneh and Boyen at Eurocrypt’05 [16] now has been accepted widely by researchers [17–22].Aggregate Signature.Aggregate signature was first introduced by Bonehet al. at Eurocrypt’03 [23]. In this scheme, each signer in an aggregating set signs a different message and then all those signatures are aggregated into a single short signature, which is called aggregate signature. As shown in [5, 23–25], aggregate signature can be applied well to several practical applications such as Bitcoin blockchain, Secure BGP protocol (SBGP) [26], Healthcare, and so on. Certificateless aggregate signature was first proposed in [27], since then it has been studied in numerous of papers such as [5, 28–35], to name a few. However, all of these schemes either are insecure [29, 30, 35] or suffer a drawback that the signature size is linear in the number of signers in the aggregating set [5, 28, 31–34]. Moreover, all of these schemes need to use random oracle to prove the security. Very recently, the authors in [5] proposed a new certificateless aggregate scheme with short public parameters and achieving the highest level of security according to the classification given by Huangel al. [13] under a standard assumption. However, their scheme still suffers two drawbacks: the signature size is linear in the number of signers in the aggregating set and their scheme needs to use random oracle to prove the security. To our knowledge, the task of designing a certificateless aggregate signature scheme with short signature size and secured in the standard model is still open.Multisignature.In contrast to aggregate signature, multisignature scheme allows multisigners to jointly sign only one message. This scheme was first introduced in [36], and then it has been the topic of many other works such as [25, 37–43], to name a few. At ACM CCS’01, Micaliel al. [37] first formalized the security model for a multisignature scheme; they also proposed a multisignature scheme based on Schnorr-signature secured in this model. In [25], the authors defined a multisignature scheme with public key aggregation, for which all public keys of signers in the aggregating set are aggregated into a short aggregate public key through a new additional Key Aggregation algorithm. The advantage of this scheme is that the verifier can only take a constant-size of input (multisignature and aggregate public key) to verify the multisignature, which were showed in [25, 43] that this type of scheme can be applied well to the Bitcoin blockchain application. However, the downside of this scheme is that each aggregating set of signers needs to publish in advance its aggregate public key. Very recently, Bonehel al. [43] proposed a new such compact multisignature scheme with public key aggregation; their scheme however is secure in the random oracle model. Regarding the multisignature scheme in the certificateless setting, several schemes were proposed [3, 4, 44, 45]. The authors in [3] addressed the problem of fast verification but they did not give a formal security proof of their schemes. The authors in [4] proposed a certificateless multisignature scheme without using Pairings; they also gave a formal security proof for their scheme under standard assumption. All of these schemes achieve constant-size of signature; however they did not address the problem of public key aggregation and still need to use random oracle to prove the security.


### 1.1. Our Contribution and Organization of the Paper

In this paper, we extend the work in [14] to consider the combination of an aggregate signature scheme and a multisignature scheme, and in the context of certificateless. More precisely, in our server-aided certificateless aggregate multisignature scheme (SCL-AMS for short), an aggregating set of signers can choose to generate either an aggregate signature or a multisignature with the help of private key generator (PKG); for simplicity such signature is called an aggregate multisignature. If the aggregating set of signers contains only one signer, the resulting signature is a usual signature and the signer does not need the help from PKG.More precisely, ourSCL-AMS scheme has following properties:(i)
the first certificateless aggregate multisignature scheme;(ii)
the signature which contains four elements in all cases;(iii)
being secure against strong Type I and strong Type II adversaries (according to the classification given by Huangel al. [13]) in the standard model under GDDHE assumptions;(iv)
server-aided scheme;(v)
support public key aggregation;(vi)
public key size, signing time, and verifying time which depend on the maximum number of signers for one aggregating set, which is fixed at the setup. More details can be found in the Tables1 and 2.Table 1
n ′ is the size of the aggregating set of signers; n≥n′ is fixed at the setup. P denotes pairing computation, exp denotes exponentiation, and H denotes hash operation. Note that only our scheme is described in type 3 Pairings.
Signature Secret-key Public-key Signing Verifying [3] 1G 1G+1p 2G n ′ e x p + n ′ H + 3 n ′ P 3P+ 1H  [4] 1G+ 1p 2p 2G 2 n ′ e x p  +  2 n ′ H (n′+ 3)exp+ 2H  [5] (n′+ 1)G 1G+ 1p 2G 4n′exp+ 3n′H 2n′exp+ 3P (3n′+ 1)H  Ours 3G+ 1G~ 3G+ 1p 3G+ (n+ 3)G~ (2n′+ 9)exp + (2n′+ 1)H (n′+ 1)exp+ 3P+(2n′+ 1)HTable 2
ROM denotes random oracle model, SM denotes standard model, and PKA denotes supporting public key aggregation.
Multi/Aggre non-interactive Security PKA Server-Aid [3] yes/no no not known no no  [4] yes/no no ROM+Strong Type I,II+ECDLP assumption no no no no  [5] no/yes yes ROM+Super Type I,II+CDH problem no no no no  Ours yes/yes no SM+Strong Type I,II+GDDHEassumption yes yesAlthough ourSCL-AMS scheme requires server-aid and is secure in a strong assumption (GDDHE assumption), our scheme might be considered as a partial answer for the question of designing a certificateless aggregate signature scheme which has short signature size and is secure in the standard model. In addition, our scheme is not only certificateless aggregate signature but also certificateless multisignature with public key aggregation. This type of scheme, recently showed in [25, 43], can be applied well to the Bitcoin blockchain application. We also note that the server-aided model is not new; this model has been used in many other contexts. Regarding the context of signature, we can find several other signature schemes in the literature which use the server-aid model [46–49]. Regarding the GDDHE assumption, it is introduced by Boneh and Boyen at Eurocrypt’05 [16] and now has been accepted and used widely by researchers with a lot of papers based on it [50–52].We give in Tables1 and 2 the detailed comparison between our scheme and some latest relevant schemes in the literature.In the Table2, regardingnoninteractive, to generate a multisignature, in [3] the first signer in the aggregating set signs the message and then sends the resulting signature to the second signer, the second signer based on this signature and his/her secret key to generate a new signature and sends this new signature to the third signer, and this process continues to the last signer. That means it needs n′ rounds to generate a multisignature, n′ is the size of the aggregating set. In [4], each signer needs to broadcast a value to (n′-1) other signers and receives (n′-1) values from (n′-1) other signers before generating multisignature as in usualnoninteractive scheme [40–42]. In our scheme, in the first round, PKG relies on the description of the aggregating set and messages to compute four elements and sends them to n′ signers, all signers then based on these values to generate aggregate multisignature as in usualnoninteractive scheme [40–42].Regarding security model, we only consider theselective model where adversary has to declare the identity of target user at the beginning of security game; the challenger thus does not need to guess the identity of target user at the beginning of security game. In scheme [4, 5], the authors considered a more practical model, theadaptive model where adversary does not have to declare the identity of target user at the beginning of security game; however in their security proof, the challenger needs to guess in advance the identity of the target user at the beginning of security game; their schemes therefore lose a factor in the reduction to the corresponding assumptions. We also note that all of these schemes need to use random oracle to prove the security.Paper organization. In the Preliminaries section, we present definition and security model for our SCL-AMS scheme, and then some useful tools for our construction. We next describe our SCL-AMS scheme and its security analysis in Section 3. Section 4 is devoted for the conclusion.


## 1.1. Our Contribution and Organization of the Paper

In this paper, we extend the work in [14] to consider the combination of an aggregate signature scheme and a multisignature scheme, and in the context of certificateless. More precisely, in our server-aided certificateless aggregate multisignature scheme (SCL-AMS for short), an aggregating set of signers can choose to generate either an aggregate signature or a multisignature with the help of private key generator (PKG); for simplicity such signature is called an aggregate multisignature. If the aggregating set of signers contains only one signer, the resulting signature is a usual signature and the signer does not need the help from PKG.More precisely, ourSCL-AMS scheme has following properties:(i)
the first certificateless aggregate multisignature scheme;(ii)
the signature which contains four elements in all cases;(iii)
being secure against strong Type I and strong Type II adversaries (according to the classification given by Huangel al. [13]) in the standard model under GDDHE assumptions;(iv)
server-aided scheme;(v)
support public key aggregation;(vi)
public key size, signing time, and verifying time which depend on the maximum number of signers for one aggregating set, which is fixed at the setup. More details can be found in the Tables1 and 2.Table 1
n ′ is the size of the aggregating set of signers; n≥n′ is fixed at the setup. P denotes pairing computation, exp denotes exponentiation, and H denotes hash operation. Note that only our scheme is described in type 3 Pairings.
Signature Secret-key Public-key Signing Verifying [3] 1G 1G+1p 2G n ′ e x p + n ′ H + 3 n ′ P 3P+ 1H  [4] 1G+ 1p 2p 2G 2 n ′ e x p  +  2 n ′ H (n′+ 3)exp+ 2H  [5] (n′+ 1)G 1G+ 1p 2G 4n′exp+ 3n′H 2n′exp+ 3P (3n′+ 1)H  Ours 3G+ 1G~ 3G+ 1p 3G+ (n+ 3)G~ (2n′+ 9)exp + (2n′+ 1)H (n′+ 1)exp+ 3P+(2n′+ 1)HTable 2
ROM denotes random oracle model, SM denotes standard model, and PKA denotes supporting public key aggregation.
Multi/Aggre non-interactive Security PKA Server-Aid [3] yes/no no not known no no  [4] yes/no no ROM+Strong Type I,II+ECDLP assumption no no no no  [5] no/yes yes ROM+Super Type I,II+CDH problem no no no no  Ours yes/yes no SM+Strong Type I,II+GDDHEassumption yes yesAlthough ourSCL-AMS scheme requires server-aid and is secure in a strong assumption (GDDHE assumption), our scheme might be considered as a partial answer for the question of designing a certificateless aggregate signature scheme which has short signature size and is secure in the standard model. In addition, our scheme is not only certificateless aggregate signature but also certificateless multisignature with public key aggregation. This type of scheme, recently showed in [25, 43], can be applied well to the Bitcoin blockchain application. We also note that the server-aided model is not new; this model has been used in many other contexts. Regarding the context of signature, we can find several other signature schemes in the literature which use the server-aid model [46–49]. Regarding the GDDHE assumption, it is introduced by Boneh and Boyen at Eurocrypt’05 [16] and now has been accepted and used widely by researchers with a lot of papers based on it [50–52].We give in Tables1 and 2 the detailed comparison between our scheme and some latest relevant schemes in the literature.In the Table2, regardingnoninteractive, to generate a multisignature, in [3] the first signer in the aggregating set signs the message and then sends the resulting signature to the second signer, the second signer based on this signature and his/her secret key to generate a new signature and sends this new signature to the third signer, and this process continues to the last signer. That means it needs n′ rounds to generate a multisignature, n′ is the size of the aggregating set. In [4], each signer needs to broadcast a value to (n′-1) other signers and receives (n′-1) values from (n′-1) other signers before generating multisignature as in usualnoninteractive scheme [40–42]. In our scheme, in the first round, PKG relies on the description of the aggregating set and messages to compute four elements and sends them to n′ signers, all signers then based on these values to generate aggregate multisignature as in usualnoninteractive scheme [40–42].Regarding security model, we only consider theselective model where adversary has to declare the identity of target user at the beginning of security game; the challenger thus does not need to guess the identity of target user at the beginning of security game. In scheme [4, 5], the authors considered a more practical model, theadaptive model where adversary does not have to declare the identity of target user at the beginning of security game; however in their security proof, the challenger needs to guess in advance the identity of the target user at the beginning of security game; their schemes therefore lose a factor in the reduction to the corresponding assumptions. We also note that all of these schemes need to use random oracle to prove the security.Paper organization. In the Preliminaries section, we present definition and security model for our SCL-AMS scheme, and then some useful tools for our construction. We next describe our SCL-AMS scheme and its security analysis in Section 3. Section 4 is devoted for the conclusion.


## 2. Preliminaries

In this section, based on security models in [4, 5, 13] we first define the security model for our SCL-AMS scheme; we then give some useful tools that we need to construct our scheme such as Bilinear Groups, Target Collision Resistant Hash Function, and Assumptions.


### 2.1. Server-Aided Certificateless Aggregate Multisignature Scheme

#### 2.1.1. Definition

There are three entities involved in our server-aided certificateless aggregate multisignature scheme:(1)
a designated authority acting as a Private Key GeneratorPKG;(2)
user (or signer) who combines withPKG and all other users in an aggregating set to generate an aggregate multisignature (either an aggregate signature or a multisignature). Note that if the aggregating set of users contains just one user, user relies solely on his/her full secret key (without the help of PKG) to generate the aggregate multisignature. In this case, the aggregate multisignature is exactly the usual user’s signature;(3)
verifier who is able to check the validity of an aggregate multisignature.We also note that, in a certificateless system, a user’s full secret keySKID includes two parts: the first part is a partial secret key PID generated by the PKG from master key and user’s identity; the second part is a secret value xID chosen by user himself/herself.More formally, ourSCL-AMS scheme consists of the following nine probabilistic algorithms.(i)
Setup: it takes as input a security parameter λ; this algorithm generates system parameters param implicitly including the maximum number of users in an aggregating set n and a master secret key msk.(ii)
Partial-Secret-Key-Generation: it takes as input param, msk, and a user’s identity ID; this algorithm generates the partial secret key PID.(iii)
User-Secret-Value-Generation: it takes as input the security parameter λ and a user’s identity ID; this algorithm generates the user’s secret value xID.(iv)
Public-Key-Generation: it takes as input xID; this algorithm generates the user’s public key PKID.(v)
Full-Secret-Key-Generation: it takes as input PID and xID; the algorithm generates the user’s full secret key SKID.(vi)
Aggregation: suppose that the aggregating set of users is S,S≤n. There are two cases: if S contains just one user with identity ID, the algorithm takes as input a message M, a user’s full secret key SKID, and param; it generates a signature σ; note that in this case the algorithm works as a usual signing algorithm.IfS contains more than one user, the algorithm now is run by PKG and all users in S, takes as input messages {Mi}i∈S and the description of S, and outputs an aggregate multisignature σ on messages {Mi}i∈S. Note that the signature is called multisignature as usual if all {Mi}i∈S are the same.(vii)
Aggregation Verification: it takes as input an aggregate multisignature σ, the description of aggregating set of users S, and messages {Mi}i∈S and outputs either 1 indicating that σ is a valid signature or 0 indicating that σ is not a valid signature.


#### 2.1.2. Adversary’s Oracles

We have two types of adversary in ourSCL-AMS scheme, the first one represents a third party adversary (so-called Type I adversary) and the second one represents the malicious PKG (so-called Type II adversary), and those adversary can ask the following oracles:(i)
PartialSK(ID): when adversary requests a partial secret key corresponding to identity ID, he/she should get the user’s partial secret key PID.(ii)
UserSecret(ID): when adversary requests a user’s secret value corresponding to identity ID, he/she should get the user’s secret value xID. Note that if adversary asks both PartialSK and UserSecret oracles on input ID, he/she will get the full secret key of user associated with identity ID.(iii)
RequestPK(ID): when adversary requests a public key corresponding to identity ID, he/she should get the user’s public key PKID.(iv)
ReplacePK(ID,xID′,PKID′): adversary can choose ID and replace the original public key PKID to a new public key PKID′ by making a query (ID,xID′,PKID′) to challenger.(v)
RequestSig({Mi,IDi}i∈S): when adversary requests an aggregate multisignature on messages {Mi}i∈S corresponding to users with identities {IDi}i∈S, he/she should get a valid aggregate multisignature σ corresponding to {Mi,IDi}i∈S. In addition, in case S>1, since in the Aggregation algorithm the aggregate multisignature is generated by PKG and all users in S via public channel; adversary may also get the output of PKG as well as the outputs of some users in S.Informally, a third party adversary (an outsider attacker) cannot know the master key; however he/she can replace any public key with a secret value of his/her choice. To exclude the trivial attack, he/she obviously cannot know the partial secret key of the target user. Regarding maliciousPKG (an insider attacker), this adversary knows the master key; however to exclude the trivial attack he/she cannot know the secret value or replace the public key of the target user.On the other hand, according to the classification given by Huangel al. [13], there are three levels of adversary:(i)
normal adversary: this adversary cannot ask RequestSig({Mi,IDi}i∈S) oracle if at least one public key of a user in S has been replaced;(ii)
strong adversary: this adversary still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;(iii)
super adversary: this adversary is not required to supply the secret value xID′ when asking ReplacePK oracle, and he/she still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;In this paper, we consider thestrong adversary for both type I and type II.


#### 2.1.3. Security Model

We define two selective security games corresponding to two types of adversary, Game1 corresponds to third party adversary (denote A1-strong Type I adversary), and Game 2 corresponds to malicious PKG (denote A2-strong Type II adversary).OurSCL-AMS scheme is secure if it resists both adversaries A1 and A2.Game 1.
The first game is betweenA1 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C keeps msk secret and gives param to A1. A1 declares the target user by sending the target identity IDl to C.
Queries: A 1 may adaptively ask the following oracles with C: PartialSK(ID), UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A1 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
PartialSK(IDl) and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA1 as the success probability that adversary A1 wins the above game.Game 2.
The second game is betweenA2 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C gives both public param and msk to A2. A2 declares the target user by sending the target identity IDl to C.
Queries: A 2 may adaptively ask the following oracles with C: UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A2 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
UserSecret(IDl), ReplacePK(IDl,xID′,PKID′), and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA2 the success probability that adversary A2 wins the above game.Definition 3.
We say that our server-aided certificateless aggregate multisignature scheme is selectively existentially unforgeable against polynomially bounded adversariesA1 and A2 if the success probabilities SuccA1(λ) and SuccA2(λ) are negligible, where λ is the security parameter.


### 2.2. Bilinear Groups

In this section, we recall the definition of bilinear map and three types of Pairings. Letλ is the security parameter, p>2λ, and G, G~, and GT are three finite multiplicative abelian groups of order p. Suppose that g,g~ are generators of G and G~, respectively. Denote e:G×G~→GT as an admissible asymmetric bilinear map, where for all a,b∈Zp(1)
e(ga,g~b)=e(g,g~)ab;(2)
forg≠1G and g~≠1G~, e(g,g~)≠1GT;(3)
e(g,g~) is efficiently computable.The tuple(p,G,G~,GT,g,g~,e) is then called a bilinear map group system and is in(1)
Type 1 Pairings ifG=G~(2)
Type 2 Pairings ifG≠G~ but there is an efficiently computable homomorphism ϕ:G~→G(3)
Type 3 Pairings ifG≠G~ but there is no efficiently computable homomorphism between G~ and GIn [16], the authors introduced the generalization of the Diffie-Hellman exponent assumption in Type 3 Pairings bilinear map group system.AssumegT=e(g,g~)∈GT,s,n∈Zp∗, and P,Q,R∈Fp[X1,…,Xn]s are three s-tuples of n-variate polynomials over Fp. Thus, P, Q, and R are just three lists containing s multivariate polynomials each. We write P=(p1,p2,…,ps), Q=(q1,q2,…,qs)R=(r1,r2,…,rs) and impose that p1=q1=r1=1. For any function h:Fp→Ω and vector (x1,…,xn)∈Fpn, h(P(x1,…,xn)) stands for (h(p1(x1,…,xn)),…, h(ps(x1,…,xn)))∈Ωs. We use a similar notation for the s-tuples Q and R. Let f∈Fp[X1,…,Xn]. It is said that f depends on (P,Q,R), which denotes f∈〈P,Q,R〉, when there exists a linear decomposition(1)f=∑1≤i,j≤sai,j·pi·qj+∑1≤i≤sci·ri,ai,j,ci∈Zp.LetP,Q,R be as above and f∈Fp[X1,…,Xn]. The (P,Q,R,f)-GDDHE problem is defined as follows.Definition 4 (P,Q,f-GDHE [16]).
Given the tupleH(x1,…,xn)=(gPx1,…,xn,g~Qx1,…,xn,gTRx1,…,xn)∈Gs×G~s×GTs compute gTf(x1,…,xn).Definition 5 ((P,Q,R,f)-GDDHE [16]).
GivenH(x1,…,xn)=(gPx1,…,xn,g~Qx1,…,xn,gTRx1,…,xn)∈Gs×G~s×GTs as above and T∈GT decide whether T=gTf(x1,…,xn).


### 2.3. Target Collision Resistant Hash Function

Definition 6.
A target collision resistant hash functionH guarantees that given a random element x which is from the valid domain of H, a PPT adversary A cannot find y≠x such that H(x)=H(y). We let AdvH,ATCR=Pr(x,y)→A(1k):H(x)=H(y),x≠y,x,y∈DH be the advantage of A in successfully finding collisions from a target collision resistant hash function H, where DH is the valid input domain of H; k is the security parameter. If a hash function is chosen from a target collision resistant hash function family, AdvH,ATCR is negligible.In this paper, for simplicity we call such target collision resistant hash function a hash function.


### 2.4. Assumptions

In this section, we recall one assumption and introduce a new assumption which are used to prove the security of ourSCL-AMS scheme. Those assumptions are in the similar style of the PS assumption 1 in [52].Definition 7.
Assumption 1. Let (p,G,G~,GT,g,g~,e) be a bilinear group setting of type 3. Choose u,v⟵$Zp∗, we define the oracle O on input m∈Zp∗ that chooses a random r∈Zp∗ and outputs the tuple g(u+mv)r,gr,g~v/r,g~uv/r.
Given(g,g~,g~u,g~v,gv) and unlimited access to this oracle, no adversary can have nonnegligible success probability to generate a pair (g(u+m∗v)r∗,gr∗), with gr∗≠1G, for a new scalar m∗ not asked to O.Intuitively, when comparing to PS assumption 1 in [52], we set h=gr and the oracle O outputs just two more elements in the group G~ which offers no help for the adversary. It is thus obvious that our Assumption 1 holds and we refer the reader to [52] for details. We also note that this assumption was first introduced in [14].Definition 8.
Assumption 2. Let (p,G,G~,GT,e) be a bilinear group setting of type 3, with g (resp., g~) being a generator of G (resp., G~). Choose x,y,s,n⟵$Zp∗; we define two oracles: the oracle O1 which is on input ID∈Zp∗ outputs the triplet(gx/s+ID, gy/s+ID, g1/s+ID); the oracle O2 which is on input (m,{IDi∈Zp∗}i∈S) for some set S chooses a random r∈Zp∗ and outputs the tuple (g(x+my)r/∏i∈S(s+IDi), gr/∏i∈S(s+IDi), gr, g~y/r).
Given(g,g~,{g~si}i=1,…,n,g~x,g~y,gx,gy) and unlimited access to both oracles O1 and O2, no adversary can have nonnegligible success probability to generate a tuple (g(x+m∗y)r∗/∏i∈S∗(s+IDi), gr∗/∏i∈S∗(s+IDi), gr∗, g~y/r∗), with gr∗≠1G, and there exist at least one IDl,l∈S∗, not asked to O1, and input (m∗,{IDi∈Zp∗}i∈S∗) not asked to O2.For completeness, we prove that our Assumption 2 holds in Bilinear Generic Group in AppendixA.


## 2.1. Server-Aided Certificateless Aggregate Multisignature Scheme

### 2.1.1. Definition

There are three entities involved in our server-aided certificateless aggregate multisignature scheme:(1)
a designated authority acting as a Private Key GeneratorPKG;(2)
user (or signer) who combines withPKG and all other users in an aggregating set to generate an aggregate multisignature (either an aggregate signature or a multisignature). Note that if the aggregating set of users contains just one user, user relies solely on his/her full secret key (without the help of PKG) to generate the aggregate multisignature. In this case, the aggregate multisignature is exactly the usual user’s signature;(3)
verifier who is able to check the validity of an aggregate multisignature.We also note that, in a certificateless system, a user’s full secret keySKID includes two parts: the first part is a partial secret key PID generated by the PKG from master key and user’s identity; the second part is a secret value xID chosen by user himself/herself.More formally, ourSCL-AMS scheme consists of the following nine probabilistic algorithms.(i)
Setup: it takes as input a security parameter λ; this algorithm generates system parameters param implicitly including the maximum number of users in an aggregating set n and a master secret key msk.(ii)
Partial-Secret-Key-Generation: it takes as input param, msk, and a user’s identity ID; this algorithm generates the partial secret key PID.(iii)
User-Secret-Value-Generation: it takes as input the security parameter λ and a user’s identity ID; this algorithm generates the user’s secret value xID.(iv)
Public-Key-Generation: it takes as input xID; this algorithm generates the user’s public key PKID.(v)
Full-Secret-Key-Generation: it takes as input PID and xID; the algorithm generates the user’s full secret key SKID.(vi)
Aggregation: suppose that the aggregating set of users is S,S≤n. There are two cases: if S contains just one user with identity ID, the algorithm takes as input a message M, a user’s full secret key SKID, and param; it generates a signature σ; note that in this case the algorithm works as a usual signing algorithm.IfS contains more than one user, the algorithm now is run by PKG and all users in S, takes as input messages {Mi}i∈S and the description of S, and outputs an aggregate multisignature σ on messages {Mi}i∈S. Note that the signature is called multisignature as usual if all {Mi}i∈S are the same.(vii)
Aggregation Verification: it takes as input an aggregate multisignature σ, the description of aggregating set of users S, and messages {Mi}i∈S and outputs either 1 indicating that σ is a valid signature or 0 indicating that σ is not a valid signature.


### 2.1.2. Adversary’s Oracles

We have two types of adversary in ourSCL-AMS scheme, the first one represents a third party adversary (so-called Type I adversary) and the second one represents the malicious PKG (so-called Type II adversary), and those adversary can ask the following oracles:(i)
PartialSK(ID): when adversary requests a partial secret key corresponding to identity ID, he/she should get the user’s partial secret key PID.(ii)
UserSecret(ID): when adversary requests a user’s secret value corresponding to identity ID, he/she should get the user’s secret value xID. Note that if adversary asks both PartialSK and UserSecret oracles on input ID, he/she will get the full secret key of user associated with identity ID.(iii)
RequestPK(ID): when adversary requests a public key corresponding to identity ID, he/she should get the user’s public key PKID.(iv)
ReplacePK(ID,xID′,PKID′): adversary can choose ID and replace the original public key PKID to a new public key PKID′ by making a query (ID,xID′,PKID′) to challenger.(v)
RequestSig({Mi,IDi}i∈S): when adversary requests an aggregate multisignature on messages {Mi}i∈S corresponding to users with identities {IDi}i∈S, he/she should get a valid aggregate multisignature σ corresponding to {Mi,IDi}i∈S. In addition, in case S>1, since in the Aggregation algorithm the aggregate multisignature is generated by PKG and all users in S via public channel; adversary may also get the output of PKG as well as the outputs of some users in S.Informally, a third party adversary (an outsider attacker) cannot know the master key; however he/she can replace any public key with a secret value of his/her choice. To exclude the trivial attack, he/she obviously cannot know the partial secret key of the target user. Regarding maliciousPKG (an insider attacker), this adversary knows the master key; however to exclude the trivial attack he/she cannot know the secret value or replace the public key of the target user.On the other hand, according to the classification given by Huangel al. [13], there are three levels of adversary:(i)
normal adversary: this adversary cannot ask RequestSig({Mi,IDi}i∈S) oracle if at least one public key of a user in S has been replaced;(ii)
strong adversary: this adversary still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;(iii)
super adversary: this adversary is not required to supply the secret value xID′ when asking ReplacePK oracle, and he/she still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;In this paper, we consider thestrong adversary for both type I and type II.


### 2.1.3. Security Model

We define two selective security games corresponding to two types of adversary, Game1 corresponds to third party adversary (denote A1-strong Type I adversary), and Game 2 corresponds to malicious PKG (denote A2-strong Type II adversary).OurSCL-AMS scheme is secure if it resists both adversaries A1 and A2.Game 1.
The first game is betweenA1 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C keeps msk secret and gives param to A1. A1 declares the target user by sending the target identity IDl to C.
Queries: A 1 may adaptively ask the following oracles with C: PartialSK(ID), UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A1 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
PartialSK(IDl) and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA1 as the success probability that adversary A1 wins the above game.Game 2.
The second game is betweenA2 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C gives both public param and msk to A2. A2 declares the target user by sending the target identity IDl to C.
Queries: A 2 may adaptively ask the following oracles with C: UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A2 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
UserSecret(IDl), ReplacePK(IDl,xID′,PKID′), and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA2 the success probability that adversary A2 wins the above game.Definition 3.
We say that our server-aided certificateless aggregate multisignature scheme is selectively existentially unforgeable against polynomially bounded adversariesA1 and A2 if the success probabilities SuccA1(λ) and SuccA2(λ) are negligible, where λ is the security parameter.


## 2.1.1. Definition

There are three entities involved in our server-aided certificateless aggregate multisignature scheme:(1)
a designated authority acting as a Private Key GeneratorPKG;(2)
user (or signer) who combines withPKG and all other users in an aggregating set to generate an aggregate multisignature (either an aggregate signature or a multisignature). Note that if the aggregating set of users contains just one user, user relies solely on his/her full secret key (without the help of PKG) to generate the aggregate multisignature. In this case, the aggregate multisignature is exactly the usual user’s signature;(3)
verifier who is able to check the validity of an aggregate multisignature.We also note that, in a certificateless system, a user’s full secret keySKID includes two parts: the first part is a partial secret key PID generated by the PKG from master key and user’s identity; the second part is a secret value xID chosen by user himself/herself.More formally, ourSCL-AMS scheme consists of the following nine probabilistic algorithms.(i)
Setup: it takes as input a security parameter λ; this algorithm generates system parameters param implicitly including the maximum number of users in an aggregating set n and a master secret key msk.(ii)
Partial-Secret-Key-Generation: it takes as input param, msk, and a user’s identity ID; this algorithm generates the partial secret key PID.(iii)
User-Secret-Value-Generation: it takes as input the security parameter λ and a user’s identity ID; this algorithm generates the user’s secret value xID.(iv)
Public-Key-Generation: it takes as input xID; this algorithm generates the user’s public key PKID.(v)
Full-Secret-Key-Generation: it takes as input PID and xID; the algorithm generates the user’s full secret key SKID.(vi)
Aggregation: suppose that the aggregating set of users is S,S≤n. There are two cases: if S contains just one user with identity ID, the algorithm takes as input a message M, a user’s full secret key SKID, and param; it generates a signature σ; note that in this case the algorithm works as a usual signing algorithm.IfS contains more than one user, the algorithm now is run by PKG and all users in S, takes as input messages {Mi}i∈S and the description of S, and outputs an aggregate multisignature σ on messages {Mi}i∈S. Note that the signature is called multisignature as usual if all {Mi}i∈S are the same.(vii)
Aggregation Verification: it takes as input an aggregate multisignature σ, the description of aggregating set of users S, and messages {Mi}i∈S and outputs either 1 indicating that σ is a valid signature or 0 indicating that σ is not a valid signature.


## 2.1.2. Adversary’s Oracles

We have two types of adversary in ourSCL-AMS scheme, the first one represents a third party adversary (so-called Type I adversary) and the second one represents the malicious PKG (so-called Type II adversary), and those adversary can ask the following oracles:(i)
PartialSK(ID): when adversary requests a partial secret key corresponding to identity ID, he/she should get the user’s partial secret key PID.(ii)
UserSecret(ID): when adversary requests a user’s secret value corresponding to identity ID, he/she should get the user’s secret value xID. Note that if adversary asks both PartialSK and UserSecret oracles on input ID, he/she will get the full secret key of user associated with identity ID.(iii)
RequestPK(ID): when adversary requests a public key corresponding to identity ID, he/she should get the user’s public key PKID.(iv)
ReplacePK(ID,xID′,PKID′): adversary can choose ID and replace the original public key PKID to a new public key PKID′ by making a query (ID,xID′,PKID′) to challenger.(v)
RequestSig({Mi,IDi}i∈S): when adversary requests an aggregate multisignature on messages {Mi}i∈S corresponding to users with identities {IDi}i∈S, he/she should get a valid aggregate multisignature σ corresponding to {Mi,IDi}i∈S. In addition, in case S>1, since in the Aggregation algorithm the aggregate multisignature is generated by PKG and all users in S via public channel; adversary may also get the output of PKG as well as the outputs of some users in S.Informally, a third party adversary (an outsider attacker) cannot know the master key; however he/she can replace any public key with a secret value of his/her choice. To exclude the trivial attack, he/she obviously cannot know the partial secret key of the target user. Regarding maliciousPKG (an insider attacker), this adversary knows the master key; however to exclude the trivial attack he/she cannot know the secret value or replace the public key of the target user.On the other hand, according to the classification given by Huangel al. [13], there are three levels of adversary:(i)
normal adversary: this adversary cannot ask RequestSig({Mi,IDi}i∈S) oracle if at least one public key of a user in S has been replaced;(ii)
strong adversary: this adversary still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;(iii)
super adversary: this adversary is not required to supply the secret value xID′ when asking ReplacePK oracle, and he/she still can ask RequestSig({Mi,IDi}i∈S) oracle even if all public keys of users in S have been replaced;In this paper, we consider thestrong adversary for both type I and type II.


## 2.1.3. Security Model

We define two selective security games corresponding to two types of adversary, Game1 corresponds to third party adversary (denote A1-strong Type I adversary), and Game 2 corresponds to malicious PKG (denote A2-strong Type II adversary).OurSCL-AMS scheme is secure if it resists both adversaries A1 and A2.Game 1.
The first game is betweenA1 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C keeps msk secret and gives param to A1. A1 declares the target user by sending the target identity IDl to C.
Queries: A 1 may adaptively ask the following oracles with C: PartialSK(ID), UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A1 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
PartialSK(IDl) and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA1 as the success probability that adversary A1 wins the above game.Game 2.
The second game is betweenA2 and the challenger C.
Initialization: C runs the Setup algorithm to generate a master secret key msk and public system parameters param. C gives both public param and msk to A2. A2 declares the target user by sending the target identity IDl to C.
Queries: A 2 may adaptively ask the following oracles with C: UserSecret(ID), RequestPK(ID), ReplacePK(ID,xID′,PKID′), and RequestSig({Mi,IDi}i∈S). Note that S≤n.
Output: Finally, A2 outputs ({Mi∗,IDi}i∈S∗,σ∗), where S∗≤n,l∈S∗, and σ∗ is an aggregate multisignature on messages {Mi∗}i∈S∗. We say that A1 wins the game if the following conditions are verified: (1)
UserSecret(IDl), ReplacePK(IDl,xID′,PKID′), and RequestSig({Mi∗,IDi}i∈S∗) have never been queried.(2)
AggragationVerification which outputs σ∗ is a valid aggregate multisignature on messages {Mi∗}i∈S∗ under public keys corresponding to {IDi}i∈S∗.DenoteSuccA2 the success probability that adversary A2 wins the above game.Definition 3.
We say that our server-aided certificateless aggregate multisignature scheme is selectively existentially unforgeable against polynomially bounded adversariesA1 and A2 if the success probabilities SuccA1(λ) and SuccA2(λ) are negligible, where λ is the security parameter.


## 2.2. Bilinear Groups

In this section, we recall the definition of bilinear map and three types of Pairings. Letλ is the security parameter, p>2λ, and G, G~, and GT are three finite multiplicative abelian groups of order p. Suppose that g,g~ are generators of G and G~, respectively. Denote e:G×G~→GT as an admissible asymmetric bilinear map, where for all a,b∈Zp(1)
e(ga,g~b)=e(g,g~)ab;(2)
forg≠1G and g~≠1G~, e(g,g~)≠1GT;(3)
e(g,g~) is efficiently computable.The tuple(p,G,G~,GT,g,g~,e) is then called a bilinear map group system and is in(1)
Type 1 Pairings ifG=G~(2)
Type 2 Pairings ifG≠G~ but there is an efficiently computable homomorphism ϕ:G~→G(3)
Type 3 Pairings ifG≠G~ but there is no efficiently computable homomorphism between G~ and GIn [16], the authors introduced the generalization of the Diffie-Hellman exponent assumption in Type 3 Pairings bilinear map group system.AssumegT=e(g,g~)∈GT,s,n∈Zp∗, and P,Q,R∈Fp[X1,…,Xn]s are three s-tuples of n-variate polynomials over Fp. Thus, P, Q, and R are just three lists containing s multivariate polynomials each. We write P=(p1,p2,…,ps), Q=(q1,q2,…,qs)R=(r1,r2,…,rs) and impose that p1=q1=r1=1. For any function h:Fp→Ω and vector (x1,…,xn)∈Fpn, h(P(x1,…,xn)) stands for (h(p1(x1,…,xn)),…, h(ps(x1,…,xn)))∈Ωs. We use a similar notation for the s-tuples Q and R. Let f∈Fp[X1,…,Xn]. It is said that f depends on (P,Q,R), which denotes f∈〈P,Q,R〉, when there exists a linear decomposition(1)f=∑1≤i,j≤sai,j·pi·qj+∑1≤i≤sci·ri,ai,j,ci∈Zp.LetP,Q,R be as above and f∈Fp[X1,…,Xn]. The (P,Q,R,f)-GDDHE problem is defined as follows.Definition 4 (P,Q,f-GDHE [16]).
Given the tupleH(x1,…,xn)=(gPx1,…,xn,g~Qx1,…,xn,gTRx1,…,xn)∈Gs×G~s×GTs compute gTf(x1,…,xn).Definition 5 ((P,Q,R,f)-GDDHE [16]).
GivenH(x1,…,xn)=(gPx1,…,xn,g~Qx1,…,xn,gTRx1,…,xn)∈Gs×G~s×GTs as above and T∈GT decide whether T=gTf(x1,…,xn).


## 2.3. Target Collision Resistant Hash Function

Definition 6.
A target collision resistant hash functionH guarantees that given a random element x which is from the valid domain of H, a PPT adversary A cannot find y≠x such that H(x)=H(y). We let AdvH,ATCR=Pr(x,y)→A(1k):H(x)=H(y),x≠y,x,y∈DH be the advantage of A in successfully finding collisions from a target collision resistant hash function H, where DH is the valid input domain of H; k is the security parameter. If a hash function is chosen from a target collision resistant hash function family, AdvH,ATCR is negligible.In this paper, for simplicity we call such target collision resistant hash function a hash function.


## 2.4. Assumptions

In this section, we recall one assumption and introduce a new assumption which are used to prove the security of ourSCL-AMS scheme. Those assumptions are in the similar style of the PS assumption 1 in [52].Definition 7.
Assumption 1. Let (p,G,G~,GT,g,g~,e) be a bilinear group setting of type 3. Choose u,v⟵$Zp∗, we define the oracle O on input m∈Zp∗ that chooses a random r∈Zp∗ and outputs the tuple g(u+mv)r,gr,g~v/r,g~uv/r.
Given(g,g~,g~u,g~v,gv) and unlimited access to this oracle, no adversary can have nonnegligible success probability to generate a pair (g(u+m∗v)r∗,gr∗), with gr∗≠1G, for a new scalar m∗ not asked to O.Intuitively, when comparing to PS assumption 1 in [52], we set h=gr and the oracle O outputs just two more elements in the group G~ which offers no help for the adversary. It is thus obvious that our Assumption 1 holds and we refer the reader to [52] for details. We also note that this assumption was first introduced in [14].Definition 8.
Assumption 2. Let (p,G,G~,GT,e) be a bilinear group setting of type 3, with g (resp., g~) being a generator of G (resp., G~). Choose x,y,s,n⟵$Zp∗; we define two oracles: the oracle O1 which is on input ID∈Zp∗ outputs the triplet(gx/s+ID, gy/s+ID, g1/s+ID); the oracle O2 which is on input (m,{IDi∈Zp∗}i∈S) for some set S chooses a random r∈Zp∗ and outputs the tuple (g(x+my)r/∏i∈S(s+IDi), gr/∏i∈S(s+IDi), gr, g~y/r).
Given(g,g~,{g~si}i=1,…,n,g~x,g~y,gx,gy) and unlimited access to both oracles O1 and O2, no adversary can have nonnegligible success probability to generate a tuple (g(x+m∗y)r∗/∏i∈S∗(s+IDi), gr∗/∏i∈S∗(s+IDi), gr∗, g~y/r∗), with gr∗≠1G, and there exist at least one IDl,l∈S∗, not asked to O1, and input (m∗,{IDi∈Zp∗}i∈S∗) not asked to O2.For completeness, we prove that our Assumption 2 holds in Bilinear Generic Group in AppendixA.


## 3. OurSCL-AMS Scheme

In this section, we first gives the detailed construction of ourSCL-AMS scheme, then in the next section we give the security analysis of our SCL-AMS scheme.


### 3.1. Construction

The construction of ourSCL-AMS scheme is detailed as follows.S e t u p: it takes as input the security parameter λ; the algorithm generates a bilinear map group system (p,G,G~,GT,g,g~,e). Next, it chooses random scalars s,x,y⟵$Zp∗, and n∈Zp∗ is the maximum number of users in an aggregating set, as well as two hash functions H1,H2 where(2)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗Finally, it sets the public parameter(3)param=g,g~,g~sii=1,…,n,X~=g~x,Y~=g~y,X=gx,Y=gy,H1,H2and the master secret keymsk=s.P a r t i a l-Secret-Key-Generation: it takes as input param, msk=s, and the user i’s identity IDi; let IDi=H2(IDi); the algorithm generates a partial secret key (4)PIDi=Pi,1,Pi,2,Pi,3=gx/s+IDi,gy/s+IDi,g1/s+IDifor useri.U s e r-Secret-Value-Generation: it takes as input user i’s identity IDi; the algorithm chooses bi⟵$Zp∗ and sets xIDi=bi as user i’s secret value.P u b l i c-Key-Generation: it takes as input param and xIDi; the algorithm sets PKIDi=g~bi as the public key of user i.F u l l-Secret-Key-Generation: it takes as input xIDi and PIDi; the algorithm outputs SKi=(xIDi,PIDi) as the full secret key of user i.A g g r e g a t i o n: denote S as the aggregating set of users, S≤n. There are two cases, if |S|=1, the algorithm takes as input param, IDi, SKi, and a message Mi,i∈S. The algorithm first chooses r⟵$Zp∗ and computes m=H2(Mi),IDi=H2(IDi) and then outputs signature σ=(σ1,σ2,σ3,σ4), where(5)σ1=Pi,1rPi,2mrPi,3bir=gx+bi+myr/s+IDi,σ2=Pi,3r=gr/s+IDi,σ3=gr,σ4=Y~bi/r=g~biy/rIf|S|>1, the algorithm now is run by PKG and all users in S. More precisely, the algorithm consists of two separate following algorithms: note that {IDi=H2(IDi)}i∈S:(1)
First algorithm:PKG takes as input msk, the description of S,{Mi∈{0,1}∗}i∈S as well as param; note that if all messages {Mi∈{0,1}∗}i∈S are the same, the signature is multisignatures.PKG follows strictly the order of pair (Mi,IDi)i∈S to compute m as follows:(6)m=H1H2Mi,H2IDii∈S,0i=1,…,2n-2SNext, it choosesk⟵$Zp∗ and computes(7)Psig=gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/kPsig are then sent to all users in S via public channel or PKG simply publishes it to the public domain. PKG then is not involved in the second algorithm.(2)
Second algorithm: it takes as inputPsig and runs by all users in S. First, each user i∈S takes as input xIDi=bi,Psig and computes the pair:(8)gbik/∏i∈Ss+IDi,g~biy/kFinally, select one user inS as designated combiner, S-1, other remaining users in S send their above outputs to this designated combiner via public channel, and the aggregate multisignature is then built as follows: designated combiner takes as input (9)Psig,gbik/∏i∈Ss+IDi,g~biy/ki∈Sand choosesr′⟵$Zp∗ and outputs the aggregate multisignature σ=(σ1,σ2,σ3,σ4), where(10)σ1=gx+b+myr/∏i∈Ss+IDi,σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~by/randb=∑i∈Sbi,r=r′·k.Note that the designated combiner computes(11)σ1=gx+myk·r′/∏i∈Ss+IDi·∏i∈Sgbi·k·r′/∏i∈Ss+IDi;σ4=∏i∈Sg~biy/k·r′AggregateVerification: it take as input aggregate multisignature σ=(σ1,σ2,σ3,σ4), the description of aggregating set of users S, messages Mi∈{0,1}∗i∈S, and param, the algorithm computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and(12)PKS=∏i∈SPKIDi=g~b,T=g~∏i∈Ss+IDi,T′=X~·PKS·Y~m·g~=g~x+b+my+1;note that he/she can computeT from {g~si}i=1,…,n in param.Finally, the aggregate multisignature is accepted (output1) if the following equation holds:(13)eσ1·σ2,T·eσ3,σ4=eσ3,T′·eY,PKS⇔eσ1·σ2,T·eσ3,σ4T′=eY,PKSCorrectness. It is easy to show that (14)eσ1·σ2,T·eσ3,σ4=egx+b+myr/∏i∈Ss+IDi·gr/∏i∈Ss+IDi,g~∏i∈Ss+IDi·egr,g~by/r=egx+b+my+1r,g~·eg,g~by=egr,g~x+b+my+1·egy,g~b=eσ3,T′·eY,PKSMultisignature Scheme with Public Key Aggregation. In [25], the authors defined a multisignature scheme with public key aggregation, for which the public keys of users in the aggregating set S are aggregated into a short aggregate public key in advance through an additional Key Aggregation algorithm. The advantage of this scheme is that the verifier can only take a constant-size of input (multisignature and aggregate public key) to verify the multisignature, which were showed in [25, 43] that this type of scheme can be applied well to the Bitcoin blockchain application.It is clear that our scheme is a multisignature scheme with public key aggregation as defined in [25], since we can add a new Key Aggregation algorithm which computes in advance the pair (PKS, T) as an aggregate public key of the aggregating set S. The verifier therefore just needs to take a constant-size of input to verify the validity of the signature. Note that we can use a short length of bits to describe the aggregating set S.Remark 9.
We also note that, in our scheme, for an aggregate signature, we do not need to require that all messages{Mi∈{0,1}∗}i∈S are different.


### 3.2. Efficiency

Regarding the signature size, as in the construction and detailed in Table1, the signature in our SCL-AMS scheme just contains four elements, three in the group G and one in the group G~. If we decide to use NIST’s figures [53], then to achieve 80 bits or 128 bits of security (that means the adversary needs at least 280 or 2128 operations to break the security of our scheme), each element in the group G is about 160 bits or 256 bits and in the group G~ is about 1024 bits or 3072 bits. This leads to the fact that the signature size of our scheme is 1504 bits or 3840 bits corresponding to the security parameter 80 bits or 128 bits, respectively.Similarly, the user’s full secret key size of our scheme is 640 bits or 1024 bits corresponding to the security parameter 80 bits or 128 bits, respectively.Regarding the signing phase, there are two cases:(1)
S = 1, the signing phase requires five exponentiations in G, one exponentiation in G~, and two hash operations.(2)
S>1, the signing phase requires n′+7 exponentiations in G, n′+2 exponentiations in G~, and 2n′+1 hash operations, where n′ is the size of the aggregating set of signers.Regarding the verification phase, there are also two cases:(1)
|S| = 1, the verification phase requires two exponentiations in G~, three Pairings, and two hash operations.(2)
|S|>1, the verification phase requires n′+1 exponentiations in G~, three Pairings, and 2n′+1 hash operations, where n′ is the size of the aggregating set of signers.Overall, for both storage and computational complexity, our scheme can meet the requirements for a lightweight device, that means our scheme is suitable for resource-constrained applications such as Bitcoin blockchain, Healthcare, Multicast Acknowledgment Aggregation, vehicular ad hoc networks, wireless sensor networks, Internet of Things, and so on.


### 3.3. Security

We give in this section two theorems which show that ourSCL-AMS scheme is secure.


#### 3.3.1. Secure against Strong Type I Adversary

We first prove that ourSCL-AMS scheme is secure against strong Type I adversary.Theorem 10.
If there exists a strong Type I adversaryA1 defined in Game 1 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 2 with the same probability ε.Proof.
Suppose thatC is an adversary against our Assumption 2; we let C act as a challenger in Game 1 (see Section 2.1.3), that means C simulates A1 and then uses the output of A1 to break the security of the Assumption 2.
At the beginning,C has an instance of Assumption 2: (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy), x,y,s,n∈Zp∗ as well as the right to access two oracles O1 and O2. Note that, for oracle O1, on input ID∈Zp∗, output the triplet (gx/s+ID, gy/s+ID, g1/s+ID). For oracle O2, on input (m,{IDi∈Zp∗}i∈S), choose a random r∈Zp and output (g(x+my)r/∏i∈S(s+IDi), gr/∏i∈S(s+IDi), gr, g~y/r).
Note thatC does not know the values s, x, and y.
To simulateA1, C first receives from A1 the target identity IDl for which he/she intends to attack.
C chooses two hash functions H1,H2 where(15)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A1 as public parameters.
To simulateA1, C must manage to answer oracles as follows.
P a r t i a l S K ( I D i ). C simply requests oracle O1 on input IDi and directly forwards the result to A1. Note that, following Game 1 (see Section 2.1.3), A1 cannot make PartialSK(IDi) query on i=l.
R e q u e s t P K ( I D i ). C chooses bi⟵$Zp∗ and gives PKIDi=g~bi to A1.
U s e r S e c r e t ( I D i ). C first checks whether the RequestPK(IDi) has been queried before; if it is not the case C first make this query on IDi itself, using the above descriptions. In both cases, C knows xIDi; thus C gives xIDi to A1.
R e p l a c e P K ( I D i , x I D i ′ , P K D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKDi′=g~xIDi′.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S, then C requests oracle O2 on input (m,{IDi}i∈S) to get the tuple:(16)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
SinceC knows {xIDi=bi}i∈S (even if PKIDi has been replaced), he/she can easily compute the aggregate multisignature σ as the Aggregation algorithm and returns σ to A1.
We also note here that, in ourAggregation algorithm, the output of PKG and the outputs of users who are not designated combiner are sent via public channel (or made public), that means A1 can request to know these outputs.
Note that the output ofPKG is(17)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/k
and the output of each user inS is(18)gbik/∏i∈Ss+IDi,g~biy/k
for somek∈Zp∗. However, since C knows (19)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
and all{xIDi=bi}i∈S, C can easily answer A1 by choosing r′⟵$Zp∗ and implicitly sets k=r′·r.
Finally,A1 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(20)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, m∗ is computed as in Aggregation algorithm, and C knows all {xIDi=bi}i∈S∗; it is easy for C to recover the tuple(21)T=gx+m∗yr∗/∏i∈S∗s+IDi,gr∗/∏i∈S∗s+IDi,gr∗,g~y/r∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, (m∗,{IDi}i∈S∗) has never been asked to O2 and IDl also has never been asked to O1. This leads to the fact that T is a valid tuple to break the security of the Assumption 2.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA1 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 2 with the same success probability ε, which concludes our proof.


#### 3.3.2. Secure against Strong Type II Adversary

In this section, we prove that ourSCL-AMS scheme is secure against strong Type II adversary.Theorem 11.
If there exists an adversaryA2 defined in Game 2 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 1 with the same probability ε.Proof.
Suppose thatC is an adversary against Assumption 1; we let C act as a challenger in Game 2 (see Section 2.1.3), that means C simulates A2 and then uses the output of A2 to break the security of the Assumption 1.
At the beginning,C has the instance of assumption: (g,g~,g~u,g~v,gv) as well as the right to access oracle O. Note that for oracle O, on input m∈Zp∗, output the tuple (g(u+mv)r, gr, ,g~v/r,g~uv/r).
Note thatC does not know the values u and v.
To simulateA2, C first receives from A2 the target identity IDl for which he/she intends to attack. C chooses x,s,n⟵$Zp∗ and two hash functions H1,H2 where(22)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗Next, C implicitly sets y=v and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A2 as public parameters.
To simulateA2, C must manage to answer oracles as follows.
R e q u e s t P K ( I D i ). If i≠l, C chooses xIDi=bi⟵$Zp∗ and returns PKIDi=g~bi to A2. If i=l, C implicitly sets bi=u and returns PKIDi=g~u to A2. Note that, in this case, C does not know xIDi.
U s e r S e c r e t ( I D i ). C checks whether RequestPK(IDi) has been queried before, if it is not the case C first makes this query on IDi itself, using the above description. In both cases, C knows xIDi and return xIDi to A2. Note that follow the definition of security model, A2 cannot make query on the case i=l.
R e p l a c e P K ( I D i , x I D i ′ , P K I D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKIDi′=g~xIDi′. Note that, following the definition of security model, A2 cannot make query on the case i=l.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S.
There are two cases, ifl∉S then C knows all information; thus he/she chooses r⟵$Zp∗ and easily computes the aggregate multisignature σ=(σ1,σ2,σ3,σ4), where(23)σ1=gx+b+myr/∏i∈Ss+IDi,σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~by/rand b=∑i∈Sbi. Finally, C returns σ to A2.
In casel∈S, C does not knows bl; that means C cannot know b; he/she therefore cannot compute σ1,σ4. In this case, C requests oracle O on input m to receive the tuple (note that bl=u,y=v):(24)gu+mvr,gr,g~v/r,g~uv/r=gbl+myr,gr,g~y/r,g~bly/rSince C knows {xIDi=bi}i∈Si≠l (even if corresponding public keys have been replaced) and x,s, he/she can easily compute(25)σ1=gx+bl+myr/∏i∈Ss+IDi·gr·b′/∏i∈Ss+IDi=gx+b+myr/∏i∈Ss+IDiand(26)σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~bly/r·g~b′y/r=g~by/rwhere b′=∑i∈Si≠lbi. Finally, C returns σ to A2.
We also note here that, in ourAggregation algorithm, PKG only runs the first algorithm and does not participate in the second algorithm; that means A2 knows the output of PKG, which is (27)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/kfor some k∈Zp∗. On the other hand, since in Aggregation algorithm, users who are not designated combiner send their outputs to designated combiner via public channel, that means A2 can know these outputs, which are S-1 pairs:(28)gbik/∏i∈Ss+IDi,g~biy/kTo answer A2, C first implicitly sets user with identity IDl as designated combiner. Since C knows x,s,gy,g~y,{xIDi=bi}i∈Si≠l, he/she can choose k⟵$Zp∗ and easily answer A2.
Finally,A2 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(29)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, and m∗ is computed as in Aggregation algorithm.
SinceC knows x,s and all {xIDi=bi}i∈S∗i≠l, he/she computes(30)σ1′=gx+b′r∗/∏i∈S∗s+IDiwhere b′=∑i∈S∗i≠lbi; next he/she computes(31)σ1∗σ1′∏i∈S∗s+IDi=gx+b∗+m∗y-x-b′r∗/∏i∈S∗s+IDi∏i∈S∗s+IDi=gbl+m∗yr∗=gu+m∗vr∗Finally, C can have the pair(32)T=gu+m∗vr∗,gr∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, m∗ has never been asked to O; this leads to the fact that T is a valid pair to break the security of the Assumption 1. Note that m∗=H1{H2(Mi∗),H2(IDi)}i∈S∗,{0}i=1,…,2n-2S∗.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA2 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 1 with the same success probability ε, which concludes our proof.


## 3.1. Construction

The construction of ourSCL-AMS scheme is detailed as follows.S e t u p: it takes as input the security parameter λ; the algorithm generates a bilinear map group system (p,G,G~,GT,g,g~,e). Next, it chooses random scalars s,x,y⟵$Zp∗, and n∈Zp∗ is the maximum number of users in an aggregating set, as well as two hash functions H1,H2 where(2)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗Finally, it sets the public parameter(3)param=g,g~,g~sii=1,…,n,X~=g~x,Y~=g~y,X=gx,Y=gy,H1,H2and the master secret keymsk=s.P a r t i a l-Secret-Key-Generation: it takes as input param, msk=s, and the user i’s identity IDi; let IDi=H2(IDi); the algorithm generates a partial secret key (4)PIDi=Pi,1,Pi,2,Pi,3=gx/s+IDi,gy/s+IDi,g1/s+IDifor useri.U s e r-Secret-Value-Generation: it takes as input user i’s identity IDi; the algorithm chooses bi⟵$Zp∗ and sets xIDi=bi as user i’s secret value.P u b l i c-Key-Generation: it takes as input param and xIDi; the algorithm sets PKIDi=g~bi as the public key of user i.F u l l-Secret-Key-Generation: it takes as input xIDi and PIDi; the algorithm outputs SKi=(xIDi,PIDi) as the full secret key of user i.A g g r e g a t i o n: denote S as the aggregating set of users, S≤n. There are two cases, if |S|=1, the algorithm takes as input param, IDi, SKi, and a message Mi,i∈S. The algorithm first chooses r⟵$Zp∗ and computes m=H2(Mi),IDi=H2(IDi) and then outputs signature σ=(σ1,σ2,σ3,σ4), where(5)σ1=Pi,1rPi,2mrPi,3bir=gx+bi+myr/s+IDi,σ2=Pi,3r=gr/s+IDi,σ3=gr,σ4=Y~bi/r=g~biy/rIf|S|>1, the algorithm now is run by PKG and all users in S. More precisely, the algorithm consists of two separate following algorithms: note that {IDi=H2(IDi)}i∈S:(1)
First algorithm:PKG takes as input msk, the description of S,{Mi∈{0,1}∗}i∈S as well as param; note that if all messages {Mi∈{0,1}∗}i∈S are the same, the signature is multisignatures.PKG follows strictly the order of pair (Mi,IDi)i∈S to compute m as follows:(6)m=H1H2Mi,H2IDii∈S,0i=1,…,2n-2SNext, it choosesk⟵$Zp∗ and computes(7)Psig=gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/kPsig are then sent to all users in S via public channel or PKG simply publishes it to the public domain. PKG then is not involved in the second algorithm.(2)
Second algorithm: it takes as inputPsig and runs by all users in S. First, each user i∈S takes as input xIDi=bi,Psig and computes the pair:(8)gbik/∏i∈Ss+IDi,g~biy/kFinally, select one user inS as designated combiner, S-1, other remaining users in S send their above outputs to this designated combiner via public channel, and the aggregate multisignature is then built as follows: designated combiner takes as input (9)Psig,gbik/∏i∈Ss+IDi,g~biy/ki∈Sand choosesr′⟵$Zp∗ and outputs the aggregate multisignature σ=(σ1,σ2,σ3,σ4), where(10)σ1=gx+b+myr/∏i∈Ss+IDi,σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~by/randb=∑i∈Sbi,r=r′·k.Note that the designated combiner computes(11)σ1=gx+myk·r′/∏i∈Ss+IDi·∏i∈Sgbi·k·r′/∏i∈Ss+IDi;σ4=∏i∈Sg~biy/k·r′AggregateVerification: it take as input aggregate multisignature σ=(σ1,σ2,σ3,σ4), the description of aggregating set of users S, messages Mi∈{0,1}∗i∈S, and param, the algorithm computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and(12)PKS=∏i∈SPKIDi=g~b,T=g~∏i∈Ss+IDi,T′=X~·PKS·Y~m·g~=g~x+b+my+1;note that he/she can computeT from {g~si}i=1,…,n in param.Finally, the aggregate multisignature is accepted (output1) if the following equation holds:(13)eσ1·σ2,T·eσ3,σ4=eσ3,T′·eY,PKS⇔eσ1·σ2,T·eσ3,σ4T′=eY,PKSCorrectness. It is easy to show that (14)eσ1·σ2,T·eσ3,σ4=egx+b+myr/∏i∈Ss+IDi·gr/∏i∈Ss+IDi,g~∏i∈Ss+IDi·egr,g~by/r=egx+b+my+1r,g~·eg,g~by=egr,g~x+b+my+1·egy,g~b=eσ3,T′·eY,PKSMultisignature Scheme with Public Key Aggregation. In [25], the authors defined a multisignature scheme with public key aggregation, for which the public keys of users in the aggregating set S are aggregated into a short aggregate public key in advance through an additional Key Aggregation algorithm. The advantage of this scheme is that the verifier can only take a constant-size of input (multisignature and aggregate public key) to verify the multisignature, which were showed in [25, 43] that this type of scheme can be applied well to the Bitcoin blockchain application.It is clear that our scheme is a multisignature scheme with public key aggregation as defined in [25], since we can add a new Key Aggregation algorithm which computes in advance the pair (PKS, T) as an aggregate public key of the aggregating set S. The verifier therefore just needs to take a constant-size of input to verify the validity of the signature. Note that we can use a short length of bits to describe the aggregating set S.Remark 9.
We also note that, in our scheme, for an aggregate signature, we do not need to require that all messages{Mi∈{0,1}∗}i∈S are different.


## 3.2. Efficiency

Regarding the signature size, as in the construction and detailed in Table1, the signature in our SCL-AMS scheme just contains four elements, three in the group G and one in the group G~. If we decide to use NIST’s figures [53], then to achieve 80 bits or 128 bits of security (that means the adversary needs at least 280 or 2128 operations to break the security of our scheme), each element in the group G is about 160 bits or 256 bits and in the group G~ is about 1024 bits or 3072 bits. This leads to the fact that the signature size of our scheme is 1504 bits or 3840 bits corresponding to the security parameter 80 bits or 128 bits, respectively.Similarly, the user’s full secret key size of our scheme is 640 bits or 1024 bits corresponding to the security parameter 80 bits or 128 bits, respectively.Regarding the signing phase, there are two cases:(1)
S = 1, the signing phase requires five exponentiations in G, one exponentiation in G~, and two hash operations.(2)
S>1, the signing phase requires n′+7 exponentiations in G, n′+2 exponentiations in G~, and 2n′+1 hash operations, where n′ is the size of the aggregating set of signers.Regarding the verification phase, there are also two cases:(1)
|S| = 1, the verification phase requires two exponentiations in G~, three Pairings, and two hash operations.(2)
|S|>1, the verification phase requires n′+1 exponentiations in G~, three Pairings, and 2n′+1 hash operations, where n′ is the size of the aggregating set of signers.Overall, for both storage and computational complexity, our scheme can meet the requirements for a lightweight device, that means our scheme is suitable for resource-constrained applications such as Bitcoin blockchain, Healthcare, Multicast Acknowledgment Aggregation, vehicular ad hoc networks, wireless sensor networks, Internet of Things, and so on.


## 3.3. Security

We give in this section two theorems which show that ourSCL-AMS scheme is secure.


### 3.3.1. Secure against Strong Type I Adversary

We first prove that ourSCL-AMS scheme is secure against strong Type I adversary.Theorem 10.
If there exists a strong Type I adversaryA1 defined in Game 1 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 2 with the same probability ε.Proof.
Suppose thatC is an adversary against our Assumption 2; we let C act as a challenger in Game 1 (see Section 2.1.3), that means C simulates A1 and then uses the output of A1 to break the security of the Assumption 2.
At the beginning,C has an instance of Assumption 2: (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy), x,y,s,n∈Zp∗ as well as the right to access two oracles O1 and O2. Note that, for oracle O1, on input ID∈Zp∗, output the triplet (gx/s+ID, gy/s+ID, g1/s+ID). For oracle O2, on input (m,{IDi∈Zp∗}i∈S), choose a random r∈Zp and output (g(x+my)r/∏i∈S(s+IDi), gr/∏i∈S(s+IDi), gr, g~y/r).
Note thatC does not know the values s, x, and y.
To simulateA1, C first receives from A1 the target identity IDl for which he/she intends to attack.
C chooses two hash functions H1,H2 where(15)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A1 as public parameters.
To simulateA1, C must manage to answer oracles as follows.
P a r t i a l S K ( I D i ). C simply requests oracle O1 on input IDi and directly forwards the result to A1. Note that, following Game 1 (see Section 2.1.3), A1 cannot make PartialSK(IDi) query on i=l.
R e q u e s t P K ( I D i ). C chooses bi⟵$Zp∗ and gives PKIDi=g~bi to A1.
U s e r S e c r e t ( I D i ). C first checks whether the RequestPK(IDi) has been queried before; if it is not the case C first make this query on IDi itself, using the above descriptions. In both cases, C knows xIDi; thus C gives xIDi to A1.
R e p l a c e P K ( I D i , x I D i ′ , P K D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKDi′=g~xIDi′.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S, then C requests oracle O2 on input (m,{IDi}i∈S) to get the tuple:(16)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
SinceC knows {xIDi=bi}i∈S (even if PKIDi has been replaced), he/she can easily compute the aggregate multisignature σ as the Aggregation algorithm and returns σ to A1.
We also note here that, in ourAggregation algorithm, the output of PKG and the outputs of users who are not designated combiner are sent via public channel (or made public), that means A1 can request to know these outputs.
Note that the output ofPKG is(17)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/k
and the output of each user inS is(18)gbik/∏i∈Ss+IDi,g~biy/k
for somek∈Zp∗. However, since C knows (19)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
and all{xIDi=bi}i∈S, C can easily answer A1 by choosing r′⟵$Zp∗ and implicitly sets k=r′·r.
Finally,A1 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(20)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, m∗ is computed as in Aggregation algorithm, and C knows all {xIDi=bi}i∈S∗; it is easy for C to recover the tuple(21)T=gx+m∗yr∗/∏i∈S∗s+IDi,gr∗/∏i∈S∗s+IDi,gr∗,g~y/r∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, (m∗,{IDi}i∈S∗) has never been asked to O2 and IDl also has never been asked to O1. This leads to the fact that T is a valid tuple to break the security of the Assumption 2.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA1 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 2 with the same success probability ε, which concludes our proof.


### 3.3.2. Secure against Strong Type II Adversary

In this section, we prove that ourSCL-AMS scheme is secure against strong Type II adversary.Theorem 11.
If there exists an adversaryA2 defined in Game 2 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 1 with the same probability ε.Proof.
Suppose thatC is an adversary against Assumption 1; we let C act as a challenger in Game 2 (see Section 2.1.3), that means C simulates A2 and then uses the output of A2 to break the security of the Assumption 1.
At the beginning,C has the instance of assumption: (g,g~,g~u,g~v,gv) as well as the right to access oracle O. Note that for oracle O, on input m∈Zp∗, output the tuple (g(u+mv)r, gr, ,g~v/r,g~uv/r).
Note thatC does not know the values u and v.
To simulateA2, C first receives from A2 the target identity IDl for which he/she intends to attack. C chooses x,s,n⟵$Zp∗ and two hash functions H1,H2 where(22)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗Next, C implicitly sets y=v and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A2 as public parameters.
To simulateA2, C must manage to answer oracles as follows.
R e q u e s t P K ( I D i ). If i≠l, C chooses xIDi=bi⟵$Zp∗ and returns PKIDi=g~bi to A2. If i=l, C implicitly sets bi=u and returns PKIDi=g~u to A2. Note that, in this case, C does not know xIDi.
U s e r S e c r e t ( I D i ). C checks whether RequestPK(IDi) has been queried before, if it is not the case C first makes this query on IDi itself, using the above description. In both cases, C knows xIDi and return xIDi to A2. Note that follow the definition of security model, A2 cannot make query on the case i=l.
R e p l a c e P K ( I D i , x I D i ′ , P K I D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKIDi′=g~xIDi′. Note that, following the definition of security model, A2 cannot make query on the case i=l.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S.
There are two cases, ifl∉S then C knows all information; thus he/she chooses r⟵$Zp∗ and easily computes the aggregate multisignature σ=(σ1,σ2,σ3,σ4), where(23)σ1=gx+b+myr/∏i∈Ss+IDi,σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~by/rand b=∑i∈Sbi. Finally, C returns σ to A2.
In casel∈S, C does not knows bl; that means C cannot know b; he/she therefore cannot compute σ1,σ4. In this case, C requests oracle O on input m to receive the tuple (note that bl=u,y=v):(24)gu+mvr,gr,g~v/r,g~uv/r=gbl+myr,gr,g~y/r,g~bly/rSince C knows {xIDi=bi}i∈Si≠l (even if corresponding public keys have been replaced) and x,s, he/she can easily compute(25)σ1=gx+bl+myr/∏i∈Ss+IDi·gr·b′/∏i∈Ss+IDi=gx+b+myr/∏i∈Ss+IDiand(26)σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~bly/r·g~b′y/r=g~by/rwhere b′=∑i∈Si≠lbi. Finally, C returns σ to A2.
We also note here that, in ourAggregation algorithm, PKG only runs the first algorithm and does not participate in the second algorithm; that means A2 knows the output of PKG, which is (27)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/kfor some k∈Zp∗. On the other hand, since in Aggregation algorithm, users who are not designated combiner send their outputs to designated combiner via public channel, that means A2 can know these outputs, which are S-1 pairs:(28)gbik/∏i∈Ss+IDi,g~biy/kTo answer A2, C first implicitly sets user with identity IDl as designated combiner. Since C knows x,s,gy,g~y,{xIDi=bi}i∈Si≠l, he/she can choose k⟵$Zp∗ and easily answer A2.
Finally,A2 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(29)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, and m∗ is computed as in Aggregation algorithm.
SinceC knows x,s and all {xIDi=bi}i∈S∗i≠l, he/she computes(30)σ1′=gx+b′r∗/∏i∈S∗s+IDiwhere b′=∑i∈S∗i≠lbi; next he/she computes(31)σ1∗σ1′∏i∈S∗s+IDi=gx+b∗+m∗y-x-b′r∗/∏i∈S∗s+IDi∏i∈S∗s+IDi=gbl+m∗yr∗=gu+m∗vr∗Finally, C can have the pair(32)T=gu+m∗vr∗,gr∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, m∗ has never been asked to O; this leads to the fact that T is a valid pair to break the security of the Assumption 1. Note that m∗=H1{H2(Mi∗),H2(IDi)}i∈S∗,{0}i=1,…,2n-2S∗.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA2 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 1 with the same success probability ε, which concludes our proof.


## 3.3.1. Secure against Strong Type I Adversary

We first prove that ourSCL-AMS scheme is secure against strong Type I adversary.Theorem 10.
If there exists a strong Type I adversaryA1 defined in Game 1 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 2 with the same probability ε.Proof.
Suppose thatC is an adversary against our Assumption 2; we let C act as a challenger in Game 1 (see Section 2.1.3), that means C simulates A1 and then uses the output of A1 to break the security of the Assumption 2.
At the beginning,C has an instance of Assumption 2: (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy), x,y,s,n∈Zp∗ as well as the right to access two oracles O1 and O2. Note that, for oracle O1, on input ID∈Zp∗, output the triplet (gx/s+ID, gy/s+ID, g1/s+ID). For oracle O2, on input (m,{IDi∈Zp∗}i∈S), choose a random r∈Zp and output (g(x+my)r/∏i∈S(s+IDi), gr/∏i∈S(s+IDi), gr, g~y/r).
Note thatC does not know the values s, x, and y.
To simulateA1, C first receives from A1 the target identity IDl for which he/she intends to attack.
C chooses two hash functions H1,H2 where(15)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A1 as public parameters.
To simulateA1, C must manage to answer oracles as follows.
P a r t i a l S K ( I D i ). C simply requests oracle O1 on input IDi and directly forwards the result to A1. Note that, following Game 1 (see Section 2.1.3), A1 cannot make PartialSK(IDi) query on i=l.
R e q u e s t P K ( I D i ). C chooses bi⟵$Zp∗ and gives PKIDi=g~bi to A1.
U s e r S e c r e t ( I D i ). C first checks whether the RequestPK(IDi) has been queried before; if it is not the case C first make this query on IDi itself, using the above descriptions. In both cases, C knows xIDi; thus C gives xIDi to A1.
R e p l a c e P K ( I D i , x I D i ′ , P K D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKDi′=g~xIDi′.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S, then C requests oracle O2 on input (m,{IDi}i∈S) to get the tuple:(16)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
SinceC knows {xIDi=bi}i∈S (even if PKIDi has been replaced), he/she can easily compute the aggregate multisignature σ as the Aggregation algorithm and returns σ to A1.
We also note here that, in ourAggregation algorithm, the output of PKG and the outputs of users who are not designated combiner are sent via public channel (or made public), that means A1 can request to know these outputs.
Note that the output ofPKG is(17)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/k
and the output of each user inS is(18)gbik/∏i∈Ss+IDi,g~biy/k
for somek∈Zp∗. However, since C knows (19)gx+myr/∏i∈Ss+IDi,gr/∏i∈Ss+IDi,gr,g~y/r
and all{xIDi=bi}i∈S, C can easily answer A1 by choosing r′⟵$Zp∗ and implicitly sets k=r′·r.
Finally,A1 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(20)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, m∗ is computed as in Aggregation algorithm, and C knows all {xIDi=bi}i∈S∗; it is easy for C to recover the tuple(21)T=gx+m∗yr∗/∏i∈S∗s+IDi,gr∗/∏i∈S∗s+IDi,gr∗,g~y/r∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, (m∗,{IDi}i∈S∗) has never been asked to O2 and IDl also has never been asked to O1. This leads to the fact that T is a valid tuple to break the security of the Assumption 2.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA1 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 2 with the same success probability ε, which concludes our proof.


## 3.3.2. Secure against Strong Type II Adversary

In this section, we prove that ourSCL-AMS scheme is secure against strong Type II adversary.Theorem 11.
If there exists an adversaryA2 defined in Game 2 (see Section 2.1.3), who breaks the security of our SCL-AMS scheme with probability ε, then there exists an adversary C who can break the security of the Assumption 1 with the same probability ε.Proof.
Suppose thatC is an adversary against Assumption 1; we let C act as a challenger in Game 2 (see Section 2.1.3), that means C simulates A2 and then uses the output of A2 to break the security of the Assumption 1.
At the beginning,C has the instance of assumption: (g,g~,g~u,g~v,gv) as well as the right to access oracle O. Note that for oracle O, on input m∈Zp∗, output the tuple (g(u+mv)r, gr, ,g~v/r,g~uv/r).
Note thatC does not know the values u and v.
To simulateA2, C first receives from A2 the target identity IDl for which he/she intends to attack. C chooses x,s,n⟵$Zp∗ and two hash functions H1,H2 where(22)H2:0,1∗→Zp∗,H1:Zp∗2n→Zp∗Next, C implicitly sets y=v and then gives (g, g~, {g~si}i=1,…,n, g~x, g~y, gx, gy,H1,H2) to A2 as public parameters.
To simulateA2, C must manage to answer oracles as follows.
R e q u e s t P K ( I D i ). If i≠l, C chooses xIDi=bi⟵$Zp∗ and returns PKIDi=g~bi to A2. If i=l, C implicitly sets bi=u and returns PKIDi=g~u to A2. Note that, in this case, C does not know xIDi.
U s e r S e c r e t ( I D i ). C checks whether RequestPK(IDi) has been queried before, if it is not the case C first makes this query on IDi itself, using the above description. In both cases, C knows xIDi and return xIDi to A2. Note that follow the definition of security model, A2 cannot make query on the case i=l.
R e p l a c e P K ( I D i , x I D i ′ , P K I D i ′ ). C knows xIDi′ and then simply sets PKIDi=PKIDi′=g~xIDi′. Note that, following the definition of security model, A2 cannot make query on the case i=l.
R e q u e s t S i g ( { M i , I D i } i ∈ S ). C computes m=H1{H2(Mi),H2(IDi)}i∈S,{0}i=1,…,2n-2S, and {IDi=H2(IDi)}i∈S.
There are two cases, ifl∉S then C knows all information; thus he/she chooses r⟵$Zp∗ and easily computes the aggregate multisignature σ=(σ1,σ2,σ3,σ4), where(23)σ1=gx+b+myr/∏i∈Ss+IDi,σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~by/rand b=∑i∈Sbi. Finally, C returns σ to A2.
In casel∈S, C does not knows bl; that means C cannot know b; he/she therefore cannot compute σ1,σ4. In this case, C requests oracle O on input m to receive the tuple (note that bl=u,y=v):(24)gu+mvr,gr,g~v/r,g~uv/r=gbl+myr,gr,g~y/r,g~bly/rSince C knows {xIDi=bi}i∈Si≠l (even if corresponding public keys have been replaced) and x,s, he/she can easily compute(25)σ1=gx+bl+myr/∏i∈Ss+IDi·gr·b′/∏i∈Ss+IDi=gx+b+myr/∏i∈Ss+IDiand(26)σ2=gr/∏i∈Ss+IDi,σ3=gr,σ4=g~bly/r·g~b′y/r=g~by/rwhere b′=∑i∈Si≠lbi. Finally, C returns σ to A2.
We also note here that, in ourAggregation algorithm, PKG only runs the first algorithm and does not participate in the second algorithm; that means A2 knows the output of PKG, which is (27)gx+myk/∏i∈Ss+IDi,gk/∏i∈Ss+IDi,gk,g~y/kfor some k∈Zp∗. On the other hand, since in Aggregation algorithm, users who are not designated combiner send their outputs to designated combiner via public channel, that means A2 can know these outputs, which are S-1 pairs:(28)gbik/∏i∈Ss+IDi,g~biy/kTo answer A2, C first implicitly sets user with identity IDl as designated combiner. Since C knows x,s,gy,g~y,{xIDi=bi}i∈Si≠l, he/she can choose k⟵$Zp∗ and easily answer A2.
Finally,A2 outputs a tuple (S∗, {Mi∗}i∈S∗, σ∗) for which RequestSig({Mi∗,IDi}i∈S∗) has never been queried; note that l∈S∗.
Fromσ∗=(σ1∗,σ2∗,σ3∗,σ4∗), where(29)σ1∗=gx+b∗+m∗yr∗/∏i∈S∗s+IDi,σ2∗=gr∗/∏i∈S∗s+IDi,σ3∗=gr∗,σ4∗=g~b∗y/r∗,b∗=∑i∈S∗bi, and m∗ is computed as in Aggregation algorithm.
SinceC knows x,s and all {xIDi=bi}i∈S∗i≠l, he/she computes(30)σ1′=gx+b′r∗/∏i∈S∗s+IDiwhere b′=∑i∈S∗i≠lbi; next he/she computes(31)σ1∗σ1′∏i∈S∗s+IDi=gx+b∗+m∗y-x-b′r∗/∏i∈S∗s+IDi∏i∈S∗s+IDi=gbl+m∗yr∗=gu+m∗vr∗Finally, C can have the pair(32)T=gu+m∗vr∗,gr∗
SinceRequestSig({M∗i,IDi}i∈S∗) has never been queried, m∗ has never been asked to O; this leads to the fact that T is a valid pair to break the security of the Assumption 1. Note that m∗=H1{H2(Mi∗),H2(IDi)}i∈S∗,{0}i=1,…,2n-2S∗.
Since the simulation is perfect, this leads to the fact that if there exists an adversaryA2 who can break the security of our scheme with success probability ε, then there exists an attacker who can solve the Assumption 1 with the same success probability ε, which concludes our proof.


## 4. Conclusion

Aggregate signature and multisignature have many practical applications such as Bitcoin blockchain, Healthcare, Multicast Acknowledgment Aggregation, and so on, while certificateless is an interesting technique to avoid the use of expensive certificate inPKI and key escrow problem in identity-based cryptography. In this paper, we consider the combination of an aggregate signature scheme and a multisignature scheme in the certificateless setting. We concretely propose the first server-aided certificateless aggregate multisignature scheme which achieves the following properties:(i)
the signature contains four elements in all cases. When using NIST’s figures [53], the signature size of our scheme is 1504 bits or 3840 bits corresponding to the security parameter 80 bits or 128 bits, respectively. The user’s full secret key size is 640 bits or 1024 bits corresponding to the security parameter 80 bits or 128 bits, respectively;(ii)
it is secure against strong Type I and strong Type II adversaries in the standard model underGDDHE assumptions;(iii)
support public key aggregation;(iv)
public key size, signing time, and verifying time depend on the maximum number of signers for one aggregating set, which is fixed at the setup.



---

*Source: 3424890-2019-03-18.xml*