Abstract:
To generate a group signature on a message, a processor generates a two-level signature on an identity of the group member at the first level and the message at the second level; generates a commitment to the identity of the group member, commitments to each group element and a proof that the identity and the group elements satisfy a predetermined equation; encodes the identity of the group member in the group signature in a bit-wise manner using an identity-based encryption scheme where the message serves as the identity of the identity-based encryption scheme to produce a ciphertext; generates a first proof that the ciphertext encrypts the identity of the group member; generates a second proof that the encoded identity is an identity of a group member in a certificate signed by a group manager and that the certificate was used to generate the signature on the message at the second level; and outputs the group signature comprising the two-level signature, the commitments, the encoded identity of the group member and the proofs

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates generally to cryptography, and in particular to group signatures. 
       BACKGROUND 
       [0002]    This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art. 
       Group Signatures 
       [0003]    Group signatures, introduced at EUROCRYPT 1991 by David Chaum and Eugene van Heyst in “Group Signatures”, allow members of a group to sign messages anonymously on behalf of the whole group. The group is controlled by a group manager who handles the enrolment of the group members, and who has the ability to open a group signature generated by a member of its group in order to determine who generated this group signature. 
         [0004]    Group signatures are useful in contexts where it is desirable to preserve the signer&#39;s anonymity with the possibility to retrieve, by some authority, the signer&#39;s identity, for example in case of abuse. An illustrative example are employees equipped with badges that open the doors to certain protected areas. The badges use group signatures to prove the right to enter the protected areas, but a log of entries does not show who entered at what time (as legal reasons may preclude this). However, it should still be possible, e.g. in case of theft, to find out the identity of a signing group member. 
         [0005]    A group signature with message-dependent opening (GS-MDO) is a group signature where an opening authority (OA) should not be able to open all messages by itself. To do this, the OA needs the cooperation of another authority, called admitter, that generates a trapdoor t M  associated with the message M. In order to identity the author of a signature, the OA has to use both its private key and the trapdoor t M . Formally, a GS-MDO scheme is a tuple (Keygen, Sign, Verify, TrapGen, Open) of efficient algorithms with the following specification: 
         [0000]    Keygen(λ, N): given a security parameter λε          and a maximal number of group members Nε         , this randomized algorithm outputs a group public key gpk, a vector
 
gsk=(gsk[0], . . . , gsk[N−1]) of group members&#39; private keys as well as private keys msk ADM  and ok for the admitter and the opening authority, respectively.
 
Sign: takes as input a message M, a private key gsk[i] and the group public key gpk. It outputs a signature σ.
 
Verify: is a deterministic algorithm taking as input a signature a, a message M and a group public key gpk. It returns either 1 or 0 depending on whether or not the signature is successfully verified or not.
 
TrapGen: is a possibly randomized algorithm that takes as input the admitter&#39;s private key msk ADM  and outputs a trapdoor t M  allowing the OA to open all signatures on the message M.
 
