Receiver Selective Opening CCA Secure Public Key Encryption from Various Assumptions

Abstract

Receiver selective opening (RSO) attacks for public key encryption (PKE) capture a situation where one sender sends messages to multiple receivers, and an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers’ ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.

1 Introduction

1.1 Background and Motivation

In the context of security notions of public key encryption (PKE), there are a lot of formulations considering different attack scenarios, such as chosen plaintext attacks (CPA) and chosen ciphertext attacks (CCA), and different attacker goals, such as one-wayness, indistinguishability (IND), and non-malleability. However, Bellare, Hofheinz, and Yilek  [3] claimed that $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ or $\mathrm {IND}\mathrm {-}\mathrm {CCA}$ security  [7, 9], which are the most accepted security notions for PKE, can not provide adequate security in a multi-user scenario. Concretely, they showed that when some of users has been corrupted, there are situations where we cannot preserve the other users’ confidentiality of ciphertexts by using only $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ or $\mathrm {IND}\mathrm {-}\mathrm {CCA}$ secure PKE schemes. Then, they proposed selective opening (SO) security for PKE which can ensure that the uncorrupted users’ ciphertexts leak no information about their secrets.

Depending on different attack scenarios, SO security is divided into two settings: sender selective opening (SSO) security  [3, 4] and receiver selective opening (RSO) security  [2, 14]. In this paper, we focus on RSO security. In RSO security, we consider a situation where there are one sender and multiple receivers. An adversary can corrupt some receivers, which means he gets their secret keys and plaintexts. RSO security ensures the confidentiality of uncorrupted receivers’ ciphertexts. Here, if we also consider an active adversary who can execute CCA, we can also consider $\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ security for PKE.

From another point of view, there are two flavors of definitions for SO security: indistinguishability-based SO security and simulation-based SO security. As mentioned in some previous works  [2, 14], simulation-based SO security is more desirable than indistinguishability-based SO security, because the definition of indistinguishability-based SO security can support only a plaintext space which satisfies a notion called efficient resamplability  [3]. Roughly, efficient resamplability refers to when a part of plaintexts are fixed, the remaining plaintexts can be resampled efficiently. This requirement is somewhat artificial and limits real-world applications because a plaintext distribution in practice scenarios do not necessarily satisfy this requirement.

From the above arguments, simulation-based $\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ ($\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$) security is the most favorable notion among all of the RSO security. Recently, some works  [10,11,12] proposed constructions of $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE under standard computational assumptions, such as the decisional Diffie-Hellman (DDH) assumption and the decisional composite residuosity (DCR) assumption. One of the important research area for cryptography is making a cryptographic primitive under the various assumptions. More specifically, we have two main problems in this area: Can we construct a cryptographic primitive under a weaker computational assumption or a post-quantum computational assumption ? In particular, National Institute of Standards and Technology (NIST) launched the Post-Quantum Cryptography Standardization in 2016, and thus post-quantum cryptography has been attracting more attention. Hence, in this paper, we tackle the following question:

Is it possible to construct a SIM-RSO-CCA secure PKE scheme from weaker or post-quantum computational assumptions ?

1.2 Our Contribution

Based on the above motivation, we give affirmative answers to the question. More precisely, we show that $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE can be constructed under the computational Diffie-Hellman (CDH) assumption (weaker computational assumption) or the learning parity with noise (LPN) assumption (new post-quantum computational assumption). In the following, we explain the details of our contribution.

Hara et al.’s Approach and Its Limitation. Toward our goal, we focus on the Hara et al.’s work  [10, 11]. In  [10, 11], they introduced the receiver non-committing CCA ($\mathrm {RNC}\mathrm {-}\mathrm {CCA}$) security for receiver non-committing encryption (RNCE), which is a variant of PKE with a special non-committing property, then showed that $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE implies $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE. Moreover, they proposed a construction of $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE by using an $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure PKE scheme and a non-interactive zero-knowledge (NIZK) proof system satisfying one-time simulation soundness.¹ In a nutshell, their construction is obtained by combining the classical Naor-Yung paradigm  [21] and a trick for a non-committing property that the decryption key used in a decryption algorithm of their RNCE scheme is chosen at random from two decryption keys of an underlying $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure PKE scheme.

In order to obtain a $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE scheme under the CDH or LPN assumption through their generic construction, all of the components of their construction should be realized under the CDH or LPN assumption. Actually, we can construct an $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure PKE scheme based on the CDH assumption  [13] or the LPN assumption  [1, 25]. However, NIZK proof system has not been proposed under these assumptions so far, and thus we cannot obtain a CDH or LPN based $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE scheme through this generic construction.

Our Approach. In order to circumvent the above problem, we show that an NIZK proof system is not needed, but a designated-verifier NIZK (DV-NIZK) argument is sufficient for our goal. More specifically, we show that $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE can be obtained from $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure PKE and DV-NIZK argument satisfying one-time simulation soundness. Roughly, a DV-NIZK argument is a relaxation of an NIZK proof system to the designated-verifier model, in other words, the model which only a user who has a secret verification key can verify a proof correctly. Although it is known that $\mathrm {IND}\mathrm {-}\mathrm {CCA}$ secure PKE scheme can be constructed from these two primitives  [8], we have the following nebulous point for proving the $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security for RNCE.

In contrast to $\mathrm {IND}\mathrm {-}\mathrm {CCA}$ security for PKE, when showing $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security for RNCE, we have to consider a situation where an adversary can get a decryption key in a security game. For checking the validity of a ciphertext, we need to include a secret verification key of DV-NIZK argument into a decryption key of our RNCE scheme. Furthermore, as well as the original Naor-Yung paradigm  [21], we need to use zero-knowledge and (one-time simulation) soundness of a DV-NIZK argument in our security proof. However, in DV-NIZK setting, we cannot ensure soundness if a secret verification key is revealed to an adversary, while zero-knowledge still holds. Thus, it seems that our strategy does not make sense at first glance. However, by focusing on the details of a security proof, we have seen through that there is no problem. The main reason is that soundness is only used to prevent an adversary from making “unfavorable” decryption queries in a security proof, and thus soundness need to be held only while it makes decryption queries. Here, in RNC-CCA security, we consider decryption queries only before a decryption key (including a secret verification key) is revealed. Therefore, it is possible to prevent unfavorable decryption queries without a secret verification key, that is, soundness of DV-NIZK argument is sufficient for proving $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security of RNCE. See Sect. 4.2 for more details.

Construction of One-time Simulation Sound DV-NIZK. Recently, a lot of works  [6, 17, 18, 20, 23] showed that a DV-NIZK argument can be constructed under the CDH and LPN assumption. The notion of a one-time simulation sound DV-NIZK argument was considered in the Elkind et al.’s work  [8]. However, a concrete construction of one-time simulation sound DV-NIZK argument has not been proposed so far. Then, in order to complete our $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE scheme, we propose a construction of one-time simulation sound DV-NIZK argument by combining (ordinary) DV-NIZK argument, strong one-time signature, and commitment based on the Lindell’s approach  [19]. See Sect. 3 for more details. (Note that we can construct strong one-time signature and commitment based on the one-way function, which is obtained under the CDH or LPN assumption.)

By combining the above results, we can obtain a $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE scheme based on the CDH or LPN assumption.

1.3 Related Work

Jia et al.  [15] proposed the first construction of $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE using indistinguishability obfuscation. Moreover, Jia et al.  [16] proposed indistinguishability-based RSO-CCA (IND-RSO-CCA) secure PKE schemes based on standard computational assumptions. Concretely, they showed two generic constructions of $\mathrm {IND}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE. First, they gave a generic construction based on an $\mathrm {IND}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CPA}$ secure PKE scheme, an $\mathrm {IND}\mathrm {-}\mathrm {CCA}$ secure PKE scheme, an NIZK proof system, and a strong one-time signature scheme. Second, they gave a generic construction based on a universal hash proof system. Recently, Huang et al.  [12] showed that a $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE scheme can be constructed under the DDH or DCR assumption. Moreover, they showed that a $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure PKE scheme can be constructed from an identity-based encryption scheme satisfying $\mathrm {RSO}$ security for a master secret key in the ideal cipher model.

2 Preliminaries

In this section, we define notations and recall the definitions for some cryptographic primitives.

2.1 Notations

In this paper, $x \leftarrow X$ denotes sampling an element x from a finite set X uniformly at random. $y \leftarrow \mathcal {A}(x;r)$ denotes that a probabilistic algorithm $\mathcal {A}$ outputs y for an input x using a randomness r, and we simply denote $y \leftarrow \mathcal {A}(x)$ when we do not need to write an internal randomness explicitly. For strings x and y, $x \Vert y$ denotes the concatenation of x and y. Also, $x \mathrel {\mathop :}=y$ denotes that x is defined by y. $\lambda$ denotes a security parameter. A function $f(\lambda )$ is a negligible function in $\lambda$, if $f(\lambda )$ tends to 0 faster than $\frac{1}{\lambda ^c}$ for every constant $c>0$. $\mathsf{negl}(\lambda )$ denotes an unspecified negligible function. PPT stands for probabilistic polynomial time. If n is a natural number, [n] denotes a set of integers $\{1, \cdots , n \}$. Also, if a and b are integers such that $a \le b$, [a, b] denotes a set of integers $\{a, \cdots , b\}$. If $\mathbf {m}= (m_1, \cdots , m_n)$ is an n-dimensional vector, $\mathbf {m}_J$ denotes a subset $\{m_j\}_{j \in J}$ where $J \subseteq [n]$. If $\mathcal {O}$ is a function or an algorithm and $\mathcal {A}$ is an algorithm, $\mathcal {A}^{\mathcal {O}}$ denotes that $\mathcal {A}$ has an oracle access to $\mathcal {O}$.

