Cryptography Reference
In-Depth Information
Definition 2.4.6 (Claw-Free Collection): A collection of pairs of functions
consists of an infinite set of indices, denoted I , two finite sets D
i
and D
i
for each
i
I , and two functions f
i
and f
i
defined over D
i
and D
i
, respectively. Such
a collection is called
claw-free
if there exist three probabilistic polynomial-time
algorithms I , D, and F such that the following conditions hold:
∈
1.
Easy to sample and compute:
The random variable I
(1
n
)
is assigned values in
the set I
I and
n
. For each i
∩{
0
,
1
}
∈
σ
∈{
0
,
1
}
, the random variable D
(
σ,
i
)
is
D
i
.
2.
Identical range distribution:
For every i in the index set I , the random variables
f
i
distributed over D
i
, and F
(
σ,
,
=
f
i
(
x
)
for each x
∈
i
x
)
i
))
are identically distributed.
3.
Hard to form claws:
A pair
(
x
(
D
(0
,
i
))
and f
i
(
D
(1
,
f
i
(
y
)
is called a
claw
for
index i . Let C
i
denote the set of claws for index i . It is required that for every
probabilistic polynomial-time algorithm A
, every positive polynomial p
(
y
)
satisfying f
i
(
x
)
,
=
·
)
, and
all sufficiently large n's,
1
p
(
n
)
where I
n
is a random variable describing the output distribution of algorithm I
on input
1
n
.
[
A
(
I
n
)
Pr
∈
C
I
n
]
<
The first requirement in Definition 2.4.6 is analogous to what appears in Definition 2.4.3.
The other two requirements in Definition 2.4.6 are conflicting in nature. On one hand, it
is required that claws do exist (to say the least), whereas on the other hand it is required
that claws cannot be efficiently found. Clearly, a claw-free collection of functions yields
a collection of strong one-way functions (see Exercise 22). A case of special interest
arises when the two domains are identical (i.e.,
D
i
def
=
D
i
=
D
i
), the random variable
σ,
i
) is uniformly distributed over
D
i
, and the functions
f
i
and
f
i
are permutations
over
D
i
. Such a collection is called a
collection of claw-free pairs of permutations
.
Again, a useful relaxation of the conditions of Definition 2.4.6 is obtained by allow-
ing the algorithms (i.e.,
I
,
D
, and
F
) to fail with negligible probability. An additional
property that a (claw-free) collection may (or may not) have is an efficiently recogniz-
able index set (i.e., a probabilistic polynomial-time algorithm for determining whether
or not a given string is in
I
).
D
(
2.4.5.2. The DLP Claw-Free Collection
We now seek to show that claw-free collections do exist under specific reasonable in-
tractability assumptions. We start by presenting such a collection under the assumption
that the discrete-logarithm problem (DLP) for fields of prime cardinality is intractable.
Following is the description of a collection of claw-free pairs of
permutations
(based
on the foregoing assumption). The index set consists of triples, (
P
,
G
,
Z
), where
P
is a
prime,
G
is a primitive element mod
P
, and
Z
is an element in the field (of residues mod
P
). The index-sampling algorithm selects
P
and
G
as in the DLP collection presented
in Section 2.4.3, and
Z
is selected uniformly among the residues mod
P
. The domain
is the same for both functions with index (
P
,
G
,
Z
) and equals the set
{
1
,...,
P
−
1
}
,
