QCCA-Secure Generic Key Encapsulation Mechanism with Tighter Security in the Quantum Random Oracle Model

Abstract

Xagawa and Yamakawa (PQCrypto 2019) proved the transformation $\mathsf {SXY}$ can tightly turn $\mathsf {DS}$ secure $\mathsf {PKE}$s into $\mathsf {IND}\text {-}\mathsf{qCCA}$ secure $\mathsf {KEM}$s in the quantum random oracle model (QROM). But transformations such as $\mathsf {KC,\ TPunc}$ that turn PKEs with standard security ($\mathsf {OW}\text {-}\mathsf{CPA}$ or $\mathsf {IND}\text {-}\mathsf{CPA}$) into $\mathsf {DS}$ secure $\mathsf {PKE}$s still suffer from quadratic security loss in the QROM. In this paper, we give a tighter security reduction for the transformation $\mathsf {KC}$ that turns $\mathsf {OW}\text {-}\mathsf{CPA}$ secure deterministic $\mathsf {PKE}$s into modified $\mathsf {DS}$ secure $\mathsf {PKE}$s in the QROM. We use the Measure-Rewind-Measure One-Way to Hiding Lemma recently introduced by Kuchta et al. (EUROCRYPT 2020) to avoid the square-root advantage loss. Moreover, we extend it to the case that underlying $\mathsf {PKE}$s are not perfectly correct. Combining with other transformations, we finally obtain a generic $\mathsf {KEM}$ from any $\mathsf {IND}\text {-}\mathsf{CPA}$ secure $\mathsf {PKE}$. Our security reduction has roughly the same tightness as the result of Kuchta et al. without any other assumptions and we achieve the stronger $\mathsf {IND}\text {-}\mathsf{qCCA}$ security. We also give a similar result for another $\mathsf {KEM}$ transformation achieving the same security notion from any $\mathsf {OW}\text {-}\mathsf{CPA}$ secure deterministic $\mathsf {PKE}$.

1 Introduction

Key encapsulation mechanism ($\mathsf {KEM}$) is a foundational cryptography primitive. It can be used to construct efficient hybrid encryption using the $\mathsf {KEM/DEM}$ paradigm [8]. Indistinguishability under chosen ciphertext attacks ($\mathsf {IND}\text {-}\mathsf{CCA}$) is widely used as the desired security notion for $\mathsf {KEM}$ and public-key encryption ($\mathsf {PKE}$). With the development of quantum computer, we need to develop cryptographic schemes that would be secure against both quantum and classical computers. In this paper, we consider the indistinguishability under quantum chosen ciphertext attacks ($\mathsf {IND}\text {-}\mathsf{qCCA}$) for $\mathsf {KEM}$ in the quantum random oracle model (QROM).

In the quantum world, one can deal with superposition states, which brings more capabilities to the adversaries. To achieve the security against quantum adversaries, we have to base our cryptographic constructions on quantum-resistant assumptions. But it is not sufficient if adversaries can interact with honest parties using quantum communication. Boneh et al. [6] argued that quantum random oracle model should be used instead of random oracle model (ROM) [4]. In the QROM, hash functions are modeled as public oracles similarly as ROM but with quantum access. Furthermore, Boneh and Zhandry [7] introduced the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security notion for $\mathsf {PKE}$, where adversaries can make quantum queries to the decryption oracle. Their goal is to construct classical systems that remain secure even when implemented on a quantum computer, thereby potentially giving the attacker the ability to issue quantum queries. Following it, Xagawa and Yamakawa [22] considered the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security for $\mathsf {KEM}$, where adversaries can make quantum queries to the decapsulation oracle. Note that different from $\mathsf {PKE}$, there is no challenge messages queried by the adversary in the $\mathsf {IND}\text {-}\mathsf{CCA}$ game for $\mathsf {KEM}$. All interactions with the adversary use quantum communication. Therefore, the corresponding $\mathsf {IND}\text {-}\mathsf{qCCA}$ security in the QROM is the security notion against fully quantum adversaries for $\mathsf {KEM}$.

To achieve the $\mathsf {IND}\text {-}\mathsf{CCA}$ security, generic transformations such as Fujisaki-Okamoto ($\mathsf {FO}$) transformation [10, 11] are usually used. They can transform a weakly secure (one-wayness under chosen plaintext attacks $(\mathsf {OW}\text {-}\mathsf{CPA})$ or indistinguishability under chosen plaintext attacks $(\mathsf {IND}\text {-}\mathsf{CPA})$) $\mathsf {PKE}$ to a $\mathsf {IND}\text {-}\mathsf{CCA}$ one. Dent [9] gave the $\mathsf {KEM}$ version of $\mathsf {FO}$. Hofheinz, Hövelmanns and Kiltz [12] analyzed it in a modular way, decomposing it into two transformations named $\mathsf {T}$ and . They also introduced some variants of transformation named and $\mathsf {U}_m^\perp$, and they gave a detailed result about them in the classical setting. Subsequent works [5, 13, 15,16,17,18] are devoted to the analysis in the quantum setting. The core tool used in these analysis is the One-Way to Hiding (O2H) Lemma [21] and its variants [2, 5, 12, 18]. Roughly speaking, the O2H lemma can be used to construct a one-wayness adversary from a distinguisher.

Recently, Kuchta et al. [18] introduced a new O2H variant named Measure-Rewind-Measure One-Way to Hiding (MRM O2H) Lemma. It is the first variant to get rid of the square-root advantage loss, and using this lemma, they gave a security proof for $\mathsf {FO}$ from $\mathsf {IND}\text {-}\mathsf{CPA}$ security to $\mathsf {IND}\text {-}\mathsf{CCA}$ security without the square-root advantage loss for the first time. Their security proof is nearly tight for low query depth attacks. The case of (relatively) low query depth attacks tends to be of high practical interest, since it corresponds, for instance, to massively parallelized attacks, which are the standard approach to deal with high computation costs in practical cryptanalysis. However, their proof doesn’t apply to the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security. As argued in [7, 22], in order to be immune to quantum superposition attacks, quantum chosen ciphertext security is worth investigating. On the other hand, Saito, Xagawa and Yamakawa [20] introduced a new security notion named disjoint simulatability ($\mathsf {DS}$). Intuitively, disjoint simulatability means that we can efficiently sample “fake ciphertexts” that are computationally indistinguishable from real ciphertexts (“simulatability”), while the set of possible fake ciphertexts is required to be (almost) disjoint from the set of real ciphertexts (“disjointness”). In addition, they gave a transformation named $\mathsf {SXY}$ which can tightly turn $\mathsf {DS}$ secure $\mathsf {PKE}$s into $\mathsf {IND}\text {-}\mathsf{CCA}$ secure $\mathsf {KEM}$s. Furthermore, they find it can be easily extended to the stronger $\mathsf {IND}\text {-}\mathsf{qCCA}$ security tightly also [22]. However, transformations $\mathsf {KC}$ and $\mathsf {TPunc}$ introduced in [20] from standard secure ($\mathsf {OW}\text {-}\mathsf{CPA}$ or $\mathsf {IND}\text {-}\mathsf{CPA}$) $\mathsf {PKE}$s to $\mathsf {DS}$ secure $\mathsf {PKE}$s still suffer from quadratic security loss, so is the $\mathsf {KEM}$ combined with transformation $\mathsf {SXY}$.

Our Contributions. In this paper, we analyze two generic $\mathsf {KEM}$s and we prove that they achieve $\mathsf {IND}\text {-}\mathsf{qCCA}$ security from standard security without quadratic security loss in the QROM. At the heart of our result is a tighter security reduction for the transformation $\mathsf {KC}$. We modify the definition of $\mathsf {DS}$ and we use the MRM O2H lemma to prove that the transformation $\mathsf {KC}$ can transform a $\mathsf {OW}\text {-}\mathsf{CPA}$ secure deterministic $\mathsf {PKE}$ ($\mathsf {dPKE}$) into a modified $\mathsf {DS}$ secure $\mathsf {PKE}$ without the square-root advantage loss. Moreover, we don’t require the underlying $\mathsf {PKE}$ to be perfectly correct as before.

