Cryptography Reference
In-Depth Information
10.2 Identity-Based Signatures
Before studying IBE in more detail, we will have a brief look at identity-based
signatures (IBS). IBS schemes are much easier to construct than IBE schemes. The
reason is that in IBS schemes the first usage of a cryptographic primitive is made
by the private key owner when computing the signature, allowing her to embed in
the message the necessary information about her public key. In contrast, in IBE, the
starting point is the encryption of a message and, in that case, the user performing it
must derive all the information from the public system parameters and the identity
string of the receiver. Because of this asymmetry, while full-featured IBE schemes
were introduced only recently and there are not many of them, a great variety of IBS
schemes are known, the first one having already been proposed by Shamir in his
1984 paper [175].
10.2.1 IBS Schemes
Before describing how to construct IBS schemes, we give the formal definition of
such a scheme, which is the following:
Definition 10.1
An
identity-based signature scheme
(or an
IBS scheme
, for short)
is a 4-tuple
IB
(
Setup
,
Der
,
Sign
,
Ve r
) of polynomial-time algorithms, where
the first three may be probabilistic and
Ve r
is deterministic, that act as follows:
Σ
=
Setup
is run by the PKG and, on input a security parameter 1
k
, outputs a master key
mk
•
=
(
mpk
,
msk
)
. The master public key
mpk
is published as a system parameter.
}
∗
of
•
Der
is run by the PKG and, on input
msk
and the identity string
id
∈{
0
,
1
a user, outputs the user's private key
usk
←
Der
(
msk
,
id
)
, which is then securely
transmitted to the user with identity
id
.
•
The signing algorithm
Sign
takes as input a user private key
usk
and a message
m
, and outputs a signature
σ
←
(
,
)
Sign
usk
m
.
•
The verification algorithm
Ve r
takes as input the master public key
mpk
,a
user identity string
id
, a message
m
and a signature
σ
, and outputs a bit
b
:=
Ve r
(
mpk
,
id
,
m
,σ)
∈{
0
,
1
}
.
b
=
1 is interpreted as meaning
valid
and
b
=
0as
meaning
invalid
.
We require that
Ve r
(
mpk
,
id
,
m
,
Sign
(
usk
,
m
)) =1 whenever
mpk
and
usk
have been
generated as indicated above.
In order to define the concept of unforgeability under a chosen message attack for
IBS schemes, we consider the following experiment:
Definition 10.2
The
IB signature unforgeability experiment under an adaptive cho-
sen message attack
IBSign
uf-cma
A,
IB
Σ
(
)
k
is the following:
Setup
is run on input 1
k
, obtaining a master key
1
k
(
,
)
←
(
)
1.
mpk
msk
Setup
.