2.2 Public Key Encryption

Here, we review the definition of public key encryption (PKE).

Definition 1 (Public key encryption)

A PKE scheme with a plaintext space $\mathcal {M}$ consists of a tuple of the following three PPT algorithms $\varPi = (\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec})$.

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

• $\mathbf {Enc}$: The encryption algorithm, given a public key ${ pk}$ and a plaintext $m \in \mathcal {M}$, outputs a ciphertext c.

• $\mathbf {Dec}$: The (deterministic) decryption algorithm, given a public key ${ pk}$, a secret key ${ sk}$, and a ciphertext c, outputs a plaintext $m \in \{ \bot \} \cup \mathcal {M}$.

As the correctness for $\varPi$, we require that $\mathbf {Dec}({ pk}, { sk}, \mathbf {Enc}({ pk}, m)) = m$ holds for all $\lambda \in \mathbb {N}$, $m \in \mathcal {M}$, and $({ pk}, { sk}) \leftarrow \mathbf {KG}(1^\lambda )$.

Then, we recall $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ security and $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ security for PKE.²

Definition 2 (IND-CPA security)

We say that $\varPi = (\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec})$ is $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure if for any PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$,

$$\begin{aligned} \mathsf{Adv}^{\mathsf {ind}\mathrm {-}\mathsf {cpa}}_{\varPi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=2 \cdot \Bigl | \Pr [b \leftarrow \{0,1\}; ({ pk}, { sk}) \leftarrow \mathbf {KG}(1^\lambda ); (m^{*}_0,m^{*}_1, \mathsf{st}_1) \leftarrow \mathcal {A}_1({ pk}); \\ c^{*} \leftarrow \mathbf {Enc}({ pk},m^{*}_b); b' \leftarrow \mathcal {A}_2(c^*,\mathsf{st}_1): b = b'] - \frac{1}{2} \Bigr | = \mathsf{negl}(\lambda ), \end{aligned}$$

Definition 3 (SIM-RSO-CCA security)

Let n be the number of users. For a PKE scheme $\varPi = (\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec})$, an adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2,\mathcal {A}_3)$, and a simulator $\mathcal {S}= (\mathcal {S}_1,\mathcal {S}_2, \mathcal {S}_3)$, we define the following pair of experiments.

In both of the experiments, we require that the distributions $\mathsf{Dist}$ output by $\mathcal {A}$ and $\mathcal {S}$ be efficiently samplable. In $\mathsf{Exp}^{\mathsf {rso}\mathrm {-}\mathsf {cca}\mathrm {-}\mathsf {real}}_{n, \varPi , \mathcal {A}}(\lambda )$, a decryption query (c, j) is answered by $\mathbf {Dec}({ pk}_j,{ sk}_{j},c)$. $\mathcal {A}_2$ and $\mathcal {A}_3$ are not allowed to make a decryption query $(c^*_j, j)$ for any $j \in [n]$. Furthermore, $\mathcal {A}_3$ is not allowed to make a decryption query (c, j) satisfying $j \in J$. (This is without losing generality, since $\mathcal {A}_3$ can decrypt any ciphertext using the given secret keys.)

We say that $\varPi$ is $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure if for any PPT adversary $\mathcal {A}$ and any positive integer $n = n(\lambda )$, there exists a PPT simulator $\mathcal {S}$ such that for any PPT distinguisher $\mathcal {D}$,

$$\begin{aligned} \mathsf{Adv}^{\mathsf {rso}\mathrm {-}\mathsf {cca}}_{n, \varPi , \mathcal {A}, \mathcal {S}, \mathcal {D}}(\lambda )&\mathrel {\mathop :}=|\Pr [\mathcal {D}(\mathsf{Exp}^{\mathsf {rso}\mathrm {-}\mathsf {cca}\mathrm {-}\mathsf {real}}_{n, \varPi , \mathcal {A}}(\lambda )) = 1] - \Pr [\mathcal {D}(\mathsf{Exp}^{\mathsf {rso}\mathrm {-}\mathsf {cca}\mathrm {-}\mathsf {sim}}_{n, \varPi , \mathcal {S}}(\lambda )) = 1]| \\&= \mathsf{negl}(\lambda ). \end{aligned}$$

2.3 Receiver Non-committing Encryption

Here, we review receiver non-committing encryption (RNCE)  [5]. Informally, RNCE is public key encryption (PKE) having the property that it can generate a fake ciphertext which can be later opened to any plaintext (by showing an appropriate secret key). In the following, we give a syntax of RNCE and $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security for it  [10].

Definition 4 (Receiver non-committing encryption)

An RNCE scheme $\varPi$ with a plaintext space $\mathcal {M}$ consists of the following seven PPT algorithms $(\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec}, \mathbf {FKG}, \mathbf {Fake}, \mathbf {Open}, \mathbf {FDec})$. $(\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec})$ are the same algorithms as those of a PKE scheme. $(\mathbf {FKG}, \mathbf {Fake}, \mathbf {Open}, \mathbf {FDec})$ are defined as follows.

• $\mathbf {FKG}$: The fake key generation algorithm, given a security parameter $1^\lambda$, outputs a public key ${ pk}$ and a trapdoor td.

• $\mathbf {Fake}$: The fake encryption algorithm, given a public key ${ pk}$ and a trapdoor td, outputs a fake ciphertext $\widetilde{c}$.

• $\mathbf {Open}$: The opening algorithm, given a public key ${ pk}$, a trapdoor td, a fake ciphertext $\widetilde{c}$, and a plaintext m, outputs a fake secret key $\widetilde{{ sk}}$.

• $\mathbf {FDec}$: The fake decryption algorithm, given a public key ${ pk}$, a trapdoor td, and a ciphertext c, outputs $m \in \{ \bot \} \cup \mathcal {M}$.

Definition 5 (RNC-CCA security)

For an RNCE scheme $\varPi = (\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec}, \mathbf {FKG}, \mathbf {Fake}, \mathbf {Open}, \mathbf {FDec})$ and an adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2,\mathcal {A}_3)$, we consider the following pair of experiments.

In $\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {real}}_{\varPi , \mathcal {A}}(\lambda )$, a decryption query c is answered by $\mathbf {Dec}({ pk}, { sk}, c)$. On the other hand, in $\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {sim}}_{\varPi , \mathcal {A}}(\lambda )$, a decryption query c is answered by $\mathbf {FDec}({ pk}, { td}, c)$. In both of the experiments, $\mathcal {A}_2$ is not allowed to make a decryption query $c = c^*$ and $\mathcal {A}_3$ is not allowed to make any decryption query. We say that $\varPi$ is $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure if for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {rnc}\mathrm {-}\mathsf {cca}}_{\varPi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=|\Pr [\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {real}}_{\varPi , \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {sim}}_{\varPi , \mathcal {A}}(\lambda ) = 1]| = \mathsf{negl}(\lambda )$ holds.

In the previous work  [10], the following theorem was shown.

Theorem 1

( [10]). If an RNCE scheme $\varPi = (\mathbf {KG}, \mathbf {Enc}, \mathbf {Dec}, \mathbf {FKG}, \mathbf {Fake},$ $\mathbf {Open}, \mathbf {FDec})$ is $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure, then a PKE scheme $\varPi _{\mathsf {rso}} \mathrel {\mathop :}=(\mathbf {KG}, \mathbf {Enc},$ $\mathbf {Dec})$ is $\mathrm {SIM}\mathrm {-}\mathrm {RSO}\mathrm {-}\mathrm {CCA}$ secure.

2.4 Signature

Here, we review the definition of a signature scheme.

Definition 6 (Signature)

A signature scheme $\varSigma$ with a message space $\mathcal {M}$ consists of the following three PPT algorithms.

• $\mathbf {SKG}$: The key generation algorithm, given a security parameter $1^\lambda$, outputs a verification key ${ vk}$ and a signing key ${ sigk}$.

• $\mathbf {Sign}$: The signing algorithm, given a signing key ${ sigk}$ and a message m, and outputs a signature $\sigma$.

• $\mathbf {SVer}$: The verification algorithm, given a verification key ${ vk}$, a message m, and a signature $\sigma$, outputs either 1 (meaning “accept”) or 0 (meaning “reject”).

As the correctness for $\varSigma$, we require that for all $\lambda \in \mathbb {N}$, $({ vk},{ sigk}) \leftarrow \mathbf {SKG}(1^\lambda )$, and messages $m \in \mathcal {M}$, it holds that $\mathbf {SVer}({ vk}, m, \mathbf {Sign}({ sigk},m)) = 1$.

Next, we define strong one-time unforgeability under chosen message attacks for a signature scheme.