The first $\mathsf {KEM}$ we analyzed is $\mathsf {SXY\circ KC\circ T}$ and the second $\mathsf {KEM}$ is $\mathsf {SXY\circ KC}$. We give an overview in Fig. 1. The upper part and the lower part of Fig. 1 are the two $\mathsf {KEM}$s respectively. The second $\mathsf {KEM}$ is relatively simple, and it is the combination of transformation $\mathsf {KC}$ and transformation $\mathsf {SXY}$. Xagawa and Yamakawa has already proved transformation $\mathsf {SXY}$ can tightly turn $\delta$-correct $\mathsf {DS}$ secure $\mathsf {dPKE}$s into $\mathsf {IND}\text {-}\mathsf{qCCA}$ secure $\mathsf {KEM}$s in the QROM (Lemma 5 [22]).

Fig. 1.

Overview of $\mathsf {KEM}$s.

In the previous security proofs of $\mathsf {KC}$ [17, 20], some variants of O2H lemmas are used. However, they all incur a quadratic loss of security. The MRM O2H lemma doesn’t suffer from it, but it requires the simulator can simulate both G and H. In our case, the simulator doesn’t know the $m^*\in S$, however, the simulator can simulate G (or H) that should be reprogrammed at $m^*$ by testing whether the queried m satisfies $\mathsf {Enc}(pk,m)=c^*$ or not instead. With a detailed analysis, the MRM O2H lemma can be applied to prove the second property of $\mathsf {DS}$ even if the underlying $\mathsf {PKE}$ is not perfectly correct. But it is difficult to satisfy the first requirement of $\mathsf {DS}$ with imperfectly correct underlying $\mathsf {PKE}$s in $\mathsf {KC}$. However, we find that the $\mathsf {DS}$ notion in [20] is slightly stronger, so we make a modification to its definition to relax the requirement. With this new $\mathsf {DS}$ notion, we get rid of the perfectly correctness requirement in $\mathsf {KC}$. And finally we prove that the transformation $\mathsf {KC}$ can turn $\delta$-correct $\mathsf {OW}\text {-}\mathsf{CPA}$ secure $\mathsf {dPKE}$s into $\delta$-correct $\mathsf {DS}$ secure $\mathsf {dPKE}$s without the square-root advantage loss in Theorem 2.¹

The underlying $\mathsf {PKE}$ of above $\mathsf {KEM}$ is $\mathsf {dPKE}$. If we want to let the underlying $\mathsf {PKE}$ be a $\mathsf {rPKE}$ (randomized $\mathsf {PKE}$), we can apply the transformation $\mathsf {T}$ first. And this yields the first $\mathsf {KEM}$. Although there exists results of transformation $\mathsf {T}$ that it can turn $\delta$-correct $\mathsf {IND}\text {-}\mathsf{CPA}$ secure $\mathsf {rPKE}$s into $\mathsf {OW}\text {-}\mathsf{CPA}$ secure $\mathsf {dPKE}$s (Lemma 6 [5]), we cannot simply append it to the proof of the second $\mathsf {KEM}$. The reason is that the concept of $\delta$-correct doesn’t apply to the resulting $\mathsf {dPKE}$ of $\mathsf {T}$ directly, though the resulting $\mathsf {dPKE}$ is not perfectly correct. So actually, Theorem 1 and Theorem 3 are different from corresponding Theorem 2 and Lemma 5 [22]. In the proof of Theorem 3, we use the method in [12, 15] to deal with it. In the proof of Theorem 1, we make a direct analysis to get a better result. Specifically, we use a different $\mathsf {Bad}$ event than that in the proof of Theorem 2 to separate the case that a “bad” message is chosen.

Here we give a comparison of $\mathsf {KEM}$ transformations from $\mathsf {IND}\text {-}\mathsf{CPA}$ secure $\mathsf {PKE}$s in the QROM in Table 1. Kuchta et al.’s [18] proof of achieves the best known security bound of $\mathsf {KEM}$s from $\mathsf {IND}\text {-}\mathsf{CPA}$ security to $\mathsf {IND}\text {-}\mathsf{CCA}$ security in the QROM. Xagawa and Yamakawa [22] gave the first $\mathsf {KEM}$ to achieve the stronger $\mathsf {IND}\text {-}\mathsf{qCCA}$ security. And Jiang et al. [17] improved the security bound of $\mathsf {Tpunc}$. But the security bound of the combination scheme is still larger than the first one in certain settings. Our proof of achieves the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security with tighter security bound than the second one, roughly the same as the first one. What’s more, it doesn’t need any other requirements.

Table 1. Comparison of $\mathsf {KEM}$ transformations from $\mathsf {IND}\text {-}\mathsf{CPA}$ secure $\mathsf {PKE}$s in the QROM. The “Security bound” column shows the dependence of the approximate upper bound on attacker’s advantage $\mathsf {Adv}(\mathcal {A})$ against the $\mathsf {KEM}$ in terms of the attacker advantage $\epsilon$ against the underlying $\mathsf {PKE}$, and $\mathcal {A}$’s total query number q or query depth d to quantum random oracles.

2 Preliminaries

2.1 Notation

For a finite set S, |S| denotes the cardinality of S, and we denote the sampling of a uniformly random element x from S by $x\xleftarrow {\$}S$, while we denote the sampling according to some distribution $\mathcal D$ by $x\leftarrow \mathcal D$. $\mathcal U_S$ denotes the uniform distribution over S. By $\llbracket B\rrbracket$ we denote the bit that is 1 if the Boolean statement B is true, and otherwise 0.

We denote deterministic computation of an algorithm $\mathsf {A}$ on input x by . We denote algorithms with access to an oracle O by $\mathsf {A}^O$. Unless stated otherwise, we assume all our algorithms to be probabilistic and denote the computation by $y\leftarrow \mathsf {A}(x)$. We also use the notation to make the randomness r explicit. By $\mathsf {Time(A)}$ we denote the running time of $\mathsf {A}$.

Some algorithms such as $\mathsf {Gen}$ need a security parameter $\lambda \in \mathbb {N}$ as input. However, we usually omit it for simplicity. We say a function is negligible in $\lambda$ if $f(\lambda )=\lambda ^{-\omega (1)}$. PPT stands for probabilistic polynomial time.

2.2 Quantum Computation

We refer to [19] for basic of quantum computation. In this subsection we mainly present several useful lemmas.

Quantum Random Oracle Model. Following [3, 6], we review a quantum oracle O as a mapping

where $O:\{0,1\}^n\rightarrow \{0,1\}^m,x\in \{0,1\}^n$ and $y\in \{0,1\}^m$. Roughly speaking, the quantum random oracle model (QROM) is an idealized model where a hash function is modeled as a publicly and quantumly accessible random oracle, while adversaries are only given classical oracle access in the classical random oracle model (ROM).

Lemma 1

([20, Lemma 2.2]). Let l be an integer. Let $\mathsf {H}:\{0,1\}^l\times X\rightarrow Y$ and $\mathsf {H'}:X\rightarrow Y$ be two independent random oracles. If an unbounded time quantum adversary $\mathcal {A}$ makes a query to $\mathsf {H}$ at most $q_\mathsf {H}$ times, then we have

$$\left| \Pr [1\leftarrow \mathcal {A}^{\mathsf {H,H}(s,\cdot )}|s\leftarrow \{0,1\}^l]-\Pr [1\leftarrow \mathcal {A}^\mathsf {H,H'}]\right| \le q_\mathsf {H}\cdot 2^\frac{-l+1}{2}$$

where all oracle accesses of $\mathcal {A}$ can be quantum.

Lemma 2

(Generic Distinguishing Problem with Bounded Probabilities [1, 13, 14]). Let X be a finite set, and let $\lambda \in [0,1]$. $\mathsf {F_1}:X\rightarrow \{0,1\}$ is the following function: For each $x\in X,\ \mathsf {F_1}(x)=1$ with probability $\lambda _x\ (\lambda _x\le \lambda )$, and $\mathsf {F_1}(x)=0$ else. $\mathsf {F_2}$ is the constant zero function. Then, for any algorithm $\mathsf {A}$ issuing at most q quantum queries to $\mathsf {F_1}$ or $\mathsf {F_2}$, $|\Pr [1\leftarrow \mathsf {A^{F_1}}]-\Pr [1\leftarrow \mathsf {A^{F_2}}]|\le 8q^2\lambda$.

Lemma 3

(Measure-Rewind-Measure One-Way to Hiding [18, Lemma 3.3]). Let $G,H: X\rightarrow Y$ be random functions, z be a random value, and $S\subseteq X$ be a random set such that $G(x)=H(x)$ for every $x\notin S$. The tuple (G, H, S, z) may have arbitrary joint distribution. Furthermore, let $\mathcal {A}^O$ be a quantum oracle algorithm which queries oracle O with query depth d. Then we can construct an algorithm $\mathcal {D}^{G,H}(z)$ such that $\mathsf {Time}(\mathcal {D}^{G,H})\approx 2\cdot \mathsf {Time}(\mathcal {A}^O)$² and

Here with

and

2.3 Public-Key Encryption

Definition 1

($\mathsf {PKE}$). A (randomized) public-key encryption scheme $(\mathsf {(r)PKE})$ is defined over a message space $\mathcal {M}$, a ciphertext space $\mathcal {C}$, a public key space $\mathcal {PK}$ and a secret key space $\mathcal {SK}$. It consists of a triple of algorithms $\mathsf {PKE=(Gen,Enc,Dec)}$ defined as follows.

• $\mathsf {Gen}\rightarrow (pk,sk)$ is a randomized algorithm that returns a public key $pk\in \mathcal {PK}$ and a secret key $sk\in \mathcal {SK}$.

• $\mathsf {Enc}(pk,m)\rightarrow c$ is a randomized algorithm that takes as input a public key pk and a message $m\in \mathcal {M}$, and outputs a ciphertext $c\in \mathcal {C}$. If necessary, we make the used randomness of $\mathsf {Enc}$ explicit by writing , where $r\xleftarrow {\$}\mathcal {R}$ and $\mathcal {R}$ is the randomness space.

• $\mathsf {Dec}(sk,c)\rightarrow m/\perp$ is a deterministic algorithm that takes as input a secret key $sk\in \mathcal {SK}$ and a ciphertext $c\in \mathcal {C}$ and returns either a message $m\in \mathcal {M}$ or a failure symbol $\perp \ \notin \mathcal {M}$.

A deterministic public-key encryption scheme $(\mathsf {dPKE})$ is defined the same way, except that $\mathsf {Enc}$ is a deterministic algorithm.

Definition 2

(Correctness [12]). A public-key encryption scheme $\mathsf {PKE}$ is $\delta$-correct if

$$\mathrm E\left[ \max _{m\in \mathcal {M}}\Pr [\mathsf {Dec}(sk,c)\ne m|c\leftarrow \mathsf {Enc}(pk,m)]\right] \le \delta ,$$

where the expectation is taken over $(pk,sk)\leftarrow \mathsf {Gen}$. We say the $\mathsf {PKE}$ is perfectly correct if $\delta =0$.

Remark 1

Above correctness definition is in the standard model, there is no random oracle relative to the $\mathsf {PKE}$. But we still use this definition in the random oracle model if random oracles have no effect on it.

Let $\mathsf {PKE=(Gen,Enc,Dec)}$ be a public-key encryption scheme with message space $\mathcal {M}$. We now define three security notions for it. We say the $\mathsf {PKE}$ is $\mathsf {GOAL}\text {-}\mathsf{ATK}$ secure if $\mathsf {Adv_{PKE,\mathcal {A}}^{GOAL}\text {-}\mathsf{ATK}}$ is negligible for any PPT adversary $\mathcal {A}$.

Definition 3

($\mathsf {OW}\text {-}\mathsf{CPA}$). The One-Wayness under Chosen Plaintext Attacks $(\mathsf {OW}\text {-}\mathsf{CPA})$ game for $\mathsf {PKE}$ is defined in Fig. 2, and the $\mathsf {OW}\text {-}\mathsf{CPA}$ advantage of an adversary $\mathcal {A}$ against $\mathsf {PKE}$ is defined as .

Fig. 2.

Games $\mathsf {OW}\text {-}\mathsf{CPA}$ and $\mathsf {IND}\text {-}\mathsf{CPA}$ for $\mathsf {PKE}$.

Definition 4

($\mathsf {IND}\text {-}\mathsf{CPA}$). The Indistinguishability under Chosen Plaintext Attacks $(\mathsf {IND}\text {-}\mathsf{CPA})$ game for $\mathsf {PKE}$ is defined in Fig. 2, and the $\mathsf {IND}\text {-}\mathsf{CPA}$ advantage of an adversary $\mathcal {A=(A}_1,\mathcal {A}_2)$ against $\mathsf {PKE}$ is defined as .

Definition 5

($\mathsf {IND}\text {-}\mathsf{qCCA}$ [7]). The Indistinguishability under quantum Chosen Ciphertext Attacks $(\mathsf {IND}\text {-}\mathsf{qCCA})$ game for $\mathsf {PKE}$ is defined in Fig. 3, and the $\mathsf {IND}\text {-}\mathsf{qCCA}$ advantage of an adversary $\mathcal {A=(A}_1,\mathcal {A}_2)$ against $\mathsf {PKE}$ is defined as .

Fig. 3.

Game $\mathsf {IND}\text {-}\mathsf{qCCA}$ for $\mathsf {PKE}$.

Saito, Xagawa and Yamakawa [20] introduced a new security notion named $\mathsf {DS}$ for $\mathsf {dPKE}$. Here we give a modified version and we keep the name unchanged in this paper.

Definition 6

($\mathsf {DS}$, modified from [20]). Let $\mathcal {D_M}$ denote an efficiently sampleable distribution on a set $\mathcal {M}$. A deterministic public-key encryption scheme $\mathsf {PKE=(Gen,Enc,Dec)}$ with plaintext and ciphertext spaces $\mathcal {M}$ and $\mathcal {C}$ is $\mathcal {D_M}$-disjoint-simulatable $(\mathsf {DS})$ if there exists a PPT algorithm $\mathcal {S}$ that satisfies the followings.

• Disjointness:

  

  is negligible.

• Ciphertext-indistinguishability: For any PPT adversary $\mathcal {A}$,

  
  

  is negligible.

Remark 2

In the original definition of $\mathsf {DS}$, the first condition is “statistical disjointness”:

is negligible, where $\lambda$ is the security parameter and $\mathcal {R}$ denotes the randomness space for $\mathsf {Gen}$. We relax this condition to “disjointness” as we find it is sufficient to prove those theorems we needed.

2.4 Key Encapsulation Mechanism

Definition 7

($\mathsf {KEM}$). A key encapsulation mechanism $(\mathsf {KEM})$ is defined over a key space $\mathcal {K}$, a ciphertext space $\mathcal {C}$, a public key space $\mathcal {PK}$ and a secret key space $\mathcal {SK}$. It consists of a triple of algorithms $\mathsf {KEM=(Gene,Enca,Deca)}$ defined as follows.

• $\mathsf {Gene}\rightarrow (pk,sk)$ is a randomized algorithm that returns a public key $pk\in \mathcal {PK}$ and a secret key $sk\in \mathcal {SK}$.

• $\mathsf {Enca}(pk)\rightarrow (c,k)$ is a randomized algorithm that takes as input a public key pk and outputs a ciphertext $c\in \mathcal {C}$ as well as a key $k\in \mathcal {K}$.

• $\mathsf {Deca}(sk,c)\rightarrow k/\perp$ is a deterministic algorithm that takes as input a secret key $sk\in \mathcal {SK}$ and a ciphertext $c\in \mathcal {C}$ and returns either a key $k\in \mathcal {K}$ or a failure symbol $\perp \ \notin \mathcal {K}$.

Definition 8

(Correctness [12]). A key encapsulation mechanism $\mathsf {KEM}$ is $\delta$-correct if

$$\Pr [\mathsf {Deca}(sk,c)\ne k|(pk,sk)\leftarrow \mathsf {Gene},(c,k)\leftarrow \mathsf {Enca}(pk)]\le \delta .$$

Let $\mathsf {KEM=(Gene,Enca,Deca)}$ be a key encapsulation mechanism with key space $\mathcal {K}$. Following the definition of $\mathsf {IND}\text {-}\mathsf{qCCA}$ for $\mathsf {PKE}$, the $\mathsf {KEM}$ version for it can be defined similarly. We say the $\mathsf {KEM}$ is $\mathsf {IND}\text {-}\mathsf{qCCA}$ secure if is negligible for any PPT adversary $\mathcal {A}$.

Definition 9

($\mathsf {IND}\text {-}\mathsf{qCCA}$ [22]). The $\mathsf {IND}\text {-}\mathsf{qCCA}$ game for $\mathsf {KEM}$ is defined in Fig. 4, and the $\mathsf {IND}\text {-}\mathsf{qCCA}$ advantage of an adversary $\mathcal {A}$ against $\mathsf {KEM}$ is defined as .

Fig. 4.

Game $\mathsf {IND}\text {-}\mathsf{qCCA}$ for $\mathsf {KEM}$.

3 Tighter Proofs for the Transformation KC

In this section, we give a tighter security reduction for the transformation $\mathsf {KC}$ [20] that transforms $\mathsf {OW}\text {-}\mathsf{CPA}$ secure $\mathsf {dPKE}$s into $\mathsf {DS}$ secure $\mathsf {dPKE}$s without the perfect correctness requirement of underlying $\mathsf {PKE}$s.

Transformation KC . To a deterministic public-key encryption scheme $\mathsf {PKE=}$ $\mathsf {(Gen,Enc,Dec)}$ with message space $\mathcal {M}$, and a hash function $\mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n$, we associate . The algorithms of $\mathsf {PKE'=(Gen',Enc',Dec')}$ are defined in Fig. 5.

Fig. 5.

with simulator $\mathcal {S}$.

Before we prove the security of $\mathsf {KC}$, we first review the transformation $\mathsf {T}$ introduced in [12].

Transformation T . To a public-key encryption scheme $\mathsf {PKE_0=(Gen_0,Enc_0,}$ $\mathsf {Dec_0)}$ with message space $\mathcal {M}$ and randomness space $\mathcal {R}$, and a hash function $\mathsf {G}:\mathcal {M\rightarrow R}$, we associate . The algorithms of $\mathsf {PKE=(Gen,Enc,}$ $\mathsf {Dec)}$ are defined in Fig. 6.

Fig. 6.

.

Next, we give a lemma related to the transformation $\mathsf {T}$. It roughly speaks that there is a high probability the ciphertext corresponding to a randomly chosen message has only one preimage with regard to .

Lemma 4

Let $\mathsf {PKE_0=(Gen_0,Enc_0,Dec_0)}$ be a $\delta$-correct $\mathsf {rPKE}$ with message space $\mathcal {M}$ and randomness space $\mathcal {R}$. We define a set with respect to fixed (pk, sk) and $\mathsf {G}\in \varOmega _\mathsf {G}:$

where $\varOmega _\mathsf {G}$ denotes the set of all functions $\mathsf {G}:\mathcal {M\rightarrow R}$.

Then we have

$$\Pr [m\in S_{(pk,sk),\mathsf {G}}^{collision}|(pk,sk)\leftarrow \mathsf {Gen_0},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G},m\xleftarrow {\$}\mathcal {M}]\le 2\delta .$$

Proof

From the definition of $\delta$-correct, we have

The inequality still holds when the m is chosen at random, i.e.,

We represent above inequality in a different form with equivalent meaning:

$$\Pr [\mathsf {Dec_0}(sk,c)\ne m|(pk,sk)\leftarrow \mathsf {Gen_0},m\xleftarrow {\$}\mathcal {M},c\leftarrow \mathsf {Enc_0}(pk,m)]\le \delta .$$

Then we make the randomness used by $\mathsf {Enc_0}$ explicit:

$$\Pr [\mathsf {Dec_0}(sk,\mathsf {Enc_0}(pk,m;r))\ne m|(pk,sk)\leftarrow \mathsf {Gen_0},m\xleftarrow {\$}\mathcal {M},r\xleftarrow {\$}\mathcal {R}]\le \delta .$$

It equals that:

$$\Pr [\mathsf {Dec_0}(sk,\mathsf {Enc_0}(pk,m;\mathsf {G}(m)))\ne m|(pk,sk)\leftarrow \mathsf {Gen_0},m\xleftarrow {\$}\mathcal {M},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G}]\le \delta .$$

