Group Signatures are Suitable for Constrained Devices - Information Security and Cryptology-ICISC 2010 - page 148

A.2 Decision Linear Problem and Encryption

The Decision Linear Problem has been introduced in [3] and is defined as follows.

Definition 5. Given G, G ,H,α.G,β.G ,γ.H ∈ G as input, the Decision Linear

Problem consists to decide if γ = α + β or not.

A great advantage of this problem is that it is still a hard problem even in bilinear
groups where the DDH problem is easy. Based on this problem, the authors of [3]
introduced a new encryption scheme called Linear Encryption:

- GenParam (1 λ ): let be a group of prime order q . Select three generators

G, G and Rpk such that there exists rsk 1 , rsk 2 ∈ Z q which verify Rpk =
rsk 1 .G = rsk 2 .G . The public-key of the system is the tuple ( G, G , Rpk )
while the secret key is ( rsk 1 , rsk 2 ).
- Enc ( m ): to encrypt the message m

G

∈ G

, this algorithm selects two random

∈ Z q and computes T 1 = α.G, T 2 = β.G ,T 3 = m +( α + β ) Rpk .
The encrypted message is ( T 1 ,T 2 ,T 3 ).
- Dec ( T 1 ,T 2 ,T 3 ): to decrypt a message, this algorithm computes m = T 3 −
rsk 1 .T 1 − rsk 2 .T 2 .

values α, β

To define the parameters of this scheme verifying is Rpk = rsk 1 .G = rsk 2 .G ,a
solution is described by the next steps:

- choose a random generator G ∈ G ;
- choose a random value rsk ∈ R Z q and compute G = rsk .G ;
- choose a first secret key rsk 1 ∈ R Z q and compute Rpk = rsk 1 .G ;
- compute rsk 2 = rsk 1 / rsk (mod q ).

A.3 The XSGS Group Signature Scheme

We now focus on the XSGS protocol, introduced by Delerablee and Pointcheval
in [14]. For security reasons (see Section 8.1 of the extended version of [3] for more
details), we use the XSGS scheme without the XDH assumption. We thus use the
double linear encryption scheme, introduced by Boneh et al. in [3] and described
in Appendix A.2, instead of a double ElGamal encryption, as suggested in [14].
The group signature scheme is described by the following procedures, where λ
is a security parameter.

- GenParam (1 λ ): this procedure generates the public parameters of the sys-
tem and also the keys of the different entities as follows:
• a bilinear environment ( q, G 1 , G 2 , G T ,e,ψ );

• the parameters for the double linear encryption, i.e. a generator G ∈ R G 1

and another generator G = rsk .G where rsk ∈ R Z q .

2

• the secret keys of the opening judge ( rsk 1 , rsk 3 )

q , rsk 2 = rsk 1 / rsk ,
rsk 4 = rsk 3 / rsk and the associated public keys Rpk 1 = rsk 1 .G = rsk 2 .G
and Rpk 2 = rsk 3 .G = rsk 4 .G ;

∈ R Z