Advanced
Efficient Signature Scheme with Batch Verifications in Identity-Based Framework
Efficient Signature Scheme with Batch Verifications in Identity-Based Framework
ETRI Journal. 2016. Apr, 38(2): 397-404
Copyright © 2016, Electronics and Telecommunications Research Institute (ETRI)
  • Received : October 06, 2014
  • Accepted : December 09, 2015
  • Published : April 01, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
P.V.S.S.N. Gopal
P. Vasudeva Reddy
T. Gowri

Abstract
In group-oriented applications, it is often required to verify a group of signatures/messages. The individual verification of signed messages in such applications comes at a high cost in terms of computations and time. To improve computational efficiency and to speed up the verification process, a batch verification technique is a good alternative to individual verification. Such a technique is useful in many real-world applications, such as mail servers, e-commerce, banking transactions, and so on. In this work, we propose a new, efficient identity-based signature (IDS) scheme supporting batch verifications. We prove that the proposed IDS scheme and its various types of batch verifications is tightly related to the Computational Diffie–Hellman problem under a random oracle paradigm. We compare the efficiency of the proposed scheme with related schemes that support batch verifications.
Keywords
I. Introduction
In group-oriented applications and multicast communications, it is often required to verify a group of signatures/messages. However, individual verification of signed messages comes at a high cost in terms of computations and time. Verification of signatures on a batch basis is essential in many real-world applications, such as mail servers, e-commerce, e-voting, banking transactions, and so on. To improve the verification process and minimize the verification time, a signature scheme with batch verifications — one that verifies multiple signatures simultaneously as a whole — is needed.
The notion of batch cryptography was introduced by Fiat [1] in 1989. Fiat proposed a modified version of RSA suitable for batch signature generation. Many public key infrastructure (PKI)–based schemes with batch verifications have been proposed in the literature [2] [4] . Bellare and others’ scheme [4] gave a systematic approach for batch verification and presented three generic methods for batching modular exponentiations: the random subset test, the small exponents test, and the bucket test.
To overcome the task of maintaining certificate libraries used for revoking, storage, and distribution of certificates that require huge communication overload within a PKI-based setting, Shamir [5] , in 1984, devised a new paradigm called identity-based cryptography (IBC). Under such a paradigm, the public key of a user can be directly derived from the user’s personal information, such as a telephone number, an e-mail address, and so on. The corresponding private key is issued by a trusted authority, termed a key generation center (KGC). Since 1984, many encryption and signature schemes have been constructed in identity-based settings, but the most usable and practical encryption scheme was devised by Boneh and Franklin [6] in 2001 using Weil pairing over elliptic curves. Based on Boneh and Franklin’s work in [6] , many signature schemes in identity-based settings have been proposed [7] [10] .
However, so far, little attention has been paid to design signature schemes that support batch verification. To facilitate the wide use of identity-based signature (IDS) schemes in real applications such as e-commerce, electronic payment systems, and e-government, it is necessary and important to study the design of secure and efficient batch verifications for ID-based signature schemes.
The first IDS scheme supporting batch verifications using pairings over elliptic curves was proposed by Yoon and others [11] in 2004. Based on the number of messages and signers, the authors in [11] classified multiple signatures into the following types:
  • ▪ Type 1: Multiple users sign on a single message.
  • ▪ Type 2: A single user signs on multiple messages.
  • ▪ Type 3: Multiple users sign on multiple messages, where every message is signed by a different user.