Here we define a set in which messages are incorrectly decrypted with respect to fixed (pk, sk) and $\mathsf {G}$:

Finally, we have

$$\begin{aligned}&\Pr [m\in S_{(pk,sk),\mathsf {G}}^{collision}|(pk,sk)\leftarrow \mathsf {Gen_0},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G},m\xleftarrow {\$}\mathcal {M}]\\&\le 2\Pr [m\in S_{(pk,sk),\mathsf {G}}^{collision}\cap S_{(pk,sk),\mathsf {G}}^{error}|(pk,sk)\leftarrow \mathsf {Gen_0},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G},m\xleftarrow {\$}\mathcal {M}]\\&\le 2\Pr [m\in S_{(pk,sk),\mathsf {G}}^{error}|(pk,sk)\leftarrow \mathsf {Gen_0},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G},m\xleftarrow {\$}\mathcal {M}]\\&=2\Pr [\mathsf {Dec_0}(sk,\mathsf {Enc_0}(pk,m;\mathsf {G}(m)))\ne m|(pk,sk)\leftarrow \mathsf {Gen_0},m\xleftarrow {\$}\mathcal {M},\mathsf {G}\xleftarrow {\$}\varOmega _\mathsf {G}]\\&\le 2\delta , \end{aligned}$$

where the first inequality follows from the fact that m is chosen randomly and $|S_{(pk,sk),\mathsf {G}}^{collision}\setminus S_{(pk,sk),\mathsf {G}}^{error}|\le |S_{(pk,sk),\mathsf {G}}^{collision}\cap S_{(pk,sk),\mathsf {G}}^{error}|$ for fixed (pk, sk) and $\mathsf {G}$.    $\square$

Now we are ready to prove the security of $\mathsf {KC}$ in the QROM. In particular, we prove it in two cases. The first case is that the underlying $\mathsf {dPKE}$ is derived from $\mathsf {T}$, as opposed to a general $\delta$-correct $\mathsf {dPKE}$ in the second case. In both cases, underlying $\mathsf {PKE}$s don’t need to be perfectly correct.

Previous proofs [17, 20] use some variants of O2H lemma, but they all incur a quadratic loss of security. Kuchta et al. [18] recently introduced the MRM O2H lemma (Lemma 3) without the square-root advantage loss. We apply it to $\mathsf {KC}$ and we avoid the square-root advantage loss in the proof accordingly.

Theorem 1

