Cryptography Reference
In-Depth Information
present a simple version of their scheme that is unforgeable under a weak chosen-message
attack if the
q
-strong Diffie-Hellman problem holds (these notions are defined below).
We briefly introduce pairing groups (more details are given in Chapter
26
). We use
multiplicative notation for pairing groups, despite the fact that
G
1
and
G
2
are typically
subgroups of elliptic curves over finite fields and hence are usually written additively.
Definition 22.2.14
(
Pairing groups
)Let
G
1
,
G
2
,
G
T
be cyclic groups of prime order
r
.A
pairing is a map
e
:
G
1
×
G
2
→
G
T
such that:
1.
e
is
non-degenerate
and
bilinear,
i.e.
g
1
∈
G
1
−{
1
}
and
g
2
∈
G
2
−{
1
}
implies
=
1 and
e
(
g
1
,g
2
)
=
e
(
g
1
,g
2
)
ab
for
a,b
∈ Z
,
2. there is a polynominal-time algorithm to compute
e
(
g
1
,g
2
).
e
(
g
1
,g
2
)
For the Boneh-Boyen scheme we also need there to be an efficiently computable injective
group homomorphism
ψ
:
G
2
→
G
1
(for example, a distortion map; see Section
26.6.1
).
KeyGen
: Choose
g
2
∈
G
2
−{
1
}
uniformly at random and set
g
1
=
ψ
(
g
2
). Let
z
=
e
(
g
1
,g
2
).
Choose 1
≤
a<r
and set
u
=
g
2
. The public key is
pk
=
(
g
1
,g
2
,u,z
) and the private key is
a
.
Sign
(
m
,a
): We assume that
m
∈ Z
/r
Z
.If
a
+
≡
0 (mod
r
) then return
⊥
, else compute
m
g
(
a
+
m
)
−
1
(mod
r
)
=
and return
s
.
s
1
Verify
(
m
,
s
,
pk
): Check that
s
∈
G
1
and then check that
e
(
s
,ug
2
)
=
z.
Box 22.2
Weakly secure Boneh-Boyen signature scheme
We will assume that elements in
G
1
have a compact representation (i.e., requiring not
much more than log
2
(
r
) bits), whereas elements of
G
2
do not necessarily have a compact
representation. The signature is an element of
G
1
and hence is very short. Box
22.2
gives
the (weakly secure) Boneh-Boyen Signature Scheme.
Exercise 22.2.15
Show that if the Verify algorithm for weakly secure Boneh-Boyen sig-
natures accepts (
m
,
s
) then
s
g
(
m
+
a
)
−
1
(mod
r
)
=
.
1
The Boneh-Boyen scheme is unforgeable under a weak chosen-message attack if the
q
-strong Diffie-Hellman problem holds. We define these terms now.
Definition 22.2.16
A
weak chosen-message attack
(called a
generic chosen-message
attack
in [
235
]) on a signature scheme is an adversary
A
that outputs a list
m
1
,...,
m
t
of
messages, receives a public key and signatures
s
1
,...,
s
t
on these messages and then must
output a message
m
and a signature
s
. The adversary wins if Verify(
m
,
s
,
pk
)
=
“valid” and
if
m
∈{
m
1
,...,
m
t
}
.
Hence, a weak chosen-message attack is closer to a known message attack than a
chosen-message attack.
