Tightly CCA-secure encryption scheme in a multi-user setting with corruptions

Abstract

The security of public-key encryption (PKE) schemes in a multi-user setting is aimed at capturing real-world scenarios in which an adversary could attack multiple users and multiple ciphertexts of its choice. However, the fact that a real-world adversary can also mount key-exposure attacks for a set of multiple public keys requires us to consider a more realistic notion of security in multi-user settings. In this study, we establish the security notion of PKE in a multi-user setting with corruptions, where an adversary is able to issue (adaptive) encryption, decryption, and corruption (i.e., private key) queries. We then propose the first practical PKE scheme whose security is proven in a multi-user setting with corruptions. The security of our scheme is based on the computational Diffie–Hellman (CDH) assumption and is proven to be tightly chosen-ciphertext secure in a random oracle model. Our scheme essentially follows the recently proposed modular approach of combining KEM and augmented DEM in a multi-user setting, but we show that this modular approach works well in a multi-user setting with corruptions.

1 Introduction

The security of most public-key encryption (PKE) schemes is analyzed using security models that reflect real-world attack environments as closely as possible. The standard security model for PKE schemes has been formalized as the indistinguishability against adaptive chosen-ciphertext attacks model (denoted as ‘$\mathsf {IND}$-$\mathsf {CCA}$’ security [5, 12, 26, 27]), where a single user and a single ciphertext become targets to an adversary. However, the $\mathsf {IND}$-$\mathsf {CCA}$ security model is still lacking for fully reflecting realistic scenarios because a real-world adversary can try to attack multiple users and multiple ciphertexts of their choice. To narrow the gap between the $\mathsf {IND}$-$\mathsf {CCA}$ security model and real-world scenarios, Bellare et al. [6] proposed an $\mathsf {IND}$-$\mathsf {CCA}$ security model in a multi-user setting (hereafter denoted as ‘$\mathsf {IND}$-$\mathsf {CCA}$-$\mathsf {MUC}$’ or simply the ‘$\mathsf {MUC}$’ model), where multiple users and multiple ciphertexts become targets to an adversary. In particular, the $\mathsf {MUC}$ model captures even attack scenarios in which an attacker obtains related messages encrypted using different public keys. Recently, many studies [2, 14, 15, 18, 20,21,22, 24, 25] have focused on designing new PKE schemes that are proven secure in the $\mathsf {MUC}$ model [6].

Another consideration to make when constructing PKE schemes is to provide tight security reductions, which involve proving the security of the scheme based on certain computational hardness assumptions. In general, a security reduction demonstrates that if a computational problem is hard to solve with probability $2^{-\lambda }$, then any adversary in a security model can break such a PKE scheme with a probability of at most $L \cdot 2^{-\lambda }$, where $\lambda$ is a security parameter and L is a factor of security loss. If L is a constant, the hardness of a computational assumption is tightly transformed into the security of a PKE scheme at the same security level. On the other hand, if $L=2^{30}$ for instance, then any adversary can break such a PKE scheme with a probability of at most $2^{30} \cdot 2^{-\lambda }$, which means that the security parameter $\lambda$ should be increased to approximately $\lambda +30$ to achieve the same level of security. Because increasing the security parameter results in a significant decrease in efficiency, it is important to achieve tight security reductions in a practical sense. Moreover, there is no doubt that computational assumptions should be believed to be standard, i.e., well-established as cryptographic complexity assumptions, such as the discrete logarithm and the computational Diffie-Hellman (CDH) assumptions [4, 11].

In light of the above considerations, many PKE schemes [2, 14, 15, 18, 20,21,22, 24, 25] have been proposed to provide (almost¹) tight security reductions in the $\mathsf {MUC}$ model. Though most of them provide (almost) tight security reductions without using random oracles, these schemes are generally considered inefficient for practical use. More concretely, some these PKE schemes [21, 24, 25] are constructed using a variant of the Naor–Yung (NY) double-encryption paradigm [26] and the Groth–Sahai [19] non-interactive zero-knowledge (NIZK) proofs, so they require quite a large number of pairing operations during decryption. In addition, for a security parameter $\lambda$, some have the drawbacks of requiring $O(\lambda )$ ciphertexts [21] or $O(\lambda )$ public keys [24, 25]. Two of these PKE schemes are obtained by applying the Boneh–Canetti–Halevi–Katz transform [8] to identity-based encryption (IBE) schemes [2, 22] that are almost tightly secure in a multi-challenge and multi-instance² setting. The resultant PKE constructions [2, 22] are all based on bit-by-bit encoding methods for handling elements corresponding to $O(\lambda )$-bit identities, resulting in $O(\lambda )$-long public keys. Recently, Gay et al. [14] presented a PKE scheme with an almost tight security reduction in pairing-free groups, but their scheme still suffers from having $O(\lambda )$ public keys. More recently, Gay et al. [15] reduced the size of the public keys to a constant size. However, their security reduction is almost tight, which means that a security loss still occurs with a factor of $O(\lambda )$.

1.1 Motivation

Although the $\mathsf {MUC}$ model has been considered to capture real attack scenarios in which an adversary tries to attack multiple users and multiple ciphertexts of its choice, the security guarantee of the $\mathsf {MUC}$ model is still insufficient to reflect attacks that can occur in reality. This insufficiency comes from not taking the corruption of private keys into account as a possible attack even though many public keys are given to the adversary. Namely, in the $\mathsf {MUC}$ model, a set of public keys $\{\mathsf {PK}_{1}, \ldots , \mathsf {PK}_{n}\}$ for a positive integer n are given to the adversary but, without allowing for the corruption of some private keys corresponding to the public keys, the adversary must rely on chosen-ciphertext attacks. However, given the fact that cryptographic computations (such as decryption using private keys) are sometimes performed on weakly protected devices, the adversary can successfully expose some private keys. This issue requires us to strengthen the $\mathsf {MUC}$ model by including so-called corruption (i.e., private key) queries on some of the public keys. We denote the strengthened $\mathsf {MUC}$ model as the $\mathsf {MUC}^{+}$ model, which refers to the $\mathsf {IND}$-$\mathsf {CCA}$ security model in a multi-user setting with corruptions. Such private key queries in a multi-user setting can also be justified by the recent works [3, 17], which suggests a practical and tightly-secure signature scheme in a multi-user setting with corruptions. Similarly, the standard notion of IBE security [7, 28] offers corruption queries for identities (used as public keys) that an adversary can choose adaptively.

The more realistic $\mathsf {MUC}^{+}$ model raises the following question: can we construct a practical and tightly secure PKE scheme in the $\mathsf {MUC}^{+}$ model? It is known that using random oracles makes it easy to design such a PKE scheme in the $\mathsf {MUC}$ model. For instance, one can obtain the ElGamal encryption scheme, which is proven to be tightly secure against chosen-plaintext attacks (denoted as ‘$\mathsf {IND}$-$\mathsf {CPA}$’) in the $\mathsf {MUC}$ model, based on the decisional Diffie–Hellman (DDH) problem and its random self-reducibility [6]. Next, by applying the tight variant [23] of the Fujisaki–Okamoto (FO) transform [13] to the $\mathsf {IND}$-$\mathsf {CPA}$-secure ElGamal scheme, one can achieve a practical PKE scheme with a tight security reduction in the $\mathsf {MUC}$ model. This is the reason why there has not been enough research to find practical and tightly secure PKE schemes in random-oracle models. However, the same approach does not hold for constructing a secure PKE scheme in the $\mathsf {MUC}^{+}$ model because handling corruption queries on an arbitrary subset of public keys $\{\mathsf {PK}_{1}, \ldots , \mathsf {PK}_{n}\}$ (by guessing a subset of public keys in advance) results in a poor security reduction, even for somewhat large values of n, e.g., $n=2^{10}$. This shows that a new technique may be required when using random oracles to construct an tightly $\mathsf {IND}$-$\mathsf {CCA}$-secure PKE scheme in the $\mathsf {MUC}^{+}$ model.

1.2 Our contributions

Table 1 Comparison between previous PKE schemes and ours

We propose the first practical PKE scheme with tight security reduction in the $\mathsf {MUC}^{+}$ model, following the modular approaches of the KEM (key encapsulation mechanism) and augmented DEM (data encapsulation mechanism) frameworks in a multi-user setting [16]. In terms of efficiency, our scheme offers a O(1)-sized public key that contains four group elements and O(1)-sized ciphertext that consists of two hash outputs plus one group element. In addition, KEM encryption and decryption operations each require five group exponentiations. In particular, because our scheme works with pairing-free groups, those group operations can be easily performed using elliptic-curve cryptography (ECC) algorithms. In terms of security, we first provide a formal definition of KEM with respect to the $\mathsf {MUC}^{+}$ model where, in addition to multiple encapsulation and decapsulation queries, corruption (i.e., private key) queries are permitted given a set of public keys $\{\mathsf {PK}_{1}, \ldots , \mathsf {PK}_{n}\}$. Next, we suggest a modified version of augmented hybrid encryption by combining a KEM approach (secure in the $\mathsf {MUC}^{+}$ model) and an augmented DEM approach (secure in a multi-instance setting) and show that the resulting PKE scheme achieves a tight security reduction in the $\mathsf {MUC}^{+}$ model. Interestingly, augmented DEM (without allowing for corruption queries in its security) suffices for the security of the $\mathsf {MUC}^{+}$ model because corruption queries involve key-exposure attacks only in KEM. Under the abovementioned security frameworks, we prove that our KEM scheme is tightly secure in the $\mathsf {MUC}^{+}$ model using random oracles based on the CDH assumption. Table 1 presents a comparison between previous (almost) tightly secure PKE schemes and our scheme in terms of security and efficiency.

1.2.1 Our approach

