US 2014/0369494 A1Published application

Signature verification system, signature device, verification device, and signature verification method

AssigneeNippon Telegraph and Telephone Corporation

InventorMasayuki Abe

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims8

Dependent claims

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
=
g
1
ζ
,

s
=
g
2
ρ
,

t
=
(
g
2
δ
u
·
δ
v
-
δ
s
·
ρ

∏
k
=
1
K


m
k
-
δ
k
)
1
/
δ
t
r
=
(
g
2
γ
u
·
γ
v
-
γ
s
·
ρ
·
t
-
γ
t

∏
k
=
1
K


m
k
-
γ
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.

106 more elements

A signature verification method used with a signature device which generates a signature and a verification device which verifies the signature,

the signature verification method comprising:
a signature recording step in which the signature device 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, δv, γv, δv, {γ1, δ1}, . . . , {K, δK} as a secret key sk;
a signature generating step in which the signature device selects ζ and ρ at random from integers between 0 and p−1, both inclusive, obtains w, s, t, and r, as given below,
w
=
g
1
ζ
,

s
=
g
2
ρ
,

t
=
(
g
2
δ
u
·
δ
v
-
δ
s
·
ρ

∏
k
=
1
K


m
k
-
δ
k
)
1
/
δ
t
r
=
(
g
2
γ
u
·
γ
v
-
γ
s
·
ρ
·
t
-
γ
t

∏
k
=
1
K


m
k
-
γ
k
)
1
/
ζ
and generates, as a signature σ, data that includes w, s, t, and r;
a verification recording step in which the verification device records the public key vk;
and
a verifying step in which the verification device 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 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.

101 more elements

A signature verification method used with a signature device which generates a signature and a verification device which verifies the signature,

the signature verification method comprising:
a signature recording step in which the signature device records information indicating p, G1, G2, GT, e, gt, and g2, information needed to obtain 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, δu, δv, {γ1, δ1}, . . . , {γ6K, δK} as a secret key sk;
a signature generating step in which the signature device selects ζ and ρ at random from integers between 0 and p−1, both inclusive, obtains w, s, t, and r, as given below,
w
=
g
1
ζ
,

s
=
g
2
ρ
,

t
=
(
g
2
δ
u
·
δ
v
-
δ
s
·
ρ

∏
k
=
1
K


m
k
-
δ
k
)
1
/
δ
t
r
=
(
g
2
-
γ
u
·
ρ
·
t
-
γ
t

∏
k
=
1
K


m
k
-
γ
k
)
1
/
ζ
and generates, as a signature σ, data that includes w, s, t, and r;
a verification recording step in which the verification device records the public key vk;
and
a verifying step in which the verification device checks whether two equations
1=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 determines that the signature is correct when the two equations are satisfied, or it is determined 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, δv, {γ1, δ1}, . . . , {K, δK} are integers between 0 and −1, both inclusive;
and
gs, hs, gt, ht, hu, hu, gv, {g1, h1}, . . . , {gK, hK} are given as follows:
gs=g1̂γshs=g1̂δs
gt=g1̂γtht=g1̂δt
hu=g1̂δu
hv=g2̂δv
gk=g1̂γkhk=g1̂δk
where k=1, . . . , K.

96 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/371,110Filed 18 Jan 2013
Priority: JP 2012-01222424 Jan 2012
Published: 18 Dec 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

H04L 9/3006
Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy: underlying…
G09C 1/00
Apparatus or methods whereby a given sequence of signs
H04L 9/3073
Involving algebraic varieties, e.g. elliptic or hyper-elliptic curves: involving pairings, e.g. identity based encryption [IBE], bilinear mappings…
H04L 9/3218
Including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity…: using…