# Identity-based ring signature schemes for multiple domains.

1. IntroductionEnabling ubiquitous applications most often requires a pervasive computing environment in which large amounts of user information are collected and distributed. In such environment, the risk of mistakenly collecting sensitive user data or willfully misusing user data is inherent. Therefore, in order to benefit from the convenience of information technology without running the risks associated with the proliferation of information, it is important that security procedures such as message authentication and user privacy protection should be properly implemented and followed. This paper deals with designing a separable identity-based ring signature (IBRS) scheme, which may be used as a basic primitive for security procedures.

The main purpose of a ring signature is to maintain an appropriate level of signer ambiguity and authenticate messages [1]. Using a list or a ring of arbitrary signers or ring members, a signer can generate a signature associated with the ring. A valid ring signature convinces the verifier that the signature has been generated by one of the members of the ring, without revealing the identity of the actual signer. Meanwhile, by applying identity-based cryptography to a ring signature scheme, one can simplify (certificate-based) public key management procedures. For example, an arbitrary public string such as an e-mail address or phone number may be used as a user's public key [2][3]. This technique for simplification of public key management is particularly suitable for ring signature schemes which deal with multiple signers (from the same domain) at a time, as it does not require additional certificates to associate random public keys with a user.

A domain can be defined using an identity-based signature (IBS) scheme. It should be noted that for a concrete implementation of an IBS scheme, specific public parameters and their corresponding master keys must be first generated and defined. A user obtains a private key for his or her identity, which is associated with the master private key. Then, according to the IBS scheme, signatures can be generated for message authentication and can be validated. Thus, a domain can be viewed as an instance of an IBS scheme, which is defined by a specific parameter. The same IBS scheme can have concrete instances that vary according to the master keys and parameters. On the other hand, in situations where two different IBS schemes are involved, the instances of the respective schemes will be always different.

An IBRS scheme can be devised only for a specific single domain by extending the structure of a particular IBS scheme that works in that domain [4], [5]. Realistically, however, it must be assumed that there are various domains that are based on various cryptographic techniques and assumptions. In order to achieve an appropriate level of privacy, an IBRS scheme must, therefore, be capable of supporting multiple domains; for example, a signer should be able to pick ring members arbitrarily from across various domains. This property allowing the selection of ring members from different domains is known as separability. Using the separability property, a signer can have fine-grained control over his/her privacy.

1.1 Our Contributions

In this paper, we propose a modular method which enables the efficient construction of IBRS schemes with varying levels of separability. To do this, we first present a basic method for constructing an efficient IBRS scheme for a single domain. We explain this method through concrete examples based on an RSA cryptosystem and pairing map parameters. Next, we present a generic method for constructing an IBRS scheme for multiple domains, using IBRS schemes designed for a single domain. The resulting IBRS schemes afford a high level of separability, allowing, for example, a signer to select the identities of ring members from across different domains, irrespective of the public parameters and signing methods. Our method, extending the technique of [6], offers a good structure for linking various ID-based signatures sequentially. We present a highly-refined security model for a separable IBRS scheme and prove that all the proposed IBRS schemes achieve strong anonymity and unforgeability in the model. To demonstrate the effectiveness of our approach, we compare the performance of our schemes with that of other known IBRS schemes, with respect to the size of signatures and computational costs. Due to their intrinsic property of dealing with multiple (possible) signers at the same time, reducing the size of a signature is one of the critical efficiency concerns for IBRS schemes. We show that the signature size of our separable IBRS schemes is shorter than those of other known schemes with the same degree of separability.

1.2 Related Works

Since the first introduction of the notion of an identity-based cryptosystem by [2], many IBS schemes have been proposed using various cryptographic techniques based on RSA, discrete logarithm, or bilinear map parameters [3], [7][8][9][10]. [1], meanwhile, presented the concept of a non-ID-based ring signature scheme, proposing an RSA-based ring signature scheme. The first explicit construction of an IBRS scheme was presented by [11], and this scheme was without a formal security proof. Various other IBRS schemes have been suggested, subsequently, for improving efficiency or refining security models [4][12][13]. Some extensions of ring structures have been also presented to support a general access structure [4][14]. However, most IBRS schemes have thus far been constructed for single domains. Several works, including [6][13], and [15], have focused on a modular approach to combine signatures with different structures. The results by [6] and [15] provide novel methods to link non-ID-based signatures in a sequential or parallel manner. The result by [13] directly applied these link methods to ID-based signature schemes to achieve strong separability. Under the approach proposed in this study, as will be shown later in detail, signatures are significantly shorter in length, than those under the previously proposed approaches.

1.3 Organization

The rest of this paper is organized as follows: In section II, we present a security model for a separable IBRS scheme. In section III, we describe our IBRS scheme for a single domain and provide two instances of its use. In section IV, we present a generic method to construct an IBRS scheme for multiple domains, and prove the security of the IBRS scheme constructed using this method. In section V, we compare the size of our signatures to those of other best known signatures. Finally, we offer a conclusion in section VI.

2. Security Model

We formally define a security notion for a separable IBRS scheme. Let [lambda] denote the fixed parameter for the size of user identities.

The notion of separability was introduced by [16] to quantify the amount of common system parameters for a signature. Levels of separability can be defined according to whether a pair of independent keys is used in a signature scheme or completely different signature schemes are in use. For example, when all parties must use the same signature scheme and public system parameters, the level of separability is considered weak, while it is considered strong when parties may use potentially different signature schemes, and the signature is based on roughly the minimum security parameter of the signature schemes involved.

Next, we formally define a separable IBRS scheme [PI], which consists of a tuple of polynomial-time algorithms, SetUp, Extract, Sign, and Vrfy.

--SetUp is a probabilistic polynomial-time (PPT) algorithm that, on input of security parameter [kappa], outputs a tuple of public system parameters [pi] =([[pi].sub.1],..., [[pi].sub.[alpha]]) and its corresponding master secret key msk = ([msk.sub.1],..., [msk.sub.[alpha]]), where [alpha] is a polynomial in [kappa].

--Extract is a PPT algorithm that, on input of [msk.sub.j], [[pi].sub.j], and ID [member of] [{0,1}.sup.[lambda]], outputs a signing key [sk.sub.j,ID]. This is denoted by [sk.sub.j,ID] [left arrow] Extract ([msk.sub.j], [[pi].sub.j], ID).