To achieve tight security reductions in the $\mathsf {MUC}^{+}$ model, we first need to consider a technique to handle corruption queries without causing a non-tight security reduction. To do this, we employ the idea of the NY double-encryption paradigm (even in a random oracle model), by which a simulator in our security analysis can answer any corruption queries with respect to each of the public keys $\{\mathsf {PK}_{1}, \ldots , \mathsf {PK}_{n}\}$. More precisely, each $\mathsf {PK}_{i}$ consists of two public keys $(\mathsf {pk}_{0,i}, \mathsf {pk}_{1,i})$ and thus, for a randomly chosen bit $b \in \{0,1\}$, only $\mathsf {sk}_{b,i}$ is the corresponding private key. In this setting, the simulator knows only one of the private keys, $\mathsf {sk}_{b,i}$, which can be given as the answer to the corruption query, whereas the other private key $\mathsf {sk}_{1-b,i}$ is unknown to the simulator. Using the encryption algorithm $\mathsf {enc}$ of a PKE scheme under $\mathsf {pk}_{0,i}$ and $\mathsf {pk}_{1,i}$, our KEM scheme encrypts the same message R (randomly chosen in a message space) and generates a ciphertext $\mathsf {CT}=(C_{0}, C_{1})$, where $C_{0}=\mathsf {enc}(\mathsf {pk}_{0,i}, R)$ and $C_{1}=\mathsf {enc}(\mathsf {pk}_{1,i}, R)$. Given the ciphertext $\mathsf {CT}=(C_{0}, C_{1})$ generated in the abovementioned way, the simulator can decrypt $C_{b}$ using $\mathsf {sk}_{b,i}$ but cannot decrypt the other part $C_{1-b}$. This makes it hard for the simulator to check the well-formedness of $C_{1-b}$ and thus deal with (adversarial) decapsulation queries. To solve this problem, the NY technique generates the NIZK proof $\pi$ to prove that $C_{0}$ and $C_{1}$ encrypt the same message R and appends proof $\pi$ to the ciphertext.

On the other hand, using random oracles instead of the generally inefficient NIZK proof makes it easier and simpler to solve the problem without increasing the size of ciphertexts. Let H and $H'$ be hash functions modeled as random oracles. Our idea is to use the KEM variant of the FO transform [1] to check the well-formedness of the other part, $C_{1-b}$. For the same encrypted message R, the ciphertext is constructed as $\mathsf {CT}=(C_{0}, C_{1})$, where $C_{0}=\mathsf {enc}(\mathsf {pk}_{0,i}, R; H(R))$ and $C_{1}=\mathsf {enc}(\mathsf {pk}_{1,i}, R; H(R))$ for the same randomness H(R). In this case, the simulator can obtain R by decrypting $C_{b}$ and check if $C_{1-b}$ was generated correctly through the simple re-encryption of R under the randomness H(R). That is, the randomness recovery property of the FO transform makes it very simple to check in the NY paradigm whether both $C_{0}$ and $C_{1}$ encrypt the same message under the same randomness. Under the ciphertext $\mathsf {CT}$ generated as explained above, the relevant KEM key is computed as $\textsf {K}=H'(R)$. Because the adversary is asked to query R to oracle H each time it encrypts message R, the queried R allows the simulator to know beforehand what the KEM key $\textsf {K}$ corresponding to ciphertext $\mathsf {CT}$ will be. This shows how the simulator is able to handle decapsulation queries in the above (NY$+$FO)-combined technique.

Given a challenge ciphertext $\mathsf {CT}^{*}=(C^*_{0}, C^*_{1})$ for a challenged $\mathsf {PK}^*_{i}$ $=$ $(\mathsf {pk}^*_{b}$, $\mathsf {pk}^*_{1-b})$ (which can be easily extended to a multi-user setting), the adversary must decrypt either $C^{*}_{0}$ or $C^*_{1}$ to recover the encrypted message $R^*$ (and then the KEM key $\textsf {K}^*=H'(R^*)$). We now have a simulator that can decrypt $C^*_{b}$ using $\mathsf {sk}^{*}_{b,i}$ but not $C^*_{1-b}$, hoping that the adversary can decrypt $C^*_{1-b}$. If the adversary does not know bit b for private key $\mathsf {sk}^{*}_{b,i}$, which has not been corrupted, we can expect that the adversary will decrypt $C^*_{1-b}$ with a probability of essentially 1/2. Hence, the simulator can use the ability of the adversary to break the PKE scheme under $\mathsf {pk}^{*}_{1-b,i}$ with the same probability of 1/2. This observation shows that it is necessary to prove that bit b for $\mathsf {sk}^{*}_{b,i}$ is not revealed to the adversary in our security proofs. However, this hiding is not enough to prove that the (NY+FO)-combined KEM is tightly secure in a multi-user setting, especially, under the CDH assumption. Given a set of challenged public keys, the simulator should be able to check which public key among the challenged set is the target for the adversary to succeed, because a distinct instance of the CDH problem is associated with each (challenged) public key, respectively. Otherwise, the simulator choose a target public key among the set of challenged public keys, which also causes $\mathcal {O}(n)$ security loss. To solve these issues, we use a PKE scheme as a building block (regarding $\mathsf {pk}_{0,i}$ and $\mathsf {pk}_{1,i}$), which is a slight variant of the twin ElGamal encryption scheme [9]. Our variant³ can be proven to be tightly one-way-secure against chosen-plaintext attacks (denoted as ‘$\mathsf {OW}$-$\mathsf {CPA}$’) based on the twin Diffie–Hellman (TDH) assumption [9] (and thus the CDH assumption), which has an access to a decisional TDH oracle as a checking mechanism. Therefore, breaking the PKE scheme under $\mathsf {pk}^{*}_{1-b,i}$ with probability $\varepsilon$ allows the simulator to solve an instance of the TDH (and thus the CDH) problem with probability $\varepsilon /2$. Finally, the random self-reducibility of the TDH assumption implies that the results in single-user settings can be easily extended to multi-user settings without causing any security loss.

In 2015, Bader et al. [3] showed that using the NY double encryption technique, the generic KEM based on any $\mathsf {IND}$-$\mathsf {CPA}$-$\mathsf {MUC}$-secure PKE scheme can be proven tightly secure in the $\mathsf {IND}$-$\mathsf {CPA}$-$\mathsf {MUC}^{+}$ model. Their construction idea is almost similar to the above mentioned one, in that each public key $\mathsf {PK}$ consists of two public keys $(\mathsf {pk}_{0}, \mathsf {pk}_{1})$ and only one $\mathsf {sk}_{b}$ is generated for a randomly chosen $b \in \{0,1\}$. In that case, one might think that it is generically easy to build a KEM (tightly) secure in the $\mathsf {IND}$-$\mathsf {CCA}$-$\mathsf {MUC}^{+}$ model from a KEM (or PKE scheme) secure in the $\mathsf {IND}$-$\mathsf {CPA}$-$\mathsf {MUC}^{+}$ model, using the FO transform as usual. Our answer is no, and the reason is from the indistinguishability of the underlying PKE scheme. Our argument is as follows: for a challenged public key $\mathsf {PK}^*=(\mathsf {pk}^*_{0}, \mathsf {pk}^*_{1})$, a challenge ciphertext is constructed as $\mathsf {CT}^*=(C^*_{0}, C^*_{1})$ on a message $m^*$, where $C^*_{b}$ is an encryption of $m^*$ generated by the simulator itself and $C^*_{1-b}$ is the challenge ciphertext that the simulator is given in response to the same $m^*$. Thus, $C^*_{1-b}$ could be an encryption of either $m^*$ or a random (unknown) message R, and the goal of the simulator is to correctly guess which one of the two cases, using the ability of the adversary. When applying the FO transform, $C^*_{b}$ is computed as $C^*_{b}=\mathsf {enc}(\mathsf {pk}^*_{b}, m^*;H(b,m^*))$. In case of a single challenge ciphertext, it is easy to see that the simulator can use the adversary’s ability straightforwardly by checking if $(b, m^*)$ is queried to H oracle. This is because making such a query related to $m^*$ is the only way that the adversary distinguishes between a real game and the simulation game. However, in case of $\mathsf {CT}^*=(C^*_{0}, C^*_{1})$, the adversary can distinguish between the two games, regardless of whether $C^*_{1-b}$ is the encryption of $m^*$ or R. Firstly, when $C^*_{1-b}=\mathsf {enc}(\mathsf {pk}^*_{1-b}, m^*; r^*)$ for some randomness $r^*$, the adversary recovers $m^*$ from either $C^*_{b}$ or $C^*_{1-b}$ and issues H-oracle queries on inputs $(b, m^*)$ and $(1-b, m^*)$. The point is that even though those oracle queries related to $m^*$ are made, the simulator does not know which ciphertext among $(C^*_{0}, C^*_{1})$ is decrypted by the adversary. Moreover, the simulator cannot answer the H-oracle query on the input $(1-b, m^*)$ unless $r^*$ is known to the simulator, which allows the adversary to differentiate between the two games. Secondly, when $C^*_{1-b}=\mathsf {enc}(\mathsf {pk}^*_{1-b}, R; r^*)$, the adversary is able to recover both $m^*$ from $C^*_{b}$ and R from $C^*_{1-b}$, in which case the adversary immediately can see that it is under simulation. If the adversary recovers either $m^*$ from $C^*_{b}$ or R from $C^*_{1-b}$, the simulator cannot reply to H-oracle queries on inputs $(1-b,m^*)$, (b, R), and $(1-b, R)$ consistently. As a result, in any case, the adversary can distinguish the two games. On the other hand, the idea behind our construction is that we rely the security of the underlying PKE scheme on the computational hardness (rather than indistinguishability) of the TDH problem, and find a correct answer with respect to a TDH instance, using H-oracle queries and the decisional TDH oracle.

2 Background

2.1 Notation

We write $\lambda \in \mathbb {N}$ for the security parameter. We say that a function $\nu : \mathbb {N}\rightarrow \mathbb {R}$ is negligible if, for every positive polynomial $\textsf {poly}(\cdot )$, there exists an integer $N>0$ such that for all $x>N$ it holds that $|\nu (x)|<\textsf {poly}(x)^{-1}$. Given an algorithm A, we write $y \leftarrow A$ to denote that y is the output of A. If A is a probabilistic algorithm, then $y \xleftarrow {\$}A$ denotes that y is computed by A using fresh random coins. When A is a set, $a\xleftarrow {\$}A$ denotes that a is chosen uniformly over A. For $n\in \mathbb {N}$, we write [n] to denote the set $\{1,\ldots ,n\}$.

2.2 Computational Diffie–Hellman assumption

Let $({\mathbb {G}}, p, g)$ be a group generated by a group generation function $\mathcal {G}(\lambda )$. Given $(p, g, g^a, g^b)$, where $a, b \xleftarrow {\$} \mathbb {Z}_p$, the CDH problem consists in computing $g^{ab}$ in ${\mathbb {G}}$. The advantage of $\mathcal {A}$ for solving the CDH problem is defined as

$$\begin{aligned} \epsilon (\lambda ) =&\Pr [ Z \leftarrow \mathcal {A}(p, g, g^a, g^b) : a, b \xleftarrow {\$} \mathbb {Z}_p \wedge Z = g^{ab}]. \end{aligned}$$

We say that the $(t,\epsilon )$-CDH assumption holds in group $({\mathbb {G}}, p, g)$ if no t-time algorithm has an advantage of at least $\epsilon$ when solving the CDH problem.

2.3 Twin Diffie–Hellman assumption

Let $({\mathbb {G}}, p, g)$ be a group generated by a group generation function $\mathcal {G}(\lambda )$. Given $(p, g, g^a, g^{b_1},g^{b_2})$, where $a, b_1, b_2 \xleftarrow {\$} \mathbb {Z}_p$ and a decisional twin Diffie–Hellman oracle (for fixed $g^{b_1},g^{b_2}$), that is, an oracle that for any $(R,B_1,B_2)\in {\mathbb {G}}^3$ given as inputs correctly answers the question “is it the case that both $B_1=g^{b_1 r}$ and $B_2=g^{b_2 r}$, where r is the exponent for which $R=g^r$?”, the TDH problem consists in computing $(g^{ab_1},g^{ab_2})$. The advantage of $\mathcal {A}$ for solving the TDH problem is defined as

$$\begin{aligned} \epsilon (\lambda ) = \Pr [ (Z_1,Z_2) \leftarrow&\mathcal {A}^{O_{\textsf {DTDH}}(\cdot )}(p, g, g^a, g^{b_1}, g^{b_2}) :\\&a, b_1, b_2 \xleftarrow {\$} \mathbb {Z}_p \wedge Z_1 = g^{ab_1} \wedge Z = g^{ab_2}]. \end{aligned}$$

We say that the $(t,\epsilon )$-TDH assumption holds in group $({\mathbb {G}}, p, g)$ if no t-time algorithm has an advantage of at least $\epsilon$ when solving the TDH problem.

Theorem 1

[Theorem 1 in [9]] The CDH assumption holds if and only if the TDH assumption holds.

3 IND-CCA secure KEM

In this section, we define the $\textsf {MUC}^+$ model of $\textsf {KEM}$ and present our practical $\textsf {KEM}$ scheme. Then, we prove our scheme in the $\textsf {MUC}^+$ model of $\textsf {KEM}$.

3.1 Formal model

3.1.1 Syntax

A key encapsulation mechanism $\textsf {KEM}$ = ($\textsf {KEM.Param}$, $\textsf {KEM.Gen}$, $\textsf {KEM.Encap}$, $\textsf {KEM.Decap}$) consists of four algorithms. The parameter generation algorithm $\Pi$ $\xleftarrow {\$}$ $\textsf {KEM.Param}(\lambda )$ takes the security parameter $\lambda$ as input and outputs parameter $\Pi$. The key generation algorithm $(\textsf {PK}, \textsf {SK})$ $\xleftarrow {\$}$ $\textsf {KEM.Gen}(\Pi )$ generates, after receiving input $\Pi$, a public key $\textsf {PK}$ and a private key $\textsf {SK}$. The encapsulation algorithm $(\textsf {K}, \textsf {CT})$ $\xleftarrow {\$}$ $\textsf {KEM.Encap}(\textsf {PK})$ generates, with $\textsf {PK}$ as input, a key $\textsf {K}$ and a ciphertext $\textsf {CT}$. The decapsulation algorithm $\{\textsf {K}, \bot \}$ $\leftarrow$ $\textsf {KEM.Decap}(\textsf {PK}, \textsf {SK}, \textsf {CT}$) takes public key $\textsf {PK}$, private key $\textsf {SK}$, and ciphertext $\textsf {CT}$ as inputs and then outputs a key $\textsf {K}$ or an error symbol $\bot$. The correctness of $\textsf {KEM}$ is defined as follows: For all $(\textsf {PK}, \textsf {SK})$ generated by $\textsf {KEM.Gen}(\Pi )$, it is required that $\bar{\textsf {K}}=\textsf {K}$ where $(\textsf {K},\textsf {CT}) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK})$ and $\bar{\textsf {K}}\leftarrow \textsf {KEM.Decap}(\textsf {PK}, \textsf {SK}, \textsf {CT})$.

