On the Non-tightness of Measurement-Based Reductions for Key Encapsulation Mechanism in the Quantum Random Oracle Model

Abstract

Key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto (FO) transformation (TCC 2017) that turn a weakly-secure public-key encryption (PKE) into an IND-CCA-secure KEM, were widely used among the KEM submissions to the NIST Post-Quantum Cryptography Standardization Project. Under the standard CPA security assumptions, i.e., OW-CPA and IND-CPA, the security of these variants in the quantum random oracle model (QROM) has been proved by black-box reductions, e.g., Jiang et al. (CRYPTO 2018), and by non-black-box reductions (EUROCRYPT 2020). The non-black-box reductions (EUROCRYPT 2020) have a liner security loss, but can only apply to specific reversible adversaries with strict reversible implementation. On the contrary, the existing black-box reductions in the literature can apply to an arbitrary adversary with an arbitrary implementation, but suffer a quadratic security loss.

In this paper, for KEM variants of the FO transformation, we first show the tightness limits of the black-box reductions, and prove that a measurement-based reduction in the QROM from breaking the standard OW-CPA (or IND-CPA) security of the underlying PKE to breaking the IND-CCA security of the resulting KEM, will inevitably incur a quadratic loss of the security, where “measurement-based” means the reduction measures a hash query from the adversary and uses the measurement outcome to break the underlying security of PKE. In particular, most black-box reductions for these FO-like KEM variants are of this type, and our results suggest an explanation for the lack of progress in improving this reduction tightness in terms of the degree of security loss. Then, we further show that the quadratic loss is also unavoidable when one turns a search problem into a decision problem using the one-way to hiding technique in a black-box manner, which has been recognized as an essential technique to prove the security of cryptosystems involving quantum random oracles.

Appendices

A Cryptographic Primitives

Definition A.1

(One-way function (OWF)). We say a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a one way function if for any PPT adversary $\mathcal {A}$, the following advantage function is negligible in $\lambda$: $\mathtt{Adv}_{f}^{\textsc {OW}}(\mathcal {A}):= \Pr [x'=x^*: x^*\overset{\$}{\leftarrow } \{0,1\}^n;y^*\leftarrow f(x^*); x' \leftarrow \mathcal {A}(1^\lambda ,y^*)].$

Definition A.2

(Public-key encryption). A public-key encryption scheme $\mathrm {PKE}=(Gen, Enc, Dec)$ consists of a triple of polynomial time (in the security parameter $\lambda$) algorithms and a finite message space $\mathcal {M}$. (1) $Gen(1^\lambda )\rightarrow (pk,sk)$: the key generation algorithm, is a probabilistic algorithm which on input $1^{\lambda }$ outputs a public/secret key-pair (pk, sk). Usually, for brevity, we will omit the input of Gen. (2) $Enc(pk,m)\rightarrow c$: the encryption algorithm Enc, on input pk and a message $m \in \mathcal {M}$, outputs a ciphertext $c\leftarrow Enc(pk,m)$. If necessary, we make the used randomness of encryption explicit by writing $c:=Enc(pk,m;r)$, where $r \overset{\$}{\leftarrow } R$ (R is the randomness space). (3) $Dec(sk,c)\rightarrow m$: the decryption algorithm Dec, is a deterministic algorithm which on input sk and a ciphertext c outputs a message $m:=Dec({sk},c)$ or a rejection symbol $\perp \notin \mathcal {M}$.

A PKE is deterministic if Enc is deterministic. We denote $\mathrm {DPKE}$ to stand for a deterministic PKE.

Definition A.3

(Correctness). A public-key encryption scheme $\mathrm {PKE}$ is perfectly correct if for any $(pk,sk) \leftarrow Gen$ and $m\in \mathcal {M}$, we have that $\Pr [Dec(sk,c)= m| c \leftarrow Enc(pk,m) ]=1.$

Definition A.4

