1.1Background and Motivation

Security against chosen ciphertext attacks (CCA) has been considered as a desirable security notion for public key encryption (PKE) schemes. In order to take adversaries who mount active attacks into consideration, it is desirable that PKE schemes satisfy CCA security. Moreover, since CCA security implies non-malleability [7,18], it is considered that CCA security is strong enough for many applications. Therefore, many standardization bodies for public key cryptography judge whether they include a PKE scheme or not mainly based on whether the scheme satisfies CCA security [28].

On these backgrounds, it has been widely studied how to construct a practical CCA secure PKE scheme [10,19–21,26]. Among them, the constructions proposed by Fujisaki and Okamoto [19,21] are one of the most famous constructions. In [19], Fujisaki and Okamoto showed how to convert any PKE scheme secure against chosen plaintext attacks (CPA) to a PKE scheme which is CCA secure in the random oracle model. Surprisingly, the resulting CCA secure scheme has almost the same efficiency as the underlying CPA secure scheme. Moreover, in [21], they proposed more efficient conversion by using the hybrid encryption framework. EPOC (Efficient PrObabilistiC public-key encryption) that is one of the concrete instantiations of [19,21] has been included by IEEE p1363a [1], as it has high practicality, and moreover, its security can be strictly analyzed.

CCA security has been considered as a standard security notion, but it has recently come to light that there are many situations where even CCA security may not guarantee confidentiality of communication. One typical example is situations where secret keys are encrypted in the system. It is known that there is an encryption scheme which is totally insecure when an adversary can get an encryption of secret keys, even though the scheme satisfies CCA security [16].

Black, Rogaway, and Shrimpton [11] introduced a security notion calledkey dependent message (KDM) security which guarantees confidentiality even in the situation of encrypting secret keys. (Around the same time, Camenisch and Lysyanskaya [15] independently formalized a similar notion called circular security.) It is widely known that when an encryption scheme is used as a building block of complicated systems, encrypting secret keys can often occur. Hard disk encryption systems (e.g., BitLocker [11]) and anonymous credential systems [15] are known as such examples. In addition, from the perspective of symbolic cryptography, KDM security is also important [2,3]. From these facts, we consider that KDM security against chosen ciphertext attacks, that is,\(\text {KDM}\text {-}\text {CCA}\) security is one of the desirable security notions for practical encryption schemes.

Since CCA security is regarded as a desirable security notion, the security of standardized PKE schemes has been analyzed only in the sense of CCA security. Therefore, it is not clear whether these schemes remain secure even when an adversary can get an encryption of secret keys. In modern society where encryption schemes can be used as a building block of complicated systems, and can encrypt secret keys, it is very important to clarify whether standardized schemes are secure also in the sense of\(\text {KDM}\text {-}\text {CCA}\) security.

1.2Our Results

Based on this motivation, in this paper, we clarify whether the constructions proposed by Fujisaki and Okamoto [19,21] satisfy\(\text {KDM}\text {-}\text {CCA}\) security^Footnote1 under exactly the same assumptions on the building blocks as those used in [19,21], and show two results.^Footnote2 Firstly, we show that the construction of [19] (which we call\(\mathsf {FO}_1\)) does not satisfy\(\text {KDM}\text {-}\text {CCA}\) security generally. Secondly, on the other hand, we show that the construction of [21] (which we call\(\mathsf {FO}_2\)) satisfies\(\text {KDM}\text {-}\text {CCA}\) security. More specifically, we prove the following two theorems.

Theorem 1

(Informal). Assume that there exists an\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme. Then, there exists an\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme\(\varPi \) such that the PKE scheme\(\mathsf {FO}_1\) does not satisfy\({\text {KDM-CPA}}\) security in the random oracle model, where\(\mathsf {FO}_1\) is constructed by applying the conversion of [19] to\(\varPi \).

Theorem 2

(Informal). Let\(\varPi \) be a\(\text {OW}\text {-}\text {CPA}\) secure and smooth PKE scheme,\(\varSigma \) be a\({\text {OT-CPA}}\) secure symmetric key encryption scheme, and\(\mathsf {FO}_2\) be the PKE scheme which is constructed by applying the conversion of [21] to\(\varPi \) and\(\varSigma \). Then,\(\mathsf {FO}_2\) satisfies\(\text {KDM}\text {-}\text {CCA}\) security in the random oracle model.

We note that smoothness is a security notion for PKE schemes introduced by Bellare et al. [9], and essentially equivalent to\(\gamma \)-uniformity which is used in [19,21]. We review the definition of smoothness in Sect. 2.

We think it is theoretically very interesting that the construction of [19] does not necessarily satisfy\(\text {KDM}\text {-}\text {CCA}\) security, and on the other hand, that of [21] satisfies\(\text {KDM}\text {-}\text {CCA}\) security, even though these two constructions are closely related. In addition, due to Theorem2, we can construct various practical\(\text {KDM}\text {-}\text {CCA}\) secure PKE schemes in the random oracle model, by applying the construction of [21] to existing\(\text {OW}\text {-}\text {CPA}\) secure PKE schemes and\({\text {OT-CPA}}\) secure symmetric key encryption (SKE) schemes.

The standardized PKE schemes EPOC-1 and EPOC-2 are respectively instantiated by applying the conversion of [19,21] to the PKE scheme proposed by Okamoto and Uchiyama [27]. We note that the counter-example we show in the proof of Theorem1 does not capture the PKE scheme of [27]. Therefore, it is not the case that Theorem1 states that EPOC-1 is insecure in the sense of KDM security. On the other hand, due to Theorem2, we can immediately see that EPOC-2 is\(\text {KDM}\text {-}\text {CCA}\) secure in the random oracle model.

1.3Related Work

Backes et al. [6] showed that RSA-OAEP is secure in the sense of KDM security in the random oracle model. More specifically, they defined a security notion calledadKDM security which takes adaptive corruptions and arbitrary active attacks into consideration, and showed that OAEP is adKDM secure in the random oracle model if the underlying trapdoor permutation satisfies partial domain one-wayness. Recently, Davies and Stam [17] studied KDM security of hybrid encryption in the random oracle model. (Since the construction treated in [17] is associated with the construction of\(\mathsf {FO}_2\), we later refer to their work in detail in Sect. 5).

Boneh et al. [12] constructed the first KDM secure PKE scheme in the standard model under the decisional Diffie-Hellman (DDH) assumption. Their scheme is KDM secure relative to the family of affine functions (affine-KDM secure, for short) which is a comparatively simple function family. Informally, a PKE scheme is said to be KDM secure relative to a function family\(\mathcal {F}\) if the scheme remains secure even when an adversary can get an encryption off(sk), wheresk is the secret key andf is an arbitrary function belonging to\(\mathcal {F}\). Also, affine-KDM secure schemes were later constructed under the learning with errors (LWE) [5], quadratic residuosity (QR) [13], decisional composite residuosity (DCR) [13,25], and learning parity with noise (LPN) [5] assumptions.

Boneh et al.’s scheme is KDM secure only in the CPA setting, and thus how to construct a\(\text {KDM}\text {-}\text {CCA}\) secure scheme remained open. Camenisch et al. [14] later showed how to construct a\(\text {KDM}\text {-}\text {CCA}\) secure scheme using a\({\text {KDM-CPA}}\) secure scheme and a non-interactive zero-knowledge (NIZK) proof system for NP languages as building blocks. Recently, Hofheinz [22] showed the first construction of a circular-CCA secure scheme whose security can be directly proved based on number theoretic assumptions.

Applebaum [4] showed how to construct a PKE scheme which is KDM secure relative to functions computable by a-priori bounded polynomial time, based on a PKE scheme which is KDM secure relative to a simple function family called projection functions. We note that the result of Applebaum works in both of the CPA and the CCA settings. Bellare et al. [8] showed a similar result that works only in the CPA setting but is more efficient than Applebaum’s. Recently, Kitagawa et al. [23] also showed a more efficient result than Applebaum’s, which works in the CCA setting. In addition, Kitagawa et al. [24] showed how to expand the plaintext space of a PKE scheme which is KDM secure relative to projection functions, without using any other assumption.

1.4Outline of the Paper

In Sect. 2, we review the definitions of the primitives and the security notions that we use in this paper. Then, in Sect. 3, we prove Theorem1. In the subsequent sections, we tackle Theorem2. Our idea for proving Theorem2 is simple, but the proof of Theorem2 might look somewhat complicated. Thus, after reviewing the construction of\(\mathsf {FO}_2\) in Sect. 4, in Sect. 5, we first explain the difficulty which we encounter when trying to prove the KDM security of a hybrid encryption scheme whose key derivation function is regarded as a random oracle. Then, in Sect. 6, we prove Theorem2.

In order to help the reader understand the proof of Theorem2, in the full version of this paper, we also show that the hybrid encryption scheme whose key derivation function is a random oracle satisfies\({\text {KDM-CPA}}\) security in the random oracle model, if the underlying PKE scheme and SKE scheme satisfy\(\text {OW}\text {-}\text {CPA}\) security and\({\text {OT-CPA}}\) security, respectively. Since the construction can roughly be seen as a simplification of\(\mathsf {FO}_2\), we believe the proof is relatively easy to understand than that of Theorem2.

In this section we define some notations and cryptographic primitives.

2.1Notations

\(x \xleftarrow {r} X\) denotes choosing an element from a finite setX uniformly at random, and\(y \leftarrow \mathsf {A}(x;r)\) denotes assigningy to the output of an algorithm\(\mathsf {A}\) on an inputx and a randomnessr. When there is no need to write the randomness clearly, we omit it and simply write\(y \leftarrow \mathsf {A}(x)\). For stringsx andy,\(x \Vert y\) denotes the concatenation ofx andy.\(\lambda \) denotes a security parameter. A function\(f(\lambda )\) is a negligible function if\(f(\lambda )\) tends to 0 faster than\(\frac{1}{\lambda ^c}\) for every constant\(c>0\). We write\(f(\lambda ) = \mathsf{negl}(\lambda )\) to denote\(f(\lambda )\) being a negligible function. PPT stands for probabilistic polynomial time.\([\ell ]\) denotes the set of integers\(\{1, \cdots , \ell \}\).\(\mathsf {MSB}_n(x)\) denotes the firstn bits ofx.\(\emptyset \) denotes the empty set.

2.2Public Key Encryption

In this subsection we define public key encryption (PKE).

Definition 1

