BRICS RS-98-27 Camenisch & Michels: A Group Signature Scheme Based on an RSA-Variant BRICS

Basic Research in Computer Science

A Group Signature Scheme Based on an RSA-Variant

Jan Camenisch Markus Michels BRICS Report Series RS-98-27 ISSN 0909-0878 November 1998 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1998, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/98/27/

A Group Signature Scheme Based on an RSA-Variant^{∗}

Jan Camenisch^{†}

BRICS Department of Computer Science University of Aarhus Ny Munkegade DK – 8000 Århus C, Denmark

         camenisch@brics.dk

Markus Michels^{‡}

Entrust Technologies r3 security engineering ag Glatt Tower, 6th floor CH – 8301 Glattzentrum, Switzerland

                                     Markus.Michels@entrust.com

November 3, 1998

Abstract

The concept of group signatures allows a group member to sign messages anonymously on behalf of the group. However, in the case of a dispute, the identity of a signature’s originator can be revealed by a designated entity. In this paper we propose a new group signature scheme that is well suited for large groups, i.e., the length of the group’s public key and of signatures do not depend on the size of the group. Our scheme is based on a variation of the RSA problem called strong RSA assumption. It is also more efficient than previous ones satisfying these requirements.

Keywords. Group signature scheme for large groups, digital signature scheme, revocable anonymity.

1 Introduction

In 1991 Chaum and van Heyst put forth the concept of a group signature scheme [16]. Participants are group members, a membership manager, and a revocation manager^{1}. A group signature scheme allows a group member to sign messages anonymously on behalf of the group. More precisely, signatures can be verified with respect to a single public key of the group and do not reveal the identity of the signer. The membership manager is responsible for the system setup and for adding group members while the revocation manager has the ability to revoke the anonymity of signatures.

∗A preliminary version of this paper appeared in [8].

†Part of this work was done while this author was with ETH Zurich.

‡Part of this work was done while this author was with Ubilab, UBS, Switzerland.

1In the original proposal, the membership manager and the revocation manager were a single entity called group manager.

A group signature scheme could for instance be used by an employee of a large company to sign documents on behalf of the company. In this scenario, it is sufficient for a verifier to know that some representative of the company has signed. Moreover, in contrast to when an ordinary signature scheme would be used, the verifier does not need to check whether a particular employee is allowed to sign contracts on behalf of the company, i.e., he needs only to know a single company’s public key. A further application of group signature schemes is electronic cash as was pointed out in [29]. In this scenario, several banks issue coins, but it is impossible for shops to find out which bank issued a coin that is obtained from a customer. Hence, the central bank plays the role of the membership and the revocation manager and all other banks issuing coins are group members. The identification as a group member is another application, e.g., in order to get access to a restricted area [25].

Various group signature schemes have been proposed so far. However, in the schemes presented in [5, 16, 17, 33] the length of signatures and/or the size of the group’s public key depend on the size of the group and thus these schemes are not suitable for large groups. Only in the two schemes presented in [9, 10] (and the blind versions thereof [29]) are the length of signatures and the size of the group’s public key independent of the number of group members^{2}. The schemes presented in [25] satisfy the length requirement as well, but these are inefficient.

In this paper we propose a new group signature scheme for which the length of signatures and the size of the group’s public key do not depend on the size of the group. The security of our scheme relies on a variant of the RSA assumption, called strong RSA-assumption and proposed in [1, 22], the discrete logarithm assumption the Diffie-Hellman decision assumption. Compared to the solutions in [9, 10], our scheme is based on a different number-theoretic assumption and is also more efficient.

2 The Model and an Approach for a Realization

2.1 The Model

A group signature scheme consists of the following algorithms:

setup : An interactive setup protocol between the membership manager, the group members, and the revocation manager. The public output is the group’s public key Y. The private outputs are the individual secret keys x_{G} for each group member, the secret key x_{M} for the membership manager, and the secret key x_{R} for the revocation manager.

sign : A signature generation algorithm that on input a message m, an individual group member’s secret key x_{G}, and the group’s public key Y outputs a signature σ.

verify : A verification algorithm that on input a message m, a signature σ, and the group’s public key Y returns 1 if and only if σ was generated by any group member using sign on input x_{G}, m, and Y. tracing : A tracing algorithm that on input a signature σ, a message m, the revoca-

2The other schemes [26, 32] with the same properties were shown to be flawed [28, 30].

tion manager’s secret key x_{R}, and the group’s public key Y returns the identity ID of the group member who issued the signature σ together with an argument argof this fact.

vertracing : A tracing-verification algorithm that on input a signature σ, a message m, the group’s public key Y, the identity ID of a group member, and an argument arg outputs 1 if and only if arg was generated by tracing with respect to m, σ, Y, x_{R}.

The following informally stated security requirements must hold:

Unforgeability of signatures:Only group members are able to sign messages. Furthermore, they must only be able to sign in such a way that, when the signature is (later) presented to the revocation manager, he will be able to reveal the identity of the signer.

Anonymity of signatures:It is not feasible to find out the group member who signed a message without knowing the revocation manager’s secret key.

Unlinkability of signatures:It is infeasible to decide whether two signatures have been issued by the same group member or not.

No framing: Even if the membership manager, the revocation manager, and some of the group members collude, they cannot sign on behalf of non-involved group members.

Unforgeability of tracing verification:The revocation manager cannot accuse a signer falsely of having originated a given signature, e.g., by issuing an argument arg such that vertracing outputs 1 if input another ID than the one of the signer.

The efficiency of a group signature scheme can be measured by the size of the public key Y, the length of signatures, and by the efficiency of the algorithms sign , verify ,

setup , tracing , and vertracing .

2.2 The Approach of Camenisch and Stadler

The core idea of the schemes proposed in [9, 10] is the following. A group’s public key consists of the membership manager’s public key of an ordinary digital signature scheme and the revocation manager’s public key of a probabilistic encryption scheme. A user, say Alice, who wants to join the group chooses a random secret key x_{G} and computes her membership key z := f(x_{G}), where f is a suitable oneway function. Alice commits to z (for instance by signing it) and sends z and her commitment to the membership manager M who returns her a membership certificate u := sig_{M} (z).

To sign a message m on behalf of the group, Alice encrypts z using the public key of the revocation manager (let c denote this ciphertext) and issues a signature of knowledge^{3} [9] that she knows some values x̃ and ũ such that ũ = sig_{M} (f(x̃)) holds and that f(x̃) is encrypted in c. The verification of such a group-signature is done by checking this signature of knowledge. The revocation manager can easily revoke the anonymity of a group-signature by decrypting c and forwarding this value to the membership manager.

3These are message dependent non-interactive arguments derived from 3-move honest-verifier zeroknowledge proofs of knowledge using the Fiat-Shamir heuristic [20, 21].

To realize a concrete scheme along these lines, one has to find a suitable one-way function f and a suitable signature scheme that yield an efficient signature of knowledge for the values x̃ and ũ. In [9, 10], two proposals based on different number theoretic assumption were put forth. The first assumption is that given e, g, and an RSA-modulus n, it is hard to find integers u and x such that u^{e} ≡ g^{x} + 1 (mod n) holds, where g is an element of large order. The second one is that it is hard to find integers u and x with |x| < |n|/2 such that u^{3} ≡ x^{5}+v (mod n) when given a suitably chosen integer v and an RSA-modulus n.

3 Number Theoretic Assumptions

In this section we describe the assumptions the security of our group signature schemes is based upon. In particular, we will introduce an alternative to the assumptions discussed in the previous section that allows the construction of a new group signature scheme and will show that this assumption can be reduced a variant of the RSA assumption.

Recently, Fujisaki and Okamoto [22] proposed a variation of the well-known RSA assumption [36]: the so-called strong RSA assumption. Let ℓ_{g} be a security parameter and let G(ℓ_{g}) denote the set of groups whose order has length ℓ_{g} and consists of two prime factors of length (ℓ_{g} − 2)/2.

Problem 1 (Strong RSA Problem). Given G and z ∈ G/{±1}, find a pair (u, e) ∈ G×ℤ such that u^{e} = z and e > 1.

Let K denote a key-generator that on input 1^{ℓ_{g}} outputs a G ∈ G(ℓ_{g}) and a z ∈ G/{±1}.

Assumption 1 (Strong RSA Assumption). There exists a probabilistic algorithm K such that for all probabilistic polynomial-time algorithms A, all polynomials p(·), all sufficiently large ℓ_{g}

Pr[z = u^{e} ∧ e > 1 : (G, z) := K(1^{ℓ_{g}} ), (u, e) := A(G, z)] < \frac{1}{p(ℓ_{g})} .

In an implementation of the key-generator K, where G is chosen to be ℤ_{n}^{∗} and n is an RSA modulus, the parameter z should not be chosen as a power in ℤ.

Let us focus on a slight modification of this assumption. Let k, ℓ_{1}, ℓ_{2} < ℓ_{g}, and ϵ > 1 be further security parameters. For simplicity let denote ℓ̃:= ϵ(ℓ_{2} + k) + 1. Let be M(G, z) = {(u, e) | z = u^{e}, u ∈ G, e ∈ {2^{ℓ_{1}} − 2^{ℓ_{2}} , …, 2^{ℓ_{1}} + 2^{ℓ_{2}} }, e ∈ primes}, where G ∈ G(ℓ_{g}) and z ∈ G.

Problem 2 (Modified Strong RSA Problem). Given G, z ∈ G, and M ⊂ M(G, z) with |M| = O(ℓ_{g}) find a pair (u, e) ∈ G × ℤ such that u^{e} = z, e ∈ {2^{ℓ_{1}} − 2ℓ̃, …, 2^{ℓ_{1}} + 2ℓ̃}, and (u, e) ∉ M.

Assumption 2 (Modified Strong RSA Assumption). There exists a probabilistic algorithm K such that for all probabilistic polynomial-time algorithms A, all polynomials p(·), all sufficiently large ℓ_{g}, all M ⊂ M(G, z) with |M| = O(ℓ_{g}), and suitably chosen ℓ_{1}, ℓ_{2}, k, and ϵ

Pr[z = u^{e} ∧ e ∈ {2^{ℓ_{1}} − 2ℓ̃, …, 2^{ℓ_{1}} + 2ℓ̃} ∧ (u, e) ∉ M : (G, z) := K_{1}(1^{ℓ_{g}} ),

(u, e) := A(G, z, M)] < \frac{1}{p(ℓ_{g})} .

A similar assumption was proposed by Barić and Pfitzmann [1], i.e., they require e to be a prime but do not have any restriction an the sizes of the exponents. Possible choices for G are discussed in Section 5. Let us remark that, given u, e, ũ, and ẽwith z = u^{e} = ũẽ and gcd(e, ẽ) = 1, it is easy to find an element ū satisfying z = ū^{eẽ} using the extended Euclidean algorithm. However, as eẽ ∉ {2^{ℓ_{1}} − 2ℓ̃, …, 2^{ℓ_{1}} + 2ℓ̃} for suitable chosen parameter ℓ_{g}, ℓ_{1}, ℓ_{2}, ϵ, and k the integer eẽ does not satisfy the range constraint, i.e., ϵ(ℓ_{2} + k) + 1 < ℓ_{1} must hold.

Adapting methods from [38], it can be shown that Assumption 1 implies Assumption 2. That is, given a probabilistic polynomial-time algorithm A_{2} that solves Problem 2 we construct a probabilistic polynomial-time algorithm that solves Problem 1. Let G and z ∈ G be the given instance of Problem 1. Then choose arbitrary primes e_{1}, …, e_{t} for t = O(ℓ_{g}) satisfying the range conditions and set z̃ := z^{e_{1} ···e_{t}} , ũ_{i} = z̃^{1/e_{i}} := z^{e_{1} ···e_{i−1} e_{i+1} ···e_{t}} for i = 1, …, t, and M := {(u_{i}, e_{i}) | i ∈ {1, …, t} }. Run A_{2} on input G, z̃, M and get (ũ, ẽ) such that ũẽ = z̃and ẽ ∈ {2^{ℓ_{1}} − 2^{ℓ_{2}} , …, 2^{ℓ_{1}} + 2^{ℓ_{2}} }. Now we have ũẽ = z̃ = z^{e_{1} ···e_{t}} . Because of the range condition and since all e_{i}’s are prime, gcd(ẽ, e_{1} ⋯ e_{t}) = 1 holds. Thus two integers a and b such that aẽ + b(e_{1} ⋯ e_{t}) = 1 can be found efficiently and we can compute the pair (u := z^{a} ũ^{b} , ẽ) which is a solution of the given instance of Problem 1. Hence Problem 2 is at least as hard as Problem 1.

Besides the strong RSA assumption, our group signature scheme relies further on the discrete logarithm (DL) assumption and so-called Diffie-Hellman decision (DHD) assumption. Since the latter is not so well known, we state it explicitly. Let G ∈ G(ℓ_{g}), n′ be the divisor of G’s order of length ℓ_{g} − 2. Define the two sets

DH(G) := {(g_{1}, y_{1}, g_{2}, y_{2}) ∈ G^{4} | ord(g_{1}) = ord(g_{2}) = n′, log_{g_{1}} y_{1} = log_{g_{2}} y_{2}}

Q(G) := {(g_{1}, y_{1}, g_{2}, y_{2}) ∈ G^{4} | ord(g_{1}) = ord(g_{2}) = ord(y_{1}) = ord(y_{2}) = n′}

of Diffie-Hellman and arbitrary 4-tuples, respectively.