Definition 7 (Strong one-time unforgeability)

We say that a signature scheme $\varSigma = (\mathbf {SKG}, \mathbf {Sign}, \mathbf {SVer})$ satisfies strong one-time unforgeability if for any PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$,

$$\begin{aligned}&\quad \mathsf{Adv}^{\mathsf {unf}}_{\varOmega , \mathcal {A}}(\lambda ) := \Pr [ ({ vk}, { sigk}) \leftarrow \mathbf {SKG}(1^\lambda ); (m, \mathsf{st}_1) \leftarrow \mathcal {A}_1({ vk}); \sigma \leftarrow \mathbf {Sign}({ sigk}, m); \\&(m', \sigma ') \leftarrow \mathcal {A}_2(\sigma , \mathsf{st}_1) : ((m', \sigma ') \ne (m, \sigma )) \wedge (\mathbf {SVer}({ vk}, m', \sigma ') = 1) ] = \mathsf{negl}(\lambda ) \end{aligned}$$

holds.

2.5 Commitment

Here, we review the definition of a commitment scheme.

Definition 8 (Commitment)

A Commitment scheme $\varOmega$ with a plaintext space $\mathcal {M}$ consists of the following two PPT algorithms.

• $\mathbf {CKG}$: The key generation algorithm, given a security parameter $1^\lambda$, outputs a public commitment key ${ ck}$.

• $\mathbf {Commit}$: The commit algorithm, given a public commitment key ${ ck}$ and a plaintext m, outputs a commitment c.

Next, we define the following two security properties for commitment: statistical binding and computationally hiding.

Definition 9 (Statistical binding)

Let $\varOmega = (\mathbf {CKG}, \mathbf {Commit})$ be a commitment scheme. We say that $\varOmega$ satisfies statistical binding if for any computationally unbounded adversary $\mathcal {A}$,

