Cryptography Reference
In-Depth Information
/
before finding a given one, and the relation between
n
2 and log
b
n
is, of course,
exponential.
More relevant examples can be found in algorithmic number theory: as we have
seen when studying the integer factorization problem, the function
y
,
where
x
and
y
are primes of the same length, is easy to compute but the primes are
difficult to recover from their product using known algorithms. Similarly, while it
is usually easy to compute
y
(
x
,
y
)
→
x
·
g
a
given an element
g
of a group
G
and a positive
integer
a
, computing
a
given
g
and
y
is believed to be hard in general. These difficult
computational problems lead to the concept of one-way function which, as we have
already seen, is also crucial for private-key cryptography (a fact that was not known
in the mid-1970s) and one of the basic ideas of Diffie and Hellman was to construct
encryption schemes for which the encryption functions were one-way functions, so
that encrypting would be “easy” but decrypting would be “difficult”.
It is readily apparent, however, that one-way functions are not really sufficient
for this purpose, because then decryption would be difficult even for legitimate users
of the scheme, which is clearly undesirable. To overcome this difficulty, Diffie and
Hellman realized that a stronger concept was necessary, namely, a one-way function
which has a
trapdoor
, i.e., secret information whose knowledge permits efficient
inversion of the function. The idea was then to use as encryption functions a family
of trapdoor permutations, i.e., a family of one-way permutations (see Definition 3.10)
for which the parameter-generation algorithm outputs a trapdoor enabling efficient
inversion of the functions in the family:
=
Definition 8.1
A family of permutations
D
i
}
i
∈
I
, where
I
is a set and
D
i
a finite set, is
trapdoor one-way
(or simply
trapdoor
as the one-way property is
understood) if the following conditions hold:
1. There exists a PPT algorithm
Gen
which takes as input a security parameter 1
n
and outputs a pair
{
f
i
:
D
i
→
(
i
,
t
i
)
such that
i
∈
I
satisfies len
(
i
)
≥
n
and
t
i
is the
trapdoor
of
i
.
2. There exists a PPT algorithm
Samp
which, on input
i
∈
I
, outputs (with uniform
).
3. There exists a deterministic polynomial-time evaluation algorithm
Eval
which,
on input
i
distribution)
x
←
D
i
(except possibly with probability negligible in len
(
i
)
.
4. There exists a deterministic polynomial-time inverting algorithm
Inv
that, on
input
i
,
t
i
and
f
i
(
∈
I
and
x
∈
D
i
, outputs
f
i
(
x
)
x
)
, outputs
x
:=
Inv
(
i
,
t
i
,
f
i
(
x
))
, for all
i
∈
I
and
x
∈
D
i
(that is,
f
i
is easy to invert once the trapdoor information
t
i
is known).
5. For every PPT algorithm
A
, there exists a negligible function
negl
such that,
1
n
for
i
obtained from
(
i
,
t
i
)
←
Gen
(
)
,
x
←
Samp
(
i
)
, and the randomcoins of
A
:
pr
(A(
f
i
(
x
))
=
x
)
≤
negl
(
n
).
The idea then was to use a family of trapdoor permutations to build an encryption
scheme more or less as follows:
