Cryptography Reference
In-Depth Information
We are now going to show that, if factoring is hard, then the functions
BW
n
(where
n
is assumed to be a Blum integer) define a family of one-way permutations. More
generally, we can show that if factoring is hard, then the squaring functions modulo
n
, where
n
is a product of two distinct odd primes, are a family of one-way functions,
so that the former result will be obtained by restricting this family to Blum integers
and applying Theorem 3.6. For this, we must define more precisely the meaning of
“factoring is hard”. In order to do that we first define a factoring experiment:
Definition 3.14
The
factoring experiment
Fact
A
(
k
)
, where
A
is a PPT algorithm
and
k
a positive integer, is the following:
1. Run a PPT algorithm that, on input 1
k
outputs
n
pq
, where
p
and
q
are two
random
k
-bit primes (except with probability negligible in
k
).
=
2.
is given
n
and outputs a positive integer
r
.
3. The output of the experiment is defined to be 1 if
r
A
|
n
and
r
=
1,
r
=
n
(i.e., if
r
is a proper factor of
n
) and 0 otherwise.
Then we may define the
factoring assumption
:
Definition 3.15
(Factoring assumption) For every PPT algorithm
A
there exists a
negligible function
negl
such that
Pr
(
Fact
A
(
k
)
=
1
)
≤
negl
(
k
).
Remarks 3.4
1. The factoring assumption may be defined, more generally, relative to any PPT
algorithm that, on input 1
k
, generates a modulus
n
which is a product of (not
necessarily random)
k
-bit primes (see [109, Definition 7.45] for details).
where factoring algorithms and their efficiency are analyzed.
Next we are going to see that computing square roots modulo
n
, where
n
is
a product of two
k
-bit primes, is as hard as factoring
n
.Inawaysimilartothe
factoring assumption we may define what it means that “computing square roots is
hard”. For this we define:
Definition 3.16
The
square root computation experiment
,
Sqr
A
(
k
)
, where
A
is a
PPT algorithm and
k
a positive integer, is the following:
1. Run a PPT algorithm that on input 1
k
outputs
n
pq
where
p
and
q
are (except
with probability negligible in
k
) random
k
-bit primes.
2. Choose a random
y
=
←
QR
n
.
)
∈ Z
n
.
4. The output of the experiment is defined to be 1 if
x
2
3.
A
is given
n
and
y
as input and outputs
x
:=
A(
n
,
y
≡
y
(
mod
n
)
and 0
otherwise.