(OW-CPA-secure PKE). Let $\mathrm {PKE}=(Gen, Enc, Dec)$ be a public-key encryption scheme with message space $\mathcal {M}$. Define $\mathrm {OW-CPA}$ game of PKE as in Fig. 4. Define the $\mathrm {OW-CPA}$ advantage of an adversary $\mathcal {A}$ against PKE as $\mathtt{Adv}_{\textsc {PKE}}^{\textsc {OW-CPA}}(\mathcal {A}):= \Pr [\textsc {OW-CPA}_{\mathrm {PKE}}^{\mathcal {A}}=1].$

Fig. 4.

Game OW-CPA and game IND-CPA for PKE.

Fig. 5.

Game IND-CCA for KEM.

Definition A.5

(IND-CPA-secure PKE). Let $\mathrm {PKE}=(Gen, Enc, Dec)$ be a public-key encryption scheme with message space $\mathcal {M}$. Define $\mathrm {IND-CPA}$ game of PKE as in Fig. 4, where $m_0$ and $m_1$ have the same length. Define the advantage of an adversary $\mathcal {A}$ against the $\mathrm {IND-CPA}$ security of PKE as $\mathtt{Adv}_{\textsc {PKE}}^{\textsc {IND-CPA}}(\mathcal {A}):= |2\Pr [\textsc {IND-CPA}_{\mathrm {PKE}}^{\mathcal {A}}=1]-1|.$

Definition A.6

(Key encapsulation). A key encapsulation mechanism KEM consists of three algorithms Gen, Encaps and Decaps. (1) $Gen(1^\lambda )\rightarrow (pk,sk)$: the key generation algorithm Gen outputs a key pair (pk, sk). Usually, for brevity, we will omit the input of Gen. (2) $Encaps(pk) \rightarrow (K, c)$: the encapsulation algorithm Encaps, on input pk, outputs a tuple (K, c), where $K \in \mathcal {K}$ and c is said to be an encapsulation of the key K. (3) $Decaps(sk,c) \rightarrow K$: the deterministic decapsulation algorithm Decaps, on input sk and an encapsulation c, outputs either a key $K := Decaps(sk, c) \in \mathcal {K}$ or a rejection symbol $\perp \notin \mathcal {K}$.

Definition A.7

(IND-CCA-secure KEM). We define the $\mathrm {IND-CCA}$ game as in Fig. 5 and the $\mathrm {IND-CCA}$ advantage of an adversary $\mathcal {A}$ against $\mathrm {KEM}$ as $\mathtt{Adv}_{\textsc {KEM}}^{\textsc {IND-CCA}}(\mathcal {A}):= |2\Pr [\textsc {IND-CCA}_{\mathrm {KEM}}^{\mathcal {A}}=1]-1|.$

B An Alternative Measurement for the Adversary in Sect. 3

In this section, we show that an alternative measurement with operators $M_1=|\varPsi \rangle \langle \varPsi |$ and $M_0=I-M_1$ can also help the adversary in Sect. 3 to achieve advantage at least $\sqrt{p}(1-{1}/{|{\mathcal {K}}|})$, where $|\varPsi \rangle =\sin (x)|m^*\rangle |K_b\rangle +\cos (x)|m'\rangle |\varSigma \rangle$ and $x=\frac{1}{2}\arccos (-\frac{\sqrt{p}}{\sqrt{4-3p}})$ ($\sin (2x)\ge 0$).

Theorem B.1

(The advantage of $\mathcal {A}$ with an alternative measurement). If the underlying DPKE is perfectly correct, the IND-CCA advantage of $\mathcal {A}$ with the above alternative measurement is at least $\sqrt{p}(1-\frac{1}{|{\mathcal {K}}|}).$

Proof

According to the proof of Theorem 3.1, the $m^*$ that $\mathcal {A}$ gets is exactly the one chosen by the challenger.

