Informatica 42 (2018) 221–228 221
  
A Pairing Free Secure Identity-based Aggregate Signature Scheme under 
Random Oracle 
Eman Abouelkheir 
Electrical Department, Faculty of Engineering, Kafr Elsheikh University, Egypt 
E-mail: emanabouelkhair@eng.kfs.edu.eg 
 
Jolanda G. Tromp 
Department of Computer Science, State University of New York Oswego, USA 
E-mail: jolanda.tromp@oswego.edu 
 
Keywords: information security, aggregate signature, without parings, security proof, random oracle  
Received: November 15, 2016 
The signature aggregation is efficient for the communication links as the time complexity is independent 
of n different users. The bilinear pairing requires super-singular elliptic curve groups that have a 
spacious range of elements. Also, the point multiplication over elliptic curve is less computational cost 
than the pairings, therefore, the pairing-based schemes expose more computational complexity than 
schemes that without pairings. This paper introduces a new efficient and secure pairing free signature 
scheme based on the idea of aggregation. Also, the proposed scheme without pairings offers lower 
computational cost than other schemes from pairings as it saves 68.69% from computations. 
Povzetek: Ta prispevek se ukvarja s kriptografskimi algoritmi, konkretno s shemo digitalnih podpisov. 
Opisana je izboljšava obstoječega algoritma, ki dosega pohitritev za dve tretjini, hkrati ostaja varna. 
 
1 Introduction  
Cryptography has two primitive issues; confidentiality 
and authentication. Digital signature achieves the 
authentication issue. Also, for efficient communication 
links, schemes should provide low time complexity. 
Moreover, low time complexity is useful for battery and 
bandwidth saving of the channel in networks [1].  
There are many cryptographic algorithms provide 
privacy, such as signature schemes, authentication 
schemes, and encryption schemes [2]. For providing 
privacy and anonymity to a user, these schemes have to 
be properly combined. Schemes and methods such as 
group signature schemes, blind signatures, aggregate 
signatures, zero-knowledge proof methods, 
homomorphic encryption schemes offer several useful 
privacy-enhancing properties, e.g. identity hiding, 
binding information, data confidentiality, unlinkability, 
intracebility, etc. Recently, many applications and 
services require privacy protection over communication 
systems. The current secure communication systems 
support authentication, data integrity, and non-
repudiation. But, the communication systems users and 
providers can need different security properties that are 
out of basic security properties. These advanced 
properties are usually connected with user privacy. The 
following text summarizes the advanced security 
properties and requirements.  
• Privacy/Anonymity - privacy protection is ensured 
for every user in the system who follows the rules. Users 
can communicate anonymously. Their identities can be 
revealed only in special cases, e.g. when a user breaks a 
rule, authority order, police order, emergency events etc. 
Two types of privacy protection can be distinguished: a 
basic anonymity to protect a user identity against passive 
attacks and a full anonymity to protect also against active 
attacks [3]. Signatures needed when an attacker gets 
access to all old messages. When the unlinkability 
property ensured, then the attacker is not able to connect 
certain signatures together.  
 Responsibility/revocation - every user, has to be 
revealed and revoked using the certain key when 
breaking the rules of a system. The revocation assures 
that the revoked user has no rights in whole systems 
afterward. The revocation helps protect the system 
against repeated misusing. In some applications, the 
traceability of malicious users’ messages is demanded.  
 Efficient and secure key management - key exchange, 
revocation, and establishment in systems have to be 
efficient computationally/memory low cost and secure. 
In privacy-preserving solutions, key management has 
to keep user privacy.  
 Efficient and secure execution of cryptographic 
protocols - the phases of a cryptographic protocol 
should be as efficient as possible to minimize the 
negative influence of a system, especially, if the 
restricted devices have been deployed. 
 Exculpability - neither revocation or key manager, can 
be able to generate a valid signature behalf another 
user who hold trace keys. The user cannot be accused 
that makes signature which he does not make. This 
property is mainly needed in group signature schemes, 