Assumption 3 (Diffie-Hellman Decision Assumption). There exists a probabilistic algorithm K such that for all probabilistic polynomial-time algorithms A and all sufficiently large ℓ_{g}, the two probability distributions

Pr[a = 1 : G := K(1^{ℓ_{g}} ), T ∈_{R} DH(G), a := A(T)]

and

Pr[a = 1 : G := K(1^{ℓ_{g}} ), T ∈_{R} Q(G), a := A(T)]

are computationally indistinguishable.

Note that in the case G = ℤ_{n}^{∗}, where n is an RSA-modulus, the DHD assumption does not hold. The Jacobi-symbol, which can be computed efficiently without knowing the factorisation of n, leaks information about log_{g_{1}} y_{1} and log_{g_{2}} y_{2}. For instance, if (g_{1}|n) = (g_{2}|n) = (y_{2}|n) = −1 and (y_{1}|n) = 1, then log_{g_{1}} y_{1} ≠ log_{g_{2}} y_{2}. This problem is overcome if G = ⟨g⟩ is defined to be a subgroup of ℤ_{n}^{∗} with (g|n) = 1.

4 Building Blocks

In this section we introduce the building blocks for our scheme borrowing notation from [9, 10]. These building blocks are signature schemes derived from statistical (honest-verifier) zero-knowledge proofs of knowledge using the Fiat-Shamir heuristic [20, 21] and are therefore called “signatures based on a proof of knowledge”, SPK for short. Usually, the security of such building blocks is argued by showing that the underlying interactive protocols is secure and then by assuming that “nothing bad happens” when the verifier is replaced with a collision resistant hash-function. This approach has been formalised as the random oracle model (e.g., see [2, 34])^{4}. For the signer/prover security means that the protocol should be zero-knowledge and for the verifier it means that the protocol should be a proof of knowledge. An example of this method is the Schnorr signature scheme [37] that is derived from an honest-verifier zero-knowledge proof of knowledge of the discrete logarithm of the signer’s public key.

In the following we describe four building blocks. The first one shows the knowledge of a discrete logarithm, the second the equality of two discrete logarithms, the third the knowledge of one out of two discrete logarithms, and the fourth the knowledge of a discrete logarithm that lies in a certain interval. Of course, these building blocks can be combined in a natural way (e.g., see [10]). The building blocks have in common that the prover does not know the order of G, i.e., the verifier chooses a group G = ⟨g⟩ of large order such that only he can know the order. However, the order of magnitude 2^{ℓ_{g}} of the group’s order shall be known to both. Furthermore, the verifier chooses a second generator h and proves that g and h have order p′q′, where p′ and q′ are two primes of length (ℓ_{g} − 2)/2 and that he does not know log_{g} h. How this can be done is discussed in the next section. Since the group order is not publicly known, we define the discrete logarithm of an y ∈ G to the base g to be any integer x such that y = g^{x} holds. Finally, we assume a collision resistant hash function H : {0, 1}^{∗} ) {0, 1}^{k} (e.g., k ≈ 160).

Before we define the building blocks let us explain the notation with the following example [9]: a signature based on a proof of knowledge, denoted

SPK{(α, β) : y = g^{α} ∧ z = g^{β} h^{α} } (m),

is used for ‘proving’ the knowledge of the discrete logarithm of y to the base g and of a representation of z to the bases g and h, and in addition, that the h-part of this representation equals the discrete logarithm of y to the base g. This is equivalent to the knowledge of a pair (α, β) satisfying the equations on the right side of the colon. In the sequel, we use the convention that Greek letters denote the elements whose knowledge is proven and all other letters denote elements that are known to the verifier.

4Recently, it has be shown that this approach does not work for general protocols [11], i.e., there exist protocols (although specially designed ones) which are secure in the random oracle model but yield an insecure signature scheme. However, it is believed that the approach is still valid for the kind of protocols considered here.

4.1 Showing the Knowledge of a Discrete Logarithm

The building block presented in this subsection is an adaption of the protocols for proving the knowledge of a discrete logarithm [14, 37] to the setting with a group of unknown order due to Girault [23, 24]. A consequence of this setting is that the usual knowledge extractor for showing that a protocol is a proof of knowledge does not work: the knowledge extractor does not know the group’s order either and hence cannot compute inverses modulo this group order and therefore not extract the witness. Poupard and Stern [35] give a security proof for this adaption in a weaker security model, i.e., they show that if an attacker was able to carry out the protocol for almost all public keys, then he could also compute the discrete logarithm of the prover’s public key. Since the latter is assumed to be impossible the protocol is concluded to be secure.

An alternative way of proving the security was proposed by Fujisaki and Okamoto [22]. They show that under Assumption 1 the knowledge extractor is able to extract witnesses without knowing the group’s order. We will stick to this method in this paper.

Definition 1. Let ϵ > 1 be a security parameter. A pair (c, s) ∈ {0, 1}^{k} × {−2^{ℓ_{g} +k}, …, 2^{ϵ(ℓ_{g} +k)} } satisfying c = H(g∥y∥g^{s}y^{c}∥m) is a signature of a message m ∈ {0, 1}^{∗} with respect to y and is denoted SPK{(α) : y = g^{α} }(m).

An entity knowing the secret key x ∈ {0, 1}^{ℓ_{g}} such that x = log_{g} y can compute such a signature (c, s) = SPK{(α) : y = g^{α} }(m) of a message m ∈ {0, 1}^{∗} by

• choosing r ∈_{R} {0, 1}^{ϵ(ℓ_{g} +k)} and computing t := g^{r},

• c := H(g∥y∥t∥m), and

• s := r − cx (in ℤ).

In [10] it is analysed how much information (t, c, s) gives about x depending on the choice of ϵ.

Lemma 1. If Assumption 1 holds, then the interactive protocol corresponding to SPK{(α) : y = g^{α} }(m) is a honest-verifier statistical zero-knowledge proof of knowledge of the discrete logarithm of y.

Proof. To prove that the protocol is statistical honest-verifier zero-knowledge for any ϵ > 1, we have to show that an honest verifier, i.e., one who chooses the challenge c uniformly random from {0, 1}^{k}, can simulate a protocol-conversation that is statistically indistinguishable from a protocol-conversation with the prover. The following constitutes a simulator the verifier could use to do so.

The simulator randomly chooses c′ from {0, 1}^{k} and s′ from {0, 1}^{ϵ(ℓ_{g} +k)} according to the uniform distribution. Using these values, the simulator computes t′ = g^{s′} y^{c′}. To prove that these values are statistical indistinguishable from a view of a protocol run with the prover, it suffices to consider the probability distribution P_{S}(s) of the response s of the prover and the probability distribution P_{S′}(s′) according to which the simulator chooses s′. The latter is the uniform distribution over {0, 1}^{ϵ(ℓ_{g} +k)} .

If the prover chooses r uniformly at random from {0, 1}^{ϵ(ℓ_{g} +k)} and the secret key randomly from {0, 1}^{ℓ_{g}} according to any distribution, we have