$$\begin{aligned}&\mathsf{Adv}^{\mathsf {bind}}_{\varOmega , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=\Pr [{ ck}\leftarrow \mathbf {CKG}(1^\lambda ); (m_0, m_1, r_0, r_1) \leftarrow \mathcal {A}({ ck}) : \\&\qquad \qquad \qquad \qquad \ \mathbf {Commit}({ ck}, m_0 ; r_0) = \mathbf {Commit}({ ck}, m_1 ; r_1)] = \mathsf{negl}(\lambda ) \end{aligned}$$

holds.

Definition 10 (Computational hiding)

We say that a commitment scheme $\varOmega = (\mathbf {CKG}, \mathbf {Commit})$ satisfies computationally hiding if for any PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$,

$$\begin{aligned}&\mathsf{Adv}^{\mathsf {hide}}_{\varOmega , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=\Bigl | \Pr [ b \leftarrow \{0,1\}; { ck}\leftarrow \mathbf {CKG}(1^\lambda ); (m_0, m_1, \mathsf{st}_1) \leftarrow \mathcal {A}_1({ ck}); \\&\qquad \qquad \qquad c \leftarrow \mathbf {Commit}({ ck}, m_b); b' \leftarrow \mathcal {A}_2(c, \mathsf{st}_1) : b = b' ] - \frac{1}{2} \Bigr | = \mathsf{negl}(\lambda ) \end{aligned}$$

holds.

2.6 Designated-Verifier Non-interactive Zero-Knowledge Arguments

Here, we review the definition of a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument  [6, 17, 18, 20, 23].

Definition 11 (DV-NIZK argument)

Let $\mathcal {R}$ be an efficiently computable binary relation and $\mathcal {L}\mathrel {\mathop :}=\{x \, | \, \exists w \,\, \mathrm{s.t.} \, (x, w) \in \mathcal {R}\}$. A DV-NIZK argument for $\mathcal {L}$ consists of a tuple of the following five PPT algorithms $\varPhi = (\mathbf {CRSGen}, \mathbf {Prove},\mathbf {Verify}, \mathbf {SimCRS}, \mathbf {SimPrv})$.

• $\mathbf {CRSGen}$: The common reference string (CRS) generation algorithm takes a security parameter $1^{\lambda }$ as input, and outputs a CRS ${ crs}$ and a secret verification key ${ vsk}$.

• $\mathbf {Prove}$: The proving algorithm takes a CRS ${ crs}$, a statement x, and a witness w as input, and outputs a proof $\pi$.

• $\mathbf {Verify}$: The (deterministic) verification algorithm takes a CRS ${ crs}$, a secret verification key ${ vsk}$, a statement x, and a proof $\pi$ as input, outputs a bit $v \in \{0,1\}$, which is either 1 (meaning “accept”) or 0 (meaning “reject”).

• $\mathbf {SimCRS}$: The simulator’s CRS generation algorithm takes a security parameter $1^{\lambda }$ as input, outputs a simulated CRS ${ crs}$, a simulated secret verification key ${ vsk}$, and a trapdoor key ${ tk}$.

• $\mathbf {SimPrv}$: The simulator’s proving algorithm takes a trapdoor key ${ tk}$ and a statement x as input, and outputs a simulated proof $\pi$.

We say that a DV-NIZK argument $\varPhi$ is correct if we have $\mathbf {Verify}({ crs}, { vsk}, x, \mathbf {Prove}({ crs}, x, w)) = 1$ for all $\lambda \in \mathbb {N}$, $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$, and valid statement / witness pairs $(x,w) \in \mathcal {R}$.

Next, we define (standard) soundness and one-time simulation soundness for a DV-NIZK argument. We adopt a definition of soundness which was considered in recent works  [6, 17, 18, 20, 23]. Moreover, we adopt a definition of one-time simulation soundness proposed in  [8]. We note that in both of security definitions, an adversary can make multiple verification queries.

Definition 12 (Soundness)

We say that a DV-NIZK argument $\varPhi = (\mathbf {CRSGen}, \mathbf {Prove}, \mathbf {Verify}, \mathbf {SimCRS}, \mathbf {SimPrv})$ satisfies soundness if for any PPT adversary $\mathcal {A}$,

$$\begin{aligned}&\mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=\Pr [({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda ); (x, \pi ) \leftarrow \mathcal {A}^{\mathcal {O}(\cdot , \cdot )}(crs) \\&\qquad \qquad \qquad \qquad \qquad \quad : (x \notin \mathcal {L}) \wedge (\mathbf {Verify}({ crs}, { vsk}, x, \pi ) = 1) ] = \mathsf{negl}(\lambda ) \end{aligned}$$

holds, where $\mathcal {O}(\cdot , \cdot )$ is a verification oracle which receives a query $(x, \pi )$ and returns $v \leftarrow \mathbf {Verify}({ vsk}, x, \pi )$.

Definition 13 (One-time simulation soundness)

We say that a DV-NIZK argument $\varPhi = (\mathbf {CRSGen}, \mathbf {Prove}, \mathbf {Verify}, \mathbf {SimCRS}, \mathbf {SimPrv})$ satisfies one-time simulation soundness if for any PPT adversary $\mathcal {A}=(\mathcal {A}_1,\mathcal {A}_2)$,

$$\begin{aligned}&\mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=\Pr [({ crs}, { tk}, { vsk}) \leftarrow \mathbf {SimCRS}(1^\lambda ); (x', st_1) \leftarrow \mathcal {A}^{\mathcal {O}(\cdot , \cdot )}_{1}({ crs}); \\&\qquad \qquad \qquad \pi ' \leftarrow \mathbf {SimPrv}({ tk}, x'); (x, \pi ) \leftarrow \mathcal {A}^{\mathcal {O}(\cdot , \cdot )}_{2}(\pi ', st_1) \\&\qquad \;\, : ((x, \pi ) \ne (x', \pi ')) \wedge (x \notin \mathcal {L}) \wedge (\mathbf {Verify}({ crs}, { vsk}, x, \pi ) = 1) ] = \mathsf{negl}(\lambda ) \end{aligned}$$

holds, where $\mathcal {O}(\cdot , \cdot )$ is a verification oracle which receives a query $(x, \pi )$ and returns $v \leftarrow \mathbf {Verify}({ vsk}, x, \pi )$.

Then, we give the definitions of zero-knowledge and witness indistinguishability for a DV-NIZK argument. We adopt a definition of zero-knowledge which was considered in  [8]. Our definition of witness indistinguishability is a natural extension from one of a (standard) NIZK proof system. It is easy to see that our witness indistinguishability is implied by zero-knowledge.

Definition 14 (Zero-knowledge)

For a DV-NIZK argument $\varPhi = (\mathbf {CRSGen}, \mathbf {Prove}, \mathbf {Verify},\mathbf {SimCRS}, \mathbf {SimPrv})$ and a PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$, we consider the following two experiments.

In both of the experiments, it is required that $x \in \mathcal {L}$ and w be a witness for $x \in \mathcal {L}$. We say that $\varPhi$ is zero-knowledge if for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=|\Pr [\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {real}}_{\varPhi , \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {sim}}_{\varPhi , \mathcal {A}}(\lambda ) = 1]| = \mathsf{negl}(\lambda )$ holds.

Definition 15 (Witness indistinguishability)

We say that a DV-NIZK argument $\varPhi = (\mathbf {CRSGen}, \mathbf {Prove}, \mathbf {Verify}, \mathbf {SimCRS}, \mathbf {SimPrv})$ satisfies witness indistinguishability if for any PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$,

where $(x, w_0), (x, w_1) \in \mathcal {R}$ holds.

3 Construction of One-Time Simulation Sound DV-NIZK

In this section, we provide a construction of one-time simulation sound DV-NIZK. First, in Sect. 3.1, we describe our construction. Then, in Sect. 3.2, we give a security proof for our construction.

3.1 Description

In this section, we formally describe our construction of one-time simulation sound DV-NIZK argument for an NP language $\mathcal {L'}$. Let $\varSigma =(\mathbf {SKG}, \mathbf {Sign}, \mathbf {SVer})$ be a signature scheme, $\varOmega =(\mathbf {CKG}, \mathbf {Commit})$ a commitment scheme, and $\varPi =(\mathbf {CRSGen},\mathbf {Prove}, \mathbf {Verify}, \mathbf {SimCRS},\mathbf {SimPrv})$ a (standard) DV-NIZK argument for $\mathcal {L}$, where

$$\mathcal {L} \mathrel {\mathop :}=\Bigl \{(x', { ck}, { vk}, c) \, | \,\exists \, (w',r) \, \mathrm{s.t.} \, ((x',w') \in \mathcal {R'}) \vee (c = \mathbf {Commit}({ ck},vk;r)) \Bigr \}.$$

Then, we construct our one-time simulation sound DV-NIZK argument $\varPhi ' = (\mathbf {CRSGen}', \mathbf {Prove}', \mathbf {Verify}', \mathbf {SimCRS}', \mathbf {SimPrv}')$ for $\mathcal {L'}$ as described in Fig.1.

3.2 Security Proof

In this section, we show that our scheme $\varPhi '$ satisfies one-time simulation soundness (Theorem 2) and zero-knowledge (Theorem 3).

Theorem 2

If $\varPhi$ satisfies (standard) soundness, $\varOmega$ satisfies statistical binding, and $\varSigma$ satisfies strong one-time unforgeability, then $\varPhi '$ satisfies one-time simulation soundness.

Proof of Theorem 2.  Let $\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)$ be a PPT adversary that attacks the one-time simulation soundness of $\varPhi '$. The detailed description of one-time simulation soundness for $\varPhi '$ is as follows.

Fig. 1.

Construction of one-time simulation sound DV-NIZK argument $\varPhi '$.

• 1. The challenger generates ${ ck}\leftarrow \mathbf {CKG}(1^\lambda )$, $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$, and $({ sigk}^*, { vk}^*) \leftarrow \mathbf {SKG}(1^\lambda )$. Then, it samples $r \leftarrow \mathcal {R}_{\varPi }$ and computes $c^*\leftarrow \mathbf {Commit}({ ck}, { vk}^*; r)$. Finally, it sets ${ crs}' \mathrel {\mathop :}=({ crs}, { ck}, c^*)$ and ${ tk}\mathrel {\mathop :}=({ vk}^*, { sigk}^*, r)$, and runs $\mathcal {A}_1({ crs}')$. When $\mathcal {A}_1$ makes a verification query $(\widetilde{x}, \widetilde{\pi })$, the challenger returns $v \leftarrow \mathbf {Verify}({ crs}, { vsk}, \widetilde{x}, \widetilde{\pi })$ to $\mathcal {A}_1$.

• 2. When $\mathcal {A}_1$ outputs $(\hat{x}', \mathsf{st}_1)$ and terminates, the challenger sets $\hat{x} \mathrel {\mathop :}=(\hat{x}', { ck}, { vk}^*, c^*)$ and $\hat{w} \mathrel {\mathop :}=(\bot , r)$, and computes $\hat{\pi } \leftarrow \mathbf {Prove}({ crs}, \hat{x}, \hat{w})$ and $\hat{\sigma } \leftarrow \mathbf {Sign}({ sigk}^*, (\hat{x}', \hat{\pi }))$. Then, it sets $\hat{\pi }' \mathrel {\mathop :}=({ vk}^*, \hat{\pi }, \hat{\sigma })$ and runs $\mathcal {A}_2(\hat{\pi }', \mathsf{st}_1)$. When $\mathcal {A}_2$ makes a verification query $(\widetilde{x}, \widetilde{\pi })$, the challenger returns $v \leftarrow \mathbf {Verify}({ crs}, { vsk}, \widetilde{x}, \widetilde{\pi })$ to $\mathcal {A}_2$.

• 3. $\mathcal {A}_2$ outputs a pair of a statement and a proof $(x', \pi ' = ({ vk}, \pi , \sigma ))$ and terminates.

Here, in the above experiment, we let $\mathbf {Win}$ be the event that $((x',\pi ') \ne (\hat{x}', \hat{\pi }')) \wedge (x' \notin \mathcal {L'}) \wedge (\mathbf {Verify}({ crs}', { vsk}, x', \pi ') = 1)$ holds. We have the inequality $\mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi ', \mathcal {A}}(\lambda ) = \Pr [\mathbf {Win}] = \Pr [\mathbf {Win}\wedge { vk}\ne { vk}^*] + \Pr [\mathbf {Win}\wedge { vk}= { vk}^*]$.

In the following, we show that there exist a PPT adversary $\mathcal {B}$ against the soundness of $\varPhi$ such that $\mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {B}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}\ne { vk}^*]$ (Lemma 1) and a PPT adversary $\mathcal {C}= (\mathcal {C}_1, \mathcal {C}_2)$ against the strong one-time unforgeability of $\varSigma$ such that $\mathsf{Adv}^{\mathsf {unf}}_{\varSigma , \mathcal {C}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}= { vk}^*]$ (Lemma 2).

Lemma 1

There exists a PPT adversary $\mathcal {B}$ such that $\mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {B}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}\ne { vk}^*]$.

Proof of Lemma 1.  We construct a PPT adversary $\mathcal {B}$ that attacks the soundness of $\varPhi$ so that $\mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {B}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}\ne { vk}^*]$, using the adversary $\mathcal {A}$ as follows.

• $\mathcal {B}({ crs})$ : First, $\mathcal {B}$ generates ${ ck}\leftarrow \mathbf {CKG}(1^{\lambda })$, $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$, and $({ sigk}^*, { vk}^*) \leftarrow \mathbf {SKG}(1^\lambda )$. Then, it samples $r \leftarrow \mathcal {R}_{\varPi }$ and computes $c^*\leftarrow \mathbf {Commit}({ ck}, { vk}^*; r)$. Next, it sets ${ crs}' \mathrel {\mathop :}=({ crs}, { ck}, c)$ and ${ tk}' \mathrel {\mathop :}=({ vk}^*, { sigk}^*, r)$, and runs $\mathcal {A}_1({ crs}')$. When $\mathcal {A}_1$ makes a verification query $(\widetilde{x}', (\widetilde{{ vk}}, \widetilde{\pi },\widetilde{\sigma }))$, $\mathcal {B}$ computes $s \leftarrow \mathbf {SVer}(\widetilde{{ vk}}, (\widetilde{x}',\widetilde{\pi }),\widetilde{\sigma })$, makes a verification query $((\widetilde{x}', { ck}, \widetilde{{ vk}}, c), \widetilde{\pi })$, and gets the result v. If $s = v = 1$ holds, $\mathcal {B}$ returns 1 to $\mathcal {A}_1$. Otherwise, $\mathcal {B}$ returns 0 to $\mathcal {A}_1$.

  When $\mathcal {A}_1$ outputs a pair of a statement and state information $(\hat{x}', \mathsf{st}_1)$ and terminates, $\mathcal {B}$ sets $\hat{x} \mathrel {\mathop :}=(\hat{x}', { vk}, c)$ and $\hat{w} \mathrel {\mathop :}=(\bot , r)$. Next, $\mathcal {B}$ computes $\hat{\pi } \leftarrow \mathbf {Prove}({ crs}, \hat{x}, \hat{w})$ and $\hat{\sigma } \leftarrow \mathbf {Sign}({ sigk}^*, (\hat{\pi }, \hat{x}'))$. Then, $\mathcal {B}$ sets $\hat{\pi }' \mathrel {\mathop :}=({ vk}, \hat{\pi }, \hat{\sigma })$ and runs $\mathcal {A}_2(\hat{\pi }', \mathsf{st}_1)$. When $\mathcal {A}_2$ makes a verification query $((\widetilde{x}', { ck}, \widetilde{{ vk}}, c), \widetilde{\pi })$, $\mathcal {B}$ answers in the same way as above. When $\mathcal {A}_2$ outputs a pair of a statement and a proof $(x', ({ vk}, \pi , \sigma ))$ and terminates, $\mathcal {B}$ sets $x \mathrel {\mathop :}={(x', { ck}, { vk}, c)}$, returns $(x, \pi )$ to its experiment, and terminates.

We can see that $\mathcal {B}$ perfectly simulates an experiment of one-time simulation soundness for $\mathcal {A}$. Here, we assume that ${ vk}\ne { vk}^*$ holds. Firstly, if the event $\mathbf {Win}$ occurs, $\mathbf {Verify}'({ crs}', { vsk}, x', \pi ') = 1$ holds, which means that $\mathbf {Verify}({ crs}, { vsk}, (x', { ck}, { vk}, c), \pi ) = 1$ holds.

Secondly, $x' \notin L'$ holds now. Moreover, due to the fact that ${ vk}\ne { vk}^*$ and the statistical binding of $\varOmega$ hold, we can see $\mathbf {Commit}({ ck}, { vk}; r) \ne c$. Hence, we have $x \notin L$.

From the above argument, if $\mathbf {Win}$ occurs and ${ vk}\ne { vk}^*$ holds, we can see that $\mathcal {B}$ can make a pair of a statement and a proof $(x, \pi )$ breaking the soundness of $\varPhi$. Thus, $\mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {B}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}\ne { vk}^*]$ holds.    $\square$ (Lemma 1)