3.1.2 Security model in a multi-user setting with corruptions

We define the $\textsf {MUC}^+$ security of $\textsf {KEM}$ by referring to the security definition of IND-CCA-$\textsf {MUC}$ security from PKE[21]. Our security notion is a more extended concept because it allows for corruption queries, which the previous notion did not. We argue that our $\textsf {MUC}^+$ model is more realistic because the previous $\textsf {MUC}$ model cannot capture situations in which an adversary obtains some of the private keys of the users, which the $\textsf {MUC}^+$ model can capture. The following security experiment, which is a game played between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$, is parameterized by two integers $\mu ,q_e \in \mathbb {N}$.

• 1. The challenger runs $\Pi$ $\xleftarrow {\$}$ $\textsf {KEM.Param}(\lambda )$ once and then $\textsf {KEM.Gen}(\Pi )$ $\mu$ times to generate $\mu$ key pairs ($\textsf {PK}^{(i)},\textsf {SK}^{(i)}$), $i\in [\mu ]$. Then, it tosses a coin $\beta \xleftarrow {\$}\{0,1\}$, initializes lists $\textsf {Clist} := \emptyset$ and $\textsf {Klist} := \emptyset$ as empty lists, and defines a counter $j_i := 0$ for each $i \in [\mu ]$.

• 2. The adversary receives the $\mu$ public keys $\{\textsf {PK}^{(i)}\}_{i\in [\mu ]}$ as input. It may query the challenger for three types of operations.

  • Encapsulation queries The adversary submits an index $i \in [\mu ]$. If $j_i \ge q_e$ or $i \in \textsf {Klist}$, then the challenger returns $\bot$. Otherwise, it generates keys $\textsf {K}_0$ and $\textsf {K}_1$ and a ciphertext $\textsf {CT}$ by sampling $\textsf {K}_0$ $\xleftarrow {\$}$ $\mathcal {K}$ and computing $(\textsf {K}_1, \textsf {CT})$ $\xleftarrow {\$}$ $\textsf {KEM.Encap}(\textsf {PK}^{(i)})$, respectively. Then it appends $(\textsf {CT},i)$ to $\textsf {Clist}$, updates counter $j_i$ via $j_i = j_i + 1$, and returns $(\textsf {K}_\beta ,\textsf {CT})$.

  • Corruption queries The adversary submits an index $i \in [\mu ]$. If $(\textsf {CT},i) \in \textsf {Clist}$ for some $\textsf {CT}$, then the challenger returns $\bot$. Otherwise, it returns $\textsf {SK}^{(i)}$ and appends i to $\textsf {Klist}$.

  • Decapsulation queries The adversary submits a ciphertext $\textsf {CT}$ and an index $i \in [\mu ]$. If $(\textsf {CT},i) \in \textsf {Clist}$, then the challenger returns $\bot$. Otherwise, it returns whatever $\textsf {KEM.Decap}(\textsf {PK}^{(i)}, \textsf {SK}^{(i)}, \textsf {CT})$ returns.

• 3. Eventually, the adversary $\mathcal {A}$ outputs a bit $\beta '$. We say that the adversary $wins$ the game if $\beta =\beta '$.

Definition 1

Let $\mathcal {A}$ be an adversary that runs in time t, that makes at most $q_e$ encapsulation queries per user, $q_c$ corruption queries in total, and $q_d$ decapsulation queries per user, and that wins with probability $1/2 + \epsilon$. Then, we say that $\mathcal {A}$ breaks the $(\epsilon , t,\mu ,q_e,q_c,q_d)$-$\textsf {MUC}^+$ security of $\textsf {KEM}$. We say that $\textsf {KEM}$ is $(\epsilon$,t,$\mu$,$q_e$,$q_c$,$q_d)$-$\textsf {MUC}^+$ secure if there exists no such adversary $\mathcal {A}$.

Note that the above security model with $\mu =1$, $q_e=1$, and $q_c=0$ is the standard $\textsf {IND-CCA}$ security model of $\textsf {KEM}$ in a single-user setting. When $\mu \ge 2$ and $q_c=0$, it is equal to the previous $\textsf {MUC}$ model of $\textsf {KEM}$.

3.2 Construction

Our $\textsf {KEM}$ scheme is parameterized by group parameters $({\mathbb {G}},p,g)$, where p is a $\lambda$-bit integer, ${\mathbb {G}}$ is a cyclic group of order p, and g is a group generator, and by three hash functions, namely $H_1:\{0,1\}^* \rightarrow \mathbb {Z}_p$, $H_2:\{0,1\}^* \rightarrow \{0,1\}^{\ell _1}$, and $H_3:\{0,1\}^{*} \rightarrow \{0,1\}^{\ell _2}$. We denote these parameters as $\Pi = ({\mathbb {G}},p, g, H_1, H_2, H_3)$.