222 Informatica 42 (2018) 221–228 E. Abouelkheir et al.  
i.e exculpability that is ensured in [4] by Boneh, Boyen 
and Shacham. 
The aggregate signature idea arises from those 
di fferent signers aggregated into a concise aggregate 
signature on different documents[5]. Using the aggregate 
signatures instead of using n signature by n different 
users in many application such as key distribution in PKI 
reducing the communication overhead and offer efficient 
computational cost.  
Another example, in router securing system, each 
router need to sign its part of a route in the  
communication link then transmits all the signatures to 
the following router. Without the aggregation  concept, 
transmitting the different signatures exposes high 
communication overhead[6]. The aggregate signature 
could be used instead of individual signs for this goal. 
Recently, there are two signature schemes are proposed. 
The first one [5] provides flexible aggregation based on 
pairings. The second [7] provides only sequential 
aggregation using certified trapdoor permutations. For 
the schemes in [5,7], the authors proposed aggregates 
signature schemes which size is independent of n users. 
Specifying individual signers by some public information 
needed for public verification. Aggregate signature 
schemes that specify the signers with their public 
information may be similar as the traditional signatures 
and both are not efficient. Thus, specifying the signers 
with their identities is more useful than specifying them 
by their public keys.   
Cryptography from pairings has many prime 
properties. It is supposed that Pairing-based cryptography 
with smaller parameters can present a desired security 
level as the general elliptic curve cryptography. Suppose 
that  there is an elliptic curve E has elements defined 
over 
q
F . But the pairing-based cryptography is working 
with the functions and elements defined over 
k
q
F , where 
k is some random and chosen to be secure. Either the 
elliptic curve hard problem (ECDLP) defined over 
) F ( E
q
 or the discrete logarithm problem (DLP) defined 
over
 
* k
q
F are basic problems that the  cryptography from 
pairings security depends on [8]. Because of the previous 
clarification, this paper introduces a new pairing-free 
signature aggregation scheme based on the general 
elliptic curve cryptosystem depends on signers identities. 
The idea behind the identity-based cryptography 
(IBC) [9], to use some information belongs to a signer ( 
such as an email ID ) as a user public key rather than  
using public-key and certificate management. Therefore, 
the IBC system requires Private Key Generator (PKG) 
that is called a trusted third party, that generates the 
private keys for all identities based on its master key and 
the signer identity. Boneh and Franklin [10] and  Cocks 
[11] propose many identity-based encryption schemes. 
Also, old schemes in [9,12,13]; recent schemes and 
analyses include [14,15,16,17].  
The concept of signature aggregation allows 
different signers to sign different messages. This leads to 
efficient communication and fewer computations. In any 
aggregate signature scheme n different signatures are 
considered as one single signature. The aggregation 
approach can be used instead of using public key 
certificates to satisfy efficient communication and 
computations. Aggregate signatures have many 
applications such as mutual authentication between 
vehicles in VANETs and in wireless sensor network. 
The goal of my paper to introduce a new secure  
pairing-free aggregate signature scheme. The proposed 
scheme security is proven in the random oracle and 
assuming a hard Diffie-Hellman problem. Also, the 
proposed scheme saves the time complexity by 68.69% . 
The new aggregate signature and its analysis is the 
modified version of the scheme in [18].  
The rest of the paper is organized as follow : section 
two presents the digital signature approach versus the 
water marking. Also, section three describes 
preliminaries. Then section four introduces the generic 
model for the proposed scheme. Moreover, section five 
presents the security requirements of any aggregate 
signatures based on user’s identities. In section six and 
seven, the proposed scheme is presented with the formal 
security proof under random oracle respectively. In 
section eight, the results and discussion are introduced. 
The proposed scheme is compared with other in literature 
in section nine. Section ten concludes the proposed work.  
Finally, the future scope introduced in section eleven. 
2 Digital signing versus 
watermarking 
A digital signing is an approach of cryptography used for 
securing the communication links. The goal of the 
signature to verify the end to end communication system 
users.  
The digital signing operation is similar to the 
handwritten signing operation and exactly as a  paper 
signature. It used to verify the identity of a user using its 
digital certificate. This paper is concerned with the 
digital signature approach. 
The goal of watermarking to hide the information 
into a digital signal that provides a copyright protection 
in a digital format[19]. Many watermarking schemes 
have been proposed. In 2012, Nilanjan Dey, Poulami 
Das, Sheila Sinha Chaudhuri, and Achintya Das, [20] 
used  Alattar's method efficiently for watermark insertion 
and extraction for an EEG signal. In 2013, K. P. Arijit, 
D. Nilanjan, S. Sourav, D. Achintya, and S. Ch. Sheli 
[21] proposed a new technique for reversible 
watermarking is used for the color image .In 2014, 
Nilanjan Dey, Goutam Dey, Sheli Sinha Chaudhuri, and 
Sayn Chakraborty [22] proposed two novel blind-
watermarking mechanisms are; 1- session key based 
blind-watermarking mechanism and 2- self-recovery 
based blind-watermarking mechanism, into the 
Electromyogram (EMG) signal. In 2015, Nilanjan Dey, 
Monalisa Dey , Sainik Kumar Mahanta ,and  Achintya  
Das [23] proposed a technique is to prevent any 
modifications in a transmitted biomedical ECG signal. In 
2016, Y. B. Amar, I. Trabelsi, D. Nilanjan and S. 

A Pairing Free Secure Identity-based… Informatica 42 (2018) 221–228 223 
Bouhlel [24] proposed watermarking scheme used for 
copyright protection purposes. 
3 Preliminary  
3.1 Bilinear pairing 
Suppose 
1
G is a cyclic group has an order q, q is prime. 
This group is generated by the point P over an elliptic 
curve E and defined over the prime field 
q
F . Let e ˆ
 
be a 
pairing where 
T
G G G : e ˆ   . For any   R Q, P, (points 
over an elliptic curve E) and 
q
F d c,  , d c, are integers. 
The pairings satisfy the following properties:
 
- linearity: 
cd
) Q . P ( e ˆ ) dQ , cP ( e ˆ  . 
- NonDegenerate: 1 ) P . P ( e ˆ  . 
- Easy to compute : ) Q . P ( e ˆ it must be easy and 
efficient computed. 
3.2 Elliptic Curve Cryptography(ECC) 
ECC is an public key cryptography approach based on 
the mathematics of elliptic curves. ECC is faster than 
RSA and uses smaller keys, but still, provides the same 
level of security .  
Suppose ) b , a ( E
q
 are the set of points over the 
elliptic curve E that defined over the prime field
q
F , E 
defined by q mod ) b ax x ( q mod y
3 2
   and  b a,
must satisfy the equation 0 q mod ) b 27 a 4 (
2 3
    . 
The cyclic group   } F y , x : ) y , x {( G
q q
  
q
F / E ) y , x (  , 
q
G is an elliptic curve additive group. 
The group identity element in
q
G is O ; the infinity 
point; The scalar multiplication on 
q
G defined as  
P P ... .. P P . k      .  For some integer 0 > n , a point 
P of order n satisfy O = n·P . ECC was proposed in 1985, 
by Miller [25] and Koblitz [26]. When comparing ECC 
with other public key cryptosystems, it was found that 
ECC-based public key cryptosystem has many 
advantages such as low computation cost, smaller key 
size, low storage space cost etc. It is known that the 
discrete logarithm problem based on ECC (ECDLP) of 
any  elliptic curve element that has a public point known 
base point, is harder than the discrete logarithm problem 
(DLP) over the finite field 
q
F 
Security is not the only cryptography objective goal 
but also, there are many factors as the problems 
associated with key management and protection, hash 
functions , defective use of random generators, and the 
incompact private key software. The ECC 
implementation issues are [27]:  
 Used in Diffie Hellman cryptosystem and also, 
digital signing approach. 
 There are many available standardized elliptic 
curves approved by NIST for the multiple security 
requirements. 
 Elliptic curves cryptosystems enable 
comprehensive information on algorithms. 
The Benefits of elliptic curve based cryptosystems over 
RSA cryptosystem:  
 The elliptic curve based cryptosystem key takes 
significantly less memory for the same security 
level. Table I indicates the key size for RSA and 
ECC for the same security level. 
 Smaller key size in ECC leads to faster digital 
signature  generation and therefore saving resources. 
In the other hand, ECC has disadvantages versus 
RSA crypto system. It is complicated in mathematical 
backgrounds.  
NIST guidelines for key size of ECC , RSA, and AES 
ECC  RSA  Ratio AES  
163 1024 1:6  
256 3072 1:12 128 
384 7680 1:20 192 
512 15360 1:30 256 
Table 1: Security level of various key sizes in ECC and 
RSA. 
3.3 Computational problems 
Here, a briefly review of some mathematical problems: 
Definition 3.3.1. Suppose g be a group generator of the 
group G where G g  . The CDH related to g is how to 
compute 
cd
g given by  ) g , g (
d c
, 
*
q
Z d , c  . 
Definition.3.3.2. (Computational Diffie-Hellman (CDH) 
Problem) over an elliptic curve. Given P point over an 
elliptic curve and 
*
q
Z d , c  then for known
p
G dP) cP, (P,  , it is hard to compute of cdP over the 
group 
q
G 
Definition.3.3.3. (Computational Diffie-Hellman (CDH)  
Assumption). Let A be an adversary able to break the 
CDH problem with a trivial probability, if given the tuple
p
G dP) cP, (P,  of CDH problem where 
*
q
Z d , c  , then 
A could solve the CDH with the trivial advantage
] Z d , c : cdP ) dP , cP , P ( A Pr[ Adv
*
q
CDH
G , A
p
   . 
4 Aggregate signature model 
An identity-based aggregate signature scheme model has 
composed six algorithms:  
 Setup phase: with input k; the security parameter; the 
public key generator (PKG) generates the master mpk
and private keys msk  and the system parameters
 params . Finally, the PKG publishes  params , mpk
and keeps msk secret. 
 Key Extract: PKG runs this algorithm using the signer 
identity 
i
ID ;delivered by the signer 
i
U , param and 
msk as an input. The output is the signer private key 
i
d and the PKG sends the signer private key 
i
d via 
secure channel to the user 
i
U .
 
 

224 Informatica 42 (2018) 221–228 E. Abouelkheir et al.  
 Sign: this algorithm takes the user identity
i
ID , his 
private key 
i
d , message
i
m and param as input to 
create a valid signature 
i
 on 
i
m by the signer 
i
U .  
 Aggregate: this algorithm takes 
n
1 i i
} {

 as an input, 
any third party can generate the signature  aggregation
agg
 for all the messages with their identities
n
1 i i i
} ID , {m

 .  
 Signature Verification: with input 
agg
 the user 
i
U 
performs two checking operation first; whether 
i
 by 
i
ID is a valid signature on 
i
m and outputs “Valid” if 
true otherwise , “Invalid”. Second; with input 
i
ID and 
n
1 i i i
} ID , {m

 checks the validity of  the aggregate 
signature 
agg
 on 
i
 and outputs “Valid” if true 
otherwise , “Invalid”. 
5 Security algorithm  
5.1 Unforgeability 
The proposed scheme security model follows the scheme 
proposed by [18] with slight variations. The security 
model follows a game with three phases: setup, training 
and forgery phase. Two attacks in this security model are 
considered; adaptive chosen message and identity 
attacks. Thus, the scheme is secure under those attacks 
against any forgery. if the adversary A has not a 
significant advantage in any probabilistic time algorithm 
in this game : 
- Setup: by executing this algorithm the challenger C
obtains the parameters param and the msk and 
deliver the param to the adversary A .  
- Training:  A query the following oracle after the 
setup algorithm: 
 Extract oracle: With 
i
ID  A makes a query  and 
C obtains the private key 
i
d with 
i
ID and deliver 
it to A 
 Signing oracle: A queries the signing oracle with
i
ID , 
i
m  then generates a valid signature 
i
 on 
i
m . 
- Forgery: A generates an aggregate signature 
agg
 
on 
n
1 i i
} m {

 for 
n
1 i i
} ID {

  with input 
n
1 i i
} {

 in which 
at least target identity 
n
1 i i T
} ID { ID

 . The adversary 
A forge the signature if there is a valid 𝜎 𝑎𝑔𝑔
 for 
 
a 
pair ) m , ID (
T T
with the advantage:  
     )} Valid ) ( Verif y ( A {Pr[ Adv
agg A
   
 
6 The proposed scheme 
6.1 Setup 
 In this phase, the PKG selects three additive groups
3 2 1
G , G , G of order q ( prime number)  where 
k
2 q  , 
k is the security parameter. Then the PKG selects two 
pairs of integers ) b , a ( satisfying  
0 q mod ) b 27 a 4 (
2 3
  . Also, the PKG selects a 
generator point P of 
1
G on the elliptic curve E defined 
by q mod ) b ax x ( y
3
   over the finite field 
*
q
F and 
chooses a the following hash functions 
*
q 3 2 1
*
o
F G G G } 0 , 1 { : H     , 
*
q 2 1
*
1
F G G } 0 , 1 { : H    , and 
*
q
*
2
F } 0 , 1 { : H  
 Then, the PKG randomly picks up 
*
q
F s  , s is msk 
and calculates the mpk  P . s P
pub
 . The PKG keeps 
msk secrete and the 
) H , H , H , P , P , q , n G , G , G ( params
2 1 o pub 3 2 1
 public. 
6.2 Key extraction  
This algorithm follows the following steps: 
1. Picks up randomly 
*
q i
F x  and calculates P . x X
i i
  
2. Computes q mod ) q . s x ( d
i i i
  , for the all users
) X || ID ( H q
i i o i
 , n … 1 = i . 
3. The PKG sends the corresponding secrete key  
 
i
d   and the  public key  
i i
q , X to the users 
through a secrete channel 
6.3 Signing 
With input ) ID , d , X (
i i i
 : 
1. Selects  a random number 
*
q R i
F r  and calculates: 
P x W
i i
 
2. Computes : ) ID , m , X , W ( H h
i i i i 1 i 1
 , and 
) ID , m , X , W , h ( H h
i i i i i 1 2 i 2
 
3. Computes: q mod ) h d h r ( v
i 2 i i 1 i i
   , P . v Z
i i
 . 
The signature of 
i
ID on message 
i
m is 
  
i 2 i 1 i i i
h , h , X , Z 
6.4 Aggregate.  
On input ) } ID , ({
n
1 i i i 
 a set of signatures
  
i 1 i 2 i i i
h , h , X , Z , with the identity 
i
ID , n ... 1 i  , 
  
i 1 i 2 i i i
h , h , X , Z are the signatures of the messages
i
m : 



n
1 i
i agg
Z Z , P . v Z
i i
 ,
 
n ... 1 i  
The aggregate signature will be 
agg
n
1 i
i 2 i 1 i i agg
Z , } h , h , X , Z {

   
 
 

A Pairing Free Secure Identity-based… Informatica 42 (2018) 221–228 225 
6.5 Signature verification. 
With the input from
agg
n
1 i i 2 i 1 i i agg
Z , } h , h , X , Z {

    
any user can verify this signature.   The verification 
process as follow:  
 Computes )] P q X ( h Z [ h ' W
pub i i i 2 i
1
i 1 i
  

 to 
recover 
i
W 
 Checks if the following equations holds: 
) W , X , ID , m ( H h
i i i i 1
?
i 1
 and 
) h , W , X , ID , m ( H h
i 1 i i i i 2
?
i 2
 
6.6 Proof of correctness 
)] P q X ( h Z [ h ' W
pub i i i 2 i
1
i 1 i
  

 
 


  
n
1 i
pub i i i 2 i
1
i 1
)] P q X ( h P v [ h 
 



   
n
1 i
pub i i i 2 i 2 i i 1 i
1
i 1
)] P q X ( h P ) h d h r [( h   



    
n
1 i
pub i i i 2 i 2 i i i 1 i
1
i 1
)] P q X ( h P ) h ) sq x ( h r [( h 



    
n
1 i
pub i i i 2 pub i i i 2 i 1 i
1
i 1
)] P q X ( h ) P q X ( h P h r [( h
i
W  
7 The proposed scheme security 
proof 
The security proof demonstrates that ECDLP could be 
solved without significant probability 
o
 . Also, An 
adversary A may forge this scheme without significant 
probability 
o
 against chosen message and identity 
attacks   
7.1 Theorem1.  
The signature scheme is secure against chosen message 
and identity attacks if there is an adversary A with a 
polynomially bounded ) , t (
'
 query for 
o
H
q , 
1
H
q , 
2
H
q , 
S
q and 
E
q who can forge the proposed scheme with a 
non-negligible advantage '  , C may forge the signature 
with a non-significant advantage:

   
 

1
0
1 2
H
1 k
H
Extract
H H sign sign
o
q
1
.
2
)
q
q
1 ).( q q q )( 1 q .( 10
.
9
1
   
(1)  
Proof: 
a) Setup 
The challenger C selects a group 
1
G with a generator 
point P. Then, C randomly selects 𝑎 ∈ 𝑍 𝑞 ∗
 and calculate
P . a P
' pub
 . C obtains the following four hash oracles:
2 1 o
H , H , H then deliver the public 
) P . a , H , H , H , G , G ( param
2 1 o 2 1
 to A  
A asks C for different queries as follow: 
b) 
o
H query 
o Firstly, C delivers the system parameters to A, then C 
with input ID , X selects q randomly and returns it to 
A. 
o In another case, A might know the public component 
X that corresponds to an identity ID. When A makes a 
query for ID, there are two cases:    
 In the case of :
n
1 i
} ID { ID

 , the challenger C 
suits 
i
ID ID  , computes P . x X  , x is 
anonymous, C wants to solve the ECDLP for x , 
as it is part of ECDLP. After this, C stores 
  ID , q , in list H
o
. 
 If 1 i  , C selects  
*
q
Z q , x  randomly, sets 
P . x X  , delivers   X , q to the signer such that  
) X || ID ( H q
o
 and stores   ID , q , x 
c) Extract query  
When A queries for the private key of ID , C does 
the following 
o C checks the list H
o
  to verify whether or not there is 
an entry for ID . If list H
o
 does not contain an  entry 
for ID , return  
o Otherwise, if the entry corresponding to ID in list H
o
is of the form   q , x , X , ID and returns   ,*,* X , x , 
if 
n
1 i
} ID { ID

  then 𝐶 recovers the tuple  
  ID , q , x , X  from list H
o
  and returns   ID , q , X 
and compute aq x d   then returns d to A . 
d) 
1
H query 
When ) W , ID , m ( , is submitted to 
1
H queries 
for the first time C returns checks of  list H
1
 whether the 
tuples ) W , ID , m ( in list H
1
 C returns
1
h , otherwise C 
chooses a new random
*
q R 1
F h  includes 
  W , ID , m , h
1
  to the list H
1
 then C returns 
1
h  
e) H 2 queries 
When   W , ID , m , h
1
 , is submitted to 
