Public-Key Encryption with Selective Opening Security from General Assumptions

Abstract

In a selective opening (SO) attack, the attacker can corrupt a subset of senders (or receivers) to open some of the ciphertexts and try to learn information on the plaintexts of unopened ciphertexts. It is important and practical to consider SO attack in encryption scheme. In this paper we study public key encryption (PKE) schemes with SO security. Specifically:

• First, we define a new cryptographic primitive called tweaked lossy encryption, and we prove that it has simulation-based security against sender selective opening chosen plaintext attacks (denoted by SIM-SSO-CPA).

• Second, we provide a general construction of tweaked lossy encryption scheme from extractable ${\Sigma }$-protocol; and we propose two instantiations of tweaked lossy encryption, based on dual-mode commitments and Twin-Cramer-Shoup scheme respectively.

• Finally, we propose a general scheme satisfying indistinguishability-based security against receiver selective opening chosen plaintext attacks (denoted by IND-RSO-CPA), and we give a construction of the scheme from explainable hash proof systems (denoted by EHPS), and we provide the security analysis.

Our results provide a new insight about the relations among PKE schemes with SO security, extractable $\mathrm {\Sigma }$-protocol and explainable hash proof systems.

This work was supported in by the National Key Research and Development Program of China-the Key Technologies for High Security Mobile Terminals (Grant No. 2017YFB0801903).

1 Introduction

Sender Selective Opening Security. Sender selective opening (SSO) attacks are considered in public key encryption (PKE) schemes where an adversary may corrupt some of the senders to selectively open some of the ciphertexts. Specifically, an adversary may get a collection of some arbitrary challenge ciphertexts $\mathbf {c} = (c_1, \dots , c_N)$ of size N, and each ciphertext $c_i = \mathrm {Enc}_{pk}(m_i; r_i)$ is obtained by encrypting the message $m_i$ with a fresh randomness $r_i$ under a public key pk. The adversary may adaptively chooses a subset $I \subseteq [N]$ of ciphertexts to open, thus learning the messages $\{m_i\}_{i \in I}$ and the corresponding randomness $\{r_i\}_{i \in I}$, and then the adversary tries to break into the unopened ciphertexts $\{c_i\}_{i \in [N] \setminus I}$ and obtain additional information on the corresponding plaintexts. The SSO security of PKE schemes requires that the privacy of the unopened ciphertexts is perserved.

Several formal analysis [2, 4, 6, 15, 26, 27] indicated that SSO security definition is essentially stronger than traditional security definitions due to two added features. One is to enable partial revelation of the randomness, which allows the adversary to check the relation between ciphertexts and the corresponding messages. The other is that the adversary is allowed to open a selected subset of ciphertexts, which gives it more power to learn information on the plaintexts of unopened ciphertexts.

Bellare et al. [3] proposed two types of SSO security: indistinguishability-based selective opening (IND-SSO) security and simulation-based selective opening (SIM-SSO) security. IND-SSO security means that no adversary can distinguish between opened messages and unopened messages. It requires the distribution on the messages to be efficiently conditionally resamplable. SIM-SSO security is a stronger notion than IND-SSO security. In particular, SIM-SSO security requires that, a simulator that sees only the opened messages can simulate the output of any real adversary; and it has no restrictions on the message distribution. Unfortunately, SIM-SSO security is much harder to achieve than IND-SSO security [2], since for many natural encryption schemes, there exist no such simulator satisfying the definitions given in [3, 13].

Relations among IND-SSO, SIM-SSO and standard security definitions have been discussed in many literatures such as in [2, 4, 15, 19, 26, 27]. Encryption schemes with IND-SSO security against chosen plaintext attack (IND-SSO-CPA) and SIM-SSO security against chosen plaintext attack (SIM-SSO-CPA) were first given in [3], based on lossy encryption [37, 38]. In particular, Bellare et al. proved that lossy encryption implies IND-SSO-CPA security, and lossy encryption with efficient opening implies SIM-SSO-CPA security [3]. Later, Hemenway et al. [20] proposed a general construction of lossy encryption from hash proof system (HPS). Following this research, Hofheinz et al. [25] showed that lossy encryption with efficient weak opening algorithm implies SIM-SSO-CPA security. Note that most of those constructions are based on non-interactive cryptographic primitives; however, the all-but-many encryption (ABME) scheme [16] is built on interactive cryptographic primitives - extractable ${\Sigma }$-protocol, which provides a new and meaningful insight to design SSO secure encryption and related schemes.

Selective Opening Security for the Receiver. Selective opening security for the receiver (RSO) is less studied than SSO security. In the RSO setting, one sender and n receivers hold public and secret keys that are generated independently. The attacker is allowed to learn the messages together with secret keys of a subset of the receivers by corrupting them. Security is requires that the privacy of the uncorrupted receivers is perserved.

There are also indistinguishability-based selective opening for receiver (IND-RSO) security and simulation-based selective opening for receiver (SIM-RSO) security [19]. Some formal arguments show that RSO secure scheme can be constructed from non-committing encryption (NCER) schemes [7, 11, 36], while there are a few constructions from standard assumptions. In [19], Hazay et al. introduced a tweaked variant of NCER which implies IND-RSO security against chosen plaintext attack (IND-RSO-CPA), and shows that tweaked NCER can be constructed from some standard primitives.

Related Work. Deniable encryption [6] and NCER [7] can also be used to construct SSO secure encryption scheme [14, 34]. In the indistinguishability-based chosen-ciphertext (IND-SSO-CCA) and simulation-based chosen ciphertext (SIM-SSO-CCA) scenarios, handling additional decryption queries makes it even more difficult to construct schemes with IND-SSO and SIM-SSO security. Several IND-SO-CCA secure schemes have been constructed by lossy trapdoor functions [38], such as all-but-N lossy trapdoor functions [20], and all-but-many lossy trapdoor functions [5, 24, 32]. And existing SIM-SSO-CCA secure constructions follow dedicated approaches [14, 24, 29, 34]. Heuer et al. [23] showed that if a PKE scheme consists of a key encapsulation mechanism (KEM) and a blockcipher-based data encapsulation mechanism (DEM), and the DEM is simulatable, then the PKE scheme is SIM-SO-CCA secure. For sender security, Heuer et al. [21, 22] showed that some practical schemes, such as RSA-OAEP and DHIES, are SIM-SSO-CCA secure in the random oracle model. For receiver security, IND-RSO-CCA and SIM-RSO-CCA secure constructions were proposed in [18, 28, 30, 31].

1.1 Our Contribution

First, we define a new cryptographic primitive called tweaked lossy encryption, and we show that it is SIM-SSO-CPA secure. We remark that our construction is inspired by that of ABME given by Fujisaki [16], and by that of dual-mode commitments in [33], and by that of simulatable DEMs in [23], and by that of instance-dependent cryptographic primitives in [12, 35].

Second, we provide a general construction of tweaked lossy encryption based on extractable $\mathrm {\Sigma }$-protocol. Furthermore, we give two instantiations of the scheme based on two ways of constructing extractable $\mathrm {\Sigma }$-protocol, namely dual-mode commitments and Twin-Cramer-Shoup scheme. These instantiations are non-trivial, specifically, the property of efficient weak opening in lossy encryption is usually restricted to specific algebraic structures that are hard to obtain, so we need to limit the length of the plaintext to logarithmic length. While in a setting where extractable $\mathrm {\Sigma }$-protocols are executed in parallel, there may be multiple random challenges; and each of them can be associated with a plaintext, therefore it is possible to encrypt longer plaintexts by dividing them into multiple short plaintexts and encrypting each short plaintext in parallel.