P_{S}(s) \{ \begin{matrix}= 0 & for s < −(2^{k} − 1)(2^{ℓ_{g}} − 1) \\ ≤ 2^{−ϵ(ℓ_{g} +k)} & for − (2^{k} − 1)(2^{ℓ_{g}} − 1) ≤ s < 0 \\ = 2^{−ϵ(ℓ_{g} +k)} & for 0 ≤ s ≤ 2^{ϵ(ℓ_{g} +k)} − (2^{k} − 1)(2^{ℓ_{g}} − 1) \\ ≤ 2^{−ϵ(ℓ_{g} +k)} & for 2^{ϵ(ℓ_{g} +k)} − (2^{k} − 1)(2^{ℓ_{g}} − 1) < s ≤ (2^{ϵ(ℓ_{g} +k)} − 1) \\ = 0 & for (2^{ϵ(ℓ_{g} +k)} − 1) < s. \end{matrix}

This holds for any distribution of c over {0, 1}^{k}. Thus we have

∑_{α∈ℤ} |P_{S}(α) − P_{S′}(α)| ≤ \frac{2(2^{k} − 1)(2^{ℓ_{g}} − 1)}{2^{ϵ(ℓ_{g} +k)}} ≤ \frac{2^{k+ℓ_{g} +1}}{2^{ϵ(ℓ_{g} +k)}} ≤ \frac{2}{(2^{(ℓ_{g} +k)})^{(ϵ−1)}}

For ℓ_{g} and k as stated in the theorem, the last term can be expressed as one over a polynomial in the input length, and therefore the two distributions are statistical indistinguishable.

Let us show that it is a proof of knowledge. Given the fact that the equivalent protocol (e.g., [37]) for groups of known order is a proof of knowledge it is sufficient two show that the knowledge extractor can compute the witness once he has found two accepting triples. Let (t, c, s) and (t, c̃, s̃) be these two accepting triples. Since t = g^{s}y^{c} = gs̃yc̃ holds we have y^{c−c̃} = g^{s̃−s}. Let d := gcd(c − c̃, s̃− s). Using the extended Euclidean algorithm we obtain values u and v such that u\frac{c−c̃}{d} + v\frac{s̃−s}{d} = 1 and hence we have

g = g^{u \frac{c−c̃}{d} +v \frac{s̃−s}{d}} = (g^{u} y^{v})^{\frac{c−c̃}{d}} .

If d < c − c̃ then g^{u} y^{v} is a \frac{c−c̃}{d} -root of g. Since this contradicts Assumption 1 we must have d = c − c̃, hence c − c̃divides s̃− s, and we can compute the integer

x := \frac{s̃− s}{c − c̃}

such that g^{x} = y.

4.2 Showing the Equality of Two Discrete Logarithms

The next SPK is an adoption of a protocol for showing the equality of two discrete logarithms given in [15] to the setting in which the group’s order is unknown.

Definition 2. Let ϵ > 1 be a security parameter. A pair (c, s) ∈ {0, 1}^{k} × {−2^{ℓ_{g} +k}, …, 2^{ϵ(ℓ_{g} +k)} } satisfying c = H(g∥h∥y_{1}∥y_{2}∥y_{1}^{c}g^{s}∥y_{2}^{c}h^{s}∥m) is a signature of a message m ∈ {0, 1}^{∗} with respect to y_{1} and y_{2} and is denoted

SPK{(α) : y_{1} = g^{α} ∧ y_{2} = h^{α} }(m).

Let x ∈ {0, 1}^{ℓ_{g}} be the secret key of the signer such that y_{1} = g^{x} and y_{2} = h^{x} holds. Then a signature (c, s) = SPK{(α) : y_{1} = g^{α} ∧ y_{2} = h^{α} }(m) of a message m ∈ {0, 1}^{∗} can be computed as follows.

• Choose r ∈_{R} {0, 1}^{ϵ(ℓ_{g} +k)} and compute t_{1} := g^{r}, t_{2} := h^{r},

• c := H(g∥h∥y_{1}∥y_{2}∥t_{1}∥t_{2}∥m), and

• s := r − cx (in ℤ).

The security properties and proofs of this building block follow from the ones of the previous building block and from [15].

4.3 Showing the Knowledge of One Out of Two Discrete Logarithms

The realization of the following SPK of one out of two discrete logarithms is an adoption of a protocol given in [19].

Definition 3. Let ϵ > 1 be a security parameter. A tuple (c_{1}, c_{2}, s_{1}, s_{2}) ∈ {0, 1}^{k} × {0, 1}^{k} × {−2^{ℓ_{g} +k}, …, 2^{ϵ(ℓ_{g} +k)} } × {−2^{ℓ_{g} +k}, …, 2^{ϵ(ℓ_{g} +k)} } satisfying c_{1} ⊕ c_{2} = H(g∥h∥y_{1}∥y_{2}∥y_{1}^{c_{1}} g^{s_{1}} ∥y_{2}^{c_{2}} h^{s_{2}} ∥m) is a signature of a message m ∈ {0, 1}^{∗} with respect to y_{1} and y_{2} and is denoted

SPK{(α, β) : y_{1} = g^{α} ∨ y_{2} = h^{β} }(m).

Without loss of generality, we assume that the signer knows x ∈_{R} {0, 1}^{ℓ_{g}} such that y_{1} = g^{x} holds. Then a signature SPK{(α, β) : y_{1} = g^{α} ∨ y_{2} = h^{β} }(m) of a message m ∈ {0, 1}^{∗} can be computed as follows.

• Choose r_{1} ∈_{R} {0, 1}^{ϵ(ℓ_{g} +k)} , r_{2} ∈_{R} {0, 1}^{ϵ(ℓ_{g} +k)} , and c_{2} ∈_{R} {0, 1}^{k} and compute t_{1} := g^{r_{1}} , t_{2} := h^{r_{2}} y_{2}^{c_{2}} ,

• c_{1} := c_{2} ⊕ H(g∥h∥y_{1}∥y_{2}∥t_{1}∥t_{2}∥m),

• s_{1} := r_{1} − c_{1}x (in ℤ), and s_{2} := r_{2}.

The security properties and proofs of this building block follow from the ones of the previous building blocks and from [19].

4.4 Showing That a Discrete Logarithm Lies in an Interval

The last building block is based on a proof that the secret the prover knows lies in a given interval. It is related to protocols presented in [13, 22].

Definition 4. Let ϵ > 1 be a security parameter and let ℓ_{1} < ℓ_{g} and ℓ_{2} denote lengths. A pair (c, s) ∈ {0, 1}^{k} × {−2^{ℓ_{2} +k}, …, 2^{ϵ(ℓ_{2} +k)} } satisfying c = H(g∥y∥g^{s−c2^{ℓ_{1}}} y^{c}∥m) is a signature of a message m ∈ {0, 1}^{∗} with respect to y and is denoted

SPK{(α) : y = g^{α} ∧ (2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} < α < 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} )}(m).