Lemma 2

There exists a PPT adversary $\mathcal {C}= (\mathcal {C}_1, \mathcal {C}_2)$ such that $\mathsf{Adv}^{\mathsf {unf}}_{\varSigma , \mathcal {C}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}= { vk}^*]$.

Proof of Lemma 2.  We construct a PPT adversary $\mathcal {C}=(\mathcal {C}_1, \mathcal {C}_2)$ that attacks the strong one-time unforgeability of $\varSigma$ so that $\mathsf{Adv}^{\mathsf {unf}}_{\varSigma , \mathcal {C}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}= { vk}^*]$, using the adversary $\mathcal {A}$ as follows.

• $\mathcal {C}_1({ vk}^*)$: First, $\mathcal {C}_1$ generates ${ ck}\leftarrow \mathbf {CKG}(1^{\lambda })$ and $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^{\lambda })$. Next, $\mathcal {C}_1$ samples $r \leftarrow \mathcal {R}_{\varPi }$ and computes $c \leftarrow \mathbf {Commit}({ ck}, { vk}^*; r)$. Then, $\mathcal {C}_1$ sets ${ crs}' \mathrel {\mathop :}={({ crs}, { ck}, c)}$ and runs $\mathcal {A}_1({ crs}')$. When $\mathcal {A}_1$ makes a verification query of $(\widetilde{x}', \widetilde{\pi }')$, $\mathcal {C}_1$ returns $v \leftarrow \mathbf {Verify}'({ crs}', { vsk}, \widetilde{x}', \widetilde{\pi }')$ to $\mathcal {A}_1$.

  When $\mathcal {A}_1$ outputs a pair of a statement and state information $(\hat{x}', \mathsf{st}_1)$ and terminates, $\mathcal {C}_1$ sets $\hat{x} \mathrel {\mathop :}=(\hat{x}', { ck}, { vk}^*, c)$ and $\hat{w} \mathrel {\mathop :}=(\bot , r)$, and computes $\hat{\pi } \leftarrow \mathbf {Prove}({ crs}, \hat{x}, \hat{w})$. Then, $\mathcal {C}_1$ sets $\hat{m} \mathrel {\mathop :}={(\hat{x}', \hat{\pi })}$ and $\mathsf{st}'_1$ as all the information known to $\mathcal {C}_1$, returns $(\hat{m}, \mathsf{st}_1)$ to its experiment, and terminates.

• $\mathcal {C}_2(\hat{\sigma }, \mathsf{st}_1)$: First, $\mathcal {C}_2$ sets $\hat{\pi }'\mathrel {\mathop :}={({ vk}^*,\hat{\sigma }, \hat{\pi })}$ and runs $\mathcal {A}_2(\hat{\pi }', \mathsf{st}_1)$. When $\mathcal {A}_2$ outputs a pair of a challenge statement and a proof $(x', ({ vk}, \pi , \sigma ))$, and terminates, $\mathcal {C}_2$ sets $m'\mathrel {\mathop :}={(x', \pi )}$, returns $(\sigma , m')$ to its experiment, and terminates.

We can see that $\mathcal {C}$ perfectly simulates an experiment of one-time simulation soundness for $\mathcal {A}$. Here, we assume that ${ vk}= { vk}^*$ holds. If the event $\mathbf {Win}$ occurs, $\mathbf {Verify}({ crs}', { vsk}, x', \pi ') = 1$ holds, which means that $\mathbf {SVer}({ vk}^*, m', \sigma ) = 1$ holds. Moreover, $(x', \pi ') \ne (\hat{x}', \hat{\pi }')$ holds now, which implies $(m', \sigma ) \ne (\hat{m}, \hat{\sigma })$. From the above argument, if $\mathbf {Win}$ occurs and ${ vk}= { vk}^*$ holds, we can see that $\mathcal {C}$ can make a pair of a statement and a proof $(x', \pi )$ breaking the strong one-time unforgeability of $\varSigma$. Thus, $\mathsf{Adv}^{\mathsf {unf}}_{\varSigma , \mathcal {C}}(\lambda ) = \Pr [\mathbf {Win}\wedge { vk}= { vk}^*]$ holds.    $\square$ (Lemma 2)

Putting everything together, we obtain $\mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi ', \mathcal {A}}(\lambda ) \le \mathsf{Adv}^{\mathsf {sound}}_{\varPhi , \mathcal {B}}(\lambda ) + \mathsf{Adv}^{\mathsf {unf}}_{\varSigma , \mathcal {C}}(\lambda )$. Since $\varPhi$ satisfies (standard) soundness and $\varSigma$ satisfies strong one-time unforgeability, for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi ', \mathcal {A}}(\lambda ) = \mathsf{negl}(\lambda )$ holds. Therefore, $\varPhi '$ satisfies one-time simulation soundness.    $\square$ (Theorem 2)

Theorem 3

If $\varPhi$ satisfies witness indistinguishability and $\varOmega$ satisfies computationally hiding, then $\varPhi '$ satisfies zero-knowledge.

Proof of Theorem 3.  Let $\mathcal {A}=(\mathcal {A}_1,\mathcal {A}_2)$ be a PPT adversary that attacks the zero-knowledge of $\varPhi '$. We introduce the following experiments $\{\mathsf{Exp}_i\}^{2}_{i=0}$.

• $\mathsf{Exp}_0$: $\mathsf{Exp}_0$ is exactly the same as $\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {real}}_{\varPhi ', \mathcal {A}}(\lambda )$. The detailed description is as follows.

  • 1. $\mathsf{Exp}_0$ generates ${ ck}\leftarrow \mathbf {CKG}(1^\lambda )$ and $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$. Then, $\mathsf{Exp}_0$ samples $r \leftarrow \mathcal {R}_{\varOmega }$ and computes $c \leftarrow \mathbf {Commit}(0^{|{ vk}|}; r)$. Next, $\mathsf{Exp}_0$ sets ${ crs}' \mathrel {\mathop :}=({ crs}, { ck}, c)$ and runs $\mathcal {A}_1({ crs}', { vsk})$.

  • 2. When $\mathcal {A}_1$ outputs a tuple $(x', w', \mathsf{st}_1)$ and terminates, $\mathsf{Exp}_0$ generates $({ vk}, { sigk}) \leftarrow \mathbf {SKG}(1^\lambda )$ and sets $x \mathrel {\mathop :}=(x', { ck}, { vk}, c)$ and $w \mathrel {\mathop :}=(w', \bot )$. Then, $\mathsf{Exp}_0$ computes $\pi \leftarrow \mathbf {Prove}({ crs}, x, w)$ and $\sigma \leftarrow \mathbf {Sign}({ sigk}, (x', \pi ))$, and returns $\pi ' \mathrel {\mathop :}=({ vk}, \pi , \sigma )$ to $\mathcal {A}_2$.

  • 3. When $\mathcal {A}_2$ outputs a bit $b' \in \{0,1\}$ and terminates, $\mathsf{Exp}_0$ outputs $b'$.

• $\mathsf{Exp}_1:$ $\mathsf{Exp}_1$ is identical to $\mathsf{Exp}_0$ except that $\mathsf{Exp}_1$ generates another $({ sigk}^*, { vk}^*) \leftarrow \mathbf {SKG}(1^{\lambda })$ and computes $c \leftarrow \mathbf {Commit}({ vk}^*; r)$ instead of $c \leftarrow \mathbf {Commit}(0^{|{ vk}|}; r)$.

• $\mathsf{Exp}_2:$ $\mathsf{Exp}_2$ is identical to $\mathsf{Exp}_1$ except that $\mathsf{Exp}_2$ sets $w \mathrel {\mathop :}=(\bot , r)$ and uses this w to make a proof $\pi$. Note that $\mathsf{Exp}_2$ is exactly the same as $\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {sim}}_{\varPhi ', \mathcal {A}}(\lambda )$.

We let $p_i \mathrel {\mathop :}=\Pr [\mathsf{Exp}_i(\lambda ) = 1]$ for all $i \in [0, 2]$. Then, we have

$$\begin{aligned} \mathsf{Adv}^{\mathsf {zk}}_{\varPhi ', \mathcal {A}}(\lambda )&= |\Pr [\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {real}}_{\varPhi ', \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {zk}\mathrm {-}\mathsf {sim}}_{\varPhi ', \mathcal {A}}(\lambda ) = 1]| \\&= |p_0 - p_2| \le \sum ^{1}_{i = 0} |p_i - p_{i+1}|. \end{aligned}$$

It remains to show how each $|p_i - p_{i+1}|$ is upper-bounded. To this end, in the following, we show that there exist an adversary $\mathcal {D}= (\mathcal {D}_1, \mathcal {D}_2)$ against the computationally hiding of $\varOmega$ such that $|p_0 - p_1| = \mathsf{Adv}^{\mathsf {hide}}_{\varOmega , \mathcal {D}}(\lambda )$ (Lemma 3) and an adversary $\mathcal {E}= (\mathcal {E}_1, \mathcal {E}_2)$ against the witness indistinguishability of $\varPhi$ such that $|p_1 - p_2| = \mathsf{Adv}^{\mathsf {wi}}_{\varPhi , \mathcal {E}}(\lambda )$ (Lemma 4).

Lemma 3

There exists a PPT adversary $\mathcal {D}= (\mathcal {D}_1, \mathcal {D}_2)$ such that $|p_0 - p_1| = \mathsf{Adv}^{\mathsf {hide}}_{\varOmega , \mathcal {D}}(\lambda )$.

Proof of Lemma 3.  We construct a PPT adversary $\mathcal {D}= (\mathcal {D}_1, \mathcal {D}_2)$ that attacks the hiding property of $\varOmega$ so that $|p_0 - p_1| = \mathsf{Adv}^{\mathsf {hide}}_{\varOmega , \mathcal {D}}(\lambda )$, using the adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$ as follows.

• $\mathcal {D}_1({ ck})$: First, $\mathcal {D}_1$ generates $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^{\lambda })$ and $({ sigk}^*, { vk}^*) \leftarrow \mathbf {SKG}(1^{\lambda })$. Then, $\mathcal {D}_1$ sets $m_0 \mathrel {\mathop :}={0^{|{ vk}^*|}}$, $m_1 \mathrel {\mathop :}={vk^*}$, and $\mathsf{st}_1$ as all of the information known to $\mathcal {D}_1$, returns $(m_0, m_1, \mathsf{st}_1)$ to its experiment, and terminates.

• $\mathcal {D}_2(c)$: First, $\mathcal {D}_2$ sets ${ crs}' \mathrel {\mathop :}=({ crs}, c)$ and runs $\mathcal {A}_1({ crs}')$. When $\mathcal {A}_1$ outputs a tuple $(x', w', st'_1)$, $\mathcal {D}_2$ sets $x \mathrel {\mathop :}=(x', { ck}, { vk}^*, c)$ and $w \mathrel {\mathop :}=(w', \bot )$. Then, $\mathcal {D}_2$ computes $\pi \leftarrow \mathbf {Prove}({ crs}, x, w)$ and $\sigma \leftarrow \mathbf {Sign}({ sigk}^*, (x', \pi ))$, sets $\pi ' \mathrel {\mathop :}=({ vk}^*, \pi , \sigma )$, and runs $\mathcal {A}_2(\pi ', \mathsf{st}_1)$. When $\mathcal {A}_2$ outputs a bit $b' \in \{0,1\}$ and terminates, $\mathcal {D}_2$ returns $b'$ to its experiment and terminates.

