Computational Difficulty - Foundations of Cryptography: Basic Tools - page 62

and the domain-sampling algorithm selects uniformly from this set. As for the functions
themselves, we set

f P , G , Z ( x ) def

Z σ · G x

= mod P (2.13)

The reader can easily verify that both functions are permutations over { 1 ,..., P − 1 } .In
fact, the function f P , G , Z coincides with the function DLP P , G presented in Section 2.4.3.
Furthermore, the ability to form a claw for the index ( P , G , Z ) yields the ability to
find the discrete logarithm of Z mod P to base G (since G x ≡ Z · G y (mod P )

yields G x − y Z (mod P )). Thus, the ability to form claws for a non-negligible

fraction of the index set translates to the ability to invert the DLP collection presented
in Section 2.4.3. Put in other words, if the DLP collection is one-way, then the collection
of pairs of permutations defined in Eq. (2.13) is claw-free.
The foregoing collection does not have the additional property of having an ef-
ficiently recognizable index set, because it is not known how to efficiently recognize
primitive elements modulo a prime. This can be remedied by making a slightly stronger
assumption concerning the intractability of DLP. Specifically, we assume that DLP is
intractable even if one is given the factorization of the size of the multiplicative group
(i.e., the factorization of P − 1) as additional input. Such an assumption allows one to
add the factorization of P − 1 into the description of the index. This makes the index
set efficiently recognizable (since one can test whether or not G is a primitive element
by raising it to powers of the form ( P − 1) / Q , where Q is a prime factor of P − 1). If
DLP is hard also for primes of the form 2 Q + 1, where Q is also a prime, life is even
easier: To test whether or not G is a primitive element mod P , one simply computes
G 2

≡

mod P and G ( P − 1) / 2

mod P and checks whether or not both of them are different

from 1.

2.4.5.3. Claw-Free Collections Based on Factoring

We now show that a claw-free collection (of functions) does exist under the assumption
that integer factorization is infeasible. In the following description, we use the structural
properties of Blum integers (i.e., products of two primes both congruent to 3 mod 4),
which are further discussed in Appendix A. In particular, for a Blum integer N , it holds
that

• the Jacobi symbol of

1 mod N equals 1, and
• half of the square roots of each quadratic residue have Jacobi symbol 1.

−

Let J + N (resp., J − N ) denote the set of residues in the multiplicative group modulo N
with Jacobi symbol + 1 (resp., − 1).
The index set of the collection consists of all Blum integers that are composed of
two primes of the same length. The index-selecting algorithm, on input 1 n , uniformly
selects such an integer by uniformly selecting two ( n -bit) primes, each congruent to 3
mod 4, and outputting their product, denoted N . Both functions of index N , denoted f N
and f N , consist of squaring modulo N , but their corresponding domains are disjoint.
The domain of function f N equals the set J ( − 1) N . The domain-sampling algorithm,
denoted D , uniformly selects an element of the corresponding domain in the natural