Such a signature of a message m ∈ {0, 1}^{∗} with respect to a public key y ∈ G can be computed as follows if an integer x ∈ {2^{ℓ_{1}} , …, 2^{ℓ_{1}} + 2^{ℓ_{2}} } is known such that y = g^{x} holds:

• choose r ∈_{R} {0, 1}^{ϵ(ℓ_{2} +k)} , and compute t := g^{r}, • c := H(g∥y∥t∥m), and

• s := r − c(x − 2^{ℓ_{1}} ) (in ℤ).

Lemma 2. If Assumption 1 holds and ϵ > 1 then the interactive protocol corresponding to SPK{(α) : y = g^{α} ∧ (2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} < α < 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} )}(m) is a statistical honest-verifier zero-knowledge proof of knowledge of an integer x such that x ∈ {2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} , …, 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} } and y = g^{x}.

Sketch.The proof that the protocol is statistical honest-verifier zero-knowledge is similar as for Lemma 1.

Let us consider the proof-of-knowledge part. As in the proof of Lemma 1 the knowledge-extractor gets two accepting triples (t, c, s) and (t, c̃, s̃) from which he can similarly compute the integer

x := 2^{ℓ_{1}} + \frac{s̃− s}{c − c̃}

such that g^{x} = y since c − c̃ must divide s̃− s if Assumption 1 holds. It remains to show that this integer lies in the claimed bounds. Due to Definition 4 the integers s and s̃must lie in {−2^{ϵ(ℓ_{2} +k)} , …, 2^{ϵ(ℓ_{2} +k)} } and since the smallest value that c − c̃can have is 1 the computed x must lie in {2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} , …, 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} }.

Note that ϵ(ℓ_{2} + k) + 2 < log (ord(g)) ≈ ℓ_{g} should hold in order to indeed restrict the size of log_{g} y.

5 The Proposed Scheme

In this section we propose a realization of a group signature scheme the security of which is based on Assumptions 2 and 3. The basic idea of the scheme is the following. The membership manager chooses a group G = ⟨g⟩ and a group element z such that Assumptions 2 and 3 hold. Furthermore, he chooses a second generator h such that log_{g} h is unknown. Computing discrete logs in G to the bases g, h, or z must be infeasible. Finally, computing roots in G must be feasible only to the membership manager, i.e., he should the only one who knows the order of G. The revocation manager chooses his secret key x and publishes y = g^{x}.

Each group member chooses a prime e randomly in a determined range together with the membership manager. Only the group member learns e and stores it as a secret key. A membership certificate issued by the membership manager is an element u ∈ G such that u^{e} = z holds. Here we slightly deviate from the approach of Camenisch and Stadler, i.e., the membership certificate and the membership key are the same number. As a consequence, the issuing of certificates must be realized in a way that the membership manager is not able to learn the group member’s secret key e.

A signature of a message m by a group member consists of a triple (a, b, d) ∈ G^{3} and an SPK of integers u and e such that

• the pair (a, b) is an encryption of u under the revocation manager’s public key (which is part of the group public key)

• d commits to e,

• e lies in the necessary range, and

• u^{e} = z holds.

The membership manager can reveal the identity of a signer by asking the revocation manager to decrypt (a, b).

The following paragraphs describe the new scheme in detail and provide security and efficiency analyses.

5.1 The Setup of the Scheme

The setup procedure of our scheme consists of two phases. In the first phase the membership manager and the revocation manager construct the group’s public key and choose their secret keys. This is described in this subsection. In the second phase of the setup, the group members choose their membership secret keys and get their membership certificates. This phase is described in the next subsection.

The membership manager chooses a group G = ⟨g⟩ and two random elements z, h ∈ G with the same (large) order (≈ 2^{ℓ_{g}} ) such that Assumptions 2 and 3 hold. He publishes z, g, h, G, and ℓ_{g} and proves that g, h, and z have the same order which is non-prime, of the order of magnitude 2^{ℓ_{g}} , and non-smooth (how this can be done will be discussed later). The membership manager must further prove that z and h where chosen at random. The revocation manager chooses his secret key x randomly in {0, …, 2^{ℓ_{g}} − 1} and publishes y = g^{x} as his public key. Finally, a hash function H : {0, 1}^{∗} −) {0, 1}^{k} and security parameters ℓ̂, ℓ_{1}, ℓ_{2}, and ϵ are set. An example for choosing the parameters ϵ, ℓ̂, ℓ_{g}, ℓ_{1}, and ℓ_{2} is given in Section 5.6.

A possible choice of G = ⟨g⟩ is a subgroup of ℤ_{n}^{∗} such that (g|n) = 1. In this case the membership manager chooses two large random primes p and q (≈ 2^{ℓ_{g} /2}) of form p = 2p′ + 1 and q = 2q′ + 1, where p′ and q′ are primes as well, such that p, q ≢ 1 (mod 8) and p ≢ q (mod 8) holds. He keeps p and q secret and publishes n := pq. For proving that n if indeed the product of two safe primes the method described in [7] could be used. Verifying that an element a has (large) order at least p′q′ in ℤ_{n}^{∗} and Jacobi symbol 1 can done by anyone: one needs only to test whether a ≢ ±1 (mod n) and gcd(a−1, n) = 1 holds. An alternative choice of G is a suitable elliptic curve (e.g., see [27]).

5.2 The Registration of a Group Member

To become a group member Alice chooses a random prime ê ∈_{R} {2^{ℓ̂−1}, …, 2ℓ̂ − 1} and e ∈_{R} {2^{ℓ_{1}} , …, 2^{ℓ_{1}} + 2^{ℓ_{2}} − 1} such that ê, e ≢ 1 (mod 8) and ê ≢ e (mod 8), Alice computes ẽ := eê and z̃ := zê, commits to ẽ and z̃ (for instance by signing them), sends ẽ, z̃, and their commitments to the membership manager, and carries out the interactive protocols corresponding to

W := SPK⟨(α, β) : zẽ = z̃^{α} ∧ z̃ = z^{β} ∧

(2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} ) < α < (2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} )⟩(z̃) , with the membership manager (cf. previous section). Furthermore, Alice proves the the membership manager that ẽis the product of two primes (e.g., using the methods described in [4, 39]). Using the same arguments as for the building blocks in the previous section, it can be seen that the protocol corresponding to W convinces the membership manager that Alice has chosen ẽand z̃correctly.

The membership manager computes u := z̃^{1/ẽ} and sends u to Alice, who checks that z̃ = uẽ holds (which is equivalent to z = u^{e}). The membership manager stores (u, ẽ, z̃) together with Alice’s identity and her commitments to ẽ and z̃ in a groupmember list. Finally, Alice stores the pair (u, e) as her membership key.

