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

2.4.3.2. The Rabin Function

The Rabin collection of functions is defined analogously to the RSA collection, except
that the function is squaring modulo N (instead of raising to the e th power mod N ).
Namely,

Rabin N ( x ) def = x 2 mod N (2.11)

This function, however, does not induce a permutation on the multiplicative group
modulo N , but is rather a 4-to-1 mapping on this group.
It can be shown that extracting square roots modulo N is computationally equiv-
alent to factoring N (i.e., the two tasks are reducible to one another via probabilistic
polynomial-time reductions). For details, see Exercise 21. Hence, squaring modulo a
composite is a collection of one-way functions if and only if factoring is intractable. We
remind the reader that it is generally believed that integer factorization is intractable,
and this holds also for the special case in which the integer is a product of two primes
of the same length. 8

2.4.3.3. The Factoring Permutations

For a special subclass of the integers, known by the name of Blum integers , the function
Rabin N ( · ) defined earlier induces a permutation on the quadratic residues modulo N .
We say that r is a quadratic residue mod N if there exists an integer x such that r ≡ x 2
(mod N ). We denote by Q N the set of quadratic residues in the multiplicative group mod
N . For purposes of this paragraph, we say that N is a Blum integer if it is the product of
two primes, each congruent to 3 mod 4. It can be shown that when N is a Blum integer,
each element in Q N has a unique square root that is also in Q N , and it follows that
in this case the function Rabin N ( · ) induces a permutation over Q N . This leads to the
introduction of the collection SQR def F SQR ) of permutations. On input 1 n ,

algorithm I BI selects uniformly two primes, P and Q , such that 2 n − 1

= ( I BI , D QR ,

≤ P < Q < 2 n and

Q . On input N , algorithm D QR uniformly
selects an element of Q N by uniformly selecting an element of the multiplicative
group modulo N and squaring it mod N . Algorithm F SQR is defined exactly as in
the Rabin collection. The resulting collection is one-way, provided that factoring is
intractable.

P ≡ Q ≡ 3 (mod 4), and outputs N = P ·

2.4.3.4. Discrete Logarithms
Another computational number-theoretic problem that is widely believed to be in-
tractable is that of extracting discrete logarithms in a finite field (and, in particular, of
prime cardinality). The DLP collection of functions, which borrows its name (and its
conjectured one-wayness) from the discrete-logarithm problem , is defined by the triplet
of algorithms ( I DLP ,

F DLP ).
On input 1 n , algorithm I DLP selects uniformly a prime P , such that 2 n − 1

D DLP ,

2 n ,
and a primitive element G in the multiplicative group modulo P (i.e., a generator

≤ P <

8 In fact, the latter case is believed to be the hardest.