--Sign is a PPT algorithm that, on input of a private key [sk.sub.i,ID], a ring RID = {([[pi]'.sub.1], [ID.sub.1]),..., ([[pi]'.sub.n], [ID.sub.n])} for [[pi]'.sub.j] [member of] [pi] and [ID.sub.j] = ([ID.sub.j,l],..., [ID.sub.j, t[j]]), and a message m [member of] {0,1}*, outputs [sigma]. Assume that i is selected in {1,...,n} uniformly at random, [[pi].sub.i] [member] {[[pi]'.sub.1],..., [[pi]'.sub.n]} and ID [member of] [ID.sub.i]. This is denoted by [sigma] [left arrow] Sign ([sk.sub.i,ID], RID, m).

--Vrfy is a deterministic polynomial-time algorithm that, on input of [pi], a ring RID, message m, and signature [sigma], returns 1 (valid) or 0 (invalid). This is denoted by b [left arrow] Vrfy ([pi], [sigma], RID, m).

In the above description, we assume that a signature scheme is implicitly defined or described in its corresponding public system parameter. Given that separability can be measured by a, when [alpha] = 1, it represents the weakest level of separability; that is, a ring can be constructed by picking only users in the same domain. The greater the value of [alpha], the greater the degree of separability. However, this is only a quantitatively measurement of separability and does not reflect qualitative separability. For example, the signature schemes corresponding to two different domain parameters [[pi]'.sub.i] and [[pi]'.sub.j] may be the same in some cases. To take this factor into consideration, we can measure separability using additional indices to indicate signature schemes in public system parameters [[pi]'.sub.i]. If the two system parameters [[pi]'.sub.i] and [[pi]'.sub.j] are defined for a signature scheme, we can assume that there is no increase in separability.

For security, an IBRS scheme must achieve correctness and two basic security notions, unforgeability and anonymity.

Correctness. We say that an IBRS scheme is correct if the following conditions hold: 1 [left arrow] Vrfy ([pi], [sigma], RID, m) for a message m [member of] {0,1}*, a positive integer n [member of] N, and RID = {([[pi]'.sub.1],[ID.sub.1]),...,([[pi]'.sub.n], [ID.sub.n]) | [[pi]'.sub.i] [member of] [pi], [ID.sub.1], = ([ID.sub.i,l],..., [ID.sub.i,t[i]])} where (msk, [pi]) [left arrow] Setup ([1.sub.k]); [sk.sub.i,ID] [left arrow] Extract ([msk.sub.i], [[pi]'.sub.I], ID [member of] [ID.sub.i]); and [sigma] [left arrow] Sign ([sk.sub.i,ID], RID, m) for all i = 1,..., n.

Unforgeability. An IBRS scheme 77 is said to be existentially unforgeable under adaptively chosen message and identity (CMIA) attacks if no PPT adversary A has a non-negligible advantage in the following game with a challenger C.

(1) C runs SetUp to obtain [pi] = ([[pi].sub.1],..., [[pi].sub.[alpha]]) and msk = ([msk.sub.1],..., [msk.sub.[alpha]]). The public parameters [pi] is given to A.

(2) The adversary A adaptively makes polynomially many queries as follows.

--Extract query ([[pi].sub.j], ID): C returns [sk.sub.j,ID] [left arrow] Extract ([msk.sub.j], [[pi].sub.j], ID).

--Sign query (([[pi]'.sub.[beta]], ID [member of] [ID.sub.[beta]]), RID ={([[pi]'.sub.1], IDO,...,([[pi]'.sub.n], [ID.sub.n])}, m) : C returns [sigma] [left arrow] Sign ([sk.sub.[beta]ID], RID, m) where [sk.sub.[beta]ID] [left arrow] Extract ([msk.sub.[beta]], [[pi]'.sub.p], ID).

(3) A outputs [RID.sup.*] = {([[pi].sup.*.sub.1],[ID.sup.*.sub.1]]),...,([[pi].sup.*.sub.n],[ID.sup.*.sub.n])}, [m.sup.*], and [[sigma].sup.*].

A succeeds in the game if [[sigma].sup.*] on ([m.sup.*], [RID.sup.*]) is valid, i.e., 1 [left arrow] Vrfy ([pi], [[sigma].sup.*], [RID.sup.*], [m.sup.*]) and for all j=1,...,n, Extract ([msk.sup.*.sub.j], [[pi].sup.*.sub.j], [ID.sup.*] [member of] [ID.sup.*.sub.j]) and Sign (([[pi].sup.*.sub.j], [ID.sup.*] [member of] [ID.sup.*.sub.j]), [RID.sup.*], [m.sup.*]) queries have never been issued. A successful event is denoted by [Suc.sub.forg]. The EUF-advantage of A for [PI] is defined by [Adv.sup.IBRS,EUF-CMIA]([PI],A) = Pr[[Suc.sub.forg]].

Anonymity--An IBRS scheme [PI] is said to be anonymous if no PPT adversary A has a non-negligible advantage in the following game with a challenger C.

(1) C runs SetUp to obtain [pi] = ([[pi].sub.1],...,[[pi].sub.[alpha]]) and msk. The public parameters [pi] is given to A.

(2) The adversary A adaptively makes polynomially many queries as follows.

--Extract query ([[pi].sub.j], ID): C returns [sk.sub.j,ID] [left arrow] Extract ([msk.sub.j], [[pi].sub.j], ID).

--Sign query (([[pi]'.sub.[beta]], ID [member of] [ID.sub.[beta]]), RID={([[pi]'.sub.1], [ID.sub.1]),...,([[pi]'.sub.n], [ID.sub.n])}, m): C returns [sigma] [left arrow] Sign ([sk.sub.[beta],ID], RID, m).

(3) The adversary A outputs a message [m.sup.*], two distinct tuples of a public parameter and an identity, (([[pi].sup.*.sub.0], [ID.sup.*.sub.0]), ([[pi].sup.*.sub.1], [ID.sup.*.sub.1])), and a ring [RID.sup.*] for which ([[pi].sup.*.sub.0], [ID.sup.*.sub.0]), ([[pi].sup.*.sub.1], [ID.sup.*.sub.1]) [member of] [RID.sup.*], and [[pi].sup.*.sub.0], [[pi].sup.*.sub.1] [member of] [pi].

(4) The challenger C picks a random bit b [member of] {0,1} and gives A with the signature on ID=[ID.sup.*.sub.b], [sigma]' [left arrow] Sign([sk.sub.b,ID], [RID.sup.*], [m.sup.*]).

(5) A makes Extract and Sign queries adaptively.

(6) Finally, the adversary outputs bit b'.

A succeeds in the game if b = b'. The successful event is denoted by [Suc.sub.anon]. The ANON-advantage of A for [PI] is defined by [Adv.sup.IBRS,Anon-CMIA]([PI],A) = Pr[[Suc.sub.anon]].

The above definition considers anonymity against full key exposure; that is, an adversary can obtain the secret keys of all honest users including even users in the ring. As noted by [12], this definition is polynomial-time equivalent to the case in which an adversary should be unable to guess the real signer among r, randomly chosen ring members, with probability better than 1/r + [epsilon] for a negligible [epsilon].

3. IBRS Schemes for a Single Domain

In this section, we present an efficient method of extending IBS schemes into IBRS schemes for a single domain. Throughout the paper, we denote by [direct sum] and [parallel] bitwise-eXclusive OR and concatenation operations, respectively. Meanwhile, we denote by [PHI](N) Euler's totient function. We define [[direct sum].sub.i=1,...,k] [c.sub.i] = [c.sub.1] [direct sum]... [direct sum] [c.sub.k] for L-bit strings [c.sub.i] [member of] [{0,1}.sup.L].

Intuitively, the main idea of our construction is to aggregate random commitments for other fake signers into a single random commitment using a common public system parameter. Since a real signer can compute a secret share in advance, he/she can generate a correct response using his/her signing key, the secret share, and a random number. The response can be used to cancel exactly the identity of the real signer in the verification equation without changing the aggregated commitment. In the process, the identity of the signer is not exposed thanks to the computational symmetry of the verification equation. Our method is as follows where the choice of domains is not considered, as the scheme is constructed for one particular domain:

--SetUp. Given a security parameter [kappa], output a master secret key msk and its corresponding public system parameters [pi]. Assume that [pi] includes a cryptographic hash function H:[{0,1}.sup.*] [right arrow] [{0,1}.sup.L].

--Extract. Given an identity ID, return its corresponding private key [sk.sub.ID].

--Sign. Given [pi], a signing key [sk.sub.ID], message m, and a ring of identities RID=([pi], ([ID.sub.1],...,[ID.sub.t])) including ID=[ID.sub.[beta]] for random [beta] [member of] {1,...,t}, pick random [c.sub.i] [member of] [{0,1}.sup.L] for i =1,...,t, (i [not equal to] [beta]), and some randomness [R.sub.[beta]] and compute a simulated commitment B. This is denoted by B [left arrow] Sim([pi], RID, [R.sub.[beta]], ([c.sub.1],...,[c.sub.[beta]- 1],[c.sub.[beta]+1],...,[c.sub.t])). Compute a challenge w [left arrow] H(RID, m, B). Also compute [c.sub.[beta]] = w [direct sum] ([[direct sum].sub.i=1,...,t], (i [not equal to] [beta]) [c.sub.i]) and a response V using share [c.sub.[beta]], randomness [R.sub.[beta]], and signing key [sk.sub.ID]. Output [sigma] = ([c.sub.1],...,[c.sub.t],V).

--Vrfy. Given [pi], a ring RID, message m, and [sigma] = ([c.sub.1],...,[c.sub.t],V), compute B' [left arrow] VComp([pi], RID, [c.sub.1],...,[c.sub.t],V) and check if [c.sub.1] [direct sum]... [direct sum] [c.sub.t] = H(RID, m, B'). If the equality holds, then output 1; otherwise output 0.

For correctness, it is required that Sim ([pi], RID, Rp, ([c.sub.1],..., [c.sub.[beta]-1], [c.sub.[beta]+1],..., [c.sub.t]) = VComp ([pi], RID, [c.sub.1],...,[c.sub.t],V).

To explain our method through concrete examples, we chose two IBRS schemes extending the RSA-based IBS [7] and (modified) pairing-based IBS [8] schemes, respectively. The first RSA-based IBRS scheme is as follows:

--SetUp. Given a security parameter [kappa], generate two random [[lambda].sub.0]-bit primes [p.sub.1], [p.sub.2] and compute N = [p.sub.1][p.sub.2]. Let L [less than or equal to] [[lambda].sub.0]. Select e [member of] [{0,1}.sup.L] such that gcd([PHI](N),e) = 1. Let d = [e.sup.-1] mod N. Generate cryptographic hash functions [H.sub.id] : [{0,1}.sup.[lambda]] [right arrow] [Z.sub.N.sup.*] and H: [{0,1}.sup.*] [right arrow] [{0,1}.sup.L]. Output a master secret key msk = ([p.sub.1],[p.sub.2]) and a public system parameter [pi] = (N, e, [H.sub.id], H).

--Extract. Given an identity ID, compute Q = [H.sub.id](ID) and [sk.sub.ID]= [Q.sup.d] mod N, and return [sk.sub.ID]. If [sk.sub.ID.sup.e] = [H.sub.id](ID) mod N, then [sk.sub.ID] is a valid key for the ID.

--Sign. Given [pi], a signing key [sk.sub.ID], message m, and a ring RID = ([pi], ([ID.sub.1],...,[ID.sub.t])), including ID = [ID.sub.[beta]], select random r [member of] [Z.sub.N.sup.*], [c.sub.i] [member of] [{0,1}.sup.L] for i=1,...,t, (i [not equal to][beta]) and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Output [sigma] = ([c.sub.1],...,[c.sub.t],V).

--Vrfy. Given [pi], a ring RID, message m, and [sigma] = ([c.sub.1],...,[c.sub.t],V), check if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If the equality holds, then output 1; otherwise output 0.

It is easy to see that the above IBRS scheme is correct, because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 1. Let [H.sub.id] and H be random hash functions. The above RSA-based IBRS scheme is anonymous against full key exposure.

Proof. A simulator sets up all parameters correctly as defined in the proposed IBRS scheme. All private keys [sk.sub.ID]= [H.sub.id](ID)d mod N are given to an adversary. A simulator can provide a perfect simulation with the adversary because it knows all private keys. As in the definition of anonymity in section II, assume that an adversary outputs two distinct identities [ID.sub.1] and [ID.sub.2] for the proposed IBRS scheme. Since the scheme is constructed for a single domain we do not consider the choice of domains.

For random b[member of]{0,1}, assume that signature [sigma] = ([c.sub.0], [c.sub.1], V) is generated according to the signing method of the proposed IBRS scheme. That is, for a given signing key [sk.sub.ID,b] = [H.sub.id] [([ID.sub.b]).sup.d], message m, and ring of identities RID = ([pi], ([ID.sub.0], [ID.sub.1]), select random r [member of] [Z.sub.N.sup.*] and [c.sub.z] [member of] [{0,1}.sup.L] for z ([not equal to]b) [member of] {0,1} and then compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The verification equation shows the symmetry of computation with respect to identity. In fact, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be equivalently represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], while maintaining the validity of the signature. Also, r' is uniformly distributed over [Z.sub.N.sup.*] because r is uniformly distributed over [Z.sub.N.sup.*], and r' is represented by a linear combination of fixed parameters [sk.sub.ID,z], [sk.sub.ID,b], [c.sub.z], and [c.sub.b]. This means that V can be generated equally by a key for [ID.sub.0] or [ID.sub.1], though it was generated by the key for a specific identity.

Therefore, for given (m, RID, [sigma]), the probability that a specific [ID.sub.i] in RID is the identity of the real singer is 1/2. []

Theorem 2. Let [H.sub.id] and H be random hash functions. The above RSA-based IBRS scheme is existentially unforgeable under CMIA attacks under the hardness of the RSA problem.

Proof. We show that the security of the proposed IBRS scheme is reduced to the hardness of the RSA problem. We want to build an algorithm A that uses a forger F against our IBRS scheme to solve the RSA problem. Suppose that a random RSA instance (N, e, y) is given to A. Its goal is to compute x such that [x.sup.e] = y mod N.

A gives system parameters [pi] = (N, e) to F. A simulates oracle queries as follows: Suppose F makes at most [q.sub.id] and [q.sub.H] queries to [H.sub.id] and H oracles, respectively. For simplicity, we also assume that hash-queries are never repeated.

--[H.sub.id] query. First, A chooses [theta] [member of] {1,..., [q.sub.id]} uniformly at random. On an [H.sub.id](ID;) query, if it is the [[theta].sup.th] [H.sub.id] query, let [ID.sub.i] = [ID.sup.*]. A returns y. Otherwise, A picks a random D [member of] [Z.sub.N.sup.*] and returns [D.sup.e] mod N.

--H query. A obviously responds as follows: On a query, A picks random w [member of] [{0,1}.sup.L] and returns w.

--Extract query. On an Extract(ID) query, if ID [not equal to] [ID.sup.*] then A returns [sk.sub.ID]= D for [H.sub.id](ID) = [D.sup.e] mod N. Otherwise, A outputs FAIL and aborts the simulation.

--Sign query. On a Sign ([ID.sub.x], RID=(n, ([ID.sub.1],...,[ID.sub.t])), m) query, if [ID.sub.x] [not equal to] [ID.sup.*], then A returns [sigma] after correctly generating a signature a with the signing key for [ID.sub.x]. Otherwise, A chooses [c.sub.1],...,[c.sub.t] [member of][{0,1}.sup.L] and V(E [Z.sub.N.sup.*] uniformly at random. Then, A computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Define h = [c.sub.1]+...+[c.sub.t] as the value of H(RID, m, Y). A returns [sigma] = ([c.sub.1],...,[c.sub.t],V).

Eventually, F outputs a valid ring signature [[sigma].sup.*] = ([c'.sub.1],...,[c'.sub.s], V') on ([RID.sup.*], [m.sup.*]), where [RID.sup.*] = ([pi], ([ID.sup.*.sub.1],..., [ID.sup.*.sub.s])). Assume that for all j = 1,...,s, Extract ([ID.sup.*.sub.j]) and Sign ([ID.sup.*.sub.j], [RID.sup.*], [m.sup.*]) queries have never been issued. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and h' [not equal to] H([RID.sup.*], [m.sup.*], Y').

By using a standard rewinding technique, we can non-negligibly obtain another forged signature [sigma] = ([c".sub.1],...,[c".sub.s],V") satisfying the following condition: h' [not equal to] h", where Y" = [V".sup.e]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and h" = H([RID.sup.*], [m.sup.*], Y"). For some [beta] [member of]{1,...,s}, [c'.sub.[beta]][not equal to][c".sub.[beta]]and [c'.sub.j] = [c".sub.j] for j = 1,...,s (j [not equal to] [beta]).

If [ID.sub.[beta]] = [ID.sup.*] then A can compute Z = V'[(V").sup.-1] = [x.sup.[xi]] for [xi] = - [c'.sub.[beta]]+[c".sub.[beta]]. As already noted in the proof of Theorem 1, due to the symmetry of the verification equation, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some r [member of] [Z.sub.N.sup.*]. In addition, by the condition of the rewinding technique, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, we can have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [xi] = - [c'.sub.[beta]] + [c".sub.[beta]]. Using a similar method, A can compute another Z' = V" *[(V"").sup.-1] = [x.sup.[xi]], where [xi] = - [c'.sub.[beta]] + [c".sub.[beta]]. Next, A computes integers [tau] and [tau]' such that [tau] [xi] + [tau]'[xi]' = 1 using the extended Euclidean algorithm. Finally, A outputs T = [Z.sup.[tau]] * (Z')[tau]' = [x.sup.[xi][tau]] * [x.sup.[xi]'[tau]']= [x.sup.[xi][tau] + [xi]'[tau]'] = x = [y.sup.d] mod N as a solution to the given RSA problem.

It is well-known that the probability that two random numbers are relatively prime is 6/[[pi].sup.2] [approximately equal to] 0.6 [17]. Hence A can highly compute [tau] and [tau]'. It is easy to see that the simulation that A makes is perfect unless an abortion occurs. The adversary A does not abort the simulation if A at least correctly guesses the value of [theta], i.e, [ID.sub.[theta]] = [ID.sup.*] =[ID.sub.[beta]]. Since [ID.sup.*] is uniformly selected from the viewpoint of the forger, the probability of the event is at least 1/[q.sub.id]. Therefore, if the forger F who can break our IBRS scheme exists, then a poly-time solver to the RSA problem in [G.sub.1] non-negligibly exists. []

The second pairing-based IBRS scheme is described as follows.

--SetUp. Given a security parameter [kappa], generate an a[D.sub.[omega]]issible bilinear map e: [G.sub.1]x[G.sub.2] [right arrow] [G.sub.T], a random generator P of [G.sub.1]. Pick a random s [member of] [Z.sub.q.sup.*] and compute [P.sub.pub] = sP. Let [pi] = (e, [G.sub.1], [G.sub.2], [G.sub.T], q, P, [P.sub.pub], [H.sub.id], H), where [H.sub.id]: [{0,1}.sup.[lambda]] [right arrow] [G.sub.1] and H: [{0,1}.sup.*] [right arrow] [Z.sub.q.sup.*] are cryptographic hash functions. Output a master secret key msk=s and public system parameters [pi].

--Extract. Given an identity ID, compute Q = [H.sub.id](ID) and return the private key [sk.sub.ID]= sQ [member of] [G.sub.1].

--Sign. Given [pi], a signing key [sk.sub.ID], message m, and a ring of identities RID = ([pi], ([ID.sub.1], ... ,[ID.sub.t])), including ID = [ID.sub.[beta]], select random r [member of] [Z.sub.q.sup.*] and [c.sub.i] [member of] [{0,1}.sup.L] for i = 1,...,t, (i [not equal to] [beta]). Then, compute [Q.sub.i] = [H.sub.id]([ID.sub.i]), B = r[Q.sub.[beta]] + [[summation].sub.i=1,...,t(i[not equal to][beta])] [c.sub.i][Q.sub.i] [member of] [G.sub.1], w = H(RID, m, e(B,[P.sub.pub])), [c.sub.[beta]] = w [direct sum] ([[direct sum].sub.i=l,...,t(i[not equal to][beta])] [c.sub.i]), V = ([-c.sub.[beta]]+r)*[sk.sub.ID] [member of] [G.sub.1]. Output [sigma] = ([c.sub.1],...,[c.sub.t],V).

--Vrfy. Given [pi], a ring RID, message m, and [sigma] = ([c.sub.1],...,[c.sub.t],V), compute D' = e(V,P)*e([[summation].sub.i=1,...,t] [c.sub.i][Q.sub.i], [P.sub.pub]) and check if [c.sub.1] [direct sum]... [direct sum] [c.sub.t] = H (RID, m, D'), where [Q.sub.i] = [H.sub.id]([ID.sub.i]). If the equality holds, then output 1; otherwise output 0.

It is easy to see that the above IBRS scheme is correct because e(B,[P.sub.pub]) = e(r[Q.sub.[beta]]+ [[summation].sub.i=1,...,t(i[not equal to][beta])] [c.sub.i][Q.sub.i], [P.sub.pub]) = e((r-[c.sub.[beta]])[Q.sub.[beta]]+ [[summation].sub.i=1,...,t][c.sub.i][Q.sub.i][P.sub.pub]) = e(V,P) * e ([[summation].sub.i=1,...,t][c.sub.i][Q.sub.i], [P.sub.pub]).

Theorem 3. Let [H.sub.id] and H be random hash functions. The above pairing-based IBRS scheme is unconditionally anonymous against full key exposure.

Proof. A simulator sets up all parameters correctly as defined in the proposed IBRS scheme. All private keys [sk.sub.ID]= s[H.sub.id](ID) [member of] [G.sub.l] are given to the adversary. A simulator can provide a perfect simulation to the adversary because it knows all of the private keys. As in the definition of anonymity in section II, assume that the adversary outputs two distinct identities, [ID.sub.1] and [ID.sub.2], for the proposed IBRS scheme. Since the scheme is constructed for a single domain, we do not consider the choice of domains.

For a random b [member of]{0,1}, assume that a signature [sigma] = ([c.sub.0], [c.sub.1], V) is generated according to the signing method of the proposed IBRS scheme. That is, given a signing key [sk.sub.ID,b] = s[H.sub.id]([ID.sub.b]), message m, and a ring RID = ([pi], ([ID.sub.0], [ID.sub.1]), select random r [member of] [Z.sub.q.sup.*] and [c.sub.z] [member of] [{0,1}.sup.L] and then compute [Q.sub.z] = [H.sub.id]([ID.sub.z]), B = r [Q.sub.b] + [c.sub.z] [Q.sub.z] [member of] [G.sub.1], w = H(RID, m, e(B, [P.sub.pub])), [c.sub.b] = w [direct sum] [c.sub.z], V = (-[c.sub.b]+r)*[sk.sub.ID,b] [member of] [G.sub.1].

By the definition of the verification algorithm, it holds that [c.sub.0] [direct sum] [c.sub.1] = H (RID, m, e(V,P)*e([c.sub.0][Q.sub.0]+[c.sub.1][Q.sub.1],[P.sub.pub])). The verification equation has computational symmetry with respect to an identity. In fact, V = (- [c.sub.b] + r) * [sk.sub.IDb] can be equivalently represented by V = (- [c.sub.z] + r') [sk.sub.ID,z], where r' = [c.sub.z] + (r - [c.sub.b])*[alpha] and [sk.sub.ID,Z] = a * [sk.sub.ID,z] for some [alpha] [member of] [Z.sub.q.sup.*]. Note that V = (- [c.sub.z] + r')*[sk.sub.ID,z] = (-[c.sub.z] + [c.sub.z] + (r - [c.sub.b])*[alpha])*[sk.sub.ID,z] = (r - [c.sub.b])*[sk.sub.ID,b]. Here, r' is uniformly distributed over [G.sub.l] because r is uniformly distributed over [G.sub.1], and r' is represented by a linear combination of fixed parameters [alpha], [c.sub.z] and [c.sub.b]. This means that V can be generated equally by a key for [ID.sub.1] or [ID.sub.2], although it was generated by the key for a specific identity. Therefore, for given (m, RID, a), the probability that a specific [ID.sub.i] in RID is the identity of the real singer is 1/2. []

Theorem 4. Let [H.sub.id] and H be random hash functions. The above pairing-based IBRS scheme is existentially unforgeable under CMIA attacks under the hardness of the computational DH problem.

Proof. We want to build an algorithm A that uses a forger F against our pairing-based IBRS scheme to solve the CDH problem. Suppose that a random CDH instance (P, A = [alpha]P, B = [beta]P) is given to A. Its goal is to compute a[beta]P [member of] [G.sub.1]. A sets [P.sub.pub] = A (= [alpha]P) and gives system parameters [pi] = (e, [G.sub.1], [G.sub.2], [G.sub.T], q, P, [P.sub.pub]) to F. A simulates the oracle queries as follows: Suppose F makes at most [q.sub.id] and [q.sub.H] queries to [H.sub.id] and H oracles, respectively. For simplicity, we also assume that hash-queries are never repeated.

--[H.sub.id] query. First, A chooses [theta] [member of] {1,...,[q.sub.id]} uniformly at random. On an [H.sub.id](ID) query, if it is the [theta]th [H.sub.id] query, let ID = [ID.sup.*]. A returns B = [beta]P; otherwise, A picks a random z [member of] [Z.sub.q.sup.*] and returns zP.

--H query. A obviously responds as follows: On a query, A picks random w [member of] [{0,1}.sup.L] and returns w.

--Extract query. On an Extract (ID) query, if ID [not equal to] [ID.sup.*], then A returns [sk.sub.ID]= z[P.sub.pub] using z with [H.sub.id](ID) = zP. Otherwise, A outputs FAIL and aborts the simulation.

--Sign query. On a Sign ([ID.sub.x], RID =([pi], ([ID.sub.1],...,[ID.sub.t])), m) query, if [ID.sub.x] [not equal to] [ID.sup.*], then A returns [sigma] after correctly generating a signature a with the signing key for [ID.sub.x]. Otherwise, A chooses [c.sub.1],...,[c.sub.t] [member of] [Z.sub.q.sup.*] and V [member of] [G.sub.1] uniformly at random. Then, A computes Y = e([V.sub.[beta]])*e([[summation].sub.i=i,...,t][c.sub.i][H.sub.id]([ID.sub.i]),[P.sub.pub]). Define h = [c.sub.1]+...+[c.sub.t] as the value of H(RID, m, Y). A returns [sigma] = ([c.sub.1],...,[c.sub.t],V).

Eventually, F outputs a valid ring signature [[sigma].sup.*] = ([c'.sub.L],...,[c'.sub.s], V') on ([RID.sup.*], [m.sup.*]), where [RID.sup.*] = ([pi], ([ID.sup.*.sub.1],...,[ID.sup.*.sub.s])). Assume that for any ID E{[ID.sup.*.sub.1],...,[ID.sup.*.sub.s]}, Extract(ID) and Sign(ID, [RID.sup.*], m*) queries have never been issued. Let Y' = e(V',P)*e([[summation].sub.i=1,...,s] [c'.sub.i], [H.sub.id]([ID.sup.*.sub.i] [P.sub.pub]) and h' = H([RID.sup.*], [m.sup.*], Y').

By using a rewinding technique, we can non-negligibly obtain another forged signature [[sigma].sup.**] = ([c".sub.1],...,[c".sub.s],V") satisfying the following condition: h' [not equal to] h" where Y" = e(V",P)*e([[summation].sub.i=1,...,s] [c".sub.i] [H.sub.id]([ID.sup.*]i), [P.sub.pub]) and h" = H([RID.sup.*], [m.sup.*], Y"). For some [beta] [member of] {1,...,s}, [c'.sub.[beta]] [not equal to] [c".sub.[beta]] and [c'.sub.j] = [c".sub.j] for j = 1,...,s (j [not equal to] [beta]).

Note that if [ID.sub.[beta]] = [ID.sup.*], then the algorithm A can compute Z = [(-[c'.sub.[beta]] + [c".sub.[beta]]).sup.-]1 (V - V") = [sk.sub.ID*] = a[beta]P as a solution to the given CDH instance. As already noted in the proof of Theorem 3, due to the symmetry of the verification equation, V = (-[c'.sub.[beta]] + r)-[sk.sub.ID]* for some r [member of] [Z.sub.q.sup.*]. In addition, by the condition of the rewinding technique, we can have V" = (-[c'.sub.[beta]] +r)-[sk.sub.ID]*. Thus, we have Z = (- [c'.sub.[beta]] + [c".sub.[beta]])-1(V - V") = (- [c'.sub.[beta]] + [c".sub.[beta]])-1[(- [c'.sub.[beta]] + r)* [sk.sub.ID*] - (- [c".sub.[beta]] + r) *[sk.sub.ID*]] = [sk.sub.ID*] = [alpha][H.sub.id]([ID.sup.*]) = a[beta]P.

It is easy to see that the simulation that A makes is perfect unless an abortion occurs. The adversary A does not abort the simulation if A correctly guesses at least the value [theta], i.e, [ID.sub.[theta]]= [ID.sup.*] =[ID.sub.[beta]]. Since [ID.sup.*] is uniformly selected from the viewpoint of the forger, the probability of the event is at least 1/[q.sub.id]. Therefore, if a forger F who can break our IBRS scheme exists, then a poly-time solver to the CDH problem in [G.sub.1] non-negligibly exists. []

4. A Generic Construction for IBRS Schemes for Multiple Domains

We present a generic method to construct an IBRS scheme for multiple domains from IBRS schemes for a single domain. The resulting IBRS schemes achieve strong separability; a signer can, for example, select identities from across different master-key domains, regardless of public parameters or signing methods. Our method basically extends the technique of [6] for linking signatures with different structures. It should be noted that the technique has a good structure for accommodating various proof-of-knowledge schemes sequentially. However, the technique cannot be directly applied to IBRS schemes for single domains because it was originally devised to link non-identity-based signatures. Also, this will necessitate the simultaneous treatment of multiple challenges for generating an IBRS. For our purposes, we modify the technique using a simple (t,t) secret sharing method.

1. Our Extension Method

Let us describe our extension method more concretely. Let [pi] = ([[pi].sub.1],...,[[pi].sub.[alpha]]) and [[summation].sub.i] = ([Extract.sub.i], [Sign.sub.i], [Vrfy.sub.i]) be an IBRS scheme for single domains, which can be generically constructed, as shown in the previous section. Assume that [[pi].sub.j] includes a cryptographic hash function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Here, [[summation].sub.i] is assumed to be defined with each domain parameter [[pi].sub.i]. We assume that each [ID.sub.i,j] is associated with a master-key domain, [[pi].sub.i], and is included in [ID.sub.i] = (IDi,1,..., [ID.sub.i,t[i]]) for a positive integer t[i]. We also assume that a real signer with an identity, [ID.sub.[beta][gamma]] [member of] [ID.sub.[beta]], in domain [[pi].sub.[beta]] obtains a secret signing key [sk.sub.[beta][gamma]] from the [Extract.sub.[beta]] algorithm.

--Sign. Given [pi], a secret signing key [sk.sub.[beta][gamma]], message m, and a ring RID={([[pi]'.sub.1], [ID.sub.1]),...,([[pi]'.sub.n],[ID.sub.n])| [[pi]'.sub.j] [member of] [pi]} for random [beta] [member of] {1,...,n} and [gamma] [member of] {1,...,[t.sub.[[beta]]]}, perform the following:

* Initialization. First, pick random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i=1,...,[t.sub.[[beta]]], (i[not equal to][gamma]) and randomness [R.sub.[beta]], and compute a simulated commitment [B.sub.[beta]] [left arrow] Sim([[pi].sub.[beta]], RID, [R.sub.[beta]], ([c.sub.[beta],1],...,[c.sub.[beta],[gamma]-1],[c.sub.[beta],[gamma]+1],...,[c.sub.[beta],t[[beta]]])). Compute a challenge [w.sub.[beta]+1] [left arrow] [H.sub.[beta]+1](RID, m, [B.sub.[beta]]).

* Simulation. For each j=[beta]+1,...,n,1,...,[beta]-1, (1) pick random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i = 2,...,[t.sub.[j]] and then compute the challenge share [c.sub.j,i] = [w.sub.j] [direct sum] ([[direct sum].sub.i=2,...,t[j]] [c.sub.j,i]), (2) pick a random [V.sub.j] and compute [B.sub.j] [left arrow] VComp ([[pi].sub.j], RID, [c.sub.j,1],...,[c.sub.j,t[j]], [V.sub.j]), and (3) compute [w.sub.j+1] [left arrow] [H.sub.j+i](RID, m, [B.sub.j]).

* Real Proof. Compute [c.sub.[beta],[gamma]] = [w.sub.[beta]] [direct sum] ([[direct sum].sub.j=1,...,t[j](j[not equal to]y)] [c.sub.[beta],j]) and response [V.sub.[beta]] using the signing key, [sk.sub.[beta],[gamma]], [R.sub.[beta]], and [c.sub.[beta],[gamma]].

Output signature [sigma] = {([c.sub.j,1],...,[c.sub.j,t[j]], [V.sub.j])| 1 [less than or equal to] j [less than or equal to] n} for positive integers t[j].

--Vrfy. Given [pi], a message m, ring RID, and a signature [sigma] = {([c.sub.j,1],...,[c.sub.j,t[j]], [V.sub.j])| 1 [less than or equal to] j [less than or equal to] n}, for each j = 1,...,n, compute [B'.sub.j] [left arrow] VComp([[pi].sub.j], RID, [c.sub.j,1],...,[c.sub.j,t[j]], [V.sub.j]) and then check if [[direct sum].sub.i=1,...,t[j+1]] [C.sub.j+1,i] = [H.sub.j+1](RID, m, [B'.sub.j]). If all the equalities hold then output 1; otherwise, output 0.

Assume that the given underlying IBRS schemes used for the domain are correct, that is, for [gamma] [member of] {1,...,[t.sub.[j]]}, Sim([[pi].sub.[beta]], RID, [R.sub.[beta][gamma]], ([c.sub.[beta],1],...,[c.sub.[beta],[gamma]-1], [c.sub.[beta],[gamma]+1],[c.sub.[beta],t[beta]]) = VComp([[pi].sub.[beta]], RID, [c.sub.[beta],1],[c.sub.[beta],t[beta]], [V.sub.[beta]]). Using the assumption, we can show as follows that the extended IBRS scheme is correct: For j ([not equal to][beta]), by construction, [w.sub.j] is computed in the signing and verifying algorithms using the same value [B.sub.j]. For j=[beta], by correctness of a given underlying IBRS scheme, Sim([[pi].sub.j], RID, [R.sub.j,y], ([c.sub.j,1],...,[c.sub.j[gamma]-1], [c.sub.j[gamma]+1],...,[c.sub.j,t[j]])) = [B.sub.j] = VComp (n,, RID, [c.sub.j,1],...,[c.sub.j,t[j]], [V.sub.j]), and so the same hash value [w.sub.j] is computed from Bj in the signing and verifying algorithms.

Next, we show that if the underlying IBRS schemes for single domains are secure, the extended scheme for multiple domains is secure in the random oracle.

Theorem 5. The extended IBRS scheme is anonymous against full key exposure if the underlying IBRS schemes used for the domain are anonymous against full key exposure in the random oracle model.

Proof. First, consider a case in which two identities, say [ID.sub.[theta],1] and [ID.sub.[theta],2], are selected in a domain. In this case, it is easy to see that the anonymity of the extended scheme is reduced to that of the underlying scheme used for the domain. Hence, the extended scheme is anonymous against full key exposure because, by assumption, the underlying scheme is anonymous against full key exposure.

Second, consider a case in which two identities are selected in two different domains, [[pi].sub.[theta]] and [[pi].sub.[omega]]. Denote the identities by [ID.sub.[theta],1] and [ID.sub.[omega],1], respectively. For simplicity, we assume that RID = {([[pi].sub.[theta]], [ID.sub.[theta],1]), ([[pi].sub.[omega]], [ID.sub.[omega],1])} is a ring that the adversary selects. Consider two distributions of signatures, [D.sub.[theta]] and [D.sub.[omega]], where [D.sub.[theta]] (resp. [D.sub.[omega]]) is a distribution of signatures that a real signer in the domain [[pi].sub.[theta]] (resp. [[pi].sub.[omega]]) generates. Consider a signature [sigma] ={([c.sub.1,1],[V.sub.1]), ([c.sub.2,1], [V.sub.2])} [member of] [D.sub.[theta]]. By the construction, [c.sub.1,1] = [H.sub.1](RID, m, VComp([[pi].sub.[omega]], RID, [c.sub.2,1], [V.sub.2])) and [c.sub.2,1] = [H.sub.2](RID, m, Sim([[pi].sub.[theta]], RID, [R.sub.1])). Because of the correctness of the underlying IBRS scheme, we also have Sim ([[pi].sub.[theta]], RID, [R.sub.1])= VComp([[pi].sub.[theta]], RID, [c.sub.1,1], [V.sub.1]), and so [c.sub.2,1] = [H.sub.2](RID, m, VComp([[pi].sub.[theta]], RID, [c.sub.1,1], [V.sub.1])). Since the random hash model is considered in the proof, [c.sub.1,1] and [c.sub.2,1] are uniformly distributed.

Next, consider another case, that is, a signature [sigma]' = {([c'.sub.1,1], [V'.sub.1]), ([c'.sub.2,1], [V'.sub.2])} [member of] [D.sub.[omega]]. We have [c'.sub.1,1] = [H.sub.1](RID, m, Sim([[pi].sub.[theta]], RID, [R'.sub.2])) and [c'.sub.2,1] = [H.sub.2](RID, m, VComp([[pi].sub.[theta]], RID, [c'.sub.1,1], [V'.sub.1])). Because of the correctness of the underlying IBRS scheme, we have Sim ([[pi].sub.[omega]], RID, [R'.sub.2]) = VComp([[pi].sub.[omega]], RID, [c'.sub.2,1], [V'.sub.2]), and thus [c'.sub.1,1] = [H.sub.1](RID, m, VComp([[pi].sub.[omega]], RID, [c'.sub.2,1], [V'.sub.2])). Since the random hash model is considered in the proof, [c'.sub.1.1] and [c'.sub.2,1] are uniformly distributed. Furthermore, since the underlying IBRS schemes for a domain are anonymous against full key exposure, the distributions of [c.sub.1,1] = [H.sub.1](RID, m, VComp([[pi].sub.[omega]], RID, [c.sub.2,1], [V.sub.2])) and [c'.sub.1,1] = [H.sub.1](RID, m, VComp([[pi].sub.[omega]], RID, [c'.sub.2,1], [V'.sub.2])) are (computationally) indistinguishable under full key exposure attacks. A similar reasoning can be applied to [c.sub.2,1] = [H.sub.2](RID, m, VComp([[pi].sub.[theta]], RID, [c.sub.1,1], [V.sub.l])) and [c'.sub.2,1] = [H.sub.2](RID, m, VComp(ng, RID, c'u, V'i)),'that is, c2,i = [H.sub.2](RID, m, VComp(ng, RID, cu, [V.sub.1])) and [c'.sub.2,1] = [H.sub.2](RID, m, VComp([[pi].sub.[theta]], RID, [c'.sub.1,1], [V'.sub.1])) are (computationally) indistinguishable under full key exposure attacks. Thus, we have ([c.sub.1,1], [c.sub.2,1]) and ([c'.sub.1,1], [c'.sub.2,1]) being (computationally) indistinguishable under full key exposure attacks. Therefore, the extended IBRS scheme is anonymous against full key exposure. []

Theorem 6. The extended IBRS scheme is existentially unforgeable in the random oracle model.

Proof. The proof of the theorem mainly relies on a similar rewinding technique of [13] and [18][19][20]. We can simulate random hash functions, in a typical fashion, by selecting an element uniformly. Further, since the extended IBRS scheme follows a so-called commitment-challenge-response paradigm, and since we can control the simulation of the random hash functions, we can obviously simulate a signing oracle for the extended IBRS scheme by selecting a challenge as a hash output in advance. Assume that a forger generates a forged signature [sigma] = {([c.sub.j,1],...,[c.sub.jt[j],[V.sub.j]) | 1 [less than or equal to] j [less than or equal to] k}. Let [h.sub.j] = [H.sub.j](RID, m, VComp([[pi].sub.j-1], RID, [c.sub.j-1,1],...,[c.sub.j-1,t[j-1]],[V.sub.j-1])). By using a rewinding technique, we can non-negligibly obtain another signature [sigma]' = {([c'.sub.j,1],...,[c'.sub.j,t[j]], [V.sub.j])| 1 [less than or equal to] j [less than or equal to] k} satisfying the following condition: Let [h'.sub.j] = [H.sub.j](RID, m, VComp ([[pi].sub.j-1], RID, [c'.sub.j-1,1],...,[c'.sub.j-1,t[j-1]], [V'.sub.j-1])). For some [beta] [member of] {1,...,k}, and for, j = 1,...,k (j [not equal to] [beta]), [V.sub.j] = [V'.sub.j], [h.sub.j] = [h'.sub.j], and [V.sub.[beta]] [not equal to] [V'.sub.[beta]], [h.sub.[beta]] [not equal to] [h'.sub.[beta]]. For i = 1,...,[t.sub.[[beta]]] (i [not equal to] [gamma]), [c.sub.[beta],i] = [c'.sub.[beta],i] and [c.sub.[beta],[gamma]] [not equal to] [c'.sub.[beta],[gamma]]. Using a knowledge extractor with [V.sub.[beta]], [V'.sub.[beta]], [c.sub.[beta],[gamma]], and [c'.sub.[beta],[gamma]], an adversary can break an underlying IBRS scheme for single domains. This contradicts the unforgeability of the underlying IBRS schemes. Hence, the extended IBRS scheme is existentially unforgeable. []

2. A Concrete Instance for Multiple Domains

To further the understanding of our construction method for strongly separable IBRS schemes, let us now turn to an example using the IBRS schemes for a domain, which were suggested in the previous section. Let [pi] = ([[pi].sub.1], [[pi].sub.2]), where [[pi].sub.1] and [[pi].sub.2] are public system parameters for the RSA-based IBRS scheme and the pairing-based IBRS scheme, respectively, i.e., [[pi].sub.1] = (N, e, [H.sub.1,id], [H.sub.1]) and [[pi].sub.2]=(e, [G.sub.1], [G.sub.2], [G.sub.T], q, P, [P.sub.pub], [H.sub.2,id], [H.sub.2]).

For convenience, we denote the schemes by [[summation].sub.1] and [[summation].sub.2], respectively. Assume that a real signer has a signing key [sk.sub.2,[gamma]] [member of] [G.sub.1] for the second domain with [[pi].sub.2].

--Sign. Given [pi], a signing key [sk.sub.2,[gamma]] [member of] [G.sub.l], message m, and a ring RID = {([[pi].sub.1], ([ID.sub.1,1],...,[ID.sub.i,t'])), ([[pi].sub.2], ([ID.sub.2,1],...,[ID.sub.2,t"])}, do the following:

* Initialization. Pick random [c".sub.i] [member of] [{0,1}.sup.L"] for i = 1,...,t", (i [not equal to] [gamma]), and random [r.sub.2] [member of] [Z.sub.q.sup.*], and compute simulated commitment [B.sub.2] [left arrow] e([r.sub.2][Q.sub.2,[gamma]] + [[summation].sub.i=1,...,t"(i[not equal to][gamma]]c";[Q.sub.2,i], [P.sub.pub]) and challenge [w.sub.1] [left arrow] [H.sub.1](RID, m, [B.sub.2]), where [Q.sub.2,i] = [H.sub.2,id] ([ID.sub.2,i]).

* Simulation. For i = 2,...,t', select V [member of] [Z.sub.N.sup.*], [c'.sub.i] [member of] [Z.sub.q.sup.*] at random, and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [w.sub.2] [left arrow] [H.sub.2](RID, m, [B.sub.1]), where [Q.sub.1,i]= [H.sub.1,id] ([ID.sub.1]1).

* Real Proof. Compute [c".sub.[gamma]] = [w.sub.2] [direct sum] ([[direct sum].sub.i=2,...,t"(i [not equal to] [gamma])] [c".sub.i]) and [V.sub.2] = ([r.sub.2] - [c".sub.[gamma]]) [sk.sub.2,[gamma]]. Output signature a = {([c'.sub.1],...,[c'.sub.t'], [V.sub.1]), ([c".sub.1],...,[c".sub.t"], [V.sub.2])}.

--Vrfy. Given [pi], a message m, and [sigma] = {([c'.sub.1],...,[c'.sub.t'], [V.sub.1]), ([c".sub.1],...,[c".sub.t"], [V.sub.2])}, compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [B'.sub.2] [left arrow] e([V.sub.2],P) * e([[summation].sub.i=1,...t"] [c".sub.i][Q.sub.2,i], [P.sub.pub]). Check if [[direct sum].sub.i=1,...,t"] [c".sub.i] = [H.sub.2](RID, m, [B.sub.1]') and [[direct sum].sub.i=1,...,t'] [c'.sub.i] = [H.sub.1](RID, m, [B'.sub.2]). If the equality holds, then output 1; otherwise, output 0.

Similarly, a real signer with the signing key sk1n for the first domain [pi] is able to generate a ring signature of which the ring consists of ring members chosen from the two different domains.

5. Performance Comparison

In this section, we present a performance comparison between our schemes and some of the best-known IBRS schemes with respect to the size of signatures and computational costs. For convenience we denote by IBRS-1 and IBRS-2 our RSA-based IBRS scheme and our pairing-based IBRS scheme, respectively.

In this analysis, we define some notations: [pi] is the number of all ring members in a ring of a given signature. Dnum is the number of all different domains in a ring of a given signature. [L.sub.hash] is the bit-length of a given hash function to generate parameters [c.sub.j]. Exp is a modulo exponentiation under a RSA modulus. S is a scalar multiplication on [G.sub.1], and P is a pairing operation. [L.sub.N] and [L.sub.G1] are the bit-length of an RSA modulus N and the shortest group [G.sub.1] defined for a pairing map, respectively.

First, we compare our IBRS schemes for single domains with the IBRS schemes by [4] and [5] [See Table 1.].

Currently, [L.sub.hash] = 160 and [L.sub.N] = 1024 are considered practically secure. Meanwhile, to achieve the same security level as an 1024-bit RSA system, the bit-length of group [G.sub.1] for a pairing map must be 171 bits. Note that this assumption can be obtained by using MNT curves [21]. Let [L.sub.G1] = 171. As summarized in Table 1, the signature length of our IBRS-1 is n x [L.sub.hash] + [L.sub.N] and that of the RSA-based IBRS scheme [5] is (n+1) [L.sub.N]. (n x [L.sub.hash]+[L.sub.N])/(n+1) x [L.sub.N] becomes asymptotically close to w = [L.sub.hash]/[L.sub.N] as n, the size of a ring, increases. Thus, the ratio w = 160/1024 = 0.156 for [L.sub.hash] = 160 and [L.sub.N] = 1024. In this case, our IBRS-1 is 84% more efficient, compared to the scheme of [5]. Using a similar analysis, we can show that our IBRS-2 is 7% more efficient, compared to the pairing-based IBRS scheme [4]. As can be noted in Table 1, our IBRS-2 is comparable to the scheme of [4], and our IBRS-1 outperforms the scheme of [5] in terms of signing and verifying costs.

Next, we compare our generic IBRS scheme for multiple domains with the separable IBRS scheme of [13]. Let [absolute value of OURS] and [absolute value of AHR] denote the signature size of [13] and that of our scheme, respectively. We can summarize the signature sizes of the two schemes as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the size of each variable [V.sub.j] in signature {([c.sub.j,1],...,[c.sub.j,t[j]],[V.sub.j]) | 1 [less than or equal to] j [less than or equal to] k}. It is easy to see that [absolute value of OURS] [less than or equal to] [absolute value of AHR] because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for positive integers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The equality only holds when [n.sub.i] = 1 for all i; that is, only one signer is chosen from each domain.

5. Conclusion

We have proposed generic methods to construct IBRS schemes with varying levels of separability. We first presented a method for constructing an IBRS for a single domain. We then presented a generic method for constructing IBRS schemes for multiple domains by extending the IBRS schemes for a single domain. We showed that our method results in short signatures. We also demonstrated that the schemes presented are secure in the random oracle model. An interesting open problem would be to construct a secure IBRS scheme for multiple domains without a random oracle.

http://dx.doi.org/10.3837/tiis.2012.10.015

References

[1] L. Rivest, A. Shamir, and Y. Tauman, "How to leak a secret," in Advances in Cryptology--ASIACRYPT'01, LNCS 2248, 2001, pp. 552-565. Article(CrossRef Link)

[2] A. Shamir, "Identity-based cryptosystems and signature schemes," in Advances in Cryptology--CRYPTO'84, LNCS 196, 1985, pp. 47-53. Article(CrossRef Link)

[3] M. Bellare, C. Namprempre, and G. Neven, "Security proofs for identity-based identification and signature schemes," in Advances in Cryptology - EUROCRYPT04, 2009, LNCS 3027, pp. 268-286. Article(CrossRef Link)

[4] S. S.M. Chow, S.M. Yiu, and L. C.K. Hui, "Efficient identity based ring signature," in ACNS'05, 2005, LNCS 3531, pp. 499-512. Article(CrossRef Link)

[5] J. Herranz, "Identity-based ring signatures from RSA," in Theoretical Computer Science, 2007, vol. 389 (1-2), pp. 100-117. Article (CrossRef Link)

[6] M. Abe, M. Ohkubo, and K. Suzuki, "1-Out-of-n signatures from a variety of keys," in Advances in Cryptology--ASIACRYPT'02, LNCS 2501, 2002, pp. 415-432. Article(CrossRef Link)

[7] Guillou and J.J. Quisquater, "A Paradoxical" Identity-Based Signature Scheme Resulting from Zero-knowledge," in Advances in Cryptology - CRYPTO'88, 1990, LNCS 403, pp. 216-231. Article(CrossRef Link)

[8] J. C. Cha and J. H. Cheon, "An identity-based signature from gap Diffie-Hellman Groups," in Public Key Cryptography--PKC'03, LNCS 2139, 2003, pp. 18-30. Article (CrossRef Link)

[9] F. Hess, "Efficient Identity Based Signature Schemes on Pairings," in Selected Areas in Cryptography--SAC'02, LNCS 2595, 2003, pp. 310-324. Article (CrossRef Link)

[10] J. Herranz, "Formal Proof of Security of Zhang and Kim's ID-Based Ring Signature Scheme," International Workshop on Security in Information Systems, in WOSIS'04, 2004, pp. 63-72. Article(CrossRef Link)

[11] F. Zhang and K. Kim, "ID-based Blind Signature and Ring Signature from Pairings," in Advances in Cryptology - ASIACRYPT'02, LNCS 2501, 2002, pp. 533-547. Article(CrossRef Link)

[12] A. Bender, J. Katz, and R. Morselli, "Ring Signatures: Stronger Definitions, and Constructions without Random Oracles," in Proceedings of TCC'06, LNCS 3876, 2006, vol. 3876, pp. 60-79. Article(CrossRef Link)

[13] B. Adida, S. Hohenberger, and R. L. Rivest, "Separable Identity-Based Signature: Theoretical Foundation For Fighting Phishing Attacks," Computer Science and Artificial Intelligence Laboratory; MIT. Article(CrossRef Link)

[14] K. Lee, J. Y. Hwang, and D. H. Lee, "Non-Interactive Identity-Based DNF Signature Scheme and Its Extensions," in Bulletin of the Korean Mathematical Society, 2009, vol. 46, no. 4, pp. 743-769. Article(CrossRef Link)

[15] R. Cramer, I. Damgard, and B. Schoenmakers, "Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols," in Advances in Cryptology - CRYPTO'94, 2004, LNCS 839, pp. 174-187. Article(CrossRef Link)

[16] J. Camenisch and M. Michels, "Separability and Efficiency for Generic Group Signature Schemes," in Advances in Cryptology--CRYPTO '99, 1999, LNCS 1666, pp. 413-430. Article(CrossRef Link)

[17] J. E. Nymann, "On the Probability that Positive Integers are Relatively Prime," J. Number Th., vol. 4, 1972, pp. 469-473. Article (CrossRef Link)

[18] A. Fiat and A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems," in Advances in Cryptology--CRYPTO'86, 1987, LNCS 263, pp. 186-199. Article(CrossRef Link)

[19] K. Ohta and T. Okamoto, "On Concrete Security Treatment of Signatures Devised from Identification," in Advances in Cryptology--CRYPTO '98, LNCS 1462, 1998, pp. 354-369. Article(CrossRef Link)

[20] D. Pointcheval and J. Stern, "Security Arguments for Digital Signatures and Blind Signatures," in J. of Cryptology, vol. 13, 2000, pp. 361-396. Article (CrossRef Link)

[21] X. Boyen, "A Tapestry of Identity-Based Encryption: Practical Frameworks Compared," in Int. J. Applied Cryptography, Vol. 1, No. 1, 2008, Inderscience, pp. 3-21. Article(CrossRef Link)

JuHee Ki (1), Jung Yeon Hwang (2) and Dong Hoon Lee (3)

(1) Korea Evaluation Institute of Industrial Technology (KEIT), Daejeon, Korea

(2) Electronics and Telecommunications Research Institute (ETRI), Daejeon, Korea

(3) CIST, Korea University, Seoul, Korea

[e-mail: eye@keit.re.kr, videmot@etri.re.kr, donghlee@korea.ac.kr]

* Corresponding author: Dong Hoon Lee

Received March 30, 2012; revised June 30, 2012; accepted September 19, 2012 published October 29, 2012

JuHee Ki received the B.S. degree in Mathematics from University of Seoul and the M.S. degree in Information Security from Korea University, Korea in 2001 and 2003, respectively. Since 2003, she has been a researcher of KEIT (Korea Evaluation Institute of Industrial Technology), Korea. Her main research interests include cryptography, broadcast encryption, digital signatures, Identity-based cryptography, attribute-based cryptography, and their applications. Also, she is interested in privacy-enhancing cryptography.

Jung Yeon Hwang received the B.Sc. degree in Mathematics from Korea University, the M.S. and Ph.D. degrees in information security from Korea University, Korea on 1999, 2003, and 2006 respectively. He has been a post-doctoral researcher of Korea University from 2006 to 2009. Since 2009, he has been a senior member of engineering staff of Electronics and Telecommunications Research Institute (ETRI), Korea. Dr. Hwang's research interests include cryptography, broadcast encryption, digital signatures, Identity-based cryptography, attribute-based cryptography, and their applications. Also, he is interested in privacy-enhancing techniques.

Dong Hoon Lee received the B.S. degree from the Department of Economics at Korea University, Seoul, in 1985, and the M.S. and Ph.D. degrees in computer science from the University of Oklahoma, Norman, in 1988 and 1992, respectively. Currently he is a professor and the vice director of the Graduate School of Information Security at Korea University. His main research interests include the design and analysis of cryptographic protocols in key agreement, encryption, signature, embedded device security, and privacy-enhancing technology.

Table 1. Performance Comparison. Computational Costs Sig-Length (bit) Sign [5] (1+n) x [L.sub.N] 2n x Exp Our IBRS-1 n x [L.sub.hash]+LN (n+2) x Exp [4] (1+n) x [L.sub.G1] (n+1) x S Our IBRS-2 n x [L.sub.hash]+ (n+1) x S+1 x P [L.sub.G1] Computational Costs Vrify Param. Security [5] (n+1) x Exp RSA RSA Problem Our IBRS-1 (n+1) x Exp RSA RSA Problem [4] n x S+2 x P Pairing CDH Problem Our IBRS-2 n x S+2 x P Pairing CDH Problem

Printer friendly Cite/link Email Feedback | |

Author: | Ki, JuHee; Hwang, Jung Yeon; Lee, Dong Hoon |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Geographic Code: | 9CHIN |

Date: | Oct 1, 2012 |

Words: | 10283 |

Previous Article: | Constrained high accuracy stereo reconstruction method for surgical instruments positioning. |

Next Article: | A privacy-aware graph-based access control system for the healthcare domain. |

Topics: |