Cryptography Reference
In-Depth Information
master private key.
2
The output of
Der
is the user private key:
usk
:=
(
sk
,
pk
,
cert
).
•
Sign
: The signing algorithm takes as input a user private key
usk
and a message
m
, and produces a signature
σ
as follows:
-
usk
is parsed into its components (
sk, pk, cert
).
- The standard
Σ
-signature
s
←
SSign
(
sk
,
m
)
is computed.
- The output of
Sign
is the signature
σ
:=
(
s
,
pk
,
cert
)
.
•
Ve r
: The verification algorithm takes as input the master public key
mpk
, the user
identity
id
, a message
m
, and the signature
σ
=
(
s
,
pk
,
cert
)
and outputs a bit
b
.
b
=
1 if and only if
SVer
(
pk
,
m
,
s
)
=
1 and
SVer
(
mpk
,
pk
||
id
,
cert
)
=
1
.
As usual,
b
=
1 is interpreted as
valid
and
b
=
0as
invalid
.
This construction is interesting not only because it gives an automatic procedure
to obtain IBS schemes from standard signatures but also because the security of the
IBS schemes thus obtained may be reduced to that of the standard signature schemes
used in the construction. This is discussed in detail in [17], where the following result
is proved:
Theorem 10.1
Let
Σ
be a UF-CMA secure standard signature scheme. Then the
scheme Cert-IB
Σ
is a UF-CMA secure IBS scheme.
Exercise 10.1
Write a Maple version of the IBS scheme obtained by applying the
Remark 10.1
We have seen inChap.
9
that UF-CMA secure schemes exist evenwith-
out assuming random oracles—for example, the Cramer-Shoup signature scheme.
From these schemes and the SS-2-IBS construction one obtains UF-CMA secure
IBS schemes. We have also mentioned in Chap.
9
that, as was shown in [166], the
existence of UF-CMA secure schemes is equivalent to the existence of one-way func-
tions. From this fact and the preceding theorem, a result of considerable theoretical
interest follows, namely:
•
The existence of UF-CMA secure IBS schemes is equivalent to the existence of
one-way functions
.
Indeed, if one-way functions exist, then UF-CMA secure IBS schemes exist by
what we have just seen and, for the converse, it suffices to observe that any secure
IBS scheme defines a secure standard signature scheme by including an arbitrary
2
This can be interpreted as the PKG creating a certificate stating that “the public key of user
id
is
pk
”.
