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.
Search WWH ::




Custom Search