We let b be the challenge bit for $\mathcal {D}$ in its experiment. When $b=0$, we can see that $\mathcal {D}$ perfectly simulates $\mathsf{Exp}_0$ for $\mathcal {A}$. This ensures that when $b=0$, the probability that $\mathcal {D}$ outputs 1 is exactly the same as the probability that $\mathcal {A}$ outputs $b' = 1$ in $\mathsf{Exp}_0$. On the other hand, when $b=1$, we can see that $\mathcal {D}$ perfectly simulates $\mathsf{Exp}_1$ for $\mathcal {A}$. This ensures that when $b = 1$, the probability that $\mathcal {D}$ outputs 1 holds is exactly the same as the probability that $\mathcal {A}$ outputs $b' = 1$ in $\mathsf{Exp}_1$. Therefore, we have $\mathsf{Adv}^{\mathsf {hide}}_{\varOmega ,\mathcal {D}}(\lambda ) = |\Pr [b' = 1 | b = 0] - \Pr [b' = 1 | b = 1]| = |p_0 - p_1|.$    $\square$ (Lemma 3)

Lemma 4

There exists a PPT adversary $\mathcal {E}= (\mathcal {E}_1, \mathcal {E}_2)$ such that $|p_1 - p_2| = \mathsf{Adv}^{\mathsf {wi}}_{\varPhi , \mathcal {E}}(\lambda )$.

Proof of Lemma 4.  We construct a PPT adversary $\mathcal {E}= (\mathcal {E}_1, \mathcal {E}_2)$ that attacks the witness indistinguishability of $\varPhi$ so that $|p_1 - p_2| = \mathsf{Adv}^{\mathsf {wi}}_{\varPhi , \mathcal {E}}(\lambda )$, using the adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$ as follows.

• $\mathcal {E}_1({ crs})$: First, $\mathcal {E}_1$ generates ${ ck}\leftarrow \mathbf {CKG}(1^\lambda )$ and $({ sigk}^*, { vk}^*) \leftarrow \mathbf {SKG}(1^{\lambda })$. Then, $\mathcal {E}_1$ samples $r \leftarrow \mathcal {R}_{\varOmega }$ and computes $c \leftarrow \mathbf {Commit}({ ck}, { vk}^*; r)$. Next, $\mathcal {E}_1$ sets ${ crs}' \mathrel {\mathop :}=({ crs}, c)$ and runs $\mathcal {A}_1({ crs}')$. When $\mathcal {A}_1$ outputs $(x', w', \mathsf{st}_1)$ and terminates, $\mathcal {E}_1$ sets $x \mathrel {\mathop :}=(x', { ck}, { vk}^*, c)$, $w_0 \mathrel {\mathop :}=(w', \bot )$, and $w_1 \mathrel {\mathop :}=(\bot , r)$. Then, $\mathcal {E}_1$ returns $(x, w_0, w_1)$ and $\mathsf{st}'_1$ including all of the information known to $\mathcal {E}_1$ to its experiment, and terminates.

• $\mathcal {E}_2(\pi , \mathsf{st}_1')$: First, $\mathcal {E}_2$ computes $\sigma \leftarrow \mathbf {Sign}({ sigk}, (x', \pi ))$. Then, $\mathcal {E}_2$ sets $\pi ' \mathrel {\mathop :}=(\pi , \sigma , { vk}^*)$ and runs $\mathcal {A}_2(\pi ', \mathsf{st}_1)$. When $\mathcal {A}_2$ outputs a bit $b' \in \{0,1\}$ and terminates, $\mathcal {E}_2$ returns $b'$ to its experiment and terminates.

Fig. 2.

Construction of $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE $\varPi '$.

We let b be the challenge bit for $\mathcal {E}$ in its experiment. When $b=0$, we can see that $\mathcal {E}$ perfectly simulates $\mathsf{Exp}_1$ for $\mathcal {A}$. This ensures that when $b = 0$, the probability that $\mathcal {E}$ outputs 1 holds is exactly the same as the probability that $\mathcal {A}$ outputs 1 in $\mathsf{Exp}_1$. On the other hand, when $b=1$, $\mathcal {E}$ perfectly simulates $\mathsf{Exp}_2$ for $\mathcal {A}$. This ensures that when $b = 0$, the probability that $\mathcal {E}$ outputs 1 is exactly the same as the probability that $\mathcal {A}$ outputs 1 in $\mathsf{Exp}_2$. Therefore, we have $\mathsf{Adv}^{\mathsf {wi}}_{\varPhi , \mathcal {E}}(\lambda ) = |\Pr [b' = 1 | b = 0] - \Pr [b' = 1 | b = 1]| = |p_1 - p_2|.$    $\square$ (Lemma 4)

Putting everything together, we obtain $\mathsf{Adv}^{\mathsf {zk}}_{\varPhi ', \mathcal {A}}(\lambda ) \le \mathsf{Adv}^{\mathsf {hide}}_{\varOmega , \mathcal {D}}(\lambda ) + \mathsf{Adv}^{\mathsf {wi}}_{\varPhi , \mathcal {E}}(\lambda )$. Since $\varOmega$ satisfies computationally hiding and $\varPhi$ satisfies witness indistinguishability, for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {zk}}_{\varPhi ', \mathcal {A}}(\lambda ) = \mathsf{negl}(\lambda )$ holds. Therefore, $\varPhi '$ satisfies zero-knowledge.    $\square$ (Theorem 3)

4 Construction of $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ Secure RNCE

In this section, we show that our generic construction of $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure RNCE with the plaintext space $\{0,1\}$. Firstly, in Sect. 4.1, we describe our generic construction. Then, in Sect. 4.2, we give a security proof for it.

4.1 Description

In this section, we formally describe our generic construction of RNC-CCA secure RNCE with the plaintext space $\{0,1\}$. Let $\varPi =(\mathbf {KG},\mathbf {Enc},\mathbf {Dec})$ be a PKE scheme with the plaintext space $\{0,1\}$ and $\mathcal {R}_{\pi }$ a randomness space for the encryption algorithm $\mathbf {Enc}$. Let $\varPhi =(\mathbf {CRSGen},\mathbf {Prove}, \mathbf {Verify}, \mathbf {SimCRS},\mathbf {SimPrv})$ be a DV-NIZK argument for