As mentioned in the Introduction section, our $\textsf {KEM}$ scheme uses a variant of the twin ElGamal approach. In this variant of twin ElGamal, a public key consists of two group elements $(X_1=g^{x_1}$, $X_2=g^{x_2})\in {\mathbb {G}}^2$ with a corresponding private key $(x_1,x_2)\in \mathbb {Z}_p^2$, and encryption is done by computing $(g^s,m\oplus H_2(g^s,X_1^s,X_2^s))$ for a random exponent $s\in \mathbb {Z}_p$. Using this variant of twin ElGamal as a building block, the encapsulation algorithm of our scheme generates two ciphertexts of the same message $R\in \{0,1\}^{\ell _1}$ and the same random seed $s\in \mathbb {Z}_p$ using two different public keys $(X_{0,1}, X_{0,2})$ and $(X_{1,1}, X_{1,2})$. The algorithms of our scheme are described as follows.

KEM.Gen ($\Pi$): Given parameters $\Pi$, the Setup algorithm runs as follows:

• 1. Select a bit $b \in \{0,1\}$.

• 2. Select random exponents $x_1,x_2 \in \mathbb {Z}_p$ and set $(X_{b,1},X_{b,2}) = (g^{x_1},g^{x_2}) \in {\mathbb {G}}^2$.

• 3. Select random group elements $(X_{1-b,1},X_{1-b,2}) \in {\mathbb {G}}^2$.

• 4. Output $\textsf {PK}=(X_{0,1}, X_{0,2}, X_{1,1}, X_{1,2}) \in {\mathbb {G}}^4$ and $\textsf {SK}=(b,x_1,x_2) \in \{0,1\}\times \mathbb {Z}_p^2$.

KEM.Encap ($\Pi , \textsf {PK}$): Given a public key $\textsf {PK}=(X_{0,1}, X_{0,2}, X_{1,1}, X_{1,2})$, the Encap algorithm runs as follows:

• 1. Select a random string $R \in \{0,1\}^{\ell _1}$ and set $s=H_1(R) \in \mathbb {Z}_p$.

• 2. Compute ($g^s,X_{0,1}^s,X_{0,2}^s,X_{1,1}^s,X_{1,2}^s$) $\in {\mathbb {G}}^5$ and set $C_2 = g^s \in {\mathbb {G}}$.

• 3. Set $C_0 = R \oplus H_2(g^s, X_{0,1}^s, X_{0,2}^s)$ and $C_1 = R \oplus H_2(g^s, X_{1,1}^s, X_{1,2}^s)$.

• 4. Set $\textsf {K}=H_3(R) \in \{0,1\}^{\ell _2}$.

• 5. Output $\textsf {K}$ and $\textsf {CT}= (C_0, C_1, C_2) \in \{0,1\}^{2\ell _1} \times {\mathbb {G}}$.

KEM.Decap ($\Pi , \textsf {PK}, \textsf {SK}, \textsf {CT}$): Given a public key $\textsf {PK}=(X_{0,1}, X_{0,2}, X_{1,1}, X_{1,2})$, a private key $\textsf {SK}= (b,x_1,x_2)$, and a ciphertext $\textsf {CT}= (C_0, C_1, C_2)$, the Decap algorithm runs as follows:

• 1. Compute $R_b = C_b \oplus H_2(C_2,C_2^{x_1},C_2^{x_2}) \in \{0,1\}^{\ell _1}$.

• 2. Set $s=H_1(R_b) \in \mathbb {Z}_p$ and $\textsf {K}=H_3(R_b) \in \{0,1\}^{\ell _2}$.

• 3. Compute $R_{1-b}=C_{1-b} \oplus H_2(C_2,X_{1-b,1}^s,X_{1-b,2}^s) \in \{0,1\}^{\ell _1}$.

• 4. If $R_b = R_{1-b}$ and $C_2 = g^s$, output K. Otherwise, abort.

3.2.1 Correctness

Given $\textsf {PK}=(X_{0,1}, X_{0,2}, X_{1,1}, X_{1,2}) \in {\mathbb {G}}^4$ and $\textsf {SK}=(b,x_1,x_2) \in \{0,1\}\times \mathbb {Z}_p^2$, $(\textsf {K},\textsf {CT})$ is calculated by KEM.Encap($\Pi , \textsf {PK}$) as follows: $\textsf {K}=H_3(R)$, $\textsf {CT}= (C_0, C_1, C_2)$ $=$ $(R \oplus H_2(g^s, X_{0,1}^s, X_{0,2}^s), R \oplus H_2(g^s, X_{1,1}^s, X_{1,2}^s), g^s)$ where $s=H_1(R)$. Then, we can show that KEM.Decap($\Pi , \textsf {PK}, \textsf {SK}, \textsf {CT}$)=$\textsf {K}$ as follows: first, we have $R_b = C_b \oplus H_2(C_2,C_2^{x_1},C_2^{x_2}) = R \oplus H_2(g^s, X_{b,1}^s, X_{b,2}^s) \oplus H_2(C_2,C_2^{x_1},C_2^{x_2})$. Since $X_{b,1}^s=g^{x_1s}=C_2^{x_1}$ and $X_{b,2}^s=g^{x_2s}=C_2^{x_2}$, we have $R_b=R$. Finally, we have $H_1(R_b)=s$, $C_2=g^s=g^{H_1(R)}$ and $R_b = R_{1-b}$ by $R_{1-b} = C_{1-b}\oplus H_2(C_2,X_{1-b,1}^s,X_{1-b,2}^s)=R$. Then, this algorithm outputs $H_3(R_b)=H_3(R)=\textsf {K}$.

3.3 Security proof

Theorem 2

Suppose that the $(\epsilon _{\textsf {TDH}},t_{\textsf {TDH}})$-TDH assumption holds in $({\mathbb {G}},p,g)$, that $H_1$, $H_2$, and $H_3$ are random oracles, and that an adversary $\mathcal {A}$ makes at most $q_{H_1}$ $H_1$-queries, $q_{H_2}$ $H_2$-queries, $q_{H_3}$ $H_3$-queries, $q_e$ encapsulation queries per user, $q_c$ corruption queries in total, and $q_d$ decryption queries per user. Then, the above mentioned $\textsf {KEM}$ scheme is $(\epsilon ,t,\mu ,q_e,q_c,q_d)$-$\textsf {MUC}^+$ secure, where

$$\begin{aligned}&\epsilon \le 2\epsilon _{\textsf {TDH}} + \frac{q_{H_3}}{2^{\ell _2}}{\mu q_e},\\&t\approx t_{\textsf {TDH}} + (5\mu + 2\mu q_e +5\mu q_d )t_e. \end{aligned}$$

Here, $t_e$ denotes the time required for computing exponentiation in ${\mathbb {G}}$ and $\ell _2$ denotes the output length of random oracle $H_2$.

Table 2 Simulation of a $\textsf {MUC}^+$ game

Proof

The proof is presented as a sequence of hybrid games Game 0,..., Game 3. Game 0 is the actual $\textsf {MUC}^+$ security game and, in Game 3, the adversary will win with an exact probability of 1/2. Let $\textsf {Win}_i$ denote the event in which $\mathcal {A}$ wins in Game i.

Game 0 This is the $(\mu ,q_e)$-$\textsf {MUC}^+$ security experiment from Definition 2. Let $b_i \in \{0,1\}$ be the randomly chosen coin associated with the private key of user i $\in [\mu ]$. In all subsequent games, the coin $b_i$ for each user i $\in [\mu ]$ is fixed. By definition, we have

$$\begin{aligned} \Pr [\textsf {Win}_0] = \frac{1}{2} + \epsilon _{\textsf {KEM}}^{\textsf {MUC}^+}. \end{aligned}$$

Game 1 In this game, the challenger simulates the random oracles, generating random answers for any new queries as shown in Table 2. This game is identical to Game 0. Thus, we have

$$\begin{aligned} \Pr [\textsf {Win}_1] = \Pr [\textsf {Win}_0]. \end{aligned}$$

Game 2 This game is identical to Game 1 except that now the encapsulation oracle operates differently. Given an index $i \in [\mu ]$, unlike the previous game, the challenger sets $C_{2} \xleftarrow {\$}{\mathbb {G}}$, instead of computing $C_{2} = g^{s}$ where $s=H_1(R)$. Then, it sets $C_j = R \oplus V_j$, where $V_j$ is randomly chosen from $\{0,1\}^{\ell _1}$ for $j \in \{0,1\}$. The rest of the procedure is the same as that in Game 1.

Note that Game 1 and Game 2 are indistinguishable unless at least one of the following events occurs:

Event E:

: ($g^{\bar{s}},X_{1-b,1}^{\bar{s}},X_{1-b,2}^{\bar{s}}$) is asked to the $H_2$-oracle, where $g^{\bar{s}} = C_2$ for some $((C_0,C_1,C_2),i)$ in $\textsf {Clist}$, $\textsf {PK}^{(i)}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, and $\textsf {SK}^{(i)}=(b,x_1,x_2).$

Event F:

: ($g^{\bar{s}},X_{b,1}^{\bar{s}},X_{b,2}^{\bar{s}}$) is asked to the $H_2$-oracle, where $g^{\bar{s}} = C_2$ for some (($C_0$, $C_1$, $C_2)$, i) in $\textsf {Clist}$, $\textsf {PK}^{(i)}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, and $\textsf {SK}^{(i)}=(b,x_1,x_2).$

Then, we have

$$\begin{aligned} |\Pr [\textsf {Win}_2]-\Pr [\textsf {Win}_1]| \le \Pr [\textsf {E}] + \Pr [\textsf {F}] \le 2\Pr [\textsf {E}] \le 2\epsilon _{\textsf {TDH}}. \end{aligned}$$

We prove that the inequality above holds after finishing the proof of theorem 2.

Game 3 In this game, the challenge ciphertexts are computed differently compared with the previous game. Given index $i \in [\mu ]$, unlike the previous game, the challenger randomly selects $\textsf {K}\in \mathcal {K}$. Finally, it outputs $(\textsf {K},\textsf {CT}= (C_0,C_1,C_2))$.

