Simulation-Based Bi-Selective Opening Security for Public Key Encryption

Abstract

Selective opening attacks (SOA) (for public-key encryption, PKE) concern such a multi-user scenario, where an adversary adaptively corrupts some fraction of the users to break into a subset of honestly created ciphertexts, and tries to learn the information on the messages of some unopened (but potentially related) ciphertexts. Until now, the notion of selective opening attacks is only considered in two settings: sender selective opening (SSO), where part of senders are corrupted and messages together with randomness for encryption are revealed; and receiver selective opening (RSO), where part of receivers are corrupted and messages together with secret keys for decryption are revealed.

In this paper, we consider a more natural and general setting for selective opening security. In the setting, the adversary may adaptively corrupt part of senders and receivers simultaneously, and get the plaintext messages together with internal randomness for encryption and secret keys for decryption, while it is hoped that messages of uncorrupted parties remain protected. We denote it as Bi-SO security since it is reminiscent of Bi-Deniability for PKE.

We first formalize the requirement of Bi-SO security by the simulation-based (SIM) style, and prove that some practical PKE schemes achieve SIM-Bi-$\text {SO}$-CCA security in the random oracle model. Then, we suggest a weak model of Bi-SO security, denoted as SIM-wBi-$\text {SO}$-CCA security, and argue that it is still meaningful and useful. We propose a generic construction of PKE schemes that achieve SIM-wBi-$\text {SO}$-CCA security in the standard model and instantiate them from various standard assumptions. Our generic construction is built on a newly presented primitive, namely, universal$_{\kappa }$ hash proof system with key equivocability, which may be of independent interest.

1 Introduction

Public key encryption (PKE) is a fundamental tool to protect messages sent over a public channel. Usually, a PKE scheme is used in an open system with multi-users. The system contains multiple, say n, users, each with a public key/secret key pair, i.e., there are n public keys in the system. Anyone (even not registered in the system) can send messages over the public channel to a user securely via encrypting the message under the user’s public key. Thus, each public key will be used for multiple, say k, times during the lifetime of the system.

Selective Opening Attacks. Currently, the standard security for PKE schemes is the so-called “Chosen-ciphertext attack (CCA) security”, which allows the attacker to learn the decryption of its selected ciphertexts. Generally, PKE schemes are designed to guarantee security of all messages in the system against a CCA attacker under the assumption that internal status of all users are properly protected. This assumption, however, will be challenged in some real-world scenarios:

• The attacker may corrupt the senders and learn their messages and the encryption randomness.

• The attacker may corrupt the receivers and learn their secret keys. With the receivers’ secret keys, the attacker is able to decrypt all ciphertexts sent to the receivers and obtain the messages.

While it is hopeless to protect those opened messages, one natural question is whether the unopened messages are still well protected. The above attacks are called selective opening attacks. Surprisingly, it is proved that standard security notion (i.e., CCA security) is not able to guarantee security against selective opening attacks (SO security) [2, 17, 18].

The notion of SO security for PKE was firstly formalized by Bellare et al. [3] at EUROCRYPT 2009. To date, two settings have been considered for SO security: sender corruption [3] and receiver corruption [2]. In the sender corruption setting, part of senders are corrupted, with the corruption exposing their coins and messages. In the receiver corruption setting, part of receivers are corrupted, with corruption exposing their secret keys and messages. We denote SO security in the sender-corruption setting and in the receiver-corruption setting by SSO security and RSO security, respectively.

Furthermore, for each setting, there are two types of definitions for SO security: indistinguishability-based (IND) SO security and simulation-based (SIM) SO security. IND-SO security requires that no efficient adversary can distinguish the uncorrupted users’ ciphertexts from the encryption of fresh messages, which are sampled according to a conditional probability distribution (conditioned on the opened ciphertexts, which means the ciphertexts of the corrupted parties). In other words, IND-SO security requires that the considered message distributions should be efficiently conditionally re-samplable [3]. SIM-SO security requires that anything, which can be computed efficiently from the ciphertexts, the opened messages as well as the corrupted information, can also be computed efficiently only with the opened messages. SIM-SO security imposes no limitation on the message distributions.

Motivations. Previous works on SIM-SO-CCA secure PKE schemes only provide either sender selective opening security [3, 9, 14, 16, 20, 21, 25,26,27], or receiver selective opening security [2, 11, 12, 19, 23, 32]. However, it is rarely possible to predict whether the attacker will corrupt the senders or the receivers beforehand in practice. Moreover, most of the previous works about RSO security only focused on the single-challenge setting, i.e., each public key can only be used once to produce a single ciphertext. This is very unrealistic in practice.¹

Based on the above facts, the following question is raised naturally: How to define security models to capture the practical requirements of selective opening security in the multi-user scenario, and provide secure PKE schemes in the new models?

Our Contributions. In this paper, for a multi-user system with multiple public keys where each public key will be used multiple times, we give a new security definition of SO security, denoted as SIM-Bi-SO-CCA security. In the security model, the adversary may adaptively corrupt some fraction of senders and receivers simultaneously, and get the plaintext messages together with internal randomness for encryption and secret keys for decryption, while it is hoped that messages of uncorrupted parties remain protected. (The definition is reminiscent of Bi-Deniability [29] for PKE.) We prove that some practical PKE schemes achieve SIM-Bi-SO-CCA security in the random oracle model.

Then, we suggest a weak model of SIM-Bi-SO-CCA security, denoted as SIM-wBi-$\text {SO}_{k}$-CCA security ($k\in \mathbb {N}$), where (i) the adversary has to specify whether it is going to corrupt the senders or the receivers after receiving the public keys and before seeing the challenge ciphertexts, and (ii) if the adversary chooses to corrupt some fraction of the receivers, it is just allowed to corrupt the receivers whose public keys are employed for encryption at most k times. We stress that the weak model is still meaningful and useful because it provides the original SIM-SSO-CCA security and SIM-RSO-CCA security simultaneously. Furthermore, we show that SIM-wBi-$\text {SO}_{k}$-CCA security is strictly stronger than SIM-SSO-CCA security and SIM-RSO-CCA security. We also stress that the recently proposed SIM-$\text {RSO}_k$-CCA security notion [32] is a special case of our SIM-wBi-$\text {SO}_{k}$-CCA security.

Finally, we propose a generic construction of PKE that achieves SIM-wBi-$\text {SO}_{k}$-CCA security in the standard model and instantiate it from various standard assumptions. Our generic construction is built on a new variant of hash proof system (HPS), which should additionally satisfy the universal$_{k+1}$ property and key equivocability. The technical overview of the generic construction is given in Sect. 4.1. We also explore the existence of universal$_{k+1}$ HPS with key equivocability and provide instantiations from either the DDH assumption or the DCR assumption.

Related works. Since proposed by Bellare et al. in [3], selective opening secure PKE has been extensively studied.

For SSO security, Bellare et al. in [3] firstly showed that any lossy encryption is IND-SSO-CPA secure. IND-SSO-CCA secure PKE schemes were constructed from All-But-N lossy trapdoor functions [13] or All-But-Many lossy trapdoor functions [5, 16, 21, 25]. If this lossy encryption has an efficient opener, then the resulting PKE scheme can be proven to be SIM-SSO-CCA secure as shown in [3]. Fehr et al. [9] showed an approach, employing extended hash proof system and cross-authentication code (XAC), to build SIM-SSO-CCA secure PKE schemes. As pointed out in [20], a stronger property of XAC is needed to make the proof rigorous. Following this line of research, a generic construction of SIM-SSO-CCA secure PKE, from a special kind of key encapsulation mechanism (KEM) and a strengthened XAC, was proposed in [26] and then extended to achieve tight security in [27]. As showed in [14, 15], some practical PKE constructions also enjoy SIM-SSO-CCA security.

For RSO security, Hazay et al. [12] showed that SIM-RSO-CPA secure PKE can be built from non-committing encryption for receiver (NCER) [6], and IND-RSO-CPA secure PKE can be built from a tweaked variant of NCER. IND-RSO-CCA secure PKE schemes were proposed in [23]. SIM-RSO-CCA secure PKE was constructed using indistinguishability obfuscation (iO) in [22], and constructed based on standard computational assumptions in [11, 19]. Recently, Yang et al. [32] formalized the notion of multi-challenge RSO security (RSO$_k$ security), proved that SIM-RSO security is not enough to guarantee SIM-RSO$_k$ security ($k>1$), and showed SIM-RSO$_k$-CPA/CCA secure PKE constructions.

Roadmap. In the rest part of this work, we give some preliminaries in Sect. 2. We introduce the formal definitions for SIM-Bi-SO-CCA security and SIM-wBi-$\text {SO}_{k}$-CCA security ($k\in \mathbb {N}$), and show that SIM-wBi-$\text {SO}_{k}$-CCA security is strictly stronger than SIM-SSO-CCA and SIM-RSO-CCA security in Sect. 3. Next, we introduce the main building block, namely, universal$_\kappa$ HPS with key equivocability, and present a generic construction of PKE scheme that achieves SIM-wBi-$\text {SO}_{k}$-CCA security in the standard model in Sect. 4. Finally, we show that some practical PKE schemes achieve SIM-Bi-SO-CCA security in the random oracle model, in Sect. 5.

2 Preliminaries

Notations. Throughout this paper, let $\lambda \in \mathbb {N}$ denote the security parameter. For $n\in \mathbb {N}$, let [n] denote the set $\{1, 2, \cdots , n\}$. For a finite set $\mathcal {S}$, we use $|\mathcal {S} |$ to denote the size of $\mathcal {S}$; we use $s\leftarrow \mathcal {S}$ to denote the process of sampling s uniformly from $\mathcal {S}$. For a distribution $\textsf {Dist}$, $x\leftarrow \textsf {Dist}$ denotes the process of sampling x from $\textsf {Dist}$.

We use boldface to denote vectors, e.g., $\mathbf{x}$. We use $\mathbf{x} [i]$ to denote the i-th component of $\mathbf{x}$.

For a probabilistic algorithm $\mathcal {A}$, let $\mathcal {R}_\mathcal {A}$ denote the randomness space of $\mathcal {A}$. We let $y\leftarrow \mathcal {A}(x;r)$ denote the process of running $\mathcal {A}$ on input x and inner randomness $r\in \mathcal {R}_{\mathcal {A}}$ and outputting y. We write $y\leftarrow \mathcal {A}(x)$ for $y\leftarrow \mathcal {A}(x;r)$ with uniformly chosen $r\in \mathcal {R}_{\mathcal {A}}$. We write PPT for probabilistic polynomial-time. For a function $f(\lambda )$, we write that $f(\lambda )\le \textsf {negl}(\lambda )$ if it is negligible.

For two distributions $\textsf {Dist}_1$ and $\textsf {Dist}_2$, the statistical distance between $\textsf {Dist}_1$ and $\textsf {Dist}_2$ is defined as

$$\varDelta (\textsf {Dist}_1,\textsf {Dist}_2):=\frac{1}{2}\sum _{x}|\mathop {\Pr }\limits _{X_1\leftarrow \textsf {Dist}_1}{[X_1=x]}-\mathop {\Pr }\limits _{X_2\leftarrow \textsf {Dist}_2}{[X_2=x]}|.$$

We say that $\textsf {Dist}_1$ and $\textsf {Dist}_2$ are statistically indistinguishable (denoted by $\textsf {Dist}_1\overset{s}{\approx }\textsf {Dist}_2$), if $\varDelta (\textsf {Dist}_1,\textsf {Dist}_2)$ is negligible.

Collision-resistant hash. We recall the definition of collision-resistant hash function here.

Definition 1

(Collision-resistant hash function). A family of collision-resistant hash function $\mathcal {H}$, with domain ${\mathsf{Dom}}$ and range ${\mathsf{Rge}}$, is a family of functions having the following property: for any PPT algorithm $\mathcal {A}$, its advantage ${\mathtt {Adv}}_{\mathcal {H}, \mathcal {A}}^{\mathrm {CR}}(\lambda ):= {\mathrm {Pr}}[{\mathsf{H}}\leftarrow \mathcal {H}; (x,x')\leftarrow \mathcal {A}({\mathsf{H}}):x\ne x'\bigwedge {\mathsf{H}}(x)={\mathsf{H}}(x')]$ is negligible.

Efficiently samplable and explainable domain. In this paper, some of the domains are required to be efficiently samplable and explainable [9]. We recall its definition as follows.

Definition 2

(Efficiently samplable and explainable domain). We say that a domain ${\mathsf{Dom}}$ is efficiently samplable and explainable, if there are two PPT algorithms $({\mathsf{Sample}},{\mathsf{Explain}})$:

• Sample$(\mathsf{Dom};r)$ : On input a domain ${\mathsf{Dom}}$ with uniformly sampled $r\leftarrow \mathcal {R}_{{\mathsf{Sample}}}$, Sample outputs an element which is uniformly distributed over ${\mathsf{Dom}}$.

• Explain$(\mathsf{Dom},x)$ : On input ${\mathsf{Dom}}$ and $x\in {\mathsf{Dom}}$, Explain outputs r which is uniformly distributed over the set $\{r\in \mathcal {R}_{{\mathsf{Sample}}}\mid {\mathsf{Sample}}({\mathsf{Dom}}; r)=x\}$.

This notion can be relaxed by allowing a negligibly small error probability (which includes that sampling algorithms may produce near-uniform output).

Cross-authentication code. The notion of $\ell$-cross-authentication code (XAC) was proposed by Fehr et al. [9], and later adapted to strong and semi-unique XAC in [24].

Definition 3

($\ell$-Cross-authentication code). For $\ell \in \mathbb {N}$, an $\ell$-cross-authentication code ($\ell$-XAC) XAC, associated with a key space $\mathcal {XK}$ and a tag space $\mathcal {XT}$, consists of three PPT algorithms (XGen, XAuth, XVer). Algorithm XGen$(1^\lambda )$ generates a uniformly random key $K\in \mathcal {XK}$, deterministic algorithm ${\mathsf{XAuth}}(K_1, \cdots , K_\ell )$ produces a tag $T\in \mathcal {XT}$, and deterministic algorithm ${\mathsf{XVer}}(K, T)$ outputs $b\in \{0, 1\}$. The following properties are required:

• Correctness: For all $i\in [\ell ]$, ${\mathsf{fail}}_{{\mathsf{XAC}}}(\lambda ):={\mathrm {Pr}}[{\mathsf{XVer}}(K_i, {\mathsf{XAuth}}(K_1, \cdots , K_\ell ))\ne 1]$ is negligible, where $K_1, \cdots , K_\ell \leftarrow {\mathsf{XGen}}(1^\lambda )$ in the probability.

• Security against impersonation and substitution attacks: ${\mathtt {Adv}}_{{\mathsf{XAC}}}^{{\mathrm {IMP}}}(\lambda )$ and ${\mathtt {Adv}}_{{\mathsf{XAC}}}^{{\mathrm {SUB}}}(\lambda )$ as defined below are both negligible: ${\mathtt {Adv}}_{{\mathsf{XAC}}}^{{\mathrm {IMP}}}(\lambda ):=\max \limits _{i, T'}{\mathrm {Pr}}[K\leftarrow {\mathsf{XGen}}(1^\lambda ):{\mathsf{XVer}}(K,T')=1]$, where the max is over all $i\in [\ell ]$ and $T'\in \mathcal {XT}$, and

  $$\begin{aligned} \begin{array}{r@{~}l} {\mathtt {Adv}}_{{\mathsf{XAC}}}^{{\mathrm {SUB}}}(\lambda ):=\max \limits _{i, K_{\ne i}, F} {\mathrm {Pr}} \left[ \begin{array}{l} K_i\leftarrow {\mathsf{XGen}}(1^k) \\ T={\mathsf{XAuth}}((K_j)_{j\in [\ell ]})\\ T'\leftarrow F(T)\\ \end{array} {\mathrm {{:}}} \begin{array}{c} T'\ne T \bigwedge \\ {\mathsf{XVer}}(K_i, T')=1 \end{array} \right] ,\nonumber \end{array} \end{aligned}$$

  where the max is over all $i\in [\ell ]$, all $K_{\ne i}:=(K_j)_{j\ne i}\in \mathcal {XK}^{\ell -1}$ and all possibly randomized functions $F: \mathcal {XT}\rightarrow \mathcal {XT}$.

Definition 4

(Strong and semi-unique $\ell$-XAC). For $\ell \in \mathbb {N}$, we say that an $\ell$-XAC XAC is strong and semi-unique, if it has the following two properties:

• Strongness: There is a PPT algorithm ReSamp, which takes $i\in [\ell ]$, $K_{\ne i}$ and T as input (where $K_1, \cdots , K_\ell \leftarrow {\mathsf{XGen}}(1^\lambda )$ and $T={\mathsf{XAuth}}((K_j)_{j\in [\ell ]})$) and outputs $K'_i$, such that $K'_i$ and $K_i$ are statistically indistinguishable, i.e.,

  $$\begin{aligned} {\mathtt {StD}}^{{\mathrm {STRN}}}_{{\mathsf{XAC}}}(\lambda ):= & {} \varDelta (K'_i,K_i)\\= & {} \frac{1}{2}\sum _{K\in \mathcal {XK}} \left| {\mathrm {Pr}}[K_i'=K|(K_{\ne i}, T)]-{\mathrm {Pr}}[K_i=K|(K_{\ne i}, T)]\right| \end{aligned}$$

  is negligible, where the probabilities are taken over $K_i\leftarrow {\mathsf{XGen}}(1^\lambda )$, conditioned on $(K_{\ne i}, T)$, and the randomness of ReSamp.

• Semi-uniqueness: The key space $\mathcal {XK}$ can be written as $\mathcal {K}_a\times \mathcal {K}_b$. Given a tag $T\in \mathcal {XT}$ and $K_a\in \mathcal {K}_a$, there is at most one $K_b\in \mathcal {K}_b$ such that ${\mathsf{XVer}}((K_a,K_b),T)=1$.

3 Bi-SO Security for PKE

Previous security notions of SOA for PKE only consider either sender corruption setting or receiver corruption setting. We consider a more natural and general setting for selective opening security. In the setting, the adversary may adaptively corrupt part of senders and receivers simultaneously. We denote it as Bi-SO security since it is reminiscent of Bi-Deniability [29] for PKE.

For a multi-user system with multiple public keys where each public key will be used many times, we firstly give the most natural security notion of Bi-SO security, denoted as SIM-Bi-SO-CCA security. Then, we suggest a weak model of SIM-Bi-SO-CCA security, denoted as SIM-wBi-$\text {SO}_{k}$-CCA security ($k\in \mathbb {N}$). The weak model is still meaningful and useful because it provides the original SIM-SSO-CCA security and SIM-RSO-CCA security simultaneously. Finally, for completeness, we show that SIM-wBi-$\text {SO}_{k}$-CCA security is strictly stronger than SIM-SSO-CCA and SIM-RSO-CCA security.

3.1 Security Definitions

Simulation-based Bi-SO security. In the Bi-SO setting, some of the senders and some of the receivers may be corrupted simultaneously, and each public key may be used to encrypt multiple messages. The formal definition is as follows.

Definition 5

(SIM-Bi-SO-CCA). We say that a PKE scheme ${\mathsf{PKE}}= ({\mathsf{Setup}},{\mathsf{Gen}}, {\mathsf{Enc}}, {\mathsf{Dec}})$² is SIM-Bi-SO-CCA secure, if for any PPT adversary $\mathcal {A}$, there exists a PPT simulator $\mathcal {S}$, such that for any PPT distinguisher $\mathcal {D}$,

$$\begin{aligned} \mathtt {Adv}_{{\mathsf{PKE}}, \mathcal {A},\mathcal {S},\mathcal {D}}^{{\mathrm{SIM\hbox {-}Bi\hbox {-}SO\hbox {-}CCA}}}(\lambda ):= & {} |\Pr [\mathcal {D}(\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A}}^{\mathrm{Bi\hbox {-}SO\hbox {-}real}}(\lambda ))=1]\\&~~~~~~~~~~-\Pr [\mathcal {D}(\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {S}}^{\mathrm{Bi\hbox {-}SO\hbox {-}ideal}}(\lambda ))=1]| \end{aligned}$$

is negligible, where both $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A}}^{\mathrm{Bi\hbox {-}SO\hbox {-}real}}(\lambda )$ and $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {S}}^{\mathrm{Bi\hbox {-}SO\hbox {-}ideal}}(\lambda )$ are defined in Fig. 1.

Fig. 1.

Experiments for defining SIM-Bi-SO-CCA security of PKE. In these two experiments, we require that $\mathcal {I}_S\subset \{(i,j)\mid i\in [n], j\in [|\mathbf{m} _i|]\}$ and $\mathcal {I}_R\subset [n]$.

Note that in the real experiment, the total number of public keys and the times that each public key is used for encryption are completely determined by the adversary.

Remark 1

One can generalize both SIM-Bi-SO-CCA and SIM-wBi-$\text {SO}_{k}$-CCA security to a new version that the adversary is allowed to make multiple selective opening queries adaptively. We stress that all the PKE constructions presented in this paper also achieve the generalized security.

Simulation-based weak Bi-SO security. Now we introduce a weak model of SIM-Bi-SO-CCA security, which we denote as SIM-wBi-$\text {SO}_k$-CCA security ($k\in \mathbb {N}$). The differences between these two security models are that in the real experiment of SIM-wBi-$\text {SO}_k$-CCA security: (i) the adversary has to specify whether it is going to corrupt some fraction of the senders or the receivers, before seeing the challenge ciphertexts; (ii) if the adversary chooses to corrupt some fraction of the receivers, it is just allowed to corrupt the receivers whose public keys are used for encryption at most k times. The formal definition is as follows.

Definition 6

(SIM-wBi-SO$_{\boldsymbol{k}}$ -CCA). For any $k\in \mathbb {N}$, we say that a PKE scheme ${\mathsf{PKE}}= ({\mathsf{Setup}},{\mathsf{Gen}}, {\mathsf{Enc}}, {\mathsf{Dec}})$ is $\mathrm{SIM\hbox {-}wBi\hbox {-}SO}_{k}\mathrm{\hbox {-}CCA}$ secure, if for any PPT adversary $\mathcal {A}$, there exists a PPT simulator $\mathcal {S}$, such that for any PPT distinguisher $\mathcal {D}$,

$$\begin{aligned} \mathtt {Adv}_{{\mathsf{PKE}}, \mathcal {A},\mathcal {S},\mathcal {D}}^{\mathrm{SIM\hbox {-}Bi\hbox {-}SO\hbox {-}CCA}}(\lambda ):= & {} |\Pr [\mathcal {D}(\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A}}^{\mathrm{Bi\hbox {-}SO\hbox {-}real}}(\lambda ))=1]\\&~~~~~~~~~~-\Pr [\mathcal {D}(\mathtt {Exp}_{\mathsf{PKE}, \mathcal {S}}^{\mathrm{Bi\hbox {-}SO\hbox {-}ideal}}(\lambda ))=1]| \end{aligned}$$

is negligible, where both $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}real}}}(\lambda )$ and $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {S},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}ideal}}}(\lambda )$ are defined in Fig. 2.

Fig. 2.

Experiments for defining SIM-wBi-$\text {SO}_{k}$-CCA security. Here in both $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}real}}}(\lambda )$ and $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {S},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}ideal}}}(\lambda )$, we require that (i) $\beta \in \{0,1\}$, and (ii) when $\beta =0$, $\mathcal {I}\subset \{(i,j)\mid i\in [n], j\in [|\mathbf{m} _i|]\}$, and when $\beta =1$, $\mathcal {I}\subset \{i\in [n]\mid |\mathbf{m} _{i}|\le k\}$.

In both $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}real}}}(\lambda )$ and $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {S},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}ideal}}}(\lambda )$, we use $\beta =0$ (resp. $\beta =1$) to represent that adversary $\mathcal {A}$/simulator $\mathcal {S}$ chooses to corrupt some of the senders (resp. receivers). We stress that in $\mathtt {Exp}_{{\mathsf{PKE}}, \mathcal {A},k}^{{\mathrm{wBi\hbox {-}SO\hbox {-}real}}}(\lambda )$, when $\mathcal {A}_1$ outputs $\beta =0$, the parameter k puts no restrictions on sender corruptions $\mathcal {I}$; and when $\mathcal {A}_1$ outputs $\beta =1$, $\mathcal {A}_2$ is allowed to corrupt the receivers whose public keys are used for encryption at most k times (i.e., $\mathcal {I}\subset \{i\in [n]\mid |\mathbf{m} _i|\le k\}$).

Note that the original SIM-SSO-CCA security [9, 13] and SIM-RSO-CCA security [11, 19] are both special cases of SIM-wBi-$\text {SO}_{k}$-CCA security. Specifically, the original SIM-SSO-CCA security is SIM-wBi-$\text {SO}_{k}$-CCA security when $\mathcal {A}_1$ always outputs $\beta =0$ and queries the $\mathtt {MkRec}$ oracle only once,³ and the original SIM-RSO-CCA security is SIM-wBi-$\text {SO}_{k}$-CCA security when $\mathcal {A}_1$ always outputs $\beta =1$ and $|\mathbf{m} _1|=\cdots =|\mathbf{m} _n|=1$ (note that the latter implicitly suggests $k=1$). Hence, for a SIM-wBi-$\text {SO}_{k}$-CCA secure PKE scheme, it achieves the original SIM-SSO-CCA and SIM-RSO-CCA (and even SIM-$\text {RSO}_k$-CCA) security simultaneously.

Very recently, Yang et al. [32] introduced an enhanced security notion of RSO, SIM-$\text {RSO}_k$-CCA security ($k\in \mathbb {N}$), for PKE. We notice that their SIM-$\text {RSO}_k$-CCA security is a special case of SIM-wBi-$\text {SO}_{k}$-CCA security as well. Specifically, SIM-$\text {RSO}_k$-CCA security is SIM-wBi-$\text {SO}_{k}$-CCA security when $\mathcal {A}_1$ always outputs $\beta =1$.

3.2 Separation of SIM-wBi-$\text {SO}_{k}$-CCA and SIM-SSO-CCA and SIM-RSO-CCA

Now we show that SIM-wBi-$\text {SO}_{k}$-CCA security is strictly stronger than SIM-SSO-CCA security and SIM-RSO-CCA security. Our conclusion is derived from the fact that SIM-wBi-$\text {SO}_{k}$-CCA security implies SIM-SSO-CCA and SIM-RSO-CCA security simultaneously, and SIM-SSO-CCA and SIM-RSO-CCA security do not imply each other. Actually, we have stronger conclusions:

• (1) Supposing that the $\kappa$-Linear assumption holds ($\kappa \in \mathbb {N}$), SIM-SSO-CCA security does not imply SIM-RSO-CPA security;

• (2) Supposing that the DDH or DCR assumption holds, SIM-RSO-CCA security does not imply SIM-SSO-CPA security.

SIM-SSO-CCA $\nRightarrow$ SIM-RSO-CPA. Bellare et al. [2] introduced the notion of decryption verifiability for PKE, and showed that assuming the existence of a family of collision-resistant hash functions, which can be constructed under the discrete-logarithm assumption [10], any decryption-verifiable PKE scheme is not SIM-RSO-CPA secure [2, Theorem 5.1]⁴.

Informally, a PKE scheme ${\mathsf{PKE}}= ({\mathsf{Setup}},{\mathsf{Gen}}, {\mathsf{Enc}}, {\mathsf{Dec}})$ is called decryption-verifiable, if it is infeasible to generate $(pk,sk_0,sk_1,c,m_0,m_1)$ such that (i) $m_0\ne m_1$, (ii) both $sk_0$ and $sk_1$ are valid secret keys corresponding to pk, and (iii) $\textsf {Dec}(sk_0,c)=m_0$ and $\textsf {Dec}(sk_1,c)=m_1$. We note that (i) and (iii) implicitly suggest that $sk_0\ne sk_1$. In other words, for any PKE scheme, if each of its public key uniquely determines its corresponding secret key, then it must be decryption-verifiable.

We notice that the $\kappa$-Linear-based SIM-SSO-CCA secure PKE scheme proposed by Liu and Paterson [26] is such a decryption-verifiable PKE scheme. Generally, a public key of the $\kappa$-Linear-based Liu-Paterson scheme is of the form $(g^y,(g^{x_\theta },g^{x_\theta \alpha _\theta },g^{x_\theta \beta _\theta })_{\theta \in [\kappa ]})$, where g is a generator of a cyclic group $\mathbb {G}$ of prime order q and $(y,(x_\theta ,\alpha _\theta ,\beta _\theta )_{\theta \in [\kappa ]})\in (\mathbb {Z}_q)^{3\kappa +1}$, and the corresponding secret key is $(\alpha _\theta ,\beta _\theta ,x_\theta ^{-1}y)_{\theta \in [\kappa ]}$. It’s obvious that the public key uniquely determines its corresponding secret key. So the $\kappa$-Linear-based Liu-Paterson scheme is decryption-verifiable. According to [2, Theorem 5.1], we conclude that assuming the existence of a family of collision-resistant hash functions, the $\kappa$-Linear-based Liu-Paterson scheme is not SIM-RSO-CPA secure.

For completeness, we recall the formal definition of decryption verifiability [2] and the $\kappa$-Linear-based Liu-Paterson scheme [26] in the full version of this paper.

SIM-RSO-CCA $\nRightarrow$ SIM-SSO-CPA. As pointed out in [2, Theorem 4.1], the DDH-based Cramer-Shoup scheme [7] is not SIM-SSO-CPA secure. On the other hand, Huang et al. [19] and Hara et al. [11] showed that this PKE scheme (for single-bit message) achieves SIM-RSO-CCA security. This fact suggests that when the DDH assumption holds, SIM-RSO-CCA security does not imply SIM-SSO-CPA security. With similar analysis, this conclusion can be extended to the case that the DCR assumption holds.

4 PKE with SIM-wBi-$\text {SO}_{k}$-CCA Security

In this section, we propose a PKE scheme achieving SIM-wBi-$\text {SO}_{k}$-CCA security. We firstly introduce a new primitive, universal$_{\kappa }$ HPS with key equivocability for any polynomially bounded function $\kappa$, and provide concrete constructions for it from the DDH assumption and the DCR assumption respectively. Then, with this new primitive as a building block, we show our PKE construction and prove that it meets SIM-wBi-$\text {SO}_{k}$-CCA security in the standard model.

In order to make our idea more understandable, we firstly provide a technique overview before going into the details.

4.1 Technique Overview

In the real experiment of SIM-wBi-$\text {SO}_{k}$-CCA security, the bit $\beta$ is used to indicate whether the adversary wants to corrupt some fraction of the senders ($\beta =0$) or the receivers ($\beta =1$), and the adversary does not specify the value of $\beta$ until it sees public keys $(pk_i)_{i\in [n]}$ via querying the oracle $\mathtt {MkRec}$. Hence, to prove SIM-wBi-$\text {SO}_{k}$-CCA security, when $\beta =0$, we need to somehow generate malformed ciphertexts for $(pk_i)_{i\in [n]}$, such that they can be opened in the sense of SSO (i.e., exposing the messages and the corresponding randomness to the adversary); and when $\beta =1$, we need to somehow generate malformed ciphertexts for $(pk_i)_{i\in [n]}$, such that they can be opened in the sense of RSO (i.e., exposing the messages and the corresponding secret keys to the adversary).

Our scheme, encrypting $\ell$-bit messages, is inspired by the works of [9, 20, 24]. The public/secret key pair is $\ell$ pairs of public and secret keys (i.e., $(hpk_\gamma ,hsk_{\gamma })_{\gamma \in [\ell ]}$) of a hash proof system (HPS) HPS [8]. Informally, to encrypt a message $m=(m_1,\cdots ,m_{\ell })\in \{0,1\}^{\ell }$, the encryption algorithm sets that for each $\gamma \in [\ell ]$,

$$\begin{aligned} {\left\{ \begin{array}{ll} \text {If}~m_{\gamma }=0: ~x_{\gamma }\leftarrow \mathcal {X};~K_{\gamma }\leftarrow \mathcal {K}_{sp}\\ \text {If}~m_{\gamma }=1: ~x_{\gamma }\leftarrow \mathcal {L};~K_{\gamma }=\textsf {PubEv}(hpk_{\gamma },x_{\gamma },w_{\gamma }) \end{array}\right. } \end{aligned}$$

where $\mathcal {L}\subset \mathcal {X}$ and $\mathcal {X}$ are both finite sets generated with a hard subset membership problem, $\textsf {PubEv}$ is the public evaluation algorithm of HPS, $w_{\gamma }$ is a witness for $x_{\gamma }\in \mathcal {L}$, and $\mathcal {K}_{sp}$ is the range of $\textsf {PubEv}$. Then, we use a strengthened cross-authentication code (XAC) to “glue” $x_1,\cdots ,x_\ell$ together, obtaining a XAC tag T. So the generated ciphertext corresponding to m is $c=(x_1,\cdots ,x_\ell ,T)$. To decrypt a ciphertext $c=(x_1,\cdots ,x_\ell ,T)$, the decryption algorithm firstly computes that $(\overline{K}_\gamma =\textsf {SecEv}(hsk_\gamma ,x_\gamma ))_{\gamma \in [\ell ]}$, where $\textsf {SecEv}$ is the secret evaluation algorithm of HPS, and then for each $\gamma \in [\ell ]$, sets $\overline{m}_{\gamma }=1$ if and only if T is verified correctly by $\overline{K}_\gamma$ (via the verification algorithm of XAC).

Now we turn to the security proof. In order to prove SIM-wBi-$\text {SO}_{k}$-CCA security, we need to construct a PPT simulator $\mathcal {S}$, such that the ideal experiment and the real experiment are indistinguishable. In particular, we need to generate some malformed ciphertexts (before seeing the real messages), such that they are computationally indistinguishable from the real challenge ciphertexts, and meanwhile can be efficiently opened according to the value of $\beta$.

$\underline{\mathbf {If}\, \boldsymbol{\beta =0}{} \mathbf , }$ we need to generate malformed ciphertexts $c=(x_1,\cdots ,x_\ell ,T)$, and then open them according to the real messages $m=(m_1,\cdots ,m_\ell )$, by providing random coins which can be used to encrypt the real messages to recover the malformed ciphertexts. We generate the malformed ciphertexts with encryptions of $\ell$ ones, i.e., for each $\gamma \in [\ell ]$, $x_{\gamma }\leftarrow \mathcal {L}\subset \mathcal {X}$ and $K_{\gamma }=\textsf {PubEv}(hpk_{\gamma },x_{\gamma },w_{\gamma })\subset \mathcal {K}_{sp}$. Hence, after generating these malformed ciphertexts, to open a ciphertext, for each $\gamma \in [\ell ]$, if the real message bit $m_\gamma =1$, the random coin (i.e., $w_\gamma$) employed to generate $(x_\gamma ,K_\gamma )$ can be returned directly; if $m_\gamma =0$, return the random coin which is generated by explaining $x_\gamma$ as a random element sampled from $\mathcal {X}$, and explaining $K_\gamma$ as a random key sampled from $\mathcal {K}_{sp}$.

Now, we show that a real challenge ciphertext can be substituted with the malformed ciphertext without changing the adversary’s view significantly. For $\gamma =1$ to $\ell$,

• 1) We modify the decryption procedure of the decryption oracle, such that it does not make use of $hsk_\gamma$. More specifically, for a decryption query $c'=(x'_1,\cdots ,x'_\ell ,T')$, if $x'_\gamma \notin \mathcal {L}$, the decryption oracle directly sets $\overline{m}_\gamma =0$. The statistical properties of HPS and strengthened XAC guarantee that this modification does not change the adversary’s view significantly.

• 2) If $m_\gamma =0$, the randomly sampled $K_\gamma$ is replaced with $K_\gamma =\textsf {SecEv}(hsk_\gamma ,x_\gamma )$. The perfect universality of HPS guarantees that this change is imperceptible to the adversary.

• 3) If $m_\gamma =0$, $K_\gamma$ is updated again via the resampling algorithm of strengthened XAC. The statistical property of strengthened XAC guarantees that this modification does not change the adversary’s view significantly.

• 4) The decryption procedure of the decryption oracle is changed to work with the original decryption rules. The statistical properties of HPS and strengthened XAC guarantee that this modification is imperceptible to the adversary.

• 5) If $m_\gamma =0$, $x_\gamma \leftarrow \mathcal {L}$ instead of uniformly sampling from $\mathcal {X}$. The underlying subset membership problem of HPS guarantees that this change is also imperceptible to the adversary.

Note that these substitutions only consider the situation that a single public key is used to encrypt a single message. Fortunately, we can extend it to the situation that there are n public keys (for any $n\in \mathbb {N}$), and each public key is employed to encrypt multiple messages.

$\underline{\mathbf {If} \, \boldsymbol{\beta =1}{} \mathbf , }$ we need to generate malformed ciphertexts, and then open them according to the real messages, by providing valid secret keys which can be used to decrypt the malformed ciphertexts to obtain the messages. Note that a public key of this scheme is of the form $pk=(hpk_1,\cdots ,hpk_\ell )$, and the corresponding secret key is $sk=(hsk_1,\cdots ,hsk_\ell )$. Hence, informally, what we need is to generate a malformed ciphertext without seeing the message, such that for any message $m=(m_1,\cdots ,m_\ell )\in \{0,1\}^{\ell }$, we can generate some secret key $sk'=(hsk'_1,\cdots ,hsk'_\ell )$ satisfying that (i) $sk'$ is a valid secret key corresponding to pk (i.e., for all $\gamma \in [\ell ]$, $hsk'_\gamma$ is a valid HPS secret key corresponding to $hpk_\gamma$); (ii) decrypting the malformed ciphertext with $sk'$ will lead to m.

We try to generate such a malformed ciphertext $c=(x_1,\cdots ,x_\ell , T)$. For each $\gamma \in [\ell ]$, if $x_\gamma \in \mathcal {L}$ (with a witness $w_\gamma$), all the HPS secret keys corresponding to $hpk_\gamma$ will lead to the same $\widetilde{K}_\gamma =\textsf {PubEv}(hpk_\gamma ,x_\gamma ,w_\gamma )=K_\gamma$. In other words, for any fixed ciphertext $(\cdots ,x_\gamma ,\cdots ,T)$, no matter what the secret key is, the decryption of this ciphertext will lead to the same $\overline{m}_\gamma$. So it’s impossible to open the malformed ciphertext successfully when $m_\gamma =1-\overline{m}_\gamma$. Hence, our malformed ciphertexts focus on the case $c=(x_1,\cdots ,x_\ell , T)$ that $x_1,\cdots ,x_\ell \in \mathcal {X}\setminus \mathcal {L}$. On the other hand, if $K_\gamma$ is uniformly sampled, it seems unlikely to decrypt the ciphertext to recover the original message when $m_\gamma =1$ due to the property of XAC. So our malformed ciphertexts further focus on the case $c=(x_1,\cdots ,x_\ell , T)$ that for all $\gamma \in [\ell ]$, $x_\gamma \in \mathcal {X}\setminus \mathcal {L}$ and $K_\gamma =\textsf {SecEv}(hsk_\gamma ,x_\gamma )$.

We stress that in the real experiment of SIM-wBi-$\text {SO}_k$-CCA security, the adversary is just allowed to corrupt the receivers whose public keys are used for encryption at most k times. So for simplicity, here we only consider the case that $pk=(hpk_1,\cdots ,hpk_\ell )$ is used to encrypt exactly k messages (i.e., $m_j=(m_{j,1},\cdots ,m_{j,\ell })\in \{0,1\}^{\ell }$ ($j\in [k]$)). More specifically, for each $\gamma \in [\ell ]$, $hsk_\gamma$ is used k times (note that we use sk to generate the malformed ciphertexts), generating k ciphertext parts (i.e., $K_{1,\gamma }=\textsf {SecEv}(hsk_\gamma ,x_{1,\gamma }),\cdots ,K_{k,\gamma }=\textsf {SecEv}(hsk_\gamma ,x_{k,\gamma })$). In other words, to generate the k malformed ciphertexts, for each $\gamma \in [\ell ]$, we need to

• (i) compute $\textsf {SecEv}(hsk_\gamma ,x_{1,\gamma }),\cdots ,\textsf {SecEv}(hsk_\gamma ,x_{k,\gamma })$ for some $x_{1,\gamma },\cdots ,x_{k,\gamma }\in \mathcal {X}\setminus \mathcal {L}$ before seeing the messages;

• (ii) generate a HPS secret key $hsk'_\gamma$ such that $\textsf {SecEv}(hsk'_\gamma ,x_{j,\gamma })=\textsf {SecEv}(hsk_\gamma ,x_{j,\gamma })$ if $m_{j,\gamma }=1$, and $\textsf {SecEv}(hsk'_\gamma ,x_{j,\gamma })\ne \textsf {SecEv}(hsk_\gamma ,x_{j,\gamma })$ if $m_{j,\gamma }=0$.

However, there is no algorithm for HPS which can generate two HPS secret keys (i.e. $hsk_\gamma$ and $hsk'_\gamma$) meeting the above requirements. Therefore, we introduce the following new property, which we call “key equivocability”, of HPS. Informally, we require that there is an efficient algorithm SampHsk and a trapdoor $\mathsf {td}$, such that for any $x_{1},\cdots ,x_{k}\in \mathcal {X}\setminus \mathcal {L}$, the following two distribution ensembles, $\textsf {Dist}^k_0$ and $\textsf {Dist}^k_1$, are statistically indistinguishable:

$$\begin{aligned} \textsf {Dist}^k_0:= & {} \{(hsk,K_1,\cdots ,K_k,hpk)\big |hsk\leftarrow \mathcal {SK}; ~hpk=\mu (hsk);\nonumber \\&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \forall j\in [k]:\nonumber \\&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ K_j \leftarrow \mathcal {K}_{sp} \quad \text {if } m_j=0; \nonumber \\&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ K_j = \textsf {SecEv}(hsk,x_j) \quad \text {if } m_j=1 \},~~~~\end{aligned}$$

(1)

$$\begin{aligned} \textsf {Dist}^k_1:= & {} \{(hsk',K_1,\cdots ,K_k,hpk)\big |hsk\leftarrow \mathcal {SK}; ~hpk=\mu (hsk);\nonumber \\&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(K_j=\textsf {SecEv}(hsk,x_j))_{j\in [k]};\nonumber \\&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~hsk'\leftarrow \textsf {SampHsk}(hsk,\mathsf {td},\{x_j\}_{j\in [k]})\}. \end{aligned}$$

(2)

We stress that this property requires that no information about hsk beyond hpk is leaked. Similar to the proof of case $\beta =0$, we introduce a modification to the decryption oracle before employing the key equivocability of HPS in order to make sure that nothing about hsk beyond hpk is leaked. For any decryption query $(x'_1,\cdots ,x'_\ell , T')$ and any $\gamma$, if $x'_\gamma \in \mathcal {X}\setminus \mathcal {L}$, the decryption oracle sets $\overline{m}_{\gamma }=0$ directly. However, we note that in the SIM-wBi-$\text {SO}_{k}$-CCA security model, each public key is used to encrypt k messages. As a result, hsk may be employed k times, i.e., to compute $\textsf {SecEv}(hsk,x_1),\cdots ,\textsf {SecEv}(hsk,x_k)$ for some $x_1,\cdots ,x_k$. So the perfect $\text {universality}_2$ of HPS [8] is not enough to guarantee that the modification to the decryption oracle is imperceptible to the adversary. To solve this problem, we introduce another property, perfect $universality_{k+1}$, for HPS. Roughly speaking, HPS is called perfectly $\text {universal}_{k+1}$, if for any $x_1,\cdots ,x_{k+1}\in \mathcal {X}\setminus \mathcal {L}$ and any $K'\in \mathcal {K}_{sp}$, even given $(hpk, \textsf {SecEv}(hsk,x_1), \cdots , \textsf {SecEv}(hsk,x_k))$, the probability that $\textsf {SecEv}(hsk,x_{k+1})=K'$ is $\frac{1}{|\mathcal {K}_{sp}|}$.

With the help of this new variant of HPS, we can use algorithm $\textsf {SampHsk}$ to open the aforementioned equivocable ciphertexts $c=(x_1,\cdots ,x_\ell , T)$ where for each $\gamma \in [\ell ]$, $x_\gamma \in \mathcal {X}\setminus \mathcal {L}$ and $K_\gamma =\textsf {SecEv}(hsk_\gamma ,x_\gamma )$, successfully. Now, we show that a real challenge ciphertext can be substituted with the malformed ciphertext without changing the adversary’s view significantly. A high-level description of the substitution is presented as follows.

• 1) We use the secret keys to generate the challenge ciphertexts, instead of the public keys. The statistical property of HPS guarantees that this change is imperceptible to the adversary.

• 2) All the $x_{j,\gamma }$ ($j\in [k],\gamma \in [\ell ]$) are sampled from $\mathcal {X}\setminus \mathcal {L}$, instead of being sampled from $\mathcal {L}$ (when $m_{j,\gamma }=1$). The underlying subset membership problem of HPS guarantees that this change is also imperceptible to the adversary.

• 3) Note that $sk=(hsk_1,\cdots ,hsk_\ell )$ is employed to encrypt $m_j=(m_{j,1},\cdots ,m_{j,\ell })\in \{0,1\}^{\ell }$ ($j\in [k]$), and specifically, for each $\gamma \in [\ell ]$, $hsk_{\gamma }$ is used to handle $m_{1,\gamma },\cdots ,m_{k,\gamma }$, as shown in Fig. 3. For each $\gamma \in [\ell ]$, employ $hsk_\gamma$ to compute $K_{j,\gamma }$ when $m_{j,\gamma }=0$ (for all $j\in [k]$). The key equivocability of HPS guarantees that this modification does not change the adversary’s view significantly.

Fig. 3.

Relations among sk and $m_{1},\cdots ,m_{k}$

4.2 Universal$_\kappa$ Hash Proof System with Key Equivocability

Now we introduce the main building block, namely, universal$_{\kappa }$ HPS with key equivocability, for any polynomially bounded $\kappa$, and show concrete constructions for it.

The definition. For any polynomially bounded function $\kappa$, we provide a definition of universal$_\kappa$ HPS with key equivocability, which enhances the standard HPS [8] with key equivocability and universal$_{\kappa }$ property. It works on a strengthened version of subset membership problem ${\mathsf{SSMP}}$, which defines some additional languages and provides a trapdoor to recognize elements from these languages.

Definition 7

(Strengthened Subset Membership Problem). A strengthened subset membership problem (SSMP) ${\mathsf{SSMP}}$ consists of five PPT algorithms $({\mathsf{SSmpG}}, {\mathsf{SSmpX}}, {\mathsf{SSmpL}},{\mathsf{SSmpLS}},{\mathsf{SSmpChk}})$:

• SSmpG$(1^\lambda ,k)$ : On input $1^\lambda$ and polynomially bounded $k>0$, algorithm SSmpG outputs a system parameter ${\mathsf{prm}}$ and a trapdoor $\mathsf {td}$. The parameter ${\mathsf{prm}}$ defines $2k+2$ sets $(\mathcal {X}, \mathcal {L}, \mathcal {L}_{1},\cdots , \mathcal {L}_{2k})$, where $\mathcal {X}$ is an efficiently recognizable finite set, $\mathcal {L}\subset \mathcal {X}$, and $\mathcal {L}_{1},\cdots , \mathcal {L}_{2k}$ are distinct subsets of $\mathcal {X}\setminus \mathcal {L}$. For simplicity of notation, we write

  $${\mathsf{prm}}=(\mathcal {X},\mathcal {L}, \mathcal {L}_1, \ldots , \mathcal {L}_{2k})$$

  when employing ${\mathsf{HPS}}$ for ${\mathsf{SSMP}}$ to construct PKE schemes.

• SSmpX(prm): On input ${\mathsf{prm}}$, SSmpX outputs a uniformly chosen $x{\leftarrow }\mathcal {X}$.

• SSmpL(prm): On input ${\mathsf{prm}}$, SSmpL samples $x{\leftarrow }\mathcal {L}$ with randomness $w\in \mathcal {R}_{{\mathsf{SSmpL}}}$, and outputs (x, w). We say that w is a witness for $x\in \mathcal {L}$.

• SSmpLS$({\mathsf{prm}},i\in [2k])$ : On input ${\mathsf{prm}}$ and $i\in [2k]$, SSmpLS outputs a uniformly chosen $x_i{\leftarrow }\mathcal {L}_i$.

• SSmpChk$({\mathsf{prm}},\mathsf {td},x)$ : On input ${\mathsf{prm}}$, $\mathsf {td}$ and x, SSmpChk outputs an integer [0, 2k] or an abort symbol $\perp$.

Also, it satisfies the following properties:

• Hardness. For all $i\in [2k]$, for any PPT distinguisher $\mathcal {D}$, the following advantages are all negligible,

  $${\mathtt {Adv}}^{{\mathrm{HARD\hbox {-}1}}}_{{\mathsf{SSMP}}, \mathcal {D}, i}(\lambda ):=|{\mathrm{Pr}}[\mathcal {D}({\mathsf{prm}},x_{\mathcal {X}})=1]- {\mathrm{Pr}}[\mathcal {D}({\mathsf{prm}},x_i)=1]|,$$
  $${\mathtt {Adv}}^{{\mathrm{HARD\hbox {-}2}}}_{{\mathsf{SSMP}}, \mathcal {D}, i}(\lambda ):=|{\mathrm{Pr}}[\mathcal {D}({\mathsf{prm}},x_{\mathcal {L}})=1]- {\mathrm{Pr}}[\mathcal {D}({\mathsf{prm}},x_i)=1]|,$$

  where the probabilities are over ${\mathsf{prm}}\leftarrow {\mathsf{SSmpG}}(1^\lambda ,k)$, $x_{\mathcal {X}}\leftarrow {\mathsf{SSmpX}}({\mathsf{prm}})$, $(x_{\mathcal {L}},w)\leftarrow {\mathsf{SSmpL}}({\mathsf{prm}})$, and $x_{i}\leftarrow {\mathsf{SSmpLS}}({\mathsf{prm}},i)$.⁵

• Sparseness. The probability

  $${\mathtt {Spar}}_{{\mathsf{SSMP}}}(\lambda ):={\mathrm{Pr}}[({\mathsf{prm}},\mathsf {td})\leftarrow {\mathsf{SSmpG}}(1^\lambda ,k); x_{\mathcal {X}}\leftarrow {\mathsf{SampX}}({\mathsf{prm}}): x_{\mathcal {X}}\in \mathcal {L}]$$

  is negligible.

• Explainability. The finite set $\mathcal {X}$ is an efficiently samplable and explainable domain (as defined in Definition 2).

• Sampling Correctness. Let $({\mathsf{prm}},\mathsf {td}) \leftarrow \mathsf {SSmpG}(1^{\lambda },k)$. Then the distributions of the outputs of $\mathsf {SSmpX}(\mathsf {prm})$, $\mathsf {SSmpL}(\mathsf {prm})$, and $\mathsf {SSmpLS}(\mathsf {prm},i)$ ($i\in [2k]$) are statistically indistinguishable from uniform distributions over $\mathcal {X}$, $\mathcal {L}$ and $\mathcal {L}_i$ ($i\in [2k]$) respectively.

• Checking Correctness. For any $({\mathsf{prm}},\mathsf {td})$ generated by SSmpG, if $x\in \mathcal {L}$, then ${\mathsf{SSmpChk}}({\mathsf{prm}},\mathsf {td},x)=0$; if there exists $i\in [2k]$ s.t. $x\in \mathcal {L}_i$, then ${\mathsf{SSmpChk}}({\mathsf{prm}},\mathsf {td},x)=i$; otherwise, ${\mathsf{SSmpChk}}({\mathsf{prm}},\mathsf {td},x)=\perp$.

Remark 2

The additional trapdoor, generated by SSmpG, will also be used in the key equivocability property (see Definition 10) of HPS.

Definition 8

(Hash Proof System [8]). A hash proof system ${\mathsf{HPS}}$ for a SSMP SSMP consists of three PPT algorithms $({\mathsf{PrmG}},$ ${\mathsf{PubEv}},$ ${\mathsf{SecEv}})$:

• PrmG$({\mathsf{prm}})$ : Given ${\mathsf{prm}}$, which is generated by ${\mathsf{SSmpG}}(1^{\lambda },k)$ and defines $2k+2$ sets $(\mathcal {X},\mathcal {L}, \mathcal {L}_1, \ldots , \mathcal {L}_{2k})$, algorithm PrmG outputs a parameterized instance ${\mathsf{prmins}} :=(\mathcal {K}_{sp}, \mathcal {SK}, \mathcal {PK}, \varLambda _{(\cdot )}, \mu )$, where $\mathcal {K}_{sp},$ $\mathcal {SK},$ $\mathcal {PK}$ are all finite sets, $\varLambda _{(\cdot )}: \mathcal {X}\rightarrow \mathcal {K}_{sp}$ is a family of hash functions indexed with secret hash key $hsk\in \mathcal {SK}$, and $\mu :\mathcal {SK}\rightarrow \mathcal {PK}$ is an efficiently computable function.

• SecEv(hsk, x): On input $hsk\in \mathcal {SK}$ and $x\in \mathcal {X}$, the deterministic secret evaluation algorithm SecEv outputs a hash value $K=\varLambda _{hsk}(x)\in \mathcal {K}_{sp}$.

• PubEv(hpk, x, w): On input $hpk=\mu (hsk)\in \mathcal {PK}$, $x\in \mathcal {L}$ and a witness w for $x\in \mathcal {L}$, the deterministic public evaluation algorithm PubEv outputs a hash value $K=\varLambda _{hsk}(x)\in \mathcal {K}_{sp}$.

Also, it should be

• Projective. For any $hsk\in \mathcal {SK}$ and any $x\in \mathcal {L}$ with witness w, the hash value $\varLambda _{hsk}(x)$ is uniquely determined by $hpk=\mu (hsk)$ and x, concretely, we require that ${\mathsf{SecEv}}(hsk,x)={\mathsf{PubEv}}(hpk,x,w)$.

• Perfectly Universal. For all ${\mathsf{prm}}$ generated by ${\mathsf{SSmpG}}(1^\lambda )$, all possible ${\mathsf{prmins}}\leftarrow {\mathsf{PrmG}}({\mathsf{prm}})$, all $hpk\in \mathcal {PK}$, all $x\in \mathcal {X}\setminus \mathcal {L}$, and all $K\in \mathcal {K}_{sp}$, the probability ${\mathrm{Pr}}[\varLambda _{hsk}(x)=K \mid \mu (hsk)=hpk]= \frac{1}{\mathcal {K}_{sp}}$, where the probability is over $hsk\leftarrow \mathcal {SK}$.

Definition 8 is the same as the original definition of HPS in [8]. In our PKE construction, we further require that $\mathcal {K}_{sp}$ is efficiently samplable and explainable. Besides, we require $\mathsf {HPS}$ to have the following two properties.

Definition 9

(Perfectly Universal$_{\kappa }$). For any polynomial $\kappa$, we say that ${\mathsf{HPS}}$ is perfectly universal$_{\kappa }$, if for all ${\mathsf{prm}}$ generated by ${\mathsf{SSmpG}}(1^\lambda ,k)$, all possible ${\mathsf{prmins}}\leftarrow {\mathsf{PrmG}}({\mathsf{prm}})$, all $hpk\in \mathcal {PK}$, all pairwise different $x_1,\cdots ,x_{\kappa }\in \mathcal {X}\setminus \mathcal {L}$, and all $K_1,\cdots ,K_{\kappa }\in \mathcal {K}_{sp}$,

$$\begin{aligned} \begin{array}{r@{~}l} \Pr \left[ \varLambda _{hsk}(x_{\kappa })=K_{\kappa } \bigg | \begin{array}{c} \mu (hsk)=hpk \\ \varLambda _{hsk}(x_1)=K_1,\cdots ,\varLambda _{hsk}(x_{\kappa -1})=K_{\kappa -1} \end{array}\right] =\frac{1}{|\mathcal {K}_{sp}|},\nonumber \end{array} \end{aligned}$$

where the probability is over $hsk\leftarrow \mathcal {SK}$.

Definition 10

(Key Equivocability). We say that ${\mathsf{HPS}}$ is key equivocable, if there is a PPT algorithm ${\mathsf{SampHsk}}$, which takes $(hsk,\mathsf {td},x_1,\cdots ,x_{2k})$ as input and outputs another secret key $hsk'$, such that for all possible $({\mathsf{prm}},\mathsf {td})\leftarrow {\mathsf{SSmpG}}(1^\lambda ,k)$, all possible ${\mathsf{prmins}}=(\mathcal {K}_{sp},\mathcal {SK},\mathcal {PK}, \varLambda _{(\cdot )}, \mu ) \leftarrow {\mathsf{PrmG}}({\mathsf{prm}})$, all permutations $\mathsf {P}: [2k] \rightarrow [2k]$, and all $(x_1,\cdots ,x_{2k})\in \mathcal {X}^{2k}$ satisfying that $x_i \in \mathcal {L}_{\mathsf {P}(i)}$, $\varDelta ({\mathsf{Dist}}_0,{\mathsf{Dist}}_1)$ is negligible, where ${\mathsf{Dist}}_0$ and ${\mathsf{Dist}}_1$ are defined in Fig. 4.

Fig. 4.

Distributions for defining key equivocability of HPS.

Instantiation from DDH. Now we present our instantiation of universal${_{\kappa }}$ HPS with key equivocability from the DDH assumption. The definition of the DDH assumption will be recalled in Appendix A.

Let $\lambda$ be the security parameter and let $k,\kappa$ be positive integers that are polynomial in $\lambda$. Let $\mathbb {G}$ be a multiplicative cyclic group of prime order q and let g be a generator of $\mathbb {G}$. Let $\varGamma : \mathbb {G}^{2k+1} \rightarrow \mathbb {Z}^{2k+1}_q$ be an injective function, which can be extended from the injective function in the constructions of HPS in [8] directly.

We construct a strengthened subset membership problem $\mathsf {SSMP}_{1}=(\mathsf {SSmpG}, \mathsf {SSmpX}, \mathsf {SSmpL}, \mathsf {SSmpLS}, \mathsf {SSmpChk})$ as follows:

• $\mathsf {SSmpG}$. On input a security parameter $\lambda$ and an integer k, the parameter generation algorithm first samples $a_i {\leftarrow }\mathbb {Z}_q$ and computes $g_i=g^{a_i}$ for $i\in [2k+1]$. Then it sets:

  $$ \mathcal {X}=\{u_1, \ldots , u_{2k+1} \mid \forall i\in [2k+1], u_i \in \mathbb {G}\} $$
  $$ \mathcal {L}=\{g_1^{w}, \ldots , g_{2k+1}^{w} \mid w \in \mathbb {Z}_q \} $$

  and for $i\in [2k]$, it sets:

  $$\begin{aligned} \mathcal {L}_i=&\{g_1^{w_1}, \ldots , g_{2k+1}^{w_{2k+1}} \mid w,w' \in \mathbb {Z}_q, w\not =w', \\&\qquad \qquad \qquad \qquad \quad w_i=w', \forall j \in [2k+1]\backslash \{i\}, w_j = w \} \end{aligned}$$

  The public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$ and the trapdoor $\mathsf {td}=(a_1, \ldots , a_{2k+1})$

• $\mathsf {SSmpX}$. On input a public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$, the algorithm samples $u_i {\leftarrow }\mathbb {G}$ for $i\in [2k+1]$ and outputs $x=(u_1, \ldots , u_{2k+1})$.

• $\mathsf {SSmpL}$. On input a public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$, the algorithm samples $w {\leftarrow }\mathbb {Z}_q$ and outputs $x=(g_1^w, \ldots , g_{2k+1}^w)$ and the witness w.

• $\mathsf {SSmpLS}$. On input a public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$ and an integer $i\in [2k]$, the algorithm samples $w {\leftarrow }\mathbb {Z}_q$ and $w' {\leftarrow }\mathbb {Z}_q$ s.t. $w\not =w'$. Then it computes $u_j=g^{w}_j$ for $j\in [2k+1]\backslash \{i\}$ and $u_i=g^{w'}_i$ and outputs $(u_1, \ldots , u_{2k+1})$.

• $\mathsf {SSmpChk}$. On input a public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$, a trapdoor $\mathsf {td}=(a_1, \ldots , a_{2k+1})$, and $x=(u_1, \ldots , u_{2k+1})$, the algorithm first computes $v_j=u_j^{a_j^{-1}}$ for $j\in [2k+1]$. It outputs 0 if $v_1 = v_2 = \ldots =v_{2k+1}$. It outputs j if there exists some $j\in [2k]$ s.t. $v_{\jmath }=v_{\jmath '}$ for all $\jmath ,\jmath ' \in [2k] \backslash \{j\}$ and $v_j\not =v_{2k+1}$. Otherwise, it outputs $\perp$.

Also, we construct the HPS $\mathsf {HPS}_{1}=(\mathsf {PrmG},\mathsf {PubEv},\mathsf {SecEv},\mathsf {SampHsk})$ for $\mathsf {SSMP}_{1}$ as follows:

• $\mathsf {PrmG}$. On input a public parameter $\mathsf {prm}=(\mathbb {G},q,g,g_1,\ldots ,g_{2k+1})$, the algorithm defines $\mathcal {K}_{sp}=\mathbb {G}$, $\mathcal {SK}=\mathbb {Z}^{(2k+1) \times \kappa \times (2k+1)}_q$, and $\mathcal {PK}=\mathbb {G}^{(2k+1) \times \kappa }$.

  Then for any $hsk=(s_{h,i,j})_{h\in [2k+1], i\in [\kappa ], j \in [2k+1]} \in \mathcal {SK}$ and any $x=(u_1, \ldots , u_{2k+1}) \in \mathcal {X}$, it defines the map $\varLambda$ from $\mathcal {SK} \times \mathcal {X}$ to $\mathcal {K}_{sp}$ as

  $$ \varLambda _{hsk}(x)= \prod _{h\in [2k+1],i\in [\kappa ],j\in [2k+1]} u_j^{s_{h,i,j} \cdot \alpha _h^{i-1}} $$

  where $(\alpha _1, \ldots , \alpha _{2k+1}) = \varGamma (x)$. Also, for any $hsk=(s_{h,i,j})_{h\in [2k+1],}{i\in [\kappa ],j\in [2k+1]} \in \mathcal {SK}$, it defines the map $\mu$ from $\mathcal {SK}$ to $\mathcal {PK}$ as

  $$ \mu (hsk)=(p_{h,i})_{h\in [2k+1],i\in [\kappa ]}=(\prod _{j\in [2k+1]} g_j^{s_{h,i,j}})_{h\in [2k+1],i\in [\kappa ]} $$

• $\mathsf {SecEv}$. On input a secret key $hsk=(s_{h,i,j})_{h\in [2k+1],i\in [\kappa ],j\in [2k+1]} \in \mathcal {SK}$ and $x=(u_1, \ldots , u_{2k+1}) \in \mathcal {X}$, the secret evaluation algorithm outputs $K=\varLambda _{hsk}(x)$.

• $\mathsf {PubEv}$. On input a public key $hpk= (p_{h,i})_{h\in [2k+1],i\in [\kappa ]} \in \mathcal {PK}$, $x=(u_1, \ldots , u_{2k+1}) \in \mathcal {L}$ and a witness w, the public evaluation algorithm computes $(\alpha _1, \ldots , \alpha _{2k+1})=\varGamma (x)$ and outputs $K=\prod _{h\in [2k+1],i\in [\kappa ]} p_{h,i}^{w \cdot \alpha _h^{i-1}}$.

• $\mathsf {SampHsk}$. On input a secret key $hsk=(s_{h,i,j})_{h\in [2k+1],i\in [\kappa ],j\in [2k+1]}$, a trapdoor $\mathsf {td}=(a_1, \ldots , a_{2k+1})$, and 2k inputs $(x_{\ell }=(u_{\ell ,1}, \ldots , u_{\ell ,2k+1}))_{\ell \in [2k]}$, the algorithm works as follows:

  • 1. For $\ell \in [2k]$, it computes $\boldsymbol{p}[\ell ]=\mathsf {SSmpChk}(\mathsf {prm},\mathsf {td},x_{\ell })$.

  • 2. It outputs $\perp$ if there exists $\ell \in [2k]$ s.t. $\boldsymbol{p}[\ell ] \not \in [2k]$ or there exist distinct $\ell _1,\ell _2\in [2k]$ s.t. $\boldsymbol{p}[\ell _1]=\boldsymbol{p}[\ell _2]$.

  • 3. For $h\in [2k+1],i\in [\kappa ],j\in \{\boldsymbol{p}[1], \ldots , \boldsymbol{p}[k]\}$, it sets $s'_{h,i,j}=s_{h,i,j}$.

  • 4. For $h\in [2k+1],i\in [\kappa ],j\in \{\boldsymbol{p}[k+1], \ldots , \boldsymbol{p}[2k]\}$, it samples $s'_{h,i,j} {\leftarrow }\mathbb {Z}_q$.

  • 5. For $h\in [2k+1],i\in [\kappa ]$, it sets $s'_{h,i,2k+1}=(\sum _{j\in [2k+1]} a_j s_{h,i,j} - \sum _{j\in [2k]} a_j s'_{h,i,j}) \cdot a_{2k+1}^{-1}$.

  • 6. It outputs $hsk'=(s'_{h,i,j})_{h\in [2k+1],i\in [\kappa ],j\in [2k+1]}$.

Theorem 1

Assuming the DDH assumption holds, $\mathsf {SSMP}_{1}$ is a strengthened subset membership problem with hardness, sparseness, explainability, and correctness.

Theorem 2

$\mathsf {HPS}_{1}$ is a perfect universal$_\kappa$ HPS with key equivocability.

Proofs of Theorem 1 and Theorem 2 are provided in the full version.

Instantiation from DCR. We present our instantiation of universal${_{\kappa }}$ HPS with key equivocability from the DCR assumption as follows. The definition of the DCR assumption will be recalled in Appendix A.

Let $\lambda$ be the security parameter and let $k,\kappa$ be positive integers that are polynomial in $\lambda$. We construct a strengthened subset membership problem $\mathsf {SSMP}_{2}=(\mathsf {SSmpG}, \mathsf {SSmpX}, \mathsf {SSmpL}, \mathsf {SSmpLS}, \mathsf {SSmpChk})$ as follows:

• $\mathsf {SSmpG}$. On input a security parameter $\lambda$ and an integer k, the parameter generation algorithm first samples primes $p',q',p,q$ s.t. $p=2p'+1$ and $q=2q'+1$. Then it computes $N=pq$ and $N'=p'q'$. Let $\mathbb {Z}^*_{N^2} = \mathbb {G}_{N} \cdot \mathbb {G}_{N'} \cdot \mathbb {G}_2 \cdot \mathbb {T}$, where $\mathbb {G}_{N}, \mathbb {G}_{N'}, \mathbb {G}_2, \mathbb {T}$ are defined as in Appendix A. Define $\mathbb {X}=\mathbb {G}_N \cdot \mathbb {G}_{N'} \cdot \mathbb {T}$ and $\mathbb {L} = \mathbb {G}_{N'} \cdot \mathbb {T}$. Define $\chi : \mathbb {Z}_{N^2} \rightarrow \mathbb {Z}_N$ as $\chi (a)=\lfloor a/N \rfloor$. Let $\varGamma : \mathbb {X}^{2k} \rightarrow \mathbb {Z}^{2k}_{\lfloor N^2/2 \rfloor }$ be an injective function, which can be extended from the injective function in the constructions of HPS in [8] directly. Also, let $g \in \mathbb {Z}^{*}_{N^2}$ be a fixed generator of $\mathbb {L}$.

  Then it sets:

  $$ \mathcal {X}=\{u_1, \ldots , u_{2k} \mid \forall j\in [2k], u_{j} \in \mathbb {X}\}, $$
  $$ \mathcal {L}=\{g^{r_{1}}, \ldots , g^{r_{2k}} \mid \forall j\in [2k], r_{j} \in \mathbb {Z}_{2N'}\}, $$

  and for $i\in [2k]$, it sets:

  $$ \mathcal {L}_i=\{u_1, \ldots u_{2k} \mid u_i \in \mathbb {X}\backslash \mathbb {L}, \forall j\in [2k]\backslash \{i\}, r_{j} \in \mathbb {Z}_{2N'}, u_j=g^{r_j}\}. $$

  The public parameter $\mathsf {prm}=(N,g)$ and the trapdoor $\mathsf {td}=N'$.

• $\mathsf {SSmpX}$. On input a public parameter $\mathsf {prm}=(N,g)$, the algorithm samples $u_j {\leftarrow }\mathbb {X}$ for $j\in [2k]$ and outputs $x=(u_1, \ldots , u_{2k})$.

• $\mathsf {SSmpL}$. On input a public parameter $\mathsf {prm}=(N,g)$, the algorithm samples $r_j {\leftarrow }\mathbb {Z}_{\lfloor N/2 \rfloor }$ for $j\in [2k]$ and outputs $x=(g^{r_1}, \ldots , g^{r_{2k}})$ and the witness $(r_1, \ldots , r_{2k})$.

• $\mathsf {SSmpLS}$. On input a public parameter $\mathsf {prm}=(N,g)$ and an integer $i\in [2k]$, the algorithm samples $r_j {\leftarrow }\mathbb {Z}_{\lfloor N/2 \rfloor }$ for $j\in [2k]\backslash \{i\}$ and $u_i {\leftarrow }\mathbb {X}$. Then it computes $u_j=g^{r_{j}}$ for $j\in [2k]\backslash \{i\}$ and outputs $x=(u_1, \ldots , u_{2k})$.

• $\mathsf {SSmpChk}$. On input a public parameter $\mathsf {prm}=(N,g)$, a trapdoor $\mathsf {td}=N'$, and $x=(u_1, \ldots , u_{2k})$, the algorithm first computes $v_j=u_j^{2N'}$ for $j\in [2k]$. It outputs 0 if $v_1 = v_2 = \ldots v_{2k} = 1$. It outputs j if there exists $j\in [2k]$ s.t. $v_{\jmath }=1$ for all $\jmath \in [2k] \backslash \{j\}$ and $v_j \not = 1$. Otherwise, it outputs $\perp$.

Also, we construct the HPS $\mathsf {HPS}_{2}=(\mathsf {PrmG}, \mathsf {PubEv}, \mathsf {SecEv}, \mathsf {SampHsk})$ for $\mathsf {SSMP}_{2}$ as follows:

• $\mathsf {PrmG}$. On input a public parameter $\mathsf {prm}=(N,g)$, the algorithm defines $\mathcal {K}_{SP}=\mathbb {Z}_N$, $\mathcal {SK}=\mathbb {Z}^{(2k) \times (\kappa ) \times (2k)}_{\lfloor N^2/2 \rfloor }$, and $\mathcal {PK}=\mathbb {L}^{(2k) \times (\kappa ) \times (2k)}$. Then for any $hsk=(s_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]} \in \mathcal {SK}$ and any $x=(u_1, \ldots , u_{2k}) \in \mathcal {X}$, it defines the map $\varLambda$ from $\mathcal {SK} \times \mathcal {X}$ to $\mathcal {K}_{sp}$ as

  $$ \varLambda _{hsk}(x)= \chi ( \prod _{h\in [2k],i\in [\kappa ],j\in [2k]} u_j^{s_{h,i,j} \cdot \alpha _h^{i-1}} ) $$

  where $(\alpha _1, \ldots , \alpha _{2k}) = \varGamma (x)$. Also, for any $hsk=(s_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]} \in \mathcal {SK}$, it defines the map $\mu$ from $\mathcal {SK}$ to $\mathcal {PK}$ as

  $$ \mu (sk)=(p_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]}=(g^{s_{h,i,j}})_{h\in [2k],i\in [\kappa ],j\in [2k]}. $$

• $\mathsf {SecEv}$. On input a secret key $hsk=(s_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]} \in \mathcal {SK}$ and $x=(u_1, \ldots , u_{2k}) \in \mathcal {X}$, the secret evaluation algorithm outputs $K=\varLambda _{hsk}(x)$.

• $\mathsf {PubEv}$. On input a public key $hpk= (p_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]} \in \mathcal {PK}$, $x=(u_1, \ldots , u_{2k}) \in \mathcal {L}$ and a witness $(r_1, \ldots , r_{2k})$, the public evaluation algorithm computes $(\alpha _1, \ldots , \alpha _{2k})=\varGamma (x)$ and outputs $K= \chi (\prod _{h\in [2k],i\in [\kappa ],j\in [2k]} p_{h,i,j}^{r_j \cdot \alpha _h^{i-1}} )$.

• $\mathsf {SampHsk}$. On input a secret key $hsk=(s_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]}$, a trapdoor $\mathsf {td}=N'$, and 2k inputs $(x_{\ell }=(u_{\ell ,1}, \ldots , u_{\ell ,2k}))_{\ell \in [2k]}$, the algorithm works as follows:

  • 1. For $\ell \in [2k]$, it computes $\boldsymbol{p}[\ell ]=\mathsf {SSmpChk}(\mathsf {prm},\mathsf {td},x_{\ell })$.

  • 2. It outputs $\perp$ if there exists $\ell \in [2k]$ s.t. $\boldsymbol{p}[\ell ] \not \in [2k]$ or there exist distinct $\ell _1,\ell _2\in [2k]$ s.t. $\boldsymbol{p}[\ell _1]=\boldsymbol{p}[\ell _2]$.

  • 3. For $h\in [2k],i\in [\kappa ],j\in \{\boldsymbol{p}[1], \ldots , \boldsymbol{p}[k]\}$, it sets $s'_{h,i,j}=s_{h,i,j}$.

  • 4. For $h\in [2k],i\in [\kappa ],j\in \{\boldsymbol{p}[k+1], \ldots , \boldsymbol{p}[2k]\}$, it samples $t {\leftarrow }\mathbb {Z}_N$ and uses the Chinese remainder theorem to compute $s'_{h,i,j} \in \mathbb {Z}_{2NN'}$ s.t. $s'_{h,i,j}=t \mod N$ and $s'_{h,i,j}=s_{h,i,j} \mod 2N'$.

  • 5. It outputs $hsk'=(s'_{h,i,j})_{h\in [2k],i\in [\kappa ],j\in [2k]}$.

Theorem 3

Assuming the DCR assumption holds, $\mathsf {SSMP}_{2}$ is a strengthened subset membership problem with hardness, sparseness, explainability, and correctness.

Theorem 4

$\mathsf {HPS}_{2}$ is a perfect universal$_\kappa$ HPS with key equivocability.

Proofs of Theorem 3 and Theorem 4 are similar to proofs of Theorem 1 and Theorem 2. So, we omit the details here. Note that $\mathsf {SSMP}_{2}$ only achieves a statistical sampling correctness while $\mathsf {SSMP}_{1}$ achieves a perfect sampling correctness.

4.3 SIM-wBi-$\text {SO}_{k}$-CCA Secure PKE Construction

For any polynomially bounded function $k>0$, we propose a PKE scheme achieving SIM-wBi-$\text {SO}_{k}$-CCA security. Our construction is built from a perfectly $\text {universal}_{k+1}$ HPS with key-equivocability, and a strong and semi-unique XAC. The details are as follows.

Let $\textsf {SSMP}=({\mathsf{SSmpG}}, {\mathsf{SSmpX}},{\mathsf{SSmpL}}, \textsf {SSmpLS},\textsf {SSmpChk})$ be a hard SSMP. Let $\textsf {HPS}=({\mathsf{PrmG}}, {\mathsf{PubEv}}, {\mathsf{SecEv}}, \textsf {SampHsk})$ be a perfectly $\text {universal}_{k+1}$ and key equivocable HPS for SSMP, such that all the $\mathcal {K}_{sp}$ generated by PrmG can be written as $\mathcal {K}_a\times \mathcal {K}_b$. For $\ell \in \mathbb {N}$ and any ${\mathsf{prmins}}=(\mathcal {K}_{sp}, \mathcal {SK},\mathcal {PK},\varLambda _{(\cdot )}, \mu )$ generated by PrmG, let $\textsf {XAC}_{\textsf {prmins}}=({\mathsf{XGen}}, {\mathsf{XAuth}},$ ${\mathsf{XVer}}, \textsf {ReSamp})$ be a strong and semi-unique $(\ell +1)$-XAC with key space $\mathcal {XK}=\mathcal {K}_{sp}=\mathcal {K}_a\times \mathcal {K}_b$ and tag space $\mathcal {XT}$, and $\mathcal {H}_{\textsf {prmins}}:(\mathcal {X}\times \mathcal {PK})^{\ell }\rightarrow \mathcal {K}_b$ be a family of collision-resistant hash functions. Our PKE scheme $\textsf {PKE}=(\textsf {Setup}, \textsf {Gen},\textsf {Enc},\textsf {Dec})$ (for $\ell$-bit messages) is defined in Fig. 5.

Fig. 5.

Construction of $\textsf {PKE}$.

Correctness. For $\gamma \in [\ell ]$, if $m_{\gamma }=1$, then $\overline{K}_{\gamma }=K_{\gamma }$ by completeness of HPS, so $\overline{m}_\gamma =\textsf {Xver}(\overline{K}_{\gamma },\gamma ,T)=1$ except with probability $\textsf {fail}_{\textsf {XAC}}(\lambda )$ by correctness of XAC. On the other hand, if $m_{\gamma }=0$, subset sparseness of SSMP and perfect universality of HPS guarantee that with overwhelming probability, $\overline{K}_{\gamma }$ is uniformly random, even given pk, c and m. In this case, $\overline{m}_\gamma =\textsf {XVer}(\overline{K}_{\gamma },T)=0$ except with probability $\mathtt {Adv}_{{\mathsf{XAC}}}^{{\mathrm{IMP}}}(\lambda )$. So, correctness of PKE follows by a union bound over $\gamma \in [\ell ]$.

Security. Formally, we have the following theorem, the formal proof of which is provided in the full version.

Theorem 5

For any polynomial function $k>0$, ${\mathsf{PKE}}$ is SIM-wBi-$\text {SO}_{k}$-CCA secure.

5 PKE with SIM-Bi-SO-CCA Security

In [14], Heuer et al. showed that a generic construction of DHIES [31] meets SIM-SSO-CCA security in the random oracle model. In this section, we show that a variant of the generic construction actually achieves SIM-Bi-SO-CCA security in the random oracle model.

Building blocks. We simply recall the definitions of key encapsulation mechanism (KEM) and message authentication code (MAC) as follows.

Key Encapsulation Mechanism. A KEM scheme, associated with a session key space $\mathcal {K}_{\textsf {KEM}}$ and a ciphertext space $\mathcal {C}_{\textsf {KEM}}$, is a tuple of PPT algorithms $\textsf {KEM}=({\mathsf{KemGen}}, {\mathsf{Encap}},{\mathsf{Decap}})$. The key generation algorithm KemGen takes $1^\lambda$ as input, and outputs a public/secret key pair (pk, sk). The encapsulation algorithm Encap takes pk as input, outputs $(K,c)\in \mathcal {K}_{\textsf {KEM}}\times \mathcal {C}_{\textsf {KEM}}$. The decapsulation algorithm Decap, taking sk and c as input, outputs a value in $\mathcal {K}_{\textsf {KEM}}\cup \{\bot \}$. Standard correctness is required. Similar to [14], without loss of generality we assume that ${\mathsf{Encap}}$ uniformly samples $K\leftarrow \mathcal {K}_{\textsf {KEM}}$. We also assume that $|\mathcal {K}_{\textsf {KEM}}|\ge 2^{\lambda }$ and $|\mathcal {C}_{\textsf {KEM}}|\ge 2^{\lambda }$.

We say that KEM has unique encapsulations, if for any (pk, sk) generated by KemGen, and for any ciphertexts $c,c'$ satisfying $\textsf {Decap}(sk,c)=\textsf {Decap}(sk,c')\ne \bot$, $c=c'$.

The security notion, one-way security in the presence of a plaintext-checking oracle (OW-PCA security) [28], is recalled in the full version.

Message Authentication Code. A MAC scheme, associated with a key space $\mathcal {K}_{\textsf {MAC}}$, is a tuple of PPT algorithms $\textsf {MAC}=({\mathsf{MacGen}}, {\mathsf{Auth}}, {\mathsf{Verf}})$. The key generation algorithm MacGen takes $1^\lambda$ as input and outputs a key $K\in \mathcal {K}_{\textsf {MAC}}$. The authentication algorithm Auth takes K and a message m as input, outputs a tag t. On input (K, m, t), the verification algorithm Verf outputs a bit $b'\in \{0,1\}$. Standard correctness is also required here.

MAC is called deterministic, if Auth is deterministic. For a deterministic MAC, MAC is called injective, if Auth is an injective function (i.e., for any $K\in \mathcal {K}_{\textsf {MAC}}$ and any $m\ne m'$, ${\mathsf{Auth}}(K,m)\ne {\mathsf{Auth}}(K,m')$).

The security notion of strong unforgeability under one-time chosen message attacks (sUF-OT-CMA security) is recalled in the full version.

PKE Construction. Let ${\mathsf{KEM}}= ({\mathsf{KemGen}}, {\mathsf{Encap}}, {\mathsf{Decap}})$ be an OW-PCA secure KEM scheme, having unique encapsulations, associated with a session key space $\mathcal {K}_{\textsf {KEM}}$ and a ciphertext space $\mathcal {C}_{\textsf {KEM}}$, where Encap uniformly samples K, $|\mathcal {K}_{\textsf {KEM}}|\ge 2^\lambda$ and $|\mathcal {C}_{\textsf {KEM}}|\ge 2^\lambda$. Let ${\mathsf{MAC}}= ({\mathsf{MacGen}}, {\mathsf{Auth}}, {\mathsf{Verf}})$ be a deterministic, injective MAC scheme, associated with a key space $\mathcal {K}_{\textsf {MAC}}$, achieving sUF-OT-CMA security. Let $\textsf {H}_{\text {RO}}:\mathcal {K}_{\textsf {KEM}}\rightarrow \{0,1\}^{\ell }\times \mathcal {K}_{\textsf {MAC}}$ be a hash function. Our PKE scheme $\textsf {PKE}_{\mathsf{K\hbox {-}M}}=(\textsf {Setup}, \textsf {Gen}, \textsf {Enc}, \textsf {Dec})$, associated with a message space $\{0,1\}^{\ell }$, is defined in Fig. 6.

Fig. 6.

Construction of $\textsf {PKE}_{\mathsf{K\hbox {-}M}}$.

The correctness analysis of this scheme is trivial. Now we turn to its security analysis. Formally, we have the following theorem. Note that, in our construction, a valid ciphertext contains a tag t generated on $(pk^{kem},c^{kem},c^{sym})$, where in [14], the tag t is only generated on $c^{sym}$. We stress that this crucial modification makes our construction achieve SIM-Bi-SO-CCA security. The intuition for the security proof and details are provided in the full version.

Theorem 6

If ${\mathsf{KEM}}$ has unique encapsulations and is OW-PCA secure, ${\mathsf{MAC}}$ is deterministic, injective and sUF-OT-CMA secure, and ${\mathsf{H}}_{{\mathrm{RO}}}$ is modeled as a random oracle, then ${\mathsf{PKE}}_{{\mathsf{K\hbox {-}M}}}$ is SIM-Bi-SO-CCA secure in the random oracle model.

A Cryptographic Assumptions

The DDH Assumption. Let $\mathbb {G}$ be a cyclic group of prime order q with a generator g. The DDH assumption requires that it is hard to distinguish $(g^a,g^b,g^c)$ and $(g^a,g^b,g^{ab})$, where $a,b,c {\leftarrow }\mathbb {Z}_q$.

The DCR Assumption. Now, we recall the Decision Composite Residuosity (DCR) assumption [30] and some useful facts about it shown in [8].

Let $p,q,p',q'$ be primes such that $p=2p'+1$ and $q=2q'+1$. Let $N=pq$ and $N'=p'q'$. Then the group $\mathbb {Z}^*_{N^2}$ can be decomposed as the direct product $\mathbb {G}_N \cdot \mathbb {G}_{N'} \cdot \mathbb {G}_2 \cdot \mathbb {T}$, where $\mathbb {G}_{N'}$ and $\mathbb {G}_2$ are cyclic groups of order $N'$ and order 2 respectively; $\mathbb {G}_N$ is a cyclic group of order N generated by $\xi =(1+N) \mod N^2$; and $\mathbb {T}$ is the order-2 subgroup of $\mathbb {Z}^*_{N^2}$ generated by $(-1 \mod N^2)$. Note that $\xi ^a = (1+aN) \mod N^2$ for $a\in \{0,1,\cdots ,N\}$.

The DCR assumption requires that it is hard to distinguish a random element in $\mathbb {Z}^*_{N^2}$ and a random element in $\mathbb {G}_{N'} \cdot \mathbb {G}_2 \cdot \mathbb {T}$.

Next, define $\mathbb {X}=\mathbb {G}_N \cdot \mathbb {G}_{N'} \cdot \mathbb {T}$. The set $\mathbb {X}$ is an efficiently samplable and explainable domain, where the sample algorithm and the explain algorithm work as follows:

• Sample: The sample algorithm proceeds as follows:

  • 1. For $i\in [1,160]$:

    • (a) $x{\leftarrow }\mathbb {Z}_{N^2}$

    • (b) If the Jacobi symbol $(\frac{x}{N}) = 1$: output x.

  • 2. Output $\perp$.

• Explain: on input an element $x \in \mathbb {X}$, the explain algorithm proceeds as follows:

  • 1. Set $\mathsf {r}$ to be an empty string.

  • 2. For $i\in [1,160]$:

    • (a) Sample $b{\leftarrow }\{0,1\}$.

    • (b) If $b=1$, append x to $\mathsf {r}$ and outputs $\mathsf {r}$.

    • (c) Otherwise, sample an element $x'{\leftarrow }\mathbb {Z}_{N^2}$ s.t. the Jacobi symbol $(\frac{x'}{N})=-1$ and append $x'$ to $\mathsf {r}$.

  • 3. Output $\perp$.

Note that as $\frac{|\mathbb {X} |}{|\mathbb {Z}^*_{N^2} |}=1/2$, the expected repetition in the sample algorithm is about 2 and the probability that the sample algorithm outputs $\perp$ is $\frac{1}{2^{160}}$, which is negligible. Also, it is easy to see the probability that the explain algorithm outputs $\perp$ is also $\frac{1}{2^{160}}$, which is negligible.

Also, define $\chi : \mathbb {Z}_{N^2} \rightarrow \mathbb {Z}_N$ as $\chi (a)=\lfloor a/N \rfloor$. For any fixed $x\in \mathbb {X}$, $\chi (x \xi ^c)$ is uniform in $\mathbb {Z}_N$ if $c {\leftarrow }\mathbb {Z}_N$.

Finally, define $\mathbb {L}=\mathbb {G}_{N'} \cdot \mathbb {T}$. It is easy to create a generator g for $\mathbb {L}$ by first sampling a random element $\mu \in \mathbb {Z}^*_{N^2}$ and then computing $g=-\mu ^{2N}$. Besides, the DCR assumption implies that a random element in $\mathbb {X}$ is computationally indistinguishable from a random element in $\mathbb {L}$.