Cryptography Reference
In-Depth Information
23.1.1 The KEM/DEM paradigm
Shoup introduced a formalism for public key encryption that has proved to be useful. The
idea is to separate the “public key” part of the system (i.e., the value
c
1
in Box
23.1
)fromthe
“symmetric” part (i.e., (
c
2
,
c
3
)inBox
23.1
). A
key encapsulation mechanism
(or
KEM
)
outputs a public key encryption of a random symmetric key (this functionality is very
similar to
key transport
; the difference being that a KEM generates a fresh random key
as part of the algorithm). A
data encapsulation mechanism
(or
DEM
) is the symmetric
part. The name
hybrid encryption
is used to describe an encryption scheme obtained by
combining a KEM with a DEM.
More formally, a KEM is a triple of three algorithms (KeyGen, Encrypt and Decrypt)
1
that depend on a security parameter
κ
. Instead of a message space, there is space
K
κ
of possible keys to be encapsulated. The randomised algorithm Encrypt takes as input
a public key and outputs a ciphertext
c
and a symmetric key
K
∈
K
κ
(where
κ
is the
security parameter). One says that
c
encapsulates
K
. The Decrypt algorithm for a KEM
takes as input a ciphertext
c
and the private key and outputs a symmetric key
K
(or
⊥
if the decryption fails). The Encrypt algorithm for a DEM takes as input a message and
a symmetric key
K
and outputs a ciphertext. The Decrypt algorithm of a DEM takes a
ciphertext and a symmetric key
K
and outputs either
or a message.
The simplest way to obtain a KEM from Elgamal is given in Box
23.2
.TheDEM
corresponding to the hybrid encryption scheme in Section
23.1
takes as input
m
and
K
,
parses
K
as
K
1
⊥
K
2
, computes
c
2
=
Enc
K
1
(
m
) and
c
3
=
MAC
K
2
(
c
2
) and outputs (
c
2
,
c
3
).
KeyGen
(
κ
): This is the same as standard Elgamal; see Box
23.1
.
=
g
k
and
K
=
kdf
(
h
k
). Return the ciphertext
Encrypt
(h): Choose random 0
≤
k<r
and set
c
c
and the key
K
.
Decrypt
(
c
,a
): Return
⊥
if
c
∈
g
. Otherwise return
kdf
(
c
a
).
Box 23.2
Elgamal KEM
Shoup has defined an analogue of IND-CCA security for a KEM. We refer to Section
7 of Cramer and Shoup [
149
] for precise definitions for KEMs, DEMs and their security
properties, but give an informal statement now.
Definition 23.1.2
An IND-CCA adversary for a KEM is an algorithm
A
that plays the
following game: the input to
A
is a public key. The algorithm
A
can also query a decryption
oracle that will provide decryptions of any ciphertext of its choosing. At some point the
adversary requests a challenge, which is a KEM ciphertext
c
∗
together with a key
K
∗
∈
K
κ
.
The challenger chooses
K
∗
to be either the key corresponding to the ciphertext
c
∗
or
an independently chosen random element of
K
κ
(both cases with probability 1
/
2). The
1
Sometimes the names Encap and Decap are used instead of Encrypt and Decrypt.
