Cryptography Reference
In-Depth Information
in the subset S , and hence to forge signatures computed with such a scheme. The
reason is that a randomly chosen element of
Z n will almost surely fall outside S and
hence whether inverting the RSA function on S is easy or not is irrelevant as far as
its one-wayness is concerned.
The obstacle we have just mentioned can be removed if we additionally assume
that the hash function H is ideal in the sense that it hashes strings of
} onto
{
0
,
1
the full domain of the RSA function,
Z n , uniformly at random. This is the same as
saying that H behaves as a random oracle, i.e., that H returns a random element
of
Z n each time it is invoked, except that if queried twice on the same message it
returns the same result both times. For this, it is convenient to think of H as a process
which maintains a table of input-output pairs. All parties involved in the signature
scheme will have oracle access (as a black box) to the process H and, when a query
about a message m is made, the process will check whether its table contains a pair
(
—which will happen if the query about m was already made before—and, in
that case will return h . Otherwise, H picks a random h
m
,
h
)
∈ Z n , adds the pair
(
m
,
h
)
to
the table, and returns h as its answer to the query.
By assuming that the hash function H is a random oracle onto the full domain
of the RSA function we obtain a variant of hashed RSA which is UF-CMA secure
assuming that the RSA problem is hard, thus obtaining a signature scheme with a
security reduction in the random oracle model. This scheme is called Full Domain
Hash and we will denote it simply by FDH (other notations which emphasize the
fact that this is an RSA-based scheme are FDH-RSA or RSA-FDH). The scheme,
introduced in [18] and analyzed in more detail in [20] can then be defined as follows:
} → Z n ,the FDH signature
scheme is the scheme ( Gen , Sign , Ve r ) defined by the following algorithms:
Definition 9.7 Given a random hash function H
:{
0
,
1
Gen : On input 1 k , run the RSA instance generator (Algorithm 8.1) to obtain
(
n
,
e
,
d
)
Gen RSA .
Then set pk
:= (
n
,
e
)
and sk
:= (
n
,
d
)
. pk is the public
1 k
key and sk is the private key, so that
(
pk
,
sk
)
Gen
(
).
Sign : On input a private key sk
= (
n
,
d
)
and a message m
∈ Z n , proceed as
follows:
- Query the oracle H on m and obtain H
(
m
)
in return.
- Compute the signature:
d mod n
σ :=
Sign
(
sk
,
m
) =
H
(
m
)
∈ Z n .
Ve r : On input a public key pk
= (
n
,
e
)
, a message m
∈ Z n , and a signature
σ ∈ Z n , proceed as follows:
- Query the oracle H on m and obtain H
(
m
)
in return.
- Check whether
e mod n
H
(
m
) = σ
∈ Z n
and set Ve r
(
pk
,
m
,σ) :=
1 if this condition holds and Ve r
(
pk
,
m
,σ) :=
0
otherwise.
Search WWH ::




Custom Search