Cryptography Reference
In-Depth Information
factoring is also hard. This is a straightforward consequence of Algorithm 2.8 and of
the proof of Proposition 2.14, which in polynomial time reduces the computation of
square roots modulo
n
to the computation of square roots modulo its prime factors.
∈ Z
+
|
Definition 3.18
Let
I
pq
, where
p
and
q
are distinct primes of
the same length}. Then the family of
Rabin functions
is the family
={
n
n
=
: Z
n
{
R
n
→
Z
n
}
n
∈
I
, where
R
n
(
x
2
mod
n
. Similarly, if
J
is the set of Blum integers, the
family of
Blum-Williams permutations
is the family
x
)
:=
{
BW
n
:
QR
n
→
QR
n
}
n
∈
J
,
x
2
mod
n
(these are permutations as a consequence of
where, again,
BW
n
(
x
)
:=
Theorem3.6).
These families are one-way, for we have:
Theorem 3.8
Under the factoring assumption, the family of Rabin functions is a
family of one-way functions and the family of Blum-Williams permutations is a
family of one-way permutations.
Proof
To see that the Rabin functions are one-way we note that:
1. There exists a PPT algorithm that, on input
k
, outputs an integer
n
which is a
product of two random
k
-bit primes (this algorithm can be obtained from one
that outputs a random
k
-bit prime, see Algorithm 6.2).
2. There exists a PPT algorithm that, on input
n
, outputs a random
x
← Z
n
.
∈ Z
n
, computes
x
2
mod
n
∈ Z
n
.
3. There exists a PPT algorithm that, given
x
2
A,
(A(
R
n
(
))
≡
4. Finally, Theorem 3.7 implies that for every PPT algorithm
Pr
x
(
))
=
(
A
(
)
=
)
≤
negl
(
)
x
mod
n
Pr
Sqr
k
1
k
, for some negligible function
negl
.
The proof that the Blum-Williams permutations are a one-way family of permu-
tations is similar, bearing in mind that Blum integers may be generated by a PPT
algorithm and that a random
x
←
QR
n
may be chosen in polynomial time by just
Z
n
.
squaring a random element of
Remark 3.9
We will see that the family of Rabin functions is also of interest for
public-key cryptography. One of the reasons for this interest is the fact that this
family has a property that is even stronger than the one we have just seen, namely,
the Rabin functions are a family of one-way trapdoor functions. Roughly, this means
that there is a “trapdoor information”—the factorization of
n
in this case—that allows
the efficient inversion of the functions.
As mentioned before, in order to obtain a PRG from a length-preserving one-way
permutation we need a hard-core predicate. For the Blum-Williams permutations
this is given by the following result of Blum et al. [31]:
Theorem 3.9
Let n be a Blum integer. Under the factoring assumption, the least
significant bit is a hard-core predicate for the one-way permutation B W
n
.
This allows us to define the Blum-Blum-Shub (BBS) pseudo-random generator
as follows:
