Simulation-Based Receiver Selective Opening CCA Secure PKE from Standard Computational Assumptions

Abstract

In the situation where there are one sender and multiple receivers, a receiver selective opening (RSO) attack for a public key encryption (PKE) scheme considers adversaries that can corrupt some of the receivers and get their secret keys and plaintexts. Security against RSO attacks for a PKE scheme ensures confidentiality of ciphertexts of uncorrupted receivers. Simulation-based RSO security against chosen ciphertext attacks (SIM-RSO-CCA) is the strongest security notion in all RSO attack scenarios. Jia, Lu, and Li (INDOCRYPT 2016) proposed the first SIM-RSO-CCA secure PKE scheme. However, their scheme used indistinguishability obfuscation, which is not known to be constructed from any standard computational assumption. In this paper, we propose two constructions of SIM-RSO-CCA secure PKE from standard computational assumptions. First, we propose a generic construction of SIM-RSO-CCA secure PKE using an IND-CPA secure PKE scheme and a non-interactive zero-knowledge proof system satisfying one-time simulation soundness. Second, we propose an efficient concrete construction of SIM-RSO-CCA secure PKE based on the decisional Diffie-Hellman assumption.

1 Introduction

1.1 Background and Motivation

In the context of public key encryption (PKE), the generally accepted security notions are $\mathrm{IND}\text {-}\mathrm{CPA}$ and $\mathrm{IND}\text {-}\mathrm{CCA}$ security [10, 12]. However, Bellare, Hofheinz, and Yilek [4] pointed out that $\mathrm{IND}\text {-}\mathrm{CPA}$ and $\mathrm{IND}\text {-}\mathrm{CCA}$ security might not be strong enough when considering Selective Opening (SO) attacks in a multi-user scenario. Intuitively, SO attacks consider the corruptions of some fraction of users and the extortions of their secret information. Motivated by the above problem, they firstly introduced SO security for PKE. Even if an adversary can mount SO attacks, SO security can guarantee confidentiality of ciphertexts of uncorrupted users. In practice, considering secret communication among many users, we should take account of information leakage from some users. Therefore, SO security is an important security notion for PKE in practice. To date, two settings have been considered for SO security: Sender Selective Opening (SSO) security [4, 5] and Receiver Selective Opening (RSO) security [3, 15]. The main focus in this paper is on RSO security. In the situation where one sender and multiple receivers exist, RSO security guarantees confidentiality of uncorrupted ciphertexts even if an adversary can corrupt some fraction of receivers and get their plaintexts and secret keys. SO security is defined in both the chosen plaintext attack (CPA) and the chosen ciphertext attack (CCA) settings. In order to take active adversaries into account, we should consider CCA security for many situations.

Furthermore, there are two types of definitions for SO security: indistinguishability-based SO security and simulation-based SO security. The definition of indistinguishability-based SO security usually has a restriction for a plaintext distribution that an adversary can choose. More specifically, the definition of indistinguishability-based SO security usually requires the plaintext distribution to satisfy a notion called efficient resamplability [4]. Intuitively, efficient resamplability requires a plaintext distribution to be such that even if some plaintexts are fixed, the other plaintexts can be efficiently sampled. This requirement is somewhat artificial and limits application scenarios since plaintext distributions appearing in practice do not necessarily satisfy this requirement.

On the other hand, simulation-based SO security does not have such a restriction on the plaintext distribution. This security requires that the output of any adversary that is given the public keys, ciphertexts, and plaintexts and secret information of corrupted users, can be simulated by a simulator which only takes the corrupted plaintexts as its input. The secret information corresponds to randomnesses (used in encryptions) of the senders in the SSO setting and secret keys of the receivers in the RSO setting, respectively. Compared to indistinguishability-based SO security, simulation-based SO security can guarantee security even if an adversary chooses an arbitrary plaintext distribution. Since there is no restriction on the plaintext distributions, we can say that simulation-based SO security is preferable to indistinguishability-based SO security considering the utilization of PKE. Also, the previous works [3, 15] showed that simulation-based SO security is stronger than indistinguishability-based SO security in the CPA setting. It seems that this implication also holds in the CCA setting.

From the above arguments, we aim to achieve simulation-based RSO security against chosen ciphertext attacks which we call SIM-RSO-CCA security for PKE. So far, the only construction of SIM-RSO-CCA secure PKE is of Jia, Lu, and Li [16], but their construction is based on a very strong cryptographic primitive, indistinguishability obfuscation (iO) [2, 11]. This primitive is not known to be constructed from standard computational assumptions. Hence, in this paper, we tackle the following question: Is it possible to construct a SIM-RSO-CCA secure PKE scheme from standard computational assumptions?

1.2 Our Contributions

Based on the above motivation, we give affirmative answers to the question. More specifically, our technical results consist of the following three parts.

$\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ Security Derived from $\mathrm{RNC}\text {-}\mathrm{CCA}$ Security. As our first technical result, we introduce a new security notion that we call $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for receiver non-committing encryption (RNCE) [6, Sect. 4], which is a variant of PKE with a special non-committing property. Then, we show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE. When considering $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security for PKE, we must take into account information of multiple users, a simulator, and an adversary. Thus, if we try to prove $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security directly from standard computational assumptions, security proofs could become very complex. The merit of considering RNCE with our new security notion is that the definition of $\mathrm{RNC}\text {-}\mathrm{CCA}$ security involves only a single user, a single adversary, and no simulator. Hence, we can potentially avoid a complex security proof when proving $\mathrm{RNC}\text {-}\mathrm{CCA}$ security from standard computational assumptions. We believe that this result gives us a guideline for constructing a new $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE scheme, and in fact, our proposed $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE schemes are obtained via this result, as explained below.

A Generic Construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ Secure RNCE. As our second technical result, we show a generic construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE using an $\mathrm{IND}\text {-}\mathrm{CPA}$ secure PKE scheme and a non-interactive zero-knowledge (NIZK) proof system satisfying one-time simulation soundness. (In the following, we call this primitive an $\text {OTSS-NIZK}$ for simplicity.) This primitive is slightly stronger than a normal NIZK proof system. However, the constructions of this primitive based on various standard assumptions are known [13, 14, 19]. Therefore, our second technical result shows that we can construct $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE schemes from various standard assumptions through our generic construction.

An Efficient Concrete Construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ Secure RNCE. Although our generic construction of RNC-CCA secure RNCE can be instantiated based on standard computational assumptions, we require an NIZK proof system as a building block. In general, NIZK proof systems are not very efficient, and thus the above construction does not necessarily lead to an efficient construction. Thus, as our third technical result, we show an efficient concrete construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE based on the decisional Diffie-Hellman (DDH) assumption. This scheme is a variant of the Cramer-Shoup encryption scheme [7], and thus we do not need general NIZK proof systems. (We note that this efficient concrete construction supports only a polynomial-sized plaintext space.)

In summary, combining our first and second technical results, we obtain the first generic construction of $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE from an $\mathrm{IND}\text {-}\mathrm{CPA}$ secure PKE scheme and an $\text {OTSS-NIZK}$. This result enables us to construct $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE from various standard computational assumptions. Moreover, combining our first and third technical results, we obtain the first efficient concrete construction of SIM-RSO-CCA secure PKE (with a polynomial-sized plaintext space) from the DDH assumption.

1.3 Technical Overview

As mentioned earlier, Jia et al. [16] proposed the first $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE scheme using iO. They pointed out that there exist common features between an $\mathrm{IND}\text {-}\mathrm{CCA}$ security proof and a $\mathrm{SIM}\text {-}\mathrm{RSO}$ security proof. To date, there are three major techniques for constructing $\mathrm{IND}\text {-}\mathrm{CCA}$ secure PKE schemes: the double encryption technique [26], the hash proof system (HPS) technique [8], and the all-but-one (ABO) technique [24, 25]. Sahai and Waters [27] pointed out that the “punctured programming” paradigm is compatible with iO when constructing various cryptographic primitives, and they in particular constructed an $\mathrm{IND}\text {-}\mathrm{CCA}$ secure PKE scheme based on iO. Jia et al.’s SIM-RSO-CCA secure PKE scheme is obtained from the Sahai-Waters PKE scheme. Since the ABO technique has some similarity to the punctured programming paradigm, in retrospect, Jia et al.’s PKE scheme can be viewed as constructed via the ABO technique.

In contrast to their approach, we take two different paths of constructing $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE schemes, that is, the double encryption technique and the HPS technique. Somewhat surprisingly, our $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE schemes only require underlying cryptographic primitives that were required to construct $\mathrm{IND}\text {-}\mathrm{CCA}$ secure PKE schemes. In particular, our constructions do not need any other strong cryptographic primitives, such as iO, for achieving $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security.

In order to take the above approach, we adopt another strategy proposed by Hazay, Patra, and Warinschi [15], who pointed out that RNCE [6, Sect. 4] is an appropriate cryptographic primitive for achieving $\mathrm{RSO}$ security. Concretely, they showed that CPA secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CPA}$ secure PKE. Inspired by their idea, we formalize a new security notion for RNCE which we call $\mathrm{RNC}\text {-}\mathrm{CCA}$ security, and show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE. Then, we propose a generic construction and an efficient concrete construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE based on the double encryption technique and the HPS technique, respectively.

The Features of RNCE. Here, we explain the features of RNCE. Informally, RNCE is special PKE having the following two algorithms, $\mathsf {Fake}$ and $\mathsf {Open}$.¹ $\mathsf {Fake}$ is the fake encryption algorithm that takes a public key and a trapdoor information (generated at the key generation) as input, and outputs a fake ciphertext which has no information about a plaintext. $\mathsf {Open}$ is the opening algorithm that takes a public key, a trapdoor information, the fake ciphertext, and a certain plaintext m as input, and outputs a fake secret key which decrypts the fake ciphertext to the plaintext m.

RNCE requires the following two security properties. The first one is that an adversary cannot distinguish a real ciphertext generated by the ordinary encryption algorithm and a fake ciphertext generated by $\mathsf {Fake}$. The second one is that an adversary cannot distinguish a real secret key generated by the ordinary key generation algorithm and a fake secret key generated by $\mathsf {Open}$. Canetti, Halevi, and Katz [6, Sect. 4.1] firstly introduced RNCE and a security notion for it considering only non-adaptive chosen ciphertext attacks (CCA1). We extend their security notion to $\mathrm{RNC}\text {-}\mathrm{CCA}$ security considering adaptive chosen ciphertext attacks.

Sufficient Condition for $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ Secure PKE. We briefly review the security definition of RNCE. Informally, if only considering CPA, the security of RNCE is defined using an experiment that proceeds as follows.

• 1. An adversary is given a public key and chooses an arbitrary plaintext from the plaintext space.

• 2. The adversary is given either a real ciphertext or a fake ciphertext depending on the challenge bit chosen uniformly at random.

• 3. The adversary is given either a real secret key or a fake secret key depending on the above challenge bit.

• 4. The adversary guesses whether the given ciphertext and secret key are real or fake.

When defining $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for RNCE, it is natural to consider a definition in which an adversary is allowed to make a decryption query at any time in the above security experiment. If we define such a security experiment, an adversary can make a decryption query after he gets a secret key. Therefore, when we show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE, an adversary of $\mathrm{RNC}\text {-}\mathrm{CCA}$ security can perfectly simulate the decryption oracle for a $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ adversary.

However, there is one technical problem if we adopt the above definition. The problem is that we cannot obtain an efficient concrete construction of RNCE from the HPS technique. More specifically, it seems hard to construct an RNCE scheme based on the Cramer-Shoup encryption scheme [7]. The critical problem is that when proving the CCA security of the Cramer-Shoup encryption scheme, we use the fact that the entropy of the secret key is sufficiently large. In the security experiment of RNCE, an adversary gets the secret key used in the experiment, and thus the entropy of the secret key is completely lost and the security proof fails if we adopt the above definition.

In order to circumvent the above problem, we define the security experiment for $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of an RNCE scheme so that an adversary is not allowed to make decryption queries after he gets the secret key. Adopting this security definition, we do not have to simulate the decryption oracle for the adversary after he gets the secret key, and we can complete the security proof of our RNCE scheme. See Sect. 5 for the details.

Here, one might have the following question: Can we show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ security implies SIM-RSO-CCA security when adopting the above modified definition for $\mathrm{RNC}\text {-}\mathrm{CCA}$ security? We show an affirmative answer to this question. In a nutshell, we do not have to simulate the decryption queries which are relative to the secret keys of corrupted users in the definition of $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security, and thus we can still show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE. See Sect. 3 for the details.

How to Derive $\mathrm{RNC}\text {-}\mathrm{CCA}$ Secure RNCE from the Double Encryption Technique. Here, we give an overview of our generic construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE derived from the classical double encryption technique [23, 26]. One can see that our generic construction is an extension of a CPA secure RNCE scheme observed by Canetti et al. [6, Sect. 4.1]. Their RNCE scheme is inspired by the double encryption technique without considering CCA security. The trick for the non-committing property of their construction is that the secret key used in the decryption algorithm is chosen at random from the two underlying secret keys, and thus their scheme is very simple. In order to upgrade the CPA security of this RNCE scheme to CCA security, we focus on the work by Lindell [19] who constructed an $\mathrm{IND}\text {-}\mathrm{CCA}$ secure PKE scheme based on an $\mathrm{IND}\text {-}\mathrm{CPA}$ secure PKE scheme and an $\text {OTSS-NIZK}$ using the double encryption technique. Applying a similar method to the above RNCE scheme, we obtain our generic construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE. See Sect. 4 for the details.