Game 2 and Game 3 are completely indistinguishable unless query $R^{(i)}$ for any $i \in [\mu ]$ is asked to the $H_3$-oracle by either the adversary or the decryption oracle. Thus, we have

$$\begin{aligned} |\Pr [\textsf {Win}_3]-\Pr [\textsf {Win}_2]| \le \frac{q_{H_3}}{2^{\ell _2}}{\mu q_e}. \end{aligned}$$

From the results mentioned above, we can conclude that $\epsilon \le 2\epsilon _{\textsf {TDH}} + \frac{q_{H_3}}{2^{\ell _2}}{\mu q_e}$, which completes the proof. $\square$

Claim 1 $\Pr [\textsf {E}] = \Pr [\textsf {F}]$.

Proof

It is sufficient to show that the adversary’s view is independent of the variable $b^{(i)}$ such that $i \notin \textsf {Klist}$ for $i\in [\mu ]$, because if $i \in \textsf {Klist}$, the abovementioned events E and F never occur for i. Because the only variables that are possibly dependent on the $b^{(i)}$ such that $i \notin \textsf {Klist}$ are the responses from the decapsulation oracle, it is sufficient to show that there exists no ciphertext $\textsf {CT}$ such that its decapsulation results are different depending on $b^{(i)}$. For the sake of creating a contradiction, we assume that there exists $\textsf {CT}=(C_0,C_1,C_2)$ such that $Decap(\textsf {PK}^{(i)},\textsf {SK}^{(i)}_{b^{(i)}=0},\textsf {CT})$ $\ne$ $Decap(\textsf {PK}^{(i)},\textsf {SK}^{(i)}_{b^{(i)}=1},\textsf {CT})$, where $\textsf {PK}^{(i)}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, $\textsf {SK}^{(i)}_{b^{(i)}=0}=(0,x_1=\log _g X_{0,1},x_2=\log _g X_{0,1})$, and $\textsf {SK}^{(i)}_{b^{(i)}=1}=(1,x_1'=\log _g X_{1,1},x_2'=\log _g X_{1,1})$. Without loss of generality, we assume that the results of decapsulation on the left are not $\bot$. Let $s^*$ $=$ $\log _g C_2$; then, by the “well-formed” condition checked in the decapsulation procedure at step (5), it holds that $s^* = s$, where $s=H_1(R_0)$, $R_0=C_0 \oplus V_0$, and $V_0 = H_2(C_2,C_2^{x_1},C_2^{x_2})$ (when $b^{(i)}=0$). Then, it holds that $V_1=V_1'$, where $V_1$ comes from the decapsulation procedure at step (4) such that $V_1=H_2(C_2,X_{1,1}^{s},X_{1,2}^{s})$ (when $b^{(i)}=0$), and $V_1'$ comes from the decapsulation procedure at step (2) such that $V_1'=H_2(C_2,C_2^{x_1'},C_2^{x_2'})$ (when $b^{(i)}=1$) because $C_2^{x_1'}=X_{1,1}^{s^*}$, $C_2^{x_2'}=X_{1,2}^{s^*}$, and $s^*=s$. Therefore, it holds that $R_0 = R_1'$ because $R_0=R_1=C_1 \oplus V_1$ (when $b^{(i)}=0$) and $R_1'=C_1 \oplus V_1'$ (when $b^{(i)}=1$). Hence, the two results of decapsulation $H_3(R_0)$ (when $b^{(i)}=0$) and $H_3(R_1')$ (when $b^{(i)}=1$) are the same, which is a contradiction. This completes the proof of the claim. $\square$

Claim 2 $|\Pr [\textsf {Win}_2]-\Pr [\textsf {Win}_1]| \le 2\epsilon _{\textsf {TDH}}$.

Table 3 Algorithms for generating random self-reducible TDH instances

Proof

We show that $|\Pr [\textsf {Win}_2]-\Pr [\textsf {Win}_1]| \le 2\epsilon _{\textsf {TDH}}$ by constructing an algorithm $\mathcal {B}$, which solves the $\textsf {TDH}$ problem using an adversary $\mathcal {A}_\textsf {KEM}$. $\mathcal {B}$ acts as a challenger for $\mathcal {A}_\textsf {KEM}$.

Let ($A,B_1,B_2, O_{\textsf {DTDH}}(\cdot )$) be a TDH instance given to $\mathcal {B}$. For the key pair generation, for each $i \in [\mu ]$ and via the random self-reducibility of TDH, $\mathcal {B}$ obtains a randomized TDH instance ($A',B_1',B_2'$) from the $\mathcal {R}_1$ algorithm defined in Table 3 and records the instance with the exponents in the $\mathcal {R}_1$-list. Then, $\mathcal {B}$ sets $(X_{1-b_i,1}, X_{1-b_i,2})$ = ($B_1',B_2'$) instead of randomly selecting two group points $X_{1-b_i,1}, X_{1-b_i,2} \in {\mathbb {G}}$.

For the encapsulation oracle, given an index $i \in [\mu ]$, $\mathcal {B}$ retrieves the TDH instance $(A',B_1',B_2')$ from the $\mathcal {R}_1$-list. Then, $\mathcal {B}$ obtains a randomized TDH instance $(A'',B_1',B_2')$ from the $\mathcal {R}_0$ algorithm defined in Table 3 and records it with the exponents in the $\mathcal {R}_0$-list. $\mathcal {B}$ sets $C_{2} = A''$, $C_j = R \oplus V_j$, where $V_j$ is randomly chosen from $\{0,1\}^{\ell _1}$ for $j \in \{0,1\}$. The rest of the procedure is the same as that in Game 1.

As mentioned above, Game 1 and Game 2 are indistinguishable unless at least one of the following events occurs:

Event E:

: ($g^{\bar{s}},X_{1-b,1}^{\bar{s}},X_{1-b,2}^{\bar{s}}$) is asked to the $H_2$-oracle, where $g^{\bar{s}} = C_2$ for some $((C_0,C_1,C_2),i)$ in $\textsf {Clist}$, $\textsf {PK}^{(i)}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, and $\textsf {SK}^{(i)}=(b,x_1,x_2).$

Event F:

: ($g^{\bar{s}},X_{b,1}^{\bar{s}},X_{b,2}^{\bar{s}}$) is asked to the $H_2$-oracle, where $g^{\bar{s}} = C_2$ for some (($C_0$, $C_1$, $C_2)$, i) in $\textsf {Clist}$, $\textsf {PK}^{(i)}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, and $\textsf {SK}^{(i)}=(b,x_1,x_2).$

Assume that the Event E occurs i.e., ($\bar{C_2},X_{1-b,1}^{\log _g \bar{C_2}},X_{1-b,2}^{\log _g \bar{C_2}}$) is asked where ($(\bar{C_0}$, $\bar{C_1}$, $\bar{C_2}$), $\bar{i}$) in $\textsf {Clist}$, $\textsf {PK}^{(\bar{i})}=(X_{0,1},X_{0,2},X_{1,1},X_{1,2})$, and $\textsf {SK}^{(\bar{i})}=(b,x_1,x_2)$ for some $\bar{i} \in [\mu ]$. Then, $\mathcal {B}$ can find the answer for the original TDH instance $(A,B_1,B_2)$ from the tuple ($\bar{C_2}$, $X_{1-b,1}^{\log _g \bar{C_2}}$, $X_{1-b,2}^{\log _g \bar{C_2}}$) in the $H_2$-oracle, because the tuple ($\bar{C_2}$, $X_{1-b,1}$, $X_{1-b,2}$) is a randomized TDH instance using algorithms $\mathcal {R}_0$ and $\mathcal {R}_1$. More precisely, let $(A,B_1,B_2) = (g^a,g^{b_1},g^{b_2})$ be the original TDH instance. Then, we see that $(X_{1-b,1}, X_{1-b,2})$ = ($B_1',B_2'$) = $(g^{b_1 \bar{r}_1},g^{b_2 \bar{r}_2})$ and $\bar{C_2} = A''=g^{a \bar{r}_0}$. Thus, we have $(X_{1-b,1}^{\log _g \bar{C_2}},X_{1-b,2}^{\log _g \bar{C_2}}$) = $(g^{ab_1 \bar{r}_0 \bar{r}_1},g^{ab_2 \bar{r}_0 \bar{r}_2})$, where $\mathcal {B}$ can remove the randomized exponents ($\bar{r}_0,\bar{r}_1,\bar{r}_2$) found in the $\{ \mathcal {R}_0 , \mathcal {R}_1\}$-lists and recover the answer for the original TDH instance $(g^{ab_1},g^{ab_2})$. Note that this reduction is tight, because $\mathcal {B}$ can find the correct answer for the TDH instance from the $H_2$-oracle queries, using the decisional TDH oracle $O_{\textsf {DTDH}}(\cdot )$.

From the results of the two claims, we can conclude that

$$\begin{aligned} |\Pr [\textsf {Win}_3]-\Pr [\textsf {Win}_2]| \le \Pr [\textsf {E}] + \Pr [\textsf {F}] \le 2\Pr [\textsf {E}] \le 2\epsilon _{\textsf {TDH}}, \end{aligned}$$

as required. $\square$

4 IND-CCA secure PKE

In this section, we define the $\textsf {MUC}^+$ model of $\textsf {PKE}$ and review augmented hybrid encryption using augmented $\textsf {DEM}$ [16] (hereafter denoted as ‘ADEM’), which is the building block of our $\textsf {PKE}$ scheme. Then, we prove that hybrid encryption combining $\textsf {KEM}$ (secure in the $\textsf {MUC}^+$ model) and $\textsf {ADEM}$ (secure in the multi-instance setting) is tightly secure in the $\textsf {MUC}^+$ model of $\textsf {PKE}$.

4.1 Formal model

4.1.1 Syntax

A public key encryption scheme $\textsf {PKE}$ = ($\textsf {PKE.Param}$, $\textsf {PKE.Gen}$, $\textsf {PKE.Enc}$, $\textsf {PKE.Dec}$) consists of four algorithms. The parameter generation algorithm $\Pi$ $\xleftarrow {\$}$ $\textsf {PKE.Param}(\lambda )$ takes the security parameter $\lambda$ as input and outputs parameter $\Pi$. The key generation algorithm $(\textsf {PK}, \textsf {SK})$ $\xleftarrow {\$}$ $\textsf {PKE.Gen}(\Pi )$ takes $\Pi$ as input and generates a public key $\textsf {PK}$ and a secret key $\textsf {SK}$. The encryption algorithm $\textsf {CT}$ $\xleftarrow {\$}$ $\textsf {PKE.Enc}(\textsf {PK},m)$ takes a public key $\textsf {PK}$ and a message m as inputs and then outputs a ciphertext $\textsf {CT}$. The decryption algorithm m $\leftarrow$ $\textsf {PKE.Dec}(\textsf {PK}, \textsf {SK}, \textsf {CT})$ takes a public key $\textsf {PK}$, a secret key $\textsf {SK}$, and a ciphertext $\textsf {CT}$ as inputs and then outputs a message m. The correctness of $\textsf {PKE}$ is defined as follows: for all $(\textsf {PK}, \textsf {SK})$ generated by $\textsf {PKE.Gen}(\Pi )$, it is required that $\textsf {PKE.Dec}(\textsf {PK}, \textsf {SK}, \textsf {PKE.Enc}(\textsf {PK},m))=m$ for any $m \in \mathcal {M}$.

4.1.2 Security model in a multi-user setting with corruptions

We define the $\textsf {MUC}^+$ security of $\textsf {PKE}$ by referring to the security definition of IND-CCA-$\textsf {MUC}$ security from $\textsf {PKE}$ [21]. As in the $\textsf {MUC}^+$ security notion of KEM, the abovementioned security notion is also an extended concept that allows for corruption queries. The following security experiment, which is a game played between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$, is parameterized by two integers $\mu ,q_e \in \mathbb {N}$.

• 1. The challenger runs $\Pi$ $\xleftarrow {\$}$ $\textsf {PKE.Param}(\lambda )$ once and then $\textsf {PKE.Gen}(\Pi )$ $\mu$ times to generate $\mu$ key pairs ($\textsf {PK}^{(i)},\textsf {SK}^{(i)}$), $i\in [\mu ]$. Then, it tosses a coin $\beta \xleftarrow {\$}\{0,1\}$, initializes lists $\textsf {Clist} := \emptyset$ and $\textsf {Klist} := \emptyset$ as empty lists, and defines a counter $j_i := 0$ for each $i \in [\mu ]$.

• 2. The adversary receives the $\mu$ public keys $\{\textsf {PK}^{(i)}\}_{i\in [\mu ]}$ as input. It may query the challenger for three types of operations.

  • Encryption queries The adversary submits an index $i \in [\mu ]$ and two messages $(m_0,m_1)$. If $j_i \ge q_e$ or $i \in \textsf {Klist}$, then the challenger returns $\bot$. Otherwise, it generates a ciphertext $\textsf {CT}$ by computing $\textsf {CT}$ $\xleftarrow {\$}$ $\textsf {PKE.Enc}(\textsf {PK}^{(i)},m_\beta )$. Then, it appends $(\textsf {CT},i)$ to $\textsf {Clist}$, updates counter $j_i$ via $j_i = j_i + 1$, and returns $\textsf {CT}$.

  • Corruption queries The adversary submits an index $i \in [\mu ]$. If $(\textsf {CT},i) \in \textsf {Clist}$ for some $\textsf {CT}$, then the challenger returns $\bot$. Otherwise, it returns $\textsf {SK}^{(i)}$ and appends i to $\textsf {Klist}$.

  • Decryption queries The adversary submits a ciphertext $\textsf {CT}$ and an index $i \in [\mu ]$. If $(\textsf {CT},i) \in \textsf {Clist}$, then the challenger returns $\bot$. Otherwise, it returns whatever $\textsf {PKE.Dec}(\textsf {PK}^{(i)}, \textsf {SK}^{(i)}, \textsf {CT})$ returns.

• 3. Eventually, the adversary $\mathcal {A}$ outputs a bit $\beta '$. We say that the adversary $wins$ the game if $\beta =\beta '$.

As in the case of $\textsf {KEM}$, the above security model with $\mu =1$, $q_e=1$, and $q_c=0$ is a standard $\textsf {IND-CCA}$ security model of $\textsf {PKE}$ in a single-user setting. When $\mu \ge 2$ and $q_c=0$, it is equal to the previous $\textsf {MUC}$ model of $\textsf {PKE}$.

Definition 2

Let $\mathcal {A}$ be an adversary that runs in time t, that makes at most $q_e$ encryption queries per user, $q_c$ corruption queries in total, and $q_d$ decryption queries per user, and that wins with probability $1/2 + \epsilon$. Then, we can say that $\mathcal {A}$ breaks the $(\epsilon ,t,\mu ,q_e,q_c,q_d)$-$\textsf {MUC}^+$ security of $\textsf {PKE}$. We say that $\textsf {PKE}$ is $(\epsilon$, t, $\mu$, $q_e$, $q_c$, $q_d)$-$\textsf {MUC}^+$ secure if there exists no such adversary $\mathcal {A}$.

Because of the results by Giacon et al. [16], we note that the standard hybrid $\textsf {KEM}$+$\textsf {DEM}$ encryption paradigm is not enough for the a tightly secure $\textsf {PKE}$ scheme in the $\textsf {MUC}/\textsf {MUC}^+$ model. To construct a tightly secure hybrid encryption scheme in the $\textsf {MUC}^+$ model, we shall use their results. In other words, we apply our proposed $\textsf {KEM}$ approach in the augmented hybrid encryption paradigm [16], which uses the augmented data encapsulation mechanism instead of the standard $\textsf {DEM}$.

4.2 Augmented data encapsulation mechanism

4.2.1 Syntax

An augmented data encapsulation mechanism scheme $\textsf {ADEM}$ = ($\textsf {ADEM.Enc}$, $\textsf {ADEM.Dec}$) consists of two algorithms with a message space $\mathcal {M}$, a tag space $\mathcal {T}$, and a ciphertext space $\mathcal {C}$. The encapsulation algorithm ${\textsf {C}}$ $\leftarrow$ $\textsf {ADEM.Enc}(\textsf {K},\textsf {t},m)$ takes a key $\textsf {K}\in \mathcal {K}$, a tag $\textsf {t} \in \mathcal {T}$, and a message $m \in \mathcal {M}$ as inputs and then outputs a ciphertext ${\textsf {C}}\in \mathcal {C}$. The decapsulation algorithm $\{m,\bot \}$ $\leftarrow$ $\textsf {ADEM.Dec}(\textsf {K},\textsf {t}, {\textsf {C}})$ takes a key $\textsf {K}\in \mathcal {K}$, a tag $\textsf {t} \in \mathcal {T}$, and a ciphertext ${\textsf {C}}\in \mathcal {C}$ as inputs and then outputs either a message $m \in \mathcal {M}$ or the special symbol $\bot \notin \mathcal {M}$. The correctness of $\textsf {ADEM}$ is defined as follows: for all $\textsf {K}\in \mathcal {K}$, $\textsf {t} \in \mathcal {T}$, and $m \in \mathcal {M}$, it is required that $\textsf {ADEM.Dec}(\textsf {K},\textsf {t}, \textsf {ADEM.Enc}(\textsf {K},\textsf {t},m))=m$.

4.2.2 Nonce-based tag multi-instance one-time indistinguishability [16]

The security notion of nonce-based tag multi-instance one-time indistinguishability for $\textsf {ADEM}$ is based on one in which a non-repeating tag is used. The following security experiment, which is a game played between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$, is parameterized by a positive integer N.

• 1. For $i \in [N]$, the challenger samples $\textsf {K}_i$ $\xleftarrow {\$}$ $\mathcal {K}$. Then, it tosses a coin $\beta \xleftarrow {\$}\{0,1\}$ and initializes empty sets $T:= \emptyset$ and ${C}_i := \emptyset$ for each $i \in [N]$.

• 2. The adversary may query the challenger for two types of operations.

  • Encapsulation queries The adversary submits an index $i \in [N]$, a tag $\textsf {t} \in \mathcal {T}$, and two messages $(m_0,m_1)$. If $C_i \ne \emptyset$ or $\textsf {t} \in T$, then the challenger returns $\bot$. Otherwise, it sets $\textsf {t}_i = \textsf {t}$ and $T = T \cup \{ \textsf {t}_i \}$ and generates a ciphertext ${\textsf {C}}\in \mathcal {C}$ by computing ${\textsf {C}}$ $\leftarrow$ $\textsf {ADEM.Enc}(\textsf {K}_i ,\textsf {t}_i ,m_\beta )$. Then, it sets $C_i = C_i \cup \{ {\textsf {C}}\}$ and returns ${\textsf {C}}$.

  • Decapsulation queries The adversary submits an index $i \in [N]$ and a ciphertext ${\textsf {C}}$. If $C_i = \emptyset$ or ${\textsf {C}}\in C_i$, then the challenger returns $\bot$. Otherwise, it returns whatever $\textsf {ADEM.Dec}(\textsf {K}_i, \textsf {t}_i, {\textsf {C}})$ returns.

• 3. Eventually the adversary $\mathcal {A}$ outputs a bit $\beta '$. We say that the adversary $wins$ the game if $\beta =\beta '$.

Definition 3

[N-MIOT-IND security [16]] Let $\mathcal {A}$ be an adversary that runs in time t and wins with probability $1/2 + \epsilon$. Then, we say that $\mathcal {A}$ breaks the $(\epsilon ,t,N)$-$\textsf {MIOT-IND}$ security of $\textsf {ADEM}$. We say that $\textsf {ADEM}$ is $(\epsilon ,t,N)$-$\textsf {N-MIOT-IND}$ secure if there exists no such adversary $\mathcal {A}$.

4.3 Augmented hybrid encryption

• PKE.Gen ($\Pi$): Given parameters $\Pi$, the key generation algorithm runs $(\textsf {PK},\textsf {SK}) \xleftarrow {\$}\textsf {KEM.Gen}$ and returns $(\textsf {PK},\textsf {SK})$.

• PKE.Enc ($\Pi , \textsf {PK}, m$): Given parameters $\Pi$, a public key $\textsf {PK}$, and a message m, the encryption algorithm runs $(\textsf {K}, {\textsf {C}}_1) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK})$. Then, it runs ${\textsf {C}}_2 \leftarrow \textsf {ADEM.Enc}(\textsf {K},{\textsf {C}}_1,m)$ and returns $\textsf {CT}=({\textsf {C}}_1,{\textsf {C}}_2)$.

• PKE.Dec ($\Pi , \textsf {SK}, \textsf {CT}$): Given a secret key $\textsf {SK}$ and a ciphertext $\textsf {CT}= ({\textsf {C}}_1, {\textsf {C}}_2)$, the decryption algorithm runs $\textsf {K}\leftarrow \textsf {KEM.Decap}(\textsf {SK},{\textsf {C}}_1)$. Then, it returns whatever $\textsf {ADEM.Dec}(\textsf {K},{\textsf {C}}_1,{\textsf {C}}_2)$ returns.

Correctness We can simply check that the hybrid encryption is correct if both underlying schemes KEM and ADEM have the correctness.

Security proof Consider the following lemma, which states that augmented hybrid encryption combining a secure $\textsf {KEM}$ scheme in the $\textsf {MUC}$ model and a secure $\textsf {ADEM}$ scheme in the $\textsf {N-MIOT-IND}$ model is a tightly secure $\textsf {PKE}$ scheme in the $\textsf {MUC}$ model.

Lemma 1

[16, Lemma 5.3] Let $\textsf {PKE}$ be the hybrid public key encryption scheme constructed from a $\textsf {KEM}$ and an $\textsf {ADEM}$ schemes as mentioned above. Let p be the maximum ciphertext-collision probability of KEM over all positive public keys. Then, for any number of users $\mu$ and any $\textsf {PKE}$ adversary $\mathcal {A}$ that makes at most $q_e$ encryption queries and $q_d$ decryption queries per user, there exist a $\textsf {KEM}$ adversary $\mathcal {B}$ and an $\textsf {ADEM}$ adversary $\mathcal {C}$ such that

$$\begin{aligned} \epsilon _{\textsf {PKE},\mathcal {A},\mu ,q_e}^\textsf {MUC} \le 2\epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^\textsf {MUC} + \epsilon _{\textsf {ADEM},\mathcal {C},N}^\textsf {N-MIOT-IND} + 2 \left( {\begin{array}{c}N\\ 2\end{array}}\right) p, \end{aligned}$$

where $N=\mu q_e$. $\mathcal {B}$ poses at most $q_e$ encapsulation queries and $q_d$ decapsulation queries per user, and $\mathcal {C}$ poses at most $\mu q_e$ encapsulation queries and $\mu q_e$ decapsulation queries in total.

Note that our proposed $\textsf {MUC}^+$ security notion of $\textsf {PKE}$ and $\textsf {KEM}$ is different from that in the above lemma in that our model allows for corruption queries. The following theorem states that augmented hybrid encryption combining a secure $\textsf {KEM}$ scheme in the $\textsf {MUC}^+$ model and a secure $\textsf {ADEM}$ scheme in the $\textsf {N-MIOT-IND}$ model is a tightly secure $\textsf {PKE}$ scheme in the $\textsf {MUC}^+$ model.

Theorem 3

Let $\textsf {PKE}$ be a hybrid public key encryption scheme constructed from a $\textsf {KEM}$ and an $\textsf {ADEM}$ schemes as mentioned above. Let p be the maximum ciphertext-collision probability of KEM over all positive public keys. Then, for any number of users $\mu$ and any $\textsf {PKE}$ adversary $\mathcal {A}$ that makes at most $q_e$ encryption queries per user, $q_d$ decryption queries per user, and $q_c$ corruption queries in total, there exist a $\textsf {KEM}$ adversary $\mathcal {B}$ and an $\textsf {ADEM}$ adversary $\mathcal {C}$ such that

$$\begin{aligned} \epsilon _{\textsf {PKE},\mathcal {A},\mu ,q_e}^{\textsf {MUC}^+} \le 2\epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^{\textsf {MUC}^+} + \epsilon _{\textsf {ADEM},\mathcal {C},N}^\textsf {N-MIOT-IND} + 2 \left( {\begin{array}{c}N\\ 2\end{array}}\right) p, \end{aligned}$$

where $N=\mu q_e$. $\mathcal {B}$ poses at most $q_e$ encapsulation queries, $q_d$ decapsulation queries per user, and $q_c$ corruption queries in total, and $\mathcal {C}$ poses at most $\mu q_e$ encapsulation queries and $\mu q_e$ decapsulation queries in total.

Proof

We consider a sequence of hybrid games, Game 0,..., Game 5, where Game 0 is the actual $\textsf {MUC}^+$ $\textsf {PKE}$ security game with a fixed coin $\beta =0$ and Game 5 is the same game with a fixed coin $\beta =1$. Let $\textsf {Win}_i$ denote the event that $\mathcal {A}$ wins in Game i.

Game 0 This is the $\textsf {MUC}^+$ $\textsf {PKE}$ security experiment from Definition 2 executed with $\beta = 0$. Thus, the challenger returns $\textsf {CT}$ $= ({\textsf {C}}_1, {\textsf {C}}_2)$, where $(\textsf {K},{\textsf {C}}_1) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK}_i)$ and ${\textsf {C}}_2 \leftarrow \textsf {ADEM.Enc}(\textsf {K},{\textsf {C}}_1,m_0)$ for the encryption query $(i,m_0,m_1)$ only when $j_i < q_e$ and $i \notin \textsf {Klist}$. When asked a corruption query for $i \in [\mu ]$, it returns $\textsf {SK}_i$ from $\textsf {KEM.Gen}$ and appends i to $\textsf {Klist}$ only when $(\textsf {CT},i) \notin \textsf {Clist}$ for any $\textsf {CT}$. When asked a decryption query for $(\textsf {CT}=({\textsf {C}}_1,{\textsf {C}}_2),i)$, if $(\textsf {CT},i) \in \textsf {Clist}$, it returns $\bot$; otherwise, it returns $m \leftarrow \textsf {ADEM.Dec}(\textsf {K},{\textsf {C}}_1,{\textsf {C}}_2)$, where $\textsf {K}$ $\leftarrow$ $\textsf {KEM.Decap}(\textsf {SK}_i,{\textsf {C}}_1)$.