(Public key encryption). A PKE scheme\(\varPi \) is a three tuple\((\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) of PPT algorithms.

• The key generation algorithm\(\mathsf {KG}\), given a security parameter\(1^\lambda \), outputs a public key\({ pk}\) and a secret key\({ sk}\).

• The encryption algorithm\(\mathsf {Enc}\), given a public key\({ pk}\) and a message\(m \in \mathcal {M}\), outputs a ciphertextc, where\(\mathcal {M}\) is the plaintext space of\(\varPi \).

• The decryption algorithm\(\mathsf {Dec}\), given a secret key\({ sk}\) and a ciphertextc, outputs a message\(\tilde{m} \in \{ \bot \} \cup \mathcal {M}\). This algorithm is deterministic.

Correctness. We require\(\mathsf {Dec}({ sk}, \mathsf {Enc}({ pk}, m)) = m\) for every\(m \in \mathcal {M}\) and\(({ pk}, { sk})\leftarrow \mathsf {KG}(1^\lambda )\).

Next, we define one-wayness against chosen plaintext attacks (\(\text {OW}\text {-}\text {CPA}\) security) for PKE schemes. KDM security, which we define in this subsection, considers situations where there are many users, and thus KDM security is defined via a security game where there are many keys and an adversary can make many challenge queries. Therefore, for our purpose, it is useful to consider the following one-wayness in the multi-user setting. Specifically, we use a security notion which we call\({\text {List-OW-CPA}}\)security. In the security game of\({\text {List-OW-CPA}}\) security, there are many keys, and an adversary can make multiple encryption queries and outputs a list of candidate plaintexts in the final phase.

Definition 2

(List-OW-CPAsecurity). Let\(\varPi \) be a PKE scheme whose message space is\(\mathcal {M}\), and\(\ell \) be the number of keys. We define the\({\text {List-OW-CPA}}\) game between a challenger and an adversary\(\mathcal {A}\) as follows.

• Initialization. First, the challenger generates\(\ell \) key pairs\(({ pk}_j, { sk}_j) \leftarrow \mathsf {KG}(1^\lambda ) (j=1,\cdots , \ell )\). Then, the challenger sends\((pk_1, \cdots , pk_\ell )\) to\(\mathcal {A}\). Finally, the challenger sets\(L_{enc}=\emptyset \).

  \(\mathcal {A}\) may make polynomially many encryption queries.

• Encryption queries.\(j \in [\ell ]\) is an index of a key. The challenger generates\(m \xleftarrow {r}\mathcal {M}\) and computes\(c \leftarrow \mathsf {Enc}({ pk}_j, m)\). Then, the challenger addsm to\(L_{enc}\) and returnsc to\(\mathcal {A}\).

• Final phase.\(\mathcal {A}\) outputs\(L_{ans}\) which is a set of plaintexts. (We require the size of\(L_{ans}\) to be bounded by some polynomial of\(\lambda \).)

In this game, we define the advantage of the adversary\(\mathcal {A}\) as follows.

We say that\(\varPi \) is\({\text {List-OW-CPA}}\) secure if for any PPT adversary\(\mathcal {A}\) and polynomial\(\ell = \ell (\lambda )\), we have.

A\(\text {OW}\text {-}\text {CPA}\) secure PKE scheme\(\varPi \) is also\({\text {List-OW-CPA}}\) secure. Formally, the following lemma holds. We provide the definition of\(\text {OW}\text {-}\text {CPA}\) security and the proof of Lemma1 in AppendixA.

Lemma 1

Let\(\varPi \) be a\(\text {OW}\text {-}\text {CPA}\) secure PKE scheme. Then,\(\varPi \) is alsoList-\(\text {OW}\text {-}\text {CPA}\) secure.

Next, we define\({\text {KDM-CPA}}\) security and\(\text {KDM}\text {-}\text {CCA}\) security for PKE schemes.

Definition 3

(KDM-CPAsecurity). Let\(\varPi \) be a PKE scheme and\(\ell \) be the number of keys. We define the\({\text {KDM-CPA}}\) game between a challenger and an adversary\(\mathcal {A}\) as follows. In the following,\(\mathbf {sk}\) denotes\(({ sk}_1, \cdots , { sk}_\ell )\).

• Initialization. First, the challenger chooses a challenge bit\(b \xleftarrow {r}\{0,1\}\). Next, the challenger generates\(\ell \) key pairs\(({ pk}_j,{ sk}_j) \leftarrow \mathsf {KG}(1^{\lambda })(j=1,\cdots ,\ell )\) and sends\(({ pk}_1, \cdots , { pk}_\ell )\) to\(\mathcal {A}\).\(\mathcal {A}\) may adaptively make polynomially many KDM queries.

• KDM queries. (j, f), wherej is a key index andf is a function. Here,f needs to be efficiently computable. If\(b=1\) then the challenger returns\(c \leftarrow \mathsf {Enc}({ pk}_{j}, f(\mathbf {sk}))\); If\(b=0\) then the challenger returns\(c \leftarrow \mathsf {Enc}({ pk}_{j}, 0^{|f(\cdot )|})\).

• Final phase.\(\mathcal {A}\) outputs\(b' \in \{0,1\}\).

In this game, we define the advantage of the adversary\(\mathcal {A}\) as follows.

We say that\(\varPi \) is\({\text {KDM-CPA}}\) secure if for any PPT adversary\(\mathcal {A}\) and polynomial\(\ell =\ell (\lambda )\), we have.

By permitting the adversary to make decryption queries, we can analogously define\(\text {KDM}\text {-}\text {CCA}\) security.

Definition 4

(KDM-CCAsecurity). Let\(\varPi \) be a PKE scheme and\(\ell \) be the number of keys. We define the\(\text {KDM}\text {-}\text {CCA}\) game between a challenger and an adversary\(\mathcal {A}\) in the same way as the\({\text {KDM-CPA}}\) game except that\(\mathcal {A}\) is allowed to adaptively make decryption queries. In the initialization step of the\(\text {KDM}\text {-}\text {CCA}\) game, the challenger first runs in the same way as the\({\text {KDM-CPA}}\) game, and then, prepares the KDM query list\(L_{kdm}\) into which pairs of the form (j, c) will be stored, wherej is an index andc is a ciphertext, and which is initially empty. When\(\mathcal {A}\) makes a KDM query (j, f), the challenger computes the answerc and adds (j, c) to\(L_{kdm}\).\(\mathcal {A}\) is not allowed to make a decryption query (j, c) which is contained in\(L_{kdm}\).

• Decryption queries.\((j, c) \notin L_{kdm}\), wherej is a key index andc is a ciphertext. For this query, the challenger returns\(m \leftarrow \mathsf {Dec}({ sk}_j, c)\).

In this game, we define the advantage of the adversary\(\mathcal {A}\) analogously to that in the\({\text {KDM-CPA}}\) game. Then,\(\varPi \) is said to be\(\text {KDM}\text {-}\text {CCA}\) secure if for any PPT adversary\(\mathcal {A}\) and polynomial\(\ell =\ell (\lambda )\), we have.

Remarks. lack et al. [11] first defined KDM security. In their paper, they made an assumption that functions which the adversary queries in the security game are length-regular. A functionf is said to be length-regular if the output length of\(f(\mathbf {sk})\) does not depend on the value of\(\mathbf {sk}\), and thus we can uniquely determine the length of\(f(\mathbf {sk})\) only fromf. In this paper, we also impose the length-regularity of functions which the adversary queries in the security game.

In the\({\text {KDM-CPA}}\) game and\(\text {KDM}\text {-}\text {CCA}\) game in the random oracle model, the adversary is allowed to make hash queries to the random oracle. Moreover, it is more appropriate to permit a function which the adversary queries as a KDM query (KDM function) to access to the random oracle, in order to capture more various situations. Actually, Black et al. used the definition which allows KDM functions to access to the random oracle. Therefore, similarly to the definition of Black et al., we allow a KDM function to access to the random oracle.

\(\text {IND}\text {-}\text {CPA}\) security is a special case of\({\text {KDM-CPA}}\) security. More specifically, we can define\(\text {IND}\text {-}\text {CPA}\) security by restricting functions an adversary can query as a KDM query in the\({\text {KDM-CPA}}\) game to any constant functions. Similarly,\(\text {IND}\text {-}\text {CCA}\) security is a special case of\(\text {KDM}\text {-}\text {CCA}\) security.

Usually, KDM security is defined with respect to a function family\(\mathcal {F}\).\(\mathcal {F}\)-KDM security is defined by restricting KDM functions used by an adversary to functions belonging to\(\mathcal {F}\). In this paper, unless stated otherwise, we allow an adversary to query arbitrary function computable in polynomial-time in the security game, and we omit to write a function family.

Next, we review a security notion for PKE schemes calledsmoothness [9]. Informally, a PKE scheme is said to be smooth if the number of possible ciphertexts is super-polynomially large for any message. We note that many known PKE schemes secure in the sense of indistinguishability have smoothness unconditionally, but it is not the case that any\(\text {IND}\text {-}\text {CPA}\) or\(\text {IND}\text {-}\text {CCA}\) secure PKE scheme is smooth. However, we can easily transform any non-smooth PKE scheme to a smooth one. Fujisaki and Okamoto [19,21] proved the security of their scheme via a property called\(\gamma \)-uniformity.\(\gamma \)-uniformity is a slightly stronger security notion than smoothness in the sense that it considers maximum also over all public keys, but these two notions are essentially the same.

Definition 5

(Smoothness [9]). Let\(\varPi \) be a PKE scheme. For\(\lambda \in \mathbb {N}\), we defineSmth as follows.

We say that\(\varPi \) is smooth if we have\(\mathbf{Smth}(\lambda ) = \mathsf{negl}(\lambda )\).

We note that Definition5 is essentially equivalent to the security notion defined via the following game played by a challenger and an adversary\(\mathcal {A}\).

• Initialization. The challenger generates\(\ell \) key pairs\(({ pk}_j,{ sk}_j) \leftarrow \mathsf {KG}(1^{\lambda })(j=1,\cdots ,\ell )\) and sends\((({ pk}_1,sk_1), \cdots , ({ pk}_\ell ,sk_\ell ))\) to\(\mathcal {A}\).

• Final phase.\(\mathcal {A}\) outputs\((j, m, c')\), and the challenger computes\(c \leftarrow \mathsf {Enc}(pk_j,m)\).

In this game, we define the advantage of the adversary\(\mathcal {A}\) as follows.

Then, it is straightforward to see that for any computationally unbounded adversary\(\mathcal {A}\) and polynomial\(\ell =\ell (\lambda )\), we have\(\mathsf{Adv}_{\varPi , \mathcal {A}, \ell }^{smth}(\lambda ) \le \ell \cdot \mathbf{Smth}(\lambda )\). Therefore, if\(\mathbf{Smth}(\lambda )\) is negligible, so is\(\mathsf{Adv}_{\varPi , \mathcal {A}, \ell }^{smth}(\lambda )\) for any computationally unbounded adversary\(\mathcal {A}\) and polynomial\(\ell =\ell (\lambda )\).

2.3Symmetric Key Encryption

In this subsection we define symmetric key encryption (SKE).

Definition 6

(Symmetric key encryption). SKE scheme\(\varSigma \) is a two tuple\((\mathsf {E}, \mathsf {D})\) of PPT algorithms.

• The encryption algorithm\(\mathsf {E}\), given a key\(K \in \{0,1\}^\lambda \) and a message\(m \in \mathcal {M}\), outputs a ciphertextc, where\(\mathcal {M}\) is the plaintext space of\(\varSigma \).

• The decryption algorithm\(\mathsf {D}\), given a keyK and a ciphertextc, outputs a message\(\tilde{m} \in \{ \bot \} \cup \mathcal {M}\). This algorithm is deterministic.

• Correctness. We require\(\mathsf {D}(K, \mathsf {E}(K, m)) = m\) for every\(m \in \mathcal {M}\) and\(K \in \{0,1\}^\lambda \).

Next, we review the definition of indistinguishability against one-time chosen plaintext attacks (\({\text {OT-CPA}}\) security) for SKE schemes.

Definition 7

(OT-CPAsecurity). Let\(\varSigma \) be a SKE scheme whose message space is\(\mathcal {M}\). We define the\({\text {OT-CPA}}\) game between a challenger and an adversary\(\mathcal {A}\) as follows.

• Initialization. First the challenger chooses a challenge bit\(b \xleftarrow {r}\{0,1\}\). Next the challenger generates a key\(K \xleftarrow {r}\{0,1\}^\lambda \) and sends\(1^\lambda \) to\(\mathcal {A}\).

• Challenge.\(\mathcal {A}\) selects two messages\(m_0\) and\(m_1\) of equal length, and sends them to the challenger. Then the challenger returns\(c \leftarrow \mathsf {E}(K, m_b)\).

• Final phase.\(\mathcal {A}\) outputs\(b' \in \{0,1\}\).

In this game, we define the advantage of the adversary\(\mathcal {A}\) as follows.

We say that\(\varSigma \) is\({\text {OT-CPA}}\) secure if for any PPT adversary\(\mathcal {A}\), we have\(\mathsf{Adv}_{\varSigma , \mathcal {A}}^{otcpa}(\lambda ) = \mathsf{negl}(\lambda )\).

The construction [19] of an\(\text {IND}\text {-}\text {CCA}\) secure PKE scheme\(\mathsf {FO}_1=(\mathsf {KG}_\mathsf{FO1},\mathsf {Enc}_\mathsf{FO1},\mathsf {Dec}_\mathsf{FO1})\) from a PKE scheme\(\varPi =(\mathsf {KG},\mathsf {Enc},\mathsf {Dec})\) which is\(\text {IND}\text {-}\text {CPA}\) secure and smooth, and a hash function\(\mathsf {H}\).

Full size image

Fujisaki and Okamoto [19] showed how to transform any\(\text {IND}\text {-}\text {CPA}\) secure (and smooth) PKE scheme to an\(\text {IND}\text {-}\text {CCA}\) secure one by using a random oracle. The resulting scheme has almost the same efficiency as the underlying scheme. In this section, although their construction satisfies\(\text {IND}\text {-}\text {CCA}\) security, we show that their construction generally does not satisfy KDM security. In the following, we first review the construction of [19], and then we show our negative result.

Let\(\varPi = (\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) be a PKE scheme, and\(\mathsf {H}: \{0,1\}^* \rightarrow \{0,1\}^n\) be a hash function, where\(n=n(\lambda )\) is a polynomial. Then, we construct a PKE scheme\(\mathsf {FO}_1 = (\mathsf {KG}_\mathsf{FO1}, \mathsf {Enc}_\mathsf{FO1}, \mathsf {Dec}_\mathsf{FO1})\) as described in Fig. 1. Here, we assume that the plaintext space of\(\varPi \) is\(\{0,1\}^*\), and thus that of\(\mathsf {FO}_1\) is also\(\{0,1\}^*\). In addition, let the randomness spaces of\(\mathsf {Enc}\) and\(\mathsf {Enc}_\mathsf{FO1}\) be both\(\{0,1\}^n\).

In the above construction, Fujisaki and Okamoto showed that if\(\varPi \) is\(\text {IND}\text {-}\text {CPA}\) secure and smooth, and\(\mathsf {H}\) is a random oracle, then\(\mathsf {FO}_1\) is\(\text {IND}\text {-}\text {CCA}\) secure in the random oracle model. However, as mentioned above, we show that\(\mathsf {FO}_1\) does not satisfy\({\text {KDM-CPA}}\) security generally under the same assumptions. Formally, we show the following theorem.

Theorem 3

Assume that there exists an\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme. Then, there exists an\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme\(\varPi \) such that\(\mathsf {FO}_1\) does not satisfy\({\text {KDM-CPA}}\) security in the random oracle model.

Proof of Theorem3. This proof consists of two steps. In the first step, using any\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme, we construct a PKE scheme which is still\(\text {IND}\text {-}\text {CPA}\) secure and smooth, but insecure in the sense of KDM security. Then, in the second step, we show that the PKE scheme which is constructed by applying the conversion of [19] to the PKE scheme we construct in the first step, also does not satisfy\({\text {KDM-CPA}}\) security. In the following, we start with the first step.

Let\(\widehat{\varPi }=(\widehat{\mathsf {KG}}, \widehat{\mathsf {Enc}},\widehat{\mathsf {Dec}})\) be any\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme. Without loss of generality, we assume that the plaintext space of\(\widehat{\varPi }\) is\(\{0,1\}^*\), and the randomness space of\(\widehat{\mathsf {KG}}\) is\(\{0,1\}^s\) for some polynomial\(s=s(\lambda )\). Then, using\(\widehat{\varPi }\), we construct a PKE scheme\(\varPi =(\mathsf {KG},\mathsf {Enc},\mathsf {Dec})\) as described in Fig. 2.

The construction of a PKE scheme\(\varPi =(\mathsf {KG},\mathsf {Enc},\mathsf {Dec})\) which is\(\text {IND}\text {-}\text {CPA}\) secure and smooth but not\({\text {KDM-CPA}}\) secure from an\(\text {IND}\text {-}\text {CPA}\) secure and smooth PKE scheme\(\widehat{\varPi }=(\widehat{\mathsf {KG}}, \widehat{\mathsf {Enc}},\widehat{\mathsf {Dec}})\).

Full size image

It is clear that if\(\widehat{\varPi }\) is\(\text {IND}\text {-}\text {CPA}\) secure and smooth, then\(\varPi \) satisfies the same security notions. The reason is as follows. In the\(\text {IND}\text {-}\text {CPA}\) game regarding\(\varPi \), since a PPT adversary can find the randomness that was used to run\(\widehat{\mathsf {KG}}\) with negligible probability, when the challenger generates the challenge ciphertext,\(\mathsf {Enc}\) outputs a ciphertext whose first bit is 1 with negligible probability. Thus, if\(\widehat{\varPi }\) satisfies\(\text {IND}\text {-}\text {CPA}\), then so is\(\varPi \). Moreover, regardless of the plaintext, a ciphertext output by\(\mathsf {Enc}\) includes a ciphertext output by\(\widehat{\mathsf {Enc}}\) itself, and thus\(\varPi \) is smooth if so is\(\widehat{\varPi }\). On the other hand,\(\varPi \) does not satisfy\({\text {KDM-CPA}}\) security. In order to show it, we consider the following adversary\(\mathcal {A}\) which attacks the\({\text {KDM-CPA}}\) security of\(\varPi \). For simplicity, we consider the case where only one key pair exists. On inputpk,\(\mathcal {A}\) queries the identity functionid, gets the answer\(p\Vert c\), and outputs\(b'=p\). Letb be the challenge bit in the\({\text {KDM-CPA}}\) game between the challenger and\(\mathcal {A}\). Then, we can estimate the advantage of\(\mathcal {A}\) as follows.

Here, letsk be the secret key corresponding topk. Then,sk is chosen from\(\{0,1\}^s\) at random and\(pk=\widehat{pk}\), where\((\widehat{pk},\widehat{sk}) = \widehat{\mathsf {KG}}(1^\lambda ;sk)\). In addition, let\(m_1=sk\) and\(m_0=0^s\). Then, we note that for any\(b \in \{0,1\}\), the probability thatp equals 1 is the same as the probability that\(pk=pk'\) holds, where\((pk',sk') = \widehat{\mathsf {KG}}(1^\lambda ;m_b)\). We note that these probabilities are taken over the choice ofsk. When\(b=1\), it is straightforward that\(pk=pk'\) always holds, and thus we have\(\Pr [p=1|b=1]=1\). On the other hand, when\(b=0\),\(pk=pk'\) occurs only with negligible probability. The reason is as follows. If\(pk=pk'\) holds, by the correctness of\(\widehat{\varPi }\),\(\widehat{\mathsf {Dec}}(sk',\widehat{\mathsf {Enc}}(pk,m))=m\) holds for any\(m \in \{0,1\}^*\). Therefore, if\(pk=pk'\) holds with non-negligible probability, an adversary can break the\(\text {IND}\text {-}\text {CPA}\) security of\(\widehat{\varPi }\) by generating\((pk',sk') \leftarrow \widehat{\mathsf {KG}}(1^\lambda ;0^s)\) and decrypting the challenge ciphertext using\(sk'\). This is a contradiction, and thus we have\(\Pr [p=1|b=0]=\mathsf{negl}(\lambda )\). From these, we have\(\mathsf{Adv}_{\varPi , \mathcal {A},1}^{kdmcpa}(\lambda )=\frac{1}{2}(1-\mathsf{negl}(\lambda )\)), and we see that\(\varPi \) does not satisfy\({\text {KDM-CPA}}\) security.

Next, we construct a PKE scheme\(\mathsf {FO}_1=(\mathsf {KG}_\mathsf{FO1},\mathsf {Enc}_\mathsf{FO1},\mathsf {Dec}_\mathsf{FO1})\) by applying the conversion in Fig. 1 to the above\(\varPi \), and show that\(\mathsf {FO}_1\) also does not satisfy\({\text {KDM-CPA}}\) security. Let (pk, sk) be a key pair output by\(\mathsf {KG}_\mathsf{FO1}\). Here, a key pair of\(\mathsf {FO}_1\) is a key pair of\(\varPi \) itself. Namely,sk is randomly chosen from\(\{0,1\}^s\) and\(pk=\widehat{pk}\), where\((\widehat{pk},\widehat{sk}) \leftarrow \widehat{\mathsf {KG}}(1^\lambda ;sk)\). Then, for any\(m \in \{0,1\}^s\), the probability that the first bit of the result of\(\mathsf {Enc}_\mathsf{FO1}(pk,m)\) equals 1 is the same as the probability that\(pk=pk'\) holds, where\((pk',sk')=\widehat{\mathsf {KG}}(1^\lambda ;\mathsf {MSB}_s(m\Vert r))=\widehat{\mathsf {KG}}(1^\lambda ;m)\) andr is a randomness generated in\(\mathsf {Enc}_\mathsf{FO1}\). These probabilities are over the choice of the random oracle\(\mathsf {H}\), (pk, sk), and\(r \in \{0,1\}^n\). Therefore, if\(m=sk\), the first bit of\(\mathsf {Enc}_\mathsf{FO1}(pk,m;r)\) always equals 1. One the other hand, ifm does not depend onsk, similarly to the first step, the first bit of\(\mathsf {Enc}_\mathsf{FO1}(pk,m;r)\) equals 1 only with negligible probability. From these,\(\mathsf {FO}_1\) does not satisfy\({\text {KDM-CPA}}\) security.    \(\square \) (Theorem3)

Fujisaki and Okamoto [21] showed how to construct an\(\text {IND}\text {-}\text {CCA}\) secure PKE scheme in the random oracle model (which we call\(\mathsf {FO}_2\)) using a\(\text {OW}\text {-}\text {CPA}\) secure PKE scheme and a\({\text {OT-CPA}}\) secure SKE scheme. In this section, we show that\(\mathsf {FO}_2\) also satisfies\(\text {KDM}\text {-}\text {CCA}\) security in the random oracle model, under exactly the same assumptions on the building blocks as those used in [21]. First, we review the construction of\(\mathsf {FO}_2\).

Let\(\varPi =(\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) be a PKE scheme and\(\varSigma =(\mathsf {E}, \mathsf {D})\) be a SKE scheme. Here, we assume that the message space and the randomness space of\(\varPi \) are\(\{0,1\}^\lambda \) and\(\{0,1\}^n\), respectively, where\(n=n(\lambda )\) is a polynomial. Moreover, we also assume that the message space and the key space of\(\varSigma \) are\(\{0,1\}^*\) and\(\{0,1\}^\lambda \), respectively. In addition, let\(\mathsf {H}: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^{n}\) and\(\mathsf {G}: \{0,1\}^* \rightarrow \{0,1\}^{\lambda }\) be hash functions. Then, we construct a PKE scheme\(\mathsf {FO}_2=(\mathsf {KG}_\mathsf{FO2}, \mathsf {Enc}_\mathsf{FO2},\mathsf {Dec}_\mathsf{FO2})\) as described in Fig. 3. Here, we note that the message space of\(\mathsf {FO}_2\) is\(\{0,1\}^*\).

[21] showed that, by regarding\(\mathsf {H}\) and\(\mathsf {G}\) as random oracles, if\(\varPi \) is\(\text {OW}\text {-}\text {CPA}\) secure and smooth, and\(\varSigma \) is\({\text {OT-CPA}}\) secure, then\(\mathsf {FO}_2\) satisfies\(\text {IND}\text {-}\text {CCA}\) security in the random oracle model. As mentioned earlier, we show that\(\mathsf {FO}_2\) satisfies\(\text {KDM}\text {-}\text {CCA}\) security, even though we require exactly the same assumptions for building blocks as those used in [21]. Formally, we show the following theorem.

The construction [21] of a PKE scheme\(\mathsf {FO}_2=(\mathsf {KG}_\mathsf{FO2},\mathsf {Enc}_\mathsf{FO2},\mathsf {Dec}_\mathsf{FO2})\) from a PKE scheme\(\varPi =(\mathsf {KG},\mathsf {Enc},\mathsf {Dec})\) and a SKE scheme\(\varSigma =(\mathsf {E},\mathsf {D})\).

Full size image

Theorem 4

Let\(\varPi \) be a PKE scheme which is\(\text {OW}\text {-}\text {CPA}\) secure and smooth,\(\varSigma \) be a\({\text {OT-CPA}}\) secure SKE scheme, and\(\mathsf {H}\) and\(\mathsf {G}\) be random oracles. Then,\(\mathsf {FO}_2\) is a PKE scheme which is\(\text {KDM}\text {-}\text {CCA}\) secure in the random oracle model.

Our idea for proving the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\) is conceptually simple. However, unfortunately, our security proof might look somewhat complicated. Thus, in this section, we first explain where the difficulty lies and how we overcome it when showing the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\).

The difficulty.\(\mathsf {FO}_2\) has a somewhat complicated structure at first glance. However, it can roughly be seen as a hybrid encryption scheme\(\varPi _\mathsf{hyb}\) which has the following encryption algorithm\(\mathsf {Enc}_\mathsf{hyb}\).

Here, similarly to\(\mathsf {FO}_2\),\(\varPi =(\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) and\(\varSigma =(\mathsf {E},\mathsf {D})\) are a\(\text {OW}\text {-}\text {CPA}\) secure PKE scheme and a\({\text {OT-CPA}}\) secure SKE scheme, respectively, and\(\mathsf {G}\) is a random oracle. The difficulty that lies in the security proof of the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\), is almost the same as that of the\({\text {KDM-CPA}}\) security of\(\varPi _\mathsf{hyb}\). Therefore, for simplicity, we explain the difficulty we encounter when showing the\({\text {KDM-CPA}}\) security of\(\varPi _\mathsf{hyb}\) in the case where only one key pair (pk, sk) exists. In the following, we call a function an adversary queries as a KDM query in the security game a KDM function. In addition, we call an answer to a KDM query a challenge ciphertext, and randomnessr encapsulated by\(\mathsf {Enc}\) a proto-key.

We first consider a simple case, that is, the case where KDM functions cannot access to the random oracle\(\mathsf {G}\). In this case, an adversary who does not query a proto-keyr to\(\mathsf {G}\) cannot distinguish\((\mathsf {Enc}(pk, r), \mathsf {E}(\mathsf {G}(r),f(sk)))\) and\((\mathsf {Enc}(pk,r), \mathsf {E}(\mathsf {G}(r),0^{|f(\cdot )|}))\) due to the randomness of outputs of\(\mathsf {G}\) and the\({\text {OT-CPA}}\) security of\(\varSigma \), wheref is a KDM function. Thus, all we have to consider is whether the adversary can query the proto-keyr to\(\mathsf {G}\), but it is unlikely because of the\(\text {OW}\text {-}\text {CPA}\) security of\(\varPi \). From these, in this case, we can easily see that\(\varPi _\mathsf{hyb}\) is\({\text {KDM-CPA}}\) secure.

However, in the case where KDM functions can access to the random oracle\(\mathsf {G}\), there is a problem. The problem is that an adversary who makes multiple KDM queries can get an encryption of a proto-keyr which was used to compute a past challenge ciphertext. In order to take a closer look at this problem, we consider the reduction from the\({\text {KDM-CPA}}\) security of\(\varPi _\mathsf{hyb}\) to the\({\text {OT-CPA}}\) security of\(\varSigma \). For simplicity, we consider an adversary\(\mathcal {A}\) who makes only two KDM queries in the\({\text {KDM-CPA}}\) game of\(\varPi _\mathsf{hyb}\). Let\(f_1\) and\(f_2\) be the KDM functions that\(\mathcal {A}\) sends, andb denote the challenge bit between the challenger and\(\mathcal {A}\). Then, consider the sequence of games as described in Fig. 4.

The ordinary sequence of games. “1st” and “2nd” indicate the answers to the first and second KDM queries from\(\mathcal {A}\), respectively.

Full size image

Game [\(b=1\)] and Game [\(b=0\)] correspond to the\({\text {KDM-CPA}}\) game when\(b=1\) and\(b=0\), respectively. If the behavior of\(\mathcal {A}\) does not change non-negligibly between Game [\(b=1\)] and Game [\(b=0\)], then we can conclude that\(\varPi _\mathsf{hyb}\) is\({\text {KDM-CPA}}\) secure. In order to show this by using the\({\text {OT-CPA}}\) security of\(\varSigma \), we typically consider a hybrid game Game [hybrid], and we show that the behavior of\(\mathcal {A}\) does not change between Game[\(b=1\)] and Game [hybrid], and between Game [hybrid] and Game [\(b=0\)].

Then, we try to construct an adversary\(\mathcal {B}\) who simulates Game [\(b=1\)] or Game [hybrid] for\(\mathcal {A}\) according to the value of the challenge bit between\(\mathcal {B}\) and the challenger of the\({\text {OT-CPA}}\) game regarding\(\varSigma \).\(\mathcal {B}\) first generates (pk, sk) using\(\mathsf {KG}\) and sendspk to\(\mathcal {A}\).\(\mathcal {B}\) simulates\(\mathsf {G}\) by lazy sampling. For the first KDM query\(f_1\) from\(\mathcal {A}\),\(\mathcal {B}\) first makes the challenge query\((f_1^\mathsf {G}(sk),0^{|f_1(\cdot )|})\) and gets the answer\(d_1\). Then,\(\mathcal {B}\) generates a proto-key\(r_1\), computes\(c_1\leftarrow \mathsf {Enc}(pk,r_1)\), and returns\((c_1,d_1)\) to\(\mathcal {A}\). In addition,\(\mathcal {B}\) let the value of\(\mathsf {G}(r_1)\) be the value of the key of\(\varSigma \) that the challenger used to compute\(d_1\). We note that\(\mathcal {B}\) does not know the actual value of the key of\(\varSigma \). Here, suppose that\(\mathcal {A}\) sends the following KDM function\(f_2\) as the second KDM query.\(f_2^\mathsf {G}(sk)\) computes\(r_1=\mathsf {Dec}(sk,c_1)\), and then computes\(\mathsf {G}(r_1)\) and returns the value. Then, in order to compute the value of\(f_2^\mathsf {G}(r_1)\),\(\mathcal {B}\) needs the value of\(\mathsf {G}(r_1)\). However,\(\mathcal {B}\) does not know the actual value of\(\mathsf {G}(r_1)\), and thus cannot compute\(f_2^\mathsf {G}(sk)\) correctly. Therefore,\(\mathcal {B}\) fails a simulation of Games for\(\mathcal {A}\) if\(\mathcal {A}\) queries such a second KDM query.

The approach of Davies and Stam [17]. Davies and Stam [17] studied KDM security for hybrid encryption where the key derivation function (KDF) is regarded as a random oracle, and pointed out the above problem.^Footnote3 Then, they overcame the problem and showed that if a PKE scheme satisfies\(\text {OW}\text {-}\text {CCA}\) security and a SKE scheme satisfies\(\text {OT}\text {-}\text {CCA}\) security, the hybrid encryption scheme satisfies\(\text {KDM}\text {-}\text {CCA}\) security in the random oracle model.

They approached the above problem by introducing a new security notion for SKE schemes that they callprior key dependent message security (\(\text {PKDM}\) security). Informally,\(\text {PKDM}\) security guarantees that an encryption scheme can securely encrypt a message which depends only on keys of the scheme used to generate past ciphertexts. In other words, confidentiality of a ciphertext of a\(\text {PKDM}\) secure scheme under a key\(K_i\) holds even if an adversary can get an encryption of the form\(\mathsf {E}(K_i,f(K_1,\cdots ,K_{i-1}))\), where\(K_1,\cdots ,K_{i-1}\) are keys used so far andf is an arbitrary function. Davies and Stam showed that\(\text {PKDM}\text {-}\text {CCA}\) security is equivalent to\(\text {OT}\text {-}\text {CCA}\) security, and they overcame the above problem by reducing the\(\text {KDM}\text {-}\text {CCA}\) security of the hybrid encryption scheme to the\(\text {PKDM}\text {-}\text {CCA}\) security of the SKE scheme.

To accomplish this task, their reduction algorithm has to convert a KDM function of the secret keys of the PKE scheme to that of the keys of the SKE scheme. Here, in the\(\text {KDM}\text {-}\text {CCA}\) game which the reduction algorithm simulates, there exists a random oracle. On the other hand, in the\(\text {PKDM}\text {-}\text {CCA}\) game which the reduction algorithm actually plays, there does not exist a random oracle. Therefore, Davies and Stam used the technique of replacing the random oracle with a pseudorandom functions (PRF) when conducting the above conversion of KDM functions. Therefore, their security bound has a PRF term even though the construction does not include a PRF. In addition, they stated that it is difficult to prove its\(\text {KDM}\text {-}\text {CCA}\) security without using\(\text {PKDM}\) security or a PRF.

Our approach. Both our work and the work of [17] study the\(\text {KDM}\text {-}\text {CCA}\) security of the hybrid encryption scheme whose KDF is regarded as a random oracle. However, there is a big difference between our work and [17]. The difference is that the building blocks of [17] already satisfy CCA security. On the other hand, the building blocks of\(\mathsf {FO}_2\) that we treat satisfy only CPA security. In order to prove the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\) even though the building blocks satisfy only CPA security, similarly to Fujisaki and Okamoto [21], we have to use smoothness [9]. (As mentioned in Sect. 2, smoothness is essentially the same notion as\(\gamma \)-uniformity.) In addition, the construction of\(\mathsf {FO}_2\) contains two random oracles, and one of them is used to generate a randomness for the encryption algorithm of the PKE scheme. Thus, it looks difficult to replace both of two random oracles with a PRF, and thus, to directly use the proof technique used in [17]. Therefore, we try to prove the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\) by a proof technique which is different from that of [17], especially a technique without using PKDM security or a PRF. In the following, we give our main idea using\(\varPi _\mathsf{hyb}\).

As earlier, we consider an adversary\(\mathcal {A}\) for the\({\text {KDM-CPA}}\) security of\(\varPi _\mathsf{hyb}\) who makes a KDM query only twice. Our idea is to replace the challenge ciphertexts in “reverse order”. Namely, we consider the sequence of games as described in Fig. 5.

The sequence of games which replace the challenge ciphertexts in the “reverse order”.

Full size image

Then, we can avoid the problem that we explained above. We try to construct an adversary\(\mathcal {B}\) who simulates Game [\(b=1\)] or Game [reverse] for\(\mathcal {A}\) according to the value of the challenge bit between\(\mathcal {B}\) and the challenger of the\({\text {OT-CPA}}\) game regarding\(\varSigma \).\(\mathcal {B}\) first generates (pk, sk) using\(\mathsf {KG}\) and sendspk to\(\mathcal {A}\). For the first KDM query\(f_1\) from\(\mathcal {A}\),\(\mathcal {B}\) generates a proto-key\(r_1\) and a key\(K_1\) of\(\varSigma \), and returns\((\mathsf {Enc}(pk,r_1),\mathsf {E}(K_1,f_1^\mathsf {G}(sk)))\). In addition,\(\mathcal {B}\) defines the value of\(\mathsf {G}(r_1)\) as\(K_1\) by itself. For the second KDM query\(f_2\) from\(\mathcal {A}\),\(\mathcal {B}\) makes the challenge query\((f_2^\mathsf {G}(sk),0^{|f_2(\cdot )|})\) and gets the answer\(d_2\). Then,\(\mathcal {B}\) generates a proto-key\(r_2\), computes\(c_2 \leftarrow \mathsf {Enc}(pk,r_2)\), and returns\((c_2,d_2)\) to\(\mathcal {A}\). Since\(\mathcal {B}\) defines the value of\(\mathsf {G}(r_1)\) by itself,\(\mathcal {B}\) can simulate\(\mathsf {G}\) for\(f_2\) and compute\(f_2^\mathsf {G}(sk)\) correctly even if\(f_2\) calls\(\mathsf {G}\).

Then, we in turn try to construct an adversary\(\mathcal {B}'\) who simulates Game [reverse] or Game [\(b=0\)] for\(\mathcal {A}\) according to the value of the challenge bit between\(\mathcal {B}'\) and the challenger of the\({\text {OT-CPA}}\) game regarding\(\varSigma \).\(\mathcal {B}'\) also generates (pk, sk) using\(\mathsf {KG}\) and sendspk to\(\mathcal {A}\). For the first KDM query\(f_1\) from\(\mathcal {A}\),\(\mathcal {B}'\) first makes the challenge query\((f_1^\mathsf {G}(sk),0^{|f_1(\cdot )|})\) and gets the answer\(d_1\). Then,\(\mathcal {B}'\) generates a proto-key\(r_1\), computes\(c_1\leftarrow \mathsf {Enc}(pk,r_1)\), and returns\((c_1,d_1)\) to\(\mathcal {A}\). Here,\(\mathcal {B}'\) let the value of\(\mathsf {G}(r_1)\) be the value of the key of\(\varSigma \) that the challenger used to compute\(d_1\), and thus\(\mathcal {B}\) does not know the value of\(\mathsf {G}(r_1)\). However, in this case,\(\mathcal {B}'\) does not need the value of\(\mathsf {G}(r_1)\) to respond to the second KDM query because the answer to this query is an encryption of\(0^{|f_2(\cdot )|}\), and thus\(\mathcal {B}'\) does not have to compute\(f_2^\mathsf {G}(sk)\) actually. We note that since KDM functions are length regular,\(\mathcal {B}'\) can know\(|f_2(\cdot )|\) without computing\(f_2^\mathsf {G}(sk)\). Therefore, we can overcome the problem that KDM functions may refer to past proto-keys by replacing the challenge ciphertexts in the reverse order.

When we prove the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\), we have to take the\(\text {OW}\text {-}\text {CPA}\) security and smoothness of the building block PKE scheme into consideration, and then we use the identical-until-bad technique and the deferred analysis technique. Hence, in this case, whether a KDM function is computed actually or not is very sensitive, but by dividing the bad events into smaller pieces than Davies and Stam, we are able to complete the proof.

In this section, we show the formal proof of Theorem4.

Let\(\mathcal {A}\) be an adversary that attacks the\(\text {KDM}\text {-}\text {CCA}\) security of\(\mathsf {FO}_2\) in the random oracle model, and makes at most\(q_e\) KDM queries and\(q_d\) decryption queries, where\(q_e\) and\(q_d\) are polynomials of\(\lambda \). Let\(\ell \) be a polynomial of\(\lambda \) and denote the number of keys. As mentioned just after Definition4, similarly to Black et al. [11], we assume that a function which\(\mathcal {A}\) queries as a KDM query can access to the random oracles, and is length-regular. We note that since KDM functions can access to the random oracle, it makes security proof simple to clearly distinguish the entries of the hash list used to compute KDM functions and that used to make challenge ciphertexts. Thus, we divide the random oracle into multiple random oracles, which is a technique used by Davies and Stam [17]. Namely, in our sequence of games, there are six random oracles even though the construction of\(\mathsf {FO}_2\) contains only two random oracles. Now, consider the following sequence of games.

• Game 0. This is the\(\text {KDM}\text {-}\text {CCA}\) game in the random oracle model regarding\(\mathsf {FO}_2\). See Fig. 6 for how KDM queries and decryption queries are answered, and how random oracles behave in Game 0. In the original\(\text {KDM}\text {-}\text {CCA}\) game regarding\(\mathsf {FO}_2\), there exist only two random oracles\(\mathsf {H}\) and\(\mathsf {G}\). However, to define the subsequent games, we consider six random oracles\(\mathsf {H}\),\(\mathsf {H}^*\),\(\mathsf {H}\mathsf {H}^*\),\(\mathsf {G}\),\(\mathsf {G}^*\), and\(\mathsf {G}\mathsf {G}^*\). Moreover, random oracles are implemented by lazy sampling. More specifically, random oracles run as follows.

• \(\mathsf {H}\) maintains the list\(L_\mathsf{H}\) which stores query/answer pairs so far, and runs as follows. If some value (r, d) is queried to\(\mathsf {H}\),\(\mathsf {H}\) first checks whether there is an entry of the form ((r, d), R) in\(L_\mathsf{H}\). If so,\(\mathsf {H}\) returnsR. Otherwise,\(\mathsf {H}\) returns a fresh random valueR and adds ((r, d), R) to\(L_\mathsf{H}\).

• \(\mathsf {H}^*\),\(\mathsf {G}\), and\(\mathsf {G}^*\) also maintain the query/answer pairs list\(L_\mathsf{H^*}\),\(L_\mathsf{G}\), and\(L_\mathsf{G^*}\), respectively, and run in the same way as\(\mathsf {H}\).

• Similarly to the other random oracles,\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\) are implemented by lazy sampling. However,\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\) do not have their own list. When\(\mathsf {H}\mathsf {H}^*\) samples a fresh random value,\(\mathsf {H}\mathsf {H}^*\) adds a new entry to\(L_\mathsf{H}\), and when\(\mathsf {G}\mathsf {G}^*\) samples a fresh random value,\(\mathsf {G}\mathsf {G}^*\) adds a new entry to\(L_\mathsf{G}\). In addition,\(\mathsf {H}\mathsf {H}^*\) runs by referring to both lists\(L_\mathsf{H}\) and\(L_\mathsf{H^*}\), and\(\mathsf {G}\mathsf {G}^*\) runs by referring to both lists\(L_\mathsf{G}\) and\(L_\mathsf{G^*}\).

Moreover, in this game,\(\mathsf {H}\) and\(\mathsf {H}^*\) are synchronized. Namely,\(\mathsf {H}\) and\(\mathsf {H}^*\) refer to not only their own list but also the list of the other one. Similarly,\(\mathsf {G}\) and\(\mathsf {G}^*\) are synchronized. In this game, random oracles are called at the following four cases.

• (1) When\(\mathcal {A}\) makes a hash query.

• (2) When the challenger computes a hash value to respond to a KDM query from\(\mathcal {A}\).

• (3) When a function which\(\mathcal {A}\) sends to the challenger as a KDM query accesses to the random oracles.

• (4) When the challenger computes a hash value to respond to a decryption query from\(\mathcal {A}\).

\(\mathsf {H}\) and\(\mathsf {G}\) are used when(1),\(\mathsf {H}^*\) and\(\mathsf {G}^*\) are used when(2), and\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\) are used when(3) and(4). Then, we note that the difference between this game and the original\(\text {KDM}\text {-}\text {CCA}\) game is only conceptual.

The manner the challenger responds to a KDM query and a decryption query, and the behavior of\(\mathsf {H}\),\(\mathsf {H}^*\),\(\mathsf {G}\), and\(\mathsf {G}^*\) in Game 0. We note that in Game 0,\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\) run in exactly the same way as\(\mathsf {H}\) and\(\mathsf {G}\), respectively.

Full size image

• Game 1. Same as Game 0, except for the behaviors of\(\mathsf {H}^*\) and\(\mathsf {G}^*\). In this game,\(\mathsf {H}^*\) runs without referring to\(L_\mathsf{H}\). Moreover, every time\(\mathsf {H}^*\) is given an input\((r,d) \in \{0,1\}^\lambda \times \{0,1\}^*\),\(\mathsf {H}^*\) generates a uniformly random valueR over\(\{0,1\}^n\). Then,\(\mathsf {H}^*\) outputsR after adding ((r, d), R) to\(L_\mathsf{H^*}\) even if there already exists an entry whose first component is (r, d) in\(L_\mathsf{H^*}\). We note that\(\mathsf {H}\) and\(\mathsf {H}\mathsf {H}^*\) still refer to\(L_\mathsf{H^*}\) in this game. When\(\mathsf {H}\) and\(\mathsf {H}\mathsf {H}^*\) refer to\(L_\mathsf{H^*}\), if there are multiple entries whose first components are identical, then\(\mathsf {H}\) and\(\mathsf {H}\mathsf {H}^*\) adopt the entry which was added first.\(\mathsf {G}\),\(\mathsf {G}^*\), and\(\mathsf {G}\mathsf {G}^*\) run analogously to\(\mathsf {H}\),\(\mathsf {H}^*\), and\(\mathsf {H}\mathsf {H}^*\), respectively. See Fig. 7 for how\(\mathsf {H}^*\) and\(\mathsf {G}^*\) behave in Game 1.

• Game 2. Same as Game 1, except that\(\mathsf {H}\) runs without referring to\(L_\mathsf{H^*}\), and\(\mathsf {G}\) runs without referring to\(L_\mathsf{G^*}\). Here, we note that\(\mathsf {H}\mathsf {H}^*\) still refers to both\(L_\mathsf{H}\) and\(L_\mathsf{H^*}\), and\(\mathsf {G}\mathsf {G}^*\) also refers to both\(L_\mathsf{G}\) and\(L_\mathsf{G^*}\). See Fig. 8 for how\(\mathsf {H}\) and\(\mathsf {G}\) behave in Game 2.

• Game 3. Same as Game 2, except that if\(\mathcal {A}\) makes a decryption query, then the challenger responds as described in Fig. 9. We note that, due to this change, the challenger can respond to a decryption query without using the secret keys in this and subsequent games.

• Game 4. Same as Game 3, except that if\(\mathcal {A}\) makes a decryption query, the challenger refers to only\(L_\mathsf{H}\) instead of\(L_\mathsf{H}\cup L_\mathsf{H^*}\) when checking the validity of the ciphertext from\(\mathcal {A}\), and uses\(\mathsf {G}\) instead of\(\mathsf {G}\mathsf {G}^*\) to compute the answer. See Fig. 10.

• Game 5. Same as Game 4, except that if\(\mathcal {A}\) makes a KDM query (j, f), the challenger always returns a ciphertext whose plaintext is\(0^{|f(\cdot )|}\). See Fig. 11.

The above completes the description of the games.

The behavior of\(\mathsf {H}^*\) and\(\mathsf {G}^*\) in Game 1.

Full size image

The behavior of\(\mathsf {H}\) and\(\mathsf {G}\) in Game 2.

Full size image

The manner the challenger responds to a decryption query in Game 3.

Full size image

The manner the challenger responds to a decryption query in Game 4.

Full size image

The manner the challenger responds to a KDM query in Game 5.

Full size image

We define the following events in Gamei (\(i=0,\cdots , 5\)).

• SUC\(_i\):\(\mathcal {A}\) succeeds in guessing the challenge bit, that is,\(b=b'\) occurs.

• \({{{\mathbf {\mathtt{{COL}}}}}}_i\): When the challenger generates\(r \leftarrow \{0,1\}^\lambda \) to respond to a KDM query from\(\mathcal {A}\), there exists an entry of the form\((r,\cdot )\) in\(L_\mathsf{G}\cup L_\mathsf{G^*}\), or there exists an entry of the form\(((r,\cdot ),\cdot )\) in\(L_\mathsf{H}\).

• \({{{\mathbf {\mathtt{{BHQ}}}}}}_i\): When\(\mathcal {A}\) queriesr to\(\mathsf {G}\) or queries (r, d) to\(\mathsf {H}\), there exists an entry of the form\((r,\cdot )\) in\(L_\mathsf{G^*}\). We call such a hash query a “bad hash query”.

In addition, we define the following two events related to decryption queries.

• \({{{\mathbf {\mathtt{{SMTH}}}}}}_i\):\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) which satisfies the following two conditions, where\(\mathsf {Dec}(sk_j,c)=r\): There does not exist an entry of the form\(((r,d),\cdot )\) in\(L_\mathsf{H}\cup L_\mathsf{H^*}\), and\(c=\mathsf {Enc}(pk,r;\mathsf {H}\mathsf {H}^*(r,d))\) holds.

• \({{{\mathbf {\mathtt{{BDQ}}}}}}_i\):\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) which satisfies the following condition: There exists an entry\(((r,d), R) \in L_\mathsf{H}\cup L_\mathsf{H^*}\) which satisfies\(c=\mathsf {Enc}(pk_j,r;R)\), and for suchr,\((r, \cdot ) \in L_\mathsf{G^*}\) holds. Here,\((r,\cdot ) \in L_\mathsf{G^*}\) indicates that there exists an entry in\(L_\mathsf{G^*}\) whose first component isr. We call such a decryption query a “bad decryption query”.

Using the above events, we can estimate\(\mathsf{Adv}_{\mathsf {FO}_2, \mathcal {A}, \ell }^{kdmcca}(\lambda )\) as Lemma2 stated below.

Lemma 2

We can estimate\(\mathsf{Adv}_{\mathsf {FO}_2, \mathcal {A}, \ell }^{kdmcca}(\lambda )\) as follows:

(1)

Proof of Lemma2. As mentioned above, the difference between Game 0 and the original\(\text {KDM}\text {-}\text {CCA}\) game is only conceptual, and thus we have. By using the triangle inequality, we get the following inequality.

We note that, in Game 5, the challenger always responds to a KDM query (j, f) from\(\mathcal {A}\) by returning an encryption of\(0^{|f(\cdot )|}\) regardless of the value of the challenge bit. Therefore, in Game 5, the choice of the challenge bit and the behavior of\(\mathcal {A}\) are independent, and thus\(|\Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_5]-\frac{1}{2}|=0\). Below, we estimate\(|\Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_k]-\Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_{k+1}]| (k=0,1,2,3,4)\).

Game 0 and Game 1 are identical games unless when the challenger generates\(r \xleftarrow {r}\{0,1\}^\lambda \), there already exists an entry whose first component isr in\(L_\mathsf{H}\cup L_\mathsf{G}\cup L_\mathsf{G^*}\). We note that if\(L_\mathsf{G^*}\) does not have such an entry, the same is true for\(L_\mathsf{H^*}\). Therefore, we can see that Game 0 and Game 1 are identical unless the event\({{{\mathbf {\mathtt{{COL}}}}}}_0\) (resp.\({{{\mathbf {\mathtt{{COL}}}}}}_1\)) occurs in Game 0 (resp. Game 1), and thus we have\(|\Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_0] - \Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_1]| \le \Pr [{{{\mathbf {\mathtt{{COL}}}}}}_1]\).

Next, the only difference between Game 1 and Game 2 is how the challenger responds to a bad hash query from\(\mathcal {A}\). In other words, Game 1 and Game 2 are identical unless the event\({{{\mathbf {\mathtt{{BHQ}}}}}}_1\) (resp.\({{{\mathbf {\mathtt{{BHQ}}}}}}_2\)) occurs in Game 1 (resp. Game 2), and thus we have\(|\Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_1] - \Pr [{{{\mathbf {\mathtt{{SUC}}}}}}_2]| \le \Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_2]\).

Moreover, Game 2 and Game 3, and Game 3 and Game 4 are identical games except for how the challenger responds to a decryption query which satisfies the condition we stated in the definition of events\({{{\mathbf {\mathtt{{SMTH}}}}}}_i\) and\({{{\mathbf {\mathtt{{BDQ}}}}}}_i\), respectively. In other words, Game 2 and Game 3 are identical unless the event\({{{\mathbf {\mathtt{{SMTH}}}}}}_2\) (resp.\({{{\mathbf {\mathtt{{SMTH}}}}}}_3\)) occurs in Game 2 (resp. Game 3), and Game 3 and Game 4 are identical unless the event\({{{\mathbf {\mathtt{{BDQ}}}}}}_3\) (resp.\({{{\mathbf {\mathtt{{BDQ}}}}}}_4\)) occurs in Game 3 (resp. Game 4). and. Then, we get the following inequality.

(2)

In addition,\(\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_2] \le \sum _{k=2}^{4} |\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_k]-\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_{k+1}]| + \Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_5]\) holds. By considering analogously to the above argument, we get\(|\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_2]-\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_3]|\le \Pr [{{{\mathbf {\mathtt{{SMTH}}}}}}_3]\) and\(|\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_3]-\Pr [{{{\mathbf {\mathtt{{BHQ}}}}}}_4]\le \Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_4]\). Therefore, the following inequality holds.

Moreover, we have\(\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_4] \le |\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_4]-\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_5]|+\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_5]\). By using these inequalities in the inequality (2), we get the inequality (1).    \(\square \) (Lemma2)

Below, we show the following lemmas that state each term of the right side of the inequality (1) is negligible.

Lemma 3

.

Lemma 4

Let\(\varPi \) be smooth. Then.

Lemma 5

Let\(\varSigma \) be\({\text {OT-CPA}}\) secure. Then,, and.

Lemma 6

Let\(\varPi \) be\(\text {OW}\text {-}\text {CPA}\) secure. Then.

Lemma 7

Let\(\varPi \) be\(\text {OW}\text {-}\text {CPA}\) secure. Then.

Proof of Lemma3. Since\(\mathcal {A}\) is a PPT algorithm, there is a polynomial of\(\lambda \) which is the upper bound of the number of total entries in\(L_\mathsf{H}\cup L_\mathsf{G}\cup L_\mathsf{G^*}\). Let\(Q=Q(\lambda )\) denote this upper bound. Then, the probability that when the challenger generates\(r \xleftarrow {r}\{0,1\}^\lambda \) to respond to a KDM query form\(\mathcal {A}\), there is an entry of the form\((r,\cdot )\) in\(L_\mathsf{G}\cup L_\mathsf{G^*}\), or there is an entry of the form\(((r,\cdot ),\cdot )\) in\(L_\mathsf{H}\) is at most\(\frac{Q}{2^\lambda }\).\(\mathcal {A}\) makes a KDM query at most\(q_e\) times, and\(q_e\) is a polynomial of\(\lambda \). Therefore, we have.    \(\square \) (Lemma3)

Proof of Lemma4. We first define the following event for every\(i \in [q_d]\).

• \({{{\mathbf {\mathtt{{SMTH}}}}}}_3^i\): In Game 3, thei-th decryption query (j, c, d) made by\(\mathcal {A}\) satisfies the following two conditions, where\(\mathsf {Dec}(sk_j,c)=r\):(1) There does not exist an entry of the form\(((r,d),\cdot )\) in\(L_\mathsf{H}\cup L_\mathsf{H^*}\), and(2)\(c=\mathsf {Enc}(pk_j,r;\mathsf {H}\mathsf {H}^*(r,d))\).

When the condition(1) is satisfied, the value of\(\mathsf {H}\mathsf {H}^*(r,d)\) is defined with a newly generated uniformly random value. Then, the above condition(2) means that\(c=\mathsf {Enc}(pk_j,r;R)\) holds, where\(R \xleftarrow {r}\{0,1\}^n\). In addition,\(\Pr [{{{\mathbf {\mathtt{{SMTH}}}}}}_3] \le \sum _{i \in [q_d]} \Pr [{{{\mathbf {\mathtt{{SMTH}}}}}}_3^i]\) holds. Then, using the adversary\(\mathcal {A}\) that attacks\(\mathsf {FO}_2\), we construct the following adversary\(\mathcal {B}\) that attacks the smoothness of\(\varPi \).

• Initialization. On input\(((pk_1,sk_1), \cdots , (pk_\ell ,sk_\ell ))\),\(\mathcal {B}\) first chooses\(b \xleftarrow {r}\{0,1\}\) and\(t \xleftarrow {r}[q_d]\). Then,\(\mathcal {B}\) sends\(({ pk}_1, \cdots , { pk}_\ell )\) to\(\mathcal {A}\). Finally,\(\mathcal {B}\) sets\(\mathbf {sk}= (sk_1, \cdots , sk_\ell )\) and\(L_{kdm}= L_\mathsf{H}=L_\mathsf{H^*}=L_\mathsf{G}=L_\mathsf{G^*}= \emptyset \).

• Hash queries. If\(\mathcal {A}\) queries (r, d) to\(\mathsf {H}\),\(\mathcal {B}\) simulates\(\mathsf {H}\). Namely,\(\mathcal {B}\) first checks whether there is an entry of the form ((r, d), R) in\(L_\mathsf{H}\). If so,\(\mathcal {B}\) returnsR to\(\mathcal {A}\). Otherwise,\(\mathcal {B}\) generates\(R \xleftarrow {r}\{0,1\}^n\), adds ((r, d), R) to\(L_\mathsf{H}\), and returnsR to\(\mathcal {A}\). If\(\mathcal {A}\) queriesr to\(\mathsf {G}\),\(\mathcal {B}\) simulates\(\mathsf {G}\) analogously.

• KDM queries. For a KDM query (j, f) from\(\mathcal {A}\),\(\mathcal {B}\) computes\(m_1 \leftarrow f^{\mathsf {H}\mathsf {H}^*,\mathsf {G}\mathsf {G}^*}(\mathbf {sk})\) and\(m_0 \leftarrow 0^{|m_1|}\). Here,\(\mathcal {B}\) correctly forms\(L_\mathsf{H}\),\(L_\mathsf{H^*}\),\(L_\mathsf{G}\), and\( L_\mathsf{G^*}\) through to the end, and thus iff calls\(\mathsf {H}\mathsf {H}^*\) or\(\mathsf {G}\mathsf {G}^*\),\(\mathcal {B}\) can simulate them forf. Next,\(\mathcal {B}\) generates\(r \xleftarrow {r}\{0,1\}^\lambda \),\(K \xleftarrow {r}\{0,1\}^\lambda \), and\(R \xleftarrow {r}\{0,1\}^n\). Then,\(\mathcal {B}\) computes\(c \leftarrow \mathsf {Enc}({ pk}_j,r;R)\) and\(d \leftarrow \mathsf {E}(K,m_b)\), and returns (c, d) to\(\mathcal {A}\). Finally,\(\mathcal {B}\) adds (r, K) to\(L_\mathsf{G^*}\), ((r, d), R) to\(L_\mathsf{H^*}\), and (j, c, d) to\(L_{kdm}\).

• Decryption queries. For thei-th decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\),\(\mathcal {B}\) responds as follows.

  1. –

     In the case\(i < t\), if there does not exist an entry\(((r,d),R) \in L_\mathsf{H}\) which satisfies\( c=\mathsf {Enc}(pk_j,r;R)\),\(\mathcal {B}\) returns\(\bot \) to\(\mathcal {A}\). Otherwise,\(\mathcal {B}\) first checks whether there is an entry of the form (r, K) in\(L_\mathsf{G}\cup L_\mathsf{G^*}\). If so,\(\mathcal {B}\) returns\(m \leftarrow \mathsf {D}(K,d)\) to\(\mathcal {A}\). Otherwise,\(\mathcal {B}\) generates\(K \xleftarrow {r}\{0,1\}^\lambda \), adds (r, K) to\(L_\mathsf{G}\), and returns\(m \leftarrow \mathsf {D}(K,d)\) to\(\mathcal {A}\).

  2. –

     In the case\(i=t\),\(\mathcal {B}\) first computes\(r \leftarrow \mathsf {Dec}(sk_j,c)\). Then, if there exists an entry of the form\(((r,d),\cdot )\) in\(L_\mathsf{H}\cup L_\mathsf{H^*}\),\(\mathcal {B}\) aborts with output\(\bot \). Otherwise,\(\mathcal {B}\) outputs (j, r, c) and terminates.

\(\mathcal {B}\) perfectly simulates Game 3 until\(\mathcal {A}\) makes thet-th decryption query. We note that sincet is chosen from\([q_d]\) uniformly at random and independently of\(\mathcal {A}\), and is information-theoretically hidden from the view of\(\mathcal {A}\), the choice oft does not affect the behavior of\(\mathcal {B}\). When\(\mathcal {A}\) makes thet-th decryption query (j, c, d),\(\mathcal {B}\) first computes\(r \leftarrow \mathsf {Dec}(sk_j,c)\), and if there does not exist an entry of the form\(((r,d),\cdot )\) in\(L_\mathsf{H}\cup L_\mathsf{H^*}\),\(\mathcal {B}\) outputs (j, r, c) and terminates. Otherwise,\(\mathcal {B}\) outputs\(\bot \) and terminates. We can see that\(\mathcal {B}\) succeeds in breaking the smoothness of\(\varPi \) if and only if\(c=\mathsf {Enc}(pk_j,r;R)\) holds for a fresh randomnessR, which means that the event\({{{\mathbf {\mathtt{{SMTH}}}}}}_3^t\) occurs in Game 3 which\(\mathcal {B}\) simulates for\(\mathcal {A}\). Therefore, we can estimate the advantage of\(\mathcal {B}\)\(\mathsf{Adv}_{\varPi , \mathcal {B}}^{smth}(\lambda )\) as follows.

Therefore, we see that. Since\(\varPi \) is smooth and\(q_d\) is a polynomial of\(\lambda \), we have.    \(\square \) (Lemma4)

Proof of Lemma5. Using the adversary\(\mathcal {A}\) that attacks\(\mathsf {FO}_2\), we construct the adversaries\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\),\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\), and\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) all of which attack the\({\text {OT-CPA}}\) security of\(\varSigma \). We first describe\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) below.

• Initialization. On input security parameter\(1^{\lambda }\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) first chooses\(t \xleftarrow {r}[q_e]\). Then,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) generates\(\ell \) key pairs\(({ pk}_j, { sk}_j) \leftarrow \mathsf {KG}(1^\lambda ) (j=1,\cdots ,\ell )\) and sends\(({ pk}_1, \cdots , { pk}_\ell )\) to\(\mathcal {A}\). Finally,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) sets\(\mathbf {sk}=(sk_1,\cdots ,sk_\ell )\) and\(L_{kdm}= L_\mathsf{H}=L_\mathsf{H^*}=L_\mathsf{G}=L_\mathsf{G^*}=\emptyset \).

• Hash queries. For a hash query from\(\mathcal {A}\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) responds in the same manner as\(\mathcal {B}\) in the proof of Lemma4.

• KDM queries. For thei-th KDM query (j, f) from\(\mathcal {A}\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) responds as follows.

  1. –

     In the case\(i<t\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) first computes\(m_1 \leftarrow f^{\mathsf {H}\mathsf {H}^*, \mathsf {G}\mathsf {G}^*}(\mathbf {sk})\) and\(m_0 \leftarrow 0^{|f(\cdot )|}\). Since\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) correctly forms\(L_\mathsf{H}\),\(L_\mathsf{H^*}\),\(L_\mathsf{G}\), and\(L_\mathsf{G^*}\) up to this point, whenf calls\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) can simulate them forf. Next,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) generates\(r \xleftarrow {r}\{0,1\}^\lambda \),\(K \xleftarrow {r}\{0,1\}^\lambda \), and\(R \xleftarrow {r}\{0,1\}^n\). Then\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) computes\(c \leftarrow \mathsf {Enc}({ pk}_j,r;R)\) and\(d \leftarrow \mathsf {E}(K,m_b)\), and returns (c, d) to\(\mathcal {A}\). Finally,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) adds (r, K) to\(L_\mathsf{G^*}\), ((r, d), R) to\(L_\mathsf{H^*}\), and (j, c, d) to\(L_{kdm}\).

  2. –

     In the case\(i=t\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) first computes\(m_1 \leftarrow f^{\mathsf {H}\mathsf {H}^*, \mathsf {G}\mathsf {G}^*}(\mathbf {sk})\) and\(m_0 \leftarrow 0^{|f(\cdot )|}\). Since\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) correctly forms\(L_\mathsf{H}\),\(L_\mathsf{H^*}\),\(L_\mathsf{G}\), and\(L_\mathsf{G^*}\) up to this point, whenf calls\(\mathsf {H}\mathsf {H}^*\) and\(\mathsf {G}\mathsf {G}^*\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) can simulate them forf. Next,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) sends\((m_0, m_b)\) as a challenge query to the challenger to get the answerd. Then,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) generates\(r \xleftarrow {r}\{0,1\}^\lambda \) and\(R \xleftarrow {r}\{0,1\}^n\), computes\(c \leftarrow \mathsf {Enc}({ pk}_j, r;R)\), and returns (c, d) to\(\mathcal {A}\). Finally,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) adds\((r, \bot )\) to\(L_\mathsf{G^*}\), ((r, d), R) to\(L_\mathsf{H^*}\), and (j, c, d) to\(L_{kdm}\).

  3. –

     In the case\(i>t\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) first generates\(r \xleftarrow {r}\{0,1\}^\lambda \),\(K \xleftarrow {r}\{0,1\}^\lambda \), and\(R \xleftarrow {r}\{0,1\}^n\). Then,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) computes\(c \leftarrow \mathsf {Enc}({ pk}_j,r;R)\) and\(d \leftarrow \mathsf {E}(K,0^{|f(\cdot )|})\), and returns (c, d) to\(\mathcal {A}\). Finally,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) adds (r, K) to\(L_\mathsf{G^*}\), ((r, d), R) to\(L_\mathsf{H^*}\), and (j, c, d) to\(L_{kdm}\).