Of course, ℓ̂, ℓ_{1}, and ℓ_{2} must be chosen such that ẽ cannot be factored (cf. Section 5.6) and that Assumption 2 holds. In particular ℓ_{2} ≫ ℓ_{1} − (ℓ̂+ ℓ_{1})/4 must hold (cf. [18]).

5.3 The Generation of a Group-Signature

Let us first define a group-signature and then consider how a group member can compute such a signature.

Definition 5. Let ϵ, ℓ_{1}, and ℓ_{2} be security parameters such that ϵ > 1, ℓ_{2} < ℓ_{1} < ℓ_{g}, and ℓ_{2} < \frac{ℓ_{g} −2}{ϵ} − k holds. A group-signature sign (x_{G}, (g, h, y, z), m) of a message m ∈ {0, 1}^{∗} is a tuple (c, s_{1}, s_{2}, s_{3}, a, b, d) ∈ {0, 1}^{k} × {−2^{ℓ_{2} +k}, …, 2^{ϵ(ℓ_{2} +k)} } × {−2^{ℓ_{g} +ℓ_{1} +k}, …, 2^{ϵ(ℓ_{g} +ℓ_{1} +k)} } × {−2^{ℓ_{g} +k}, …, 2^{ϵ(ℓ_{g} +k)} } × G^{3} satisfying

c = H(g∥h∥y∥z∥a∥b∥d∥z^{c}b^{s_{1} −c2^{ℓ_{1}}} /y^{s_{2}} ∥a^{s_{1} −c2^{ℓ_{1}}} /g^{s_{2}} ∥a^{c}g^{s_{3}} ∥d^{c}g^{s_{1} −c2^{ℓ_{1}}} h^{s_{3}} ∥m).

Remark 1. Such a group-signature would be denoted

SPK{(η, ϑ, ξ) : z = b^{η}/y^{ϑ} ∧ 1 = a^{η}/g^{ϑ} ∧ a = g^{ξ} ∧ d = g^{η}h^{ξ} ∧

(2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} < η < 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} )}(m).

To sign a message m ∈ {0, 1}^{∗} on the group’s behalf, a group member Alice

• chooses an integer w ∈_{R} {0, 1}^{ℓ_{g}} , computes a := g^{w} , b := uy^{w}, and d := g^{e}h^{w},

• chooses r_{1} ∈_{R} {0, 1}^{ϵ(ℓ_{2} +k)} , r_{2} ∈_{R} {0, 1}^{ϵ(ℓ_{g} +ℓ_{1} +k)} , and r_{3} ∈_{R} {0, 1}^{ϵ(ℓ_{g} +k)} , and computes

• t_{1} := b^{r_{1}} (1/y)^{r_{2}} , t_{2} := a^{r_{1}} (1/g)^{r_{2}} , t_{3} := g^{r_{3}} , t_{4} := g^{r_{1}} h^{r_{3}} ,

• c := H(g∥h∥y∥z∥a∥b∥d∥t_{1}∥t_{2}∥t_{3}∥t_{4}∥m),

• s_{1} := r_{1} − c(e − 2^{ℓ_{1}} ) (in ℤ), s_{2} := r_{2} − cew (in ℤ), and s_{3} := r_{3} − cw (in ℤ).

The resulting signature of m is (c, s_{1}, s_{2}, s_{3}, a, b, d). It can easily be verified that it satisfies the verification condition given in Definition 5.

5.4 Verifying Signatures, Tracing, and Verifying Tracing

A signature (c, s_{1}, s_{2}, s_{3}, a, b, d) of a message m can be verified by checking the equation stated in Definition 5.

To reveal the originator of a given signature σ := (c, s_{1}, s_{2}, s_{3}, a, b, d) of a message m, the revocation manager first checks its correctness. He aborts if the signature is not correct. Otherwise he computes u′ := b/a^{x}, issues a signature

P := SPK{(α) : y = g^{α} ∧ b/u′ = a^{α} }(u′∥σ∥m)

(see Section 4.2), and reveals arg := u′∥P. He then looks up u′ in the group-member list and will find the corresponding u, the group member’s identity and his/her commitment to ẽand z̃.

Checking whether the revocation manager correctly revealed the originator of a signature σ = (c, s_{1}, s_{2}, s_{3}, a, b, d) of a message m can simply be done by verifying σ and arg.

5.5 Security Analysis

Before discussing the security requirements described in Section 2.1 let us have a closer look at the interactive protocol corresponding to the generation of a groupsignature.

Theorem 3. The interactive protocol corresponding to the generation of a group signature is a honest-verifier statistical zero-knowledge proof of knowledge of a membership key and certificate provided that Assumption 1 holds. Furthermore, the pair (a, b) encrypts the certificate under the revocation manager’s public key y.

Sketch.Let (t_{1}, t_{2}, t_{3}, t_{4}, c, s_{1}, s_{2}, s_{3}) and (t_{1}, t_{2}, t_{3}, t_{4}, c̃, s̃_{1}, s̃_{2}, s̃_{3}) be two accepting tuples that the knowledge extractor obtained. Thus we get the four equations

z^{c̃−c} = b^{s_{1} −s̃_{1} +(c̃−c)2^{ℓ_{1}}} (1/y)^{s_{2} −s̃_{2}}  (1)
1 = a^{s_{1} −s̃_{1} +(c̃−c)2^{ℓ_{1}}} (1/g)^{s_{2} −s̃_{2}}  (2)
a^{c̃−c} = g^{s_{3} −s̃_{3}}  (3)
d^{c̃−c} = g^{s_{1} −s̃_{1} +(c̃−c)2^{ℓ_{1}}} h^{s_{3} −s̃_{3}}  (4)

Under Assumption 1 we can compute x_{3} := (s_{3} − s̃_{3})/(c̃− c) (in ℤ) such that a = g^{x_{3}} holds (cf. Lemma 1). Using that we can rewrite Equation 4 as

(dh^{−x_{3}} )^{c̃−c} = g^{s_{1} −s̃_{1} +(c̃−c)2^{ℓ_{1}}}

and compute (since under Assumption 1 c̃− c divides s_{1} − s̃_{1} ) the integer

x_{1} = \frac{s_{1} − s̃_{1}}{c̃− c} + 2^{ℓ_{1}}

such that d = g^{x_{1}} h^{x_{3}} and x_{1} ∈ {2^{ℓ_{1}} − 2^{ϵ(ℓ_{2} +k)+1} , …, 2^{ℓ_{1}} + 2^{ϵ(ℓ_{2} +k)+1} } holds (cf. Lemma 2). Similarly, from Equation 1 we can compute (under Assumption 1) the integer

x_{2} = \frac{s_{2} − s̃_{2}}{c̃− c}