Let $|\psi _{0}\rangle =\sqrt{p}|a\rangle +\sqrt{1-p}|c\rangle$, $|\psi _{1}\rangle =\sqrt{p}|b\rangle +\sqrt{1-p}|c\rangle$, $|\varPsi _{0}\rangle =\sin (x)|a\rangle +\cos (x)|c\rangle$ and $|\varPsi _{1}\rangle =\sin (x)|b\rangle +\cos (x)|c\rangle$, where $|a\rangle = |m^*\rangle |K_0\rangle$, $|b\rangle = |m^*\rangle |K_1\rangle$, and $|c\rangle = |m'\rangle |\varSigma \rangle$. Then, the probability $\Pr [\mathcal {A}\Rightarrow 1]$ is $|{\langle \psi _0|\varPsi _0\rangle }|^2$ if $b=0$, and $|{\langle \psi _0|\varPsi _1\rangle }|^2$ if $b=1$. Thus,

When $K_0=K_1$, $|\varPsi _0\rangle =|\varPsi _1\rangle$ and the advantage of $\mathcal {A}$ is 0. In the following, we consider the case $K_0 \ne K_1$. It’s easy to verify that when $K_0 \ne K_1$, $\langle a |b\rangle =\langle a |c\rangle =\langle b |c\rangle =0$ since $m^*\ne m'$. Thus, $|{\langle \psi _0|\varPsi _1\rangle }|^2=|{\langle \psi _1|\varPsi _0\rangle }|^2$. Therefore, the advantage of $\mathcal {A}$ will become

Simple calculations show that $|{|{\langle \psi _0|\varPsi _0\rangle }|^2-|{\langle \psi _1|\varPsi _0\rangle }|^2}|=\sqrt{p}(\frac{\sqrt{p}+\sqrt{4-3p}}{2} )$. It is easy to verify that ${\sqrt{p}+\sqrt{4-3p}}\ge 2$ for $0\le p \le 1$. Thus, we can have $|{|{\langle \psi _0|\varPsi _0\rangle }|^2-|{\langle \psi _1|\varPsi _0\rangle }|^2}|$ $\ge \sqrt{p}.$ Note that $K_0 \ne K_1$ with probability $1-\frac{1}{|{\mathcal {K}}|}$. Therefore, we have    $\square$

C Impossibility Results with Sequential Rewinding

In this section, we show Theorem 5.1 can be extended to cover measurement-based reductions with simple rewinding. Similarly, the generalized impossibility results in Secs. 5.1 and 6.2 can be also extended, we just omit them here.

As noted by Remark 5, simple rewinding considered here is a simple quantum counterpart of classical sequential rewinding [46]. In particular, quantum adversary $\mathcal {A}$ is not allowed to use intrinsic “quantum randomness” or have auxiliary quantum input. The reduction R can sequentially restart $\mathcal {A}$ with the same input and (classical) randomness used in the first invocation. Thus, $\mathcal {A}$ queries with a fixed quantum state in every invocation. Take the adversary in Sect. 3 as an example. When reduction $R^{\mathcal {A}}$ rewinds $\mathcal {A}$, $R^{\mathcal {A}}$ restarts $\mathcal {A}$ with the same input $(pk,c^*,K_b)$ and randomness $(r_1,r_2)$ from the beginning.

Next, we will bound the advantage of a measurement-based black-box reduction with simple rewinding, and extend Theorem 4.1 to the following theorem.

Theorem C.1

If the underlying DPKE is perfectly correct, for any measurement-based black-box reduction $R^{\mathcal {A}}$ that sequentially rewinds the adversary $\mathcal {A}$ at most r ($r\ge 1$) times, there exist two meta-reductions $MR_1^{R}$ and $MR_2^{R}$ against the OW-CPA security of the underlying DPKE such that

$$ \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}}) \le (r+1) \cdot p+\mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(MR_1^{R}) +(\frac{|{\mathcal {M}}|}{|{\mathcal {M}}|-1})^{r+1}\mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(MR_2^{R}),$$

and $\textsf {Time}(R)\approx \textsf {Time}(MR_1^{R}) \approx \textsf {Time}(MR_2^{R})$.

Proof

