Cryptography Reference
In-Depth Information
def
=
group mod
N
P
·
Q
. It outputs the sequence
lsb
X
e
2
mod
φ
(
N
)
mod
N
,
lsb
X
e
3
mod
φ
(
N
)
mod
N
,...
lsb(
X
e
lsb(
X
)
,
mod
N
)
,
Z
e
mod
N
.
•
The intractability of factoring Blum integers
: Specifically, we assume that given a prod-
uct of two large primes, each congruent to 3 (mod 4), it is infeasible to retrieve these
primes. The generator is based on the fact that (under this assumption) the least signif-
icant bit constitutes a hard-core predicate for the modular squaring function. We also
use the fact that for such moduli (called Blum integers), modular squaring induces a
permutation over the quadratic residues.
The generator uses the seed in order to select a pair of primes (
P
That is, the function being iterated is
Z
→
,
Q
), each congruent
def
=
to 3
(mod 4), and an element
X
in the multiplicative group mod
N
P
·
Q
. It outputs
the sequence
lsb
X
2
2
mod
φ
(
N
)
mod
N
,
lsb
X
2
3
mod
φ
(
N
)
mod
N
,...
lsb(
X
2
lsb(
X
)
,
mod
N
)
,
Z
2
That is, the function being iterated is
Z
→
mod
N
.
All these suggestions rely on a randomized algorithm for selecting random primes.
Thus, regarding the random bits such an algorithm uses, the fewer the better. Obvious
algorithms for generating
n
-bit-long random primes utilize
O
(
n
3
) random bits (see
Appendix A). We comment that there are procedures that are more randomness-efficient
for generating an
n
-bit-long prime, utilizing only
O
(
n
) random bits.
3.4.3.
∗
Using Hard-Core Functions Rather than Predicates
Construction 3.4.2 (resp., Construction 3.4.4) can be easily generalized to one-way
permutations (resp., collections of one-way permutations) having hard-core functions,
rather than hard-core predicates. The advantage in such constructions is that the number
of bits output by the generator per each application of the one-way permutation is
larger (i.e., greater than 1). We assume familiarity with Section 2.5.3, where hard-core
functions are defined. Next, we present only the generalization of Construction 3.4.4.
Construction 3.4.7:
Let
(
I
,
D
,
F
)
be as in Construction 3.4.4, and suppose that
H is a corresponding hard-core function. Let p
(
·
)
be an arbitrary polynomial.
Fo r n
∈ N
and r
,
s
∈{
0
,
1
}
def
=
I
(1
n
q
(
n
)
, define G
(
r
,
s
)
=
α
1
···
α
p
(
n
)
, where i
,
r
)
,
def
=
s
0
D
(
i
,
s
)
, and for every
1
≤
j
≤
p
(
|
s
|
)
it holds that
α
j
=
H
(
i
,
s
j
−
1
)
and
s
j
=
f
i
(
s
j
−
1
)
.
For a hard-core function
H
, we denote by
H
(
n
) the logarithm to base 2 of the size of
the range of
H
(
i
) for
i
produced by
I
(1
n
). Any hard-core predicate can be viewed
as a hard-core function
H
with
,
·
1. Recall that any one-way function can be
modified to have a hard-core function
H
with
H
(
n
)
=
O
(log
n
) (see Theorem 2.5.6).
Also, assuming that the RSA collection is one-way, the
O
(log
n
) least significant bits
constitute a hard-core function (with
H
(
n
)
=
H
(
n
)
=
O
(log
n
)). The same holds for the Rabin
collection.