• Decryption queries. For a decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\), if there does not exist an entry\(((r,d),R) \in L_\mathsf{H}\) which satisfies\(c=\mathsf {Enc}(pk_j,r;R)\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) returns\(\bot \) to\(\mathcal {A}\). Otherwise,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) first checks whether there is an entry of the form (r, K) in\(L_\mathsf{G}\). If so,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) returns\(m \leftarrow \mathsf {D}(K,d)\) to \(\mathcal {A}\). Otherwise,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) generates\(K \xleftarrow {r}\{0,1\}^\lambda \), adds (r, K) to\(L_\mathsf{G}\), and returns\(m \leftarrow \mathsf {D}(K,d)\) to\(\mathcal {A}\).

• Final phase. When\(\mathcal {A}\) terminates with output\(b'\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) outputs\(\beta _{{{\mathbf {\mathtt{{SUC}}}}}}=1\) if\(b=b'\). Otherwise,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) outputs\(\beta _{{{\mathbf {\mathtt{{SUC}}}}}}=0\).

\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) runs in exactly the same way as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) except for how to determine the final output bit\(\beta _{{{\mathbf {\mathtt{{BHQ}}}}}}\).\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) determines\(\beta _{{{\mathbf {\mathtt{{BHQ}}}}}}\) as follows.\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) initially sets\(\beta _{{{\mathbf {\mathtt{{BHQ}}}}}}=0\). When\(\mathcal {A}\) queriesr to\(\mathsf {G}\) or queries (r, d) to\(\mathsf {H}\),\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) first responds in the same manner as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\). In addition,\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) checks whether the query is a bad hash query or not. Namely,\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) checks whether there exists an entry in\(L_\mathsf{G^*}\) whose first component isr. If so,\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) sets\(\beta _{{{\mathbf {\mathtt{{BHQ}}}}}}=1\). When\(\mathcal {A}\) terminates with output\(b'\),\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) outputs\(\beta _{{{\mathbf {\mathtt{{BHQ}}}}}}\).

\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) also runs in exactly the same way as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) except for how to determine the final output bit\(\beta _{{{\mathbf {\mathtt{{BDQ}}}}}}\).\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) determines\(\beta _{{{\mathbf {\mathtt{{BDQ}}}}}}\) as follows.\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) initially sets\(\beta _{{{\mathbf {\mathtt{{BDQ}}}}}}=0\). When\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\),\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) first responds in the same manner as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\). In addition,\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) checks whether the query is a bad decryption query or not. Namely,\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) checks whether the query satisfies the following condition: There exists an entry\(((r,d),R) \in L_\mathsf{H}\cup L_\mathsf{H^*}\) which satisfies\(c=\mathsf {Enc}(pk_j,r;R)\), and if so, for suchr,\((r, \cdot ) \in L_\mathsf{G^*}\) holds. If (j, c, d) satisfies the above condition, then\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) sets\(\beta _{{{\mathbf {\mathtt{{BDQ}}}}}}=1\). When\(\mathcal {A}\) terminates with output\(b'\),\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) outputs\(\beta _{{{\mathbf {\mathtt{{BDQ}}}}}}\).

Let\(\beta \) be the challenge bit in the game between the challenger and\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\). Then, the advantage of\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) is estimated as follows.

Here, for any\(k \in [q_e]\), we have the following two equations.

We note thatt is chosen from\([q_e]\) uniformly at random and independently of\(\beta \). Hence, for all\(k \in [q_e]\), we have\(\Pr [ t = k | \beta = 1] = \Pr [ t = k | \beta = 0 ] = \frac{1}{q_e}\). Moreover, for every\(k \in [q_e-1]\), in the cases\(\beta =1 \wedge t=k\) and\(\beta =0 \wedge t=k+1\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) responds to KDM queries from\(\mathcal {A}\) in exactly the same way. In the above two cases, the only difference is whether\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) computes\(f^{\mathsf {H}\mathsf {H}^*,\mathsf {G}\mathsf {G}^*}(\mathbf {sk})\) to responds to the\((k+1)\)-th KDM query from\(\mathcal {A}\). Due to this difference, in the above two cases, the manner\(L_\mathsf{H}\) and\(L_\mathsf{G}\) are formed is different. However, since\(\mathcal {A}\) cannot see the contents of\(L_\mathsf{H}\) and\(L_\mathsf{G}\), this does not affect the behavior of\(\mathcal {A}\). Therefore, we have\(\Pr [\beta _{{{\mathbf {\mathtt{{SUC}}}}}}=1|\beta =1 \wedge t=k]=\Pr [\beta _{{{\mathbf {\mathtt{{SUC}}}}}}=1|\beta =0 \wedge t=k+1]\) for any\(k \in [q_e-1]\). From these, we have the following equality.

Since\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) and\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) run in exactly the same way as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) except for how to determine the final output bit, all of the above arguments also hold for\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) and\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\). Therefore, we also have the following equalities.

We note that, until\(\mathcal {A}\) makes thet-th KDM query,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) correctly forms\(L_\mathsf{H}\),\(L_\mathsf{H^*}\),\(L_\mathsf{G}\), and\(L_\mathsf{G^*}\), and thus\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) can compute KDM functions up to this point. On the other hand,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) cannot simulate thet-th entry of\(L_\mathsf{G^*}\) because\(\mathcal {B}\) simulates the security game for\(\mathcal {A}\) so that the second component of thet-th entry of\(L_\mathsf{G^*}\) is the value of the key the challenger generates, and thus\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) does not know it. Therefore, when responding to the subsequent KDM queries,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) cannot compute KDM functions correctly. However, since\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) only needs the output length of KDM functions to respond to the\((t+1)\)-th and subsequent KDM queries, and KDM functions are length regular,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) need not computef. Then, we see that when\(\beta =1 \wedge t=q_e\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) perfectly simulates Game 4 for\(\mathcal {A}\). On the other hand, when\(\beta =0 \wedge t=1\),\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) perfectly simulates Game 5 for\(\mathcal {A}\). We note thatt is information-theoretically hidden from the view of\(\mathcal {A}\), and thus the choice oft does not affect the behavior of\(\mathcal {A}\). Here, this argument also holds for\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) and\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\).

In addition,\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) outputs 1 only when\(\mathcal {A}\) succeeds in guessingb, that is,\(b=b'\) occurs,\(\mathcal {B}_{{{\mathbf {\mathtt{{BHQ}}}}}}\) outputs 1 only when\(\mathcal {A}\) makes a bad hash query, and\(\mathcal {B}_{{{\mathbf {\mathtt{{BDQ}}}}}}\) outputs 1 only when\(\mathcal {A}\) makes a bad decryption query. Therefore, we have following equalities.

Therefore, we get the following equalities.

Since\(\varSigma \) is\({\text {OT-CPA}}\) secure and\(q_e\) is a polynomial of\(\lambda \), we see that,, and.    \(\square \) (Lemma5)

Proof of Lemma6. Using the adversary\(\mathcal {A}\) that attacks\(\mathsf {FO}_2\), we construct the following adversary\(\mathcal {B}\) that attacks the\({\text {List-OW-CPA}}\) security of\(\varPi \). We note that since\(\varPi \) is\(\text {OW}\text {-}\text {CPA}\) secure, by Lemma1,\(\varPi \) is also\({\text {List-OW-CPA}}\) secure.

• Initialization. On input\((pk_1, \cdots , pk_\ell )\),\(\mathcal {B}\) sends\((pk_1, \cdots , pk_\ell )\) to\(\mathcal {A}\), and\(\mathcal {B}\) sets\(L_{kdm}= L_\mathsf{H}=L_\mathsf{G}=L_{ans}= \emptyset \).

• Hash queries. If\(\mathcal {A}\) queries (r, d) to\(\mathsf {H}\),\(\mathcal {B}\) simulates\(\mathsf {H}\). Namely,\(\mathcal {B}\) first checks whether there is an entry of the form ((r, d), R) in\(L_\mathsf{H}\). If so,\(\mathcal {B}\) returnsR to\(\mathcal {A}\). Otherwise,\(\mathcal {B}\) generates\(R \xleftarrow {r}\{0,1\}^n\), adds ((r, d), R) to\(L_\mathsf{H}\), and returnsR to\(\mathcal {A}\). Then,\(\mathcal {B}\) addsr to\(L_{ans}\). If\(\mathcal {A}\) queriesr to\(\mathsf {G}\),\(\mathcal {B}\) simulates\(\mathsf {G}\) analogously to\(\mathsf {H}\) as above, and addsr to\(L_{ans}\).

• KDM queries. For a KDM query (j, f) from\(\mathcal {A}\),\(\mathcal {B}\) first queriesj to the challenger as an encryption query and gets the answerc. Then,\(\mathcal {B}\) generates\(K \xleftarrow {r}\{0,1\}^\lambda \) and computes\(d \leftarrow \mathsf {E}(K,0^{|f(\cdot )|})\). Finally,\(\mathcal {B}\) adds (j, c, d) to\(L_{kdm}\), and returns (c, d) to\(\mathcal {A}\).

• Decryption queries. For a decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\),\(\mathcal {B}\) responds in the same manner as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) in the proof of Lemma5.

• Final phase. When\(\mathcal {A}\) terminates with output\(b'\),\(\mathcal {B}\) outputs\(L_{ans}\).

In the\({\text {List-OW-CPA}}\) game, the challenger maintains the list\(L_{enc}\) which stores plaintexts of the challenge ciphertexts. Then, the advantage of\(\mathcal {B}\) is\(\Pr [L_{enc}\cap L_{ans}\ne \emptyset ]\). We see that\(\mathcal {B}\) perfectly simulates Game 5 for\(\mathcal {A}\). If\(\mathcal {A}\) queriesr as a\(\mathsf {G}\) query or (r, d) as a\(\mathsf {H}\) query,\(\mathcal {B}\) addsr to\(L_{ans}\). In addition, in Game 5, a new entry is added to\(L_\mathsf{G}\) and\(L_\mathsf{H}\) only when\(\mathcal {A}\) makes a\(\mathsf {G}\) query and\(\mathsf {H}\) query, respectively. Therefore, we can write\(L_{ans}= \{r|(r, \cdot ) \in L_\mathsf{G}\vee ((r,\cdot ),\cdot ) \in L_\mathsf{H}\}\). Here,\((r,\cdot ) \in L_\mathsf{G}\) (resp.\(((r,\cdot ),\cdot ) \in L_\mathsf{H}\)) indicates that there exists an entry in\(L_\mathsf{G}\) (resp.\(L_\mathsf{H}\)) whose first component isr.

On the other hand, every time\(\mathcal {A}\) makes a KDM query (j, f),\(\mathcal {B}\) sendsj to the challenger as an encryption query and gets the answerc. Here, letc be an encryption ofr. Then, by the above encryption query from\(\mathcal {B}\), the challenger addsr to\(L_{enc}\). On the other hand, in Game 5, the hash value ofr is computed using\(\mathsf {G}^*\) at this point, and thus an entry of the form\((r, \cdot )\) is added to\(L_\mathsf{G^*}\). Therefore,\(L_{enc}\) can be seen as the set of the first components of the entries in\(L_\mathsf{G^*}\) in Game 5. (Actually,\(\mathcal {B}\) does not make\(L_\mathsf{G^*}\) by itself, but\(\mathcal {B}\) does not need\(L_\mathsf{G^*}\) to simulate Game 5 for\(\mathcal {A}\).) From these, we see that\(L_{enc}\cap L_{ans}\ne \emptyset \) holds if the event\({{{\mathbf {\mathtt{{BHQ}}}}}}_5\) occurs in Game 5 which\(\mathcal {B}\) simulates for\(\mathcal {A}\). Therefore, we can see that. Since\(\varPi \) is\({\text {List-OW-CPA}}\) secure, we see that.    \(\square \) (Lemma6)

Proof of Lemma7. First, we define the following two events.

• \({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5\): In Game 5,\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) satisfying the following condition: There exists an entry\(((r,d), R) \in L_\mathsf{H}\) which satisfies\(c=\mathsf {Enc}(pk_j,r;R)\) and\((r,\cdot ) \in L_\mathsf{G^*}\).

• \({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5\): In Game 5,\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) satisfying the following condition: There exists an entry\(((r,d), R) \in L_\mathsf{H^*}\) which satisfies\(c=\mathsf {Enc}(pk_j,r;R)\). (We note that if there is an entry of the form\(((r,\cdot ),\cdot ) \in L_\mathsf{H^*}\), then there is an entry of the form\((r,\cdot ) \in L_\mathsf{G^*}\).)

By the definition of the events, obviously,\({{{\mathbf {\mathtt{{BDQ}}}}}}_5={{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5 \vee {{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5\) holds, and thus we have\(\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}_5] \le \Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5]+\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5]\). Here, regarding\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5\), when\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) satisfying the condition of\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5\), it holds that\(r=r^*\),\(R=R^*\), and\(d=d^*\) for some entry\((j^*,c^*,d^*) \in L_{kdm}\), where\(c^*=\mathsf {Enc}(pk_{j^*},r^*;R^*)\). In addition, in this case,\(j \ne j^*\) also holds. The reason is as follows. If\(j=j^*\) holds, then\(c=\mathsf {Enc}(pk_j,r;R)=\mathsf {Enc}(pk_{j^*},r^*;R^*)=c^*\) holds, and thus we have\((j,c,d)=(j^*,c^*,d^*)\), which contradicts\((j,c,d) \notin L_{kdm}\). Therefore,\(j \ne j^*\) holds. From these, the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5\) implies the following event.