The proof of Theorem C.1 has the same skeleton as the one of Theorem 4.1. Let $(pk_1,c_1^*)$ be the challenge given to $R^{\mathcal {A}}$ against the OW-CPA security of underlying PKE, and $\mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}})=\Pr [R^{\mathcal {A}} \Rightarrow m_1^*]$, where $Enc(pk_1,m_1^*)=c_1^*$. Let $(pk,c^*,K_b)$ be the input to $\mathcal {A}$ provided by $R^{\mathcal {A}}$. We only consider the reduction that rewinds the adversary with the same input and randomness. Thus, $(pk,c^*,K_b)$ and $r_1, r_2$ are fixed in every rewinding of $\mathcal {A}$. If the event Exi (Ine, resp. ) happens in the first invocation of $\mathcal {A}$, then the event Exi (Ine, resp.) happens in the sequent rewinding with probability 1, where the events Exi and Ine are defined as in Sect. 4. Then, define $\overline{\textsc {Ine}}$ ($\overline{\textsc {Exi}}$, resp.) as the event that Ine ($\textsc {Exi}$, resp.) happens in every invocation of $\mathcal {A}$. Denote $\overline{\textsc {Good}}_i$ ($i \in \{1,\ldots ,r+1\}$) as the event that $\overline{\textsc {Exi}}$ happens, the measurement of $\mathcal {A}$’s query in the i-th invocation returns $m^*$ such that $Enc(pk,m^*)=c^*$, and all the measurement outputs of $\mathcal {A}$’s queries in the previous $i-1$ invocations are not $m^*$. Denote $\overline{\textsc {Bad}}$ as the event that $\overline{\textsc {Exi}}$ happens, and all the the measurement outputs of $\mathcal {A}$’s queries in the $r+1$ invocations are not $m^*$. Thus, we have

$$\begin{aligned} \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}}) =&\sum _{i \in [r+1] }\Pr [R^{\mathcal {A}} \Rightarrow m_1^*\wedge \overline{\textsc {Exi}}\wedge \overline{\textsc {Good}}_i ]\nonumber \\&+\Pr [R^{\mathcal {A}} \Rightarrow m_1^*\wedge \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}} ]+\Pr [R^{\mathcal {A}}\Rightarrow m_1^*\wedge \overline{\textsc {Ine}}] \end{aligned}$$

(3)

Note that for any $i \in \{1,\ldots ,r+1\}$, $\Pr [R^{\mathcal {A}} \Rightarrow m_1^*\wedge \overline{\textsc {Exi}}\wedge \overline{\textsc {Good}}_i ]$

$$\begin{aligned}= & {} \Pr [R^{\mathcal {A}} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Good}}_i ]\Pr [\overline{\textsc {Good}}_i \wedge \overline{\textsc {Exi}} ] \nonumber \\\le & {} \Pr [\overline{\textsc {Good}}_i \wedge \overline{\textsc {Exi}} ]= \Pr [\overline{\textsc {Good}}_i | \overline{\textsc {Exi}} ]\Pr [\overline{\textsc {Exi}}]\nonumber \\\le & {} \Pr [\overline{\textsc {Good}}_i |\overline{\textsc {Exi}} ]=(1-p)^{i-1}\cdot p \le p \end{aligned}$$

(4)

Thus, combing the Eqs. (3) and (4), we have $\mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}})$

$$\begin{aligned} \le (r+1)\cdot p +\Pr [R^{\mathcal {A}} \Rightarrow m_1^*\wedge \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}} ]+\Pr [R^{\mathcal {A}}\Rightarrow m_1^*\wedge \overline{\textsc {Ine}}] \nonumber \\ \le (r+1)\cdot p +\Pr [R^{\mathcal {A}} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}} ] \cdot \Pr [\overline{\textsc {Exi}}] +\Pr [R^{\mathcal {A}}\Rightarrow m_1^*\wedge \overline{\textsc {Ine}}] \end{aligned}$$

(5)

Note that when the event $\overline{\textsc {Ine}}$ happens, $\mathcal {A}$ just outputs 1 for every invocation, and can be replaced by a trivial adversary $\mathcal {A}_1$ that always returns 1 and does nothing else. Then, we can construct a meta reduction $MR_1^{R}$ against the OW-CPA security of DPKE that simulates $\mathcal {A}_1$, runs $R^{\mathcal {A}_1}$ and returns $R^{\mathcal {A}_1}$’s output. Obviously, $\textsf {Time}(R)\approx \textsf {Time}(MR_1^{R})$. As in Lemma 4.1, we can have