(Security of $\mathsf {KC}$ in the QROM, Case 1). Let $\mathsf {PKE}$ be a $\mathsf {dPKE}$ transformed from $\mathsf {PKE_0}$ by $\mathsf {T}$, i.e., . $\mathsf {PKE_0}$ is a $\delta$-correct $\mathsf {rPKE}$ with message space $\mathcal {M}$ and randomness space $\mathcal {R}$. Let $\mathsf {G}:\mathcal {M\rightarrow R},\ \mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n$ be hash functions modeled as quantum random oracles. $\mathsf {H]}$ and $\mathcal {S}$ is the algorithm defined in Fig. 5. Then we have $\mathsf {Disj_{PKE',\mathcal {S}}}\le 2^{-n}+2\delta$. Moreover, for any adversary $\mathcal {A}$ against the $\mathsf {DS}\text {-}\mathsf{IND}$ security of $\mathsf {PKE'}$ issuing quantum queries to $\mathsf {H}$ with depth $d_\mathsf {H}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {OW}\text {-}\mathsf{CPA}$ security of $\mathsf {PKE}$ such that

and $\mathsf {Time}(\mathcal {B})\approx 2\cdot \mathsf {Time}(\mathcal {A})$.

Proof

We first define two events:

where $S_{(pk,sk),\mathsf {G}}^{collision}$ is defined in Lemma 4, and Lemma 4 says that $\Pr [\mathsf {Bad}]\le 2\delta$ as $\mathsf {Gen}$ equals $\mathsf {Gen_0}$;

Then, we have

$$\begin{aligned} \mathsf {Disj_{PKE',\mathcal {S}}}&=\Pr [\mathsf {Disj}]\\&=\Pr [\mathsf {Disj\wedge \overline{Bad}}]+\Pr [\mathsf {Disj\wedge Bad}]\\&\le \Pr [\mathsf {Disj\wedge \overline{Bad}}]+\Pr [\mathsf {Bad}]\\&\le 2^{-n}+2\delta , \end{aligned}$$

where the first equality follows from the definition of $\mathsf {DS}$ and the last inequality follows from the fact that if $\mathsf {Bad}$ doesn’t happen, the only possibility that $\mathsf {Disj}$ happens is the second part $d^*$ of the element returned by $\mathcal {S}$ collides with the unique value which is $\mathsf {H}(m^*).$ The probability of this is $2^{-n}$ as $d^*$ is chosen uniformly at random.

To prove the rest of the theorem, we consider games in Fig. 7. From the definition of $\mathsf {DS}$, we have

Fig. 7.

Games $G_0-G_2$ for the proof of Theorem 1.

Notice that $\mathsf {H'},d^*$ in game $G_2$ are randomly distributed as $\mathsf {H},d^*$ in game $G_1$, and they are independent of each other and $\mathcal {A}$’s other view ($\mathsf {G},pk,c^*$) in both $G_1$ and $G_2$, that is, the environments of $\mathcal {A}$ in $G_1$ and $G_2$ have the same distribution. It follows that

$$\Pr [G_1^{\mathcal {A}}\Rightarrow 1]=\Pr [G_2^{\mathcal {A}}\Rightarrow 1].$$

The only difference between game $G_0$ and game $G_2$ is that $\mathcal {A}$ is interacted with $\mathsf {H}$ or $\mathsf {H'}$ respectively. Therefore, applying Lemma 3 with $X=\mathcal {M},Y=\{0,1\}^n,G=\mathsf {H},H=\mathsf {H'},S=S_{c^*},z=(\mathsf {G},pk,(c^*,d^*))$³ and $\mathcal {A}$, we can construct algorithm $\mathcal {D}$, with run-time $\approx 2\cdot \mathsf {Time}(\mathcal {A})$ and making oracle calls to $\mathsf {H,\ H'}$ and $\mathsf {G}$ in game $G_3$, such that

$$|\Pr [G_0^{\mathcal {A}}\Rightarrow 1]-\Pr [G_2^{\mathcal {A}}\Rightarrow 1]|\le 4d_\mathsf {H}\cdot \Pr [T\cap S_{c^*}\ne \varnothing ],$$

where T is the output of $\mathcal {D}$ and game $G_3$ is described in Fig. 8.

Fig. 8.

Game $G_3$ for the proof of Theorem 1.

The game $G_3$ actually can be seen as the $\mathsf {OW}\text {-}\mathsf{CPA}$ game for $\mathsf {PKE}$, in which an adversary $\mathcal {B}$ invokes the algorithm $\mathcal {D}$. More specifically, the $\mathsf {OW}\text {-}\mathsf{CPA}$ game for $\mathsf {PKE}$ and the adversary $\mathcal {B}$ against $\mathsf {PKE}$ we construct are described in Fig. 9. We note that $\mathcal {B}$ cannot directly compute $\mathsf {H}(m^*)$ because $m^*$ is unknown for $\mathcal {B}$, but $\mathcal {B}$ can choose a random value $d^*\in \{0,1\}^n$ as $\mathsf {H}(m^*)$ in advance and simulate $\mathsf {H}$ using it, i.e., $\mathcal {B}$ returns $d^*$ if $\mathsf {Enc}(pk,m)=c^*$, else returns $\mathsf {H}(m)$, where m is $\mathcal {D}$’s query to $\mathsf {H}$. Furthermore, if $\mathsf {Bad}$ doesn’t happen, the set $S_{c^*}$ has only one element, $m^*$, and the environments of $\mathcal {D}$ in game $G_3$ and game have the same distribution. In other words, $\mathcal {B}$ can simulate the environment for $\mathcal {D}$ as in game $G_3$ perfectly in the case that $\mathsf {Bad}$ doesn’t happen. Therefore, we have

where the final equality holds for the same reason that if $\mathsf {Bad}$ doesn’t happen, the set $S_{c^*}$ has only one element, $m^*$.

Fig. 9.

Game for the proof of Theorem 1.

Combining above formulas with the following simple inequality:

$$\Pr [T\cap S_{c^*}\ne \varnothing ]\le \Pr [T\cap S_{c^*}\ne \varnothing \wedge \mathsf {\overline{Bad}}]+\Pr [\mathsf {Bad}],$$

we finally obtain

   $\square$

Theorem 2

(Security of $\mathsf {KC}$ in the QROM, Case 2). Let $\mathsf {PKE}$ be a $\delta$-correct $\mathsf {dPKE}$ with message space $\mathcal {M}$. Let $\mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n$ be a hash function modeled as a quantum random oracle. and $\mathcal {S}$ is the algorithm defined in Fig. 5. Then we have $\mathsf {Disj_{PKE',\mathcal {S}}}\le 2^{-n}+\delta$. Moreover, for any adversary $\mathcal {A}$ against the $\mathsf {DS}\text {-}\mathsf{IND}$ security of $\mathsf {PKE'}$ issuing quantum queries to $\mathsf {H}$ with depth $d_\mathsf {H}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {OW}\text {-}\mathsf{CPA}$ security of $\mathsf {PKE}$ such that

and $\mathsf {Time}(\mathcal {B})\approx 2\cdot \mathsf {Time}(\mathcal {A})$.

Proof

The proof is essentially the same as Theorem 1’s proof, except for the definition of $\mathsf {Bad}$:

From the fact that $\mathsf {PKE}$ is deterministic and the definition of $\delta$-correct, we have

$$\Pr [\mathsf {Bad}]\le \delta .$$

Then, we complete the proof.    $\square$

Remark 3

$\mathsf {PKE'}$ remains $\delta$-correct.

4 QCCA-Secure Generic KEM in the QROM

In this section, we prove that $\mathsf {DS}$ secure $\mathsf {dPKE}$s can be converted to $\mathsf {IND}\text {-}\mathsf{qCCA}$ secure $\mathsf {KEM}$s by transformation $\mathsf {SXY}$ [20] in the QROM. In particular, we also consider two cases corresponding to the two cases in Sect. 3. The first case is that the underlying $\mathsf {dPKE}$ is derived from $\mathsf {KC\circ T}$⁴, as opposed to a general $\delta$-correct $\mathsf {dPKE}$ in the second case. In both cases, underlying $\mathsf {PKE}$s don’t need to be perfectly correct. Note that the second case was proved in [22], we present it here as a lemma.

At the end, we combine results in this paper and get two $\mathsf {IND}\text {-}\mathsf{qCCA}$ secure generic $\mathsf {KEM}$s without quadratic security loss in the QROM. One is based on $\mathsf {rPKE}$s and the other is based on $\mathsf {dPKE}$s.

Transformation SXY . To a deterministic public-key encryption scheme $\mathsf {PKE'=}$ $\mathsf {(Gen',Enc',Dec')}$ with message space $\mathcal {M}$ and ciphertext space $\mathcal {C}$, and two hash functions $\mathsf {H_1}:\mathcal {M\rightarrow K},\ \mathsf {H_2}:\{0,1\}^l\times \mathcal {C}\rightarrow \mathcal {K}$, we associate $\mathsf {H_2]}$. The algorithms of $\mathsf {KEM=(Gene,Enca,Deca)}$ are defined in Fig. 10.

Fig. 10.

.

Theorem 3

($\mathsf {IND}\text {-}\mathsf{qCCA}$ Security of $\mathsf {SXY}$ in the QROM, Case 1). Let $\mathsf {PKE'}$ be a $\mathsf {dPKE}$ transformed from $\mathsf {PKE_0}$ by $\mathsf {KC\circ T}$, i.e., . $\mathsf {PKE_0}$ is a $\delta$-correct $\mathsf {rPKE}$ with message space $\mathcal {M}$, ciphertext space $\mathcal {C}$ and randomness space $\mathcal {R}$. Let $\mathsf {G}:\mathcal {M\rightarrow R},\ \mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n,\ \mathsf {H_1}:\mathcal {M\rightarrow K},\ \mathsf {H_2}:\{0,1\}^l\times \mathcal {C}\times \{0,1\}^n\rightarrow \mathcal {K}$ be hash functions modeled as quantum random oracles. Suppose that $\mathsf {PKE'}$ is $\mathcal {D_M}$-disjoint-simulatable with a simulator $\mathcal {S}$. Then for any adversary $\mathcal {A}$ against the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of issuing $q_\mathsf {G}$ and $q_\mathsf {H_2}$ quantum queries to $\mathsf {G}$ and $\mathsf {H_2}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {DS}\text {-}\mathsf{IND}$ security of $\mathsf {PKE'}$ such that

and $\mathsf {Time}(\mathcal {B})\approx \mathsf {Time}(\mathcal {A})$.

Proof

We use a game-hopping proof. The proof is essentially the same as the following Lemma 5 [22]’s proof, except for two more games. We insert game $G_{0.5}$ and $G_{3.5}$ into $G_{0},G_{1}$ and $G_{3},G_{4}$ respectively. Besides, we replace the event $\overline{\mathsf {Acc}}$ with another event $\mathsf {Bad}$. The overview of all games is given in Table 2.

Table 2. Summary of games for the proof of Theorem 3.

$\mathbf{GAME} G_0$: This is the original game, .

Let $\mathsf {G'}$ be a random function such that $\mathsf {G'}(m)$ is sampled according to the uniform distribution over . Let $\varOmega _\mathsf {G'}$ be the set of all functions $\mathsf {G'}$. Define $\delta _{(pk,sk),m}=\frac{|\mathcal {R}\setminus \mathcal {R}_{(pk,sk),m}^{good}|}{|\mathcal {R}|}$ as the fraction of bad randomness and $\delta _{(pk,sk)}=\max _{m\in \mathcal {M}}\delta _{(pk,sk),m}$. With this notation $\delta =\mathrm E[\delta _{(pk,sk)}]$, where the expectation is taken over $(pk,sk)\leftarrow \mathsf {Gen_0}$.

$\mathbf{GAME} G_{0.5}$: This game is the same as $G_0$ except that we replace $\mathsf {G}$ by $\mathsf {G'}$ that uniformly samples from “good” randomness at random, i.e., $\mathsf {G'}\xleftarrow {\$}\varOmega _\mathsf {G'}$.

$\mathbf{GAME} G_1$: This game is the same as $G_{0.5}$ except that $\mathsf {H_2}(s,c)$ in the decapsulation oracle is replaced with $\mathsf {H}_q(c)$ where $\mathsf {H}_q: \mathcal {C}\times \{0,1\}^n\rightarrow \mathcal {K}$ is another random oracle. We remark that $\mathcal {A}$ is not given direct access to $\mathsf {H}_q$.

$\mathbf{GAME} G_{1.5}$: This game is the same as $G_1$ except that the random oracle $\mathsf {H_1}(\cdot )$ is simulated by $\mathsf {H}_q'(\mathsf {Enc'}(pk,\cdot ))$ where $\mathsf {H}_q'$ is yet another random oracle. We remark that the decapsulation oracle and generation of $k_0^*$ also use $\mathsf {H}_q'(\mathsf {Enc'}(pk,\cdot ))$ as $\mathsf {H_1}(\cdot )$ and that $\mathcal {A}$ is not given direct access to $\mathsf {H}_q'$.

$\mathbf{GAME} G_2$: This game is the same as $G_{1.5}$ except that the random oracle $\mathsf {H_1}(\cdot )$ is simulated by $\mathsf {H}_q(\mathsf {Enc'}(pk,\cdot ))$ instead of $\mathsf {H}_q'(\mathsf {Enc'}(pk,\cdot ))$. We remark that the decapsulation oracle and generation of $k_0^*$ also use $\mathsf {H}_q(\mathsf {Enc'}(pk,\cdot ))$ as $\mathsf {H_1}(\cdot )$.

$\mathbf{GAME} G_3$: This game is the same as $G_2$ except that $k_0^*$ is set as $\mathsf {H}_q(c^*)$ and the decapsulation oracle always returns $\mathsf {H}_q(c)$ as long as $c\ne c^*$. We denote the modified decapsulation oracle by $\mathsf {Deca}'$.

$\mathbf{GAME} G_{3.5}$: This game is the same as $G_3$ except that we switch $\mathsf {G'}$ back to the ideal random oracle $\mathsf {G}$.

$\mathbf{GAME} G_4$: This game is the same as $G_{3.5}$ except that $c^*$ is set as $\mathcal {S}(pk)$.

The above completes the descriptions of games. We clearly have

by the definition. We bound this by the following claims.

Claim 1

We have

$$|\Pr [G_0\Rightarrow 1]-\Pr [G_{0.5}\Rightarrow 1]|\le 8q^2_\mathsf {G}\delta ,$$

$$|\Pr [G_3\Rightarrow 1]-\Pr [G_{3.5}\Rightarrow 1]|\le 8q^2_\mathsf {G}\delta .$$

Proof

Following the same analysis as in the proof of [15, Theorem 1], we can show that the distinguishing problem between $G_0$ and $G_{0.5}$ is essentially the distinguishing problem between $\mathsf {G}$ and $\mathsf {G}'$, which can be converted into a distinguishing problem between $\mathsf {F_1}$ and $\mathsf {F_2}$, where $\mathsf {F_1}$ is a function such that $\mathsf {F_1}(m)$ is sampled according to Bernoulli distribution $B_{\delta _{(pk,sk),m}}$, i.e., $\Pr [\mathsf {F_1}(m)=1]=\delta _{(pk,sk),m}$ and $\Pr [\mathsf {F_1}(m)=0]=1-\delta _{(pk,sk),m}$, and $\mathsf {F_2}$ is a constant function that always outputs 0 for any input. Thus, conditioned on a fixed (pk, sk) we obtain by Lemma 2, $|\Pr [G_0\Rightarrow 1|(pk,sk)]-\Pr [G_{0.5}\Rightarrow 1|(pk,sk)]|\le 8q^2_\mathsf {G}\delta _{(pk,sk)}$. By averaging over $(pk,sk)\leftarrow \mathsf {Gen_0}$ we finally obtain

$$|\Pr [G_0\Rightarrow 1]-\Pr [G_{0.5}\Rightarrow 1]|\le 8q^2_\mathsf {G}\mathrm E[\delta _{(pk,sk)}]=8q^2_\mathsf {G}\delta .$$

In the same way, we have

$$|\Pr [G_3\Rightarrow 1]-\Pr [G_{3.5}\Rightarrow 1]|\le 8q^2_\mathsf {G}\delta .$$

   $\square$

Claim 2

We have

$$|\Pr [G_{0.5}\Rightarrow 1]-\Pr [G_1\Rightarrow 1]|\le q_\mathsf {H_2}\cdot 2^\frac{-l+1}{2}.$$

Proof

This is obvious from Lemma 1.    $\square$

Claim 3

We define an event:

Then we have $\Pr [\mathsf {Bad}]\le \delta$ and

$$|\Pr [G_1\Rightarrow 1]-1/2|\le |\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|+\delta .$$

Proof

By the definition, we have

$$\begin{aligned}&\Pr [\mathsf {Bad}]\\&=\Pr [\exists m\in \mathcal {M}, \mathcal {R}_{(pk,sk),m}^{good}=\varnothing |(pk,sk)\leftarrow \mathsf {Gen_0}]\\&=\Pr [\exists m\in \mathcal {M}, \delta _{(pk,sk),m}=1|(pk,sk)\leftarrow \mathsf {Gen_0}]\\&=\Pr [\delta _{(pk,sk)}=1|(pk,sk)\leftarrow \mathsf {Gen_0}]\\&\le \mathrm E[\delta _{(pk,sk)}]\\&=\delta . \end{aligned}$$

Then we have

$$\begin{aligned}&|\Pr [G_1\Rightarrow 1]-1/2|\\&=|\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]+\Pr [G_1\Rightarrow 1\wedge \mathsf {Bad}]-1/2|\\&\le |\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|+\Pr [G_1\Rightarrow 1\wedge \mathsf {Bad}]\\&\le |\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|+\Pr [\mathsf {Bad}]\\&\le |\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|+\delta \end{aligned}$$

as we wanted.    $\square$

Claim 4

We have

$$\Pr [G_1\Rightarrow 1\wedge \overline{\mathsf {Bad}}]=\Pr [G_{1.5}\Rightarrow 1\wedge \overline{\mathsf {Bad}}].$$

Proof

From the definition of $\mathsf {G'}$, if $\mathsf {Bad}$ doesn’t happen, any message can be decrypted correctly for the $\mathsf {PKE'}$, i.e., $\mathsf {Dec'}(sk,\mathsf {Enc'}(pk,m))=m$ for all $m\in \mathcal {M}$. Therefore, $\mathsf {Enc'}(pk,\cdot )$ is injective. And if $\mathsf {H}_q'(\cdot )$ is a random function, then $\mathsf {H}_q'(\mathsf {Enc'}(pk,\cdot ))$ is also a random function. Remarking that access to $\mathsf {H}_q'$ is not given to $\mathcal {A}$, it causes no difference from the view of $\mathcal {A}$ if we replace $\mathsf {H_1}(\cdot )$ with $\mathsf {H}_q'(\mathsf {Enc'}(pk,\cdot ))$.    $\square$

Claim 5

We have

$$\Pr [G_{1.5}\Rightarrow 1\wedge \overline{\mathsf {Bad}}]=\Pr [G_2\Rightarrow 1\wedge \overline{\mathsf {Bad}}].$$

Proof

We say that a ciphertext c is valid if we have $\mathsf {Enc'}(pk,\mathsf {Dec'}(sk,c))=c$ and invalid otherwise. We remark that $\mathsf {H}_q$ is used only for decrypting an invalid ciphertext c as $\mathsf {H}_q(c)$ in $G_{1.5}$. This means that a value of $\mathsf {H}_q(c)$ for a valid c is not used at all in $G_{1.5}$.

On the other hand, any output of $\mathsf {Enc'}(pk,\cdot )$ is valid if $\mathsf {Bad}$ doesn’t happen. Since $\mathsf {H}_q'$ is only used for evaluating an output of $\mathsf {Enc'}(pk,\cdot )$, a value of $\mathsf {H}_q'(c)$ for an invalid c is not used at all in $G_{1.5}$.

Hence, it causes no difference from the view of $\mathcal {A}$ if we use the same random oracle $\mathsf {H}_q$ instead of two independent random oracles $\mathsf {H}_q$ and $\mathsf {H}_q'$.    $\square$

Claim 6

We have

$$\Pr [G_2\Rightarrow 1\wedge \overline{\mathsf {Bad}}]=\Pr [G_3\Rightarrow 1\wedge \overline{\mathsf {Bad}}].$$

Proof

Since we set , for any valid c and , we have $\mathsf {H_1}(m)=\mathsf {H}_q(\mathsf {Enc'}(pk,m))=\mathsf {H}_q(c)$. Therefore, responses of the decapsulation oracle are unchanged. We also have $\mathsf {H_1}(m^*)=\mathsf {H}_q(c^*)$.    $\square$

Claim 7

We have

$$|\Pr [G_3\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|\le |\Pr [G_3\Rightarrow 1]-1/2|+\delta .$$

Proof

We have

$$\begin{aligned}&|\Pr [G_3\Rightarrow 1\wedge \overline{\mathsf {Bad}}]-1/2|\\&=|\Pr [G_3\Rightarrow 1]-\Pr [G_3\Rightarrow 1\wedge \mathsf {Bad}]-1/2|\\&\le |\Pr [G_3\Rightarrow 1]-1/2|+\Pr [G_3\Rightarrow 1\wedge \mathsf {Bad}]\\&\le |\Pr [G_3\Rightarrow 1]-1/2|+\Pr [\mathsf {Bad}]\\&\le |\Pr [G_3\Rightarrow 1]-1/2|+\delta . \end{aligned}$$

   $\square$

Claim 8

There exists a quantum adversary $\mathcal {B}$ such that

and $\mathsf {Time}(\mathcal {B})\approx \mathsf {Time}(\mathcal {A})$.

Proof

We construct an adversary $\mathcal {B}$, which is allowed to access two random oracles $\mathsf {H}_q$ and $\mathsf {H}_2$, against the disjoint simulatability as follows.

$\mathcal {B}^{\mathsf {H}_q,\mathsf {H}_2}(pk,c^*)$: It picks $b\leftarrow \{0,1\}$, sets and $k_1^*\xleftarrow {\$}\mathcal {K}$, and invokes $b'\leftarrow \mathcal {A}^{\mathsf {H_1,H_2,Deca'}}(pk,c^*,k_b^*)$ where $\mathcal {A}$’s oracles are simulated as follows.

• $\mathsf {H_1}(\cdot )$ is simulated by $\mathsf {H}_q(\mathsf {Enc'}(pk,\cdot ))$.

• $\mathsf {H_2}$ can be simulated because $\mathcal {B}$ has access to an oracle $\mathsf {H_2}$.

• $\mathsf {Deca'}$ is simulated by filtering $c^*$ and using $\mathsf {H}_q(\cdot )$, that is, on input $\sum _{c,k}\psi _{c,k}$ , $\mathcal {B}$ returns .

Finally, $\mathcal {B}$ returns $\llbracket b'=b\rrbracket$.

This completes the description of $\mathcal {B}$. It is easy to see that $\mathcal {B}$ perfectly simulates $G_{3.5}$ if $c^*=\mathsf {Enc'}(pk,m^*)$ and $G_4$ if $c^*=\mathcal {S}(pk)$. Therefore, we have

and $\mathsf {Time}(\mathcal {B})\approx \mathsf {Time}(\mathcal {A})$.    $\square$

Claim 9

We have

$$|\Pr [G_4\Rightarrow 1]-1/2|\le \mathsf {Disj_{PKE',\mathcal {S}}}.$$

Proof

Let $\mathsf {Bad'}$ denote the event that $c^*$ is in $\mathsf {Enc'}(pk,\mathcal {M})$ in $G_4$. Then we have

$$\Pr [\mathsf {Bad'}]=\mathsf {Disj_{PKE',\mathcal {S}}}.$$

When $\mathsf {Bad'}$ does not occur, i.e., $c^*\notin \mathsf {Enc'}(pk,\mathcal {M})$, $\mathcal {A}$ obtains no information about $k_0^*=\mathsf {H}_q(c^*)$. This is because queries to $\mathsf {H_1}$ only reveal $\mathsf {H}_q(c)$ for $c\in \mathsf {Enc'}(pk,\mathcal {M})$, and $\mathsf {Deca'}(c)$ returns $\perp$ if $c=c^*$. Therefore, we have

$$\Pr [G_4\Rightarrow 1|\overline{\mathsf {Bad'}}]=1/2.$$

Combining the above, we have

$$\begin{aligned}&|\Pr [G_4\Rightarrow 1]-1/2|\\&=|\Pr [\mathsf {Bad'}]\cdot (\Pr [G_4\Rightarrow 1|\mathsf {Bad'}]-1/2)+\Pr [\overline{\mathsf {Bad'}}]\cdot (\Pr [G_4\Rightarrow 1|\overline{\mathsf {Bad'}}]-1/2)|\\&\le \Pr [\mathsf {Bad'}]+|\Pr [G_4\Rightarrow 1|\overline{\mathsf {Bad'}}]-1/2|\\&=\mathsf {Disj_{PKE',\mathcal {S}}} \end{aligned}$$

as we wanted.    $\square$

Combining all claims above, we obtain the following inequality:

   $\square$

Lemma 5

( $\mathsf {IND}\text {-}\mathsf{qCCA}$ Security of $\mathsf {SXY}$ in the QROM, Case 2 [22, Theorem 4.1]). Let $\mathsf {PKE'}$ be a $\delta$-correct $\mathsf {dPKE}$ with message space $\mathcal {M}$ and ciphertext space $\mathcal {C}$. Let $\mathsf {H_1}:\mathcal {M\rightarrow K},\ \mathsf {H_2}:\{0,1\}^l\times \mathcal {C}\rightarrow \mathcal {K}$ be hash functions modeled as quantum random oracles. Suppose that $\mathsf {PKE'}$ is $\mathcal {D_M}$-disjoint-simulatable with a simulator $\mathcal {S}$. Then for any adversary $\mathcal {A}$ against the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of issuing $q_\mathsf {H_2}$ quantum queries to $\mathsf {H_2}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {DS}\text {-}\mathsf{IND}$ security of $\mathsf {PKE'}$ such that

and $\mathsf {Time}(\mathcal {B})\approx \mathsf {Time}(\mathcal {A})$.

Remark 4

Lemma 5 still holds with our modified definition of $\mathsf {DS}$. The only thing that needs to be changed is “$\Pr [\mathsf {Bad}]\le \mathsf {Disj_{PKE_1,\mathcal {S}}}$” in [22, Lemma 4.8], which should be replaced with “$\Pr [\mathsf {Bad}]=\mathsf {Disj_{PKE_1,\mathcal {S}}}$” as $(ek,dk)\leftarrow \mathsf {Gen_1}$ exactly in the proof.

Remark 5

$\mathsf {KEM}$ remains $\delta$-correct.

We also need the following lemma about the security of transformation $\mathsf {T}$. It is a version without the square-root advantage loss at the cost of stronger security requirement of the underlying $\mathsf {PKE}$.

Lemma 6

(Security of $\mathsf {T}$ in the QROM [5, Theorem 1]). Let $\mathsf {PKE_0}$ be a $\mathsf {rPKE}$ with messages space $\mathcal {M}$ and random space $\mathcal {R}$. Let $\mathsf {G}:\mathcal {M\rightarrow R}$ be a hash function modeled as a quantum random oracle. Then for any adversary $\mathcal {A}$ against the $\mathsf {OW}\text {-}\mathsf{CPA}$ security of issuing $q_\mathsf {G}$ quantum queries to $\mathsf {G}$ with depth $d_\mathsf {G}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {IND}\text {-}\mathsf{CPA}$ security of $\mathsf {PKE_0}$ such that

and $\mathsf {Time}(\mathcal {B})\approx \mathsf {Time}(\mathcal {A})$.

Finally, we can get the security results of the two $\mathsf {KEM}$s. For simplicity, we assume the number of parallel queries is $n_p$ for all oracle algorithms. And we use $\mathcal {A}^{\mathsf {P}}$ in the following proofs to denote the adversary against the scheme $\mathsf {P}$.

Combining Lemma 6 with Theorem 1 and Theorem 3, we obtain the following result for the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of from the $\mathsf {IND}\text {-}\mathsf{CPA}$ security of a $\delta$-correct $\mathsf {rPKE}$ in the QROM.

Corollary 1

($\mathsf {IND}\text {-}\mathsf{qCCA}$ Security of $\mathsf {SXY\circ KC\circ T}$ in the QROM). Let $\mathsf {PKE_0}$ be a $\delta$-correct $\mathsf {rPKE}$ with message space $\mathcal {M}$, ciphertext space $\mathcal {C}$ and randomness space $\mathcal {R}$. Let $\mathsf {G}:\mathcal {M\rightarrow R},\ \mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n,\ \mathsf {H_1}:\mathcal {M\rightarrow K},\ \mathsf {H_2}:\{0,1\}^l\times \mathcal {C}\times \{0,1\}^n\rightarrow \mathcal {K}$ be hash functions modeled as quantum random oracles. Then for any adversary $\mathcal {A}$ against the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of $\mathsf {H_1,H_2]}$ issuing $q_\mathsf {G},\ q_\mathsf {H},\ q_\mathsf {H_1}$ and $q_\mathsf {H_2}$ quantum queries to $\mathsf {G},\ \mathsf {H},\ \mathsf {H_1}$ and $\mathsf {H_2}$ with depth $d_\mathsf {G},\ d_\mathsf {H},\ d_\mathsf {H_1}$ and $d_\mathsf {H_2}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {IND}\text {-}\mathsf{CPA}$ security of $\mathsf {PKE_0}$ such that

and $\mathsf {Time}(\mathcal {B})\approx 2\cdot \mathsf {Time}(\mathcal {A})$, where and .

Proof

From the construction of $\mathcal {A}^{\mathsf {PKE'}}$ in the proof of Theorem 3, we can know that $\mathcal {A}^{\mathsf {PKE'}}$ issues $q_\mathsf {G}+q_\mathsf {H_1},\ q_\mathsf {H}+q_\mathsf {H_1}$ queries to $\mathsf {G,\ H}$ with depth $d_\mathsf {G}+d_\mathsf {H_1},\ d_\mathsf {H}+d_\mathsf {H_1}$. Furthermore, from the construction of $\mathcal {A}^{\mathsf {PKE}}$ in the proof of Theorem 1 and the construction of $\mathcal {D}$ in the proof of Lemma 3, we can know that $\mathcal {A}^{\mathsf {PKE}}$ issues at most $(q_\mathsf {G}+q_\mathsf {H_1})\times 2+(q_\mathsf {H}+q_\mathsf {H_1})\times 2+2n_p$ queries to $\mathsf {G}$ with depth $(d_\mathsf {G}+d_\mathsf {H_1})\times 2+(d_\mathsf {H}+d_\mathsf {H_1})\times 2+2$, where the first part comes from $\mathcal {D}$’s twice invocations to $\mathcal {A}^{\mathsf {PKE'}}$, the second part comes from $\mathcal {D}$’s queries to $\mathsf {H}$ and $\mathsf {H'}$, and the third part comes from $\mathcal {A}^{\mathsf {PKE}}$’s testing of the set T returned by $\mathcal {D}$.    $\square$

Combining Theorem 2 with Lemma 5, we obtain the following result for the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of from the $\mathsf {OW}\text {-}\mathsf{CPA}$ security of a $\delta$-correct $\mathsf {dPKE}$ in the QROM.

Corollary 2

($\mathsf {IND}\text {-}\mathsf{qCCA}$ Security of $\mathsf {SXY\circ KC}$ in the QROM). Let $\mathsf {PKE}$ be a $\delta$-correct $\mathsf {dPKE}$ with message space $\mathcal {M}$ and ciphertext space $\mathcal {C}$. Let $\mathsf {H}:\mathcal {M}\rightarrow \{0,1\}^n,\ \mathsf {H_1}:\mathcal {M\rightarrow K},\ \mathsf {H_2}:\{0,1\}^l\times \mathcal {C}\times \{0,1\}^n\rightarrow \mathcal {K}$ be hash functions modeled as quantum random oracles. Then for any adversary $\mathcal {A}$ against the $\mathsf {IND}\text {-}\mathsf{qCCA}$ security of issuing $q_\mathsf {H},\ q_\mathsf {H_1}$ and $q_\mathsf {H_2}$ quantum queries to $\mathsf {H},\ \mathsf {H_1}$ and $\mathsf {H_2}$ with depth $d_\mathsf {H},\ d_\mathsf {H_1}$ and $d_\mathsf {H_2}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {OW}\text {-}\mathsf{CPA}$ security of $\mathsf {PKE}$ such that

and $\mathsf {Time}(\mathcal {B})\approx 2\cdot \mathsf {Time}(\mathcal {A})$, where .

Proof

From the construction of $\mathcal {A}^{\mathsf {PKE'}}$ in the proof of Lemma 5, we can know that $\mathcal {A}^{\mathsf {PKE'}}$ issues $q_\mathsf {H}+q_\mathsf {H_1}$ queries to $\mathsf {H}$ with depth $d_\mathsf {H}+d_\mathsf {H_1}$.    $\square$