Game 1 This game is identical to Game 0 except that we change the way in which encryption queries are executed. We replace the keys for data encapsulation with randomly chosen keys in $\mathcal {K}$. In other words, the challenger returns $\textsf {CT}$ $= ({\textsf {C}}_1, {\textsf {C}}_2)$, where $(\textsf {K},{\textsf {C}}_1) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK}_i)$, ${\textsf {C}}_2 = \textsf {ADEM.Enc}(\textsf {K}',{\textsf {C}}_1,m_0)$, and $\textsf {K}' \xleftarrow {\$}\mathcal {K}$ for the encryption query $(i,m_0,m_1)$ only when $j_i < q_e$ and $i \notin \textsf {Klist}$. We claim that there exists an adversary $\mathcal {B}$ such that

$$\begin{aligned} |\Pr [\textsf {Win}_1] - \Pr [\textsf {Win}_0]| = \epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^{\textsf {MUC}^+}. \end{aligned}$$

Game 2 This game is identical to Game 1, except that now the encryption oracle operates differently. In this game, the challenger aborts if $\textsf {KEM.Encap}$ generates the same ciphertext ${\textsf {C}}_1$ more than once. Let p be the maximum ciphertext-collision probability of $\textsf {KEM}$. Then, the probability that the challenger aborts during the i-th encryption query is lower-bounded by $(i-1)p$. By summing up all the probabilities for up to $N=\mu q_e$ queries(i.e., $p + 2p + \cdots + (N-1)p$), we have

$$\begin{aligned} |\Pr [\textsf {Win}_2]-\Pr [\textsf {Win}_1]| \le \left( {\begin{array}{c}N\\ 2\end{array}}\right) p. \end{aligned}$$

Game 3 This game is identical to Game 2 except that the challenge ciphertexts are now computed differently. In this game, the challenger encrypts $m_\beta$ with $\beta =1$. In other words, it returns $\textsf {CT}$ $= ({\textsf {C}}_1, {\textsf {C}}_2)$, where $(\textsf {K},{\textsf {C}}_1) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK}_i)$, ${\textsf {C}}_2 = \textsf {ADEM.Enc}(\textsf {K}',{\textsf {C}}_1,m_1)$, and $\textsf {K}' \xleftarrow {\$}\mathcal {K}$ for the encryption query $(i,m_0,m_1)$ only when $j_i < q_e$ and $i \notin \textsf {Klist}$. We claim that there exists an adversary $\mathcal {C}$ such that

$$\begin{aligned} |\Pr [\textsf {Win}_3] - \Pr [\textsf {Win}_2]|=\epsilon _{\textsf {ADEM},\mathcal {C},N}^\textsf {N-MIOT-IND}. \end{aligned}$$

Game 4 This game is identical to Game 3, except that the encryption oracle now operates differently. Now the challenger does not abort even if $\textsf {KEM.Encap}$ generates he same ciphertext ${\textsf {C}}_1$ more than once. Then, just as in Game 1 and Game 2, we have

$$\begin{aligned} |\Pr [\textsf {Win}_4]-\Pr [\textsf {Win}_3]| \le \left( {\begin{array}{c}N\\ 2\end{array}}\right) p. \end{aligned}$$

Game 5 This game is identical to Game 4 except that we change the way in which the encryption queries are executed. We replace the keys randomly chosen in $\mathcal {K}$ with the keys generated by $\textsf {KEM.Encap}$ for data encapsulation. In other words, the challenger returns $\textsf {CT}$ $= ({\textsf {C}}_1, {\textsf {C}}_2)$, where $(\textsf {K},{\textsf {C}}_1) \xleftarrow {\$}\textsf {KEM.Encap}(\textsf {PK}_i)$ and ${\textsf {C}}_2 = \textsf {ADEM.Enc}(\textsf {K},{\textsf {C}}_1,m_1)$ for the encryption query $(i,m_0,m_1)$ only when $j_i < q_e$ and $i \notin \textsf {Klist}$. Then, just as in Game 0 and Game 1, we have

$$\begin{aligned} |\Pr [\textsf {Win}_5] - \Pr [\textsf {Win}_4]| = \epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^{\textsf {MUC}^+}. \end{aligned}$$

Note that Game 5 is identical to the $\textsf {MUC}^+$ $\textsf {PKE}$ security experiment from Definition 2 executed with $\beta = 1$. Then, we have

$$\begin{aligned} |\Pr [\textsf {Win}_{0}]-\Pr [\textsf {Win}_{5}]|= \epsilon _{\textsf {PKE},\mathcal {A},\mu ,q_e}^{\textsf {MUC}^+} \le 2\epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^{\textsf {MUC}^+} + \epsilon _{\textsf {ADEM},\mathcal {C},N}^\textsf {N-MIOT-IND}+ 2\left( {\begin{array}{c}N\\ 2\end{array}}\right) p. \end{aligned}$$

$\square$

Claim 1 The advantage of adversary $\mathcal {B}$ for breaking the $\textsf {MUC}^+$ security of $\textsf {KEM}$ is exactly $|\Pr [\textsf {Win}_1] - \Pr [\textsf {Win}_0]|$.

Proof

Let $\mathcal {A}$ be a distinguisher between Game 1 and Game 0. We now show how to construct an adversary $\mathcal {B}$ for breaking the $\textsf {MUC}^+$ security of $\textsf {KEM}$.

The adversary $\mathcal {B}$ receives the $\mu$ public keys $\{\textsf {PK}^{(i)}\}_{i\in [\mu ]}$ as input, as stated in Definition 1. Then, $\mathcal {A}$ runs as distinguisher by simulating Game 0 with the following changes:

• As the challenger, $\mathcal {B}$ sends $\mu$ public keys $\{\textsf {PK}^{(i)}\}_{i\in [\mu ]}$ to $\mathcal {A}$.

• When asked to resolve an encryption query on $(i,m_0,m_1)$ from $\mathcal {A}$, $\mathcal {B}$ makes an encapsulation query on i and receives $(\textsf {K},{\textsf {C}}_1)$ from its $\textsf {MUC}^+$ $\textsf {KEM}$ challenger. Then, $\mathcal {B}$ sends the challenge ciphertext $\textsf {CT}=({\textsf {C}}_1,{\textsf {C}}_2)$, where ${\textsf {C}}_2$ $\leftarrow$ $\textsf {ADEM.Enc}(\textsf {K},{\textsf {C}}_1,m_0)$. $\mathcal {B}$ lists up encapsulation queries by defining $(\textsf {K},{\textsf {C}}_1,i)\in \textsf {Chlist}$.

• When asked to resolve a corruption query on i from $\mathcal {A}$, $\mathcal {B}$ makes a corruption query on i and receives $\textsf {SK}_i$ from its $\textsf {MUC}^+$ $\textsf {KEM}$ challenger. Then, $\mathcal {B}$ sends a private key for user i to $\mathcal {A}$.

• When asked to resolve a decryption query on $(\textsf {CT}=({\textsf {C}}_1,{\textsf {C}}_2),i)$ from $\mathcal {A}$, $\mathcal {B}$ returns $\textsf {ADEM.Dec}(\textsf {K},{\textsf {C}}_1,{\textsf {C}}_2)$ if there exists a tuple such that $(\textsf {K},{\textsf {C}}_1,i)\in \textsf {Chlist}$. Otherwise, $\mathcal {B}$ makes a decapsulation query on $({\textsf {C}}_1,i)$, and receives $\textsf {K}$ from its challenger, and returns $\textsf {ADEM.Dec}(\textsf {K},{\textsf {C}}_1,{\textsf {C}}_2)$.

Eventually, $\mathcal {A}$ outputs a guess. If the guess is “Game 1”, then $\mathcal {B}$ outputs 0, which means that $\textsf {K}$ is randomly chosen in $\mathcal {K}$; otherwise, it outputs 1.

Note that, in the above simulation, if challenges come from a $\textsf {MUC}^+$ $\textsf {KEM}$ game executed with $\beta =0$ (resp, $\beta =1$), then the challenges transferred to $\mathcal {A}$ are the same as in Game 1 (resp, Game 0). Moreover, it holds that $i \in \textsf {Klist}_{\textsf {KEM},\mathcal {B}}$ when $i \in \textsf {Klist}_{\textsf {PKE},\mathcal {A}}$. Hence, $\mathcal {B}$ can simulate $\mathcal {A}$ without aborting. In other words, the probability of $\mathcal {A}$ distinguishing between Game 0 and Game 1 is exactly same as the probability of $\mathcal {B}$ to win. Therefore, we have

$$\begin{aligned} |\Pr [\textsf {Win}_1]-\Pr [\textsf {Win}_0]| = \epsilon _{\textsf {KEM},\mathcal {B},\mu ,q_e}^{\textsf {MUC}^+}. \end{aligned}$$

$\square$

Claim 2 The advantage of adversary $\mathcal {C}$ for breaking the $\textsf {N-MIOT-IND}$ security of $\textsf {ADEM}$ is exactly $|\Pr [\textsf {Win}_3] - \Pr [\textsf {Win}_2]|$.

Proof

Let $\mathcal {A}$ be a distinguisher between Game 3 and Game 2. We now show how to construct an adversary $\mathcal {C}$ for breaking the $\textsf {N-MIOT-IND}$ security of $\textsf {ADEM}$. The adversary $\mathcal {C}$ runs $\mathcal {A}$ as a distinguisher by simulating Game 2 with the following changes:

• As the challenger, $\mathcal {C}$ initializes an integer $j \leftarrow 0$ and empty sets Clist and Klist.

• When asked to resolve encryption query on $(i,m_0,m_1)$ from $\mathcal {A}$, if $i\in \textsf {Klist}$, then $\mathcal {C}$ aborts. Otherwise, it computes $(\textsf {K},{\textsf {C}}_1) \leftarrow \textsf {KEM.Encap}(\textsf {PK}_i)$, makes an encapsulation query on $(i,{\textsf {C}}_1,m_0,m_1)$, and receives ${\textsf {C}}_2$ from its $\textsf {N-MIOT-IND}$ $\textsf {ADEM}$ challenger. Then, it sets index$[i,{\textsf {C}}_1] \leftarrow j$ and $j \leftarrow j+1$, appends $(\textsf {CT}=({\textsf {C}}_1,{\textsf {C}}_2),i)$ to Clist, and returns challenge ciphertext $\textsf {CT}$ to $\mathcal {A}$.

• When asked to resolve a corruption query on i from $\mathcal {A}$, if $(\textsf {CT},i)\in \textsf {Clist}$ for any $\textsf {CT}$, $\mathcal {C}$ aborts. Otherwise, it returns the private key for user $\textsf {SK}_i$ to $\mathcal {A}$.

• When asked to resolve a decryption query on $(\textsf {CT},i)$ from $\mathcal {A}$, if $(\textsf {CT},i) \in \textsf {Clist}$, $\mathcal {C}$ aborts. Otherwise, if index$[i,{\textsf {C}}_1] \ne \bot$, $\mathcal {C}$ makes an decapsulation query on (index$[i,{\textsf {C}}_1],{\textsf {C}}_2)$, receives m from its $\textsf {ADEM}$ challenger, and returns m to $\mathcal {A}$. Otherwise, it returns whatever $\textsf {ADEM.Dec}(\textsf {K}, {\textsf {C}}_1, {\textsf {C}}_2)$ returns, where $\textsf {K}$ $\leftarrow$ KEM.Decap $(\textsf {SK}_i$, ${\textsf {C}}_1)$.

Eventually $\mathcal {A}$ outputs a guess. If the guess is “Game 3”, then $\mathcal {C}$ outputs $\beta '=1$; otherwise it outputs $\beta '=0$.

Note that, in the above simulation, if challenges come from a $\textsf {N-MIOT-IND}$ $\textsf {ADEM}$ game executed with $\beta =0$ (resp, $\beta =1$), then the challenges transferred to $\mathcal {A}$ are the same as in Game 2 (resp, Game 3). Additionally, the adversary $\mathcal {A}$ makes at most $q_e$ encryption queries per user, which corresponds to at most $\mu q_e$ encapsulation queries. Hence, $\mathcal {C}$ is correctly simulating Game 2 or Game 3 (depending on the bit $\beta$) without any violation of the restrictions on the number of queries. In other words, the probability of $\mathcal {A}$ to distinguish between Game 2 and Game 3 is exactly the same as the probability of $\mathcal {B}$ to win. Therefore, we have

$$\begin{aligned} |\Pr [\textsf {Win}_3]-\Pr [\textsf {Win}_2]| = \epsilon _{\textsf {ADEM},\mathcal {C},\mu q_e}^\textsf {N-MIOT-IND}. \end{aligned}$$

$\square$

Note that the maximum ciphertext-collision probability of our $\textsf {KEM}$ scheme over all public keys is negligible because a random coin for encryption is chosen from $\mathbb {Z}_p^2$.