Abstract:
Generation of linearly homomorphic structure-preserving signature σ on a vector (M 1 , . . . , M n )∈           n  by computing, in a processor, using a signing key sk={χ i , γ i , δ i } i=1   n , signature elements (z, r, u) by calculating 
     
       
         
           
             
               z 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     
                       - 
                       
                         χ 
                         i 
                       
                     
                      
                     
                         
                     
                   
                 
               
             
             , 
             
               r 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       γ 
                       i 
                     
                   
                 
               
             
             , 
             
               u 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       δ 
                       i 
                     
                   
                 
               
             
             , 
           
         
       
     
     and outputting the signature σ comprising the signature elements (z, r, u). The signature is verified by verifying, in a processor that (M 1 , . . . , M n )≠(         , . . . ,          ) and that (z, r, u) satisfy the equalities          =e(g z , z)·e(g r , r)·Π i=1   n e(g i , M i ),          =e(h z , z)·e(h, u)·Π i=1   n e (h i , M i ); and determining that the signature has been successfully verified in case the verifications are successful and that the signature has not been successfully verified otherwise. Also provided are a fully-fledged scheme and a context-hiding scheme.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates generally to cryptography, and in particular to linearly homomorphic structure-preserving 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. 
         [0003]    Linearly homomorphic signatures are well known in the art of cryptography. A definition is given in D. Boneh, D. Freeman, J. Katz, B. Waters. Signing a Linear Subspace: Signature Schemes for Network Coding. In  PKC&#39; 09 , Lecture Notes in Computer Science  5443, pp. 68-87, 2009. 
         [0004]    Other examples of linearly homomorphic signatures are available in:
   U.S. Pat. No. 7,743,253, issued Jun. 22, 2010; D.-X. Charles, K. Jain, K. Lauter. Digital signature for network coding.   D. Boneh, D. Freeman, J. Katz, B. Waters. Signing a Linear Subspace: Signature Schemes for Network Coding. In  PKC&#39; 09 , Lecture Notes in Computer Science , vol. 5443, pp. 68-87, 2009.   R. Gennaro, J. Katz, H. Krawczyk, T. Rabin. Secure Network Coding over the Integers. In  PKC&#39; 10 , Lecture Notes in Computer Science , vol. 6056, pp. 142-160, 2010.   N. Attrapadung, B. Libert. Homomorphic Network Coding Signatures in the Standard Model. In  PKC&#39; 11 , Lecture Notes in Computer Science , vol. 6571, pp. 17-34, 2011.   D. Boneh, D. Freeman. Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures. In  PKC&#39; 11 , Lecture Notes in Computer Science , vol. 6571, pp. 1-16, 2011.   D. Boneh, D. Freeman. Homomorphic Signatures for Polynomial Functions. In  Eurocrypt&#39; 11 , Lecture Notes in Computer Science , vol. 6632, pp. 149-168, 2011.   D. Freeman. Improved security for linearly homomorphic signatures: A generic framework. In  PKC&#39; 12 , Lecture Notes in Computer Science , vol. 7293, pp. 697-714, 2012.   D. Catalano, D. Fiore, B. Warinschi. Adaptive Pseudo-free Groups and Applications. In  Eurocrypt&#39; 11 , Lecture Notes in Computer Science , vol. 6632, pp. 207-223, 2011.   D. Catalano, D. Fiore, B. Warinschi. Efficient Network Coding Signatures in the Standard Model. In  PKC&#39; 12 , Lecture Notes in Computer Science , vol. 7293, pp. 680-696, 2012.   
 
         [0014]    It would appear that among the schemes proven secure in the standard model under standard assumptions the most efficient scheme is the one in N. Attrapadung, B. Libert, T. Peters. Computing on Authenticated Data: New Privacy Definitions and Constructions. In  Asiacrypt&#39; 12, LNCS 7658, pp. 367-385, 2012. 
         [0015]    The construction is homomorphic over the additive group (           p , +). Namely, the underlying cyclic group is          =           p  and messages being signed consist of a file identifier τ∈{0,1} L  and a vector of            p   n . The scheme makes use of a bilinear map e:          ×         →           T  defined between groups (           T ) of prime order p. 
         [0000]    Keygen(λ, n): given a security parameter λ∈          and an integer n∈poly(λ) denoting the dimension of vectors to be signed, choose bilinear groups (           T ) of prime order p&gt;2 λ . Choose 
         [0000]    
       
         
           
             
               α 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
             , 
             
               
                 g 
                 ^ 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                 ^ 
               
             
             , 
             
               v 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 
                   u 
                   0 
                 
               
             
             , 
             
               u 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 u 
                 L 
               
               ← 
                
             
           
         
       
     
         [0000]    for some L∈poly(λ). These elements (u 0 , u 1 , . . . , u L )∈           L+1  will be used to implement a number theoretic hash function          : {0,1} L →          such that any L-bit string m=m[1] . . . m[L]∈{0,1} L  has a hash value          (m)=u 0 ·Π i=1   L u i   m[i] . Pick 
         [0000]    
       
         
           
             
               g 
               i 
             
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
              
           
         
       
     
         [0000]    for i=1 to n. Finally, define the identifier space          :={0,1} L . The private key is sk:=α and the public key consists of 
         [0000]        pk: =((         ,           T ), ĝ,ĝ   α   ,v,{g   i } i=1   n   ,{u   i } i=0   L ). 
         [0000]    Sign(sk, τ, {right arrow over (v)})): given a vector {right arrow over (v)}=(v 1 , . . . v n )∈           p   n , a file identifier τ:={0,1} L  and the private key sk=α∈           p , choose 
         [0000]    
       
         
           
             r 
             , 
             
               s 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    Then, compute a signature σ=(σ 1 , σ 2 , s)∈         ×         ×           p  as 
         [0000]    
       
         
           
             
               
                 σ 
                 1 
               
               = 
               
                 
                   
                     ( 
                     
                       
                         g 
                         1 
                         
                           v 
                           1 
                         
                       
                        
                       … 
                        
                       
                           
                       
                        
                       
                         
                           g 
                           n 
                           
                             v 
                             n 
                           
                         
                         · 
                         
                           v 
                           s 
                         
                       
                     
                     ) 
                   
                   α 
                 
                 · 
                 
                   
                     
                       H 
                        
                     
                      
                     
                       ( 
                       τ 
                       ) 
                     
                   
                   r 
                 
               
             
             , 
             
               
                 σ 
                 2 
               
               = 
               
                 
                   
                     g 
                     ^ 
                   
                   r 
                 
                 . 
               
             
           
         
       
     
       SignDerive 
       [0016]    
       
         
           
             
               ( 
               
                 pk 
                 , 
                 τ 
                 , 
                 
                   
                     { 
                     
                       ( 
                       
                         
                           β 
                           i 
                         
                         , 
                         
                           σ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       ) 
                     
                     } 
                   
                   
                     i 
                     = 
                     1 
                   
                    
                 
               
               ) 
             
              
             
               : 
             
           
         
       
     
         [0000]    given pk, a file identifier τ and l tuples (β i , σ (i) ), parse each σ (i)  as σ (i)  (σ i,1 , σ i,2 , s i ) for          =1 to l. Choose 
         [0000]    
       
         
           
             
               r 
               ~ 
             
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               
                 ℤ 
                 p 
               
               . 
             
           
         
       
     
         [0000]    Then, compute and output (σ 1 , σ 2 , s), where 
         [0000]    
       
         
           
             
               σ 
               1 
             
             = 
             
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                    
                 
                  
                 
                     
                 
                  
                 
                   
                     
                       σ 
                       
                         i 
                         , 
                         1 
                       
                       
                         β 
                         i 
                       
                     
                     · 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       
                         r 
                         ~ 
                       
                     
                   
                    
                   
                       
                   
                    
                   
                     σ 
                     2 
                   
                 
               
               = 
               
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         σ 
                         
                           i 
                           , 
                           2 
                         
                         
                           β 
                           i 
                         
                       
                       · 
                       
                         
                           g 
                           ^ 
                         
                         
                           r 
                           ~ 
                         
                       
                     
                      
                     
                         
                     
                      
                     s 
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                     
                       β 
                       i 
                     
                     · 
                     
                       s 
                       i 
                     
                   
                 
               
             
           
         
       
     
         [0000]    Verify(pk, τ, {right arrow over (γ)}, σ): given pk, a signature σ=(σ 1 , σ 2 , s) and a message (τ, {right arrow over (γ)}), where τ∈{0,1} L  and {right arrow over (γ)}=(γ 1 , . . . , γ n )∈(           p ) n , return ⊥ if {right arrow over (γ)}={right arrow over (0)}. Otherwise, return 1 if and only if 
         [0000]        e (σ 1   ,ĝ )= e ( g   1   γ     1      . . . g   n   γ     n·v     s   ,ĝ   α )· e (         (τ),σ 2 ).
 
         [0017]    It will be appreciated that in the construction, signatures on the all-zero vector {right arrow over (0)} are not allowed. This is not a restriction since, in all applications of linearly homomorphic signatures, a unit vector (0, . . . , 1, . . . , 0) of appropriate length is appended to signed vectors. 
         [0018]    In the paper by Attrapadung et al., the above scheme was proved unforgeable under a variant of the Diffie-Hellman assumption. This assumption posits that, given (g, ĝ, g a , ĝ b )∈(         ×         ) 2 , for randomly chosen a, b∈           p  and where (         ,          ) are cyclic bilinear group of order p, no Probabilistic Polynomial Time (PPT) algorithm can compute g ab . In the version hereinbefore, the scheme is not completely context hiding (i.e., derived signatures are not statistically independent of original ones). Attrapadung et al. has shown how to modify the scheme so as to make it completely context hiding at the cost of increasing the signature length [see N. Attrapadung, B. Libert, T. Peters. Efficient Completely Context-Hiding Quotable Signatures and Linearly Homomorphic Signatures. In  PKC&#39; 13, LNCS 7778, pp. 386-404, 2013]. 
         [0019]    The linearly homomorphic signatures in the prior art only exist for vector spaces where each vector&#39;s coordinates belong to a group, like (           p , +), where it is easy to compute discrete logarithms. It will thus be appreciated that it is desired to have a scheme that can handle vectors {right arrow over (M)} 1 ∈           n  whose coordinates live in a discrete-logarithm-hard group           of finite order p. One major difficulty is that, in such groups, it is usually difficult to decide whether a plurality of vectors {right arrow over (M)} 1 , . . . , {right arrow over (M)} n−1 ∈           n  are linearly dependent. In general, for n&gt;2, the only known method to do this is to compute the discrete logarithms of all coordinates in            p . 
         [0020]    It will thus be appreciated that it is desired to have a linearly homomorphic signature scheme where messages can be elements with a special algebraic structure, i.e. a “structure-preserving” signature scheme. The present invention provides such a scheme. 
       SUMMARY OF INVENTION 
       [0021]    In a first aspect, the invention is directed to a method for generating a linearly homomorphic signature σ on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group. A processor of a device computes, using a signing key sk={χ i , γ i , δ i } i=1   n , signature elements (z, r, u) by calculating z=Π i=1   n M i   −χ     i   , r=Π i=1   n M i   −γ     i   , 
         [0000]    
       
         
           
             
               u 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       δ 
                       i 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    and outputs the signature σ comprising the signature elements (z, r, u). 
         [0022]    In a preferred embodiment, the signing key further comprises an element 
         [0000]    
       
         
           
             
               h 
               z 
               
                 α 
                 r 
               
             
             , 
           
         
       
     
         [0000]    the processor further chooses random elements θ, 
         [0000]    
       
         
           
             
               ρ 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
             ; 
           
         
       
     
         [0000]    calculates a further signature element v=h ρ , wherein h is an element of a second group; wherein the calculation of z further comprises a multiplication by g r   θ , the calculation of r further comprises a multiplication by g z   −θ  and the calculation of u further comprises a multiplication by 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   h 
                   z 
                   
                     α 
                     r 
                   
                 
                 ) 
               
               
                 - 
                 θ 
               
             
             , 
           
         
       
     
         [0000]    wherein α r  is an integer and h, g r  and g z  are elements of the second group; wherein the signature further comprises the signature element v; and wherein the first group and the second group are the same. 
         [0023]    In a second aspect, the invention is directed to a method of verifying a linearly homomorphic signature σ comprising signature elements (z, r, u) on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group. A processor of a device verifies that (M 1 , . . . , M n )≠(         , . . . ,          ) and that (z, r, u) satisfy a first equality          =e(g z , z)·e(g r , r)·Π i=1   n e(g i , M i ) and a second equality          =e(h z , z)·e(h, u)·Π i=1   n e(h i , M i ), wherein e(·, ·) denotes a symmetric and commutative pairing and wherein h, h z , h i , g r , g i  and g z  are elements of a second group; and determines that the signature has been successfully verified in case the verifications are successful and that the signature has not been successfully verified otherwise. 
         [0024]    In a first embodiment, the second equality further comprises a term e(         (τ), v), wherein          (τ) denotes a hash function and τ denotes an identifier of a subspace in which the signed vectors live. 
         [0025]    In a third aspect, the invention is directed to a device for generating a linearly homomorphic signature σ on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group. The device comprises a processor configured to: compute, using a signing key sk={χ i , γ i , δ i } i=1   n , signature elements (z, r, u) by calculating z=Π i=1   n M i   −χ     i   , r=Π i=1   n M i   −γ     i   , 
         [0000]    
       
         
           
             
               u 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       δ 
                       i 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    and output the signature σ comprising the signature elements (z, r, u). 
         [0026]    In a first embodiment, the signing key further comprises an element 
         [0000]    
       
         
           
             
               h 
               z 
               
                 α 
                 r 
               
             
             , 
           
         
       
     
         [0000]    the processor is further configured to: choose random elements θ, 
         [0000]    
       
         
           
             
               ρ 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
             ; 
           
         
       
     
         [0000]    and calculate a further signature element v=h ρ , wherein h is an element of a second group; wherein the calculation of z further comprises a multiplication by g r   θ , the calculation of r further comprises a multiplication by g z   −θ  and the calculation of u further comprises a multiplication by 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   h 
                   z 
                   
                     α 
                     r 
                   
                 
                 ) 
               
               
                 - 
                 θ 
               
             
             , 
           
         
       
     
         [0000]    wherein α r  is an integer and h, g r  and g z  are elements of the second group; wherein the signature further comprises the signature element v; and wherein the first group and the second group are the same. 
         [0027]    In a fourth aspect, the invention is directed to a device for verifying a linearly homomorphic signature σ comprising signature elements (z, r, u) on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group. The device comprises a processor configured to: verify that (M 1 , . . . , M n )≠(         , . . . ,          ), and that (z, r, u) satisfy a first equality          =e(g z , z)·e(g r , r)·Π i=1   n e(g i , M i ) and a second equality          =e(h z , z)·e(h, u)·Π i=1   n e(h i , M i ), wherein e(·, ·) denotes a symmetric and commutative pairing and wherein h, h z , h i , g r , g i  and g z  are elements of a second group; and determine that the signature has been successfully verified in case the verifications are successful and that the signature has not been successfully verified otherwise. 
         [0028]    In a first embodiment, the second equality further comprises a term e(         (τ), v), wherein          (τ) denotes a hash function and τ denotes an identifier of a subspace in which the signed vectors live. 
         [0029]    In a fifth aspect, the invention is directed to a device for generating a linearly homomorphic signature σ on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group. The device comprises a processor configured to: compute, using a signing key 
         [0000]    
       
         
           
             sk 
             = 
             
               
                 { 
                 
                   
                     h 
                     z 
                     
                       α 
                       r 
                     
                   
                   , 
                   
                     χ 
                     i 
                   
                   , 
                   
                     γ 
                     i 
                   
                   , 
                   
                     δ 
                     i 
                   
                 
                 } 
               
               
                 i 
                 = 
                 1 
               
               n 
             
           
         
       
     
         [0000]    wherein h z  is a member of a second group and α r  is an integer, signature elements (z, r, u, v) by calculating 
         [0000]    
       
         
           
             
               z 
               = 
               
                 
                   g 
                   r 
                   θ 
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         χ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               r 
               = 
               
                 
                   g 
                   z 
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         γ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               u 
               = 
               
                 
                   
                     ( 
                     
                       h 
                       z 
                       
                         α 
                         r 
                       
                     
                     ) 
                   
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         δ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               v 
               = 
               
                 h 
                 ρ 
               
             
             , 
           
         
       
     
         [0000]    wherein          (τ) denotes a hash function and τ denotes an identifier of a subspace in which the signed vectors live; generate commitments to z, r and u respectively; generate, using the commitments to z, r and u, proofs that z, r and u satisfy predetermined verification algorithms; and output the signature σ comprising the signature element v the commitments to z, r and u, and the proofs. 
         [0030]    In a sixth aspect, the invention is directed to a device for verifying a linearly homomorphic signature σ on a vector (M 1 , . . . , M n )∈           n , wherein           denotes a first group, the linearly homomorphic signature σ comprising a first signature element v, commitments {right arrow over (C)} z , {right arrow over (C)} r , {right arrow over (C)} u  to further signature elements z, r and u respectively, the commitments having been generated using vectors {right arrow over (f)} 1 , {right arrow over (f)} 2 , {right arrow over (f)} 3 , and proofs {right arrow over (π)} 1 , {right arrow over (π)} 2  that z, r and u satisfy predetermined verification algorithms. The device comprises a processor configured to: verify that (M 1 , . . . , M n )≠(         , . . . ,          ) and that the verifications 
         [0000]    
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   E 
                    
                   
                     ( 
                     
                       
                         g 
                         i 
                       
                       , 
                       
                         ( 
                         
                           
                             1 
                              
                           
                           , 
                           
                             1 
                              
                           
                           , 
                           
                             M 
                             i 
                           
                         
                         ) 
                       
                     
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
             
             = 
             
               
                 
                   E 
                    
                   
                     ( 
                     
                       
                         g 
                         z 
                       
                       , 
                       
                         
                           C 
                           → 
                         
                         z 
                       
                     
                     ) 
                   
                 
                 · 
                 
                   ( 
                   
                     
                       g 
                       r 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       r 
                     
                   
                   ) 
                 
                 · 
                 
                   E 
                    
                   
                     ( 
                     
                       
                         π 
                         
                           1 
                           , 
                           1 
                         
                       
                       , 
                       
                         
                           f 
                           → 
                         
                         1 
                       
                     
                     ) 
                   
                 
                 · 
                 
                   E 
                    
                   
                     ( 
                     
                       
                         π 
                         
                           1 
                           , 
                           2 
                         
                       
                       , 
                       
                         
                           f 
                           → 
                         
                         2 
                       
                     
                     ) 
                   
                 
                 · 
                 
                   E 
                    
                   
                     ( 
                     
                       
                         π 
                         
                           1 
                           , 
                           3 
                         
                       
                       , 
                       
                         
                           f 
                           → 
                         
                         3 
                       
                     
                     ) 
                   
                 
               
                
               
                   
               
                
               and 
             
           
         
       
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           h 
                           i 
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             
                               M 
                               i 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
                 · 
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           
                             H 
                              
                           
                            
                           
                             ( 
                             τ 
                             ) 
                           
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             v 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
               
             
             = 
             
               
                 E 
                  
                 
                   ( 
                   
                     
                       h 
                       z 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       z 
                     
                   
                   ) 
                 
               
               · 
               
                 
                   E 
                    
                   
                     ( 
                     
                       h 
                       , 
                       
                         
                           C 
                           → 
                         
                         u 
                       
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    E(π 2,1 , {right arrow over (f)} 1 )·E(π 2,2 , {right arrow over (f)} 2 )·E(π 2,3 , {right arrow over (f)} 3 ), wherein E(·, ·) denotes a coordinate-wise pairing and wherein h, h z , h i , g r , g i  and g z  are elements of a second group; and determine that the signature has been successfully verified in case the verifications are successful and that the signature has not been successfully verified otherwise. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0031]    Preferred features of the present invention will now be described, by way of non-limiting example, with reference to the accompanying drawings, in which: 
           [0032]      FIG. 1  illustrates a structure-preserving linearly homomorphic signature system according to a preferred embodiment of the invention; and 
           [0033]      FIG. 2  illustrates a method for generating and verifying context-hiding linearly homomorphic structure-preserving signatures according to a preferred embodiment of the invention. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0034]    The structure-preserving linearly homomorphic signature scheme of the present invention is based on a modification of a structure-preserving signature scheme proposed in M. Abe, K. Haralambiev, M. Ohkubo. Signing on Elements in Bilinear Groups for Modular Protocol Design. Cryptology ePrint Archive: Report 2010/133, 2010 and in M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo. Structure-Preserving Signatures and Commitments to Group Elements. In  Crypto&#39; 10 , Lecture Notes in Computer Science , vol. 6223, pp. 209-236, 2010 [see Appendix C of the first document for a description]. It will be appreciated that the scheme neither is nor was meant to be homomorphic and it only allows signing one message with respect to given public key. 
         [0035]    A first modification is thus made so as to obtain a linearly homomorphic signature scheme over a discrete-logarithm-hard group as long as only one linear subspace (spanned by n−1 linearly independent vectors of            n ) is signed using a given key pair (sk; pk). This first scheme can be described as follows. In the following notations, pp denotes a set of public parameters consisting of groups (           T ) of prime order p&gt;2 λ , where λ∈          is the security parameter, over which an efficiently computable bilinear map e:          ×         →           T  is defined. 
         [0036]      FIG. 1  illustrates a cryptographic signing device  100  for generating homomorphic signatures and a cryptographic signing device  200  for verification of homomorphic signatures according to a preferred embodiment of the invention. The devices  100 ,  200  each comprise at least one interface unit  110 ,  210  configured for communication, at least one processor (“processor”)  120 ,  220  and at least one memory  130 ,  230  configured for storing data, such as accumulators and intermediary calculation results. The Figure also shows a first and a second computer program product (non-transitory storage medium)  140 ,  240  such as a CD-ROM or a DVD comprises stored instructions that, when executed by the processor  120 ,  220 , respectively generate and verify a signature according to the present invention. 
       One-Time Scheme: 
       [0037]    Keygen(pp, n): given pp and the dimension n∈          of the subspace to be signed, choose generators 
         [0000]    
       
         
           
             h 
             , 
             
               g 
               z 
             
             , 
             
               g 
               r 
             
             , 
             
               
                 z 
                 z 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                 . 
               
             
           
         
       
     
       Pick 
       [0038]    
       
         
           
             
               χ 
               i 
             
             , 
             
               γ 
               i 
             
             , 
             
               
                 δ 
                 i 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
     
         [0000]    for          =1 to n. Then, for each          ∈{1, . . . , n}, compute g i =g z   χ     i   g r   γ     i   , h i =h z   χ     i   h δ     i   . The public key is defined as 
         [0000]        pk =( g   z   ,h   r   ,h   z   ,h,{g   i   ,h   i } i=1   n )∈           2n+4  
 
         [0000]    and the private key as sk={χ i , γ i , δ i } i=1   n .
 