Open: takes as input a message M, a valid signature a with regard to gpk, the opening authority&#39;s private key ok and a trapdoor t M  for the message M. It outputs          ε{0, . . . , N−1}∪{⊥}, which is either the index of a group member or a symbol indicating an opening failure.
 
         [0006]    Sakai et al. considered [see Y. Sakai, K. Emura, G. Hanaoka, Y. Kawai, T. Matsuda, and K. Omote. Group Signatures with Message-Dependent Opening. In 5th International Conference on Pairing-Based Cryptography (Pairing 2012),  Lecture Notes on Computer Science  series, Springer, 2013.] three security properties in a model that can be seen as an extension of the Bellare-Micciancio-Warinschi [M. Bellare, D. Micciancio, B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In  Eurocrypt &#39; 03 , Lecture Notes on Computer Science  2656, pp. 614-629, 2003.]. The first one, called full traceability, captures that no coalition of dishonest group members should be able to create a non-trivial signature that cannot be traced to one of them. This should remain true even if the adversary can invoke an oracle that returns signatures on behalf of honest group members. 
         [0007]    Definition 1 
         [0008]    A GS-MDO scheme provides full traceability if, for any λε         , any Nεpoly(λ) and any Probabilistic Polynomial Time (PPT) adversary A involved in the experiment hereafter, it holds that the advantage for the adversary A 
         [0000]      Adv A   trace (λ)= Pr [Exp A   trace (λ, N )=1]εnegl(λ)
 
         [0000]    is a negligible function in the security parameter if the experiment Exp A   trace (λ,N) proceeds as follows, where C denotes a dynamically growing set of corrupted users. 
         [0000]    
       
         
               
             
               
               
             
               
             
               
               
             
               
             
           
               
                   
               
             
             
               
                 (gpk, ok, msk ADM , gsk) ← Keygen(λ,N) 
               
               
                 st ← (ok, msk ADM , gpk) 
               
               
                 C ← Ø ; K ← ε ; Cont ← true 
               
               
                 while (Cont = true) do 
               
             
          
           
               
                   
                 (Cont, st, j) ← A Sign(gsk[·],·) (st,K) 
               
               
                   
                 if Cont = true then C ← C ∪ {j} ; K ← gsk[j] end if 
               
             
          
           
               
                 end while 
               
               
                 (M*, σ*) ← A Sign(gsk[·],·) (guess; st) 
               
               
                 if Verify(gpk, M*, σ*) = 0 then Return 0 
               
               
                 if Open(gpk, TrapGen(gpk, msk ADM , M*), M*, σ*, , ok) = ⊥ then Return 
               
               
                 1 
               
               
                 if ∃j* ∈ {1, ..., N} such that 
               
             
          
           
               
                   
                 (j*=Open(gpk, M*, σ*, t M *, ok)            (j* ∉ C)            ((j*, M*) was not 
               
               
                   
                 queried to 
               
               
                   
                 the Sign(gsk[.],.) oracle ) with t M * ← TrapGen(gpk, msk ADM , M*) 
               
             
          
           
               
                 then Return 1 
               
               
                 else Return 0 
               
               
                   
               
             
          
         
       
     
         [0009]    In a GS-MDO scheme, neither the OA or the admitter should be able to identify the author of a signature alone. First, the notion of anonymity against the admitter captures that, without the private key of the OA, the admitter is unable to distinguish signatures created by two distinct group members. This remains true even if the admitter has access to the private keys of all group members and to an oracle that opens adversarially-chosen signatures (as long as these differ from the challenge signature σ*). 
         [0010]    Definition 2 
         [0011]    A GS-MDO scheme provides full anonymity against the admitter if, for any λε         , any Nεpoly(λ) and any Probabilistic Polynomial Time (PPT) adversary A, the function 
         [0000]      Adv A   anon-adm (λ)= Pr [Exp A   anon-adm (λ, N )=1]εnegl(λ)
 
         [0000]    is a negligible function in the security parameter if the experiment Exp A   anon-adm (λ,N) proceeds as follows 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 (gpk, ok, msk ADM , gsk) ← Keygen(λ,N) 
               
               
                   
                 (st, j 0 , j 1 , M*) ← A Oracle-ok (gpk, gsk, msk ADM ) 
               
               
                   
                 σ* ← Sign(gpk, gsk[j b ], M*) 
               
               
                   
                 b′← A Oracle-ok (st, σ*) 
               
               
                   
                 Return 1 if b′ = b 
               
               
                   
                   
               
             
          
         
       
     
         [0012]    In the above, Oracle-ok denotes an oracle that takes as input any adversarially chosen signature σ≠σ* and uses ok and msk ADM  to determine and return the identity of the signer. 
         [0013]    The notion of anonymity against the opener models the inability of the OA to open signatures without having obtained an appropriate message-related trapdoor from the admitter. Formally, the adversary has access to the OA&#39;s private key as well as the private keys of all group members and to an oracle returning trapdoors for arbitrary messages as long as they differ from the message of the challenge signature σ*. 
         [0014]    Definition 3 
         [0015]    A GS-MDO scheme provides full anonymity against the opener if, for any λε         , any Nεpoly(λ) and any Probabilistic Polynomial Time (PPT) adversary A, the function 
         [0000]      Adv A   anon-oa (λ)= Pr [Exp A   anon-oa (λ, N )=1]εnegl(λ)
 
         [0000]    is a negligible function in the security parameter if the experiment Exp A   anon-oa (λ,N) goes as follows 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 (gpk, ok, msk ADM , gsk) ← Keygen(λ,N) 
               
               
                   
                 (st, j 0 , j 1 , M*) ← A Oracle-ADM (gpk, gsk, ok) 
               
               
                   
                 σ* ← Sign(gpk, gsk[j b ], M*) 
               
               
                   
                 b′ ← A Oracle-ADM  (st, σ*) 
               
               
                   
                 Return 1 if b′ = b 
               
               
                   
                   
               
             
          
         
       
     
         [0016]    In the above notation, Oracle-ADM is an oracle that returns trapdoors for arbitrary messages M≠M* chosen by the adversary. 
         [0017]    The first practical and collusion-resistant group signature was given by Ateniese et al. [G. Ateniese, J. Camenisch, M. Joye, G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In  Crypto &#39; 00 , Lecture Notes in Computer Science  1880, pp. 255-270, 2000.] while schemes with short signatures were presented by Boneh et al. [D. Boneh, X. Boyen, H. Shacham. Short Group Signatures. In  Crypto &#39; 04 , Lecture Notes in Computer Science  3152, pp. 41-55. Springer, 2004.]. 
         [0018]    Simplified security models for group signatures were put forth in various papers [see for example M. Bellare, D. Micciancio, B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In  Eurocrypt &#39; 03 , Lecture Notes in Computer Science  2656, pp. 614-629, 2003. M. Bellare, H. Shi, C. Zhang. Foundations of group signatures: The case of dynamic groups. In  CT - RSA &#39; 05 , Lecture Notes in Computer Science  3376, pp. 136-153, 2005. A. Kiayias, M. Yung. Secure scalable group signature with dynamic joins and separable authorities.  International Journal of Security and Networks  ( IJSN ) Vol. 1, No. 1/2, pp. 24-45, 2006. Earlier version appeared as Cryptology ePrint Archive: Report 2004/076, 2004.] 
         [0019]    Group signatures with security proofs in the standard model are described different publications [see for example G. Ateniese, J. Camenisch, S. Hohenberger, B. de Medeiros. Practical group signatures without random oracles. Cryptology ePrint Archive: Report 2005/385, 2005. X. Boyen, B. Waters. Compact Group Signatures Without Random Oracles. In  Eurocrypt &#39; 06 , Lecture Notes in Computer Science  4004, pp. 427-444, Springer, 2006. X. Boyen, B. Waters. Full-Domain Subgroup Hiding and Constant-Size Group Signatures. In  PKC &#39; 07 , Lecture Notes in Computer Science  4450, pp. 1-15, 2007. J. Groth. Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures. In  Asiacrypt&#39; 06 , Lecture Notes in Computer Science  4284, pp. 444-459, Springer, 2006. J. Groth. Fully anonymous group signatures without random oracles. In  Asiacrypt  2007 , Lecture Notes in Computer Science  4833, pp. 164-180. Springer, 2007.] 
         [0020]    However, the problem of restricting the power of the opening authority was only considered very recently by Sakai et al. [already mentioned]. 
         [0021]    The primitive called “group signature with message-dependent opening” was suggested for the first time by Sakai et al., where a theoretical (inefficient) construction was described. Sakai et al. also suggested a relatively efficient construction based on specific assumptions and an Identity-Based Encryption (IBE) scheme described by Heng et al. [S.-H. Heng, K. Kurosawa. k-Resilient Identity-Based Encryption in the Standard Model. In  CT - RSA &#39; 04 , Lecture Notes in Computer Science  2964, pp. 67-80, 2004.]. However, this concrete construction only provides a weak flavor of anonymity against the opening authority (cf. Definition 3). Specifically, it only achieves anonymity against the opener as long as the adversary does not obtain more than a pre-determined number d of message-specific tokens. Moreover, the public key has size O(d). 
         [0022]    In the general construction of Sakai et al., the signing algorithm proceeds by choosing two random session keys K PKE  and K IBE  which are separately encrypted using a CCA2-secure public-key encryption scheme and an IBE scheme, respectively. These two keys K PKE  and K IBE  are then used to hide the group member&#39;s credential in the fashion of multiple encryptions while adding a proof that the hidden value is a valid and properly encrypted credential. 
       Identity-Based Encryption (IBE) 
       [0023]    As the invention makes use of identity-based encryption (IBE), some background information on this will now be presented. 
         [0024]    Definition 4 
         [0025]    [see further A. Shamir. Identity-Based Cryptosystems and Signature Schemes. In  Crypto &#39; 84 , Lecture Notes on Computer Science  196, pp. 47-53, 1984. and D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In  SIAM Journal of Computing  32(3), pp. 586-615, 2003, earlier version in  Crypto &#39; 01 , Lecture Notes on Computer Science  2139, pp. 213-229, 2001.] An Identity-Based Encryption scheme (IBE) is a tuple (Setup, Keygen, Encrypt, Decrypt) of probabilistic polynomial-time algorithms (PPT) such that:
       Setup takes as input a security parameter λε          and outputs a master public key mpk and a matching master secret key msk.   Keygen takes as input an identity ID and a master secret key msk. It outputs a private key d ID  for the identity ID.   Encrypt takes as input the master public key mpk, an identity ID and a message M and outputs a ciphertext C.   Decrypt takes as input the master public key mpk, a decryption key d ID  and a ciphertext C and outputs a message M.       
 
         [0030]    Correctness requires that, for any λε         , any outputs (mpk, msk) of Setup(λ), any plaintext M and any identity ID, whenever d ID ←Keygen(msk, ID), then Decrypt(mpk, d ID , Encrypt(mpk, ID, M))=M. 
         [0031]    Definition 5 
         [0032]    [see further Boneh and Franklin] An IBE system is semantically secure (or IND-ID-CPA secure) if no PPT adversary A has non-negligible advantage in this game:
       1. The challenger generates a master key pair (mpk, msk)←Setup(λ) and gives mpk to A.   2. A issues a number of key extraction queries for identities ID of its choice. The challenger responds with d ID ←Keygen(msk, ID).   3. When the adversary A decides that phase 2 is over, it chooses distinct equal-length messages M 0 , M 1  and an identity ID* that has never been queried to the key extraction oracle at step 2. The challenger flips a coin       
 
         [0000]    
       
         
           
             d 
              
             
                
               R 
             
              
             
               { 
               
                 0 
                 , 
                 1 
               
               } 
             
           
         
       
     
         [0000]    and returns a challenge ciphertext C*=Encrypt(mpk, ID, M d *).
       4. A issues new queries but cannot ask for the private key of ID*.   5. A finally outputs a bit d′ε{0,1} and wins if d′=d. A&#39;s advantage is defined as the distance Adv ind-id-cpa (A):=|Pr[d′=d]−½.       
 
         [0038]    Waters [see B. Waters. Efficient Identity-Based Encryption Without Random Oracles. In  Eurocrypt &#39; 05 , Lecture Notes on Computer Science  3494, pp. 114-127, 2005.] described the following IBE scheme that allows encrypting any message in            T . 
         [0000]    Setup(λ): Choose bilinear groups (         ,            T ) of prime order p&gt;2 λ . Then: 
         [0039]    1. Choose 
         [0000]    
       
         
           
             
               α 
                
               
                  
                 R 
               
                
               
                 ℤ 
                 p 
               
             
             , 
             
               g 
                
               
                  
                 R 
               
                
                
             
             , 
             
               
                 g 
                 2 
               
                
               
                  
                 R 
               
                
                
             
           
         
       
     
         [0000]    and set g 1 =g α . 
         [0040]    2. Choose 
         [0000]    
       
         
           
             
               u 
               0 
             
             , 
             
               u 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 u 
                 L 
               
                
               
                 ← 
                 R 
               
                
                
             
             , 
           
         
       
     
         [0000]    for some Lεpoly(λ). These will be used to implement a number-theoretic hash function H         : {0,1} L →          such that any L-bit string 
         [0041]    Σ=Σ[1] . . . τ[L]ε{0,1} L  is mapped to the value H U (τ)=u 0 ·Π i=1   L u i   τ[i] . 
         [0042]    The master public key is defined as 
         [0000]        mpk =((         ,           T ), p,g,g   1   =g   α   ,g   2   ,{u   i } i=0   L ) 
         [0043]    and the master secret key is msk:=g 2   α . 
         [0000]    Keygen(msk, ID): given the master secret key msk=g 2   α  and an identity IDε{0,1} L , compute and return d ID =(d 1 ,d 2 )=(g 2   α ·H U (ID) r ,g r ), with 
         [0000]    
       
         
           
             
               r 
                
               
                  
                 R 
               
                
               
                 ℤ 
                 p 
               
             
             . 
           
         
       
     
         [0000]    Encrypt(mpk, ID, M): to encrypt a message Mε           T , choose 
         [0000]    
       
         
           
             s 
              
             
                
               R 
             
              
             
               ℤ 
               p 
             
           
         
       
     
         [0000]    and compute 
         [0000]        C   1   =g   s   C   2   =H   U ( ID ) s   C   0   =M·e ( g   1   ,g   2 ) s . 
         [0044]    Return the ciphertext C=(C 0 , C 1 , C 2 )ε           T ×           2 . 
         [0000]    Decrypt(mpk, d ID , C): parse the ciphertext C as C=(C 0 , C 1 , C 2 ). Compute and return M=C 0 ·e(C 2 , d 2 )/e(C 1 , d 1 ). 
         [0045]    Waters&#39; IBE is known to be IND-ID-CPA secure assuming that the Decision Bilinear Diffie-Hellman (DBDH) problem is hard. Moreover, a private key d ID  can be seen as a signature on the message ID. Each signature (S 1 , S 2 ) satisfies e(S 1 , g)=e(g 1 , g 2 )·e(H U (ID), S 2 ). 
         [0046]    In some cases, the description of the scheme can be simplified by replacing public elements (g 1 , g 2 )ε           2  by e(g, g) ω =e(g 1 , g 2 ), so that the private key becomes g ω . 
         [0047]    In the following, a two-level hierarchical extension of Waters signatures will be used. Specifically, the public key contains the description of two distinct number theoretic hash functions H U : {0,1} L     1   →          and H v : {0,1} L     2   →         . A signature on a two-block mesage (M 1 , M 2 ) consists of (S 1 , S 2 , S 3 )=(g w ·H U (M 1 ) r ·H V (M 2 ) s , g r , g s ) and satisfies the verification equation 
         [0000]        e ( S   1   ,g )= e ( g,g ) ω   ·e ( H   U ( M   1 ), S   2 )· e ( H   V ( M   2 ), S   3 ).
 
       Groth-Sahai Proof Systems 
       [0048]    Groth and Sahai have described efficient non-interactive proof systems allowing a prover to convince a verifier that committed group elements satisfy certain algebraic relations [see J. Groth, A. Sahai. Efficient non-interactive proof systems for bilinear groups. In  Eurocrypt&#39; 08 , Lecture Notes in Computer Science  4965, pp. 415-432, 2008.]. These non-interactive proofs are said witness indistinguishable (WI) because, if several sets of committed variables (called witnesses) satisfy the proved relation, the proof does not reveal any information about which specific witnesses were used by the prover. 
         [0049]    The Groth-Sahai non-interative witness indistinguishable (NIWI) proof systems can be based on the Decision Linear Problem (DLIN) assumption. In this case, they use prime order groups and a common reference string (CRS, i.e. a set of common public parameters that are trusted to have the appropriate distribution; it is produced by some trusted party and used by both the prover and the verifier) consisting of three vectors {right arrow over (f)} 1 , {right arrow over (f)} 2 , {right arrow over (f)} 3 ε           3 , where {right arrow over (f)} 1 =(f 1 , 1, g) and {right arrow over (f)} 2 =(1, f 2 , g) for some f 1 , f 2 , gε         . To commit to a group element Xε         , the prover chooses 
         [0000]    
       
         
           
             r 
             , 
             s 
             , 
             
               t 
                
               
                  
                 R 
               
                
               
                 ℤ 
                 p 
                 * 
               
             
           
         
       
     
         [0000]    and computes {right arrow over (C)}=(1,1,X)·{right arrow over (f)} t   r ·{right arrow over (f)} 2   s ·{right arrow over (f)} 3   t . On a perfectly sound CRS, {right arrow over (f)} 3 ={right arrow over (f)} 1   ξ     1   ·{right arrow over (f)} 2   ξ     2   , where ξ 1 , ξ 2 ε           p *. Commitments {right arrow over (C)}=(f 1   r+ξ     1     t , f 2   s+ξ     2     t , X·g r+s+t(ξ     1     +ξ     2)   ) are extractable commitments whose distribution is that of Boneh-Boyen-Shacham (BBS) ciphertexts [see D. Boneh, X. Boyen, H. Shacham. Short Group Signatures. In  Crypto&#39; 04 , Lecture Notes in Computer Science  3152, pp. 41-55. Springer, 2004.]: committed values can be extracted using β 1 =log g (f 1 ), β 2 =log g (f 2 ). In the witness indistinguishability (WI) setting, vector {right arrow over (f)} 3  is chosen outside the span of ({right arrow over (f)} 1 , {right arrow over (f)} 2 ), so that {right arrow over (C)} is a perfectly hiding commitment. Under the DLIN assumption, the two kinds of CRS are computationally indistinguishable. 
         [0050]    To commit to an exponent xε           p , one computes {right arrow over (C)}={right arrow over (φ)} x ·{right arrow over (f)} 1   r ·{right arrow over (f)} 2   s , with 
         [0000]    
       
         
           
             r 
             , 
             
               s 
                
               
                  
                 R 
               
                
               
                 ℤ 
                 p 
                 * 
               
             
           
         
       
     
         [0000]    using a CRS comprising vectors {right arrow over (φ)},{right arrow over (f)} 1 ,{right arrow over (f)} 2 . In the soundness setting, {right arrow over (φ)},{right arrow over (f)} 1 ,{right arrow over (f)} 2  are linearly independent vectors (typically, one chooses {right arrow over (φ)}={right arrow over (f)} 3 ·(1,1,g) where {right arrow over (f)} 3 ={right arrow over (f)} 1   ξ     1   ·{right arrow over (f)} 2   ξ     2   ) whereas, in the WI setting, choosing {right arrow over (φ)}={right arrow over (f)} 1   ξ     1   ·{right arrow over (f)} 2   ξ     2    gives a perfectly hiding commitment since {right arrow over (C)} is always a BBS encryption of 1         . On a perfectly sound CRS (where {right arrow over (f)} 3 ={right arrow over (f)} 1   ξ     1   ·{right arrow over (f)} 2   ξ     2    and {right arrow over (φ)}={right arrow over (f)} 3 ·(1,1,g)), commitments to exponents are not fully extractable since the trapdoor (α 1 , α 2 ) only allows recovering g x  from {right arrow over (C)}={right arrow over (φ)} x ·{right arrow over (g)} 1   r ·{right arrow over (g)} 2   s . 
         [0051]    To provide evidence that committed group elements satisfy a set of relations, the prover computes one commitment per variable and one proof element per relation. Such efficient NIWI proofs are available for pairing-product equations, which are relations of the type 
         [0000]    
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         A 
                         i 
                       
                       , 
                       
                         χ 
                         i 
                       
                     
                     ) 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                         
                     
                      
                     
                       
                         e 
                          
                         
                           ( 
                           
                             
                               χ 
                               i 
                             
                             , 
                             
                               χ 
                               j 
                             
                           
                           ) 
                         
                       
                       
                         a 
                         
                           i 
                           , 
                           j 
                         
                       
                     
                   
                 
               
             
             = 
             
               t 
               T 
             
           
         
       
     
         [0052]    for variables χ 1 , . . . , χ n ε          and constants t T ε           T , A 1 , . . . , A n ε         , a i,j ε           p , for i, jε{1, . . . , n}. 
         [0053]    In pairing-product equations, proofs for quadratic equations require 9 group elements whereas linear equations (i.e., where a i,j =0 for all i,j in the equation only cost 3 group elements each. 
         [0054]    Efficient NIWI proofs also exist for multi-exponentiation equations which are equations of the form 
         [0000]    
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 m 
               
                
               
                   
               
                
               
                 
                   A 
                   i 
                   
                     y 
                     i 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       j 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       χ 
                       j 
                       
                         b 
                         j 
                       
                     
                     · 
                     
                       
                         ∏ 
                         
                           i 
                           = 
                           1 
                         
                         m 
                       
                        
                       
                           
                       
                        
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                             
                         
                          
                         
                           χ 
                           j 
                           
                             
                               y 
                               i 
                             
                              
                             
                               γ 
                               ij 
                             
                           
                         
                       
                     
                   
                 
               
             
             = 
             T 
           
         
       
     
         [0055]    for variables χ 1 , . . . , χ n ε         , y 1 , . . . , y m ε           p  and constants T, A 1 , . . . , A m ε         , b 1 , . . . , b n ε           p , and γ ij ε         , for iε{1, . . . , m}, jε{1, . . . , n}. 
         [0056]    Multi-exponentiation equations admit non-interactive zero-knowledge (NIZK) proofs, i.e. proofs that can be perfectly simulated (using a simulation trapdoor) without knowing the witnesses on a simulated CRS. 
         [0057]    For linear equations (i.e., when γ ij =0 for all i,j), the size of the proofs depends on the form of the considered equation. Namely, linear multi-exponentiation equations of the type Π j−1   n χ j   b     j j   =T (resp. Π i=1   m A i   y     i   =T) demand 3 (resp. 2) group elements. 
       Kiltz&#39;s Cryotosystem 
       [0058]    Kiltz has described a chosen-ciphertext-secure public-key encryption scheme based on the DLIN assumption [see E. Kiltz. Chosen-ciphertext security from tag-based encryption. In  TCC &#39; 06 , Lecture Notes in Computer Science  3876, pp. 581-600, 2006.]. The public key is (X, Y, U, V)=(g β     x   ,g β     y   ,g β     u   ,g β     v   ) if gε          is part of the public parameters. To encrypt mε         , the sender generates a one-time signature key pair (SK, VK)←G(λ), picks 
         [0000]    
       
         
           
             
               z 
               1 
             
             , 
             
               
                 z 
                 2 
               
                
               
                  
                 R 
               
                
               
                 ℤ 
                 p 
                 * 
               
             
           
         
       
     
         [0000]    and computes 
         [0000]      ψ=( VK,Ψ   1 ,Ψ 2 ,Ψ 3 ,Ψ 4 ,Ψ 5 ,σ)=( VK,X   z     1     ,Y   z     2   ,( g   VK   ·U ) z     1   ,( g   VK   ·V ) z     2     ,m·g   z     1     +z     2   ,σ)
 
         [0000]    where σ is a signature of (Ψ 1 ,Ψ 2 , Ψ 3 , Ψ 4 , Ψ 5 ). To decrypt ψ, the receiver first checks that Ψ 3 =Ψ 1   (VK+β     u     )/β     x   , Ψ 4 =Ψ 2   (VK+β     v     )/β     y    and that σ is a valid one-time signature on the message (Ψ 1 ,Ψ 2 ,Ψ 3 ,Ψ 4 ,Ψ 5 ). If so, the receiver outputs the plaintext m=Ψ 5 /(Ψ 1   1/β     x   Ψ 2   1/β     y   ). 
         [0059]    It will be appreciated that there is a need for a more efficient scheme than the ones in the prior art. The present invention provides such a scheme. 
       SUMMARY OF INVENTION 
       [0060]    In a first aspect, the invention is directed to a method of generating a group signature on a message. A processor generates a two-level signature on an identity of the group member at the first level and the message at the second level; generates a commitment to the identity of the group member, commitments to group elements which form a certificate for the identity and a proof that the identity and the group elements satisfy a predetermined equation; encodes the identity of the group member in the group signature in a bit-wise manner where a given bit value corresponds to a given group element using an identity-based encryption scheme where the message serves as the identity of the identity-based encryption scheme to produce a ciphertext; generates a first proof that the ciphertext encrypts the identity of the group member; generates a second proof that the encoded identity is an identity of a group member in the certificate signed by a group manager and that the certificate was used to generate the signature on the message at the second level; and outputs the group signature comprising the two-level signature, the commitments, the encoded identity of the group member and the proofs. 
         [0061]    In a first embodiment, the processor further generates a further signature on the two-level signature, the commitments, the encoded identity of the group member and the proofs using a one-time signature key; and the group signature further comprises the further signature. It is advantageous that the processor further generates, using a private key of the group member, a one-time signature key pair comprising the one-time signature key. 
         [0062]    In a second embodiment, the two-level signature is a two-level Waters signature. 
         [0063]    In a second aspect, the invention is directed to a device for generating a group signature on a message. The device comprises a processor configured to: generate a two-level signature on an identity of the group member at the first level and the message at the second level; generate a commitment to the identity of the group member, commitments to group elements which form a certificate for the identity and a proof that the identity and the group elements satisfy a predetermined equation; encode the identity of the group member in the group signature in a bit-wise manner where a given bit value corresponds to a given group element using an identity-based encryption scheme where the message serves as the identity of the identity-based encryption scheme to produce a ciphertext; generate a first proof that the ciphertext encrypts the identity of the group member; generate a second proof that the encoded identity is an identity of a group member in the certificate signed by a group manager and that the certificate was used to generate the signature on the message at the second level; and output the group signature comprising the two-level signature, the commitments, the encoded identity of the group member and the proofs. 
         [0064]    In a first embodiment, the processor is further configured to generate a further signature on the two-level signature, the commitments, the encoded identity of the group member and the proofs using a one-time signature key; and the group signature further comprises the further signature. It is advantageous that the processor is further configured to generate, using a private key of the group member, a one-time signature key pair comprising the one-time signature key. 
         [0065]    In a second embodiment, the two-level signature is a two-level Waters signature. 
         [0066]    In a third aspect, the invention is directed to a method of verifying a group signature on a message, the group signature comprising a two-level signature on an identity of a group member at the first level and the message at the second level, a commitment to the identity, commitments to group elements which form a certificate for the identity, a ciphertext comprising an encoded identity of the group member, a proof that the identity and the group elements satisfy a predetermined equation, a proof that the ciphertext encrypts the identity of the group member, a proof that the encoded identity is an identity of a group member in the certificate signed by a group manager and that the certificate was used to generate the signature on the message at the second level. A processor verifies that the ciphertext is a valid ciphertext, that the commitments verify properly and that the proofs verify properly; and validates the group signature upon successful verifications. 
         [0067]    In a first embodiment, the group signature further comprises a further signature on the two-level signature, the commitment to the identity, the commitments to the group elements, the ciphertext, the proof that the identity and the group elements satisfy the predetermined equation, the proof that the ciphertext encrypts the identity of the group member, the proof that the encoded identity is an identity of a group member in the certificate and that the certificate was used to generate the signature on the message at the second level. The processor further verifies the further signature and validates the group signature upon successful verification of the further signature. 
         [0068]    In a second embodiment, the two-level signature is a two-level Waters signature. 
         [0069]    In a fourth aspect, the invention is directed to a device for verifying a group signature on a message, the group signature comprising a two-level signature on an identity of a group member at the first level and the message at the second level, a commitment to the identity, commitments to group elements which form a certificate for the identity, a ciphertext comprising an encoded identity of the group member, a proof that the identity and the group elements satisfy a predetermined equation, a proof that the ciphertext encrypts the identity of the group member, a proof that the encoded identity is an identity of a group member in the certificate signed by a group manager and that the certificate was used to generate the signature on the message at the second level. The device comprises a processor configured to: verify that the ciphertext is a valid ciphertext, that the commitments verify properly and that the proofs verify properly; and validate the group signature upon successful verifications. 
         [0070]    In a first embodiment, the group signature further comprises a further signature on the two-level signature, the commitment to the identity, the commitments to the group elements, the ciphertext, the proof that the identity and the group elements satisfy the predetermined equation, the proof that the ciphertext encrypts the identity of the group member, the proof that the encoded identity is an identity of a group member in the certificate and that the certificate was used to generate the signature on the message at the second level; and the processor is further configured to verify the further signature and to validate the group signature upon successful verification of the further signature. 
         [0071]    In a second embodiment, the two-level signature is a two-level Waters signature. 
         [0072]    In a fifth aspect, the invention is directed to a non-transitory computer program product having stored thereon instructions that, when executed by a processor, perform the method of the first aspect. 
         [0073]    In a sixth aspect, the invention is directed to a non-transitory computer program product having stored thereon instructions that, when executed by a processor, perform the method of the third aspect. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0074]    Preferred features of the present invention will now be described, by way of non-limiting example, with reference to the accompanying drawings, in which: 
           [0075]      FIG. 1  illustrates a group signature system according to a preferred embodiment of the invention. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0076]    The present invention is directed to a group signature scheme with message-dependent opening and logarithmic-size signature. 
         [0077]    The present invention uses a different approach than Sakai et al. Instead of encrypting two random session keys which are used to conceal the group member&#39;s credential, the method of the present invention directly encrypts the bits of the group member&#39;s identity as if it were the session key K in the structure-preserving IBE scheme described hereinafter. This allows reducing the number of bit-carrying IBE ciphertext components from O(λ) to O(log N). In order to make sure that neither the admitter or the opening authority will be able to individually open any signature, the invention adds a second encryption layer and additionally encrypts—under the admitter&#39;s public key—the IBE ciphertext components which depend on the bits of the group member&#39;s identity. 
         [0078]    In the present invention, each group member is assigned a l-bit identifier, where l=log N, and obtains a Waters signature on this identifier as a private key gsk[i]. Then, as in the Boyen-Waters group signature [see “Compact Group Signatures Without Random Oracles” already mentioned], each member signs messages using a two-level hierarchical extension of Waters signatures at step 1 of the signing algorithm described hereinafter. The group member does not let the resulting signature appear in the clear (since this would reveal its identity) but rather generates commitments to this signature and to its identity along with non-interactive proofs that these commitments contain a valid signature on some hidden message. 
         [0079]    In order to make the proofs that the group member has correctly encoded the bits of its identity within a set of l IBE ciphertexts {(C j,1 , C j,2 , C j,3 , C j,4 )} i=1   l  (all of which are encrypted using the message to sign as an identity) NIZK (and not just NIWI), extra auxiliary variables (with their own commitments) are introduced and used to simulate the adversary&#39;s view in the proofs of anonymity. 
         [0080]    In order to prevent the admitter from opening signatures without knowing the private key of the opening authority, the signer additionally encrypts each IBE ciphertext (C j,1 , C j,2 , C j,3 , C j,4 ) (or, more precisely, its component C j,3 ) under the public key of the opening authority using Kiltz&#39;s encryption scheme. 
       Preferred Embodiment 
       [0081]    Keygen(λ,N): given a security parameter λε          and N=2 l , 
         [0082]    1. Choose bilinear groups (         ,            T ) of prime order p&gt;2 λ  with 
         [0000]    
       
         
           
             
               g 
                
               
                  
                 R 
               
                
                
             
             . 
           
         
       
     
         [0083]    2. As a Common Reference String for the Groth-Sahai NIWI proof system (already described), select vectors f=({right arrow over (f)} 1 , {right arrow over (f)} 2 , {right arrow over (f)} 3 ) such that {right arrow over (f)} 1 =(f 1 ,1,g)ε           3 , {right arrow over (f)} 2 =(1,f 2 ,g)ε           3  and {right arrow over (f)} 3 ={right arrow over (f)} 1   ξ     1   ·{right arrow over (f)} 2   ξ     2   , where f 1 =g β     1   , 
         [0000]    
       
         
           
             
               f 
               2 
             
             = 
             
               
                 g 
                 
                   β 
                   2 
                 
               
                
               
                 ← 
                 R 
               
                
                
             
           
         
       
     
         [0000]    and 
         [0000]    
       
         
           
             
               β 
               1 
             
             , 
             
               β 
               2 
             
             , 
             
               ξ 
               1 
             
             , 
             
               
                 
                   ξ 
                   2 
                 
                  
                 
                    
                   R 
                 
                  
                 
                   ℤ 
                   p 
                   * 
                 
               
               . 
             
           
         
       
     
         [0000]    In addition, {right arrow over (Φ)}={right arrow over (f)} 3 ·(1,1,g). 
         [0084]    3. Generate a master key pair (mskIBE, mpkIBE) for the IBE scheme described hereinafter. These consist of msk IBE =(g 2   α     0   ,g 2   α     1   ) and mPk IBE =(g 0 =g α     0   ,g 1 =g α     1   ,g 2 {u i } i=0   L ), where Lεpoly(λ) denotes the length of (hashed) messages to be signed. For a message Mε{0,1} L , the function H U (M)ε          defined as 
         [0000]    
       
         
           
             
               
                 H 
                 U 
               
                
               
                 ( 
                 M 
                 ) 
               
             
             = 
             
               
                 u 
                 0 
               
               · 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   L 
                 
                  
                 
                     
                 
                  
                 
                   u 
                   i 
                   
                     M 
                      
                     
                       [ 
                       i 
                       ] 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where M[i]ε{0,1} denotes the i-th bit of M. 
         [0085]    4. Generate a key pair (sk W , pk W ) for a two-level hierarchical Waters signature (described hereinbefore). At level 1 (resp. level 2), messages will be of length l (resp. L). This key pair consists of sk W =g ω  and 
         [0000]        pk   W =( e ( g,g ) ω   ,{v   i } i=0   l   ,{w   i } i=0   L ) 
         [0000]    where ωε R             p . Analogously to step 3, H W (M) denotes the function that maps the message Mε{0,1} L  to H W (M)=ω 0 ·Π i=0   L ω i   M[i] , where M[i]ε{0,1} denotes the i-th bit of M. 
         [0086]    5. For each iε0, . . . , N−1) generate the private key gsk[i] of member i as a Waters signature 
         [0000]    
       
         
           
             
               gsk 
                
               
                 [ 
                 i 
                 ] 
               
             
             = 
             
               ( 
               
                 
                   
                     g 
                     ω 
                   
                   · 
                   
                     
                       ( 
                       
                         
                           v 
                           0 
                         
                         · 
                         
                           
                             ∏ 
                             
                               j 
                               = 
                               1 
                             
                              
                           
                            
                           
                               
                           
                            
                           
                             v 
                             j 
                             
                               
                                 id 
                                 i 
                               
                                
                               
                                 [ 
                                 j 
                                 ] 
                               
                             
                           
                         
                       
                       ) 
                     
                     r 
                   
                 
                 , 
                 
                   g 
                   r 
                 
               
               ) 
             
           
         
       
     
         [0000]    with 
         [0000]    
       
         
           
             
               r 
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
             , 
           
         
       
     
         [0000]    on the message id i =id i [1] . . . id i [l]ε{0,1} l  which is obtained as the binary expansion of iε0, . . . , N−1). The private key sk W  is not needed beyond this point and can be erased after the generation of the vector of private keys gsk=(gsk[0], . . . , gsk[N−1]). 
         [0087]    6. Choose a key pair (X,Y,U,V)=(g β     x   ,g β     y   ,g β     u   ,g β     v   ) with 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     β 
                     x 
                   
                   , 
                   
                     β 
                     y 
                   
                   , 
                   
                     β 
                     u 
                   
                   , 
                   
                     β 
                     v 
                   
                 
                 ) 
               
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
             , 
           
         
       
     
         [0000]    for Kiltz&#39;s CCA2-secure encryption scheme (already described). 
         [0088]    7. Select a strongly unforgeable one-time signature scheme Σ=(G,S,V). Any suitable prior art one-time signature scheme provided that it is strongly unforgeable. A definition of strongly unforgeable may be found in J. H. An, Y. Dodis and T. Rabin: On the Security of Joint Signature and Encryption. Eurocrypt 2002. 
         [0089]    The admitter&#39;s message specification key consists of msk ADM :=msk IBE . The private key ok of the opening authority is defined as ok:=(β x ,β y ,β u ,β v ). The private key of member i is gsk[i] (as defined in step 5) while the group public key is defined to be 
         [0000]        gpk: =((         ,           T ), p,g,f =( {right arrow over (f)}   1   ,{right arrow over (f)}   2   ,{right arrow over (f)}   3 ), mpk   IBE   ,pk   W ,( X,Y,U,V ),Σ)
 
         [0000]    Sign(gpk, gsk[i], M): to sign a message Mε{0,1} L  using the i-th group member&#39;s private key gsk[i]=(S i,1 S i,2 )=(g ω v 0 ·Π j=1   l v j   id     i     [j] ) r ,g r ), generate a one-time signature key pair (SK,VK)←Σ·G(λ) and: 
         [0090]    1. Generate a two-level Waters signature where the message is id i ε{0,1} l  at the first level and Mε{0,1} L  at level 2. The signature comprises 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         Ω 
                         1 
                       
                       , 
                       
                         Ω 
                         2 
                       
                       , 
                       
                         Ω 
                         3 
                       
                     
                     ) 
                   
                   = 
                     
                    
                   
                     ( 
                     
                       
                         
                           S 
                           
                             i 
                             , 
                             1 
                           
                         
                         · 
                         
                           
                             ( 
                             
                               
                                 v 
                                 0 
                               
                               · 
                               
                                 
                                   ∏ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                    
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   v 
                                   i 
                                   
                                     
                                       id 
                                       i 
                                     
                                      
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             r 
                              
                             
                                 
                             
                              
                             ′ 
                           
                         
                         · 
                         
                           
                             
                               H 
                               W 
                             
                              
                             
                               ( 
                               M 
                               ) 
                             
                           
                           s 
                         
                       
                       , 
                       
                         
                           S 
                           
                             i 
                             , 
                             2 
                           
                         
                         · 
                         
                           g 
                           
                             r 
                              
                             
                                 
                             
                              
                             ′ 
                           
                         
                       
                       , 
                       
                         g 
                         s 
                       
                     
                     ) 
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     ( 
                     
                       
                         
                           g 
                           ω 
                         
                         · 
                         
                           
                             ( 
                             
                               
                                 v 
                                 0 
                               
                               · 
                               
                                 
                                   ∏ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                    
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   v 
                                   i 
                                   
                                     
                                       id 
                                       i 
                                     
                                      
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             r 
                              
                             
                                 
                             
                              
                             ″ 
                           
                         
                         · 
                         
                           
                             
                               H 
                               W 
                             
                              
                             
                               ( 
                               M 
                               ) 
                             
                           
                           s 
                         
                       
                       , 
                       
                         g 
                         
                           r 
                            
                           
                               
                           
                            
                           ″ 
                         
                       
                       , 
                       
                         g 
                         s 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where r″=r+r′. 
         [0091]    2. Generate a Groth-Sahai commitment {right arrow over (C)} H     V    to H V =v 0 ·Π j=0   l v j   id     i     [j] . Then, for each jε{0, . . . , l}, generate a commitment {right arrow over (C)} F     j    to the group element F j =g id     i     [l]  and generate a NIWI proof {right arrow over (π)} H     V   ε           3  that e(H V ,g)·Π j=1   l e(u j ,F j ) −1 =e(v 0 , g). 
         [0092]    Since this is a linear equation, {right arrow over (π)} H     V    only requires 3 group elements. 
         [0093]    3. Choose 
         [0000]    
       
         
           
             
               s 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 s 
                  
               
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               ω 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 ω 
                  
               
                
               
                 ← 
                 R 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    For i=1 to l, compute 
         [0000]        C   j,1   =g   s     j     ,C   j,2   =H   U ( M ) s     j     ,C   j,3   =g   id     i     [j]   s     j     /ω     j     ,C   j,4   =g   2   ω     j   . 
         [0094]    Then encrypt C j,3  using Kiltz&#39;s encryption scheme by choosing 
         [0000]    
       
         
           
             
               z 
               
                 j 
                 , 
                 1 
               
             
             , 
             
               
                 z 
                 
                   j 
                   , 
                   2 
                 
               
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
     
         [0000]    and computing 
         [0000]      Ψ j =(Ψ j,1 ,Ψ j,2 ,Ψ j,3 ,Ψ j,4 ,Ψ j,5 )= X   z     j,1     ,Y   z     j,2     ,C   j,3   ·g   z     j,1     +z     j,2   ,( g   VK   ·U ) z     j,1   ,( g   VK   ·V ) z     j,2   ).
 
         [0095]    The next step is to prove that the ciphertexts {Ψ j } j=1   l  encrypt {C j,3 } j=1   l , such that {(C j,1 , C j,2 , C j,3 , C j,4 )} j=1   l  are of the form given in this step with id i [j]ε{0,1}. 
         [0096]    4. Generate NIZK proofs for the statements mentioned at the end of step 3 by generating commitments {right arrow over (C)} θ ={right arrow over (φ)} θ ·{right arrow over (f)} 1   r     θ   ·{right arrow over (f)} 2   s     θ    as well as {right arrow over (C)} Γ  and {right arrow over (C)} Γ     2    to the variables 
         [0000]      θ=1 ,γ=g   θ Γ 2   =g   2   θ 
 
         [0097]    and a non-interactive proof {right arrow over (π)} Γ  for these five equalities, which requires 9 group elements (3 for each equation). Then, for each jε{1, . . . , l}, generate Groth-Sahai commitments {right arrow over (C)} G     j   , {right arrow over (C)} Θ     j   , {right arrow over (C)} Z     j,1    and {right arrow over (C)} Z     j,2    to the variables G j =g 1   id     i     [j] ·g 0   1-id     i     [j] , Θ j =g s     j     /ω     j   , Z j,1 =g z     j,1    and Z j,2 =g z     j,2   . Then, generate NIZK proofs {right arrow over (π)} j , {right arrow over (π)} G     j   , {right arrow over (π)} Θ     j   , {{right arrow over (π)} Ψ     j,k   } k=1   3  for the following relations 
         [0000]        e ( F   j   ,F   j )= e ( g,F   j ) 
         [0000]        e ( G   j   ,g )= e ( g   1   ,F   j )· e ( g   0   ,F   j   −1   ·g )
 
         [0000]        e (Θ j   ,C   j,4 )= e ( C   j,1   ,g   2 )
 
         [0000]        e (Ψ j,1   g )= e ( X,Z   i,1 )
 
         [0000]        e (Ψ j,2   g )= e ( Y,Z   i,2 )
 
         [0000]        e (Ψ j,3   g )= e (Θ j   ,G   j )· e ( g,Z   i,1   ·Z   i,2 )
 
         [0098]    This is done by proving that 
         [0000]        e ( F   j   ,F   j )= e ( g,F   j ) 
         [0000]        e ( G   j   ,g )= e ( g   1   ,F   j )· e ( g   0   ,F   j   −1   ·g )
 
         [0000]        e (Θ j   ,C   j,4 )= e ( C   j,1 ,Γ 2 )
 
         [0000]        e (Ψ j,1 ,Γ)= e ( X,Z   i,1 )
 
         [0000]        e (Ψ j,2 ,Γ)= e ( Y,Z   i,2 )
 
         [0000]        e (Ψ j,3 ,Γ)= e (Θ j   ,G   j )· e (Γ, Z   i,1   ·Z   i,2 )
 
         [0099]    It should be noted that the first relation guarantees that id i [j] is indeed a bit. The first and sixth relations are quadratic equations and thus require 9 elements each whereas relations 2-5 only cost 12 group elements together. It should also be noted that the same variable θε           p  can be reused for each jε{1, . . . , l} so that the equalites of step 4 (which are guaranteed by {right arrow over (π)} Γ ) only need to be proved once. 
         [0100]    6. Generate a commitment {right arrow over (C)} Ω     1    to Ω 1  with a NIWI proof {right arrow over (π)} W ε           3  that variables (Ω 1 , H U ) satisfy the verification equation 
         [0000]        e ( g,g ) ω   ·e ( H   W ( M ),Ω 3 )= e (Ω 1   ,g )· e ( H   V ,Ω 2   −1 )
 
         [0000]    of the two-level Waters signature. 
         [0101]    7. Finally, use the one-time private key SK to generate a one-time signature σ ots  on the entire set of commitments and NIWI/NIZK proofs in order to achieve anonymity in the CCA2 sense. 
         [0102]    The whole signature a comprises 
         [0000]      σ=( VK,{right arrow over (C)}   H     V     ,{right arrow over (C)}   θ   ,{right arrow over (C)}   Γ   ,{right arrow over (C)}   Γ     2   ,{right arrow over (π)} H     U   ,{right arrow over (π)} W ,{right arrow over (π)} Γ 
 
         [0000]      {{right arrow over (C)} F     j   ,( C   j,1   ,C   j,2   C   j,4 Ψ j ), {right arrow over (C)}   G     j   ,{right arrow over (π)} G,j ,{right arrow over (π)} Θ     j     ,{right arrow over (C)}   Θ     j     ,{right arrow over (C)}   Z     j,1     ,{right arrow over (C)}   Z     j,2   ,{right arrow over (π)} j ,{{right arrow over (π)} Ψ     j,k   } k=1   3 } j=1   l   ,{right arrow over (C)}   Ω     1   ,Ω 2 ,Ω 3 ,σ ots )
 
         [0000]    Verify(gpk, M, σ): parse σ as indicated. Return 1 if and only if: (i) σ ots  is a valid one-time signature on the whole bundle; (ii) {Ψ j } j=1   l . are all valid ciphertexts for Kiltz&#39;s cryptosystem (i.e. by testing if e(Ψ j,4 ,X)=e(Ψ j,1 ,g VK ·U) and e(Ψ j,5 ,Y)=e(Ψ j,2 ,g VK ·V); (iii) For each jε{1, . . . , l}, (C j,1 ,C j,2 ) satisfies e(C j,1 ,H U (M))=e(g,C j,2 ); (iv) All proofs properly verify.
 
Trapgen(gpk, msk ADM , M): given the admitter&#39;s key msk ADM =(g 2   α     0   ,g 2   α     1   ) and a message Mε{0,1} L , compute and return
 
         [0000]        t   M =( t   0,1   ,t   0,2   ,t   1,1   ,t   1,2 )=( g   2   α     0     ·H   U ( M ) r     0     ,g   r     0     ,g   2   α     1     ·H   U ( M ) r     1     ,g   r     1   ) 
         [0000]    where 
         [0000]    
       
         
           
             
               r 
               0 
             
             , 
             
               
                 r 
                 1 
               
                
               
                 ← 
                 R 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    Open(gpk, M, σ, t M , ok): return ⊥ if σ is not a valid signature with regard to gpk and M. Otherwise, parse t M  as in described in Trapgen. For i=1 to l: 
         [0103]    1. Decrypt Ψ j =(Ψ j,1 ,Ψ j,2 ,Ψ j,3 ,Ψ j,4 ,Ψ j,5 ) using ok=(β x ,β y ,β u ,β v ) to obtain C j,3 ε         . 
         [0104]    2. Use t M  to determine the bit id[i]ε{0,1} for which the equalities C j,1 ,C j,2 ,C j,3 ,C j,4  (see Sign, step 3) are satisfied. 
         [0105]    Return the identifier id=id[1] . . . id[l]ε{0,1} l . 
         [0106]    Overall, each signature comprises 53l+35 group elements if the scheme is instantiated with Groth&#39;s one-time signature [see “Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures”]. 
         [0107]    From a security point of view, the traceability property of the scheme relies on the standard Computational Diffie-Hellman (CDH) assumption whereas the anonymity against the opening authority relies on the Decision 3-party Diffie-Hellman (C3DH) and the anonymity against the admitter relies on the Decision Linear Problem (DLIN) assumption. In the proof of anonymity against the admitter, it is also needed to assume that the one-time signature is strongly unforgeable (i.e. it should be unfeasible to publicly compute a new signature on a previously signed message). 
         [0108]      FIG. 1  illustrates a group signature system  100  according to a preferred embodiment of the present invention. For ease of illustration and comprehension, the connections between the devices in the system have been omitted. 
         [0109]    The system  100  comprises a signer  110  and a verifier  120 , each comprising at least one interface unit  111 ,  121  configured for communication with the other device, at least one processor (“processor”)  112 ,  122  and at least one memory  113 ,  123  configured for storing data, such as accumulators and intermediary calculation results. The system  100  further comprises an admitter  130  and an opening authority; although not illustrated for the sake of clarity, each of these devices comprises the necessary hardware such as processors and memory. 
         [0110]    The processor  112  of the signer  110  is configured to perform the Sign part of the present group signature scheme, and the processor  122  of the verifier  120  is adapted to verify a received group signature, i.e. perform Verify. The admitter  130  is configured to perform the TrapGen part. The opening authority  140  is configured to perform the Open part. A first non-transitory computer program product  114  such as a CD-ROM or a DVD comprises stored instructions that, when executed by the processor  112  of the sender  110 , performs the Sign parts according to the invention. A non-transitory second computer program product  124  comprises stored instructions that, when executed by the processor  122  of the receiver  120 , performs Verify according to the invention. 
       A Structure-Preserving IBE Scheme 
       [0111]    Setup(λ): Choose bilinear groups (         ,           T ) of prime order p&gt;2 λ . Then: 
         [0112]    1. Choose 
         [0000]    
       
         
           
             
               α 
               0 
             
             , 
             
               
                 α 
                 1 
               
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
             , 
             
               g 
                
               
                 ← 
                 R 
               
                
                
             
             , 
             
               
                 g 
                 2 
               
                
               
                 ← 
                 R 
               
                
                
             
           
         
       
     
         [0000]    and set g 0 =g α     0   ,g 1 =g α     1   . 
         [0113]    2. Choose 
         [0000]    
       
         
           
             
               u 
               0 
             
             , 
             
               u 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 u 
                 L 
               
                
               
                 ← 
                 R 
               
                
                
             
           
         
       
     
         [0000]    for some Lεpoly(λ). These are used to implement a number-theoretic hash function H         :{0,1} L →          that maps any L-bit string τ=τ[1] . . . τ[L]ε{0,1} L  to and H         (τ)=u 0 ·Π i=1   L u i   τ[i] . 
         [0114]    3. Choose group elements 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     Z 
                     1 
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     Z 
                      
                   
                 
                 ) 
               
                
               
                 ← 
                 R 
               
                
               
                  
                  
               
             
             , 
           
         
       
     
         [0000]    where l=2 log 2 (p)&gt;2λ. 
         [0115]    The master public key mpk is defined as 
         [0000]        mpk =((         ,           T ), P,g,g   0   =g   α     0     =g   α     1     ,g   2   ,{u   i } i=0   L   ,{Z   i } i=0   l ) 
         [0000]    and the master secret key msk is msk:=(g 2   α     0   ,g 2   α     1   ).
 
Keygen(msk, ID): given the master secret key msk=(g 2   α     0   ,g 2   α     1   ) and an identity IDε{0,1} L , compute and return
 
         [0000]        d   ID =( d   0,1   ,d   0,2   ,d   1,1   ,d   1,2 )=( g   2   α     0     ·H           ( ID ) r     0     ,g   r     0     ,g   2   α     1     ·H           ( ID ) r     1     ,g   r     1   ) 
         [0000]    where 
         [0000]    
       
         
           
             
               r 
               0 
             
             , 
             
               
                 r 
                 1 
               
                
               
                 ← 
                 R 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    Encrypt(mpk, ID, M): to encrypt a message Mε         : 
         [0116]    1. Choose 
         [0000]    
       
         
           
             
               K 
                
               
                 ← 
                 R 
               
                
               
                 
                   { 
                   
                     0 
                     , 
                     1 
                   
                   } 
                 
                  
               
             
             , 
           
         
       
     
         [0000]    where l=2 log 2 (p). 
         [0117]    2. Choose 
         [0000]    
       
         
           
             
               s 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 s 
                  
               
                
               
                 ← 
                 R 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               ω 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 ω 
                  
               
                
               
                 ← 
                 R 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0118]    3. Parse K as K[1], . . . K[l]ε{0,1} l . For i=1 to l, compute 
         [0000]        C   i,1   =g   s     i     ,C   1,2 =         ( ID ) s     i     ,C   i,3   =g   K[i]   s     i     /ω     i     ,C   i,4   =g   2   ω     i   . 
         [0119]    4. Compute C 0 =M·Π i=1   l Z i   K[i] . 
         [0000]    Return the ciphertext C=(C 0 ,{C i,1 ,C i,2 ,C i,3 ,C i,4 } i=1   l )ε           4l+1 .
 
Decrypt(mpk, d ID , C): parse the ciphertext C as C=(C 0 ,{C i,1 ,C i,2 ,C i,3 ,C i,4 } i=1   l ) and
       1. For i, =1 to l, compute μ b =e(C i,1 ,d b,1 )/e(C i,2 ,d b,2 ) for each bε{0,1}. If μ b =e(C i,3 ,C i,4 ) for some bε{0,1}, set K[i]=b. Otherwise, return ⊥.   2. Compute and return M=C 0 /(Π i=1   l Z i   K[i] ).       
 
         [0122]    Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features described as being implemented in hardware may also be implemented in software, and vice versa. Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.