Cryptography Reference
In-Depth Information
t
)
in the range of I
(1
n
)
such
5.
Inverting with trapdoor:
For every n
∈ N
, any pair
(
i
,
I
n
, and every x
that i
∈
∈
D
i
,
[
F
−
1
(
t
2
−
n
Pr
,
f
i
(
x
))
=
x
]
>
1
−
We comment that an exponentially vanishing measure of indices for which any of
Items 2, 3, and 5 does not hold can be omitted from
I
(and accounted for by the error
allowed in Item 1). Items 3 and 5 can be relaxed by taking the probabilities also over
all possible
x
∈
D
i
with uniform distribution.
2.4.4.2. The RSA (and Factoring) Trapdoor
The RSA collection presented earlier can be easily modified to have the trapdoor
property. To this end, algorithm
I
RSA
should be modified so that it outputs both the
index (
N
,
e
) and the trapdoor (
N
,
d
), where
d
is the multiplicative inverse of
e
mod-
ulo (
P
−
1)
·
(
Q
−
1) (note that
e
has such inverse because it has been chosen to be
relatively prime to (
P
−
1)
·
(
Q
−
1)). The inverting algorithm
F
−
1
RSA
is identical to
the algorithm
F
RSA
(i.e.,
F
−
1
RSA
((
N
,
d
)
,
y
)
=
y
d
mod
N
). The reader can easily verify
that
F
−
1
RSA
((
N
,
d
)
,
F
RSA
((
N
,
e
)
,
x
))
=
x
ed
mod
N
indeed equals
x
, for every
x
in the multiplicative group modulo
N
. In fact, one can
show that
x
ed
≡
x
(mod
N
) for every
x
(even in case
x
is not relatively prime to
N
).
The Rabin collection presented earlier can be easily modified in a similar manner,
enabling one to efficiently compute all four square roots of a given quadratic residue
(mod
N
). The trapdoor in this case is the prime factorization of
N
. The square roots
mod
N
can be computed by extracting a square root modulo each of the prime factors
of
N
and combining the results using the Chinese Remainder Theorem. Efficient algo-
rithms for extracting square roots modulo a given prime are known (see Appendix A).
Furthermore, in case the prime
P
is congruent to 3 mod 4, the square roots of
x
mod
P
can be computed by raising
x
to the power
P
+
1
4
(while reducing the intermediate
results mod
P
). Furthermore, in case
N
is a Blum integer, the collection SQR, presented
earlier, forms a collection of trapdoor permutations (provided, of course, that factoring
is hard).
2.4.5.
∗
Claw-Free Functions
The formulation of collections of one-way functions is also a convenient starting point
for the definition of a collection of claw-free pairs of functions.
2.4.5.1. The Definition
Loosely speaking, a claw-free collection consists of a set of pairs of functions that are
easy to evaluate, that have the same range for both members of each pair, and yet for
which it is infeasible to find a range element together with a pre-image of it under each
of these functions.