Sign(sk, τ, (M 1 , . . . , M n )): to sign a vector (M 1 , . . . , M n )∈           n  associated with the identifier τ=∈ using sk={χ i , γ i , δ i } i=1   n , compute
 
         [0000]    
       
         
           
             
               z 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       χ 
                       i 
                     
                   
                 
               
             
             , 
             
               r 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       γ 
                       i 
                     
                   
                 
               
             
             , 
             
               u 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   M 
                   i 
                   
                     - 
                     
                       δ 
                       i 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0039]    The signature comprises σ=(z, r, u)∈{circumflex over (         )} 3 . 
       SignDerive 
       [0040]    
       
         
           
             
               ( 
               
                 pk 
                 , 
                 τ 
                 , 
                 
                   
                     { 
                     
                       ( 
                       
                         
                           ω 
                           i 
                         
                         , 
                         
                           σ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       ) 
                     
                     } 
                   
                   
                     i 
                     = 
                     1 
                   
                    
                 
               
               ) 
             
              
             
               : 
             
           
         
       
     
         [0000]    given pk, a file identifier τ and l tuples (ω i , σ (i) ), parse each signature σ (i)  as σ (i) =(z i , r i , u i )∈{circumflex over (         )} 3  for          =1 to l. Compute 
         [0000]    
       
         
           
             z 
             = 
             
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                    
                 
                  
                 
                     
                 
                  
                 
                   
                     z 
                     i 
                     
                       ω 
                       i 
                     
                   
                    
                   
                       
                   
                    
                   r 
                 
               
               = 
               
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       r 
                       i 
                       
                         ω 
                         i 
                       
                     
                      
                     
                         
                     
                      
                     u 
                   
                 
                 = 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     u 
                     i 
                     
                       ω 
                       i 
                     
                   
                 
               
             
           
         
       
     
         [0000]    and return σ=(z, r, u).
 
Verify(pk, σ, τ, (M 1 , . . . , M n )): given a signature σ=(z, r, u)∈{circumflex over (         )} 3 , a vector (M 1 , . . . , M n ) and a file identifier τ=∈, return 1 if and only if (M 1 , . . . , M n )≠(         , . . . ,          ) and (z, r, u) satisfy the equalities
 
         [0000]                = e ( g   z   ,z )· e ( g   r   ,r )·Π i=1   n   e ( g   i   ,M   i ),          = e ( h   z   ,z )· e ( h,u )·Π i=1   n   e ( h   i   ,M   i ).
 
         [0041]    It can be proved that an adversary obtaining signatures on at most n−1 linearly independent vectors {right arrow over (M)} 1 , . . . , {right arrow over (M)} n−1  is unable to forge a signature on a vector {right arrow over (M)}∉ span({right arrow over (M)} 1 , . . . , {right arrow over (M)} n−1 ) as long as the Simultaneous Double Pairing (SDP) assumption holds. The SDP assumption, described in the paper by Abe, Haralambiev and Ohkubo, is to, in (         ), given a tuple of elements (g z , g r , h z , h u )∈           4 , find a non-trivial tuple (z, r, u)∈{circumflex over (         )} 3 \{(         )} such that e(g z ·z)·e(g r ·r)=          and e(h z ·z)·e(h u ·u)=         . 
       Full-Fledged Scheme: 
       [0042]    The one-time scheme can be upgraded to a linear construction allowing to sign an arbitrary number of linear subspaces. To do this, a configuration of bilinear groups (         ) for which          ={circumflex over (         )} is needed. In other words, the bilinear map e:          ×         →           T  must have both of its arguments in the same group           because it should be symmetric and commutative. 
         [0043]    In the construction, each file identifier T consists of a L-bit string, for some L∈poly(λ). The u component of each signature can be seen as an aggregation of the signature of the one-time scheme with a Waters signature (h z   α     r   ·         (τ) −ρ , h ρ ) on the file identifier τ [see B. Waters. Efficient Identity-Based Encryption Without Random Oracles. In  Eurocrypt&#39; 05 , Lecture Notes in Computer Science , vol. 3494, pp. 114-127, 2005]. In the present scheme, such a Waters signature is used as a support for a signature randomizer θ∈           p . 
         [0000]    Keygen(pp, n): given pp and the dimension n∈          of the subspace to be signed, perform the following steps:
       1. Choose       
 
         [0000]    
       
         
           
             
               h 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 
                   α 
                   z 
                 
               
             
             , 
             
               α 
               r 
             
             , 
             
               
                 β 
                 z 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    Define g z =h α     z   , g r =h α     r    and h z =h β     z.    
       2. For          =1 to n, pick       
 
         [0000]    
       
         
           
             
               χ 
               i 
             
             , 
             
               γ 
               i 
             
             , 
             
               
                 δ 
                 i 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
     
         [0000]    and compute g i =g z   χ     i   g r   γ     i   , h i =h z   χ     i   h δ     i.    
       3. Choose a random vector       
 
         [0000]    
       
         
           
             
               w 
               _ 
             
             = 
             
               
                 ( 
                 
                   
                     w 
                     0 
                   
                   , 
                   
                     w 
                     1 
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     w 
                     L 
                   
                 
                 ) 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                 
                   L 
                   + 
                   1 
                 
               
             
           
         
       
     
         [0000]    that defines a hash function          : {0,1} L →          which maps τ=τ[1] . . . τ[L]∈{0,1} L  to          (τ)=w 0 ·Π k=1   L w k   τ[k] . 
         [0047]    The public key consists of 
         [0000]        pk =( g   z   ,g   r   ,h   z   ,h,{g   i   ,h   i } i=1   n   ,  w   )∈           2n+4 ×           L+1  
 
         [0000]    while the private key is 
         [0000]    
       
         
           
             sk 
             = 
             
               
                 ( 
                 
                   
                     h 
                     z 
                     
                       α 
                       r 
                     
                   
                   , 
                   
                     
                       { 
                       
                         
                           χ 
                           i 
                         
                         , 
                         
                           γ 
                           i 
                         
                         , 
                         
                           δ 
                           i 
                         
                       
                       } 
                     
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                 
                 ) 
               
               . 
             
           
         
       
     
         [0000]    Sign(sk, τ, (M 1 , . . . , M n )): to sign a vector (M 1 , . . . , M n )∈           n  with regard to the file identifier τ using 
         [0000]    
       
         
           
             
               sk 
               = 
               
                 ( 
                 
                   
                     h 
                     z 
                     
                       α 
                       r 
                     
                   
                   , 
                   
                     
                       { 
                       
                         
                           χ 
                           i 
                         
                         , 
                         
                           γ 
                           i 
                         
                         , 
                         
                           δ 
                           i 
                         
                       
                       } 
                     
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    choose θ, 
         [0000]    
       
         
           
             ρ 
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               ℤ 
               p 
             
           
         
       
     
         [0000]    and compute 
         [0000]    
       
         
           
             
               z 
               = 
               
                 
                   g 
                   r 
                   θ 
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         χ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               r 
               = 
               
                 
                   g 
                   z 
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         γ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               u 
               = 
               
                 
                   
                     ( 
                     
                       h 
                       z 
                       
                         α 
                         r 
                       
                     
                     ) 
                   
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       M 
                       i 
                       
                         - 
                         
                           δ 
                           i 
                         
                       
                     
                     · 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       
                         - 
                         ρ 
                       
                     
                   
                 
               
             
             , 
             
               v 
               = 
               
                 h 
                 ρ 
               
             
             , 
           
         
       
     
         [0048]    The signature comprises σ=(z, r, u, v)∈           4 . 
       SignDerive 
       [0049]    
       
         
           
             
               ( 
               
                 pk 
                 , 
                 τ 
                 , 
                 
                   
                     { 
                     
                       ( 
                       
                         
                           ω 
                           i 
                         
                         , 
                         
                           σ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       ) 
                     
                     } 
                   
                   
                     i 
                     = 
                     1 
                   
                    
                 
               
               ) 
             
              
             
               : 
             
           
         
       
     
         [0000]    given pk, a file identifier τ and l tuples (ω i , σ (i) ), parse each signature σ (i)  as σ (i) =(z i , r i , u i , v i )∈           4  for          =1 to l. Then choose 
         [0000]    
       
         
           
             
               ρ 
               ′ 
             
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               ℤ 
               p 
             
           
         
       
     
         [0000]    and compute 
         [0000]    
       
         
           
             z 
             = 
             
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                    
                 
                  
                 
                     
                 
                  
                 
                   
                     z 
                     i 
                     
                       ω 
                       i 
                     
                   
                    
                   
                       
                   
                    
                   r 
                 
               
               = 
               
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       r 
                       i 
                       
                         ω 
                         i 
                       
                     
                      
                     
                         
                     
                      
                     u 
                   
                 
                 = 
                 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                        
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           u 
                           i 
                           
                             ω 
                             i 
                           
                         
                         · 
                         
                           
                             
                               H 
                                
                             
                              
                             
                               ( 
                               τ 
                               ) 
                             
                           
                           
                             - 
                             
                               ρ 
                               ′ 
                             
                           
                         
                       
                        
                       
                           
                       
                        
                       v 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                        
                     
                      
                     
                         
                     
                      
                     
                       
                         v 
                         i 
                         
                           ω 
                           i 
                         
                       
                       · 
                       
                         h 
                         
                           ρ 
                           ′ 
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    and return σ=(z, r, u, v).
 
Verify(pk, σ, τ, (M 1 , . . . , M n )): given a signature σ=(z, r, u, v)∈           4 , a file identifier τ and a vector (M 1 , . . . , M n ), return 1 if and only if (M 1 , . . . , M n )≠(         , . . . ,          ) and (z, r, u, v) satisfy the equalities
 
         [0000]    
       
         
           
             
               
                 1 
                 
                    
                   T 
                 
               
               = 
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         g 
                         z 
                       
                       , 
                       z 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       
                         g 
                         r 
                       
                       , 
                       r 
                     
                     ) 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     e 
                      
                     
                       ( 
                       
                         
                           g 
                           i 
                         
                         , 
                         
                           M 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 1 
                 
                    
                   T 
                 
               
               = 
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         h 
                         z 
                       
                       , 
                       z 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       h 
                       , 
                       u 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       , 
                       v 
                     
                     ) 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       e 
                        
                       
                         ( 
                         
                           
                             h 
                             i 
                           
                           , 
                           
                             M 
                             i 
                           
                         
                         ) 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0050]    It will be appreciated that the one-time scheme is a special case of the full-fledged scheme where 0=p=0 in each signature. 
       Context-Hiding Scheme: 
       [0051]    It will be appreciated that the full-fledged scheme does not provide complete context-hiding security because the signature derivation operation cannot re-randomize the underlying θ without knowing the private key. In some applications it may be desirable to make sure that derived signatures and original ones are unlinkable, even in the view of a computationally unbounded observer. 
         [0052]    For this reason, the preferred embodiment is a scheme that can be proved completely context-hiding. This scheme is obtained by modifying the full-fledged scheme. Essentially, the signer first computes a signature σ=(z, r, u, v) as in the full-fledged scheme. Since elements (z, r, u) cannot be publicly re-randomized, the signer only lets them appear within Groth-Sahai commitments [see J. Groth, A. Sahai. Efficient non-interactive proof systems for bilinear groups. In  Eurocrypt&#39; 08 , Lecture Notes in Computer Science , vol. 4965, pp. 415-432, 2008.] and adds a non-interactive proof that committed values satisfy the verification equations. The perfect randomizability properties (shown in M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, H. Shacham. Randomizable Proofs and Delegatable Anonymous Credentials. In  Crypto&#39; 09 , Lecture Notes in Computer Science , vol. 5677, pp. 108-125, 2009.) of Groth-Sahai proofs guarantee that derived signatures will be distributed as freshly generated signatures. 
         [0053]    In the following description, it is again required that the bilinear map e:          ×         &gt;           T  is symmetric (i.e.          =         ). In the following notations, a coordinate-wise pairing E:          ×           3 →           T   3  is defined such that, for any element h∈          and any vector {right arrow over (g)}=(g 1 , g 2 , g 3 ), E(h, {right arrow over (g)})=(e(h, g 1 ), e(h, g 2 ), e(h, g 3 )). 
         [0054]      FIG. 2  illustrates Sign, SignDerive and Verify of the following scheme. 
         [0000]    Keygen(pp, n): given pp and the dimension n∈          of the subspace to be signed, perform the following steps:
       1. Choose       
 
         [0000]    
       
         
           
             
               h 
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                  
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 
                   α 
                   z 
                 
               
             
             , 
             
               a 
               r 
             
             , 
             
               
                 β 
                 z 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 
                   ℤ 
                   p 
                 
                 . 
               
             
           
         
       
     
         [0000]    Define g z =h α     z   , g r =h α     r    and h z =h β     z.    
       2. For each          ∈{1, . . . n}, pick       
 
         [0000]    
       
         
           
             
               χ 
               i 
             
             , 
             
               γ 
               i 
             
             , 
             
               
                 δ 
                 i 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
               
                 ℤ 
                 p 
               
             
           
         
       
     
         [0000]    and compute g i =g z   χ     i   g r   γ     i   , h i =h z   χ     i   h δ     i.    
       3. Choose a Groth-Sahai common reference string by choosing       
 
         [0000]    
       
         
           
             
               f 
               1 
             
             , 
             
               
                 f 
                 2 
               
                
               
                 ← 
                 
                   
                       
                   
                    
                   R 
                    
                   
                       
                   
                 
               
                
                
             
           
         
       
     
         [0000]    and defining vectors {right arrow over (f 1 )}=(f 1 , 1, g)∈           3 , {right arrow over (f 2 )}=(1, f 2 , g)∈           3  and 
         [0000]    
       
         
           
             
               
                 f 
                 → 
               
               3 
             
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               
                  
                 3 
               
               . 
             
           
         
       
     
         [0000]    The public key consists of 
         [0000]        pk =( g   z   ,g   r   ,h   z   ,h,{g   i   ,h   i } i=1   n   ,f =({right arrow over ( f   1 )}, {right arrow over ( f   2 )}, {right arrow over ( f   3 )})) 
         [0000]    while the private key is sk=(h z   α     r, {χ     i , γ i , δ i } i=1   n ).
 
Sign(sk, τ, (M 1 , . . . , M n )): to sign a vector (M 1 , . . . , M n )∈           n  with regard to the file identifier τ using
 
         [0000]    
       
         
           
             
               sk 
               = 
               
                 ( 
                 
                   
                     h 
                     z 
                     
                       α 
                       r 
                     
                   
                   , 
                   
                     
                       { 
                       
                         
                           χ 
                           i 
                         
                         , 
                         
                           γ 
                           i 
                         
                         , 
                         
                           δ 
                           i 
                         
                       
                       } 
                     
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    perform:
       1. Choose S1 θ,       
 
         [0000]    
       
         
           
             ρ 
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               ℤ 
               p 
             
           
         
       
     
         [0000]    and compute 
         [0000]    
       
         
           
             
               z 
               = 
               
                 
                   g 
                   r 
                   θ 
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         χ 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               r 
               = 
               
                 
                   g 
                   z 
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     M 
                     i 
                     
                       - 
                       
                         γ 
                         i 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               u 
               = 
               
                 
                   
                     ( 
                     
                       h 
                       z 
                       
                         α 
                         r 
                       
                     
                     ) 
                   
                   
                     - 
                     θ 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       M 
                       i 
                       
                         - 
                         
                           δ 
                           i 
                         
                       
                     
                     · 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       
                         - 
                         ρ 
                       
                     
                   
                 
               
             
             , 
             
               v 
               = 
               
                 h 
                 ρ 
               
             
           
         
       
       
         
           
             2. Using the vectors f=({right arrow over (f 1 )}, {right arrow over (f 2 )}, {right arrow over (f 3 )}), compute S2 commitments 
           
         
       
     
         [0000]    
       
         
           
             
               
                 C 
                 → 
               
               z 
             
             = 
             
               
                 ( 
                 
                   
                     1 
                      
                   
                   , 
                   
                     1 
                      
                   
                   , 
                   z 
                 
                 ) 
               
               · 
               
                 
                   f 
                   → 
                 
                 1 
                 
                   v 
                   
                     z 
                     , 
                     1 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 2 
                 
                   v 
                   
                     z 
                     , 
                     2 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 3 
                 
                   v 
                   
                     z 
                     , 
                     3 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 C 
                 → 
               
               r 
             
             = 
             
               
                 ( 
                 
                   
                     1 
                      
                   
                   , 
                   
                     1 
                      
                   
                   , 
                   r 
                 
                 ) 
               
               · 
               
                 
                   f 
                   → 
                 
                 1 
                 
                   v 
                   
                     r 
                     , 
                     1 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 2 
                 
                   v 
                   
                     r 
                     , 
                     2 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 3 
                 
                   v 
                   
                     r 
                     , 
                     3 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 C 
                 → 
               
               u 
             
             = 
             
               
                 ( 
                 
                   
                     1 
                      
                   
                   , 
                   
                     1 
                      
                   
                   , 
                   u 
                 
                 ) 
               
               · 
               
                 
                   f 
                   → 
                 
                 1 
                 
                   v 
                   
                     u 
                     , 
                     1 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 2 
                 
                   v 
                   
                     u 
                     , 
                     2 
                   
                 
               
               · 
               
                 
                   f 
                   → 
                 
                 3 
                 
                   v 
                   
                     z 
                     , 
                     3 
                   
                 
               
             
           
         
       
     
         [0060]    to z, r and u, respectively. Using the randomness of these commitments, generate proofs {right arrow over (π)} 1 =(π 1,1 , π 1,2 , π 1,3 )∈           3  and {right arrow over (π)} 2 =(π 2,1 , π 2,2 , π 2,3 )∈           3  that (z, r, u) satisfy the verification equations of the full-fledged scheme, i.e. 
         [0000]    
       
         
           
             
               
                 1 
                 
                    
                   T 
                 
               
               = 
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         g 
                         z 
                       
                       , 
                       z 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       
                         g 
                         r 
                       
                       , 
                       r 
                     
                     ) 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     e 
                      
                     
                       ( 
                       
                         
                           g 
                           i 
                         
                         , 
                         
                           M 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 1 
                 
                    
                   T 
                 
               
               = 
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         h 
                         z 
                       
                       , 
                       z 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       h 
                       , 
                       u 
                     
                     ) 
                   
                 
                 · 
                 
                   e 
                    
                   
                     ( 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       , 
                       v 
                     
                     ) 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       e 
                        
                       
                         ( 
                         
                           
                             h 
                             i 
                           
                           , 
                           
                             M 
                             i 
                           
                         
                         ) 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0061]    These proofs are obtained as 
         [0000]    
       
         
           
             
               
                 π 
                 → 
               
               1 
             
             = 
             
               
                 ( 
                 
                   
                     π 
                     
                       1 
                       , 
                       1 
                     
                   
                   , 
                   
                     π 
                     
                       1 
                       , 
                       2 
                     
                   
                   , 
                   
                     π 
                     
                       1 
                       , 
                       3 
                     
                   
                 
                 ) 
               
               = 
               
                 ( 
                 
                   
                     
                       g 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             1 
                           
                         
                       
                     
                     · 
                     
                       g 
                       r 
                       
                         - 
                         
                           v 
                           
                             r 
                             , 
                             1 
                           
                         
                       
                     
                   
                   , 
                   
                     
                       g 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             2 
                           
                         
                       
                     
                     · 
                     
                       g 
                       r 
                       
                         - 
                         
                           v 
                           
                             r 
                             , 
                             2 
                           
                         
                       
                     
                   
                   , 
                   
                     
                       g 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             3 
                           
                         
                       
                     
                     · 
                     
                       g 
                       r 
                       
                         - 
                         
                           v 
                           
                             r 
                             , 
                             3 
                           
                         
                       
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 π 
                 → 
               
               1 
             
             = 
             
               
                 ( 
                 
                   
                     π 
                     
                       2 
                       , 
                       1 
                     
                   
                   , 
                   
                     π 
                     
                       2 
                       , 
                       2 
                     
                   
                   , 
                   
                     π 
                     
                       2 
                       , 
                       3 
                     
                   
                 
                 ) 
               
               = 
               
                 ( 
                 
                   
                     
                       h 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             1 
                           
                         
                       
                     
                     · 
                     
                       h 
                       r 
                       
                         - 
                         
                           v 
                           
                             u 
                             , 
                             1 
                           
                         
                       
                     
                   
                   , 
                   
                     
                       h 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             2 
                           
                         
                       
                     
                     · 
                     
                       h 
                       r 
                       
                         - 
                         
                           v 
                           
                             u 
                             , 
                             2 
                           
                         
                       
                     
                   
                   , 
                   
                     
                       h 
                       z 
                       
                         - 
                         
                           v 
                           
                             z 
                             , 
                             3 
                           
                         
                       
                     
                     · 
                     
                       h 
                       r 
                       
                         - 
                         
                           v 
                           
                             u 
                             , 
                             3 
                           
                         
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0062]    and satisfy the verification equations 
         [0000]    
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   E 
                    
                   
                     ( 
                     
                       
                         g 
                         i 
                       
                       , 
                       
                         ( 
                         
                           
                             1 
                              
                           
                           , 
                           
                             1 
                              
                           
                           , 
                           
                             M 
                             i 
                           
                         
                         ) 
                       
                     
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
             
             = 
             
               
                 E 
                  
                 
                   ( 
                   
                     
                       g 
                       z 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       z 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       g 
                       r 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       r 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         1 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       1 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         2 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       2 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         3 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       3 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           h 
                           i 
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             
                               M 
                               i 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
                 · 
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           
                             H 
                              
                           
                            
                           
                             ( 
                             τ 
                             ) 
                           
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             v 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
               
             
             = 
             
               
                 E 
                  
                 
                   ( 
                   
                     
                       h 
                       z 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       z 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     h 
                     , 
                     
                       
                         C 
                         → 
                       
                       u 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         1 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       1 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         2 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       2 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         3 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       3 
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0063]    The signature comprises σ=({right arrow over (C)} z , {right arrow over (C)} r , {right arrow over (C)} u , v, {right arrow over (π)} 1 , {right arrow over (π)} 2 )∈           16 . 
         [0000]    SignDerive(pk, τ, {(ω i , σ (i) )} i=1   l ): given pk, a file identifier τ and l tuples (ω i , σ (i) ), parse each signature σ (i)  as a tuple of the form σ (i) =({right arrow over (C)} z,i , {right arrow over (C)} r,i , {right arrow over (C)} u,i , v, {right arrow over (π)} 1,i , {right arrow over (π)} 2,i )∈           16  for          =1 to l. Choose 
         [0000]    
       
         
           
             
               ρ 
               ′ 
             
              
             
               ← 
               
                 
                     
                 
                  
                 R 
                  
                 
                     
                 
               
             
              
             
               ℤ 
               p 
             
           
         
       
     
         [0000]    and compute 
         [0000]    
       
         
           
             
               
                 C 
                 → 
               
               z 
             
             = 
             
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                    
                 
                  
                 
                     
                 
                  
                 
                   
                     
                       C 
                       → 
                     
                     
                       z 
                       , 
                       i 
                     
                     
                       ω 
                       i 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       C 
                       → 
                     
                     r 
                   
                 
               
               = 
               
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         C 
                         → 
                       
                       
                         r 
                         , 
                         i 
                       
                       
                         ω 
                         i 
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         C 
                         → 
                       
                       u 
                     
                   
                 
                 = 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         C 
                         → 
                       
                       
                         u 
                         , 
                         i 
                       
                       
                         ω 
                         i 
                       
                     
                     · 
                     
                       
                         
                           H 
                            
                         
                          
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       
                         - 
                         
                           ρ 
                           ′ 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               v 
               = 
               
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                      
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         v 
                         i 
                         
                           ω 
                           i 
                         
                       
                       · 
                       
                         h 
                         
                           ρ 
                           ′ 
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         π 
                         → 
                       
                       1 
                     
                   
                 
                 = 
                 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                        
                     
                      
                     
                         
                     
                      
                     
                       
                         π 
                         
                           1 
                           , 
                           i 
                         
                         
                           ω 
                           i 
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           π 
                           → 
                         
                         2 
                       
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                        
                     
                      
                     
                         
                     
                      
                     
                       π 
                       
                         2 
                         , 
                         i 
                       
                       
                         ω 
                         i 
                       
                     
                   
                 
               
             
              
             
                 
             
           
         
       
     
         [0064]    Then S3 re-randomize the commitments and proofs and return σ=({right arrow over (C)} z , {right arrow over (C)} r , {right arrow over (C)} u , v, {right arrow over (π)} 1 , {right arrow over (π)} 2 ). 
         [0000]    Verify(pk, σ, τ, (M 1 , . . . , M n )): given a pair (τ, (M 1 , . . . M n )) and a purported signature σ, parse the signature as ({right arrow over (C)} z , {right arrow over (C)} r , {right arrow over (C)} u , v, {right arrow over (π)} 1 , {right arrow over (π)} 2 ). Then, S5 return 1 if and only if (M 1 , . . . , M n )≠(         , . . . ,          ) and the Sign verifications are satisfied S4, i.e. 
         [0000]    
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   E 
                    
                   
                     ( 
                     
                       
                         g 
                         i 
                       
                       , 
                       
                         ( 
                         
                           
                             1 
                              
                           
                           , 
                           
                             1 
                              
                           
                           , 
                           
                             M 
                             i 
                           
                         
                         ) 
                       
                     
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
             
             = 
             
               
                 E 
                  
                 
                   ( 
                   
                     
                       g 
                       z 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       z 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       g 
                       r 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       r 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         1 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       1 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         2 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       2 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         1 
                         , 
                         3 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       3 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 ∏ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           h 
                           i 
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             
                               M 
                               i 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
                 · 
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           
                             H 
                              
                           
                            
                           
                             ( 
                             τ 
                             ) 
                           
                         
                         , 
                         
                           ( 
                           
                             
                               1 
                                
                             
                             , 
                             
                               1 
                                
                             
                             , 
                             v 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
               
             
             = 
             
               
                 E 
                  
                 
                   ( 
                   
                     
                       h 
                       z 
                     
                     , 
                     
                       
                         C 
                         → 
                       
                       z 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     h 
                     , 
                     
                       
                         C 
                         → 
                       
                       u 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         1 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       1 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         2 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       2 
                     
                   
                   ) 
                 
               
               · 
               
                 E 
                  
                 
                   ( 
                   
                     
                       π 
                       
                         2 
                         , 
                         3 
                       
                     
                     , 
                     
                       
                         f 
                         → 
                       
                       3 
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0065]    The unforgeability of the scheme can be proved under the Decision Linear assumption, which informally says that it is infeasible to decide whether three vectors of group elements of dimension 3 are linearly dependent or not. Moreover, the scheme is unconditionally context-hiding. 
         [0066]    The advantage of the present invention is that it can allow a signer to sign vectors consisting of group elements without knowing their discrete logarithms. For example, the signature schemes make it possible for the signer to sign ciphertexts without necessarily knowing the underlying plaintext. 
         [0067]    It will be appreciated that the schemes of the present invention can be used to outsource encrypted datasets in cloud computing services. In addition, linearly homomorphic signatures can also serve as proofs of correct aggregation in anonymous recommendation systems. 
         [0068]    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.