SIGNATURE VERIFICATION SYSTEM, SIGNATURE DEVICE, VERIFICATION DEVICE, AND SIGNATURE VERIFICATION METHOD

摘要

A group structure preserving signature system that can be applied to groups based on symmetric bilinear mapping, that reduces the signature length, and that enables efficient computation of verification equations is provided. At least, information indicating p, G1, G2, GT, e, g1, and g2, information needed to obtain e(ku, hv), and data that includes gs, hs, gt, ht, {g1, h1}, . . . , {gK, hK} are held as a public key vk, and data that includes vk, γs, δs, γt, δt, δu, δv, {γ1, δ1}, . . . , {γK, δK} are held as a secret key sk. A signature device selects ζ and ρ at random from integers between 0 and p−1, both inclusive, obtains w, s, t, and r, and generates, as a signature σ, data that includes w, s, t, and r. A verification device verifies the signature σ by using two verification equations.

主权项

1. A signature verification system comprising:
a signature device which generates a signature, and a verification device which verifies the signature, the signature device comprising: a signature recording unit which records information indicating p, G1, G2, GT, e, g1, and g2, information needed to obtain e(gu, gv) and e(hu, hv), and data that includes gs, hs, gt, ht, {g1, h1}, . . . , {gK, hK} as a public key vk and records data that includes vk, γs, δs, γt, δt, γu, δu, γv, δv, {γ1, δ1}, . . . , {γK, δK} as a secret key sk; and a signature generating unit which selects ζ and ρ at random from integers between 0 and p−1, both inclusive, obtains w, s, t, and r, as given below,w=g1ζ,s=g2ρ,t=(g2δu·δv-δs·ρ∏k=1Kmk-δk)1/δtr=(g2γu·γv-γs·ρ·t-γt∏k=1Kmk-γk)1/ζand generates, as a signature σ, data that includes w, s, t, and r; and
the verification device comprising: a verification recording unit which records the public key vk; and a verifying unit which checks whether two equations
e(gu,gv)=e(gs,s)e(gt,t)(Πk=1Ke(gk,mk))e(w,r),e(hu,hv)=e(hs,s)e)(ht,t)Πk=1Ke(hk,mk)are satisfied, and which determines that the signature is correct when the two equations are satisfied, or determines that the signature is incorrect when at least one of the two equations is not satisfied,
where G1, G2, and GT represent groups of order p, e represents pairing of G1×G2→GT, g1 represents any generator of group G1, g2 represents any generator of group G2, K represents a predetermined integer not smaller than 1, k represents an integer between 1 and K, both inclusive, m1, . . . , mK represent elements of group G1, message M is M=(m1, . . . , mK), ̂ represents a power; γs, δs, γt, δt, γu, δu, γv, δv, {γ1, δ1}, . . . , {γK, δK} are integers between 0 and p−1, both inclusive; and gs, hs, gt, ht, gu, hu, gv, hv, {g1, h1}, . . . , {gK, hK} are given as follows: gs=g1̂γshs=g1̂δs gt=g1̂γtht=g1̂δt gu=g1̂γuhu=g1̂δu gv=g2̂γvhv=g2̂δv gk=g1̂γkhk=g1̂δk where k=1, . . . , K.