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

The user outputs the signature σ =( T 1 ,T 2 ,T 3 ,T 4 ,T 5 ,T 6 ,U ).

- Verif ( m, σ ) this procedure simply verifies the correctness of the signature
of knowledge U , as detailed in Section A.4.
- Open ( m, σ, ( rsk 1 , rsk 2 , rsk 3 , rsk 4 ) , Tab )if σ is valid, the opening judge com-
putes A = T 3 − ( rsk 1 .T 1 + rsk 2 .T 2 ) and realizes the signature of knowledge

τ = SoK rsk 1 , rsk 2 : A = T 3 −

( rsk 1 .T 1 + rsk 2 .T 2 ) ∧ Rpk 1 = rsk 1 .G ∧ Rpk 1 =

rsk 2 .G .Byusing Tab , the judge can retrieve the key Upk i associated to the
user certificate A . Then he outputs Upk , S (= PkiSign usk ( A )), A and τ .
- Judge ( m, σ, A, τ, Upk , Tab ) this procedure verifies the correctness of the sig-
nature of knowledge τ . The signature S ,storedin Tab , permits to check
that the certificate A is the one which have been given to the user during
the Join procedure. If both signatures ( τ and S ) are valid, the procedure
outputs 1 else it outputs 0.

This protocol ensures all the security requirements of a group signature scheme
under the q -SDH [4] and the decision linear assumption (see Section A.2). We
refer the interested reader to [14] and [3] for the security aspects of this scheme.

A.4 Focus on the Signature of Knowledge
During the signature of a message, a user must produce the signature of knowl-
edge U . We detailed here how this should be done.

- Choose r α 1 ,r β 1 ,r α 2 ,r β 2 ∈ R Z p ; r x ,r z ∈ R Z q
- Compute

P 1 = r α 1 .G ; P 2 = r β 1 .G ; P 3 = r α 2 .G ; P 4 = r β 2 .G ;
P 5 =( r α 1 + r β 1 ) Rpk 1 −

( r α 2 + r β 2 ) Rpk 2 ;
P 6 = e ( T 3 ,G 2 ) r x e ( Rpk 1 , GMpk ) − ( r α 1 + r β 1 ) e ( Rpk 1 ,G 2 ) −r z
- Compute c = H ( m, T 1 ,T 2 ,T 3 ,T 4 ,T 5 ,T 6 ,P 1 ,P 2 ,P 3 ,P 4 ,P 5 ,P 6 )

- Compute

s α 1 = r α 1 + c.α 1

(mod q ); s β 1 = r β 1 + c.β 1 (mod q );

s α 2 = r α 2 + c.α 2 (mod q ); s β 2 = r β 2 + c.β 2 (mod q );

s x = r x + c.x (mod q ); s z = r z + c.z (mod q ) .

The signature is the tuple U =( c , s α 1 , s β 1 , s α 2 , s β 2 , s x , s z ).
The verification of this signature of knowledge is done as follow. The verifier
first computes:
- P 1 = s α 1 .G c.T 1 , P 2 = s β 1 .G − c.T 4 , P 4 = s β 2 .G − − c.T 2 , P 3 = s α 2 .G − c.T 5

and P 5 =( s α 1 + s β 1 ) Rpk 1 − ( s α 2 + s β 2 ) Rpk 2 − c. ( T 3 − T 6 )

- P 6 = e ( T 3 ,G 2 ) s x e ( Rpk 1 , GMpk ) − ( s α 1 + s β 1 ) e ( Rpk 1 ,G 2 ) −s z e ( G 1 ,G 2 )

) −c

e ( T 3 , GMpk

Finally the verifier validates the signature of knowledge if:

c = H ( m, T 1 ,T 2 ,T 3 ,T 4 ,T 5 ,T 6 ,P 1 ,P 2 ,P 3 ,P 4 ,P 5 ,P 6 ) .