Then, we use them to construct our RNCE scheme $\varPi '=(\mathbf {KG}', \mathbf {Enc}', \mathbf {Dec}', \mathbf {FKG}', \mathbf {Fake}', \mathbf {Open}', \mathbf {FDec}')$ with the plaintext space $\{0,1\}$ as described in Fig. 2. We note that the correctness of our RNCE scheme holds due to the correctness of $\varPi$ and $\varPhi$.

How to expand the plaintext space of our generic construction. In the above, we only give the construction whose plaintext space is $\{0,1\}$. However, we can expand the plaintext space by using our single-bit construction in a parallel way except for the generation of a proof of a DV-NIZK argument. More concretely, if we encrypt an $\ell$-bit plaintext $m = m_1\Vert \cdots \Vert m_{\ell }$, the procedure is as follows.

Firstly, we generate a public key ${ pk}= (({ pk}^i_0, { pk}^i_1)_{i \in [\ell ]}, { crs})$ and a secret key ${ sk}= (\alpha _i, { sk}^i_{\alpha _i}, { vsk})_{i \in [\ell ]}$, where $\alpha _1, \cdots , \alpha _{\ell } \leftarrow \{0,1\}$, $({ pk}^i_v, { sk}^i_v) \leftarrow \mathbf {KG}(1^\lambda )$ for all $(i, v) \in [\ell ] \times \{0,1\}$, and ${ crs}$ (resp., ${ vsk}$) denotes a CRS (resp., a secret verification key) of a DV-NIZK argument. Next, we compute a ciphertext $c = ((c^i_{0})_{i\in [\ell ]}, (c^i_{1})_{i\in [\ell ]}, \pi )$, where $c^i_{v} \leftarrow \mathbf {Enc}({ pk}^i_{v}, m_i)$ for all $(i, v) \in [\ell ] \times \{0,1\}$ and $\pi$ is a proof proving that, for each $i \in [\ell ]$, the ciphertexts $c^i_{0}$ and $c^i_{1}$ encrypt the same plaintext $m_i \in \{0,1\}$. Similarly, for the other procedures, we execute one-bit version algorithms in a parallel way for all $i \in [\ell ]$ except for the procedure of a DV-NIZK argument. See the full version of the paper for the details.

4.2 Security Proof

In this section, we show the following theorem.

Theorem 4

If $\varPi$ is an $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure PKE scheme and $\varPhi$ satisfies one-time simulation soundness and zero-knowledge, then $\varPi '$ is $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ secure.

Proof of Theorem 4.  Let $\mathcal {A}=(\mathcal {A}_1,\mathcal {A}_2, \mathcal {A}_3)$ be a PPT adversary that attacks the $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security of $\varPi '$. We introduce the following experiments $\{\mathsf{Exp}_i\}^{5}_{i=0}$.