We note that the technique for achieving the non-committing property, i.e., generating multiple secret keys and using only one of them for decryption, has been adopted in a number of works, e.g., in the construction of an adaptively and forward secure key-evolving encryption scheme [6, Sect. 3], and more recently in the construction of a tightly secure key encapsulation mechanism in the multi-user setting with corruption [1]. Furthermore, our construction shares an idea of binding two ciphertexts with an NIZK proof system with [6, Sect. 3] to resist against active behaviors of an adversary (e.g., decryption queries). However, one difference is that we require one-time simulation-soundness for the underlying NIZK proof system, while they require unbounded simulation-soundness.

How to Derive $\mathrm{RNC}\text {-}\mathrm{CCA}$ Secure RNCE from the HPS Technique. Here, we explain an overview of our concrete construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE derived from the HPS technique [7, 8]. Our concrete construction is an extension of the CCA1 secure RNCE scheme proposed by Canetti et al. [6, Sect. 4.2]. Their RNCE scheme is a variant of the Cramer-Shoup-“lite” encryption scheme [7], which is an IND-CCA1 secure PKE scheme based on the DDH assumption. The only difference is that they encode a plaintext m by the group element $g^m$, where g is a generator of the underlying group. This encoding is essential for the opening algorithm $\mathsf {Open}$ of their proposed scheme, and the plaintext space of their scheme is of polynomial-size since they have to compute the discrete logarithm of $g^m$ in the decryption procedure. We extend their scheme to a CCA secure RNCE scheme based on the “full”-Cramer-Shoup encryption scheme [7]. See Sect. 5 for the details.

1.4 Related Work

To date, SSO secure PKE schemes have been extensively studied, and several constructions of SIM-SSO-CCA secure PKE have been shown based on various standard computational assumptions [18, 20,21,22]. On the other hand, RSO secure PKE schemes have been much less studied.

As mentioned above, the only existing construction of $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE is the construction using iO proposed by Jia et al. [16]. Jia, Lu, and Li [17] proposed indistinguishability-based RSO-CCA ($\mathrm{IND}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$) secure PKE schemes based on standard computational assumptions. Concretely, they showed two generic constructions of $\mathrm{IND}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE schemes. First, they gave a generic construction based on an $\mathrm{IND}\text {-}\mathrm{RSO}\text {-}\mathrm{CPA}$ secure PKE scheme, an $\mathrm{IND}\text {-}\mathrm{CCA}$ secure PKE scheme, an NIZK proof system, and a strong one-time signature scheme. Second, they gave a generic construction based on universal HPS. It is not obvious whether their schemes (can be easily extended to) satisfy $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security.

1.5 Organization

The rest of the paper is organized as follows: In Sect. 2, we review the notations and definitions of cryptographic primitives. In Sect. 3, we introduce $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for RNCE and show its implication to $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security for PKE. In Sect. 4, we show a generic construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE with a binary plaintext space, which is constructed from an $\mathrm{IND}\text {-}\mathrm{CPA}$ secure PKE scheme and an $\text {OTSS-NIZK}$. In Sect. 5, we show a DDH-based concrete construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE.

2 Preliminaries

In this section, we define some notations and cryptographic primitives.

2.1 Notations

In this paper, $x \leftarrow X$ denotes sampling an element 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 need not write an internal randomness explicitly. For strings x and y, $x \Vert y$ denotes the concatenation of x and y, and $x \mathrel {\mathop :}=y$ denotes the substitution y for x. In other cases, $x \mathrel {\mathop :}=y$ denotes that x is defined as 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, a, b are integers such that $a \le b$, [n] denotes the set of integers $\{1, \cdots , n \}$ and [a, b] denotes the set of integers $\{a, \cdots , b\}$. If $\mathbf {m}= (m_1, \cdots , m_n)$ is an n-dimensional vector, $\mathbf {m}_J$ denotes the 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 oracle access to $\mathcal {O}$.

2.2 Public Key Encryption

A public key encryption (PKE) scheme with a plaintext space $\mathcal {M}$ consists of a tuple of three PPT algorithms $\varPi = (\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})$. $\mathsf {KG}$ is the key generation algorithm that, given a security parameter $1^\lambda$, outputs a public key ${ pk}$ and a secret key ${ sk}$. $\mathsf {Enc}$ is the encryption algorithm that, given a public key ${ pk}$ and a plaintext $m \in \mathcal {M}$, outputs a ciphertext c. $\mathsf {Dec}$ is the (deterministic) decryption algorithm that, 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 $\mathsf {Dec}({ pk}, { sk}, \mathsf {Enc}({ pk}, m)) = m$ holds for all $\lambda \in \mathbb {N}$, $m \in \mathcal {M}$, and $({ pk}, { sk}) \leftarrow \mathsf {KG}(1^\lambda )$.

Next, we define $\mathrm{IND}\text {-}\mathrm{CPA}$ and $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security for a PKE scheme.

Definition 1

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

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

where it is required that $|m^*_0| = |m^*_1|$.

Definition 2

(SIM-RSO-CCA security). Let n be the number of users. For a PKE scheme $\varPi = (\mathsf {KG},\mathsf {Enc}, \mathsf {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}\text {-}\mathsf {cca}\text {-}\mathsf {real}}_{n, \varPi , \mathcal {A}}(\lambda )$, a decryption query (c, j) is answered by $\mathsf {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 SIM-RSO-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}$,

Remark 1

For simplicity, we consider non-adaptive opening queries by an adversary in our experiments. That is, an adversary can make an opening query $J \subseteq [n]$ only at once. However, our constructions of $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE remain secure even if we consider adaptive opening queries by an adversary.

Remark 2

In this paper, as in the previous works [16, 17], we consider only the revelation of secret keys in the definition of $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security. Namely, we assume that an adversary cannot obtain a random coin used for generating a secret key. Hazay, Patra, and Warinschi [15] considered the revelation of both secret keys and random coins used in the key generation algorithm in the RSO-CPA security. If we take into account corruptions of both secret keys and random coins, it seems that we need key simulatability [9, 15] for building blocks.

2.3 Non-interactive Zero-Knowledge Proof System

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

$\mathsf {CRSGen}$::

The common reference string (CRS) generation algorithm, given a security parameter $1^\lambda$, outputs a CRS ${ crs}$.

$\mathsf {Prove}$::

The proving algorithm, given a CRS ${ crs}$, a statement $x \in \mathcal {L}$, and a witness w for the fact that $x \in \mathcal {L}$, outputs a proof $\pi$.

$\mathsf {Verify}$::

The verification algorithm, given a CRS ${ crs}$, a statement x, and a proof $\pi$, outputs either 1 (meaning “accept”) or 0 (meaning “reject”).

$\mathsf {SimCRS}$::

The simulator’s CRS generation algorithm, given a security parameter $1^\lambda$, outputs a simulated CRS ${ crs}$ and a trapdoor key ${ tk}$.

$\mathsf {SimPrv}$::

The simulator’s proving algorithm, given a trapdoor key ${ tk}$ and a (possibly false) statement x, outputs a simulated proof $\pi$.

  As the correctness for $\varPhi$, we require that $\mathsf {Verify}(crs,x,\mathsf {Prove}(crs,x,w)) = 1$ holds for all $\lambda \in \mathbb {N}$, all ${ crs}\leftarrow \mathsf {CRSGen}(1^\lambda )$, all statements $x \in \mathcal {L}$, and all witnesses w for the fact that $x \in \mathcal {L}$.

Next, we define the security notions for a non-interactive proof system: One-time simulation soundness (OT-SS) and zero-knowledge (ZK).

Definition 3

(One-time simulation soundness). We say that a non-interactive proof system $\varPhi = (\mathsf {CRSGen}, \mathsf {Prove}, \mathsf {Verify}, \mathsf {SimCRS},\mathsf {SimPrv})$ satisfies one-time simulation soundness (OT-SS) if for any PPT adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$,

$$\begin{aligned} \mathsf{Adv}^{\mathsf {ot}\text {-}\mathsf {ss}}_{\varPhi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=\Pr [({ crs}, { tk}) \leftarrow \mathsf {SimCRS}(1^\lambda ); (x^*, \mathsf{st}_1) \leftarrow \mathcal {A}_1({ crs});\\ \pi ^*\leftarrow \mathsf {SimPrv}({ tk}, x^*); (x, \pi ) \leftarrow \mathcal {A}_2(\pi ^*, \mathsf{st}_1) : \\ (x\notin \mathcal {L}) \wedge (\mathsf {Verify}({ crs}, x, \pi ) = 1) \wedge ((x, \pi ) \ne (x^*, \pi ^*))] = \mathsf{negl}(\lambda ). \end{aligned}$$

Definition 4

(Zero-knowledge). For a non-interactive proof system $\varPhi = (\mathsf {CRSGen}, \mathsf {Prove}, \mathsf {Verify}, \mathsf {SimCRS}, \mathsf {SimPrv})$ and an adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2)$, consider the following pair of experiments.

In both of the experiments, it is required that $x \in \mathcal {L}$ and w is a witness for $x \in \mathcal {L}$. We say that $\varPhi$ is zero-knowledge (ZK) if for any PPT adversary $\mathcal {A}$,

$$\begin{aligned} \mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {A}}(\lambda ) \mathrel {\mathop :}=|\Pr [\mathsf{Exp}^{\mathsf {zk}\text {-}\mathsf {real}}_{\varPhi , \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {zk}\text {-}\mathsf {sim}}_{\varPhi , \mathcal {A}}(\lambda ) = 1]| = \mathsf{negl}(\lambda ). \end{aligned}$$

In this paper, we call a non-interactive proof system satisfying both OT-SS and ZK property an OTSS-NIZK.

2.4 “+1”-Decisional Diffie-Hellman (DDH) Assumption

Here, we define the “+1”-DDH assumption. It is straightforward to see this assumption is implied by the standard DDH assumption. This assumption is used to simplify the security proof of our concrete construction in Sect. 5.

Definition 5

(“+1”-DDH assumption). Let p be a prime number such that $p = \varTheta (2^\lambda )$, $\mathbb {G}$ be a multiplicative cyclic group of order p, and $\mathbb {Z}_p$ be the set of integers modulo p. We say that the “$+1$”-DDH assumption holds in $\mathbb {G}$ if for any PPT adversary $\mathcal {A}$,

$$\begin{aligned} \mathsf{Adv}^{+1\text {-}\mathsf {ddh}}_{\mathbb {G}, \mathcal {A}}(\lambda )&\mathrel {\mathop :}=|\Pr [g \leftarrow \mathbb {G}; a \leftarrow \mathbb {Z}_p^*; b \leftarrow \mathbb {Z}_p: \mathcal {A}(g, g^a, g^b, g^{ab}) = 1] \\&~~ - \Pr [g \leftarrow \mathbb {G}; a \leftarrow \mathbb {Z}_p^*; b \leftarrow \mathbb {Z}_p: \mathcal {A}(g, g^a, g^b, g^{ab+1}) = 1]| = \mathsf{negl}(\lambda ). \end{aligned}$$

2.5 Collision-Resistant Hash Function

In this section, we recall the definition of a collision-resistant hash function. A hash function consists of a pair of PPT algorithms $\varLambda = (\mathsf {HKG}, \mathsf {Hash})$. $\mathsf {HKG}$ is the hash key generation algorithm that, given a security parameter $1^\lambda$, outputs a hash key ${ hk}$. $\mathsf {Hash}$ is the (deterministic) hashing algorithm that, given a hash key ${ hk}$ and a string $x \in \{0,1\}^*$, outputs a hash value $h \in \{0,1\}^{\lambda }$.

Definition 6

(Collision-resistance). We say that $\varLambda = (\mathsf {HKG}, \mathsf {Hash})$ is a collision-resistant hash function if for any PPT adversary $\mathcal {A}$,

3 CCA Security for Receiver Non-commiting Encryption

In this section, we introduce a new security notion that we call $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for receiver non-commiting encryption (RNCE). Next, we show that $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE.

3.1 Receiver Non-commiting Encryption

Here, we give definitions of RNCE and $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for this primitive. Informally, RNCE is 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). Canetti, Halevi, and Katz [6, Sect. 4.1] gave a definition of RNCE considering security against non-adaptive chosen ciphertext attacks (CCA1). We extend their definition to one considering security against adaptive CCA.

Informally, an RNCE scheme $\varPi$ consists of the seven PPT algorithms $(\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec}, \mathsf {FKG}, \mathsf {Fake}, \mathsf {Open}, \mathsf {FDec})$. $(\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})$ are the same algorithms as those of a PKE scheme. The remaining four algorithms $(\mathsf {FKG}, \mathsf {Fake}, \mathsf {Open}, \mathsf {FDec})$ are used for defining the security notion of this primitive. Therefore, these algorithms are not used when using this scheme in practice. We note that the definition of RNCE in [6, Sect. 4.1] does not contain $\mathsf {FKG}$ and $\mathsf {FDec}$, but they are necessary for our formalization of $\mathrm{RNC}\text {-}\mathrm{CCA}$ security. The formal definition is as follows.

Definition 7

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

$\mathsf {FKG}$::

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

$\mathsf {Fake}$::

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

$\mathsf {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}}$.

$\mathsf {FDec}$::

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

 

Next, we define $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for RNCE as follows.

Definition 8

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

In $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {real}}_{\varPi , \mathcal {A}}(\lambda )$, a decryption query c is answered by $\mathsf {Dec}({ pk}, { sk}, c)$. On the other hand, in $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {sim}}_{\varPi , \mathcal {A}}(\lambda )$, a decryption query c is answered by $\mathsf {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 RNC-CCA secure if for any PPT adversary $\mathcal {A}$,

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

3.2 $\mathrm{RNC}\text {-}\mathrm{CCA}$ Secure RNCE Implies $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ Secure PKE

In this section, we show that an $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE scheme implies a $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ secure PKE scheme. Specifically, we show the following theorem.

Theorem 1

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

Here we describe an intuition of the proof. (Due to the space limitation, the formal proof of Theorem 1 is given in the full version of this paper.) Let n be the number of key pairs and $\mathcal {A}$ be an adversary against the $\mathrm{SIM}\text {-}\mathrm{RSO}\text {-}\mathrm{CCA}$ security of $\varPi _{\mathsf {rso}}$ in security experiments. In the proof, we firstly construct a PPT simulator $\mathcal {S}$ in $\mathsf{Exp}^{\mathsf {rso}\text {-}\mathsf {cca}\text {-}\mathsf {sim}}_{n, \varPi _{\mathsf {rso}}, \mathcal {S}}(\lambda )$. Specifically, $\mathcal {S}$ computes fake ciphertexts $(\widetilde{c_j})_{j \in [n]}$ using $\mathsf {Fake}$ and fake secret keys $(\widetilde{{ sk}_j})_{j \in J}$ using $\mathsf {Open}$, where J is the set of corrupted indices. Here, $\mathcal {S}$ can perfectly simulate the decryption oracle for $\mathcal {A}$ using the trapdoors $({ td}_j)_{j \in [n]}$ generated by $\mathcal {S}$.

Next, in order to move from the real experiment $\mathsf{Exp}^{\mathsf {rso}\text {-}\mathsf {cca}\text {-}\mathsf {real}}_{n, \varPi _{\mathsf {rso}}, \mathcal {A}}(\lambda )$ to the simulated experiment $\mathsf{Exp}^{\mathsf {rso}\text {-}\mathsf {cca}\text {-}\mathsf {sim}}_{n, \varPi _{\mathsf {rso}}, \mathcal {S}}(\lambda )$, we change, step by step, n real challenge ciphertexts $(c^*_j)_{j \in [n]}$ to n fake ciphertexts $(\widetilde{c_j})_{j \in [n]}$ and n real secret keys $({ sk}_j)_{j \in [n]}$ to n fake secret keys $(\widetilde{{ sk}_j})_{j \in [n]}$ which are given to $\mathcal {A}$, respectively. We can show this by the $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of $\varPi$ using a hybrid argument. Here, we have to deal with some technically subtle point when simulating the decryption oracle for $\mathcal {A}$. Namely, we have to program the behavior of an adversary $\mathcal {B}$ against the $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of $\varPi$ depending on whether the index i is contained in the corrupted set J output by $\mathcal {A}_2$, where i is the position that $\mathcal {B}$ embeds his own challenge instance into the challenge instances of $\mathcal {A}$. See the full version of this paper for the details.

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

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

4.1 The Description of Our Generic Construction

Here, we formally describe our generic construction of an $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE scheme with the plaintext space $\{0,1\}$. Let $\varPi =(\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})$ be a PKE scheme with the plaintext space $\{0,1\}$ and $\mathcal {R}_{\varPi }$ be a randomness space for the encryption algorithm $\mathsf {Enc}$. Let $\varPhi = (\mathsf {CRSGen}, \mathsf {Prove}, \mathsf {Verify}, \mathsf {SimCRS}, \mathsf {SimPrv})$ be a non-interactive proof system for $L_{eq}$, where

Then, we construct an RNCE scheme $\varPi ' = (\mathsf {KG}', \mathsf {Enc}', \mathsf {Dec}', \mathsf {FKG}', \mathsf {Fake}', \mathsf {Open}', \mathsf {FDec}')$ with the plaintext space $\{0,1\}$ as described in Fig. 1. We note that, considering a real ciphertext c and a real secret key ${ sk}$, the correctness of the decryption of $\varPi '$ is straightforward due to the correctness of $\varPi$ and $\varPhi$.

Fig. 1.

Our generic construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE $\varPi '$.

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 an $\text {OTSS-NIZK}$. 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})_{i \in [\ell ]}$, where $\alpha _1, \cdots , \alpha _{\ell } \leftarrow \{0,1\}$, $({ pk}^i_v, { sk}^i_v) \leftarrow \mathsf {KG}(1^\lambda )$ for all $(i, v) \in [\ell ] \times \{0,1\}$, and ${ crs}$ denotes a CRS of an $\text {OTSS-NIZK}$. Next, we compute a ciphertext $c = ((c^i_{0})_{i\in [\ell ]}, (c^i_{1})_{i\in [\ell ]}, \pi )$, where $c^i_{v} \leftarrow \mathsf {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 the $\text {OTSS-NIZK}$. See the full version of the paper for the details.

4.2 Security Proof

In this section, we show the following theorem.

Theorem 2

If $\varPi$ is an IND-CPA secure PKE scheme and $\varPhi$ is an $\text {OTSS-NIZK}$, then $\varPi '$ is RNC-CCA secure.

Before describing the formal proof, we highlight the flow of the proof. We change $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {real}}_{\varPi ', \mathcal {A}}(\lambda )$ to $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {sim}}_{\varPi ', \mathcal {A}}(\lambda )$ step by step, where $\mathcal {A}$ is an adversary that attacks the $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of $\varPi '$. Although the main part of our proof is similar to that of the original double encryption paradigm [23, 26], we have the following three remarkable changes.

First, toward transforming the challenge ciphertext to a fake ciphertext, we make the challenge ciphertext component $c^*_{1 \oplus \alpha }$ encrypts $1 \oplus m^*$. Second, in order to eliminate the information of the bit $\alpha$ from the decryption oracle, when answering a decryption query $c = (c_0, c_1, \pi )$ made by $\mathcal {A}$, we use the components $({ pk}_0, { sk}_0, c_0)$ corresponding to the position 0 instead of the components $({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$ corresponding to the position $\alpha$. Third, we use $\alpha \oplus m^*$ instead of $\alpha$ in order to make the challenge ciphertext $c^*$ and the secret key ${ sk}$ be independent of the challenge plaintext $m^*$. Due to these changes, the challenge ciphertext $c^*$ and the real secret key ${ sk}$ are respectively switched to the fake ciphertext $\widetilde{c}$ and the fake secret key $\widetilde{{ sk}}$. The proof is as follows.

Proof of Theorem 2

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

$\mathsf{Exp}_0:$ :

$\mathsf{Exp}_0$ is the same as $\mathsf{Exp}^{\mathsf {rnc}\text {-}\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 \mathsf {KG}(1^\lambda )$, $({ pk}_1, { sk}_1) \leftarrow \mathsf {KG}(1^\lambda )$, and ${ crs}\leftarrow \mathsf {CRSGen}(1^\lambda )$. Next, $\mathsf{Exp}_0$ sets ${ pk}\mathrel {\mathop :}=({ pk}_0, { pk}_1, { crs})$ and ${ sk}\mathrel {\mathop :}=(\alpha , { sk}_{\alpha })$ 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 $\mathsf {Verify}({ crs},({ pk}_0, { pk}_1, c_0, c_1),\pi ) = 1$ holds. If this holds, $\mathsf{Exp}_0$ computes $m \leftarrow \mathsf {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}^2_{\varPi }$, computes $c^*_0 \leftarrow \mathsf {Enc}({ pk}_0, m^*; r^*_0)$, $c^*_1 \leftarrow \mathsf {Enc}({ pk}_1, m^*; r^*_1)$, and $\pi ^*\leftarrow \mathsf {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)$. 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. The common reference string ${ crs}$ is generated by executing $({ crs}, { tk}) \leftarrow \mathsf {SimCRS}(1^\lambda )$, and $\mathsf{Exp}_1$ generates a simulated proof $\pi ^*\leftarrow \mathsf {SimPrv}({ tk}, ({ pk}_0,{ pk}_1,c^*_0, c^*_1))$ when computing the challenge ciphertext $c^*$.

$\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 \mathsf {Enc}({ pk}_{1 \oplus \alpha }, 1 \oplus m^*)$ instead of $c^*_{1 \oplus \alpha } \leftarrow \mathsf {Enc}({ pk}_{1 \oplus \alpha }, m^*)$.

$\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 )$, $\mathsf{Exp}_3$ answers $m \leftarrow \mathsf {Dec}({ pk}_{0}, { sk}_{0}, c_{0})$ instead of $m \leftarrow \mathsf {Dec}({ pk}_{\alpha }, { sk}_{\alpha }, c_{\alpha })$, if $\mathsf {Verify}({ crs}, ({ pk}_0, { pk}_1, c_0, c_1),\pi ) = 1$ holds. Note that the decryption procedure in $\mathsf{Exp}_3$ is exactly the same as $\mathsf {FDec}'$.

$\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 \mathsf {Enc}({ pk}_{\alpha \oplus m^*}, m^*)$ and $c^*_{\alpha \oplus (1 \oplus m^*)} \leftarrow \mathsf {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^*})$ 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}\text {-}\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}\text {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) = |\Pr [\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {real}}_{\varPi ', \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {rnc}\text {-}\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. Due to the space limitation, we will show them formally in the full version of the paper. There, we will show that there exist an adversary $\mathcal {E}= (\mathcal {E}_1, \mathcal {E}_2)$ against the ZK property of $\varPhi$ such that $|p_0 - p_1| = \mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {E}}(\lambda )$, an adversary $\mathcal {F}= (\mathcal {F}_1, \mathcal {F}_2)$ against the $\mathrm{IND}\text {-}\mathrm{CPA}$ security of $\varPi$ such that $|p_1 - p_2| = \mathsf{Adv}^{\mathsf {ind}\text {-}\mathsf {cpa}}_{\varPi , \mathcal {F}}(\lambda )$, and an adversary ${\mathcal {G}= (\mathcal {G}_1, \mathcal {G}_2)}$ against the OT-SS of $\varPhi$ such that ${|p_2 - p_3| \le \mathsf{Adv}^{\mathsf {ot}\text {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )}$. Then, we will show that $|p_3 - p_4| = 0$ holds. The main reason why this is true, is because since $\alpha$ is chosen uniformly at random, $\alpha \oplus m^*$ is also distributed uniformly at random. Finally, we will show that $|p_4 - p_5| = 0$ holds, by showing that $\mathsf{Exp}_4$ and $\mathsf{Exp}_5$ are identical.

Putting everything together, we obtain $\mathsf{Adv}^{\mathsf {rnc}\text {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) = |p_0 - p_5| \le \sum ^{4}_{i=0} |p_i - p_{i+1} | \le \mathsf{Adv}^{\mathsf {zk}}_{\varPhi , \mathcal {E}}(\lambda ) + \mathsf{Adv}^{\mathsf {ind}\text {-}\mathsf {cpa}}_{\varPi , \mathcal {F}}(\lambda ) + \mathsf{Adv}^{\mathsf {ot}\text {-}\mathsf {ss}}_{\varPhi , \mathcal {G}}(\lambda )$. Since $\varPi$ is $\mathrm{IND}\text {-}\mathrm{CPA}$ secure and $\varPhi$ is an $\text {OTSS-NIZK}$, for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {rnc}\text {-}\mathsf {cca}}_{\varPi ', \mathcal {A}}(\lambda ) = \mathsf{negl}(\lambda )$ holds. Therefore, $\varPi '$ satisfies $\mathrm{RNC}\text {-}\mathrm{CCA}$ security. $\square$ (Theorem 2)

5 Our DDH-Based Concrete Construction of RNC-CCA Secure RNCE

In this section, we show our concrete construction of $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure RNCE with a polynomial-sized plaintext space, based on the DDH assumption and a collision-resistant hash function. First, in Sect. 5.1, we describe our DDH-based concrete construction. Then, in Sect. 5.2, we give a proof of $\mathrm{RNC}\text {-}\mathrm{CCA}$ security for our DDH-based construction.

5.1 The Description of Our Concrete Construction

Here, we give the formal description of our DDH-based construction of RNC-CCA secure RNCE with a polynomial-sized plaintext space. One can see that our scheme is a variant of the Cramer-Shoup encryption scheme [7]. The only difference is that we encode a plaintext m by the group element $g^m_1$, where $g_1$ is a generator of the underlying group. This encoding is essential for the opening algorithm $\mathsf {Open}$ of our proposed scheme. The plaintext space of our scheme needs to be of polynomial-size since we need to compute the discrete logarithm of $g^m_1$ for the decryption procedure.

Formally, we let $\varLambda = (\mathsf {HKG}, \mathsf {Hash})$ be a hash function. Let $\mathbb {G}$ be a multiplicative cyclic group of prime order $p = \varTheta (2^\lambda )$. We naturally encode an element in $\{0,1\}^\lambda$ as one in $\mathbb {Z}_p$. Then, we construct our RNCE scheme $\varPi _{\mathsf {ddh}} = (\mathsf {KG}, \mathsf {Enc}, \mathsf {Dec}, \mathsf {FKG}, \mathsf {Fake}, \mathsf {Open}, \mathsf {FDec})$ as described in Fig. 2. We note that the correctness of the decryption of $\varPi _{\mathsf {ddh}}$ is straightforward due to the correctness of the original Cramer-Shoup encryption scheme.

Fig. 2.

Our DDH-based construction of RNC-CCA secure RNCE $\varPi _{\mathsf {ddh}}$.

5.2 Security Proof

In this section, we show the following theorem.

Theorem 3

If the “+1”-DDH assumption holds in $\mathbb {G}$, and $\varLambda = (\mathsf {HKG}, \mathsf {Hash})$ is a collision-resistant hash function, then $\varPi _{\mathsf {ddh}}$ is RNC-CCA secure.

Since the “+1”-DDH assumption is implied by the ordinary DDH assumption, Theorem 3 implies that our construction $\varPi _{\mathsf {ddh}}$ is indeed $\mathrm{RNC}\text {-}\mathrm{CCA}$ secure under the ordinary DDH assumption.

Before describing the proof, we highlight the flow of the proof. We change $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {real}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda )$ to $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {sim}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda )$ step by step, where $\mathcal {A}$ is an adversary that attacks the $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of $\varPi _{\mathsf {ddh}}$. Although the main part of our proof is similar to that of the original HPS technique [7, 8], we have the following two remarkable changes in order to change the challenge ciphertext $c^*$ to a fake ciphertext $\widetilde{c}$.

First, toward transforming the challenge ciphertext to a fake ciphertext, we change the challenge ciphertext component $u^*_2 = g^{r^*}_2$ to $u^*_2 = g_1 g^{r^*}_2$. Second, we change the real secret key component $(x_1, x_2)$ to the fake secret key component $(x'_1, x'_2)$ computed by $\mathsf {Open}$ described in Fig. 2. Due to these changes, the challenge ciphertext component $e^*$ is changed to the fake ciphertext component $\widetilde{e}$ and the real secret key ${ sk}$ is changed to the fake secret key $\widetilde{{ sk}}$. The proof is as follows.

Proof of Theorem 3

Let $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2, \mathcal {A}_3)$ be any PPT adversary that attacks the $\mathrm{RNC}\text {-}\mathrm{CCA}$ security of $\varPi _{\mathsf {ddh}}$ and makes $Q_{dec} > 0$ decryption queries. We introduce the following experiments $\{\mathsf{Exp}_i\}^{7}_{i=0}$.

$\mathsf{Exp}_0:$ :

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

1.:

First, $\mathsf{Exp}_0$ samples $g_1 \leftarrow \mathbb {G}$ and $w \leftarrow \mathbb {Z}_p^*$ and sets $g_2 \mathrel {\mathop :}=g^w_1$. Next, $\mathsf{Exp}_0$ samples $x_1, x_2, y_1, y_2, z_1,z_2 \leftarrow \mathbb {Z}_p$ and sets $k \mathrel {\mathop :}=g^{x_1}_1 g^{x_2}_2$, $s \mathrel {\mathop :}=g^{y_1}_1 g^{y_2}_2$, and $t \mathrel {\mathop :}=g^{z_1}_1 g^{z_2}_2$. Then, it samples ${ hk}\leftarrow \mathsf {HKG}(1^\lambda )$, sets ${ pk}\mathrel {\mathop :}=(g_1, g_2, k, s, t, { hk})$ and ${ sk}\mathrel {\mathop :}=(x_1, x_2, y_1, y_2, z_1,z_2)$, and runs $\mathcal {A}_1({ pk})$. When $\mathcal {A}_1$ makes a decryption query $c = (u_1,u_2,e,v)$, $\mathsf{Exp}_0$ computes $\mu \leftarrow \mathsf {Hash}({ hk}, u_1\Vert u_2\Vert e)$ and checks whether $u^{y_1+z_1\mu }_1 u^{y_2+z_2\mu }_2 = v$ holds. If this holds, $\mathsf{Exp}_0$ returns $m = \log _{g_1} (e \cdot (u^{x_1}_1 u^{x_2}_2)^{-1})$ 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^*\leftarrow \mathbb {Z}_p$ and sets $u^*_1 \mathrel {\mathop :}=g^{r^*}_1$, $u^*_2 \mathrel {\mathop :}=g^{r^*}_2$, and $e^*\mathrel {\mathop :}=k^{r^*} \cdot g^{m^*}_1$. Next, $\mathsf{Exp}_0$ computes $\mu ^*\leftarrow \mathsf {Hash}({ hk}, u^*_1\Vert u^*_2\Vert e^*)$, sets $v^*\mathrel {\mathop :}=s^{r^*} t^{r^*\mu ^*}$ and $c^*\mathrel {\mathop :}=(u^*_1, u^*_2, e^*, v^*)$, and runs $\mathcal {A}_2(c^*, \mathsf{st}_1)$. When $\mathcal {A}_2$ makes a decryption query $c = (u_1, u_2, e, v)$, $\mathsf{Exp}_0$ answers the query from $\mathcal {A}_2$ 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)$. When $\mathcal {A}_3$ outputs $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^*= (u^*_1, u^*_2, e^*, v^*)$, $\mathsf{Exp}_1$ computes $e^*$ and $v^*$ by $e^*\mathrel {\mathop :}=(u^*_1)^{x_1} (u^*_2)^{x_2} \cdot \, g^{m^*}_1$ and $v^*\mathrel {\mathop :}=(u^*_1)^{y_1} (u^*_2)^{y_2} ((u^*_1)^{z_1} (u^*_2)^{z_2})^{\mu ^*}$, respectively.

$\mathsf{Exp}_2:$ :

$\mathsf{Exp}_2$ is identical to $\mathsf{Exp}_1$ except that when computing the challenge ciphertext $c^*= (u^*_1, u^*_2, e^*, v^*)$, $\mathsf{Exp}_2$ computes $u^*_2$ by $u^*_2 \mathrel {\mathop :}=g^{wr^*+1}_1$.

$\mathsf{Exp}_3:$ :

$\mathsf{Exp}_3$ is identical to $\mathsf{Exp}_2$ except that when responding to a decryption query $c = (u_1, u_2, e, v)$ made by $\mathcal {A}_2$, $\mathsf{Exp}_3$ answers $\bot$ if $\mathsf {Hash}({ hk}, u^*_1\Vert u^*_2\Vert e^*) = \mathsf {Hash}({ hk}, u_1\Vert u_2\Vert e)$ holds.

