Generic CCA Secure Key Homomorphic KEM and Updatable Public Key Encryption

Abstract

Updatable Public Key Encryption (UPKE) is a technique for updating public and private keys in secure messaging protocols, which was initially introduced by Jost et al. (EUROCRYPTO ’19). Alwen et al. (CRYPTO ’20) later provided an IND-CPA secure UPKE. Asano et al., in turn, applied the FO transformation to UPKE outputs to achieve IND-CCA security. However, their approach doubles the time complexity, as they treat the IND-CPA UPKE as a black box that runs the encryption process once. In this paper, we formalize an IND-CCA model for key encapsulation mechanisms that involve a one-way homomorphic function which is named key homomorphism (KhKEM). If we construct a UPKE scheme from an IND-CCA KhKEM, a one-way secure pseudorandom generator, and an IND-CCA Encrypt-then-MAC symmetric encryption scheme, we demonstrate that this generic hybrid UPKE design will be IND-CCA secure. We finally consider three KhKEM instances and discuss the parameters and efficiency. We show that our scheme has better efficiency compared with Asano et al.’s scheme.

Proof for Theorem 2

Proof

In the IND-CU-CCA attack game of our UPKE, let $((c_{t}^{SE},\tau _{t}),c_{t}^{KEM})$ be the challenge value in Chal phase, t is the epoch when Chal is executed, i.e. $t:=q_{SD_1}+q_{UP_1}$, let $seed'$ be the seed chosen in Comp phase, $(upk_{l},upd_{l}:=((c_{l}^{SE},\tau _{l}),c_{l}^{KEM}),usk_{l})$ be the compromised value for epoch l that $l-1$ is the epoch to execute Comp i.e. $l:=t+q_{SD_2}+q_{UP_2}+1$. Let $\mathcal {G}_i$ be the games played between the PPT adversary $\mathcal {A}$ and the challenger $\mathcal {C}$, $\Pr [\mathcal {W}_i]$ be the probability for $\mathcal {A}$ to win $\mathcal {G}_i$ where $i\in \{0,1,2,3,4,5,6\}$. The details of each game are as follows:

• $\mathcal {G}_0:$ It is the original IND-CU-CCA game. There is:

$$\begin{aligned} \Pr [\mathcal {W}_0]=Adv_{\prod _{UPKE}}^{IND-CU-CCA}(\mathcal {A},\lambda ). \end{aligned}$$

(10)