2
H queries 
the first time C returns checks of  list H
2
 whether the 
tuples   W , ID , m , h
1
 in list H
2
,C returns
2
h , 
otherwise C chooses a new random 
*
q R 2
F h  includes 
  W , ID , m , h , h
1 2
  to the list H
2
 then C returns
2
h 
f) Sign Oracle 
For each new query ) ID , m (
i
, C proceeds as follows: 
 If 
l i
ID ID  , C signs a message m as follows: 
 If the public key of 
i
ID has been replaced: 
1) Obtains  
i i
q , X by calling 
o
H query oracle on ID 
2) Selects 
*
q R
F r  randomly,  calculates: P . r W  . 

226 Informatica 42 (2018) 221–228 E. Abouelkheir et al.  
3) Computes: ) X , ID , W , m ( H h
i i i 1 1
 by calling 
1
H 
query on input  
i i
X , ID , W , m , and   
) h , X , ID , W , m ( H h
1 i i i 1 2
 by calling query H
2
on 
input  
1 i i i
h , X , ID , W , m , and 
Obtains the secrete key d from the extract query and 
computes: q mod ) dh rh ( v
2 1
  , P . v Z  .  
The signature of ID on message m is 
  
2 1
h , h , X , Z . Otherwise, C signs m in the usual 
manner by using 
i
x (obtained from the 
o
H query) and 
i
d (obtained from extract query) 
 If 
l i
ID ID  , C does the following: 
1) Generates a random 
*
q 2 1
F v , h , h  
2) Sets 
2 i 2 1 i 1 i
h h , h h , v v     
3) Computes: P v Z
i i
 , and  
)] P q X ( h Z [ h W
' Pub l l i 2 i
1
i 1 i
  

 
4) Updates the lists list H
1
and list H
2
respectively with 
the following tuples  
i i i i 1
m , ID , W , h and 
 
i 1 i i i i 2
h , m , ID , W , h . Generate a different 
*
q 2 1
F v , h , h  then repeat steps 3 and 4 if any entry 
in the list list H
1
or list H
2
is similar as the tuples 
generated. 
5) C returns the signature  
i 2 i 1 i i
h , h , X , Z on 
i
m by 
i
ID . 
Note the generated signature is valid due to: 
' Pub ' Pub l i 1 i i 1 l i 2
P q h W h X h   
P q h )] P q X ( h Z [ h [ h X h
l i 1 ' Pub l l i 2 i
1
i 1 i 1 l i 2
    

 
P q h P q h X h Z X h
l i 1 ' Pub l i 2 l i 2 i l i 2
     
P v Z
i i
  
This shows that  
i 2 i 1 i i
h , h , X , Z will able to be a 
valid signature to the adversary A. 
7.2 Forgery phase 
7.2.1 Lemma 1 
After the adversary A generate  
agg n 1 n 1
Z , X ... X , Z ... Z 
on the message 
n
1 i i
} m {

 by user identities 
n
1 i i
} ID {

. A can 
generate a valid  
agg n 1 n 1
Z , X ... X , Z ... Z with 
probability '   if there exists 
l
ID where } n ,.., 1 { l  . The 
algorithm could be flunk in the following places : 
- For the extract oracle if the adversary queries for the 
l
ID then the algorithm flunks. If 
E
q is the maximum 
extract queries number made by the adversary. The 
probability of non-querying for the extract phase is: 
*
H
Extract
l i Extract
o
q
q
1 ] ID ) ID ( q [ P                          (2)    
where 
*
H
o
q is the queries maximum number . 
A may success if 
n
1 i i l
} ID { ID

 or if the adversary A 
make a query for the signing oracle on 
i
m with user 
identity 
l
ID . This happen if: 
*
H
l i
l i
o
q . 2
n
] i l , n ,..., 1 l ID D
and n ,.., 1 i  , ID ID Pr[
    
  
                        (3) 
From the previous  probabilities, A can break the 
scheme under adaptive chosen message and identity 
attack with the advantage: 
*
H
*
H
E
o o
q . 2
n
)
q
q
1 .( '                                                      (4) 
The adversary A may generate a valid aggregate 
signature without signer secrete key with the probability  
k
H H sign sign
2
) q q q )( 1 q ( 10
1 2
  
                                (5).                        
7.2.2 Lemma 2 
A made queries for Extract , 
query H
o
, 
query H
1
, 
query H
2
, 
Sign
 query as the previous queries.  A may 
generate a valid aggregate signature  with probability 
9
1
' '   for n users. C computes s W' as same as the 
previous, and then generate a valid signature 
 
agg i i
Z , X , Z . Using two valid signatures C does the 
following: 
P ). h d h r ( P . v Z
n
1 i
i 2 i
n
1 i
i 1 i
n
1 i
i agg   
  
  
P ). ' h d h r ( ' Z
n
1 i
i 2 i
n
1 i
i 1 i agg  
 
  
P ). ' h h ( d ' Z Z
n
1 i
i 2 i 2 i agg agg 

   
P ). ' h h ( d P ). ' h h ( d ' Z Z
l 2 l 2 l
n
l i , 1 i
i 2 i 2 i agg agg
    

 
 
Thus C knows all the private keys multiplied the 
point P over the elliptic curve by P ). ' h h ( d
l 2 l 2 l
 . Also, 