$$\begin{aligned} \Pr [R^{\mathcal {A}}\Rightarrow m_1^*\wedge \overline{\textsc {Ine}}] \le \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(MR_1^{R}). \end{aligned}$$

(6)

Meanwhile, if the event $\overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}}$ happens, $\mathcal {A}$ can be substituted with $\mathcal {A}_2$ that queries the random oracle H with $\psi '_{-1}=\sum _{m,k}\frac{1}{\sqrt{|{\mathcal {M}}|\cdot |{\mathcal {K}}|}}|m\rangle |k\rangle$, and outputs 1 with probability 1 in every invocation. Then, we can construct a meta reduction $MR_2^{R}$ against the OW-CPA security of DPKE that simulates $\mathcal {A}_2$, runs $R^{\mathcal {A}_2}$ and returns $R^{\mathcal {A}_2}$’s output. It is easy to see $\textsf {Time}(R)\approx \textsf {Time}(MR_2^{R})$.

We note that conditioned on $\overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}}$, both measurement outcomes of $\mathcal {A}$’s query and $\mathcal {A}_2$’s query obey the uniform distribution over $\{m' \in \mathcal {M}: m'\ne m^*\}$ in every invocation. Thus, $\Pr [ R^{\mathcal {A}} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}} ]=\Pr [ R^{\mathcal {A}_2} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}} ]$. Since $\Pr [\overline{\textsc {Bad}} | \overline{\textsc {Exi}}]=(1-\frac{1}{|{\mathcal {M}}|})^{r+1}$,

$$\begin{aligned} \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(MR_2^{R})= & {} \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}_2}) \ge \Pr [R^{\mathcal {A}_2} \Rightarrow m_1^*|\overline{ \textsc {Exi}}]\cdot \Pr [\overline{\textsc {Exi}}]\nonumber \\\ge & {} (1-\frac{1}{|{\mathcal {M}}|})^{r+1}\Pr [R^{\mathcal {A}_2} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}}]\cdot \Pr [\overline{\textsc {Exi}}]\nonumber \\= & {} (1-\frac{1}{|{\mathcal {M}}|})^{r+1}\Pr [R^{\mathcal {A}} \Rightarrow m_1^*| \overline{\textsc {Exi}}\wedge \overline{\textsc {Bad}}]\cdot \Pr [\overline{\textsc {Exi}}]. \end{aligned}$$

(7)

Combing the Eqs. (5), (6) and (7), we can get the desired bound in Theorem C.1.    $\square$

Assuming that no PPT adversary can break the OW-CPA security of the underlying DPKE with non-negligible probability, we have $\mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}} (MR_1^{R})\approx \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}} (MR_2^{R})\in \textsf {negl}({\lambda })$. In addition, $(\frac{|{\mathcal {M}}|}{|{\mathcal {M}}|-1})^{r+1}\le (1+\frac{1}{|{\mathcal {M}}|-1})^{|{\mathcal {M}}|-1} < \exp (1)$ (assuming $r\le |{\mathcal {M}}|-2$). Thus, Theorem C.1 essentially says $\epsilon _{ R } = \mathtt{Adv}_{\textsc {DPKE}}^{\textsc {OW-CPA}}(R^{\mathcal {A}}) \lessapprox (r+1) \cdot p$. According to Theorem 3.1, . Thus, for $r\ge 1$ (the reduction rewinds the adversary r times), we have $\epsilon _{ R } \lessapprox (r+1)\cdot {\epsilon _{\mathcal {A}} }^2$. Namely, although the rewinding considered in this paper might increase the advantage of R by $r \cdot {\epsilon _{\mathcal {A}} }^2$, the running time of R will be accordingly increased by $r\cdot \textsf {Time}(\mathcal {A})$. Therefore, the current quadratic loss is also unavoidable for any measurement-based black-box reduction with simple rewinding.