Security of the KEM-DEM Paradigm

Many definitions below are taken verbatim from an upcoming new edition of The Joy of Cryptography.

1 Symmetric-key encryption

Definition 1.1 (Syntax of symmetric-key encryption)

A symmetric-key encryption (SKE) scheme consists of the following algorithms:

$\Enc$ : a (possibly randomized) algorithm that takes a key $\key \in \K$ and plaintext $\ptxt \in \M$ as input, and outputs a ciphertext $\ctxt \in \C$ .
$\Dec$ : a deterministic algorithm that takes a key $\key \in \K$ and ciphertext $\ctxt \in \C$ as input, and outputs a plaintext $\ptxt \in \M$ .

An SKE scheme is correct if encryption and decryption are inverses, in the following sense:

\PR{ \Dec\bigl(\key,\Enc(\key,\ptxt)\bigr) = \ptxt } = 1,

for all $\ptxt \in \M$ and $\key \in \K$ .

Definition 1.2 (Computational one-time secrecy)

An encryption scheme $\Sigma$ has computational one-time secrecy (cOTS) if the following two libraries are indistinguishable:

\lib{ske-ots-real}^\Sigma

\subname{ske.ots.enc}(\ptxt)

\key \gets \Sigma.\K

\ctxt := \Sigma.\Enc(\key,\ptxt)

return

\ctxt

\indist

\lib{ske-ots-rand}^\Sigma

\subname{ske.ots.enc}(\ptxt)

\ctxt \gets \Sigma.\C

return

\ctxt

Note that $\lib{ske-ots-rand}$ does not use any information about $\ptxt$ , even its length! Thus, the definition is suitable when all plaintexts have a known, fixed length.

In particular, we implicitly assume that every SKE performs key generation by sampling uniformly from $\Sigma.\K$ .

2 Public-key encryption

Definition 2.1 (Syntax & correctness of public-key encryption)

A public-key encryption (PKE) scheme consists of the following algorithms:

$\KeyGen$ : a randomized algorithm that takes no inputs (besides the security parameter, which we never write explicitly) and outputs a key pair $(\pk,\sk)$ , where $\pk$ is a public key and $\sk$ is a private key.
$\Enc$ : a randomized algorithm that takes a public key $\pk$ and plaintext $\ptxt \in \M$ as input and returns a ciphertext $\ctxt\in \C$ .
$\Dec$ : a deterministic algorithm that takes a private key $\sk$ and ciphertext $\ctxt\in\C$ as input, and returns a plaintext $\ptxt\in \M$ (or raises an error).

A PKE scheme is correct if the following program outputs $\mytrue$ with probability 1, for all $\ptxt \in \M$ :

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()(PK,SK):=KeyGen()
C:=Enc(PK,M)\ctxt := \Enc(\pk,\ptxt)C:=Enc(PK,M)
return M==Dec(SK,C)\ptxt == \Dec(\sk,\ctxt)M==Dec(SK,C)

Definition 2.2 (CPA security for public-key encryption)

A PKE scheme $\Sigma$ has security against chosen-plaintext attacks (CPA security) if the following two libraries are indistinguishable:

\lib{pke-cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\subname{pke.cpa.pk}(\,)

return

\pk

\subname{pke.cpa.enc}(\ptxt)

\ctxt := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt

\indist

\lib{pke-cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\subname{pke.cpa.pk}(\,)

return

\pk

\subname{pke.cpa.enc}(\ptxt)

\ctxt \gets \Sigma.\C

return

\ctxt

As above, the definition is suitable when plaintexts have a known, fixed length, since $\subname{pke.cpa.enc}$ of $\lib{pke-cpa-rand}$ does not even use the length of $\ptxt$ in its computation.

3 Key encapsulation mechanisms

Definition 3.1 (Key encapsulation mechanism)

A key encapsulation mechanism (KEM) consists of the following algorithms:

$\KeyGen$ : same as in a PKE scheme, a randomized algorithm that takes no inputs and outputs a keypair $(\pk,\sk)$ .
$\Encaps$ : a randomized algorithm that takes only a public key $\pk$ as input and returns both a ciphertext $\ctxt\in \C$ and plaintext $\ptxt\in\M$ .
$\Decaps$ : same as in a PKE scheme, a deterministic algorithm that takes a private key $\sk$ and ciphertext $\ctxt\in\C$ as input, and returns a plaintext $\ptxt\in \M$ (or raises an error).

A KEM is correct if the following process outputs $\mytrue$ with probability 1:

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()(PK,SK):=KeyGen()
(C,M):=Encaps(PK)(\ctxt, \ptxt) := \Encaps(\pk)(C,M):=Encaps(PK)
M′:=Decaps(SK,C)\ptxt' := \Decaps(\sk,\ctxt)M′:=Decaps(SK,C)
return M==M′\ptxt == \ptxt'M==M′

Definition 3.2 (CPA security for key encapsulation)

A KEM $\Sigma$ has security against chosen-plaintext attacks (CPA security) if the following two libraries are indistinguishable:

\lib{kem-cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\subname{kem.cpa.pk}(\,)

return

\pk

\subname{kem.cpa.enc}(\,)

return

\Sigma.\Encaps(\pk)

\indist

\lib{kem-cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\subname{kem.cpa.pk}(\,)

return

\pk

\subname{kem.cpa.enc}(\,)

\ctxt \gets \Sigma.\C

\ptxt \gets \Sigma.\M

return

(\ctxt, \ptxt)

4 Hybrid encryption

Construction 4.1 (Hybrid encryption)

Let $\textsf{KEM}$ be a KEM scheme and $\textsf{DEM}$ be a SKE scheme, such that $\textsf{KEM}.\M = \textsf{DEM}.\K$ (i.e., $\textsf{KEM}$ payloads can be interepreted as keys in $\textsf{DEM}$ ). Then hybrid encryption $\textsf{Hyb} = \textsf{Hyb}[\textsf{KEM},\textsf{DEM}]$ is defined by the following algorithms:

\begin{aligned} \textsf{Hyb}.\K &= \textsf{KEM}.\K \\ \textsf{Hyb}.\M &= \textsf{DEM}.\M \\ \textsf{Hyb}.\C &= \textsf{KEM}.\C \times \textsf{DEM}.\C \\[8pt] \textsf{Hyb}.\KeyGen &= \textsf{KEM}.\KeyGen \end{aligned}

\textsf{Hyb}.\Enc(\pk,\ptxt)

(\ctxt_{\text{kem}}, K) \gets \textsf{KEM}.\Encaps(\pk)

\ctxt_{\text{dem}} \gets \textsf{DEM}.\Enc(\key,\ptxt)

return

(\ctxt_{\text{kem}}, \ctxt_{\text{dem}})

\textsf{Hyb}.\Dec(\sk,(\ctxt_{\text{kem}},\ctxt_{\text{dem}}))

\key := \textsf{KEM}.\Decaps(\sk,\ctxt_{\text{kem}})

\key == \bot

: return

\bot

return

\textsf{DEM}.\Dec(\key,\ctxt_{\text{dem}})

Claim 4.2 (Security of hybrid encryption)

If $\textsf{KEM}$ is a CPA-secure KEM and $\textsf{DEM}$ is a computational one-time secret (cOTS) SKE, then the hybrid encryption scheme $\textsf{Hyb} = \textsf{Hyb}[\textsf{KEM},\textsf{DEM}]$ is a CPA-secure PKE.

Proof:

Hybrid Sequence:

[ [ ['4','add','hl'], ['5','add','hl'], ['11','add','hl'], ['155','add','hl'], ['37','remove','slide-up'], ['15','add','slide-down'] ], [ ['168','add','hl'], ['168','remove','slide-left'], ['19','add','hl'], ['19','remove','hidden'], ['156','add','hl'], ['156','remove','slide-left'], ['157-slide','remove','slide-left'], ['3','add','hidden'], ['4','remove','hl'], ['4','add','hidden'], ['5','remove','hl'], ['5','add','hidden'], ['11','remove','hl'], ['11','add','hidden'], ['155','remove','hl'], ['155','add','slide-right'] ], [ ['168','remove','hl'], ['19','remove','hl'], ['156','remove','hl'] ], [ ['157-flip','add','flipped'], ['61','remove','slide-up'], ['37','add','slide-down'] ], [ ['168','add','hl'], ['19','add','hl'], ['12','add','hl'], ['161','add','hl'], ['75','remove','slide-up'], ['61','add','slide-down'] ], [ ['5','add','hl'], ['5','remove','hidden'], ['155','add','hl'], ['155','remove','slide-right'], ['71','add','hl'], ['71','remove','hidden'], ['72','add','hl'], ['72','remove','hidden'], ['168','remove','hl'], ['168','add','slide-left'], ['19','remove','hl'], ['19','add','hidden'], ['12','remove','hl'], ['12','add','hidden'], ['161','remove','hl'], ['161','add','slide-left'], ['157-slide','add','slide-left'] ], [ ['5','remove','hl'], ['155','remove','hl'], ['71','remove','hl'], ['72','remove','hl'], ['160','add','hl'], ['89','remove','slide-up'], ['75','add','slide-down'] ], [ ['161','add','hl'], ['161','remove','slide-left'], ['160','remove','hl'], ['160','add','slide-right'] ], [ ['161','remove','hl'], ['72','add','hl'], ['163','add','hl'], ['108','remove','slide-up'], ['89','add','slide-down'] ], [ ['160','add','hl'], ['160','remove','slide-right'], ['164','add','hl'], ['164','remove','slide-left'], ['165-slide','remove','slide-left'], ['72','remove','hl'], ['72','add','hidden'], ['163','remove','hl'], ['163','add','slide-right'] ], [ ['160','remove','hl'], ['164','remove','hl'] ], [ ['165-flip','add','flipped'], ['126','remove','slide-up'], ['108','add','slide-down'] ], [ ['164','add','hl'], ['139','remove','slide-up'], ['126','add','slide-down'] ], [ ['166','add','hl'], ['166','remove','slide-right'], ['164','remove','hl'], ['164','add','slide-left'], ['165-slide','add','slide-left'] ], [ ['166','remove','hl'], ['167','add','hl'], ['71','add','hl'], ['13','add','hl'], ['152','remove','slide-up'], ['139','add','slide-down'] ], [ ['143','remove','hidden'], ['168','add','hl'], ['168','remove','slide-left'], ['163','add','hl'], ['163','remove','slide-right'], ['164','add','hl'], ['164','remove','slide-left'], ['150','add','hl'], ['150','remove','hidden'], ['167','remove','hl'], ['167','add','slide-right'], ['71','remove','hl'], ['71','add','hidden'], ['13','remove','hl'], ['13','add','hidden'] ], [ ['168','remove','hl'], ['163','remove','hl'], ['164','remove','hl'], ['150','remove','hl'] ] ]

The starting point is

\lib{pke-cpa-real}^{\textsf{Hyb}}

Rewrite in a logically equivalent way so that an instance of

\lib{kem-cpa-real}^{\textsf{KEM}}

appears.

\textsf{KEM}

is CPA-secure, so

\lib{kem-cpa-real}^{\textsf{KEM}}

can be replaced by

\lib{kem-cpa-rand}^{\textsf{KEM}}

with only negligible effect on the calling program.

Inline the instance of

\lib{kem-cpa-rand}^{\textsf{KEM}}

By our assumption,

\textsf{KEM}.\M = \textsf{DEM}.\K

Rewrite in a logically eqivalent way, so that an instance of

\lib{ske-ots-real}^{\textsf{DEM}}

appears.

\textsf{DEM}

has cOTS security, so

\lib{ske-ots-real}^{\textsf{DEM}}

can be replaced by

\lib{ske-ots-rand}^{\textsf{DEM}}

with only negligible effect on the calling program.

Inline the instance of

\lib{ske-ots-rand}^{\textsf{DEM}}

What remains is exactly

\lib{pke-cpa-rand}^{\textsf{Hyb}}

, after suitably renaming things.

\lib{pke-cpa-real}^{\textsf{Hyb}}

\textsf{Hyb}.\KeyGen()

(\pk,\sk) := {}

\textsf{KEM}.\KeyGen()

\textsf{Hyb}.\KeyGen()

pke.cpa.pk( ):

return

\pk

pke.cpa.enc(

\ptxt

\textsf{Hyb}.\Enc(\pk,\ptxt)

(\ctxt_{\text{kem}}, K)

{}\gets \textsf{KEM}.\Encaps(\pk)

{}:= \subname{kem.cpa.enc}()

\ctxt_{\text{dem}}

{}\gets \textsf{DEM}.\Enc(\key,\ptxt)

{}:= \subname{ske.ots.enc}(\ptxt)

{}\gets \textsf{DEM}.\C

return

(\ctxt_{\text{kem}}, \ctxt_{\text{dem}})

\link

\lib{kem-cpa-real}^{\textsf{KEM}}

(\pk,\sk) := \textsf{KEM}.\KeyGen()

kem.cpa.pk( ):

return

\pk

kem.cpa.enc( ):

return

\textsf{KEM}.\Encaps(\pk)

\lib{kem-cpa-rand}^{\textsf{KEM}}

(\pk,\sk) := \textsf{KEM}.\KeyGen()

pke.cpa.pk( ):

return

\pk

kem.cpa.enc( ):

\ctxt \gets \textsf{KEM}.\C

\ptxt \gets \textsf{KEM}.\M

return

(\ctxt, \ptxt)

\link

\lib{ske-ots-real}^{\textsf{DEM}}

ske.ots.enc(

\ptxt

\key \gets \textsf{DEM}.\K

\ctxt := \textsf{DEM}.\Enc(\key,\ptxt)

return

\ctxt

\lib{ske-ots-rand}^{\textsf{DEM}}

ske.ots.enc(

\ptxt

\ctxt \gets \textsf{DEM}.\C

return

\ctxt

Security of the KEM-DEM Paradigm

Chapter Contents

1 Symmetric-key encryption

2 Public-key encryption

3 Key encapsulation mechanisms

4 Hybrid encryption