$\mathsf{Exp}_4:$ :

$\mathsf{Exp}_4$ is identical to $\mathsf{Exp}_3$ except that when responding to a decryption query $c = (u_1, u_2, e, v)$ made by $\mathcal {A}_1$ or $\mathcal {A}_2$, $\mathsf{Exp}_4$ answers $\bot$ if $u^w_1 \ne u_2$ holds.

$\mathsf{Exp}_5:$ :

$\mathsf{Exp}_5$ is identical to $\mathsf{Exp}_4$ except that $x'_1 \mathrel {\mathop :}=x_1 + wm^*$ (mod p) and $x'_2 \mathrel {\mathop :}=x_2 - m^*$ (mod p) are used instead of $x_1$ and $x_2$, respectively. That is, when computing the challenge ciphertext $c^*\mathrel {\mathop :}=(u^*_1, u^*_2, e^*, v^*)$, $\mathsf{Exp}_5$ computes $e^*$ by $e^*\mathrel {\mathop :}=(u^*_1)^{x'_1} (u^*_2)^{x'_2} \cdot g^{m^*}_1$ instead of $(u^*_1)^{x_1} (u^*_2)^{x_2} \cdot \, g^{m^*}_1$. Note that $e^*= (u^*_1)^{x'_1} (u^*_2)^{x'_2} \cdot g^{m^*}_1 = (g^{r^*}_1)^{(x_1+wm^*)} (g^{(wr^*+1)}_1)^{(x_2 - m^*)} \cdot g^{m^*}_1 = g^{x_2}_1 (g^{x_1}_1 g^{x_2}_2)^{r^*}$ holds. Furthermore, $\mathsf{Exp}_5$ gives the secret key ${ sk}' \mathrel {\mathop :}=(x'_1, x'_2, y_1, y_2, z_1, z_2)$ to $\mathcal {A}_3$ instead of ${ sk}\mathrel {\mathop :}=(x_1, x_2, y_1, y_2, z_1, z_2)$.

Since $e^*$ in $\mathsf{Exp}_5$ is independent of the challenge message $m^*$, without loss of generality we generate it before $\mathcal {A}_1$ is run.

$\mathsf{Exp}_6:$ :

$\mathsf{Exp}_6$ is identical to $\mathsf{Exp}_5$ except that when responding to a decryption query $c = (u_1, u_2, e, v)$ made by $\mathcal {A}_1$, $\mathsf{Exp}_6$ answers $\bot$ if $\mathsf {Hash}({ hk}, u^*_1\Vert u^*_2\Vert e^*) = \mathsf {Hash}({ hk}, u_1\Vert u_2\Vert e)$ holds. Note that the procedure of the decryption oracle in $\mathsf{Exp}_6$ is exactly the same as that of $\mathsf {FDec}({ pk}, { td}, c)$.

$\mathsf{Exp}_7:$ :

$\mathsf{Exp}_7$ is exactly the same as $\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {sim}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda )$.

 

We let $p_i \mathrel {\mathop :}=\Pr [\mathsf{Exp}_i(\lambda ) = 1]$ for all $i \in [0, 7]$. Then, we have $\mathsf{Adv}^{\mathsf {rnc}\text {-}\mathsf {cca}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda ) = |\Pr [\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {real}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda ) = 1] - \Pr [\mathsf{Exp}^{\mathsf {rnc}\text {-}\mathsf {sim}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda ) = 1]| = |p_0 - p_7| \le \sum ^{6}_{i = 0} |p_i - p_{i+1}|$. It remains to show how each $|p_i - p_{i+1}|$ is upper-bounded. Due to the space limitation, we will show them formally in the full version of the paper. There, we will show that $|p_0 - p_1| = 0$ holds since the difference between $\mathsf{Exp}_0$ and $\mathsf{Exp}_1$ is only conceptual. Then, we will show that there exist a PPT adversary $\mathcal {E}$ against the “+1”-DDH assumption in $\mathbb {G}$ such that $|p_1 - p_2| = \mathsf{Adv}^{+1\text {-}\mathsf {ddh}}_{\mathbb {G}, \mathcal {E}}(\lambda )$, and a PPT adversary $\mathcal {F}$ against the collision-resistance of $\varLambda$ such that $|p_2 - p_3| \le \mathsf{Adv}^{\mathsf {cr}}_{\varLambda , \mathcal {F}}(\lambda )$. Next, we will show that $|p_3 - p_4| \le \frac{Q_{dec}}{p}$ holds by showing that the probability that each of $\mathcal {A}$’s valid queries is rejected in $\mathsf{Exp}_5$ but not in $\mathsf{Exp}_4$, is at most $\frac{1}{p}$. Then, we will show that $|p_4 - p_5| = 0$ holds since $(x_1, x_2)$ and $(x'_1, x'_2)$ are information-theoretically indistinguishable from $\mathcal {A}$. Next, we will show that there exists a PPT adversary ${\mathcal {G}}$ against the collision-resistance of $\varLambda$ such that ${|p_5 - p_6| \le \mathsf{Adv}^{\mathsf {cr}}_{\varLambda , \mathcal {G}}(\lambda ) + \frac{Q_{dec}}{p}}$. Finally, we will show that $|p_6 - p_7| = 0$ holds, by showing that $\mathsf{Exp}_6$ and $\mathsf{Exp}_7$ are identical.

Putting everything together, we obtain $\mathsf{Adv}^{\mathsf {rnc}\text {-}\mathsf {cca}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda ) = |p_0 - p_7| \le \sum ^{6}_{i=0} |p_i - p_{i+1} | \le \mathsf{Adv}^{+1\text {-}\mathsf {ddh}}_{\mathbb {G}, \mathcal {E}}(\lambda ) + \mathsf{Adv}^{\mathsf {cr}}_{\varLambda , \mathcal {F}}(\lambda ) + \mathsf{Adv}^{\mathsf {cr}}_{\varLambda , \mathcal {G}}(\lambda ) + \frac{2Q_{dec}}{p}$. Since the “+1”-DDH assumption holds in $\mathbb {G}$, $\varLambda$ is a collision-resistant hash function, $Q_{dec}$ is a polynomial of $\lambda$, and $p = \varTheta (2^\lambda )$, for any PPT adversary $\mathcal {A}$, $\mathsf{Adv}^{\mathsf {rnc}\text {-}\mathsf {cca}}_{\varPi _{\mathsf {ddh}}, \mathcal {A}}(\lambda ) = \mathsf{negl}(\lambda )$ holds. Therefore, $\varPi _{\mathsf {ddh}}$ satisfies $\mathrm{RNC}\text {-}\mathrm{CCA}$ security. $\square$ (Theorem 3)