• $\mathsf{Exp}_0:$ $\mathsf{Exp}_0$ is exactly the same as $\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {real}}_{\varPi ', \mathcal {A}}(\lambda )$. The detailed description is as follows.

  • 1. First, $\mathsf{Exp}_0$ samples $\alpha \leftarrow \{0,1\}$ and computes $({ pk}_0, { sk}_0) \leftarrow \mathbf {KG}(1^\lambda )$, $({ pk}_1, { sk}_1) \leftarrow \mathbf {KG}(1^\lambda )$, and $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$. Next, $\mathsf{Exp}_0$ sets ${ pk}\mathrel {\mathop :}=({ pk}_0, { pk}_1, { crs})$ and ${ sk}\mathrel {\mathop :}=(\alpha , { sk}_{\alpha }, { vsk})$, and runs $\mathcal {A}_1({ pk})$. When $\mathcal {A}_1$ makes a decryption query $c = (c_0, c_1, \pi )$, $\mathsf{Exp}_0$ checks whether $\mathbf {Verify}({ crs}, { vsk}, ({ pk}_0,{ pk}_1, c_0, c_1),\pi ) = 1$ or not. If this condition holds, $\mathsf{Exp}_0$ computes $m \leftarrow \mathbf {Dec}({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$ and returns m to $\mathcal {A}_1$. Otherwise, $\mathsf{Exp}_0$ returns $\bot$ to $\mathcal {A}_1$.

  • 2. When $\mathcal {A}_1$ outputs $(m^*, \mathsf{st}_1)$ and terminates, $\mathsf{Exp}_0$ computes the challenge ciphertext $c^*$ as follows. First, $\mathsf{Exp}_0$ samples $(r^*_0, r^*_1) \leftarrow (\mathcal {R}_{\varPi })^2$ and computes $c^*_0 \leftarrow \mathbf {Enc}({ pk}_0, m^*; r^*_0)$, $c^*_1 \leftarrow \mathbf {Enc}({ pk}_1, m^*; r^*_1)$, and $\pi ^*\leftarrow \mathbf {Prove}({ crs}, ({ pk}_0, { pk}_1, c^*_0, c^*_1), (m^*, r^*_0, r^*_1))$. Next, $\mathsf{Exp}_0$ sets $c^*= (c^*_0, c^*_1, \pi ^*)$ and runs $\mathcal {A}_2(c^*, \mathsf{st}_1)$. When $\mathcal {A}_2$ makes a decryption query c, $\mathsf{Exp}_0$ answers in the same way as above.

  • 3. When $\mathcal {A}_2$ outputs state information $\mathsf{st}_2$ and terminates, $\mathsf{Exp}_0$ runs $\mathcal {A}_3({ sk}, \mathsf{st}_2)$.

  • 4. When $\mathcal {A}_3$ outputs a bit $b'$ and terminates, $\mathsf{Exp}_0$ outputs $b'$.

• $\mathsf{Exp}_1:$ $\mathsf{Exp}_1$ is identical to $\mathsf{Exp}_0$ except for the following change. When computing the challenge ciphertext $c^*$, the common reference string ${ crs}$ is generated by executing $({ crs}, { vsk}, { tk}) \leftarrow \mathbf {SimCRS}(1^\lambda )$ instead of $({ crs}, { vsk}) \leftarrow \mathbf {CRSGen}(1^\lambda )$. Moreover, $\mathsf{Exp}_1$ generates a simulated proof $\pi ^*\leftarrow \mathbf {SimPrv}({ tk}, ({ pk}_0, { pk}_1,c^*_0, c^*_1))$ instead of $\pi ^*\leftarrow \mathbf {Prove}({ crs}, ({ pk}_0, { pk}_1, c^*_0, c^*_1), (m^*, r^*_0, r^*_1))$.

• $\mathsf{Exp}_2:$ $\mathsf{Exp}_2$ is identical to $\mathsf{Exp}_1$ except that when computing the challenge ciphertext $c^*$, $\mathsf{Exp}_2$ computes $c^*_{1 \oplus \alpha } \leftarrow \mathbf {Enc}({ pk}_{1 \oplus \alpha }, 1 \oplus m^*; r^*_{1 \oplus \alpha })$ instead of $c^*_{1 \oplus \alpha } \leftarrow \mathbf {Enc}({ pk}_{1 \oplus \alpha }, m^*; r^*_{1 \oplus \alpha })$.

• $\mathsf{Exp}_3:$ $\mathsf{Exp}_3$ is identical to $\mathsf{Exp}_2$ except that when responding to a decryption query $c = (c_0, c_1, \pi )$, if $\mathbf {Verify}({ crs}, { vsk}, ({ pk}_0, { pk}_1, c_0, c_1),\pi ) = 1$, $\mathsf{Exp}_3$ answers $m \leftarrow \mathbf {Dec}({ pk}_{0}, { sk}_{0}, c_{0})$ instead of $m \leftarrow \mathbf {Dec}({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$. Note that the decryption procedure in $\mathsf{Exp}_3$ is exactly the same as $\mathbf {FDec}'({ pk}, { td}, c)$.

• $\mathsf{Exp}_4:$ $\mathsf{Exp}_4$ is identical to $\mathsf{Exp}_3$ except that $\alpha \oplus m^*$ is used instead of $\alpha$. That is, when computing the challenge ciphertext $c^*$, $\mathsf{Exp}_4$ computes $c^*_0$ and $c^*_1$ by $c^*_{\alpha \oplus m^*} \leftarrow \mathbf {Enc}({ pk}_{\alpha \oplus m^*}, m^*)$ and $c^*_{\alpha \oplus (1 \oplus m^*)} \leftarrow \mathbf {Enc}({ pk}_{\alpha \oplus (1 \oplus m^*)}, 1 \oplus m^*)$. Moreover, $\mathsf{Exp}_4$ gives the secret key ${ sk}= (\alpha \oplus m^*, { sk}_{\alpha \oplus m^*}, { vsk})$ to $\mathcal {A}_3$ instead of ${ sk}= (\alpha , { sk}_{\alpha })$.

• $\mathsf{Exp}_5:$ $\mathsf{Exp}_5$ is exactly the same as $\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {sim}}_{\varPi ', \mathcal {A}}(\lambda )$.

We let $p_i \mathrel {\mathop :}=\Pr [\mathsf{Exp}_i(\lambda ) = 1]$ for all $i \in [0, 5]$. Then, we have $\mathsf{Adv}^{\mathsf {rnc}\mathrm {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) = |\Pr [\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {real}}_{\varPi ', \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {rnc}\mathrm {-}\mathsf {sim}}_{\varPi ', \mathcal {A}}(\lambda ) = 1]| = |p_0 - p_5| \le \sum ^{4}_{i = 0} |p_i - p_{i+1}|.$ It remains to show how each $|p_i - p_{i+1}|$ is upper-bounded. To this end, we will show the following lemmata.

Lemma 5

There exists a PPT adversary $\mathcal {E}= (\mathcal {E}_1, \mathcal {E}_2)$ against the zero-knowledge of $\varPhi$ such that $|p_0 - p_1| = \mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {E}}(\lambda )$.

Lemma 6

There exists a PPT adversary $\mathcal {F}= (\mathcal {F}_1, \mathcal {F}_2)$ against the $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ security of $\varPi$ such that $|p_1 - p_2| = \mathsf{Adv}^{\mathsf {ind}\mathrm {-}\mathsf {cpa}}_{\varPi , \mathcal {F}}(\lambda )$.

Lemma 7

There exists a PPT adversary $\mathcal {G}= (\mathcal {G}_1, \mathcal {G}_2)$ against the one-time simulation soundness of $\varPhi$ such that $|p_2 - p_3| \le \mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$.

Lemma 8

$|p_3 - p_4| = 0$ holds.

Lemma 9

$|p_4 - p_5| = 0$ holds.

As mentioned in Sect. 1.2, compared to the previous work  [10], the most technically obscure part is Lemma 7 using the one-time simulation soundness of a DV-NIZK argument, and thus we show only it here due to the space limitation. We will show the rest lemmata formally in the full version of the paper.

Proof of Lemma 7.  For $i \in \{2, 3\}$, we let $\mathbf {Bad}_i$ be the event that $\mathcal {A}_2$ makes a decryption query $c = (c_0, c_1, \pi )$ satisfying $(\mathbf {Dec}({ pk}_0, { sk}_0,c_0) \ne \mathbf {Dec}({ pk}_1, { sk}_1, c_1)) \wedge (\mathbf {Verify}({ crs}, { vsk}, ({ pk}_0, { pk}_1, c_0, c_1), \pi ) = 1)$ in $\mathsf{Exp}_i$. (We call such a decryption query a bad decryption query.) $\mathsf{Exp}_2$ proceeds identically to $\mathsf{Exp}_3$ unless $\mathbf {Bad}_2$ happens. Therefore, the inequality $|p_2 - p_3| \le \Pr [\mathbf {Bad}_2] = \Pr [\mathbf {Bad}_3]$ holds. In the following, we show that one can construct a PPT adversary $\mathcal {G}= (\mathcal {G}_1, \mathcal {G}_2)$ that attacks the one-time simulation soundness of $\varPhi$ so that $\Pr [\mathbf {Bad}_2] = \mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$, using the adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2, \mathcal {A}_3)$.

• $\mathcal {G}_1({ crs})$ : First, $\mathcal {G}_1$ samples $\alpha \leftarrow \{0,1\}$ and computes $({ pk}_0, { sk}_0) \leftarrow \mathbf {KG}(1^\lambda )$ and $({ pk}_1, { sk}_1) \leftarrow \mathbf {KG}(1^\lambda )$. Next, $\mathcal {G}_1$ sets ${ pk}\mathrel {\mathop :}=({ pk}_0, { pk}_1,{ crs})$ and runs $\mathcal {A}_1({ pk})$.

  When $\mathcal {A}_1$ makes a decryption query $c = (c_0, c_1, \pi )$, $\mathcal {G}_1$ makes a verification query $(({ pk}_0, { pk}_1, c_0, c_1), \pi )$ to its experiment. Upon receiving a verification result $v \in \{0,1\}$, $\mathcal {G}_1$ checks whether $v = 1$ or not. If this is the case, then $\mathcal {G}_1$ computes $m \leftarrow \mathbf {Dec}({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$ and returns m to $\mathcal {A}_1$. Otherwise, $\mathcal {G}_1$ returns $\bot$ to $\mathcal {A}_1$.

  When $\mathcal {A}_1$ outputs the challenge plaintext $m^*$ and state information $\mathsf{st}_1$, and terminates, $\mathcal {G}_1$ computes $c^*_{\alpha } \leftarrow \mathbf {Enc}({ pk}_{\alpha }, m^*)$ and $c^*_{1 \oplus \alpha } \leftarrow \mathbf {Enc}({ pk}_{1 \oplus \alpha }, 1 \oplus m^*)$. Finally, $\mathcal {G}_1$ sets $\mathsf{st}'_1$ as all the information known to it, returns $(({ pk}_0, { pk}_1, c^*_0,c^*_1),\mathsf{st}'_1)$ to its experiment, and terminates.

• $\mathcal {G}_2(\pi ^*, \mathsf{st}'_1)$ : First, $\mathcal {G}_2$ sets $c^*\mathrel {\mathop :}=(c^*_0, c^*_1, \pi ^*)$ and runs $\mathcal {A}_2(c^*, \mathsf{st}_1)$. When $\mathcal {A}_2$ makes a decryption query c, $\mathcal {G}_2$ parses $c \mathrel {\mathop :}=(c_0, c_1, \pi )$. Then, $\mathcal {G}_2$ makes a verification query $((pk_0, pk_1, c_0, c_1), \pi )$ to its experiment. If the verification result is 0, then $\mathcal {G}_2$ returns $\bot$ to $\mathcal {A}_2$. If the verification result is 1, then $\mathcal {G}_2$ checks whether $\mathbf {Dec}({ pk}_0, { sk}_0, c_0) \ne \mathbf {Dec}({ pk}_1, { sk}_1, c_1)$ or not. If this is the case, $\mathcal {G}_2$ returns $(({ pk}_0, { pk}_1, c_0, c_1), \pi )$ to its experiment and terminates. Otherwise, $\mathcal {G}_2$ computes $m \leftarrow \mathbf {Dec}({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$ and returns m to $\mathcal {A}_2$. When $\mathcal {A}_2$ outputs state information $\mathsf{st}_2$ and terminates, $\mathcal {G}_2$ gives up and terminates.

From the above construction of $\mathcal {G}$, it is easy to see that $\mathcal {G}$ perfectly simulates the experiment $\mathsf{Exp}_2$ for $\mathcal {A}$. Here, the success condition of $\mathcal {G}$ is to output a pair of a statement and a proof $(x, \pi )$ satisfying $((x^*, \pi ^*) \ne (x, \pi )) \wedge (\mathbf {Verify}({ crs}, { vsk}, x, \pi ) = 1) \wedge (x \notin \mathcal {L}_{eq})$, where $x^*= ({ pk}_0, { pk}_1, c^*_0, c^*_1)$ and $x = ({ pk}_0, { pk}_1, c_0, c_1)$. If $\mathcal {A}_2$ makes a bad decryption query $c = (c_0, c_1, \pi )$, then $\mathbf {Dec}({ pk}_0, { sk}_0,c_0) \ne \mathbf {Dec}({ pk}_1, { sk}_1, c_1)$ and $\mathbf {Verify}({ crs}, { vsk}, x, \pi ) = 1$. Thus, we can see that $x \notin \mathcal {L}_{eq}$ holds now due to the correctness of $\varPi$.

Moreover, due to the condition of decryption queries by $\mathcal {A}_2$, we have $(c^*_0, c^*_1, \pi ^*) = c^*\ne c = (c_0, c_1, \pi )$. That is, we have $(x^*, \pi ^*) \ne (x, \pi )$. Thus, when $\mathcal {A}_2$ makes a bad decryption query c, $\mathcal {G}$ achieves its success condition by returning $(x, \pi )$ to its experiment. We note that $\mathcal {G}$ can detect that the event $\mathbf {Bad}_2$ occurs because $\mathcal {G}$ has both of the secret keys ${ sk}_0$ and ${ sk}_1$, and can make a verification query $(x, \pi )$ to its experiment. From the above arguments, the probability that $\mathcal {A}_2$ makes a bad decryption query is exactly the same as the probability that $\mathcal {G}$ breaks the one-time simulation soundness of $\varPhi$. Therefore, we have $\Pr [\mathbf {Bad}_2] = \mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$, which in turn implies $|p_2 - p_3| \le \mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$.    $\square$ (Lemma 7)

Putting everything together, we obtain $\mathsf{Adv}^{\mathsf {rnc}\mathrm {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) \le \mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {E}}(\lambda ) + \mathsf{Adv}^{\mathsf {ind}\mathrm {-}\mathsf {cpa}}_{\varPi , \mathcal {F}}(\lambda ) + \mathsf{Adv}^{\mathsf {ot}\mathrm {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$. Since $\varPi$ is $\mathrm {IND}\mathrm {-}\mathrm {CPA}$ secure and $\varPhi$ satisfies one-time simulation soundness and zero-knowledge, for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {rnc}\mathrm {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) = \mathsf{negl}(\lambda )$ holds. Therefore, $\varPi '$ satisfies $\mathrm {RNC}\mathrm {-}\mathrm {CCA}$ security.    $\square$ (Theorem 4)