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\Enc: a (possibly randomized) algorithm that takes a key K∈K\key \in \K and plaintext M∈M\ptxt \in \M as input, and outputs a ciphertext C∈C\ctxt \in \C.

  • Dec\Dec: a deterministic algorithm that takes a key K∈K\key \in \K and ciphertext C∈C\ctxt \in \C as input, and outputs a plaintext M∈M\ptxt \in \M.

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

Pr⁡[ Dec(K,Enc(K,M))=M ]=1, \PR{ \Dec\bigl(\key,\Enc(\key,\ptxt)\bigr) = \ptxt } = 1,

for all M∈M\ptxt \in \M and K∈K\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:

Lske-ots-leftΣ\lib{ske-ots-left}^\Sigma
ske.ots.enc(ML,MR)\subname{ske.ots.enc}(\ptxt_L, \ptxt_R):
K↞Σ.K\key \gets \Sigma.\K
C:=Σ.Enc(K,ML)\ctxt := \Sigma.\Enc(\key,\hl{\ptxt_L})
return C\ctxt
≊\indist
Lske-ots-rightΣ\lib{ske-ots-right}^\Sigma
ske.ots.enc(ML,MR)\subname{ske.ots.enc}(\ptxt_L, \ptxt_R):
K↞Σ.K\key \gets \Sigma.\K
C:=Σ.Enc(K,MR)\ctxt := \Sigma.\Enc(\key,\hl{\ptxt_R})
return C\ctxt

Note that Lske-ots-rand\lib{ske-ots-rand} makes no restriction about the lengths of ML\ptxt_L and MR\ptxt_R. 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 Σ.K\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\KeyGen: a randomized algorithm that takes no inputs (besides the security parameter, which we never write explicitly) and outputs a key pair (PK,SK)(\pk,\sk), where PK\pk is a public key and SK\sk is a private key.

  • Enc\Enc: a randomized algorithm that takes a public key PK\pk and plaintext M∈M\ptxt \in \M as input and returns a ciphertext C∈C\ctxt\in \C.

  • Dec\Dec: a deterministic algorithm that takes a private key SK\sk and ciphertext C∈C\ctxt\in\C as input, and returns a plaintext M∈M\ptxt\in \M (or raises an error).

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

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()
C:=Enc(PK,M)\ctxt := \Enc(\pk,\ptxt)
return M==Dec(SK,C)\ptxt == \Dec(\sk,\ctxt)
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:

Lpke-cpa-leftΣ\lib{pke-cpa-left}^\Sigma
(PK,SK):=Σ.KeyGen()(\pk,\sk) := \Sigma.\KeyGen()
pke.cpa.pk( )\subname{pke.cpa.pk}(\,):
return PK\pk
pke.cpa.enc(ML,MR)\subname{pke.cpa.enc}(\ptxt_L, \ptxt_R):
C:=Σ.Enc(PK,ML)\ctxt := \Sigma.\Enc(\pk, \hl{\ptxt_L})
return C\ctxt
≊\indist
Lpke-cpa-rightΣ\lib{pke-cpa-right}^\Sigma
(PK,SK):=Σ.KeyGen()(\pk,\sk) := \Sigma.\KeyGen()
pke.cpa.pk( )\subname{pke.cpa.pk}(\,):
return PK\pk
pke.cpa.enc(ML,MR)\subname{pke.cpa.enc}(\ptxt_L, \ptxt_R):
C:=Σ.Enc(PK,MR)\ctxt := \Sigma.\Enc(\pk, \hl{\ptxt_R})
return C\ctxt

As above, the definition is suitable when plaintexts have a known, fixed length, since pke.cpa.enc\subname{pke.cpa.enc} of Lpke-cpa-rand\lib{pke-cpa-rand} does not restrict the lengths of ML\ptxt_L and MR\ptxt_R.

3 Key encapsulation mechanisms

Definition 3.1 (Key encapsulation mechanism)

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

  • KeyGen\KeyGen: same as in a PKE scheme, a randomized algorithm that takes no inputs and outputs a keypair (PK,SK)(\pk,\sk).

  • Encaps\Encaps: a randomized algorithm that takes only a public key PK\pk as input and returns both a ciphertext C∈C\ctxt\in \C and plaintext M∈M\ptxt\in\M.

  • Decaps\Decaps: same as in a PKE scheme, a deterministic algorithm that takes a private key SK\sk and ciphertext C∈C\ctxt\in\C as input, and returns a plaintext M∈M\ptxt\in \M (or raises an error).

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

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()
(C,M):=Encaps(PK)(\ctxt, \ptxt) := \Encaps(\pk)
M′:=Decaps(SK,C)\ptxt' := \Decaps(\sk,\ctxt)
return M==M′\ptxt == \ptxt'
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:

Lkem-cpa-realΣ\lib{kem-cpa-real}^\Sigma
(PK,SK):=Σ.KeyGen()(\pk,\sk) := \Sigma.\KeyGen()
kem.cpa.pk( )\subname{kem.cpa.pk}(\,):
return PK\pk
kem.cpa.enc( )\subname{kem.cpa.enc}(\,):
(C,M):=Σ.Encaps(PK)(\ctxt,\ptxt) := \Sigma.\Encaps(\pk)
return (C,M)(\ctxt, \ptxt)
≊\indist
Lkem-cpa-idealΣ\lib{kem-cpa-ideal}^\Sigma
(PK,SK):=Σ.KeyGen()(\pk,\sk) := \Sigma.\KeyGen()
kem.cpa.pk( )\subname{kem.cpa.pk}(\,):
return PK\pk
kem.cpa.enc( )\subname{kem.cpa.enc}(\,):
(C,−):=Σ.Encaps(PK)(\ctxt,-) := \Sigma.\Encaps(\pk)
M↞Σ.M\ptxt \gets \Sigma.\M
return (C,M)(\ctxt, \ptxt)

4 Hybrid encryption

Construction 4.1 (Hybrid encryption)

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

Hyb.K=KEM.KHyb.M=DEM.MHyb.C=KEM.C×DEM.CHyb.KeyGen=KEM.KeyGen\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}
Hyb.Enc(PK,M)\textsf{Hyb}.\Enc(\pk,\ptxt):
(Ckem,K)↞KEM.Encaps(PK)(\ctxt_{\text{kem}}, K) \gets \textsf{KEM}.\Encaps(\pk)
Cdem↞DEM.Enc(K,M)\ctxt_{\text{dem}} \gets \textsf{DEM}.\Enc(\key,\ptxt)
return (Ckem,Cdem)(\ctxt_{\text{kem}}, \ctxt_{\text{dem}})
Hyb.Dec(SK,(Ckem,Cdem))\textsf{Hyb}.\Dec(\sk,(\ctxt_{\text{kem}},\ctxt_{\text{dem}})):
K:=KEM.Decaps(SK,Ckem)\key := \textsf{KEM}.\Decaps(\sk,\ctxt_{\text{kem}})
if K==⊥\key == \bot: return ⊥\bot
return DEM.Dec(K,Cdem)\textsf{DEM}.\Dec(\key,\ctxt_{\text{dem}})
Claim 4.2 (Security of hybrid encryption)

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

Proof:

Hybrid Sequence:
The starting point is Lpke-cpa-leftHyb\lib{pke-cpa-left}^{\textsf{Hyb}}.
Rewrite in a logically equivalent way so that an instance of Lkem-cpa-realKEM\lib{kem-cpa-real}^{\textsf{KEM}} appears.
KEM\textsf{KEM} is CPA-secure, so Lkem-cpa-realKEM\lib{kem-cpa-real}^{\textsf{KEM}} can be replaced by Lkem-cpa-idealKEM\lib{kem-cpa-ideal}^{\textsf{KEM}} with only negligible effect on the calling program.
Inline the instance of Lkem-cpa-idealKEM\lib{kem-cpa-ideal}^{\textsf{KEM}}.
By our assumption, KEM.M=DEM.K\textsf{KEM}.\M = \textsf{DEM}.\K.
Rewrite in a logically eqivalent way, so that an instance of Lske-ots-leftDEM\lib{ske-ots-left}^{\textsf{DEM}} appears.
DEM\textsf{DEM} has cOTS security, so Lske-ots-leftDEM\lib{ske-ots-left}^{\textsf{DEM}} can be replaced by Lske-ots-rightDEM\lib{ske-ots-right}^{\textsf{DEM}} with only negligible effect on the calling program.
Inline the instance of Lske-ots-rightDEM\lib{ske-ots-right}^{\textsf{DEM}}.
The next few steps are identical to some previous steps, but taken in reverse order.
What remains is exactly Lpke-cpa-rightHyb\lib{pke-cpa-right}^{\textsf{Hyb}}.
Lpke-cpa-leftHyb\lib{pke-cpa-left}^{\textsf{Hyb}}
// Hyb.KeyGen()\textsf{Hyb}.\KeyGen():
(PK,SK):=KEM.KeyGen()(\pk,\sk) := \textsf{KEM}.\KeyGen()
pke.cpa.pk( ):
return PK\pk
pke.cpa.enc(ML,MR\ptxt_L, \ptxt_R):
// Hyb.Enc(PK,\textsf{Hyb}.\Enc(\pk, {}
ML)\ptxt_L):
MR)\ptxt_R):
(Ckem,K)(\ctxt_{\text{kem}}, K)
↞KEM.Encaps(PK){}\gets \textsf{KEM}.\Encaps(\pk)
:=kem.cpa.enc(){}:= \subname{kem.cpa.enc}()
Cdem\ctxt_{\text{dem}}
↞DEM.Enc(K,ML){}\gets \textsf{DEM}.\Enc(\key,\ptxt_L)
:={}:= {}
ske.ots.enc(ML,MR)\subname{ske.ots.enc}(\ptxt_L, \ptxt_R)
DEM.Enc(K,MR)\textsf{DEM}.\Enc(\key,\ptxt_R)
return (Ckem,Cdem)(\ctxt_{\text{kem}}, \ctxt_{\text{dem}})
⋄\link
Lkem-cpa-realKEM\lib{kem-cpa-real}^{\textsf{KEM}}
(PK,SK):=KEM.KeyGen()(\pk,\sk) := \textsf{KEM}.\KeyGen()
kem.cpa.pk( ):
return PK\pk
kem.cpa.enc( ):
(C,M):=KEM.Encaps(PK)(\ctxt, \ptxt) := \textsf{KEM}.\Encaps(\pk)
return (C,M)(\ctxt,\ptxt)
Lkem-cpa-idealKEM\lib{kem-cpa-ideal}^{\textsf{KEM}}
(PK,SK):=KEM.KeyGen()(\pk,\sk) := \textsf{KEM}.\KeyGen()
pke.cpa.pk( ):
return PK\pk
kem.cpa.enc( ):
(C,−):=KEM.Encaps(PK)(\ctxt, -) := \textsf{KEM}.\Encaps(\pk)
M↞KEM.M\ptxt \gets \textsf{KEM}.\M
return (C,M)(\ctxt,\ptxt)
⋄\link
Lske-ots-leftDEM\lib{ske-ots-left}^{\textsf{DEM}}
ske.ots.enc(ML,MR\ptxt_L, \ptxt_R):
K↞DEM.K\key \gets \textsf{DEM}.\K
C:=DEM.Enc(K,ML)\ctxt := \textsf{DEM}.\Enc(\key,\ptxt_L)
return C\ctxt
Lske-ots-rightDEM\lib{ske-ots-right}^{\textsf{DEM}}
ske.ots.enc(ML,MR\ptxt_L, \ptxt_R):
K↞DEM.K\key \gets \textsf{DEM}.\K
C:=DEM.Enc(K,MR)\ctxt := \textsf{DEM}.\Enc(\key,\ptxt_R)
return C\ctxt
⋄\link
Lkem-cpa-idealKEM\lib{kem-cpa-ideal}^{\textsf{KEM}}
(PK,SK):=KEM.KeyGen()(\pk,\sk) := \textsf{KEM}.\KeyGen ()
pke.cpa.pk( ):
return PK\pk
kem.cpa.enc( ):
(C,−):=KEM.Encaps(PK)(\ctxt, -) := \textsf{KEM}.\Encaps(\pk)
M↞KEM.M\ptxt \gets \textsf{KEM}.\M
return (C,M)(\ctxt,\ptxt)
Lkem-cpa-realKEM\lib{kem-cpa-real}^{\textsf{KEM}}
(PK,SK):=KEM.KeyGen()(\pk,\sk) := \textsf{KEM}.\KeyGen ()
pke.cpa.pk( ):
return PK\pk
kem.cpa.enc( ):
(C,M):=KEM.Encaps(PK)(\ctxt, \ptxt) := \textsf{KEM}.\Encaps(\pk)
return (C,M)(\ctxt,\ptxt)