such that z = \frac{b^{x_{1}}}{y^{x_{2}}} and a^{x_{1}} = g^{x_{2}} holds. Since a = g^{x_{3}} we must have g^{x_{1} x_{3}} = g^{x_{2}} and hence y^{x_{1} x_{3}} = y^{x_{2}} and

z = \frac{b^{x_{1}}}{y^{x_{2}}} = \frac{b^{x_{1}}}{(y^{x_{3}} )^{x_{1}}} = (\frac{b}{y^{x_{3}}} )^{x_{1}} .

Thus we can conclude that (x_{1}, \frac{b}{y^{x_{3}}} ) is a valid membership key-pair. Furthermore, (a, d) is an unconditional binding commitment to x_{1} whereas (a, b) is an unconditional binding commitment to \frac{b}{y^{x_{3}}} . Since the log_{g} h is supposed to be unknown, the value x_{1} is computationally hidden. However, the revocation manager knows the integer log_{g} y and is therefore able to compute the second element of that pair as

\frac{b}{a^{log_{g} y}} = \frac{b}{y^{x_{3}}} .

Let us now informally discuss the security properties of the proposed group signature scheme.

Unforgeability of signatures:Due to Theorem 3 the tuple (a, b, d) is an unconditionally binding commitment to a valid membership key-pair (e, u). Under Assumption 2 it is infeasible to compute such a pair without knowing the group’s order (even if other pairs are already known; cf. Section 3). Therefore the membership key-pair must stem from an execution of the registration protocol with the membership manager and only group members can sign. Furthermore, Theorem 3 shows that the revocation manager will be able to reveal the membership key of the signer by decrypting (a, b) which is sufficient for the membership manager to identify the originator of a signature.

Anonymity of signatures:Assuming that the function H is a random function, the values c, s_{1}, s_{2}, and s_{3} do statistically not reveal any knowledge. Hence, deciding whether a signature (c, s_{1}, s_{2}, s_{3}, a, b, d) originates from a group member with public key u′ requires to decide whether log_{g} a = log_{y} \frac{b}{u′} . If one was able to decide this efficiently, this would violate Assumption 3.

Unlinkability of signatures:Linking two signatures, i.e., deciding whether two signatures (c, s_{1}, s_{2}, s_{3}, a, b, d) and (c′, s′_{1}, s′_{2}, s′_{3}, a′, b′, d′) originate from the same group member requires to decide whether log_{g} \frac{a}{a′} = log_{y} \frac{b}{b′} = log_{h} \frac{d}{d′} , as c, s_{1}, s_{2}, s_{3} and c′, s′_{1}, s′_{2}, s′_{3} do not reveal useful knowledge. Under Assumption 3 this is infeasible and hence signatures are unlinkable.

No framing: Given Theorem 3, signing in the name of a group member with certificate u and requires the knowledge of log_{u} z. This can only be obtained by either factor the value ẽthat the membership manager received from the group member during registration or by computing the discrete logarithm of z to the base u. Both is assumed to be infeasible.

Unforgeability of tracing verification:The revocation manager has to issue an SPK denoted P as evidence that he decrypted the pair (a, b) correctly. Since (a, b) is a unconditionally binding commitment, the revocation manager has no means to prove that a membership key different from the one of the originator is encrypted in (a, b).

5.6 Efficiency Analysis

With ϵ = 9/8, ℓ_{g} = ℓ̂ = 1200, ℓ_{1} = 860, ℓ_{2} = 600, and k = 160, the signature generation and verification need little less than 13′000 modular multiplications modulo a 1200-bit modulus in average, and the signature is about 1 KBytes long. Compared to the most efficient scheme given in [9], our scheme is about three times more efficient and signatures are about three times shorter when choosing the same modulus for both schemes. However, the registration protocol is less efficient in our scheme. Signatures could made shorter without compromising the security of the scheme if the parameter w in the signing procedure is chosen from a smaller domain, e.g., {0, 1}^{ℓ_{2}} instead of {0, 1}^{ℓ_{g}} .

6 Conclusion

It is worthwhile noting that it is possible to realize blind group signatures using the techniques given in [6, 31], which are much more efficient than the blind versions of [9, 10] given in [29]. Splitting the membership and/or the revocation manager can be done by applying the techniques of [3, 12], respectively (see also [10]). As the signature generation algorithm was derived from an interactive protocol, a group identification scheme (also called identity escrow [25]) is obtained by using this protocol for identification.

Acknowledgments

The second author was supported by the Swiss National Foundation (SNF/SPP project no. 5003-045293). We gratefully acknowledge the discussions with Ivan Damgård, Markus Stadler, and Bartosz Przydatek.

References

[1] N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In W. Fumy, editor, Advances in Cryptology — EURO-CRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 480–494. Springer Verlag, 1997.

[2] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In First ACM Conference on Computer and Communication Security, pages 62–73. Association for Computing Machinery, 1993.

[3] D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1296 of Lecture Notes in Computer Science, pages 425–439. Springer Verlag, 1997.

[4] J. Boyar, K. Friedl, and C. Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies. Journal of Cryptology, 4(3):185–206, 1991.

[5] J. Camenisch. Efficient and generalized group signatures. In W. Fumy, editor, Advances in Cryptology — EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 465–479. Springer Verlag, 1997.

[6] J. Camenisch, U. Maurer, and M. Stadler. Digital payment systems with passive anonymity-revoking trustees. In E. Bertino, H. Kurth, G. Martella, and E. Montolivo, editors, Computer Security — ESORICS 96, volume 1146 of Lecture Notes in Computer Science, pages 33–43. Springer Verlag, 1996.

[7] J. Camenisch and M. Michels. Proving in zero-knowledge that a number n is the product of two safe primes. Manuscript, submitted for publication.

[8] J. Camenisch and M. Michels. A group signature scheme with improved efficiency. In K. Ohta and D. Pei, editors, Advances in Cryptology — ASIACRYPT ’98, volume 1514 of Lecture Notes in Computer Science, pages 160–174. Springer Verlag, 1998.

[9] J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1296 of Lecture Notes in Computer Science, pages 410–424. Springer Verlag, 1997.

[10] J. L. Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, 1998. Diss. ETH No. 12520, Hartung Gorre Verlag, Konstanz.

[11] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), 1998.

[12] D. Catalano and R. Gennaro. New efficient and secure protocols for verifiable signature sharing and other applications. In H. Krawczyk, editor, Advances in Cryptology — CRYPTO ’98, volume 1642 of Lecture Notes in Computer Science, pages 105–120, Berlin, 1998. Springer Verlag.

[13] A. Chan, Y. Frankel, and Y. Tsiounis. Easy come – easy go divisible cash. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 561–575. Springer Verlag, 1998.

[14] D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In D. Chaum and W. L. Price, editors, Advances in Cryptology — EUROCRYPT ’87, volume 304 of Lecture Notes in Computer Science, pages 127–141. Springer-Verlag, 1988.

[15] D. Chaum and T. P. Pedersen. Transferred cash grows in size. In R. A. Rueppel, editor, Advances in Cryptology — EUROCRYPT ’92, volume 658 of Lecture Notes in Computer Science, pages 390–407. Springer-Verlag, 1993.

[16] D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, Advances in Cryptology — EUROCRYPT ’91, volume 547 of Lecture Notes in Computer Science, pages 257–265. Springer-Verlag, 1991.

[17] L. Chen and T. P. Pedersen. New group signature schemes. In A. De Santis, editor, Advances in Cryptology — EUROCRYPT ’94, volume 950 of Lecture Notes in Computer Science, pages 171–181. Springer-Verlag, 1995.

[18] D. Coppersmith. Finding a small root of a bivariatre interger equation; factoring with high bits known. In U. Maurer, editor, Advances in Cryptology — EUROCRYPT ’96, volume 1070 of Lecture Notes in Computer Science, pages 178– 189. Springer Verlag, 1996.

[19] R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Y. G. Desmedt, editor, Advances in Cryptology — CRYPTO ’94, volume 839 of Lecture Notes in Computer Science, pages 174–187. Springer Verlag, 1994.

[20] U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1:77–94, 1988.

[21] A. Fiat and A. Shamir. How to prove yourself: Practical solution to identification and signature problems. In A. M. Odlyzko, editor, Advances in Cryptology — CRYPTO ’86, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer Verlag, 1987.

[22] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1294 of Lecture Notes in Computer Science, pages 16–30. Springer Verlag, 1997.

[23] M. Girault. An identity-based identification scheme based on discrete logarihtms modulo a composite number. In I. B. Damgård, editor, Advances in Cryptology – EUROCRYPT ’90, volume 473 of Lecture Notes in Computer Science, pages 481–486. Springer-Verlag, 1991.

[24] M. Girault. Self-certified public keys. In D. W. Davies, editor, Advances in Cryptology — EUROCRYPT ’91, volume 547 of Lecture Notes in Computer Science, pages 490–497. Springer-Verlag, 1992.

[25] J. Kilian and E. Petrank. Identity escrow. In H. Krawczyk, editor, Advances in Cryptology — CRYPTO ’98, volume 1642 of Lecture Notes in Computer Science, pages 169–185, Berlin, 1998. Springer Verlag.

[26] S. J. Kim, S. J. Park, and D. H. Won. Convertible group signatures. In K. Kim and T. Matsumoto, editors, Advances in Cryptology — ASIACRYPT ’96, volume 1163 of Lecture Notes in Computer Science, pages 311–321. Springer Verlag, 1996.

[27] K. Koyama, U. Maurer, T. Okamoto, and S. Vanstone. New public-key schemes based on elliptic curves over the ring Z_{n}. In J. Feigenbaum, editor, Advances in Cryptology — CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 252–266. Springer-Verlag, 1992.

[28] C. H. Lim and P. J. Lee. On the security of convertible group signatures. Electronics Letters, 1996.

[29] A. Lysyanskaya and Z. Ramzan. Group blind digital signatures: A scalable solution to electronic cash. In Proc. Second International Conference on Financial Cryptography, 1998.

[30] M. Michels. Comments on some group signature schemes. Technical Report TR-96-3-D, Departement of Computer Science, University of Technology, Chemnitz-Zwickau, Nov. 1996.

[31] T. Okamoto. Provable secure and practical identification schemes and corresponding signature schemes. In E. F. Brickell, editor, Advances in Cryptology

— CRYPTO ’92, volume 740 of Lecture Notes in Computer Science, pages 31–53. Springer-Verlag, 1993.

[32] S. J. Park, I. S. Lee, and D. H. Won. A practical group signature. In Proceedings of the 1995 Japan-Korea Workshop on Information Security and Cryptography, pages 127–133, Jan. 1995.

[33] H. Petersen. How to convert any digital signature scheme into a group signature scheme. In M. Lomas and S. Vaudenay, editors, Security Protocols Workshop, Paris, 1997.

[34] D. Pointcheval and J. Stern. Security proofs for signature schemes. In U. Maurer, editor, Advances in Cryptology — EUROCRYPT ’96, volume 1070 of Lecture Notes in Computer Science, pages 387–398. Springer Verlag, 1996.

[35] G. Poupard and J. Stern. Security analysis of a practical “on the fly” authentication and signature generation. In K. Nyberg, editor, Advances in Cryptology

— EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 422–436. Springer Verlag, 1998.

[36] R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120– 126, Feb. 1978.

[37] C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239–252, 1991.

[38] A. Shamir. On the generation of cryptographically strong pseudorandom sequences. In ACM Transaction on Computer Systems, volume 1, pages 38–44, 1983.

[39] J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public key. In C. Pomerance, editor, Advances in Cryptology — CRYPTO ’87, volume 293 of Lecture Notes in Computer Science, pages 128–134. Springer-Verlag, 1988.

Recent BRICS Report Series Publications

RS-98-27 Jan Camenisch and Markus Michels. A Group Signature Scheme Based on an RSA-Variant. November 1998. 18 pp. Preliminary version appeared in Ohta and Pei, editors, Advances in Cryptology: 4th ASIACRYPT Conference on the Theory and Applications of Cryptologic Techniques, ASIACRYPT ’98 Proceedings, LNCS 1514, 1998, pages 160–174.

RS-98-26 Paola Quaglia and David Walker. On Encoding pπ in mπ. October 1998. 27 pp. Full version of paper to appear in Foundations of Software Technology and Theoretical Computer Science: 18th Conference, FCT&TCS ’98 Proceedings, LNCS, 1998.

RS-98-25 Devdatt P. Dubhashi. Talagrand’s Inequality in Hereditary Settings. October 1998. 22 pp.

RS-98-24 Devdatt P. Dubhashi. Talagrand’s Inequality and Locality in Distributed Computing. October 1998. 14 pp.

RS-98-23 Devdatt P. Dubhashi. Martingales and Locality in Distributed Computing. October 1998. 19 pp.

RS-98-22 Gian Luca Cattani, John Power, and Glynn Winskel. A Categorical Axiomatics for Bisimulation. September 1998. ii+21 pp. Appears in Sangiorgi and de Simone, editors, Concurrency Theory: 9th International Conference, CONCUR ’98 Proceedings, LNCS 1466, 1998, pages 581–596.

RS-98-21 John Power, Gian Luca Cattani, and Glynn Winskel. A Representation Result for Free Cocompletions. September 1998. 16 pp.

RS-98-20 Søren Riis and Meera Sitharam. Uniformly Generated Submodules of Permutation Modules. September 1998. 35 pp.

RS-98-19 Søren Riis and Meera Sitharam. Generating Hard Tautologies Using Predicate Logic and the Symmetric Group. September 1998. 13 pp.

RS-98-18 Ulrich Kohlenbach. Things that can and things that can’t be done in PRA. September 1998. 24 pp.