• \({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}^*_5\): In Game 5,\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) satisfying the following condition: For some entry\((j^*,c^*,d^*) \in L_{kdm}\), where\(c^*=\mathsf {Enc}(pk_{j^*},r^*;R^*)\), it holds that\(c=\mathsf {Enc}(pk_j,r^*;R^*)\) and\(j \ne j^*\).

Here, we have\(\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5] \le \Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}^*_5]\).

Then, using the adversary\(\mathcal {A}\) that attacks\(\mathsf {FO}_2\), we construct the following adversary\(\mathcal {B}\) that attacks the\({\text {List-OW-CPA}}\) security of\(\varPi \). Since\(\varPi \) is\(\text {OW}\text {-}\text {CPA}\) secure, from Lemma1,\(\varPi \) is also\({\text {List-OW-CPA}}\) secure. Here, we note that\(\mathcal {B}\) attacks the\({\text {List-OW-CPA}}\) security of\(\varPi \) in the case the number of keys is\(\ell -1\).

• Initialization. On input\((pk^*_1, \cdots , pk^*_{\ell -1})\),\(\mathcal {B}\) first chooses\(s \xleftarrow {r}[\ell ]\) and generates\((pk_s,sk_s) \leftarrow \mathsf {KG}(1^\lambda )\). Then, for\(1 \le j < s\),\(\mathcal {B}\) sets\(pk_j=pk^*_j\), and for\(s<j \le \ell \),\(\mathcal {B}\) sets\(pk_j=pk^*_{j-1}\). Finally,\(\mathcal {B}\) sends\((pk_1, \cdots , pk_\ell )\) to\(\mathcal {A}\), and sets\(L_{kdm}= L_\mathsf{H}=L_\mathsf{G}=L_{ans}^1=L_{ans}^2= \emptyset \).

• Hash queries. If\(\mathcal {A}\) queries (r, d) to\(\mathsf {H}\),\(\mathcal {B}\) first simulates\(\mathsf {H}\). Namely,\(\mathcal {B}\) first checks whether there is an entry of the form ((r, d), R) in\(L_\mathsf{H}\). If so,\(\mathcal {B}\) returnsR to\(\mathcal {A}\). Otherwise,\(\mathcal {B}\) generates\(R \xleftarrow {r}\{0,1\}^n\), adds ((r, d), R) to\(L_\mathsf{H}\), and returnsR to\(\mathcal {A}\). Then,\(\mathcal {B}\) addsr to\(L_{ans}^1\). If\(\mathcal {A}\) queriesr to\(\mathsf {G}\),\(\mathcal {B}\) just simulates\(\mathsf {G}\) analogously to\(\mathsf {H}\). (\(\mathcal {B}\) does not addr to\(L_{ans}^1\) in the case of\(\mathsf {G}\) query.)

• KDM queries. For a KDM query (j, f) from\(\mathcal {A}\),\(\mathcal {B}\) responds as follows.

  • – In the case\(j \ne s\),\(\mathcal {B}\) first queriesj if\(j<s\) and\(j-1\) if\(j>s\) to the challenger as an encryption query and gets the answerc. Then,\(\mathcal {B}\) generates\(K \xleftarrow {r}\{0,1\}^\lambda \) and computes\(d \leftarrow \mathsf {E}(K,0^{|f(\cdot )|})\). Finally,\(\mathcal {B}\) adds (j, c, d) to\(L_{kdm}\), and returns (c, d) to\(\mathcal {A}\).

  • – In the case\(j = s\),\(\mathcal {B}\) first generates\(r \xleftarrow {r}\{0,1\}^\lambda \),\(K \xleftarrow {r}\{0,1\}^\lambda \), and\(R \xleftarrow {r}\{0,1\}^\lambda \). Then,\(\mathcal {B}\) computes\(c=\mathsf {Enc}(pk_j,r;R)\) and\(d \leftarrow \mathsf {E}(K,0^{|f(\cdot )|})\). Finally,\(\mathcal {B}\) adds (j, c, d) to\(L_{kdm}\), and returns (c, d) to\(\mathcal {A}\).

• Decryption queries. For a decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\), if\(j=s\),\(\mathcal {B}\) first computes\(r \leftarrow \mathsf {Dec}(sk_s,c)\), and addsr to\(L_{ans}^2\) if\(r \ne \bot \). Then,\(\mathcal {B}\) responds in the same manner as\(\mathcal {B}_{{{\mathbf {\mathtt{{SUC}}}}}}\) in the proof of Lemma5.

• Final phase. When\(\mathcal {A}\) terminates with output\(b'\),\(\mathcal {B}\) chooses\(\gamma \xleftarrow {r}\{1,2 \}\) and outputs\(L_{ans}^\gamma \).

We see that\(\mathcal {B}\) perfectly simulates Game 5 for\(\mathcal {A}\). In the initialization step,\(\mathcal {B}\) chooses\(s \xleftarrow {r}[\ell ]\) and generates\((pk_s,sk_s) \leftarrow \mathsf {KG}(1^\lambda )\). Sinces is information-theoretically hidden from the view of\(\mathcal {A}\), this does not affect the behavior of\(\mathcal {A}\). We note that, in the\({\text {List-OW-CPA}}\) game, the challenger maintains the list\(L_{enc}\) which stores plaintexts of the challenge ciphertexts. Then, it holds that\(\mathsf{Adv}_{\varPi , \mathcal {B}, \ell -1}^{lowcpa}(\lambda )=\Pr [L_{enc}\cap L_{ans}^\gamma \ne \emptyset ]\). Here,\(\gamma \) is a randomness over\(\{1,2\}\) which\(\mathcal {B}\) chooses in the final phase, and thus the following equality holds.

In the following, we first consider\(\Pr [L_{enc}\cap L_{ans}^1 \ne \emptyset ]\). When the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5\) occurs in Game 5 which\(\mathcal {B}\) simulates for\(\mathcal {A}\), there exists an entry\(((r^*,d),R) \in L_\mathsf{H}\) which satisfies\(c=\mathsf {Enc}(pk_j,r^*,R)\) and\((r^*,\cdot ) \in L_\mathsf{G^*}\) for some decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\). We note that only when\(\mathcal {A}\) makes a\(\mathsf {H}\) query, an entry is added to\(L_\mathsf{H}\). Thus,\(((r^*,d),R) \in L_\mathsf{H}\) means that\(\mathcal {A}\) has queries\((r^*,d)\) as a\(\mathsf {H}\) query. Therefore, in this case,\(L_{ans}^1\) contains\(r^*\). Also,\((r^*,\cdot ) \in L_\mathsf{G^*}\) means that\(r^*\) is generated to compute the answer to a KDM query from\(\mathcal {A}\). (Actually,\(\mathcal {B}\) does not make\(L_\mathsf{G^*}\) by itself, but\(\mathcal {B}\) need not make\(L_\mathsf{G^*}\) to simulate Game 5 for\(\mathcal {A}\).) Here, let\(r^*\) be generated to compute the answer\((c^*,d^*)\) to a KDM query\((j^*,f)\) from\(\mathcal {A}\). In other words, let\(c^*\) be an encryption of\(r^*\) under\(pk_{j^*}\). Then, if\(j^* \ne s\),\(c^*\) is computed by the challenger, and thus\(L_{enc}\) contains\(r^*\). On the other hand, if\(j^*=s\),\(c^*\) is computed by\(\mathcal {B}\), and thus\(L_{enc}\) does not contain\(r^*\). Therefore, at least when\(\mathcal {A}\) makes a decryption query satisfying the condition of the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5\), and\(j^* \ne s\) holds for the above\(j^*\),\(L_{enc}\cap L_{ans}^1 \ne \emptyset \) holds. Sinces is chosen from\([\ell ]\) uniformly at random, and is information-theoretically hidden from the view of\(\mathcal {A}\), the choice ofs is independent of the behavior of\(\mathcal {A}\). Therefore, the probability that\(j^* \ne s\) holds under the condition that\(\mathcal {A}\) has made a decryption query satisfying the condition of\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5\) is\(\frac{\ell -1}{\ell }\). Moreover, since\(\mathcal {B}\) perfectly simulates Game 5 for\(\mathcal {A}\), the probability that\(\mathcal {A}\) makes a decryption query satisfying the condition of the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5\) is\(\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5]\). From these, we have\(\Pr [L_{enc}\cap L_{ans}^1 \ne \emptyset ] \ge \frac{\ell -1}{\ell }\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{1}_5]\).

Next, we consider\(\Pr [L_{enc}\cap L_{ans}^2 \ne \emptyset ]\). When the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*\) occurs in Game 5 which\(\mathcal {B}\) simulates for\(\mathcal {A}\), for some decryption query\((j,c,d) \notin L_{kdm}\) from\(\mathcal {A}\) and some entry\((j^*,c^*,d^*) \in L_{kdm}\), it holds that\(c=\mathsf {Enc}(pk_j,r^*;R^*)\) and\(j \ne j^*\), where\(c^*=\mathsf {Enc}(pk_{j^*},r^*;R^*)\). Then, if\(j=s\),\(L_{ans}^2\) contains\(r^*\). In addition, in this case,\(j^* \ne j=s\) holds, and thus\(L_{enc}\) also contains\(r^*\). Therefore, at least when\(\mathcal {A}\) makes a decryption query\((j,c,d) \notin L_{kdm}\) satisfying the condition of the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*\), and\(j=s\) holds,\(L_{enc}\cap L_{ans}^2 \ne \emptyset \) holds. Since the choice ofs is independent of\(\mathcal {A}\), the probability that\(j=s\) holds under the condition that\(\mathcal {A}\) has made a decryption query satisfying the condition of\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*\) is\(\frac{1}{\ell }\). Moreover, since\(\mathcal {B}\) perfectly simlates Game 5 for\(\mathcal {A}\), the probability that\(\mathcal {A}\) makes a decryption query satisfying the condition of the event\({{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*\) is\(\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*]\). Therefore, we get\(\Pr [L_{enc}\cap L_{ans}^2 \ne \emptyset ] \ge \frac{1}{\ell }\Pr [{{{\mathbf {\mathtt{{BDQ}}}}}}\mathtt{2}_5^*]\).

From these, we can estimate\(\mathsf{Adv}_{\varPi , \mathcal {B}, \ell -1}^{lowcpa}(\lambda )\) as follows.

From the above, we have. Since\(\varPi \) is\({\text {List-OW-CPA}}\) secure and\(\ell \) is a polynomial of\(\lambda \), we see that.    \(\square \) (Lemma7)

From the inequality (1) and Lemmas3 to7, we have\(\mathsf{Adv}_{\mathsf {FO}_2, \mathcal {A}, \ell }^{kdmcca}(\lambda )=\mathsf{negl}(\lambda )\). Since the choice of\(\ell \) and\(\mathcal {A}\) is arbitrary, we see that\(\mathsf {FO}_2\) is\(\text {KDM}\text {-}\text {CCA}\) secure in the random oracle model.    \(\square \) (Theorem4)