• $\mathcal {G}_1:$ It is the same as $\mathcal {G}_0$ except that instead of generating $upk_0$ and $usk_0$ by $\mathcal {C}$, $upk_0$ is received from an IND-CCA-KH challenger $\mathcal {C}_{KEM}$. $\mathcal {C}$ initiates a value $sum_{i+1}$ with empty symbol $\bot$ to accumulate each update value $sk_{i+1}^{UP}$ for next epoch $i+1$. That is, $sum_{0}=\bot$. In this situation, $\mathcal {C}$ does not have the $usk_0$. The responses to these queries and phases should be described as follows:

  • Plaintext Query: Because this oracle does not involve anything about the private key $usk_i$, $\mathcal {C}$ can reply to $\mathcal {A}$ by running UEnc.

  • Ciphertext Query: It is the same as the one in $\mathcal {G}_0$, except that instead running the Decap in UDec, $\mathcal {C}$ queries Decap from $\mathcal {C}_{KEM}$ on the input of $c_{KEM},sum_i$.

  • Seed Query: It is the same as the one in $\mathcal {G}_0$, except that in epoch $i+1$, $\mathcal {C}$ set $sum_{i+1}:=sum_{i}\otimes sk_{i+1}^{UP}$. If $i=0$, $sum_{i+1}:= sk_{i+1}^{UP}$.

  • Update Query: It is the same as the one in $\mathcal {G}_0$, instead running the Decap in UpSk, $\mathcal {C}$ queries Decap from $\mathcal {C}_{KEM}$ on the input of $c_{KEM},sum_i$. When the epoch i moves to $i+1$, $\mathcal {C}$ set $sum_{i+1}:=sum_{i}\otimes sk_{i+1}^{UP}$. If $i=0$, $sum_{i+1}:= sk_{i+1}^{UP}$.

  • Comp: $\mathcal {C}$ does not know $usk_0$, but for Comp, we just need to ensure that $upk_{l}$ and $usk_{l}$ are a valid key pair i.e. they satisfy the correctness and key-homomorphism of KEM. It can be found that $\mathcal {A}$ has no knowledge of $sk_{l}^{UP}$, so $\mathcal {C}$ runs as follows:

    • $seed'\leftarrow \$\mathcal {S}\mathcal {D}$, $sk_{l}^{UP}\leftarrow {\textbf {G}}_0(seed')$.

    • $(upk_{l}',usk_l')\leftarrow UGen(1^\lambda )$ instead of $upk_l:=upk_{l-1}\odot {\textbf {GetPk}}(sk_{l}^{UP})$ and $usk_l:=usk_{l-1}\otimes sk_{l}^{UP}$.

    • $(c_{KEM},\textbf{k}_{KEM})\leftarrow \prod _{KEM}.{\textbf {Encap}}(upk_{l-1};sk_{l}^{UP})$.

    • $\textbf{k}_{SE}\leftarrow {\textbf {G}}_1(\textbf{k}_{KEM}), \textbf{k}_{MAC}\leftarrow {\textbf {G}}_2(\textbf{k}_{KEM})$.

    • $c_{UP}\leftarrow \prod _{EtM}.{\textbf {HEnc}}((\textbf{k}_{SE},\textbf{k}_{MAC}),sk_{l}^{UP};(c_{KEM},upk_{l}'))$.

    Finally, $\mathcal {C}$ returns $(upk_{l}',upd_{l}:=(c_{up},c_{KEM}),usk_{l}')$.

Lemma 3

If $\mathcal {A}$ can distinguish $\mathcal {G}_0$ and $\mathcal {G}_1$, there exists an adversary $\mathcal {B}_{EtM}^{0}$ that can make use of $\mathcal {G}_0$ and $\mathcal {G}_1$ to break the IND-CCA game of $\prod _{EtM}$ with the following probability $\Pr [EtM_{0}]$:

$$\begin{aligned} \Pr [EtM_{0}]:=\left| \Pr [\mathcal {W}_1]-\Pr [\mathcal {W}_0]\right| \le Adv_{\prod _{EtM}}(\mathcal {\mathcal {B}}_{EtM}^{0}). \end{aligned}$$

(11)

Proof

$\cdot$:

First, we prove that the queries are indistinguishable. From the view of $\mathcal {A}$, according to the key homomorphic of $\prod _{KEM}$:

$$\begin{aligned} \begin{array}{ll} sum_{i+1}& =sk_{1}^{UP}\otimes sk_{2}^{UP}...\otimes sk_{i}^{UP}. \\ usk_{i+1}& =usk_0\otimes sk_{1}^{UP}\otimes sk_{2}^{UP}...\otimes sk_{i}^{UP}=usk_0\otimes sum_{i+1}. \end{array} \end{aligned}$$

(12)

Because $\mathcal {C}$ can answer the queries correctly with the help of $\mathcal {C}_{KEM}$, Plaintext Queries, Ciphertext Queries Seed Queries, Update Queries in $\mathcal {G}_1$ are indistinguishabe from these in $\mathcal {G}_0$.

$\cdot$:

Second, we prove $usk_{l}$ and $usk_{l}'$ are indistinguishable. Assume there exist an $sk'\in \mathcal{S}\mathcal{K}$ s.t.:

$$\begin{aligned} \begin{array}{ll} usk_{l}& =usk_0\otimes sum_{l-1}\otimes sk_{l}^{UP}=usk_{l-1}\otimes sk_{l}^{UP} \\ usk_{l}'& =usk_0\otimes sum_{l-1}\otimes sk_{l}'=usk_{l-1}\otimes sk_{l}'. \end{array} \end{aligned}$$

(13)

Because $usk_{l}'$ is generated by random, $sk_{l}'$ can be seen as a random value, $\mathcal {A}$ cannot distinguish $sk_{l}'$ and $sk_{l}^{UP}$ so as to $usk_{l}$ and $usk_l'$.

$\cdot$:

Finally, we show that the main difference between $\mathcal {G}_0$ and $\mathcal {G}_1$ is that in $\mathcal {G}_0$, $sk_{l}^{UP}$ is the plaintext of $\prod _{EtM}.{\textbf {HEnc}}$ while it should be $sk_{l}'$ in $\mathcal {G}_1$ but not $sk_{l}^{UP}$. If $\mathcal {A}$ can distinguish $\mathcal {G}_0$ and $\mathcal {G}_1$ and abort the game, it means that $\mathcal {A}$ can distinguish the output of $\prod _{EtM}.{\textbf {HEnc}}$. Then there exists an adversary $\mathcal {B}_{EtM}^{0}$ that can make use of $\mathcal {A}$ to break the IND-CCA game of $\prod _{EtM}$. Let $m_0:=sk_{l}^{UP}$, $m_1:=sk_{l}'$. If $\mathcal {A}$ aborts the game, $\mathcal {B}_{EtM}^{0}$ outputs 1 otherwise 0. Therefore:

$$ \Pr [EtM_{0}]:=\left| \Pr [\mathcal {W}_1]-\Pr [\mathcal {W}_0]\right| \le Adv_{\prod _{EtM}}(\mathcal {\mathcal {B}}_{EtM}^{0}). $$

• $\mathcal {G}_2:$ It is the same as $\mathcal {G}_1$ except that $\mathcal {C}$ sets $sum^j$ to accumulate the $sk_j^{UP}$ in Update Queries and Seed Queries, Stage 2, where $j\in [t+1,l]$, $sum^{t+1}:=sk_{t+1}^{UP}$, and $sum^j:=sk_{t+1}^{UP}\otimes sk_{t+2}^{UP}...\otimes sk_{j}^{UP}$ if $j>t+1$. In $\mathcal {G}_2$, if $sum^j\otimes usk_{t}=usk_{t}$ occurs, $\mathcal {C}$ aborts the game.

This is to prove that our scheme can resist the non-influential randomness. Assume there are $q_{SD_2}$ Seed Queries and $q_{UP_2}$ Update Queries in Stage 2. According to Lemma 1, G$_0$ is weakly one-way and $\mathcal {A}$ cannot set $seed_j$ to decide $sk_j^{UP}$ s.t. $sum^j\otimes usk_{t}=usk_{t}$. So $\mathcal {C}$ aborts the game only when $\mathcal {A}$ executes Seed Queries and Update Queries, $sum^{j-1}\otimes sk_{j}^{UP}\otimes usk_{t}=usk_{t}$ occurs. Therefore:

$$\begin{aligned} \left| \Pr [\mathcal {W}_2]-\Pr [\mathcal {W}_1]\right| \le \frac{q_{SD_2}+q_{UP_2}}{|\mathcal{S}\mathcal{K}|}. \end{aligned}$$

(14)

• $\mathcal {G}_3$: It is the same as $\mathcal {G}_2$, except that in Comp, $\mathcal {C}$ sets $sk_{t}^{UP}\leftarrow \$\mathcal{S}\mathcal{K}$.

If $\mathcal {A}$ can distinguish $\mathcal {G}_3$ and $\mathcal {G}_2$, it means that $\mathcal {A}$ can distinguish the output of ${\textbf {G}}_0(seed')$ from random. Then there exists an adversary $\mathcal {B}_{PRG}^{0}$ that can make use of $\mathcal {A}$ to break the security game of ${\textbf {G}}_0$. Let $r_0:=sk_{t}^{UP}$, $r_1\leftarrow \$\mathcal{S}\mathcal{K}$. If $\mathcal {A}$ aborts the game, $\mathcal {B}_{PRG}^{0}$ outputs 1 otherwise 0. Therefore:

$$\begin{aligned} \left| \Pr [\mathcal {W}_3]-\Pr [\mathcal {W}_2]\right| \le Adv_{{\textbf {G}}}(\mathcal {B}_{PRG}^{0}). \end{aligned}$$

(15)

• $\mathcal {G}_4$: It is the same as $\mathcal {G}_3$, except that in Chal, $\mathcal {C}$ sets $\textbf{k}_{KEM}\leftarrow \$\mathcal {K}_{KEM}$.

If $\mathcal {A}$ can distinguish $\mathcal {G}_4$ and $\mathcal {G}_3$, it means that $\mathcal {A}$ can distinguish the output of $\prod _{KEM}.{\textbf {Decap}}$ from random. Then there exists an adversary $\mathcal {B}_{KEM}$ that can make use of $\mathcal {A}$ to break the IND-CCA-KH game of $\prod _{KEM}$. Let $k_0:=\textbf{k}_{KEM}$, $k_1\leftarrow \$mathcal{K}_{KEM}$. If $\mathcal {A}$ aborts the game, $\mathcal {B}_{KEM}$ outputs 1 otherwise 0. Therefore:

$$\begin{aligned} \left| \Pr [\mathcal {W}_4]-\Pr [\mathcal {W}_3]\right| \le Adv_{\prod _{KEM}}^{IND-CCA-KH}(\mathcal {B}_{KEM},\lambda ). \end{aligned}$$

(16)

• $\mathcal {G}_5$: It is the same as $\mathcal {G}_4$, except that in Chal, $\mathcal {C}$ sets $\textbf{k}_{SE}\leftarrow \$\mathcal {K}_{SE}$ instead of $\textbf{k}_{SE}\leftarrow {\textbf {G}}(\textbf{k}_{KEM})$.

If $\mathcal {A}$ can distinguish $\mathcal {G}_5$ and $\mathcal {G}_4$, there exists an adversary $\mathcal {B}_{PRG}^{1}$ that can make use of $\mathcal {A}$ to break the security game of ${\textbf {G}}_1$. Let $r_0:=\textbf{k}_{SE}$, $r_1\leftarrow \$\mathcal {K}_{SE}$. If $\mathcal {A}$ aborts the game, $\mathcal {B}_{PRG}^{1}$ outputs 1 otherwise 0. Therefore:

$$\begin{aligned} \left| \Pr [\mathcal {W}_5]-\Pr [\mathcal {W}_4]\right| \le Adv_{{\textbf {G}}}(\mathcal {B}_{PRG}^{1}). \end{aligned}$$

(17)

• $\mathcal {G}_6$: It is the same as $\mathcal {G}_5$, except that in Chal, $\mathcal {C}$ sets $\textbf{k}_{MAC}\leftarrow \$\mathcal {K}_{MAC}$ instead of $\textbf{k}_{MAC}\leftarrow {\textbf {G}}(\textbf{k}_{KEM})$.

If $\mathcal {A}$ can distinguish $\mathcal {G}_6$ and $\mathcal {G}_5$, there exists an adversary $\mathcal {B}_{PRG}^{2}$ that can make use of $\mathcal {A}$ to break the security game of ${\textbf {G}}_2$. Let $r_0:=\textbf{k}_{MAC}$, $r_1\leftarrow \$\mathcal {K}_{MAC}$. If $\mathcal {A}$ aborts the game, $\mathcal {B}_{PRG}^{2}$ outputs 1 otherwise 0. Therefore:

$$\begin{aligned} \left| \Pr [\mathcal {W}_6]-\Pr [\mathcal {W}_5]\right| \le Adv_{{\textbf {G}}}(\mathcal {B}_{PRG}^{2}). \end{aligned}$$

(18)

Because of the random $\textbf{k}_{SE}$ and $\textbf{k}_{MAC}$, if $\mathcal {A}$ can distinguish the outputs in $\mathcal {G}_6$, there exists an adversary $\mathcal {B}_{EtM}^{1}$ that can make use of $\mathcal {A}$ to break the $\prod _{EtM}$. Actually, $\mathcal {G}_6$ is the IND-CCA game of $\prod _{EtM}$. According to Lemma 2:

$$\begin{aligned} \Pr [\mathcal {W}_6]=Adv_{\prod _{EtM}}^{IND-CCA}(\mathcal {B}_{EtM}^{1}). \end{aligned}$$

(19)

Assume $\mathcal {B}_{EtM}$ plays the roles of $\mathcal {B}_{EtM}^0$ and $\mathcal {B}_{EtM}^1$, $\mathcal {B}_{PRG}$ plays the roles of $\mathcal {B}_{PRG}^{0}$, $\mathcal {B}_{PRG}^{1}$ and $\mathcal {B}_{PRG}^2$, according to the equations (11), (14), (15), (16), (17), (18), (19), there is

$$\begin{aligned} \begin{array}{ll} Adv_{\prod _{UPKE}}^{IND-CU-CCA}(\mathcal {A},\lambda )\le & \frac{q_{SD_2}+q_{UP_2}}{\left| \mathcal {S}\mathcal {K}\right| }+Adv_{\prod _{KEM}}^{IND-CCA-KH}(\mathcal {B}_{KEM},\lambda )\\ & +3Adv_{{\textbf {G}}}(\mathcal {B}_{PRG})+2Adv_{\prod _{EtM}}(\mathcal {B}_{EtM}). \end{array} \end{aligned}$$

(20)