Cryptography Reference
In-Depth Information
of this cyclic group), and outputs (
P
,
G
). There exists a probabilistic polynomial-
time algorithm for uniformly generating primes, together with the prime factorization
of
P
1, where
P
is the prime generated (see Appendix A). Alternatively, one can
uniformly generate a prime
P
of the form 2
Q
−
1, where
Q
is also a prime. (In the
latter case, however, one has to assume the intractability of DLP with respect to such
primes. We remark that such primes are commonly believed to be the hardest for
DLP.) Using the factorization of
P
+
1, we can find a primitive element by selecting
an element of the group at random and checking whether or not it has order
P
−
−
1
(by raising the candidate to powers that non-trivially divide
P
−
1, and comparing the
result to 1).
Regarding algorithm
D
DLP
, on input (
P
G
) it selects uniformly a residue modulo
P
−
1. Algorithm
F
DLP
, on input ((
P
,
G
)
,
x
), outputs
DLP
P
,
G
(
x
)
def
,
=
G
x
mod
P
(2.12)
Hence, inverting DLP
P
,
G
amounts to extracting the discrete logarithm (to base
G
)
modulo
P
. For every (
P
G
) of the foregoing form, the function DLP
P
,
G
induces a 1-1
and onto mapping from the additive group mod
P
,
−
1 to the multiplicative group mod
.
Exponentiation in other groups is also a reasonable candidate for a one-way function,
provided that the discrete-logarithm problem for the group is believed to be hard. For
example, it is believed that the logarithm problem is hard in the group of points on an
elliptic curve.
P
. Hence, DLP
P
,
G
induces a permutation on the set
{
1
,...,
P
−
1
}
2.4.4. Trapdoor One-Way Permutations
We shall define trapdoor (one-way) permutations and review a popular candidate (i.e.,
the RSA).
2.4.4.1. Definitions
The formulation of collections of one-way functions is convenient as a starting point
to the definition of trapdoor permutations. Loosely speaking, these are collections of
one-way permutations,
, with the extra property that
f
i
is efficiently inverted once
it is given as auxiliary input a “trapdoor” for the index
i
. The trapdoor for index
i
,
denoted by
t
(
i
),
cannot
be efficiently computed from
i
, yet one can efficiently generate
corresponding pairs (
i
{
f
i
}
,
t
(
i
)).
Definition 2.4.4 (Collection of Trapdoor Permutations):
Let I
:1
∗
→{
0
,
1
}
∗
×
{
}
∗
be a probabilistic algorithm, and let I
1
(1
n
)
denote the first element of the
pair output by I
(1
n
)
. A triple of algorithms,
(
I
,
D
,
F
)
, is called a
collection of
strong (resp., weak) trapdoor permutations
if the following two conditions
hold:
0
,
1
1.
The algorithms induce a collection of one-way permutations:
The triple
(
I
1
,
D
,
F
)
constitutes a collection of strong
(
resp., weak
)
one-way permutations.
(
Recall that, in particular, F
(
i
,
x
)
=
f
i
(
x
)
.
)