Cao and others [12] , in 2006, showed that the scheme in [11] is not secure, since an adversary can deceive a verifier to accept an invalid signature. In the same year, Cui and others [13] proposed an IDS scheme supporting batch verifications of Types 2 and 3 above with a different key construction. In 2007, Chiang and others [14] proved that the scheme in [13] is insecure.
Zhang and others [15] , in 2008, proposed an efficient identity-based batch verification scheme for vehicular sensor networks using elliptic curves. Tseng and others [16] discussed the twelve schemes of Cha and Cheon [7] , such as signature schemes, and obtained an efficient IDS scheme that supported different types of batch verifications, in 2009. Hwang and others [17] proposed a new, efficient batch verification for an IDS scheme using pairings, in 2015. Ren and others [18] , in 2015, proposed an efficient batch verification scheme for detecting illegal signatures without pairings over elliptic curves.
The schemes in [11] and [16] require a linear number of pairing operations with that of signers for a batch verification of Type 3. As discussed in [19] and [20] , the security reductions of the schemes in [11] and [16] are not tight, since these schemes use the forking lemma [21] to prove their security.
In this paper, we propose a new, efficient IDS scheme supporting batch verifications. This scheme uses bilinear pairings over elliptic curves and is secure under a random oracle paradigm with the assumption that the Computational Diffie–Hellman (CDH) problem is hard. The proposed IDS scheme provides tight reductions due to the fact that its security is not proven through use of the forking lemma [21] .
The rest of this paper is organized as follows. Section II presents some preliminaries, including bilinear maps and complexity assumptions. The proposed IDS scheme is depicted in Section III. A security analysis of the IDS scheme is presented in Section IV. Batch verifications of the proposed IDS scheme are introduced in Section V. A security analysis of the batch verifications of the proposed IDS scheme is presented in Section VI. A complexity analysis for the batch verifications of the proposed IDS scheme is presented in Section VII, and Section VIII concludes our work.
II. Preliminaries
This section summarizes some fundamental concepts and necessary hard problems.
- 1. Bilinear Map
Let ( G , +) and ( GT , ·) be additive and multiplicative cyclic groups, respectively, of the same prime order q ; that is, | G | = | GT | = q . Let P be a generator in G . A map
e ^ :G×G→ G T
is bilinear if the following properties are satisfied:
  • ▪ Bilinear: For allA,B∈G, and for anyx, y∈Zq*,e^(xA, yB)=e(A, yB)x=e^(xA, B)y=e(A, B)xy.
  • ▪ Non-degeneracy: There is an element inG, sayA∈G, such thate^(A, A)≠1.
  • ▪ Computable: For anyA,B∈G, the mape^(A, B)is computable using an efficient algorithm.
Upon making suitable variations in the Weil or Tate pairing, one can obtain such maps on elliptic curves over a finite field [6] , [22] .
- 2. Notations and their Descriptions
Table 1 illustrates the notations and their descriptions used in the proposed scheme.
Notations and their descriptions.
Notations Description
(G, +) A cyclic group under addition
(GT, ·) A cyclic group under multiplication
q Order of the groups G and GT
e ^ A symmetric bilinear map defined from G × G to GT
P A generator of the group G
ID The identity of a user
Ppub The system’s overall public key
H1 A cryptographic hash function defined by H1 :{0, 1}*G
H2 A cryptographic hash function defined by H 2 : {0, 1} * × G T Z q *
QID The public key of a user with identity ID
dID The private key of a user with identity ID
σ A signature on the message m made by the signer with identity ID
- 3. Computational Problems
In the following, we present some computationally hard problems on which the proposed scheme’s security is based.
A. CDH Problem
For a given
x, y∈ Z q *
and CDH tuple, P , xP , yP G , the CDH problem is to find xyP G . Given an adversary 𝒜, the advantage of this adversary, Adv (𝒜), to solve the CDH problem in G in polynomial time with running time t is defined as follows:
Adv CDH, t (𝒜)=Pr[𝒜(P, xP, yP)=xyP/x, y∈ Z q * ].
B. CDH Assumption
For any probabilistic polynomial time algorithm 𝒜, the advantage, Adv CDH, t (𝒜) , is negligibly small.
III. New IDS Scheme
In this section, we present our new IDS scheme. This scheme comprises four algorithms: System Setup, Key Extract, Signature Generation, and Signature Verification. Detailed functionalities of these algorithms are as follows.
- 1. System Setup
For a given security parameter l Z + , the KGC runs this algorithm to generate the following system parameters:
  • ▪ Generates additive and multiplicative cyclic groups, say (G, +) and (GT, ·), respectively, of the same prime orderq; that is, |G| = |GT| =q.
  • ▪ Generate a generatorP∈Gand an admissible bilinear mape^such thate^:G×G→GT.
  • ▪ Generate an integers∈Zq∗at random and computePpub=sP, g=e^(Ppub, P).
  • ▪ Picks cryptographic hash functionsH1:{0, 1}*→G andH2:{0, 1}*×GT→Zq∗.
  • ▪ Publishes the system’s public parameters as Params = and keeps securely as the master private key.
- 2. Key Extract
This algorithm, run by the KGC, receives an identity ID∈{0, 1}* of a user and then computes Q ID = H 1 (ID) and d ID = sQ ID G . The KGC securely transmits ( Q ID , d ID ) to the user with identity “ID.” The user keeps d ID securely and makes Q ID public.
- 3. Signature Generation
The user provides the following information as input for this algorithm: identity ID, private key d ID , Params, and message m ∈{0, 1}*. The computations performed are as follows:
  • ▪ Select an integerr∈Zq*at random and computeU=gr∈GT,h=H2(m, ID, U)∈Zq*,andV=hdID+rPpub∈G.
  • ▪ Generate the signature on messagemof the user with identity ID asσ= (U,V)∈GT×G.
- 4. Signature Verification
Any verifier can run this algorithm, which takes the signature σ on a message m by a user with identity ID as input. The verification is done as follows:
  • ▪ Compute the hash valueh=H2(m, ID, U)∈Zq*.
  • ▪ Verify the validity of the equatione^(P, V)=e^(Ppub, hQID)U.If it is valid, then accept the signature; else, reject the signature.
IV. Security Analysis
This section presents a proof of correctness and a security reduction of the proposed IDS scheme under an adaptively chosen message and ID attack under a random oracle paradigm.
- 1. Proof of Correctness
The following equation shows that the proposed IDS scheme is correct; the verification equation is valid:
e ^ (P, V) = e ^ (P, h d ID +r P pub ) = e ^ (P, h d ID ) e ^ (P, r P pub ) = e ^ (sP, h Q ID ) e ^ (sP, P) r   = e ^ ( P pub , h Q ID ) U.
- 2. Security Reduction
In the following, we prove that the proposed scheme is unforgeable under chosen message and identity attacks under a random oracle paradigm, with the assumption that the CDH problem is hard.
Theorem 1. Let 𝒜 be a probabilistic polynomial time forger who forges the proposed IDS scheme with non-negligible advantage. Then, there is an algorithm 𝐵 that can output the given CDH instance ( P , aP , bP )∈ G with a non-negligible advantage in probabilistic polynomial time.
Proof. Let 𝒜 be a forger who breaks the proposed IDS scheme. We show that by using 𝒜 one can construct an algorithm 𝐵 that can solve the CDH problem. Algorithm 𝐵 is given ( P , aP , bP ) as a random instance of the CDH problem in G ; that is, its goal is to output abP G . Algorithm 𝐵 simulates an original signer to obtain a valid signature from 𝒜, and by doing so, it can solve the CDH problem.
A. Setup/Queries
Algorithm 𝐵 sets P pub = aP as the system’s overall public key and provides 𝒜 with Params. At any time, 𝒜 may make queries to oracles H 1 , H 2 , key extract, and signature. We presume that prior to any query from key extract, both a signature query and a H 1 query have already been made on an identity ID. To respond to these queries, algorithm 𝐵 does the following:
  • ▪H1– queries: Algorithm 𝐵 keeps a list,L1, which is empty initially of tuples, (ID,c,d,v) to respond toH1– queries. Upon receiving a query from theH1oracle for ID∈{0, 1}*, made by 𝒜, algorithm 𝐵 proceeds as follows:(i) IfL1consists of the queried ID, then algorithm 𝐵 responds withH1(ID) =v∈G.(ii) If not, then algorithm 𝐵 flips a coind∈{0, 1} generated at random, such that Pr[d= 0] =1/ (qK+1). Here,qKdenotes a query made to the key extraction oracle.(iii) Now, algorithm 𝐵 picks a random integerc∈Zq*and computesv=c(bP)∈Gford= 0, andv=cP∈Gford= 1.(iv) Algorithm 𝐵 adds (ID,c,d,v) to listL1and returnsH1(ID) =v∈Gto 𝒜
  • ▪H2– queries: Algorithm 𝐵 keeps a listL2of tuples, (m, ID,U,w), which is empty initially. To respond toH2queries made by 𝒜 on tuple (m, ID,U), algorithm 𝐵 proceeds as follows:(i) IfL2contains queried tuple (m, ID,U), then algorithm 𝐵 providesH2(m, ID, U)=w∈Zq*.(ii) If not, then algorithm 𝐵 picks a random integerw∈Zq*,inserts (m, ID,U,w) inL2and returnsH2(m, ID, U)=w∈Zq*to 𝒜.
B. Key Extraction Queries
Upon receiving the private key queries on an identity ID by 𝒜, algorithm 𝐵 retrieves the respective tuple (ID, c , d , v ) from L 1 and does the following:
  • 1) It outputs “failure” and then halts, ford= 0.
  • 2) Ifd = 1, then it computes and returnsdID=cPpub=c(aP) =a(cP) ∈Gto 𝒜.
C. Signature Queries
Upon receiving the signature query on a message m under ID from 𝒜, algorithm 𝐵 retrieves the H 1 oracle and obtains the tuple (ID, c , d , v ) from L 1 . Algorithm 𝐵 then selects a random integer
x∈ Z q *
and computes U = gx . In addition, if the list L 2 contains the tuple ( m , ID, U , w ), then 𝐵 chooses
w ′ ∈ Z q *
and tries again; that is, 𝐵 adds ( m , ID, U , w' ) to L 2 . Now, 𝐵 computes V = ( wc + x ) P pub and returns σ = ( U , V ) to 𝒜 as the queried signature.
The responses to signature queries are valid, as well the output σ . This can be seen from the following:
e ^ (P, V) = e ^ ( P, (wc+x) P pub ) = e ^ (P, wc P pub ) e ^ (P, x P pub ) = e ^ (aP, wcP) e ^ (aP, xP) = e ^ ( P pub , w Q ID )U.
D. Forgery
Eventually, 𝒜 stops by conceding failure or returns a forgery σ on m under ID. Algorithm 𝐵 obtains (ID, c , d , v ) from L 1 , declares failure if d = 1, and stops. If not, then it computes Q ID = c ( bP ) for d = 0. The forged signature σ must satisfy
e ^ (P, V)= e ^ ( P pub , w Q ID )U.
Now, 𝐵 retrieves the respective tuple ( m , ID, U , w ) from L 2 and computes V = ( wc + x ) P pub ; thus, we have
e ^ ( P pub , w Q ID )U = e ^ ( P pub , w(c(bP)) ) e ^ ( P pub , P) x = e ^ ( P pub , wcbP+xP) = e ^ (P, wcabP+x P pub ) = e ^ (P, V) ⇒ V=wcabP+x P pub .
Now, 𝐵 outputs abP as a solution to the CDH instance by computing abP = w −1 c −1 ( V xP pub ). This concludes the description of algorithm 𝐵.    ■
V. Batch Verifications of Proposed IDS Scheme
This section presents batch verifications of different types for the proposed IDS scheme. To verify a k -batch signature,{(ID i , mi , σi )} i=1, 2, …, n , for n k , the verifier uses the following batch verify algorithms:
  • 1) For Type 2 batch verifications: In this case, we have ID = ID1= … = IDn. The verifier computesQIDi=H1(IDi)∈Gandhi=H2(mi,Ui), fori= 1, 2, … ,n. In addition, the verifier computesU=∏i=1nUi,whereUi=gri. The Type 2 batch verification algorithm outputs “1” if the following equation holds; otherwise, it outputs “0”:
e ^ ( P, ∑ i=1 n V i )= e ^ ( P pub , ∑ i=1 n h i Q ID )U.
  • 2) For Type 3 (or 1) batch verifications: The verifier first computesQIDi=H1(IDi) ∈Gandhi=H2(mi,Ui), fori= 1, 2, … ,n. In addition, the verifier computesU=∏i=1nUi,whereUi=gri. The Type 3 (or 1) batch verification algorithm outputs “1” if the following equation holds; otherwise, it outputs “0”:
e ^ ( P, ∑ i=1 n V i )= e ^ ( P pub ,  ∑ i=1 n h i Q ID i )U.
One can verify that the batch verifications of the proposed IDS scheme are correct as shown below.
Proof of Correctness . For Type 2 batch verifications, we have the following:
e ^ ( P,  ∑ i=1 n V i ) = e ^ ( P,  ∑ i=1 n ( h i d ID + r i P pub ) ) = e ^ ( P pub , ∑ i =1 n h i Q ID ) e ^ ( P pub , ∑ i=1 n r i P ). = e ^ ( P pub , ∑ i=1 n h i Q ID )U.
For Type 3 (or 1) batch verifications, we have the following:
e ^ ( P,  ∑ i=1 n V i ) = e ^ ( P,  ∑ i=1 n ( h i d ID i + r i P pub ) ) = e ^ ( P pub ,  ∑ i=1 n ( h i Q ID i + r i P) ) = e ^ ( P pub ,  ∑ i=1 n ( h i Q ID i ) ) e ^ ( P pub , ∑ i=1 n r i P ) = e ^ ( P pub ,  ∑ i=1 n h i Q ID i )U.
VI. Security Analysis of Batch Verifications of Proposed IDS Scheme
In this section, we will show that the proposed IDS scheme provides k -batch existential unforgeability against adaptive chosen message and ID attacks.
Definition 1. The proposed k -batch IDS scheme offers existential unforgeability under adaptively chosen message and ID attacks if there is no probabilistic polynomial time adversary/forger 𝒜 with non-negligible advantage in the following game played between 𝒜 and a challenger, 𝒞 :
  • 1) Setup: This phase is similar to the one in Theorem 1.
  • 2) Queries: Forger 𝒜 makes similar queries as in Theorem 1.
  • 3)k-batch forgery: For some integern≤k, the forger 𝒜 outputsnsignatures (IDi,mi,σi) , fori= 1, 2, … ,n. Note that there exists at least one indexisuch that IDiis not asked the extract query and (IDi,mi) in the key extraction oracle and a tuple (IDi,mi) is also not asked in the sign query; that is, the forger 𝒜 owns at most (n− 1) private keys ofnidentities. Forger 𝒜 wins the game if the batch verify algorithm outputs “1.” The advantage of the forger 𝒜 is as the probability that 𝒜 wins.
- 1. Security ofk-Batch Signature for Type 2
A security proof for Type 2 batch verifications of the proposed IDS scheme is presented below.
Theorem 2. Let 𝒜 be a probabilistic polynomial-time forger who can forge the Type 2 k -batch signature of the proposed IDS scheme with a non-negligible advantage under a random oracle paradigm. Then, there is an algorithm 𝒜 that can output the given CDH instance with non-negligible advantage in probabilistic polynomial-time.
Proof. Assume that 𝒜 is a forger who can forge a Type 2 k -batch signature under adaptively chosen message and ID attacks with a non-negligible advantage. As in Theorem 1, we show that there exists an algorithm 𝐵 that solves the given instance of the CDH problem using 𝒜. Algorithm 𝐵 runs the setup algorithm to obtain the public and private keys. The public key is sent to 𝒜. As discussed in Theorem 1, 𝒜 issues queries and is answered by 𝐵.
Algorithm 𝐵 obtains the corresponding tuple (ID i , ci , di , vi ) from list L 1 , declares failure if d = 1, and stops. If not, it computes Q ID = c ( bP ) for d = 0.
The signature σ = ( U , V ) must satisfy the equation
e ^ ( P, ∑ i=1 n V i )= e ^ ( P pub , ∑ i=1 n h i Q ID )U.
Now, 𝐵 recovers the corresponding tuple ( mi , ID, Ui , wi ) from list L 2 and computes V 1 = ( w 1 c + x 1 ) P pub . Consider
e ^ ( P pub ,  w 1 Q ID ) e ^ ( P pub ,  x 1 P)= e ^ (aP,  w 1 c(bP)+ x 1 P) e ^ (P,  w 1 c(abP)+ x 1 P pub )= e ^ (P,  V 1 ). ⇒ V 1 = w 1 c(abP)+ x 1 P pub ⇒ w 1 c(abP)= V 1 − x 1 P pub .
Now, 𝐵 outputs abP as a solution to the CDH instance by computing abP = w 1 −1 c −1 ( V 1 x 1 P pub ).    ■
- 2. Security ofk-Batch Signature for Types 1 and 3
In the following, we prove the security of batch verifications of Types 1 and 3 of the proposed IDS scheme. Notice that a Type 1 batch verification is a subcase of Type 3. Thus, it is enough to prove the security of a k -batch signature of Type 3.
Theorem 3. Let 𝒜 be a probabilistic polynomial-time forger who can forge a Type 3 k -batch signature of the proposed IDS scheme with a non-negligible advantage under a random oracle paradigm. Then, there is an algorithm 𝐵 that can output the given CDH instance with non-negligible advantage in probabilistic polynomial-time.
Proof. Let ID i , for i = 1, 2, … , n , denote the identities of distinct signers participating in a signing. From Definition 1, an adversary owns at most ( n − 1) private keys of n signers. Assume that there exists a probabilistic polynomial-time adversary 𝒜 that can forge a k -batch signature of the proposed IDS scheme of Type 3 for adaptively chosen message and ID attacks with a non-negligible advantage.
As in Theorem 1, there exists a probabilistic polynomial-time algorithm 𝐵 that returns a forged k -batch signature of Type 3, σ on messages { mi } under {ID i }, for i = 1, 2, … , n , and 𝒜 must not have requested a signature on m 1 under ID 1 .
Algorithm 𝐵 obtains (ID i , ci , di , vi ) from L 1 and continues if d 1 = 0 and di = 1 for 2 ≤ i n . If not, then 𝐵 declares failure and stops. We have Q ID1 = c 1 ( bP ) for d 1 = 0 and Q IDi = ciP for di = 1, i > 1. The forged Type 3 k -batch signature σ must satisfy the equation
e ^ ( P, ∑ i=1 n V i )= e ^ ( P pub , ∑ i=1 n w i Q ID i )U.
Now, 𝐵 retrieves the n respective tuples (ID i , mi , Ui , wi ) from L 2 and computes Vi = ( wici + xi ) P pub , for i > 1; thus, we have
e ^ (P,   V i ) =  e ^ (P,( w i c i  + x i ) P pub ) = e ^ ( P pub , w i Q ID i ) U i ,
which implies σi is valid. Now, 𝐵 considers
V 1 =V− ∑ i=2 n V i ,
and outputs
e ^ (P,  V 1 )= e ^ ( P, V− ∑ i=2 n V i )= e ^ (P,  w 1 c 1 abP+ k 1 P pub ). ⇒  V 1 = w 1 c 1 abP+ x 1 P pub ⇒ w 1 c 1 abP= V 1 − x 1 P pub .
Now, 𝐵 outputs abP as a solution to the CDH instance by computing abP = w 1 −1 c −1 ( V 1 x 1 P pub ).    ■
VII. Complexity Analysis
In this section, we present the complexity issues and compare the computational efficiency of the proposed IDS scheme supporting batch verifications with related schemes. For comparison, we consider the time-consuming operations. According to [23] and [24] , 1 T p ≈ 1200 t m , 1 T m ≈ 29 t m , and 1 T a ≈ 0.12 t m , where T a denotes the time for evaluating a point addition in G , T m denotes the time for evaluating a point scalar multiplication over G , T p denotes the time to compute one pairing operation, and t m denotes the time to perform a modular multiplication in
Z q * .
An efficiency comparison of the proposed IDS scheme supporting batch verifications with related schemes; Yoon and others [11] ; and Tseng and others [16] is presented in Table 2 .
Efficiency comparison.
Scheme Type 2 batch verifications Types 3 batch verifications
Yoon and others [11] 2Tp + nTm + (2n−2)Ta = (29.24n + 2399.76)tm (n + 1)Tp + nTm + (2n−2)Ta = (1229.24n + 1199.76)tm
Tseng and others [16] 2Tp + nTm + (2n−2)Ta = (29.24n + 2399.76)tm (n + 1)Tp + nTm + (2n−2)Ta = (1229.24n + 1199.76)tm
Proposed scheme 2Tp + nTm = (29n + 2400)tm 2Tp + nTm + (n−1)Ta = (29.12n + 2399.88)tm
Compared with the other operations, the pairing evaluation is the most costly in terms of time. Despite the fact that much research has taken place to speed up the pairing computation [22] , it is still time consuming. The proposed IDS scheme is efficient when compared to the schemes in [11] and [16] for batch verifications of Types 2 and 3. In particular, for batch verifications of Type 3, the pairing operations in the schemes in [11] and [16] grow linearly with that of the signers, whereas the proposed IDS scheme requires a constant number (only two) of pairing operations irrespective of the number of signers, which reduces greatly the computational complexity. Hence, the proposed IDS scheme supporting batch verifications is more efficient than the related existing schemes.
VIII. Conclusion
In this paper, we have proposed a new, efficient IDS scheme using bilinear pairings supporting batch verifications. We have proved that various types of batch verifications for the proposed IDS scheme are unforgeable under a random oracle paradigm with the assumption that the CDH problem is intractable. In addition, a security reduction of the proposed IDS scheme and its batch verifications has been obtained without the use of a forking lemma [21] , and so is tightly related to the CDH problem. For batch verifications of Type 3, the proposed IDS scheme requires a constant number of pairing operations, which greatly improves the computational efficiency. In summary, the performance of our scheme is good, which makes the scheme applicable in practice. Both the security and high efficiency of the batch verifications mean that it is possible to apply them in environments where computational issues are seen as the main constraints, such as in ad-hoc networks. In future, we will extend our batch verification schemes for various forms of anonymous authentication, such as group signatures, e-cash, e-voting, intelligent cars to control traffic, and anonymous credentials.
BIO
gopalcrypto786@gmail.com
P.V.S.S.N. Gopal received his MS degree in applied mathematics and MPhil in (commutative algebra) mathematics from Pondicherry University, Puducherry, India, in 2001 and 2008, respectively. He received his PhD degree in applied mathematics from Andhra University, Visakhapatnam, India, in 2015. His research interests include abstract algebra, linear algebra, number theory, and elliptic curve cryptography. He is a lifetime member of the Cryptology Research Society of India.
Corresponding Author vasucrypto@yahoo.com
P. Vasudeva Reddy received his MS and PhD degrees in mathematics from Sri Venkateswara University, Tirupati, India, in 1998 and 2006, respectively. He received his MTech degree in computer science and technology-networks from Andhra University, Visakhapatnam, India, in 2010. He is currently working as a professor with the Department of Engineering Mathematics, Andhra University. His research interests include algebra & number theory applications and cryptography. He has several publications in national and international reputed journals. He is an associate editor for the International Journal of Cryptography and Security. He is a member of the International Association of Engineers, and lifetime member of both the Cryptology Research Society of India and the Indian Mathematical Society.
gowri3478@yahoo.com
T. Gowri received her BTech degree in electronics and communications engineering from Nagarjuna University, Guntur, India, in 2000 and her MTech degree in electronics and communications engineering from Jawaharlal Nehru Technological University (A), Anantapur, India, in 2006. She is currently working as an assistant professor with the Department of Electronics and Communication Engineering, Gandhi Institute of Technology and Management University, Visakhapatnam, India. Her research interests include computer electronics, digital signal processing, and information security.
References
Fiat A. “Batch RSA,” Adv. Cryptology Santa Barbara, CA, USA Aug. 20–24, 1989 175 - 185
Lim C.H. , Lee P.J. 1994 “Security of Interactive DSA Batch Verification,” IEEE Electron. Lett. 30 (19) 1592 - 1593    DOI : 10.1049/el:19941112
Yen S.M. , Laih C.S. 1995 “Improved Digital Signature Suitable for Batch Verification,” IEEE Trans. Comput. 44 (7) 957 - 959    DOI : 10.1109/12.392857
Bellare M. , Garay J.A. , Rabin T. “Fast Batch Verification for Modular Exponentiation and Digital Signatures,” Int. Conf. Theory Appl. Cryptographic Techn. Espoo, Finland May 31–June 4, 1998 236 - 250
Shamir A. “Identity-Based Cryptosystems and Signature Schemes,” Adv. Cryptology Santa Barbara, CA, USA Aug. 19–22, 1984 47 - 53
Boneh D. , Franklin M. “Identity-Based Encryption from the Weil Pairing,” Adv. Cryptology Santa Barbara, CA, USA Aug. 19–23, 2001 213 - 229
Cha J.C. , Cheon J.H. “An Identity-Based Signature Scheme from Gap Diffie-Hellman Groups,” Int. Workshop Practice Theory Public Key Cryptography Miami, FL, USA Jan. 6–8, 2003 18 - 30
Hess F. “Efficient Identity Based Signature Schemes Based on Pairings,” Sel. Areas Cryptography St. John’s, Canada Aug. 15–16, 2002 310 - 324
Paterson K.G. 2002 “ID-Based Signatures from Pairings on Elliptic Curves,” IEEE Electron. Lett. 38 (18) 1025 - 1026    DOI : 10.1049/el:20020682
Gopal P.V.S.S.N. , Reddy P.V. , Gowri T. “New Identity Based Signature Scheme Using Bilinear Pairings over Elliptic Curves,” IEEE Int. Adv. Comput. Conf. Ghaziabad, India Feb. 22–23, 2013 361 - 365
Yoon H. , Cheon J.H. , Kim Y. “Batch Verifications with ID-Based Signatures,” Int. Conf. Inf. Security Cryptology Seoul, Rep. of Korea Dec. 2–3, 2004 233 - 248
Cao T. , Lin D. , Xue R. 2006 “Security Analysis of Some Batch Verifying Signatures from Pairings,” Int. J. Netw. Security 3 (2) 138 - 143
Cui S. , Duan P. , Chan C.W. “An Efficient Identity-Based Signature Scheme with Batch Verifications,” Int. Conf. Scalable Inf. Syst. Hong Kong, China May 29–June 1, 2006 152 (22)
Chiang H.F. , Yen S.M. , Lin H.C. “Security Analysis of Batch Verification on Identity-Based Signature Schemes,” WSEAS Int. Conf. Comput. Crete Island, Greece July 26–28, 2007 50 - 55
Zhang C. “An Efficient Identity-Based Batch Verification Scheme for Vehicular Sensor Networks,” IEEE Conf. Comput. Commun. Phoenix, AZ, USA Apr. 15–17, 2008 816 - 824
Tseng Y.M. , Wu T.Y. , Wu J.D. “Towards Efficient ID-Based Signature Schemes with Batch Verifications from Bilinear Pairings,” IEEE Int. Conf. Availability, Rel. Security Fukuoka, Japan Mar. 16–19, 2009 935 - 940
Hwang J.Y. 2015 “New Efficient Batch Verification for an Identity-Based Signature Scheme,” Security Commun. Netw. 8 (15) 2524 - 2535    DOI : 10.1002/sec.1194
Ren Y. 2015 “An Efficient Batch Verifying Scheme for Detecting Illegal Signatures,” Int. J. Netw. Security 17 (4) 463 - 470
Goh E.J. , Jarecki S. “A Signature Scheme as Secure as the Diffie-Hellman Problem,” Int. Conf. Theory Appl. Cryptographic Techn. Warsaw, Poland May 4–8, 2003 401 - 415
Katz J. , Wang N. “Efficiency Improvements for Signature Schemes with Tight Security Reductions,” ACM Conf. Comput. Commun. Security Washington, DC, USA Oct. 27–30, 2003 155 - 164
Pointcheval D. , Stern J. 2000 “Security Arguments for Digital Signatures and Blind Signatures,” J. Cryptology 13 (3) 361 - 396    DOI : 10.1007/s001450010003
Barreto P.S.L.M. “Efficient Algorithms for Pairing-Based Cryptosystems,” Adv. Cryptology Santa Barbara, CA, USA Aug. 18–22, 2002 354 - 369
Koblitz N. , Menezes A. , Vanstone S. 2000 “The State of Elliptic Curve Cryptography,” Des., Codes, Cryptography 19 (2) 173 - 193    DOI : 10.1023/A:1008354106356
Menezes A. , Van Oorschot P. , Vanstone S. 1996 Handbook of Applied Cryptography CRC Press, LLC Boca Raton, USA