Informática 35 (2011 ) 343-350 343
Improved ID-based Ring Signature Scheme with Constant-size Signatures
Hongwei Li, Xiao Li and Mingxing He School of Mathematics and Computer Engineering Xihua University
E-mail: lhwlihongwei@gmail.com
Shengke Zeng
School of Computer Science and Engineering University of Electronic Science and Technology of China E-mail: doris82414@sina.com
Keywords: ring signature, accumulator, constant-size, random oracle Received: September 7, 2001
Ring signature enable a user to sign a message on behalf of the ring, without revealing the actual signer. Constant-size ring signature is the ring scheme that the size of the signature does not grow with the size of the ring(or group), so it is practical for large rings. In this paper we use the Collision Resistant Accumulator from bilinear pairing to construct an identity-based ring signature scheme with constant-size signature. Our scheme actually is an improvement on the modified version of the scheme proposed by Nguyen, but we greatly improved the efficiency in terms of computational complexity and signature size. To the best of our knowledge, our scheme is the most efficient secure ID-based ring signature with constant-size based on accumulator proposed to date. Our scheme is proven secure in the random oracle model based on a simplified and general Forking Lemma under the k-strong Diffie-Hellman assumption.
Povzetek: Predstavljena je izboljšana metoda podpisa za obroč.
1 Introduction
Ring signature schemes, introduced by Rivest, Shamir and Tauman [1], allow a signer to form a group without a central authority and sign messages on behalf of the group. A user might not even know that he has been included in a group and even a party with unlimited computing resources can not find out the actual signer. In order to remove the need of certification of the public keys, Shamir [2] proposed the concept of ID-based cryptology to simplify public key management. Zhang and Kim [3] extended the ring signature to the ID-based ring signature schemes, where the user's public keys is their identities. The accumulator was introduced by Benaloh and de Mare [4] in order to design distributed protocols without the presence of a trusted central authority. Such a cryptographic primitive is an algorithm allowing the aggregation of a large set of elements into a single value of constant size. So the accumulator could be applied to construct constant size ring signature. Baric and Pfitzmann [5] generalized the definition of accumulators and constructed a collision-free subtype. As an application, they construct a fail-stop signature scheme based on their collision-free accumulator. Camenisch and Lysyanskaya [6] extended the concept of accumulators to dynamic accumulators which allow the addition and deletion of values from the original set of elements. Dodis, Kiayias, Nicolosi and Shoup [7] introduced ad hoc anony-
mous identification schemes based on the notion of accumulator with one-way domain, an extension of cryptographic accumulators. In 2005, Nguyen [8] proposed a dynamic accumulator based on bilinear pairings to design ID-based ad-hoc anonymous identification schemes and identity escrow protocols with membership revocation. However, Tartary, Zhou, Lin, Wang and Pieprzyk [9] demonstrated that the security model proposed by Nguyen did lead to a cryptographic accumulator which is not collision resistant, later, Nguyen had modified the security model [10] so that collision resistance can be provided. In 2009, Camenisch, Kohlweiss and Soriente proposed a new dynamic accumulator [24] based on bilinear maps for revocation of the authentication credentials. In their construction, however, in the case of accumulating an arbitrary set of size n, the issuer of the accumulator would need to publish a mapping from the set of identities to the elements of destined group. It looks like very difficult to construct ring signature schemes by hiring their accumulator [24],
Since Zhang and Kim [3] proposed the first ID-based ring signature scheme, there are lots of excellent Id-based ring signature schemes have been proposed [11, 12, 13], but all of them the size of ring signatures linearly depend on the group size, thus not practical for large groups. Actually, all the previous proposals had signature size proportional to the size of the ring before the scheme [7] proposed by Dodis, Kiayias, Nicolosi and Shoup. They
344 Informatica 35 (2011) 343-350
H. Li et al.
provided an ad-hoc anonymous identification scheme and used the Fiat-Shamir heuristics [15] to convert it into the public key which was prime, so an extension supporting ID-based keys seemed to be non-trivial [14], The first ID-based ring signature scheme with constant-size signatures [8] was proposed by Nguyen. Similar to scheme [7], Nguyen also obtained the constant-size ring signature using the Fiat-Shamir transform [15] from anonymous identification scheme. However, the scheme [8] was found flawed by Zhang and Chen [16]. After that, Nguyen proposed the modified version [10] of the original scheme [8] and shown that the ring signature in their scheme [10] is much more efficient than previous one [7]. So, is there still some room for the computational efficiency of the constant-size ring signature to improve? Is there a way to reduce the size of the constant-size ring signature scheme?
We provide the affirmative answer to these questions and deem that the constant-size ring signature scheme [10] is still not efficient enough. We propose the improved constant-size ring signature scheme which is much more efficient either on computational complexity or signature size than the scheme [10] proposed by Nguyen. Moreover, Nguyen doesn't directly give the security reduction of their ring signature scheme, but we provide the security proof in the random oracle model under the k-strong Diffie-Hellman assumption. To the best of our knowledge, our scheme is the most efficient ID-based constant-size ring signature based on accumulator in the literature.
The rest of this paper is organized as follows. In Section 2, we briefly review some notations and complexity assumptions that will be used throughout this paper. We explain the general characteristics of a ID-based constant-size ring signature scheme, and the security properties that such a scheme must satisfy in Section 3. In Section 4, We present our new ring scheme, and provide security results for it in the section 5. In section 6, we compare its efficiency with previous schemes. Finally, we sum up the work in Section 7.
2 Preliminaries
In this section, we briefly introduce some preliminaries that will be used throughout this paper. A string means a binary one. If xi, #2,... are objects, then x\ ||x211... denotes an encoding of them as strings from which the constituent objects are easily recoverable. If S is a set, s <er S denotes the operation of assigning to s an element of S chosen at random, s s means we let s = s . If A is a randomized algorithm, then A{x i, ■■■'■/>) denotes its output on inputs xi,... and p, while y r A{xi, ...; p) means that we choose p at random and let y = A(xi; ■■■'■/>)■
2.1	Bilinear map groups and related computational problems [25]
Let I be a security parameter and p be a /-bit prime. Let us consider groups G , G< and GT of the same prime order p and let P, Q be the generators of G and G< respectively. We say that (G \. G->. G-r) are bilinear map groups if there exists a bilinear map e : G\ x G2 —> GT satisfying the following properties:
-	Bilinearity: V(S,T) G Gi x G2,Va,6 G Z;, e(aS, bT) = e(S, T)ab.
-	Non-degeneracy: VS G Gu e(S, T) = 1 for all T G G2 iffS = o.
-	Computability: V(S,T) G Gi x G2,e{S,T) is efficiently computable.
-	There exits an efficient, publicly computable (but not necessarily invertible) isomorphism v : G> —> (!\ such that ip(Q) = P
Such bilinear map groups are known to be instantiate with ordinary elliptic curves such as that suggested in [21], In this case, the trace map can be used as an efficient isomorphic 4> as long as G> is properly chosen [22], With supersingular curves, symmetric pairings(i.e// = G \) can be obtained and 4> is the identity. The computational assumption for the security of our scheme was proposed by Boneh and Boyen [27] and is recalled in the following definition.
Definition 1. Let us consider the bilinear map groups (G-i,G2,Gt) and the generators P € Gi and Q € Gi. The k-strong Diffie-Hellman problem in the groups G\,Gi is defined as follows: given a (k+2)-tuple (P, Q, aQ, a2Q,..., akQ) as input, where P = ip(Q), output a pair (c, ^^P) with c e Z*.
2.2	Collision Resistant Accumulator
Here we present the definition of accumulators and the collision resistance property as set by Nguyen [10].
Definition 2. (Accumulator[10]) Accumulator is a tuple ({Xi}ieN, {Fi}ieN), where {Xi}ieN is called the value domain of the accumulator and {Fi}ieN is a sequence of families of pairs of functions such that each (/, g) € Fi is defined as f : Uf x Xefxt ->•£// for some C Xefxt, and g : Uf Ug is a bijective function. In addition, the following properties are satisfied:
-	(efficient generation) There exists an efficient algorithm Q that takes as input a security parameter ll and outputs a random element (/, g) Gr Fi, possibly together with some auxiliary information a,f.
-	(quasi commutativity) For every I e N, (f,g) € Fi, u G Uf, xi,x2 G Xt, f(f(u,xi),x2) = f(f(u, x2), x\). For any I G N, (/, g) G Fi, andX = {xh ...,xk} c Xt, we call g(f(...f(u,x1)...,xk)) the
IMPROVED ID-BASED RING SIGNATURE SCHEME...
Informatica 35 (2011 ) 343-350 345
accumulated value of the set X over u. Due to quasi commutativity, the value g(f(...f(u, xi)..., #&)) is independent of the order of the xH 's and is denoted by f(u,X).
- (efficient evaluation) For every (f,g) G Fi, u G Uf and X c Xi with size bound by a polynomial of I g(f(u,X)) is computable in time polynomial in I, even without the knowledge ofa f.
Definition 3. (Collision Resistant Accumulator [9] [10]). An accumulator is defined as collision resistant if for every PPT algorithm A, the following function Advc£lacc (I) = Pr[(fg) Gfl F;u Gfl Uf;(x,w,X) <- A(g o f, Uf, u)\(X C Xi) A (w G Ug) A (x G Xpf \ X) A (/(fi1 x) = f(u>X))] is negligible as a function of I. We say that w is a witness for the fact that x G Xi has been accumulated in v G Ug whenever g(f(g~1(w), x) = v.
To generate an instance of the accumulator [10] from the security parameter I, run the algorithm Q with I' to obtain a tuple t = (p,G1,G2,GT,e(-, -),P,Q) and a uniformly chosen element s from Z*. We construct a tuple t = (I'. (). sQ,..., sqQ) where q is the an upper bound on the number of elements to be accumulated. The corresponding functions (/, g) for this instance (/. / ) are defined as:
/ : Zp x Zp —» Zp g : Zp —» G2 (v, x) i—y (x s)v v i—y vQ
This construction involves that we have:
Uf=Xft = Zp Ug = G2 Xl = Zp\{-s}
It is clear that / is quasi-commutative. In addition, for u G Zp and a set X = {x\,..., xk} CZP\ { —s} where k <p, the accumulated value g(f(u, X)) = rii=i(xi + S)UQ is computable in time polynomial in I from the tuple t and without the knowledge of the auxiliary information s. The accumulator proposed by Nguyen [10] has been proven secure by [9] under the k-strong Diffie-Hellman assumption.
2.3 New General Forking Lemma
The security proof of our ID-based constant-size Ring Signature scheme relies on a generalization of the Forking Lemma [18] proposed by Bellare and Neven instead of the Forking Lemma in ring scenario [20] proposed by Herranz and Saez.
Lemma 1. (General Forking Lemma [18] [23]). Fix an integer Q > 1 and a set H of size \ H | > 2. Let B be a randomized algorithm that on input x,h\,... ,h,Q returns a pair (J, a) where J G {0,..., Q} and a is referred as side output. Let IG be a randomized algorithm called the input generator. Let accB = Pr[J > 1 : x R
IG, hi,...,hQ H; (J, a) B(x, hi,..., hQ)\ be the accepting probability of B. The forking algorithm Fb associated to B is the randomized algorithm that takes in input x and proceeds as follows:
Algorithm Fb(x)
Pick random coins p for B
hi,..., hQ r H
(J,a) B(x, h\,..., hq] p)
If J = 0 then return (0, _L, _L)
hi, ■■■ ,h,Q R H
(J',a) <r- B(x, hi,..., hj-1, h'j, ...,hQ;p) If(J = J and hj hj) then return (1, a, a ) Else return (0, _L, _L).
Let frk = Pr[b = 1 : x IG;(b,a,a Fb(x)}. Then frk > accB(^ - jjjj).
The exactly proof of this lemma could be found in [18]. Roughly says that if an algorithm B accepts with some non-negligible probability, then a "rewind" of B is likely to accept roughly with the probability squared[23]. The intuitions are that: (l)hi,..., hq can be seen as the set of replies to random oracle queries made by the original adversary and (2) the forking algorithm implements the rewinding. Moreover, it is important that in FB the two executions of B are run with the same random coins.
3 The Model of ID-based
Constant-size Ring Signature
3.1 ID-based Constant-size Ring Signature Schemes
Here we give the definition of ID-based constant-size ring signature schemes, which is quite the same as the definition in [10].
Definition 4. An ID-based constant-size ring signature scheme is as a tuple IR =(Setup, KeyGen, MakeGPK, MakeGSK, Sign, Verify) of PT algorithms, which are described as follows.
-	Setup: takes as input a security parameter ll and returns the public parameters par arris and a master key mk. The master key is only known to the Private Key Generator (PKG).
-	KeyGen: run by the PKG, takes as input params, mk and an arbitrary identity idi and outputs a private key Sidv The identity is used as the corresponding public key.
-	MakeGPK: takes as input par ams and a set of identities and deterministically outputs a single group public key gpk which is used in the ID-based ring signature scheme described below. Its cost linearly depends on the number of identities being aggregated. The algorithm is order invariant that means the order of aggregating the identities does not matter.
346 Informatica 35 (2011) 343-350
H. Li et al.
-	MakeGSK: takes as input params, a set of identities R, a pair of an identity idi and the corresponding private key sid. and deterministically outputs a single group secret key gskid. which is used in the ID-based ring signature scheme described below. It should be noted that each user has its own group secret key gskidi which is different from the others. Its cost linearly depends on the number of identities being aggregated. It can be observed that a group secret key gskidi MakeGSK(params, S ,(sidi,idi)) corresponds to a group public key gpk MakeGPK(params, S) if and only if S = S U idi. More than one group secret key might correspond to the same group public key.
-	Sign: takes as input the public parameter params, a user private key sid., the user's group secret key gskidi, group public key gpk which includes the identity corresponding to idit and a message to, outputs a signature a for to.
-	Verify: The deterministic polynomial time(DPT) algorithm takes as input a set of identities R, group public key gpk, a message m and a ring signature a, and outputs either accept or reject.
3.2 Security Requirements
There are two preliminary security requirements for ID-based ring signature schemes: Anonymity and Unforge-ability.
-	Anonymity: the anonymity requires, informally, that an adversary should not be able to tell which member of a ring generated the particular signature.
-	Unforgeability: the intuitive notion of unforgeabil-ity is that an adversary should be unable to output (to, a) such that Verify (to, a) = 1. However, there are lots of security definitions about unforgeability of ring signature [20]. We use the unforgeability definition [26] proposed by Herranz. It should be noted that [26]'s unforgeability definition is very similar to the strongest unforgeability definition(unforgeability w.r.t. insider corruption) proposed in [20].
Definition 5. (Unforgeability against chosen message s/identies attacks). A ring signature scheme (Setup, KeyGen, MakeGPK, MakeGSK, Sign, Verify) is unforgeable with chosen-sub ring attacks if for any PPT adversary A and for any polynomial n(-), the probability that A succeeds in the following game is negligible:
- the challenger takes a security parameter k and runs the Setup algorithm of the scheme. He gives the resulting parameter to adversary.
-	A is given access to a signing oracle OSign(-, •), OSign(ids,m, R) returns SignSid (to, R), where we require ids G R, where R is a set of identities.
-	A is also given access to extraction oracle Extraction(-), where ExtractionalDi) outputs corresponding secret key ski.
-	at the end of the above execution, A outputs (R* ,m* ,a*) and succeeds if Verifyr* (to*, a*) = 1, A never queried (R*,m*,-) to its signing oracle, and for all IDi e R, the adversary has not requested an extraction query for IDi.
4 The Proposed Constant-size Ring Signature Scheme
In this section, we present our ID-based constant-size ring signature scheme, Our scheme is the modified version of the scheme [10] proposed by Nguyen, we describe our scheme as the following algorithms: Setup, KeyGen, MakeGPK, MakeGSK, Sign, Verify.
-	Setup: on a security parameter I, chooses s <gr Z*, u Gr Z* and generates an collision resistant accumulator as in section 2.2, including functions (/, g) and tuples t (p, Gi, G2, GT, e(-, •), ijj) and t
(P, Q, sQ,..., sqQ), where q is the upper bound on the number of identities to be aggregated. It sets Qpub = sQ,Ppub = ip(Qpub)- Let H0, Hi be collision-free hash function //, : {0,1}* ->• Z*, Hi : {0,1}* —> Z*. Then, public parameter par arris (/, t,t , u, H0, Hi, f o g) and the master key is mk s.
-	KeyGen: extracts a private key sidi	} „ I' for an identity idi. The identity is used as the corresponding public key. The user can verify the private key by checking e(Ho{idi)Q + Qpub,sidJ = e(Q,P).
-	MakeGPK: given a set of identities R = {"/, } '' |, computes the set X = {//,,("/,)}'' and generates the group public key for the set gpk = V g(f(u, X)).
-	MakeGSK: generates the group secret key gsk for a user ids G R, R = {«cii}ifc=1 by just computing the
setX' {H0(idi)}!?=lti¥:s, hids H0(ids) and the witness W g(f(u,X')). Note that X = X'uhids. The group secret key is gsk = (hids, sids, W).
-	Sign: given a message to, a set of identities R = {"/, }'' which includes the signer's identity ids, the signer's private key sids.
-	Given a message to <gr {0,1}*, choose r1,r2,k1,k2,k3,k4,k5 Gr Z*.
IMPROVED ID-BASED RING SIGNATURE SCHEME...
Informatica 35 (2011 ) 343-350 347
-	Compute Ut sids + nP; U2 W + r2Q; then compute Hi e(Q, ^lX ■ e(Q, Pp ■
e(Qpub,P)kl-, n2 e(P,t/2)-fc5 • e{P,Q)k' ■ e(PPub,Q)k3.
-	Getc^Pi1(m||[/1||[/2||nilin2ll«)-
-	Then compute si ki + cr^ s2 k2 +
crihids«3 k3 + cr2; s4 k4 + cr2hids; S5 k5 + chids ■
-	The signature is a	=
(Ui, u2, ni, n2, si' s2, «3, «4, s5).
- Verify: Given signature a, message to, a set of identities R = {idi}k=1.
-	GetcVifiHI^II^Iiniliriall«)-
-Check III =	■ e(Q,P)°2 •
e(Qpub,P)Sl ■ e(Qpub,Ui)^ ■ e(P, Q)c'; ]l2 =	■ e(P,Q)"* ■ e(Ppub,Q)s3 •
e(Ppub,U2)-c' -e(P,V)c'.
If above condition holds, the verifier accept the ring signature, else reject. It's easy to see that our ring signature scheme can be converted into an ad-hoc anonymous identification scheme [7], where a user can form ad-hoc groups and anonymously prove membership in such group. Although we use the collision-free accumulator in our scheme, the dynamic accumulators are also available such that the addition and deletion of members from the original group(or ring) are allowed.
It should be noted that Nguyen' scheme and our ring signature scheme actually are both non-interactive proof of the knowledge of (sid, hid, W) satisfying e(hidQ + QPub,Sid) = e(Q, P) and e(hidP + Ppub,W) = e(P,V), although Nguyen' scheme is much more complex than ours. The exact reason why our scheme could cut down the computation and size of the signature will be given in section 6.
5 Security Analysis 5.1 Unforgeability
theorem 1. Assume that an adversary F has an advantage e against our scheme when running in time t, asking qHi queries to random oracles Hi(i = 0,1), qs signature queries to signature oracle. Then there is an adversary B to solve the k-strong Diffie-Hellman problem with probability	(gH"+gHl+g;r'24r+(r"+gHl+'js) - i Within
a timet < 2t+qs[10texp+9tp + (n+l)qmult]+0[(qs(n+ l)+qH)(l+qs+qH)}, where tp denotes the require time for a paring evaluation, texp denotes the costs of an exponentiation in Gt, tmuit denotes the costs of a multiplication in G2 and qu denotes the maximum total number of queries to all random oracles.
Proof: Here, we are ready to present the actual proof. On a security parameter I, Algorithm B takes as input
(p, GuG2, Gt, ip, P, Q, aQ, a2Q,..., akQ) and aims to —P) where w* e Z*. We first show
find a pair (w*, -how to provide the adversary with a consistent view. In setup phase, it builds a generator G G Gi such that it knows k-q(k> q) pairs (wu XX forwi,... ,wfc_g Z*. It should be noted that q is the an upper bound on the number of elements to be accumulated and k - q is the an upper bound on the number of extraction queries. To do so,
-	It picks w\,..., Wk~q Gfl Z* and expands f{z) ElXX + z) to obtain e0,..., efc_g £r Z* so that
XX EtoX-
-	It sets generators H EXeX<3) = f(&)Q G G2 and G ^(H) = f(a)P G Gv
- For 1 <

< k — q, B expands fi(z)

to obtain dio,...,dik_
k-q-l ■3=0
&R Z* so Then compute
that fi(z) = E
E-X^XX)^ M*)P =	-
-G. Then all pairs i/u',.
G
Oi+Wi
could be available.
Oi+Wi
for 1 < i < k — q
- It sets aH
k — q
<r-
E-XXXX^
<r-<r-
Ei=o9 ei{ai • • • i oiqH E to Mai+qQ).	let t
{p, Gu G2, Gt, e(-, •), G, H,aH,..., a^H}.
Now, B first chooses a random u <er Z* and generates an collision resistant accumulator / o g as in section 2.2, then send (I. /. /I. f o g) to adversary F. To handle the oracle queries, B maintains two lists LHo and LHl ■ For simplicity, we assume that adversary F asks qn0 distinct queries for qHo distinct identities. Simulates adversary's environment as follows:
-	Ho queries on an identity ID e {0,1}*: B selects a random index 7, where 1 < 7 < qn0 and fixes ID7 as target identity. B first initializes a counter index to 1 and answers w windex e Z* and increments
index if ID ^ ID7, else B returns a random w7 Gr Z;. Add the tuple (ID , Windex) tO Lh0 ■
-	H1 queries on a tuple //	= Hl^ill^linilin2ll«): If M has been defined in LHl, retrieves c from LHl and returns c to F, else chooses a new random c <gr Z* and adds (p, c) into LHl ■
-	Key extraction queries on II ): l> recovers the matching pair (ID, w) from L0 and returns the previously computed G if ID ^ ID7, else B sets badi = true, then aborts.
-	Signature queries on a pair (m,ID,R): If ID / ID7, B proceeds according to the sign algorithm. This is possible for B knows the private key of ID. If ID = 7^, then:
348 Informatica 35 (2011) 343-350
H. Li et al.
-	Chooses U\ £r Gi, U2 Gr G2, chooses pair-wise different si,..., s5 <Gr Z*.
-	Selects a random c <gr Z*, then computes ]li <~ eiHJJi)-^ ■ e{H,G)a* ■
e{Hpub,G)^ ■ e(Hpub, IJ\)~C • e(G,F)c; n2 e(G, t/2)-S5 • e(G, H)s± ■ e(Gpub, . e{Gpub, IJ2)~C • e(G, y)0. Then add the new tuple (m||[/1||[/2||nilin2ll^ci) in LHl(if (//.. r,) had already been defined in LHl, set bad? true, aborts).
-	Returns a = (£/1; U2, flu ]\2, si> s2, «3, «4, s5) as the signature.
We have explained how to simulate F's environment in chosen-messages and chosen-identities attack. So, B runs the algorithm FB(t) as described in section 2.3. In this way we get two forgeries a0 and a\ together with a set of identities R and message to. Let c0 be the answer from the random oracle // given to F in the first execution, i.e., hj in FB(t), and let be the second answer hj. The forged signature a0 = (Ui, U2, Hi, rL> S1' s2, S3, S4, S5) and another signature is o-i = (U'1,U'2,Yl1,Yl2,s'1,s'2,s3,s'4,s'5). Let/j ^
for i G {1,..., 5}, then we get a tuple (/5, £+ -/iG) satisfying e(f5H+Hpu b, U^—fiG) = e(H, G). It implies
that w* =
+ wi,
h and
i
a+tij
-G = (t/i - AG). We note that
w ^ wi,..., wfc_g with probability at least 1 - K^1. If both forgeries satisfy the verification equation, B can pro-
ceed as in [27] to extract
l
-P from
l
a+tir
-G:
- Writes f(z) = UiZi(wi + z) = 7(z)(z + w*
where 7_i G and 7(2;) =	1
7¿z •
- Then

7-1
E.
k-q-0
V>(#) = f{a)P G Gi, as thus
7-1
P

7iZ*. Since G =
1 ^ _ /(") p _
a+tij*	a+tiJ*
a+tij*
- It's easy	to get	,
^ 0	a+tiJ*	7_i L-tij*
^fc-qr-l	/ ¿mi	fk™ tka fimlo /,„t 1
1
= -L-
Yh=o 7i(«ip)]> then the tuple (w*
—G -
fa
>¿=0 /H" -1	' a+u,* P) will
be the answer of the k-strong Diffie-Hellman problem.
Let Pr[badi] denote the probability of the event that flag badi set to be true(fails in providing a consistent simulation). We bound the accepting probability acc as follows:
acc > e — Pr[badi] — Pr[bad2]
qn0 qn1 + qs
> £ -
2l
2l
The probability that algorithm B succeeds in getting the answer of the k-strong Diffie-Hellman problem is given by
e >
frk
acc —
>
2 I rHl 2'
The running time t is twice that of once execution in /''/;(/) plus the time needed to compute the solution of the k-strong Diffie-Hellman problem. The running time of once execution in /'/,< (7 j is the running time t of F plus the time needed to answer qH random oracle queries and qs signature queries, where qn denotes the maximum total number of queries to all random oracles. We assume that tp denotes the require time for a paring evaluation, texp and I,nnn respectively denotes the costs of an exponentiation in GT and a multiplication in G2, and all other operations take unit time. Each random oracle query at most cause B to perform 0(1 + qH + qs) unit-time operations. Each signature query involves at most 10texp + 9tp + (n+l)qmuit + (n+l)G(l + qH + qs) operations, where n is the maximum number of identities of each signature query. Therefore, we have t < 2t + qs [10texp + 9 tp + (n + l)qmult] + 0[(qs(n+ 1) + qH){ 1 + qs + qH)}-
5.2 Anonymity
In order to give the proof for anonymity, we present the proofs of our scheme's perfect zero-knowledge is enough. The simulator randomly chooses Ui,U2 Gi, c, si, s2, S3, S4, S5 Gr Zp, then computes Hi = e(Q, t/i)-S5 • e(Q, P)S2 • e(Qpub, P)s> ■ e(Qpub, U^ ■
e(P,Q)c-, n_2 = <P,U2)-"S • e(P,QY4 • e(Ppub,Qyi •
e(PPub, U2)~c ■ e(P, V)c. We can see that the distribution of the simulation is the same as the real transcript. This completes the proof.
1+7-1. 6 Some Remarks and Efficiency Comparison
In many scenarios, as pointed in [7], the group doesn't change for a long time or has a short description. So an appropriate measurement of ring signature-size does not need to include the group description. In this situation, both the signer and verifier need to perform a one-time computation proportional to the size of the ring, and get the gpk and gsk which allow them to produce/verify many subsequent signatures in constant time. It's obvious that the constant-size ring signature scheme will be much more efficient than the previous schemes which signature size proportional to the size of the ring in such scenarios. We note that even in large ad-hoc groups, the size of our signature scheme is much smaller than that of schemes which the size of signature linearly depends on the group size. To the best of our knowledge, Chow et al.'s scheme [14] is the most efficient one among all the ID-based ring signature schemes which the size of signature linearly depends on the group size. For the sake of comparison and concreteness, we fix |Gi| = \ZP\ = 256 bits for a security level equivalent to a 128-bit symmetric key for AES(cf.[28]). We conclude that our scheme has smaller size than Chow et al.'s scheme when the number of identities of the ring over 8.
The first constant-size ring signature scheme (DKNS04)
IMPROVED ID-BASED RING SIGNATURE SCHEME...
had been proposed by Dodis, Kiayias, Nicolosi and Shoup [7], after that, no more efficient constant-size ring signature scheme was found until the first secure ID-based ring signature scheme with constant-size signatures proposed by Nguyen [10]. Nguyen had compared his constant-size ID-based ring signature scheme with DKNS04 at the same level of security. The conclusion is that the signature size is very much smaller than that of constant-size ring signature scheme DKNS04 [7]. He also pointed out that in the future, when higher levels of security are required, this difference even grows much larger.
We now make a specific comparison between our scheme and that of Nguyen's. Due to our scheme actually is an improvement on the modified version of the scheme proposed by Nguyen [10], it seems that our scheme and Nguyen's scheme are implemented by the same elliptic curve or hyperelliptic curve over a finite field is reasonable. As shown in [10], we assume p is a 160-bit Jacobian of a hyperelliptic curve over a finite field with order p and compression techniques are used. GT is a subgroup of a finite field of size approximately 21024. A possible choice of these parameters is that C \ id = (!■>j is derived from the curve E/GF(3l ) defined by y2 = x3 — x + 1.
We summarize the result in Table 1. It's obvious that we greatly reduce the size of the signature, although the computational efficiency is improved slightly. It should be noted that our scheme has the same keys(GSK, GPK) with Nguyen's, so we don't list them(i.e. computation of keys and size of keys) in the table 1. Here we give our analysis of why our scheme could cut down the computation and size of the signature. As we mentioned is section 4, our ring signature scheme and Nguyen's scheme actually are both non-interactive proof of the knowledge of (sid, hid, W) satisfying e(hidQ + QPub,Sid) = e(Q, P) and e(hidP + Ppub,W) = e(P,V). In our signature a = (U1,U2,Yl1,Yl2, sx, s2, s3, s4, s5),
def
o\ = (Ui, |. si, s2, «5) are used to prove the knowledge (sid, hid) satisfying e(hidQ + Qpub, Sid) = e(Q, P),
de f
and <r2 = (U2, ' s3> s4> ss) rdre used to prove the knowledge (sid, hid) satisfying e(hidP + Ppub, W) = til'. Vj. It looks like that there should be some extra "useful" data to set up a tough relation between o\ and a2 to build up resistance to attack whereby the adversary "tricked" generate a new valid signature use several valid signatures. Actually, this is what Nguyen's scheme did. However, it's easy to see that a\ and ct2 share the same element s5 = k5 + chid which is used to prove the relationships of (sid,hid,W). In our scheme, s5, and EL share the same random number k5. It implies that each signature has a unique random number, and it doesn't leave open the possibility of an attack whereby the adversary "tricked" generate a new valid signature use several valid signatures. So, the extra "useful" data is really redundancy. Our constant-size ring signature actually is the essence of the Nguyen's scheme, i.e. the remaining part of the Nguyen's scheme after cut extra "useful" data down. Then, there is a question: is there a possibility that cut something down from our signature scheme? Due to the way we construct the private key of user's, it looks like
Informatica 35 (2011 ) 343-350 349
Table 1: Efficiency comparison
scheme	signature size	mul	padd	pmul
Nguyen's	2,240 bits	7	15	20
Ours	1,440 bits	5	2	2
*mul, padd and pmul respectively indicate the number of multiplications, point additions and point scalar multiplications.
paring operation is necessary. If paring operation is necessary, it's really very hard to cut something down from our signature scheme.
7 Conclusions
We have proposed an improved ID-based constant-size ring signature scheme based on Nguyen's scheme, which will be useful for implementation in large ring scenario. Our scheme outperforms in size of signature the previously proposed constant-size ring signatures and admits proofs of secure in the random oracle model based on a simplified and general Forking Lemma under the k-strong Diffie-Hellman assumption.
Acknowledgments
This work is supported by National Natural Science Foundation of China (60773035), The fund of Key Disciplinary of Computer Software and Theory(SZD0802-09-l), The research fund of key disciplinary of application mathematics (XZD0910-09-1).
References
[1]	R.Rivest,A.Shamir, and Y.Tauman. How to Leak a Secret: Theory and Applications of Ring Signatures, in: Theoretical Computer Science. LNCS, vol.3895, Springer Berlin, 2006, pp.164-186.
[2]	A.Shamir. Identity-Based Cryptosystems and Signature Schemes, in: Advances in Cryptology. LNCS, vol.196, Springer Berlin, 1985, pp.47-53.
[3]	F.Zhang, and K.Kim. ID-Based Blind Signature and ring from pairings, in: Advances in Cryptology - ASIACRYPT 2002. LNCS, vol.2501, Springer Berlin, 2002, pp.629-637.
[4]	J.Benaloh and M.de Mare. One-Way Accumulators: A Decentralized Alternative to Digital Signatures, in: Advances in Cryptology - EUROCRYPT'93. LNCS, vol.765, Springer Berlin, 1994, pp.274-285.
[5]	N.Baric and B.Pfitzmann. Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees, in: Advances in Cryptology - EUROCRYPT'97. LNCS, vol.1233, Springer Berlin, 1997, pp.480-494.
[6]	J.Camenisch, and A.Lysyanskaya. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. in: Advances in Cryptology - CRYPTO 2002. LNCS, vol.2442, Springer Berlin, 2002, pp.101-120.
350 Informatica 35 (2011) 343-350
H. Li et al.
[7]	Y.Dodis, A.Kiayias, A.Nicolosi, and V.Shoup. Anonymous Identification in Ad Hoc Groups, in: Advances in Cryp-tology - EUROCRYPT 2004. LNCS, vol.3027, Springer Berlin, 2004, pp.609-626.
[8]	Lan Nguyen. Accumulators from Bilinear Pairings and Applications. in: Topics in Cryptology - CT-RSA 2005. LNCS, vol.3376, Springer Berlin, 2005, pp.275-292.
[9]	C Tartary, S Zhou, D Lin, H Wang and J Pieprzyk. Analysis of bilinear pairing-based accumulator for identity escrow-ing. Information Security, IET 2(4)(2008), pp.99-107.
[10]	Lan Nguyen. Accumulators from Bilinear Pairings and Applications to ID-based Ring Signatures and Group Membership Revocation, http://eprint.iacr.org/2005/123.
[11]	Chih-Yin Lin and Tzong-Chen Wu. An Identity-based Ring Signature Scheme from Bilinear Pairings, in: AINA'04, Also appear in http://eprint.iacr.Org/2003/l 17.
[12]	Javier Herranz and Germán Sáez. New Identity-Based Ring Signature Schemes, in: Information and Communications Security. LNCS, vol.3269, Springer Berlin, 2004, pp. 269274.
[13]	Sherman S,M.Chow, S,M.Yiu, and Lucas C.K.Hui. Efficient Identity Based Ring Signature, in: Applied Cryptography and Network Security. LNCS, vol.3531, Springer Berlin, 2005, pp.499-512.
[14]	S.S.M. Chow,R.W.C. Lui, L.C.K.Hui, and S.M.Yiu. Identity Based Ring Signature: Why, How and What Next, in: Public Key Infrastructure. LNCS, vol.3545, Springer Berlin, 2005, pp.144-161.
[15]	A.Fiat, and A.Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems, in: Advances in Cryptology - CRYPTO'86. LNCS, vol.263, Springer Berlin, 1987, pp. 186-194.
[16]	F.Zhang and Xiaofeng Chen. Cryptanalysis and improvement of an ID-based ad-hoc anonymous identification scheme at CT-RSA 05. Information Processing Letters 105(15)(2009) pp.846-849.
[17]	D.Boneh, and X.Boyen. Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups . Journal of Cryptology 21(2)(2008), pp.149-177.
[18]	M.Bellare and G.Neven. Multi-signatures in the plain public-key model and a generalized forking lemma, in: Conference on Computer and Communications Security: Proceedings of the 13th ACM conference on Computer and communications security, ACM, New York, 2006, PP.390399.
[19]	J.Herranz and G.Sáez. Forking lemmas for ring signature schemes, in: Progress in Cryptology - INDOCRYPT 2003. LNCS, vol.2904, Springer Berlin, 2003, pp.266-279.
[20]	Adam Bender, Jonathan Katz, Ruggero Morselli. Ring Signatures: Stronger Definitions, and Constructions without Random Oracles. Journal of Cryptology 22(1)(2009), pp.114-138.
[21]	A.Miyaji, M.Nakabayashi, and S.Takano. New explict conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals E84-A(5)(2001), pp.12341243.
[22]	N.P.Smart and F.Vercauteren. On computable isomorphisms in efficient pairing based systems. http://eprint.iacr.Org/2005/l 16.
[23]	Fiore,D., Gennaro,R. Making the Diffie-Hellman Protocol Identity-Based, in: Topics in Cryptology - CT-RSA 2010. LNCS, vol.5985, Springer Berlin, 2010, pp.165-178.
[24]	J.Camenisch, M.Kohlweiss and C.Soriente. An accumulator based on bilinear maps and efficient revocation for anonymous credentials, in: Public Key Cryptography - PKC 2009. LNCS, vol.5443, Springer Berlin, 2009, pp.481-500.
[25]	Paulo S.L. Barreto, B.Libert, N.McCullagh, J.J.Quisquater. Efficient and provably-secure identity-based signatures and signcryption from bilinear maps, in: Advances in Cryptology - ASIACRYPT 2005. LNCS, vol.3788, Springer Berlin, 2005, pp.515-532.
[26]	J.Herranz. Identity-based ring signatures from RSA. Theoretical Computer Science 389(1-2)(2007) pp.100-117.
[27]	D.Boneh and X.Boyen. Short Signatures Without Random Oracles, in: Advances in Cryptology - EUROCRYPT 2004. LNCS, vol.3027, Springer Berlin, 2004, pp.56-73.
[28]	ECRYPT II Yearly Report on Algorithms and Key Lengths (2010), http://www.ecrypt.eu.Org/documents/D.SPA.13.pdf (revision 1.0, 30 March 2010).