C knows P . d
l
by multiplying the final equation by 
1
l 2 l 2
) ' h h (

 , but C cannot get 
l
d unless solving the 
ECDLP and it is hard under the assumption (ECDLP). C 
might solve ECDLP with probability: 
9
1
.
q 2
n
).
q
q
1 .(
2
) q q q )( 1 q ( 10
*
H
*
H
Extract
k
H H sign sign
o
o o
1 2

  
 
(6) 
*
H
1 k
*
H
Extract
H H sign sign
o
o
1 2
q
1
.
2
n ).
q
q
1 )( q q q )( 1 q ( 10
.
9
1

   
   
(7) 
 
By this, the proposed identity based aggregate 
signature over is secure against any forgery with a non-

A Pairing Free Secure Identity-based… Informatica 42 (2018) 221–228 227 
significant probability
o
 . Under this assumption C 
might solve the ECDLP 
8 Results and discussion 
When analyzing time complexity of the proposed 
scheme, it is found that it consumes only two point 
multiplication over elliptic curve in an individual signing 
process. Through the verification process, the proposed 
scheme consumes two point multiplication, one modular 
inverse operation and two point addition over the elliptic 
curve. All the computations are relative to the modular 
multiplication process. The proposed scheme consumes 
127.84 
ML
T in one individual complete signing and 
verification process 
9 Comparative study 
This section shows the comparative study between the 
proposed signature scheme without pairing with the 
scheme with pairings in [28] in the case of individual 
signing. The computations are all relative to the modular 
multiplication.  Table II indicates the definitions for the 
cryptographic operations. 
Notation Description 
ML
T 
The time complexity needed to execute the 
modular multiplication 
EM
T 
The time complexity needed to execute 
elliptic curve scalar point multiplication, 
ML EM
T 29 T 1  
BP
T 
The time complexity needed to execute the 
pairings operation, 
ML EM BP
T 87 T 3 T 1    
PX
T 
The time complexity needed to execute 
pairing-based exponentiation, 
ML BP PX
T 5 . 43 T
2
1
T 1   
EA
T 
The time complexity needed to execute the 
point addition over elliptic curve, 
ML EA
T 12 . 0 T 1   
IN
T 
The time complexity needed to execute the 
modular inversion operation, 
ML IN
T 6 . 11 T 1  
Table 2: Definition of different cryptographic operations. 
The scheme in [28] uses the  identity-based signature 
from pairings. Craig and Zulfikar scheme consumes 
406.24 
ML
T in an individual signing operation  while, 
the proposed pairing free scheme consumes 127.84 
ML
T 
in an individual operation and therefore the proposed 
scheme shows lower time complexity than in [28], as it 
saves 68.69% from the computations as in table III. 
10 Conclusion 
This paper introduces a new aggregate signature scheme 
without pairings. It saves 68.69% of computational cost 
than another scheme in [28] in pairings. The security 
proof of the proposed scheme shows that it is secure in 
random oracle model. The aggregate signature schemes 
are very useful when needing authentication in vehicular 
ad hoc network and e-commerce applications.  
11 Future scope 
The idea of the aggregate signature used in securing the 
communication networks such as vehicular  area network 
VANETs and Mobile area networks MANETs. Also , 
aggregate signature used in the e-commerce applications. 
The proposed scheme should be used in VANETs to 
provide aggregate authentication with low computational 
cost.  
 Signature Verification Tota
l ( in 
ML
T
) 
EM
T
 
BP
T
 
IN
T
 
EA
T
 
EM
T
 
BP
T
 
IN
T
 
EA
T
 
Crai
g, 
and 
Z ulfi
kar  
4 - - - 1 3 - 2 
406.
24 
ML
T
 
IDB-
ASC 
2 - - - 2 - 1 2 
127.
84 
ML
T
 
Table 3: Comparison of computational cost. 
12 References 
[1] K. C. Barr and K. Asanovic. Energy Aware 
Lossless Data Compression. In Proceeding of 
Mobisya 2005 
[2] A. Prace. Privacy Preserving Cryptographic 
Protocols For Secure Heterogeneous Networks. 
Thesis of Doctoral, 2014 
[3] X. Boyen and B. Waters. Full Domain Subgroup 
Hiding and Constant Size Group Signatures In 
Public Key Cryptography. Lecture notes in 
computer science, vol. 4450, pp.1-15, 2007 
[4] D. Boneh, X. Boyen and H. Shacham. Short Group 
Signatures. In Advances in Cryptology- CRYPTO 
2004, Springer , pp. 227-242. 
[5] D. Boneh, C. Gentry, B. Lynn and H. Shacham. 
Aggregate and verifiably encrypted signatures from 
bilinear maps. In Proceeding of Eurocrypt 2003, 
vol. 2656 of LNCS, pp. 416–432.  
[6] S. Kent, C. Lynn and K. Seo. Secure border 
gateway protocol (secure-bgp). IEEE Journal 
Selected Areas in Comm., pp.582–592, 2000. 
[7] A. Lysyanskaya, S. Micali, L. Reyzin and Shacham 
H. Sequential aggregate signatures from trapdoor 
permutations. In Proceeding of Eurocrypt 2004, 
vol. 9999 of LNCS, pp. 74–90.  
[8] Z. Cao and L. Liu. On the Disadvantages of 
Pairing-based Cryptography. International Journal 
of Network Security, vol.17, no.4, pp.454-462, July 
2015.  

228 Informatica 42 (2018) 221–228 E. Abouelkheir et al.  
[9] A. Shamir. Identity-based Cryptosystems and 
Signature Schemes. In Proceeding of Crypto 1984, 
vol. 196 of LNCS, pp 47–53.  
[10] D. Boneh and M. Franklin. Identity-based 
Encryption from the Weil Pairing. SIAM Journal of 
Computing, vol.32, no.3, pp.586–615, 2003 
[11] C. Cocks. An Identity Based Encryption Scheme 
Based on Quadratic Residues. In Proc. of IMA Int. 
Conf., vol. 2260 of  LNCS, pp.360–363,   2001 
[12] Fiat A. and Shamir A., “How to prove yourself: 
Practical solutions to identification and signature 
problems”, In Proceeding of Crypto 1986, vol. 263 
of LNCS, pp. 186–194.  
[13] L. C. Guillou and J. J. Quisquater. A Paradoxical 
Identity-Based Signature Scheme Resulting from 
Zero-Knowledge. In Proceeding of Crypto 1988, 
vol. 403 of  LNCS, pp 216–231.  
[14] J. C. Cha and J. H. Cheon. An Identity-Based 
Signature From Gap Di ffie-Hellman Groups. In 
Proceeding of PKC 2003, vol. 2567 of LNCS, 
pp.18–30 . 
[15] X. Boyen. Multipurpose Identity-Based 
Signcryption (A Swiss Army Knife For Identity-
based Cryptography).  In Proceeding of Crypto 
2003, vol. 2729 of LNCS, pp 383–399.  
[16] Libert B. and Quisquater J.-J., “Identity based 
undeniable signatures,”. In Proc. of CT-RSA 2004, 
pp. 112–125. 
[17] M. Bellare, CH. Namprempre and G. Neven. 
Security Proofs for Identity-Based Identification 
And Signature Schemes. In Proceeding Proc. of 
Eurocrypt 2004, vol.3027 of LNCS, pp.268-286.  
[18] S. Sharmila, D. Selvi, S. S. Vivek, J. Shriram and 
C. P. Rangan. Identity Based Partial Aggregate 
Signature Scheme Without Pairing. IACR 
Cryptology eprint Archive , 2010. 
[19] M. S. Murty, D. Veeraiah and A. S. Rao. Digital 
Signature and Watermark Methods  For Image 
Authentication using Cryptography Analysis. 
Signal & Image Processing : An International 
Journal (SIPIJ) Vol.2, No.2, June 2011. 
[20] N.  Dey, P. Das, S. S. Chaudhuri  , and A. Das. A 
Session Based Watermarking technique Within the 
NROI of Retinal Fundus Images for Authencation 
Using DWT  Spread Spectrum and Harris Corner 
Detection. In the Proceeding of the Fifth 
International Conference on Security of 
Information and Networks, 2012. 
[21] N. Dey, A. K. Pal, S. Samanta, A. Das, and S. S. 
Chaudhuri. Optimisation of Scaling Factors in 
Electrocardiogram Signal Watermarking using 
Cuckoo Search. International Journal of Bio-
Inspired Computation vol.5, no. 5, pp.315-326, 
2013. 
[22] N. Dey, G. Dey, S. Chakraborty, and S. S. 
Chaudhuri. Feature Analysis of Blind Watermarked 
Electromyogram Signal in Wireless 
Telemonitoring. In the series Annals of Information 
Systems vol. 16 pp. 205-229, 2014. 
[23] N.  Dey, M.  Dey, S. K. Mahata and  D. Ach. 
Tamper Detection of Electrocardiographic Signal 
using Watermarked Bio-hash Code in Wireless 
Cardiology. Inteligence International Journal of 
Signal and Imaging Systems Engineering , Vol.8, 
no.1-2 , 2015. 
[24] Amar, Y. B., I. Trabelsi, N. Dey, and S. Bouhlel. 
Euclidean Distance Distortion Based Robust And 
Blind Mesh Watermarking. International Journal of 
Interactive Multimedia and Artificial , vo.4, No.2, 
pp.46-51,2016. 
[25] V. S. Miller. Use of elliptic curves in cryptography. 
In the Proceedings of the CRYPTO 1985, LNCS, 
Springer-Verlag vol.218,pp.417-426, 1985. 
[26] N. Koblitz. Elliptic Curve Cryptosystem. Journal of 
Mathematics of Computation vol.48, pp. 203-209, 
1987. 
[27] K. Magons. Applications and Benefits of Elliptic 
Curve Cryptography. University of Latvia, Faculty 
of Computing, Rain¸a bulvaris 19, Riga, LV-1586, 
Latvia  
[28] C. Gentry, and Z. Ramzan. Identity-Based 
Aggregate Signatures. In the Proceeding  of 9th 
International Conference on Theory and Practice in 
Public-Key Cryptography, New York, NY, USA, 
pp.24-26, 2006.