Cryptography Reference
In-Depth Information
1. Each user
U
of the system runs the parameter generation algorithm on security
parameter 1
n
, obtaining as output a pair
(
f
U
,
t
U
)
, where
f
U
is a trapdoor permu-
tation and
t
U
is the associated trapdoor information. The user makes
f
U
public
but keeps
t
U
private.
2. A user wishing to send a message
m
to user
U
computes
c
=
f
U
(
m
)
and sends
it to
U
.
3. Upon receiving the ciphertext
c
,
U
uses the trapdoor information
t
U
to invert
f
U
on
c
and computes
f
−
1
U
f
−
1
U
(
c
)
=
(
f
U
(
m
))
=
m
.
This setup gives a first approximation to the idea of a public-key encryption scheme
but it is far from providing a reasonable measure of security. One reason is that it may
happen that the trapdoor permutation
f
U
is easy to invert on some special messages.
For example, it could happen that, when
m
is taken from the set of sentences in
the English language, then it is easy to recover
m
from
f
U
(
. Moreover, since the
encryption algorithm is deterministic, it will not have indistinguishable encryptions
which, as we shall soon see, can be defined for public-key encryption schemes in a
way similar to the private-key case. Even worse, suppose that only two messages, say
0 and 1 (meaning, for example, “Yes” and “No”, are being encrypted). Since
f
U
is
public, an attacker can easily recover the plaintext given such an encrypted message
simply by computing
f
U
(
m
)
and comparing them with the ciphertext.
Yet another shortcoming of modeling encryption schemes this way is that, even if a
trapdoor permutation prevents the computation of
m
from
f
U
(
0
)
and
f
U
(
1
)
without knowing
the trapdoor, it may well allow the leakage of partial information about
m
.For
example, the parity of
f
U
(
m
)
)
, which is easily computable, gives partial information
about
m
. All these problems derive from the fact that, in this model, encryption
algorithms are deterministic. In order to obtain secure public-key encryption, it will be
necessary to use probabilistic encryption which, together with trapdoor permutations
and their hard-core predicates, will give public-key encryption schemes with security
reductions under reasonable assumptions.
Despite these shortcomings, the concept of public-key encryption scheme can be
approximatelymodeled by the preceding description, making sure that the encryption
algorithms used are probabilistic and adding the requirement of compliance with a
precise definition of security which will be given later.
m
Definition 8.2
A
public-key encryption scheme
, also called an
asymmetric encryp-
tion scheme
, is a 3-tuple
of polynomial-time algorithms such
that
Gen
and
Enc
are probabilistic and
Dec
is deterministic, and satisfy the following
conditions:
E
=
(
Gen
,
Enc
,
Dec
)
The
key generation algorithm
Gen
takes as input a
security parameter
1
n
•
(whose
purpose is to determine the size of the key) and outputs a key
(
pk
,
sk
)
. We denote
1
n
this by
(
pk
,
sk
)
←
Gen
(
)
, where
pk
is the
public key
and
sk
is the
private key
.
•
The
encryption algorithm
Enc
takes as input a public key
pk
and a plaintext
m
(fromamessage spacewhichmay be associatedwith
pk
) and outputs a ciphertext
c
,
written
c
←
Enc
(
pk
,
m
)
.
