Cryptography Reference
In-Depth Information
3.5.1 Private-Key Encryption Schemes
A private-key encryption scheme is basically the same concept defined in the Intro-
duction but requiring explicitly that the three algorithms involved run in polynomial
time and that, moreover, the key generation algorithm
Gen
is probabilistic and the
encryption algorithm
Enc
may also be probabilistic. Of course, that
Gen
is prob-
abilistic was already implicit in the previous definition which mentioned that keys
were randomly chosen but none of the concrete encryption schemes discussed so far
has a probabilistic encryption algorithm and, in fact, the realization that this condi-
tion is important for the security of the scheme came only around 1984, when [91]
was published.
Recalling that 1
n
denotes a positive integer in unary notation, the definition of
private-key encryption scheme is then the following:
Definition 3.20
A
private-key encryption scheme
, also called a
symmetric encryp-
tion scheme
, is a 3-tuple
E
=
(
Gen
,
Enc
,
Dec
)
of polynomial-time algorithms that
satisfy the following conditions:
Gen
is a probabilistic algorithm that takes as input a
security parameter
1
n
and
outputs a key
k
such that len
•
1
n
(
k
)
≥
n
. We denote this by
k
←
Gen
(
)
(where,
as already remarked, the
notation is used for the output of a probabilistic
algorithm as in [109], whose notational conventions regarding encryption schemes
we generally follow).
←
•
Enc
is either a probabilistic or a deterministic algorithm that takes as input a key
k
and a plaintext
m
and outputs a ciphertext
c
, so that
c
←
Enc
(
k
,
m
)
.
•
Dec
is a deterministic algorithm that takes as input a key
k
and a ciphertext
c
and
outputs a plaintext
m
, which we denote
m
:=
Dec
(
k
,
c
)
(where the notation
:=
is
denoted to point to the output of a deterministic algorithm).
•
For every key
k
output by
Gen
and every plaintext
m
,
Dec
(
k
,
Enc
(
k
,
m
))
=
m
.
1
n
If, for each key
k
output by
Gen
(
)
,
Enc
is only defined for messages of a given
fixed length
(
n
)
, then
E
is said to be a
fixed-length
symmetric encryption scheme.
Remarks 3.6
1. Let us first clarify the meaning of the requirement that
Gen
Enc
and
Dec
are
polynomial-time algorithms.
Gen
takes as input an integer
n
and the requirement
of being a PPT algorithmmeans that its running time is a polynomial function of
n
, since
n
is given in unary. Notice also that, as
n
will usually be equal to len
,
,
this means that
Gen
is polynomial in the length of the output key. On the other
hand, both
Enc
and
Dec
run in time polynomial on the total (binary) length of
their inputs (the key and the plaintext or the ciphertext).
2. In the definition of private-key encryption scheme we have not made explicit
where the plaintexts, ciphertexts, etc., are taken from. We will keep the same
notation used before so the message space will be denoted by
(
k
)
M
, the key space
will be
K
and the ciphertext space
C
. We will also often write
Enc
k
(
m
)
and
Dec
k
(
)
(
,
)
(
,
)
m
instead of
Enc
k
m
and
Dec
k
m
, respectively.
