Cryptographic devices and methods for generating and verifying linearly homomorphic structure-preserving signatures

A method of verifying a linearly homomorphic signature σ comprising signature elements (z, r, u) on a vector (M1, . . . , Mn)∈n, wherein denotes a first group, the method comprising in a processor of a device:

• verifying that (M1, . . . , Mn)≠(, . . . , ) and that (z, r, u) satisfy a first equality
• =e(gz,z)·e(gr,r)·Πi=1ne(gi,Mi) and a second equality =e(hz,z)·e(h,u)·Πi=1ne(hi,Mi),
• wherein e(·, ·) denotes a symmetric and commutative pairing and wherein h, hz, hi, gr, gi and gz are elements of a second group;
• 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.

A device for generating a linearly homomorphic signature σ on a vector (M1, . . . , Mn)∈n, wherein denotes a first group, the device comprising a processor configured to:

• compute, using a signing key sk={χi, γi, δi}i=1n, 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
• output the signature σ comprising the signature elements (z, r, u).

A device for verifying a linearly homomorphic signature σ comprising signature elements (z, r, u) on a vector (M1, . . . , Mn)∈n, wherein denotes a first group, the device comprising a processor configured to:

• verify that (M1, . . . , Mn)≠(, . . . , ) and that (z, r, u) satisfy a first equality
• =e(gz,z)·e(gr,r)·Πi=1ne(gi,Mi) and a second equality =e(hz,z)·e(h,u)·Πi=1ne(hi,Mi),
• wherein e(·, ·) denotes a symmetric and commutative pairing and wherein h, hz, hi, gr, gi and gz 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.

A device for generating a linearly homomorphic signature σ on a vector (M1, . . . , Mn)∈n, wherein denotes a first group, the device comprising processor configured to:

• compute, using a signing key
• sk
• =
• {
• h
• z
• α
• r
• ,
• χ
• i
• ,
• γ
• i
• ,
• δ
• i
• }
• i
• =
• 1
• n
• wherein hz is a member of a second group and αr is an integer, signature elements (z, r, u, v) by calculating
• 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
• ρ
• ,
• 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.

A device for verifying a linearly homomorphic signature σ on a vector (M1, . . . , Mn)∈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 comprising a processor configured to:

• verify that (M1, . . . , Mn)≠(, . . . , ) and that the verifications Πi=1nE(gi, (, , Mi))−1=E(gz, {right arrow over (C)}z)·E(gr, {right arrow over (C)}r)·E (π1,1, {right arrow over (f)}1)·E(π1,2, {right arrow over (f)}2)·E(π1,3, {right arrow over (f)}3) and Πi=1nE(hi, (, , Mi))−1·E((τ), (, v))−1=E(hz, {right arrow over (C)}z)·E(h, {right arrow over (C)}u)·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, hz, hi, gr, gi and gz 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.