Third, we provide an IND-RSO-CPA secure scheme from explainable hash proof systems (denoted by EHPS). In [19], Hazay et al. proved that secure tweaked NCER implies IND-RSO-CPA secure PKE, and HPS implies tweaked NCER. Compared with the construction in [19], our tweaked NCER scheme changes the opening algorithm in several ways: for the opening algorithm in [19], an unbounded algorithm can find an appropriate secret key by searching exhaustively without a trapdoor. In our opening algorithm, EHPS provide the trapdoor information, thus the secret key can be obtained in probabilistic polynomial time. Abdalla et al. [1] have shown that such EHPS can be constructed.

Organization. The rest of our paper is organized as follows: In Sect. 2 we present some basic notions and tools used; In Sect. 3 we define a new cryptographic primitive called tweaked lossy encryption and show that it is SIM-SSO-CPA secure; In Sect. 4 we describe a generic construction of tweaked lossy encryption scheme from extractable $\mathrm {\Sigma }$-protocol; In Sect. 5, we give two instantiations of tweaked lossy encryption; In Sect. 6, we give a construction of tweaked NCER from EHPS, and prove that it is IND-RSO-CPA secure.

2 Preliminaries

Notation. We use $\mathbb {N}$ to denote the set of natural numbers, and $\mathbb {Z}$ the set of integers. For $n \in \mathbb {N}$, [n] denotes the set $\{1, \dots , n\}$. The length of a string x is denoted by |x|. We abbreviate probabilistic polynomial-time and deterministic polynomial-time as PPT and DPT respectively. Let $x \leftarrow S$ denote the process of picking up x uniformly at random from a finite set S, or the process of sampling x according to a distribution S. Given a security parameter $\lambda$, a function $\mathrm {negl}(\lambda )$ is negligible for a sufficiently large $\lambda$.

Public Key Encryption. A PKE scheme consists of three PPT algorithms. The key generation algorithm $\mathrm {Gen}(1^{\lambda })$ takes a security parameter $\lambda$ as input, and outputs a public/secret key pair (pk, sk) where pk is a public key and sk is the secret key. The encryption algorithm $\mathrm {Enc}(pk, m; r)$ takes the public key pk, a message $m \in \mathcal {M}$ and randomness $r \in \mathcal {R}$ as inputs, and outputs a ciphertext c, denoted as $c = \mathrm {Enc}(pk, m; r)$. The decryption algorithm $\mathrm {Dec}(sk, c)$ takes the secret key sk, a ciphertext c as inputs, and outputs either a message m denoted as $m = \mathrm {Dec}(sk,c)$ or a special “$\bot$” indicating invalid ciphertext c. We say that a PKE scheme satisfies correctness, if $\mathrm {Dec}(sk, c) = m$ with all but negligible probability for all (pk, sk) produced by $\mathrm {Gen}(1^{\lambda })$ and all c produced by $\mathrm {Enc}(pk, m ; r)$.

Selective Opening Security. There are several different ways of formalizing SSO security. Following the approach of [4], we consider the definition of SIM-SSO-CPA security, which requires that the output of the adversary can be simulated by an efficient simulator without seeing neither the ciphertext nor the public key. To model adaptive corruptions, the definition provides an opening oracle $\mathcal {O}$ for the adversary and the simulator.

Definition 1

(SIM-SSO-CPA Security [3, 4]). A PKE scheme $\mathrm {PKE} = (\mathrm {Gen}, \mathrm {Enc},$ $\mathrm {Dec})$ is SIM-SSO-CPA secure iff for every polynomially bounded $n = n(1^{\lambda }) > 0$, and every stateful PPT adversary $\mathcal {A}$, there exists a stateful PPT simulator $\mathcal {S}$ such that

$$\begin{aligned} \mathrm {\mathbf {Adv}}^{\mathrm {sim}-\mathrm {sso}-\mathrm {cpa}}_{\mathrm {PKE}, \mathcal {A}, \mathcal {S}}(1^{\lambda }) = |\Pr [\mathrm {Exp}^{\mathrm {real}}_{\mathrm {PKE}, \mathcal {A}}(1^{\lambda }) = 1] -\Pr [\mathrm {Exp}^{\mathrm {ideal}}_{\mathcal {S}}(1^{\lambda }) = 1]| \end{aligned}$$

is negligible. The experiments $\mathrm {Exp}^{\mathrm {real}}_{\mathrm {PKE}, \mathcal {A}, Rel}$ and $\mathrm {Exp}^{\mathrm {ideal}}_{\mathcal {S}, Rel}$ are defined as following (Fig. 1):

Fig. 1.

The REAL-SIM-SSO-CPA and IDEAL-SIM-SSO-CPA experiments

Interactive Proof System. Let L be a NP language and R a binary relation. An interactive proof system [17] (P, V) for L is a pair of interactive machines, where the prover P is able to convince the verifier V of true statements $x \in L$, which is defined by a binary relation R such that $(x, w) \in R$; while nobody can fool V into believing false statements $x \notin L$. An interactive proof system is zero knowledge [17] if for every interactive machine $V^{*}$, there exists an expected probabilistic polynomial-time simulator $M^{*}$ that can simulate the entire interaction transcript between P and V without accessing P’s certificate information. $\mathrm {\Sigma }$-protocols are special cases of three-round honest verifier zero-knowledge proofs.

Definition 2

($\mathrm {\Sigma }$-protocol [10]). A three-round public-coin protocol $\varSigma$ $=$ $(P_1$, $P_2$, V) is a $\mathrm {\Sigma }$-protocol for a relation R, if it satisfies the following properties:

• Completeness: if honest P and V are given common input x and private input w for P, where $(x, w) \in R$, then V will always accept the transcripts.

• Special soundness: there exists a PPT algorithm that takes x and a pair of accepting transcripts (a, e, z) and $(a, e', z')$ for x as input, where $e \ne e'$, then it can efficiently compute w such that $(x, w) \in R$.

• Special honest verifier zero knowledge: there exists a PPT simulator upon input $x \in L$ and the challenge $e \in \{0, 1\}^n$, then outputs an accepting transcript of the form (a, e, z). Moreover, the distribution of the simulator’s output is computationally indistinguishable from that of a real execution between P and V on input x.

Extractable $\mathrm {\Sigma }$-protocol. The notion of extractable $\mathrm {\Sigma }$-protocol was proposed in [16]. The following definition essentially repeats the definition of extractable $\mathrm {\Sigma }$-protocol from [16], expect minor changes to fit our requirement. Let $L = \{L_{pk}\}_{pk}$ be a NP language composed of a series of sets $L_{pk}$ indexed by $pk \in \mathcal {PK}$, where $\mathcal {PK}$ is the space of pk. Let $R_{pk} = \{(x, w)\}$ be a polynomial-time binary relation related to $L_{pk}$. An extractable $\mathrm {\Sigma }$-protocol $\varSigma ^{\mathrm {ext}} = (\mathrm {P}^{\mathrm {com}}_{\varSigma }, \mathrm {P}^{\mathrm {ans}}_{\varSigma }, \mathrm {V}^{\mathrm {vrfy}}_{\varSigma }, \mathrm {simP}^{\mathrm {com}}_{\varSigma }, \mathrm {Ext})$ is defined as follows: PPT algorithm $\mathrm {P}^{\mathrm {com}}_{\varSigma }$ on input $(x, w) \in R_{pk}$ and a random coins $r_a$, then outputs a commitment $a = \mathrm {P}^{\mathrm {com}}_{\varSigma }(x, w; r_a)$. DPT algorithm $\mathrm {P}^{\mathrm {ans}}_{\varSigma }$ takes as input $(x, w, r_a, e)$ and outputs $z = \mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, e)$, where e is a challenge. DPT algorithm $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }$ verifies (x, a, e, z) and decide whether to accept or reject it. PPT algorithm $\mathrm {simP}^{\mathrm {com}}_{\varSigma }$ takes as input (x, e) and outputs $(a, e, z) = \mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, e; r_z)$. Similarly, $r_z$ is the random coins, and we additionally require that $r_z = z$, and this property can be satisfied by many sigma protocols. DPT algorithm $\mathrm {Ext}$ takes as input (sk, x, a) and outputs e or a special symbol $\bot$ indicating failure, where sk is a secret key corresponding to pk. A protocol $\varSigma ^{\mathrm {Ext}}$ is said to be an extractable $\mathrm {\Sigma }$-protocol on $L = \{L_{pk}\}_{pk}$ for relation $R_{pk}$, if for all pk, there is a set $L^{co}_{pk}$ such that $L_{pk} \cap L^{co}_{pk} = \emptyset$, and the following properties hold:

• Completeness: if P and V follow the protocol for common input x and private input w for P, then for every $(x, w) \in R_{pk}$ and every $r_a$ and e, the equation $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }(x$, $\mathrm {P}^{\mathrm {com}}_{\varSigma }$ $(x, w;$ $r_a)$, e, $\mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, e)$ $) = 1$ is always true.

• Special soundness: for every $x \notin L$ and every a, there exists exactly one e such that $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }(x, a, e, z) = 1$.

• Extractability: we say that $(pk, sk^{\mathrm {ext}}) \in R^{\mathrm {ext}}$ if there is $e' = \mathrm {Ext}(sk^{\mathrm {ext}}, x, a)$ which satisfies $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }(x, a, e', z) = 1$ for all $x \in L^{co}_{pk}$ and all a, so that the equation $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }(x, a, e, z) = 1$ holds for an existing pair (e, z). If for all $pk \in \mathcal {PK}$, there is a $sk^{\mathrm {ext}}$ that satisfies the relation $(pk, sk^{\mathrm {ext}}) \in R^{\mathrm {ext}}$, we say that $\varSigma ^{\mathrm {ext}}$ has the property of extractability on $\{L^{co}_{pk}\}_{pk}$. Combined with special soundness, for all $x \in L^{co}_{pk}$, all e and all z, we can get $e = \mathrm {Ext}(sk, x, \mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, e; z)_1)$, where $\mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, e; z)_1$ is the first output of $\mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, e; z)$.

• Enhanced Honest-Verifier Statistical Zero-Knowledge (eHVSZK): for every (pk, $sk^{\mathrm {ext}})$ $\in$ $R^{\mathrm {ext}}$, every $(x, w) \in R_{pk}$, and every challenge e, the following two ensembles are statistically indistinguishable:

  $$\begin{aligned} \{\mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, e; r_z)\} \approx _s \{(\mathrm {P}^{\mathrm {com}}_{\varSigma }(x, w; r_a), e, \mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, e))\} \end{aligned}$$

3 Selective Opening Security from Tweaked Lossy Encryption

In this section, we define a new cryptographic primitive called tweaked lossy encryption (tLPKE), then we show that tLPKE is SIM-SSO-CPA secure. We can think of tLPKE as a lightweight ABME [16].

Definition 3

(Tweaked Lossy Encryption). A tweaked lossy encryption scheme with message space $\mathcal {M}$ is a tuple of PPT algorithms such that:

• $\mathrm {Gen}(1^{\lambda })$$:$ take the security parameter $\lambda$ as input and output (pk, sk) where pk is the real public key and sk is the corresponding secret key.

• $\mathrm {LGen}(1^{\lambda })$$:$ take the security parameter $\lambda$ as input and output a key pair (pk, sk) where pk is the lossy public key and sk is the lossy secret key.

• $\mathrm {Enc}(pk, m; r)$$:$ take a real or lossy public key pk, a message $m \in \mathcal {M}$, and a random coin $r \in R_{\mathrm {Enc}}$ as inputs, output a ciphertext c.

• $\mathrm {Dec}(sk, c)$$:$ take a ciphertext c and a secret key sk as inputs, output either a message $m \in \mathcal {M}$ or a special symbol “$\bot$” indicating decryption failure.

• $\mathrm {Sim} = (\mathrm {Fake}, \mathrm {Open})$$:$ is a pair of PPT and DPT algorithms such that

  • $\mathrm {Fake}(pk, r')$$:$ take a lossy public key pk and a random coin $r' \leftarrow R_{\mathrm {Enc}}$ as inputs, output a fake ciphertext $e^{*}$ and an auxiliary parameter $\varepsilon$.

  • $\mathrm {Open}(\varepsilon , m)$$:$ take an auxiliary parameter $\varepsilon$ and a message $m \in \mathcal {M}$ as inputs, output a random coin $r \in R_{\mathrm {Enc}}$.

Furthermore, tLPKE satisfies the following properties:

• Correctness: for all $(pk, sk) \leftarrow \mathrm {Gen}(1^{\lambda })$, message $m \in \mathcal {M}$, $c \leftarrow \mathrm {Enc}(pk, m; r)$, it must satisfy $\mathrm {Dec}(sk, c) = m$.

• Key indistinguishability: for any PPT distinguisher D, there exists a negligible function $\mu (\cdot )$ such that

  $$\begin{aligned} \mathrm {Adv}^{\text{ ind-lossy-key }}_{\mathrm {tLPKE}, D} = \left| \begin{array}{ll} &{}{\Pr [D(pk, 1^{\lambda }) = 1|(pk, sk) \leftarrow \mathrm {Gen}(1^{\lambda })]-} \\ &{}{\Pr [D(pk, 1^{\lambda }) = 1|(pk, sk) \leftarrow \mathrm {LGen}(1^{\lambda })]} \\ \end{array} \right| \le \mu (\lambda ) \end{aligned}$$

• Simulatability: define the following variables:

  • $\mathrm {dist}^{\mathrm {Enc}}(pk, m)$ denotes the random variable (c, r), where $r \leftarrow R_{\mathrm {Enc}}$, $c = \mathrm {Enc}(pk, m; r)$ and pk is the lossy public key.

  • $\mathrm {dist}^{\mathrm {Sim}}(pk, m)$ denotes the random variable $(e^{*}, r)$, where $(e^{*}$, $\varepsilon )$ $\leftarrow$ $\mathrm {Fake}(pk, r')$ and pk is the lossy public key; $r' \leftarrow R_{\mathrm {Enc}}$; $r \leftarrow \mathrm {Open}(\varepsilon , m)$.

  Therefore the following ensembles are statistically indistinguishable:

  $$\begin{aligned} \{\mathrm {dist}^{\mathrm {Enc}}(pk, m)\} \approx _s \{\mathrm {dist}^{\mathrm {Sim}}(pk, m)\} \end{aligned}$$

Remarks. The recent work of Heuer et al. [23] defined a simulatability property that holds for DEM. Intuitively, the encapsulation algorithm could generate a ciphertext without seeing the corresponding message. Formally, they divided the encapsulation process into two parts in sequential order, Fake and Make. Firstly, Fake algorithm outputs a ciphertext c before seeing the message m; Then, Make algorithm takes as input the message m and tries to find a possible permutation instance, under which m would be encapsulated to the ciphertext c. Our ideas are similar to those of Heuer et al., the main difference is that we use Open algorithm to replace the Make algorithm. Their Make algorithm exhaustively searches for the appropriate permutation, and may be inefficient. Our Open algorithm introduces auxiliary parameters, including the lossy secret key and some random coins, which makes the Open algorithm running in probabilistic polynomial time.

Theorem 1

The tweaked lossy encryption scheme is SIM-SSO-CPA secure.

Proof

(Sketch). The proof of Theorem 1 is similar to the proof of lossy encryption with efficient opening implies SIM-SSO-CPA security in [3], so we will only sketch it here. Consider the following sequence of games:

• $Game_0$: the REAL-SIM-SSO-CPA game.

• $Game_1$: the same as $Game_0$ except that the adversary is given a lossy public key and lossy ciphertexts. $Game_1$ and $Game_0$ are indistinguishable by the property of key indistinguishability.

• $Game_{2, 0}$: the same as $Game_1$ except that for the first ciphertext we replace $\mathrm {Enc}(pk, m_1; r_1)$ with $\mathrm {Fake}(pk, r'_1)$. In the corrupt procedure, instead of opening the first ciphertext by revealing the actual coins if $1 \in [I]$, $Game_{2, 0}$ runs $\mathrm {Open}(\varepsilon , \mathbf {M}[1])$ algorithm on the actual message and returns $r_1$, which is the random coins used to generate the first ciphertext. If $1 \notin [I]$, $Game_{2, 0}$ reveals the actual coins and returns the output. The view of adversary in this game is statistically close to that in the $Game_0$, since the variables $\{\mathrm {dist}^{\mathrm {Enc}}(pk, m)\}$ and $\{\mathrm {dist}^{\mathrm {Sim}}(pk, m)\}$ are statistically indistinguishable.

• $Game_{2, j}$: in the j-th hybrid game, we use $\mathrm {Fake}(\cdot )$ algorithm instead of $\mathrm {Enc}(\cdot )$ algorithm to generate the first j ciphertexts. In the corrupt procedure, $Game_{2, j}$ runs the $\mathrm {Open}(\varepsilon , \mathbf {M}[k])$ algorithm on the actual messages and returns $r_k$ if $k \in [I]$ and $k \le j$; Otherwise, $Game_{2, j}$ reveals the actual coins and returns the output.

• $Game_{2, n}$: in the last hybrid, all ciphertexts are generated using the $\mathrm {Fake}(\cdot )$ algorithm. In the corrupt procedure, $Game_{2, n}$ runs the $\mathrm {Open}(\varepsilon , \mathbf {M})$ algorithm on the actual messages and returns the output.

• $Game_3$: the same as $Game_{2, n}$ except that the sampling of $\mathbf {M}$ is moved before the $\mathrm {Open}(\varepsilon , \mathbf {M})$ algorithm and after the $\mathrm {Fake}(\cdot )$ algorithm. The $\mathrm {Fake}(\cdot )$ algorithm no longer requires a message vector, therefore it does not change the view of the adversary.

Now we can construct a simulator $\mathcal {S}$ that runs the adversary $\mathcal {A}$ as its subroutine, just as $\mathcal {A}$ behaves in $Game_3$. Specially, $\mathcal {S}$ chooses a lossy key pair and gives $\mathcal {A}$ the lossy public key and n fake ciphertexts under lossy public key. In case of corruption, when $\mathcal {A}$ makes a query with a set I, $\mathcal {S}$ forwards the same set I to its own challenge oracle. After receiving the messages $\mathbf {M}_I$, $\mathcal {S}$ then uses the efficient algorithm $\mathrm {Open}(\varepsilon , \mathbf {M})$ to open the fake ciphertexts to the messages $\mathbf {M}_I$. Finally, after $\mathcal {A}$ outputs a string out, the simulator $\mathcal {S}$ will output the same value. Since both $\mathcal {A}$ and $\mathrm {Open}(\varepsilon , \mathbf {M})$ are efficient, the simulator $\mathcal {S}$ is also efficient. Because the neighboring games are either statistically indistinguishable or computationally indistinguishable, the theorem holds.

4 Tweaked Lossy Encryption Scheme from Extractable $\mathrm {\Sigma }$-protocol

In this section, we build a tweaked lossy encryption scheme from extractable $\mathrm {\Sigma }$-protocol that is defined on a membership-hard language L with efficient sampling [33].

4.1 Membership-Hard Languages with Efficient Sampling

Let L be a language. Let $S_L$ be a sampling algorithm that takes a bit b as input. If $b = 0$, $S_L$ outputs an instance in the language L together with a corresponding witness w. If $b = 1$, $S_L$ outputs an instance not in the language L. It is required that no PPT distinguisher can tell which bit $S_L$ received. Let $S^{x}_L$ denote the instance of the output of the sampling algorithm $S_L$, we now recall the formal definition of the membership-hard languages with efficient sampling.

Definition 4

([33]). We say that a language L satisfies membership-hard with efficient sampling, if there exists a PPT sampling algorithm $S_L$ such for any PPT distinguisher D, the advantage $\mathrm {Adv}^x_D(n)$ defined below is negligible:

$$\begin{aligned} \mathrm {Adv}^x_D(n) = |\Pr [D(S^x_L(0, 1^n), 1^n) = 1]-\Pr [D(S_L(1, 1^n), 1^n) = 1]| \end{aligned}$$

4.2 Our Scheme

Our scheme is inspired by the general framework for constructing ABME in [16], and is also inspired by the general construction of dual-mode commitment in [33]. The detailed construction of scheme $(\mathrm {Gen},$ $\mathrm {LGen},$ $\mathrm {Enc},$ $\mathrm {Dec},$ $\mathrm {Sim}.\mathrm {Fake},$ $\mathrm {Sim}.\mathrm {Open})$ as in Definition 3 is as following (denote by Construction 1):

• $\mathrm {Gen}(1^{\lambda })$: run the sampling algorithm $S_L(1, 1^{\lambda })$ to get x, while $x \notin L$, where L is a membership-hard language. Let $\varSigma ^{\mathrm {ext}} =$ $(\mathrm {P}^{\mathrm {com}}_{\varSigma }$, $\mathrm {P}^{\mathrm {ans}}_{\varSigma }$, $\mathrm {V}^{\mathrm {vrfy}}_{\varSigma }$, $\mathrm {simP}^{\mathrm {com}}_{\varSigma }$, $\mathrm {Ext})$ be an extractable $\mathrm {\Sigma }$-protocol defined on L, where $\mathrm {Ext}$ is a deterministic extraction algorithm, and let $sk^{\mathrm {ext}}$ be the secret key of $\mathrm {Ext}$. The real public key is $pk = x$ and the real secret key is $sk = sk^{\mathrm {ext}}$.

• $\mathrm {LGen(1^{\lambda })}$: run the sampling algorithm $S_L(0, 1^{\lambda })$ to obtain (x, w), with w being the witness for $x \in L$. The lossy public key is $pk = x$ and the lossy secret key is $sk = w$.

• $\mathrm {Enc}(pk, m; r)$: to encrypt a message $m \in \{0, 1\}^n$, run $\mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, m; r)$ algorithm and output (a, m, r), denoted as $(a, m, r) = \mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, m; r)$. The ciphertext is $c = a$.

• $\mathrm {Dec}(sk^{\mathrm {ext}}, x, c)$: take the secret key $sk^{\mathrm {ext}}$, the public key x and the ciphertext c as inputs, output $m = \mathrm {Ext}(sk^{\mathrm {ext}}, x, c)$.

• $\mathrm {Sim}.\mathrm {Fake}(pk, w; r_a)$: take the lossy public key pk, witness w and a random coins $r_a$ as inputs, output $(e^{*}, \varepsilon )$ such that $e^{*} = \mathrm {P}^{\mathrm {\mathrm {com}}}_{\varSigma }(x, w; r_a)$ and $\varepsilon = (pk, w, r_a)$.

• $\mathrm {Sim}.\mathrm {Open}(\varepsilon , m)$: take $\varepsilon$ and m as inputs, and output $r = \mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, m)$.

4.3 Security Analysis

We then prove that the scheme in Construction 1 is a tweaked lossy encryption scheme.

Theorem 2

The scheme in Construction 1 is a tweaked lossy encryption scheme if L is a membership-hard language with efficient opening, and $\varSigma ^{\mathrm {ext}} = (\varSigma , \mathrm {Ext})$ is an extractable $\mathrm {\Sigma }$-protocol for L.

Proof

• Correctness. If $x \notin L$, according to the special soundness property of $\mathrm {\Sigma }$-protocol, for every a, there exists a unique m such that (a, m, r) is an accepting transcription on x, therefore m can be decrypted correctly using secret key $sk^{\mathrm {ext}}$.

• Key indistinguishability. The real public key is an instance not in language L, while the lossy public key is an instance in language L. Since L is a membership-hard language, the real public key and the lossy public key are computationally indistinguishable.

• Simulatability. While $x \in L$, $\mathrm {Sim}$ holds the witness for $x \in L$ and can run the real $\mathrm {\Sigma }$-protocol: First, the prover runs the $\mathrm {Sim}.\mathrm {Fake}$ algorithm $\mathrm {P}^{\mathrm {\mathrm {com}}}_{\varSigma }(x, w; r_a)$ where $r_a \leftarrow R_{\mathrm {Enc}}$ and outputs a commitment $a = \mathrm {P}^{\mathrm {\mathrm {com}}}_{\varSigma }(x, w; r_a)$, then sends the commitment a to the verifier; Second, the verifier sends a challenge m after receiving the commitment a; Finally, the prover runs the $\mathrm {Sim}.\mathrm {Open}$ $\mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, m)$ algorithm and outputs $r = \mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, m)$, where r is the random coins used in the encryption algorithm, then sends r to the verifier. Since $x \in L$, according to the eHVSZK property of extractable $\mathrm {\Sigma }$-protocol, the following two distributions are statistically indistinguishable:

  $$\begin{aligned} \{\mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, m; r)\} \approx _s \{(\mathrm {P}^{\mathrm {com}}_{\varSigma }(x, w; r_a), m, \mathrm {P}^{\mathrm {ans}}_{\varSigma }(x, w, r_a, m))\} \end{aligned}$$

  where $(a, m, r) = \mathrm {simP}^{\mathrm {com}}_{\varSigma }(x, m; r)$, thus the simulatability property follows readily.

5 Instantiations

In this section, we present two instantiations of tLPKE scheme from extractable $\varSigma$-protocol, based on dual-mode commitments [33] and Twin-Cramer-Shoup scheme [8, 9] respectively.

5.1 Instantiation of tLPKE from Dual-Mode Commitments

Let g be a generator of a group G of prime order q, and we assume that G is efficiently samplable. Let $u = g^x$ and $v = h^x$ with $h = g^r$ where $x, r \leftarrow \mathbb {Z}^{*}_q$. We define the language L as:

$$\begin{aligned} L=\{(u, v)|\exists \ x: u = g^x, v = h^x\}. \end{aligned}$$

We then construct an instantiation of the tLPKE as follows, and we denote it as Instantiation 1.

• $\mathrm {Gen}(1^{\lambda })$: given a security parameter $\lambda$, run $\mathcal {G}(1^{\lambda })$ to obtain a tuple $(\mathbb {G}, q, g)$. Choose $r, x_1, x_2 \leftarrow \mathbb {Z}^{*}_q$, and compute $h = g^r$, $u = g^{x_1}$, $v = h^{x_2}$. Output the public key $pk = (\mathbb {G}, q, g, h, u, v)$ and the secret key $sk=r$.

• $\mathrm {LGen}(1^{\lambda })$: given a security parameter $\lambda$, run $\mathcal {G}(1^{\lambda })$ to obtain a tuple $(\mathbb {G}, q, g)$. Choose $r, x \leftarrow \mathbb {Z}^{*}_q$, and compute $h = g^r$, $u = g^x$, $v = h^x$. Output the lossy public key $pk = (\mathbb {G}, q, g, h, u, v)$ and the lossy secret key $sk = x$.

• $\mathrm {Enc}(pk, m; z)$: to encrypt a message $m \in \{0, 1\}^{k}$ where $k = O(\log \lambda )$, choose $z \leftarrow \mathbb {Z}^{*}_q$, and compute $a = g^z\cdot u^m$, $b = h^z\cdot v^m$. Output the ciphertext as $c = (a, b)$.

• $\mathrm {Dec}(sk, c)$: take as input the real secret key $sk=r$ and the ciphertext $c = (a, b)$, search for $m \in \{0, 1\}^{k}$ such that

  $$\frac{a^r}{b} = \left( \frac{u^r}{v}\right) ^m$$

  and output m.

• $\mathrm {Sim}.\mathrm {Fake}(pk, w)$: choose $w \in \mathbb {Z}^{*}_q$ uniformly at random, and compute $a = g^w$, $b = h^w$. Output the fake ciphertext $e^{*} = (a, b)$ and the auxiliary parameter $\varepsilon = (x, w)$.

• $\mathrm {Sim}.\mathrm {Open}$: take as input the auxiliary parameter $\varepsilon = (x, w)$, the message m and the ciphertext (a, b), and output the random coins $z = w - mx$.

We can see that when using the real public key, the $\mathrm {Enc}$ algorithm runs a simulation algorithm of the extractable $\mathrm {\Sigma }$-protocol on L; however, when using the lossy public key, the $\mathrm {Enc}$ runs a real extractable $\mathrm {\Sigma }$-protocol on L with witness x. We now give a detailed analysis.

Theorem 3

The Instantiation 1 is a tweaked lossy encryption scheme if DDH assumption holds.

Proof

• Correctness. In the decryption mode, where $(u, v) \notin L$. Since $a = g^{z+x_1m}$ and $b = g^{rz+rx_2m}$, implying that:

  $$\begin{aligned} \left( \begin{array}{c} \log a\\ \log b \end{array} \right) = \left( \begin{array}{cc} 1 &{} x_1\\ r &{} rx_2 \end{array} \right) \left( \begin{array}{c} z\\ m \end{array} \right) \end{aligned}$$

  Since $x_1 \ne x_2$, the determinant of $\left( \begin{array}{cc} 1 &{} x_1\\ r &{} rx_2 \end{array} \right)$ is nonzero, and $\left( \begin{array}{c} z\\ m \end{array} \right)$ is uniquely determined, such that

  $$\begin{aligned} \frac{a^r}{b} = \left( \frac{u^r}{v}\right) ^m \end{aligned}$$

  Therefore the decryption algorithm can search $m \in \{0, 1\}^{k}$ within $O(2^{k})$ steps where $k = O(\log \lambda )$.

• Key Indistinguishability. The real public keys and the lossy public keys are computationally indistinguishable under the DDH assumption.

• Simulatability. Consider an extractable $\mathrm {\Sigma }$-protocol scenario, where the prover knows x such that $u = g^x$, $v = h^x$ and $(u, v) \in L$. The messages of the protocol include (a, b), the challenge m and the random coins z which is the response to the challenge m. And ((a, b), m, z) forms an accepting transcript of the protocol’s execution for challenge m, where $m \in \{0, 1\}^{\lambda }$, $a = g^{z+mx}$ and $b = g^{rz+rmx}=a^r$. Since r, z, x are random elements of $\mathbb {Z}^{*}_q$, a and b are also random elements of $\mathbb {G}$, and the ciphertext (a, b) contains no information of the plaintext. Now consider the algorithm $\mathrm {Sim}.\mathrm {Fake}$ and $\mathrm {Sim}.\mathrm {Open}$. $\mathrm {Sim}.\mathrm {Fake}$ picks $w \in \mathbb {Z}^{*}_q$ uniformly at random, and let $a = g^w$, $b = h^w$. $\mathrm {Sim}.\mathrm {Open}$ takes as input the auxiliary parameter $\varepsilon = (x, w)$, the message m and the ciphertext (a, b), and it outputs $z = w - mx$. Because z, w, x are in linear relations, the distribution of z is identical to that of w and x, therefore z is a random element in $\mathbb {Z}^{*}_q$. According to the above analysis, we have

  $$\begin{aligned} \{(g^{z+mx}, g^{rz+rmx}), m, z\} \approx _s \{(g^w, h^w), m, z\}. \end{aligned}$$

  Thus, the simulatability property holds.

5.2 Instantiation of tLPKE from Twin-Cramer-Shoup Scheme

The instantiation in Sect. 5.2 is inspired by the similar instantiation of ABME from Twin-Cramer-Shoup in [16]. Let g be a generator of a group G of prime order q, and assume G is efficiently samplable and the DDH assumption holds on G. Choose $x \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, and set $X = g^x$. Choose $\xi \leftarrow G$, $v_0 \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, then compute $d_0 = g^{v_0}$, $e_0 = {\xi }^{-1}X^{v_0}$. Compute $d = g^v$, $e = \xi X^v$, where $v \leftarrow \mathbb {Z}^{*}_q$. Set $\lambda = O(\log k)$. Then we define the language $L_{cs}$ under $pk = (g, X, d_0, d_0d, e_0e)$:

$$\begin{aligned} L_{cs} = \{(d, e)|\exists (\tilde{v}, v): d_0 d = g^{\tilde{v}}, e_0 e = X^{\tilde{v}}, \mathrm {where}\ {\tilde{v}} = v_0 + v \}. \end{aligned}$$

We then build another instantiation of the tLPKE scheme as follows (denote by Instantiation 2):

• $\mathrm {Gen}(1^{\lambda })$: choose $x \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, and set $X = g^x$. Choose $\xi \leftarrow G$, $v_1 \leftarrow \mathbb {Z}^{*}_q$ and $v_2 \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, then compute $d_0 = g^{v_1}$ and $e_0 = {\xi }^{-1}X^{v_2}$. Let $d = g^v$, $e = \xi X^v$, where $v \leftarrow \mathbb {Z}^{*}_q$, let $\lambda = O(\log k)$, and finally output a pair of real keys (pk, sk), where $pk = (g, X, d_0, d_0d, e_0e)$ and $sk = x$.

• $\mathrm {LGen}(1^{\lambda })$: choose $x \leftarrow \mathbb {Z}^{*}_q$, $\xi \leftarrow G$, $v_0 \leftarrow \mathbb {Z}^{\star }_q$ and $v \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, and set $X = g^x$, $d_0 = g^{v_0}$, $e_0 = {\xi }^{-1}X^{v_0}$ and $d = g^v$, $e = \xi X^v$ respectively. Let $\lambda = O(\log k)$, and finally output a pair of lossy keys (pk, sk), where $pk = (g, X, d_0, d_0d, e_0e)$ and $sk = (v_0, v)$.

• $\mathrm {Enc}(pk, m; \mathbf {z})$: to encrypt a message $m \in \{0, 1\}^n$, divide m into $(m_1, \dots , m_l)$, where $l = n/\lambda$; and for all $1\le i\le l$, $m_i \in \{0, 1\}^{\lambda }$, choose $\mathbf {z} \leftarrow \mathbb {Z}^{*}_q$ uniformly at random, where $\mathbf {z} = (z_1, \dots , z_l)$, then compute:

  $$\begin{aligned} A = \left( \begin{array}{cc} g &{} d_0d \\ X &{} e_0e \end{array} \right) \left( \begin{array}{ccc} z_1 &{} \dots &{} z_l \\ m_1 &{} \dots &{} m_l \end{array} \right) \end{aligned}$$

  And finally output the ciphertext $c = A$.

• $\mathrm {Dec}(sk, c)$: let $A = (\mathbf {a_1}, \dots , \mathbf {a_l})$, where $\mathbf {a_i} = (a_{1, i}, a_{2, i})^T$. For every $i \in [l]$, search for appropriate $m_i \in \{0, 1 \}^{\lambda }$ such that:

  $$\begin{aligned} \frac{(a_{1, i})^x}{a_{2, i}}=\left( \frac{(d_0d)^x}{e_0e}\right) ^{m_i}, \ \mathrm {if} \ e_0e \ne (d_0d)^x. \end{aligned}$$

  If such $m_i$ can not be found, then output the decryption failure symbol “$\bot$”; Otherwise output $m = (m_1, \dots , m_l) \in \{0, 1\}^n$.

• $\mathrm {Sim}.\mathrm {Fake}(pk; \mathbf {w})$: first divide m into $(m_1, \dots , m_i)$, where $i \in [l]$, then pick up $w_i \in \mathbb {Z}^{*}_q$ uniformly at random, and compute $a_{1, i} = g^{w_i}$, $a_{2, i} = X^{w_i}$. Output the fake ciphertext $c = (a_{1, i}, a_{2, i})$ and $\varepsilon = (v_0, v, \mathbf {w})$ for $i \in [l]$.

• $\mathrm {Sim}.\mathrm {Open}(\varepsilon , m)$: take as input the auxiliary parameter $\varepsilon = (x, w)$, the message $(m_1, \dots , m_i)$ and the ciphertext $c = (a_{1, i}, a_{2, i})$ where $i \in [l]$, output $\mathbf {z}$ where $z_i = w_i - m_i \cdot \tilde{v}$ and $\tilde{v} = v_0 + v$.

  We then prove that the Instantiation 2 is a tweaked lossy encryption scheme.

Proof

• Correctness. When $(d, e) \notin L_{cs}$, the encryption algorithm uses the real public key pk to encrypt message and the resulting ciphertext is

  $$\begin{aligned} A = \left( \begin{array}{ccccc} g^{z_1}(d_0d)^{m_1} &{} \dots &{} g^{z_i}(d_0d)^{m_i}&{} \dots &{} g^{z_l}(d_0d)^{m_l} \\ X^{z_1}(e_0e)^{m_1} &{} \dots &{} X^{z_i}(e_0e)^{m_i}&{} \dots &{} X^{z_l}(e_0e)^{m_l} \end{array} \right) \end{aligned}$$

  Note that $\mathrm {rank}(A) = 2$. Let $\mathbf {a_i} = (a_{1, i}, a_{2, i})^T$ denotes the i-th column of the matrix A, then $a_{1, i} = g^{z_i + (v_1 + v)m_i}$, and $a_{2, i} = X^{z_i + (v_2 + v)m_i} = (g^x)^{z_i + (v_2 + v)m_i}$. We can see that $e_0e \ne (d_0d)^x$, and therefore $m_i$ can be recovered through the following equation:

  $$\begin{aligned} \frac{(a_{1, i})^x}{a_{2, i}}=\left( \frac{(d_0d)^x}{e_0e}\right) ^{m_i} \end{aligned}$$

  Therefore the decryption algorithm can output $m = (m_1, \dots , m_l) \in \{0, 1\}^n$ correctly.

• Key indistinguishability. The lossy public key is $pk = (g, g^x$, $g^{v_0+v}$, $g^{x(v_0+v)})$, and the real public key is $pk = (g, g^x, g^{v_0 + v_1}$, $g^{x(v_0+v_2)})$. Therefore, the lossy public key and the real public key are computationally indistinguishable under the DDH assumption.

• Simulatability. When $(d, e) \in L_{cs}$, the encryption algorithm runs a real extractable $\mathrm {\Sigma }$-protocol, where the common input is $(d_0d, e_0e)$ and the prover wants to prove that $\log _g {d_0d} = \log _{X} {e_0e}$. The vector $\mathbf {a_i} = (a_{1, i}, a_{2, i})^T$ is the first message of the protocol, $(m_1, \dots , m_l)$ is the parallel challenge, and $\mathbf {z_i}$ corresponds to the response to each challenge $m_i$. Therefore $(A, \mathbf {m}, \mathbf {z})$ is an accepting proof of the parallel execution of the extractable $\mathrm {\Sigma }$-protocols, where $\mathbf {m} = (m_1, \dots , m_l)$ is the challenge, and $m_i \in \{0, 1\}^{\lambda }$, and $i \in [l]$.

  Specifically, $(a_{1, i}, a_{2, i})^T = (g^{z_i + m_i \tilde{v}}, X^{z_i + m_i \tilde{v}})^T$, where $X = g^x$, $\tilde{v} = v_0 + v$, and $z_i, v_0, v \leftarrow \mathbb {Z}^{*}_q$. Since $\mathrm {rank}(A) = 1$, the ciphertexts will be uniformly distributed over $\mathbb {G}$. Now, the $\mathrm {Sim}.\mathrm {Fake}$ algorithm first divides m into $(m_1, \dots , m_i)$, where $i \in [l]$, then it chooses $w_i \in \mathbb {Z}^{*}_q$ uniformly at random and sets $a_{1, i} = g^{w_i}$, $a_{2, i} = X^{w_i}$. The $\mathrm {Sim}.\mathrm {Open}$ algorithm takes as input $\varepsilon = (v_0, v, \mathbf {w})$, and finally outputs $z_i = w_i - m_i \cdot \tilde{v}$, where $\tilde{v} = v_0 + v$. We can see that $z_i$ is a random element of $\mathbb {Z}^{*}_q$. According to the above analysis, we have:

  $$\begin{aligned} \{(g^{z_i + m_i \tilde{v} }, X^{z_i + m_i \tilde{v}})^T, m_i, z_i\}_{i \in [l]} \approx _s \{(g^{w_i}, X^{w_i})^T, m_i, z_i\}_{i \in [l]} \end{aligned}$$

  Thus, the variables $\mathrm {dist}^{\mathrm {Enc}}(pk, m)$ and $\mathrm {dist}^{\mathrm {Sim}}(pk, m)$ are statistically indistinguishable and the simulatability property holds.

6 Selective Opening Security for the Receiver

Following the work in [3, 4, 19], we recall the definition of IND-RSO-CPA, which is restricted to efficiently conditionally resamplable distributions.

Fig. 2.

The IND-RSO-CPA experiment

Definition 5

(Efficiently Conditionally Resamplable [3, 4]). Let $\mathrm {dist}$ be a joint distribution over $\mathcal {M}^n$, where $\mathcal {M}$ is the message space. We say that $\mathrm {dist}$ is efficiently conditionally resamplable if there is a PPT algorithm $\mathrm {ReSamp}_{\mathrm {dist}}$, such that for any $I \subset [n]$ and any $\mathbf {m}_{I}{:}{=}(m_i)_{i \in I}$, $\mathrm {ReSamp}_{\mathrm {dist}}(\mathbf {m}_{I})$ outputs $\mathbf {m}'_I$, and $\mathbf {m}'_I$ is sampled from the distribution $\mathrm {dist}$, conditioned on $m'_i = m_i$ for all $i \in I$.

Definition 6

(IND-RSO-CPA Security [19]). A PKE scheme $\mathrm {PKE}$ $=$ $(\mathrm {Gen}$, $\mathrm {Enc}$, $\mathrm {Dec})$ is IND-RSO-CPA secure if for any polynomially bounded $n = n(1^{\lambda }) > 0$, and any stateful PPT adversary $\mathcal {A}$, such that

$$\begin{aligned} \mathrm {\mathbf {Adv}}^{\mathrm {IND}-\mathrm {RSO}-\mathrm {CPA}}_{\mathrm {PKE}, \mathcal {A}}(1^{\lambda }) = \Pr [\mathrm {Exp}^{\mathrm {IND}-\mathrm {RSO}-\mathrm {CPA}}_{\mathrm {PKE}, \mathcal {A}}(1^{\lambda }) = 1] -\frac{1}{2} \end{aligned}$$

is negligible. The experiment $\mathrm {Exp}^{\mathrm {IND}-\mathrm {RSO}-\mathrm {CPA}}_{\mathrm {PKE}, \mathcal {A}}(1^{\lambda })$ is defined as in Fig. 2.

6.1 Tweaked NCER for Receivers

In [19], Hazay et al. proved that secure tweaked NCER implies IND-RSO-CPA secure PKE. The following definition essentially repeats the definition of tweaked NCER from [19] with small changes: the $\mathrm {tGen}$ algorithm outputs a trapdoor for solving hard problem instances, and the $\mathrm {tOpen}$ algorithm may receive the trapdoor as an additional input.

A tweaked NCER scheme $\mathrm {tPKE}$ is a tuple of algorithms $(\mathrm {tGen}$, $\mathrm {tEnc}$, $\mathrm {tEnc}^{*}$, $\mathrm {tDec}$, $\mathrm {tOpen})$, where $(\mathrm {tGen}, \mathrm {tEnc}, \mathrm {tDec})$ form a $\mathrm {PKE}$. The fake encryption algorithm $\mathrm {tEnc}^{*}$ takes the secret key sk, the public key pk and a message m as inputs, and it outputs a ciphertext $c^{*} \leftarrow \mathrm {tEnc}^{*}(pk, sk, m)$. The opening algorithm $\mathrm {tOpen}$ takes as input the secret key sk, the trapdoor $\tau$, the public key pk, fake ciphertext $c^{*}$ where $c^{*} \leftarrow \mathrm {tEnc}^{*}(pk, sk, m')$ for some $m' \in \mathcal {M}$ and a message m, and it outputs $sk^{*}$ such that $m = \mathrm {tDec}(sk^{*}, c^{*})$. For correctness, we want $m = \mathrm {tDec}(sk, c)$ hold for all $m \in \mathcal {M}$, all $(pk, sk) \leftarrow \mathrm {tGen}(1^{\lambda })$ and all $c \leftarrow \mathrm {tEnc}(pk, m)$. For security, we require that real ciphertexts and fake ciphertexts are indistinguishable, and a fake ciphertext can be decrypted to a concrete predetermined plaintext (Fig. 3).

Fig. 3.

Tweaked NCER

Definition 7

(Tweaked NCER [19]). We say that a tweaked NCER scheme tPKE is secure if it satisfies the following two conditions:

• for any PPT adversary $\mathcal {A}, \mathrm {Adv}^{\text{ ind-tcipher }}_{\text{ tPKE },\mathcal {A}}{:}{=}|\Pr [\mathrm {Exp}^ {\text{ ind-tcipher }}_{\text{ tPKE }}(\mathcal {A})=1]-\frac{1}{2}|$ is negligible.

• for any unbounded adversary $\mathcal {A}, \mathrm {Adv}^{\text{ ind-tncer }}_{\text{ tPKE },\mathcal {A}}{:}{=}|\Pr [\mathrm {Exp}^ {\text{ ind-tncer }}_{\text{ tPKE }}(\mathcal {A})=1]-\frac{1}{2}|$ is negligible.

Despite the fact that we use the trapdoor to help the $\mathrm {tOpen}$ algorithm output the secret key, the following lemma still follows from the corresponding proof in [19] with respect to the definition of tweaked NCER.

Lemma 1

([19]). If there exists an $\{$ind-tcipher, ind-tncer$\}$ secure tweaked NCER, then there exists a PKE that is IND-RSO-CPA secure.

6.2 Explainable Hash Proof Systems

Hash Proof Systems (HPS) or Smooth Projective Hash Functions (SPHFs) refer to a family of hash functions ($\mathrm {Hash}, \mathrm {ProjHash}$) defined on a language $L \subseteq X$, and are indexed by a pair of associated keys (hk, hp), where hk is the hashing key and the secret key, and hp is the projection key and the public key. The projective property of SPHFs stipulates that, for a word $x \in L$, the hash value can be computed using either a hashing key hk or a projection key hp with a witness w for $x \in L$. In contrast, the smoothness property of SPHFs stipulates that for a word $x \notin L$, the hash value should be completely undetermined.

Explainable Hash Proof Systems (EHPS) proposed by Abdalla et al. [1] are SPHFs with an additional property that: given the trapdoor, we can first generate a random-looking projection key hp, and finally output a valid hashing key hk corresponding to the projection key hp and any hash value H. The following definition of EHPS essentially repeats the definition from [1], except minor changes to fit our requirement. Formally, EHPS are a tuple of algorithms defined as follows:

• $\mathrm {Setup}(1^{\lambda })$: take the security parameter $\lambda$ as input and output a common reference string (CRS) crs together with a trapdoor $\tau$.

• $\mathrm {HashKG}(crs)$: take the CRS crs as input and output a hashing key hk.

• $\mathrm {ProjKG}(hk, crs)$: take the hashing key hk and the CRS crs as inputs, generate the projection key hp.

• $\mathrm {Hash}(hk, crs, x)$: take the hashing key hk, the CRS crs and any word $x \in X$ as inputs, output the hash value H.

• $\mathrm {ProjHash}(hp, crs, x, w)$: take a word $x \in L$, the projection key hp, and the witness w as inputs, output the hash value H.

• $\mathrm {SimKG}(crs, \tau , x)$: take as input crs, $\tau$ and a word $x \notin L$, output a projection key hp and an explainability key expk. For our purpose, we additionally require the hashing key hk to be part of the explainability key expk. We note that the first construction in [1] satisfy this property.

• $\mathrm {Explain}(hp, crs, x, H, expk)$: take as input the projection key hp, the CRS crs, the word $x \notin L$, the hash value H and the explainability key expk, output the corresponding hashing key hk.

For any $(crs, \tau ) \leftarrow \mathrm {Setup}(1^{\lambda })$, EHPS should satisfy the following properties:

• Explainability correctness: we require that hp $=$ $\mathrm {ProjKG}$ $(hk$, crs) and $H = \mathrm {Hash}(hk, crs, x)$ hold for any hash value H and any $x \notin L$, if $(hp, expk) \leftarrow \mathrm {SimKG}(crs, \tau , x)$ and $hk \leftarrow \mathrm {Explain}(hp, crs, x, H, expk)$.

• Indistinguishability: for any $x \notin L$, the following two distributions are statistically indistinguishable:

  $$\begin{aligned} \begin{aligned}&\{(hk, hp) | H\leftarrow \varPi ; (hp, expk)\leftarrow \mathrm {SimKG}(crs,\tau ,x);hk\leftarrow \mathrm {Explain}(hp,crs,x,H,expk)\}\\&\approx _s \{(hk, hp)| hk \leftarrow \mathrm {HashKG}(crs); hp \leftarrow \mathrm {ProjKG}(hk, crs)\}.\\ \end{aligned} \end{aligned}$$

6.3 IND-RSO-CPA Secure PKE from EHPS

Hazay et al. [19] demonstrated that HPS implies tweaked NCER, and we show that tweaked NCER can also be constructed from EHPS and it has multiple advantages. The tweaked NCER scheme we constructed is a tuple of five algorithms $(\mathrm {tGen}, \mathrm {tEnc}, \mathrm {tEnc}^{*}, \mathrm {tDec}, \mathrm {tOpen})$ as follows:

• $\mathrm {tGen}$: take the security parameter $\lambda$ as input, output the global parameter crs and the trapdoor $\tau$. Invoke $\mathrm {HashKG}$ and $\mathrm {ProjKG}$ algorithms to obtain $hk \leftarrow \mathrm {HashKG}(crs)$ and $hp \leftarrow \mathrm {ProjKG}(hk, crs)$ respectively, finally output the public key hp and secret key hk.

• $\mathrm {tEnc}$: take the public key hp and the plaintext m as inputs, choose a random $x \in L$ together with the witness w; compute $e = \mathrm {ProjHash}(hp, x, w) \oplus m$, and output the ciphertext (x, e).

• $\mathrm {tDec}$: take the secret key hk and the ciphertext (x, e) as inputs, output the plaintext $m = e\oplus \mathrm {Hash}(hk, x)$.

• $\mathrm {tEnc}^{*}$: take the secret key hk and the plaintext m as inputs, choose a random $x^{*}\in X \setminus L$; compute $e^{*}= \mathrm {Hash}(hk,x^{*})\oplus m$, and output the fake ciphertext $(x^{*},e^{*})$.

• $\mathrm {tOpen}$: take as input the trapdoor $\tau$, the secret key hk and the public key hp, fake ciphertext $(x^{*},e^{*})$ and plaintext m; let $expk = (\tau , hk)$ and let $H = e^{*} \oplus m$, then invoke the $\mathrm {Explain}(hp, crs, x^{*}, H, expk)$ algorithm, and finally output a secret key $hk^{*}$.

The ciphertexts generated by $\mathrm {tEnc}$ algorithm are real ciphertexts, while those generated by $\mathrm {tEnc}^{*}$ algorithm are fake ciphertexts. Furthermore, the decryption of a fake ciphertext $e^{*}$ is the plaintext m. Our scheme also satisfies the following properties:

• Completeness: it can be guaranteed by the projective property of EHPS.

• Security: according to the indistinguishability property of EHPS, the real and the fake ciphertexts are indistinguishable. In addition, the smoothness property of EHPS guarantees that $\mathrm {Hash}(hk, x^{*})$ is randomly distributed, for $x^{*} \in X \setminus L$. Hence, according to the explainability property, for a given m, there exists a $hk^{*}$ corresponding to hp such that $\mathrm {Hash}(hk^{*}, x^{*}) = e^{*} \oplus m$.

Compared with the construction of Hazay et al. [19], our construction mainly change the $\mathrm {tOpen}$ algorithm. Specifically, the $\mathrm {tOpen}$ algorithm in Hazay et al.’s [19] scheme allows an unbounded algorithm to find the right $hk^{*}$ by searching exhaustively, while our $\mathrm {tOpen}$ algorithm is more likely to obtain $hk^{*}$ efficiently by referring to the work in [1]. Abdalla et al. [1] proposed two schemes for constructing $\mathrm {Explain}(\cdot )$ in the $\mathrm {tOpen}$ algorithm. The first one is running in $O(2^v)$ time, where v is the bit length of the hash value. If v is a polynomial in logarithmic space, then the $\mathrm {Explain}(\cdot )$ algorithm is running in polynomial time. The second one is more efficient, where the $\mathrm {Explain}(\cdot )$ algorithm runs in constant time but can only be constructed in a specific framework. We note that if we can construct a $\mathrm {Explain}(\cdot )$ algorithm that runs in probabilistic polynomial time, then it is possible to construct a NCER scheme and thereby a SIM-RSO-CPA secure PKE scheme.

Remarks. The SimKG algorithm of EHPS is implicitly used in the construction of our tweaked NCER scheme. According to the explainability correctness of EHPS, the SimKG algorithm will generate the same public key hp as the output of ProjKG algorithm, and the explainability key expk is consisted of a trapdoor $\tau$ and a secret key hk corresponding to the public key hp.

7 Conclusion

In this paper, we study PKE of security against SO attacks, which is an important topic in PKE schemes. In particular, first, we define a new cryptographic primitive called tweaked lossy encryption, mainly inspired by ABME, dual-mode commitments, simulatable DEMs, and instance-dependent cryptographic primitives; and we further show that tweaked lossy encryption satisfies the SIM-SSO-CPA security. Second, we provide a generic construction of tweaked lossy encryption from extractable $\mathrm {\Sigma }$-protocol; in addition, we propose two instantiations of the scheme based on dual-mode commitments and Twin-Cramer-Shoup scheme respectively; and we offer solid proofs of the two instantiations satisfying our definition of tweaked lossy encryption. Finally, we further propose a generic scheme with IND-RSO-CPA security based on EHPS. Our work in this paper provides an insightful view about designing PKE schemes with SO security using cryptographic primitives, such as extractable $\mathrm {\Sigma }$-protocol and EHPS.