Keywords

1 Introduction

Traditionally, cryptographic algorithms are always proven secure under the assumption that the randomness and secrets involved are completely hidden from adversaries. In reality, however, various kinds of physical attacks demonstrated that attackers usually managed to extract partial secret information by observing the physical characteristics of executing cryptographic devices.

In recent years, motivated by the proliferation of key-leakage attacks such as [24, 30], a line of research usually called leakage-resilient cryptography [2, 8, 9, 13, 16, 29, 33, 34, 36, 37], was initiated with the purpose of designing provably secure cryptographic primitives against adversaries that can obtain secret information via such kind of attacks. Generally, key-leakage attacks are captured by a leakage oracle, which enables the adversary to get partial secret information by specifying an efficient leakage function chosen by himself, and the property of leakage-resilience stipulates that the cryptographic primitives remain secure even for the adversary that has access to the leakage oracle. Thus, some restrictions should be imposed on the leakage functions, such that it is hard for the adversary to recover the whole secret key. According to the constrains on leakage function f, the main types of leakage we are interested in this work are (1) bounded-memory leakage [1], where f is required to be efficiently computable and with output length much less than |sk|, and (2) auxiliary-input leakage [14], where f is stipulated to be sufficiently hard to invert for all efficient algorithms, but with no limitation on its output. We note that the latter can be seen as a generalization of the former, which captures a larger class of key-leakage attacks.

Although leakage-resilient cryptography provides a promising way for protecting against key-leakage attacks, they are still vulnerable to fault injection and memory tampering attacks [6, 22]. The theoretical treatment of such attacks was initiated by Bellare et al. [4], and then a series of research [3, 5, 32, 35, 39, 40] was conducted for designing various provably secure cryptographic primitives against this kind of attacks. Similarly, tampering attacks are captured by a family of efficiently computable functions \(\mathcal {T}: \mathcal {SK}\rightarrow \mathcal {SK}\), and the tamper-resilience requires that the cryptographic primitives remain provably secure even for the adversary that can learn partial secret information by observing the output of cryptographic devices executed under a transformed secret state. Take a signature scheme as an example: the adversary given a target verification key vk can observe the signatures of adaptively chosen messages under not only the original secret key sk but also the related keys \(f_t(sk)\), where \(f_t\) is the tampering function adaptively chosen by the adversary from \(\mathcal {T}\); identical to the standard security, the goal of the adversary is to produce a valid signature on a new message under vk. Obviously, tamper-resilience implies the original standard security.

In light of the fact that physical attacks include key-leakage attacks as well as tampering attacks in the real world, another concerned line of research—starting from the seminal work of Kalai et al. [28]—aims at developing cryptographic systems that resist both kinds of attacks. However, it is not an easy task to design cryptographic algorithms resilient to both key-leakage and tampering attacks. As far as we know, there are only few works [11, 19,20,21, 28, 31, 38] considering how to realize leakage and tamper-resilience at the same time. More details about these works will be given in the following section.

1.1 Related Works

In 2011, Kalai et al. [28] initiated the study of designing public key cryptosystems resilient to both key-leakage and tampering attacks. With the support of key-update mechanism, they presented a one-bit-message encryption scheme and a digital signature scheme in the continuous tampering and leakage (CTL) model, where the adversary is allowed to continuously issue leakage queries and tampering queries. However, their encryption scheme is only chosen-plaintext attack (CPA) secure, meaning that the adversary is not permitted to observe the effect of tampering on the output of decryption oracle. In addition, they presented a more efficient signature scheme without key-update algorithms in the so-called continuous tampering and bounded leakage (CTBL) model by assuming the existence of a protected self-destruct.

Following the above framework, Fujisaki et al. [21] further investigated how to construct chosen-ciphertext attack (CCA) secure PKE in the CTL or CTBL model. In particular, they showed that the encryption scheme in [34] can be proven CCA secure against continuous tampering and bounded leakage attacks (CTBL-CCA secure) under the self-destructive mechanism. Moreover, they presented a new PKE scheme with a key-update algorithm, which is proven CCA secure against continuous tampering and leakage attacks (CTL-CCA secure).

Different from the previous approach, Damgård et al. [11] introduced an alternative path to achieve security against both key-leakage and tampering attacks with neither self-destruction nor key-update mechanism. Note that, as observed by Gennaro et al. [23], it is impossible to achieve security against any polynomial number of arbitrary (and efficiently computable) tampering attacks without making further assumptions (such as self-destruction). Therefore, they imposed a restriction on the number of allowed tampering attempts made by the adversary, and introduced the so-called bounded leakage and tampering (BLT) model. To achieve security in this model, their main idea is to reduce tampering to leakage. By this way, they could achieve tamper-resilience against arbitrary key-relations, but disallowed the adversary to make any “post-challenge” tampering attempts. Moreover, the tamper-resilience is realized at the heavy cost of decreasing the amount of tolerated leakage. Following this attractive work, Faonio et al. further [19] showed that the already existing signature scheme [13] and encryption scheme [34] are proven secure in this model, thus giving the first BLT secure signature without random oracle and the first BLT-CCA secure PKE scheme avoiding non-interactive zero-knowledge proofs.

Recently, motivated by the feasibility of “post-challenge” tampering attacks, [38] studied leakage and tamper-resilient CCA secure PKE from a distinct perspective, where they made a constraint on the type of tampering functions (exactly non-arbitrary tampering attacks) instead of the number of tampering attacks as in BLT model. Precisely, they introduced the leakage and tamper-resilient (LTR) model, which is generally parameterized by a family \(\mathcal {T}\) of tampering functions and a class \(\mathcal {F}\) of leakage functions. Apart from having access to bounded-memory or auxiliary-input leakage, the adversary in this model is also allowed to make any polynomial number of both “pre-challenge” and “post-challenge” tampering queries. In contrast to previous models, the tampering functions in LTR model should be restricted instead of arbitrary efficiently computable functions. Otherwise, there exists no (\(\mathcal {F}, \mathcal {T}\))-LTR secure encryption schemes, since it is impossible to realize security against arbitrary post-challenge tampering as proven in [11, 23]. Moreover, they proposed a generic construction of pubic key encryption based on the newly introduced (key-homomorphic) HPS and showed its LTR-CCA security in the standard model.

Another relevant line of research is to protect cryptosystems against physical attacks by leveraging (leakage-resilient) non-malleable codes [17, 20, 27, 31]. While this yields a generic way for resisting leakage and/or tampering attacks, it usually relies on certain hardware requirements such as self-destruction, key-update mechanism or split-state model. Moreover, this way might bring certain expansion to the key storage. In this work, we are more interested in designing leakage and tamper-resilient public cryptosystems without such constrains.

1.2 Motivations

It is well-known that properly defining security models is of great importance to provable security. If a security model fails to capture the power of adversary, the cryptographic algorithms proven secure in such model may still suffer from serious security threats. Hence, it is crucial to catch the minimal restrictions on the adversary and then establish the security models as reasonable as possible.

Although the LTR security introduced by [38] is meaningful in practice, there is still an artificial restriction on the adversary. More specifically, the adversary in their model is disallowed to ask for any tampering query \((f_t, ct)\) such that \(ct=ct^*\), where \(ct^*\) is the challenge ciphertext. That is, the adversary is unable to issue challenge-dependent tampering queries and thus cannot observe the effect of tampering on the decryption of \(ct^*\), even if the related key \(f_t(sk)\ne sk\). In practice, this is an unreasonable constraint since the adversary may launch tampering attacks depending on the target ciphertext, so it is natural to ask whether or not we can overcome this shortcoming and achieve an improved security that allows the adversary to issue challenge-dependent tampering queries satisfying \((f_t(sk), ct)\ne (sk, ct^*)\)?

On the other hand, it is still unreasonable, as shown in [26], to impose the restriction \((f_t(sk), ct)\ne (sk, ct^*)\) to the adversary since s/he is only capable of choosing tampering functions and without any knowledge of sk in practice, so we ask if we can further reduce the above constraint to \((f_t, ct)\ne (I, ct^*)\), where I denotes the identity function?

1.3 Contributions

With these questions in mind, we first present an enhanced security notion for PKE, namely strong bounded leakage and tamper-resilient chosen-ciphertext security, i.e., \((\lambda , \mathcal {T})\)-sLTR-CCA security. In contrast to the original LTR-CCA security, it only stipulates that \((f_t, ct)\ne (I, ct^*)\) rather than \(ct\ne ct^*\), which is obviously the minimal restriction on the adversary’s capability and captures the essential constraint on challenge-dependent tampering queries since otherwise there exists no provably secure PKE schemes in the LTR model.

To the end, we then introduce a refined HPS named \(\mathcal {T}_{pm}\)-public-key-malleable HPS (\(\mathcal {T}_{pm}\)-PM-HPS) and present a generic paradigm for \((\lambda , \mathcal {T})\)-sLTR-CCA secure PKE from \(\mathcal {T}_{pm}\)-PM-HPS and true-simulation extractable NIZK argument system. For our construction, the tamper-resilience captured by \(\mathcal {T}\) and the amount \(\lambda \) of leakage depend on the \(\mathcal {T}_{pm}\)-public-key malleability and leakage-resilience property of the underlying PM-HPS. Particularly, the tampering function family we achieve is \(\mathcal {T}=\mathcal {T}_{pm}\cap (\mathcal {F}_{\textit{pfp}}\cup \{I\})\), where \(\mathcal {F}_{\textit{pfp}}\) denotes a family of functions with poly-fixed points. It means that our construction can obtain tamper-resilience against \(\mathcal {F}_{\textit{pfp}}\) only if \(\mathcal {F}_{\textit{pfp}}\)-PM-HPS exists.

Moreover, we present a strong auxiliary-input and tamper-resilient chosen-ciphertext security, i.e., \((\alpha , \mathcal {T})\)-sLTR-CCA security, where the adversary has access to \(\alpha \)-hard-to-invert auxiliary-input leakage but limited to submit tampering queries s.t. \((f_t(sk), ct)\ne (sk, ct^*)\). Then we show that a sightly adapted variant of the paradigm mentioned before can also achieve the \((\alpha , \mathcal {T})\)-sLTR-CCA security. We also explain why the proposed construction cannot meet the minimal restriction \((f_t, ct)\ne (I, ct^*)\).

At last, we instantiate the PM-HPS with the DDH and DLIN problems, and get the first efficient PKE schemes in the strong bounded/auxiliary-input leakage and tamper-resilient CCA security model. The instantiated scheme from Sect. 3 (resp. Sect. 4) is secure against \((l-2)\log p-\omega (\log \kappa )\) bits of key-leakage (resp. \(2^{-l^{\delta }}\)-auxiliary input). Unfortunately, the instantiated PM-HPS only support affine-public-key malleability, and thus our concrete constructions can only achieve tamper-resilience against affine function class. Therefore, how to construct \(\mathcal {F}_{\textit{pfp}}\)-PM-HPS from number-theoretical assumptions is an interesting question.

2 Preliminaries

2.1 Definitions and Lemmas

Definition 1

(Statistical Distance [15]). For two random variables X, Y over \(\varOmega \), their statistical distance is defined as \(\varDelta (X, Y)=\frac{1}{2} \sum _{\omega \in \varOmega }|\Pr [X=\omega ]-\Pr [Y=\omega ]|\). Then, X and Y are called \(\epsilon \)-close if \(\varDelta (X, Y)\le \epsilon \). Particularly, they are called statistically close for some negligible \(\epsilon \).

Definition 2

(Randomness Extractors [15]). A function \(\mathrm {Ext}: \mathcal {K}\times \{0, 1\}^{\tau }\rightarrow \{0, 1\}^{\ell }\) is called an average-case \((v, \varepsilon )\)-strong randomness extractor if for any pair of random variables (X, Z) such that \(X\in \mathcal {K}\) and \(\tilde{{H}}_{\infty }(X|Z) \ge v\), it holds that \(\varDelta ((\mathrm {Ext}(X, R), R, Z), (U_{\ell }, R, Z)) \le \varepsilon ,\) where R and \(U_{\ell }\) are uniformly and independently distributed over \(\{0, 1\}^{\tau }\) and \(\{0, 1\}^{\ell }\), respectively.

Definition 3

(Function Family with Poly-Fixed Points). Suppose that \(\mathcal {F}\) is a family of functions onto a finite set \(\mathcal {X}\), we call it a function family with poly-fixed points over \(\mathcal {X}\), denoted by \(\mathcal {F}_{{pfp}}\), if it holds that \(\mathrm {max}_{f\in \mathcal {F}}|\{x\in \mathcal {X}: f(x)=x\}|\le p(\kappa ),\) where \(p(\kappa )\) is some polynomial in \(\kappa \).

Lemma 1

(Generalized Leftover Hash Lemma [15]). Let \(\mathcal {H}=\{ h: \mathcal {X} \rightarrow \mathcal {Y} \}\) be a family of universal hash functions. Then, for arbitrarily random variables (X, Z) it holds that \(\varDelta ((h(X), h, Z), (U_{\mathcal {Y}}, h, Z))\le \frac{1}{2}\sqrt{2^{-\tilde{{H}}_{\infty }(X|Z)}|\mathcal {Y}|},\) where \(h\leftarrow \mathcal {H}\) and \(U_{\mathcal {Y}}\leftarrow \mathcal {Y}\).

This lemma states that a family of universal hash functions gives an average-case \((v, \varepsilon )\)-strong randomness extractor as long as \(\log |\mathcal {Y}|\le v- 2\log (1/\varepsilon )\).

Lemma 2

([25]). Let X, U be two random variables over \(\mathcal {X}\), such that \(U\leftarrow \mathcal {X}\), and Z be some (correlated) random variable. If for any \(\varepsilon \in [0, 1]\), \(\varDelta ((X, Z), (U, Z))\le \varepsilon \), then it holds that \(\tilde{{H}}_{\infty }(X|Z)\ge -\log (\frac{1}{|\mathcal {X}|}+\varepsilon )\).

Lemma 3

([15]). Let X, Y, Z be arbitrarily correlated random variables assuming Y takes at most \(2^{\lambda }\) possible values, then \(\tilde{{H}}_{\infty }(X|(Y, Z))\ge \tilde{{H}}_{\infty }(X|Z)-\lambda \). Particularly, \(\tilde{{H}}_{\infty }(X|Y) \ge {H}_{\infty }(X)-\lambda \).

2.2 Hardness Assumptions

We let Group be a PPT algorithm that takes a security parameter \(\kappa \) and outputs a tuple \((\mathbb {G}, g, p)\), where \(\mathbb {G}\) is a cyclic group of order p with generator g.

Decisional Diffie-Hellman Assumption [33]. The decisional Diffie-Hellman (DDH) problem is hard if for all PPT algorithm \(\mathcal {A}\), the following advantage

is negligible in \(\kappa \), where , \(g_{1}, g_{2}\in \mathbb {G}\) and \(x, x_{1}, x_{2} \in \mathbb {Z}_{p}\) are chosen uniformly at random and independently.

d-Linear Assumption [18, 33, 41]. The d-linear (d-LIN) problem is called hard if for all PPT algorithm \(\mathcal {A}\), the following advantage is negligible in \(\kappa \):

where , the elements \(g_{0}, g_1, \cdots , g_{d}\in \mathbb {G}\) and \(x_0, x_{1},\) \(\cdots , x_{d}\in \mathbb {Z}_{p}\) are chosen uniformly at random and independently.

Alternatively, this assumption can be restated under the algebraic framework of [18], and it is usually named \(\mathcal {L}_d\)-Matrix Diffie-Hellman (\(\mathcal {L}_d\)-MDDH) assumption where \(\mathcal {L}_d\) is a matrix distribution defined as below. More formally, it is said that the \(\mathcal {L}_d\)-MDDH assumption holds relative to Group if for all PPT adversaries \(\mathcal {A}\), the following advantage is negligible in \(\kappa \):

where , \(\varvec{x}\leftarrow \mathbb {Z}_p^d\) and \(\varvec{r}\leftarrow \mathbb {Z}_{p}^{d+1}\). Moreover, \(\mathbf A \) is sampled according to the distribution \(\mathcal {L}_d\) and the distribution is defined as follows:

$$\mathbf A =\left( \begin{array}{cccccc} a_1 &{} 0 &{} \cdots &{} 0 &{} 0 &{} 1\\ 0 &{} a_2 &{} \cdots &{} 0 &{} 0 &{} 1\\ \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} \cdots &{} a_{d-1} &{} 0 &{} 1\\ 0 &{} 0 &{} \cdots &{} 0 &{} a_d &{} 1\\ \end{array} \right) \in \mathbb {Z}_{p}^{d\times (d+1)} $$

where \(a_i\in \mathbb {Z}_p^*\). Notice that \((\mathbf A , \varvec{x}^{\top }{} \mathbf A )\) can be compactly written as \((a_1, \cdots , a_d,\) \( a_1x_1, \cdots , a_dx_d, \sum _{i=1}^{d}x_{i})\) with \(a_i\leftarrow \mathbb {Z}_p^*\) (Precisely, \(a_i\) can be seen as the implicit representatoin of \(g_i\) in \(\mathbb {Z}_p^*\), i.e., \(a_i=\log _{g_0}g_i\).) and \(x_i\leftarrow \mathbb {Z}_p\) for all \(i\in [d]\).

2.3 Public-Key-Malleable HPS

Inspired by [26], we present a new variant of HPS, called public-key malleable HPS. Precisely, it is refined from the regular one by introducing some new properties, such as public-key malleability and public-key collision resistance. For simplicity, we present it similarly as in [33, 38], by viewing it as a key encapsulation mechanism. For clarity, we follow the notations of [38] in the following.

Public-Key-Malleable Projective Hashing. Suppose \(\mathcal {G}\) be the set of system parameters, such as the underlying algebraic groups, and let \(\mathcal {HK}, \mathcal {PK}\) and \(\mathcal {K}\) be the sets of secret hash keys, public keys and encapsulated symmetric keys, respectively. Besides, we let \(\mathcal {C}\) be the set of all ciphertexts and \(\mathcal {V}\) the set of all valid ones. Also, we assume that there are efficient algorithms for sampling \(hk\leftarrow \mathcal {HK}\), \(c\leftarrow \mathcal {V}\) (together with a corresponding witness w) and \(c\leftarrow \mathcal {C}\backslash \mathcal {V}\).

Let \(\mathrm {\Lambda }=\{\mathrm {\Lambda }_{hk}:\mathcal {C}\rightarrow \mathcal {K}\}\) be a family of hash functions indexed with \(hk\in \mathcal {HK}\) and \(\mu :\mathcal {HK}\rightarrow \mathcal {PK}\) be a projection function. We call \(\mathrm {\Lambda }\) \(\epsilon \)-smooth, \(\mathcal {T}\)-public-key-malleable and projective if it satisfies the following properties:

Projectivity: \(\mathrm {\Lambda }\) is said to be projective if for all \(c\in \mathcal {V}\), \(hk_{1}\ne hk_{2}\) but \(\mu (hk_{1})=\mu (hk_{2})\), it holds that \(\mathrm {\Lambda }_{hk_{1}}(c)=\mathrm {\Lambda }_{hk_{2}}(c)\), meaning that the action of \(\mathrm {\Lambda }_{hk}(\cdot )\) on \(\mathcal {V}\) is completely determined by \(\mu (hk)\) and c.

\(\mathcal {T}_{pm}\)–Public-Key Malleability: \(\mathrm {\Lambda }\) is said to be \(\mathcal {T}_{pm}\)–public-key-malleable if for all \(hk\in \mathcal {HK}\) and \(f_t\in \mathcal {T}_{pm}\), there exists a polynomial-time algorithm, called \(\mathcal {T}_{pm}\)-public-key transformer \(\texttt {Trans}: \mathcal {T}_{pm}\times \mathcal {PK}\rightarrow \mathcal {PK}\), such that

$$\mu (f_{t}(hk))=\texttt {Trans}(f_{t}, \mu (hk)).$$

Smoothness: \(\mathrm {\Lambda }\) is said to be \(\epsilon \)-smooth if the action of \(\mathrm {\Lambda }_{hk}(\cdot )\) on \(\mathcal {C}\backslash \mathcal {V}\) is completely undetermined. That is, the following distributions are \(\epsilon \)-close:

$$\varDelta \big ((c, \textit{pk}, \mathrm {\Lambda }_{hk}(c)),(c, \textit{pk}, K)\big )\le \epsilon $$

where \(hk\leftarrow \mathcal {HK}\), \(\textit{pk}=\mu (hk)\), \(c\leftarrow \mathcal {C}\backslash \mathcal {V}\) and \(K\leftarrow \mathcal {K}\).

Public-Key-Malleable HPS. Generally, a public-key-malleable HPS comprises three polynomial-time algorithms : on input a security parameter \({\kappa }\), Param\((1^{\kappa })\) generates a parameterized instance \(params=(\mathcal {G}, \mathcal {C}, \mathcal {V}, \mathcal {HK}, \mathcal {PK}, \) \(\mathcal {K}, \mathrm {\Lambda }, \mu )\); on input a public key \(\textit{pk}=\mu (hk)\), a valid ciphertext c and a witness w of the fact that \(c\in \mathcal {V}\), Pub(\(\textit{pk}, c, w\)) outputs an encapsulated key \(K=\mathrm {\Lambda }_{hk}(c)\); with a secret key hk and a ciphertext \(c\in \mathcal {C}\) as input, the algorithm Priv(hk, c) returns the encapsulated key \(K=\mathrm {\Lambda }_{hk}(c)\).

In addition, we assume that \(\mu (\cdot )\) is efficiently computable and so is \(\mathrm {\Lambda }_{hk}(\cdot )\) for each \(hk\in \mathcal {HK}\). For all \(hk\in \mathcal {HK}, \textit{pk}=\mu (hk)\) and \(c\in \mathcal {V}\) with witness w, it is obvious that we have \(\textsf {Pub}(\textit{pk}, c, w)=\textsf {Priv}(hk, c)=\mathrm {\Lambda }_{hk}(c)\).

Subset Membership Problem: A subset membership (SMP) problem associated with a PM-HPS is hard if for any PPT adversary \(\mathcal {A}\), its advantage

is negligible in \(\kappa \), which means it is difficult for all \(\mathcal {A}\) to distinguish a random valid ciphertext \(c_{0}\in \mathcal {V}\) from a random invalid ciphertext \(c_{1}\in \mathcal {C}\backslash \mathcal {V}\).

Public-Key Collision Problem: A public-key collision (PKC) problem associated with a PM-HPS is called hard if for any PPT adversary \(\mathcal {A}\), the following advantage is negligible in \(\kappa \),

$$Adv_{\textsf {PM{-}HPS},\mathcal {A}}^{\mathrm {PKC}}(\kappa )=\left| \Pr \left[ hk\ne hk'\wedge \mu (hk)=\mu (hk'): \begin{array}{c} params\leftarrow \textsf {Param}(1^{\kappa }), \\ (hk, hk')\leftarrow \mathcal {A}(params) \end{array} \right] \right| ,$$

which means it is difficult for all \(\mathcal {A}\) to find a collision of \(\mu \). For a PM-HPS, it is called public-key collision resistant if the associated PKC problem is hard.

Definition 4

A PM-HPS is called a smooth HPS with \(\mathcal {T}_{pm}\)-public-key malleability and public-key collision resistance, if for all \(\kappa \in \mathbb {N}\) and outcomes of Param(\(1^{\kappa }\)): (1) the underling projective hash is \(\epsilon (\kappa )\)-smooth and \(\mathcal {T}_{pm}\)-public-key malleable for some negligible \(\epsilon (\kappa )\); (2) both the SMP and PKC problems are hard.

2.4 True-Simulation Extractability

The notion of true-simulation extractability is proposed by Dodis et al. [13]. More formally, for an NP relation R with corresponding language \(\mathtt {L}=\{y: \exists ~x ~s.t.~ (y, x)\in \mathtt {R} \}\), a tSE-NIZK proof system for R generally consists of a triple of polynomial-time algorithms (Gen, Prov, Verf):

Gen(\(1^{\kappa }\)): on input a security parameter \(\kappa \), the algorithm generates a common reference string crs together with a trapdoor tk and an extraction key ek.

Prov(y, x)Footnote 1: on input a valid pair \((y, x)\in \mathtt {R}\), the algorithm outputs an argument \(\pi \) proving that \(\mathtt {R}(y, x)=1\).

Verf(y, \(\pi \)): on input a pair \((y, \pi )\), the algorithm verifies whether or not the argument \(\pi \) w.r.t. y is true and outputs 0/1.

For such a proof system \(\mathrm {\Pi }=(\textsf {Gen}, \textsf {Prov}, \textsf {Verf})\), it is called true simulation extractable (tSE) if it satisfies all the following properties:

Completeness. For all (y, x) s.t. \(\mathtt {R}(y, x)=1\) and \((crs, tk, ek)\leftarrow \mathsf {Gen}(1^{\kappa })\), it holds

$$\Pr [\mathsf {Verf}(y, \pi )=1: \pi \leftarrow \textsf {Prov}(y, x)]=1.$$

Composable Non-interactive Zero Knowledge. There exists an efficient simulator \(\mathcal {S}\) such that, for all PPT algorithm \(\mathcal {A}\) in the following game, it holds that

$$\left| \Pr \left[ b'=b: \begin{array}{l} (crs, tk, ek)\leftarrow \textsf {Gen}(1^{\kappa }); (y, x)\leftarrow \mathcal {A}(crs); b\leftarrow \{0, 1\}\\ \pi _{0}=\textsf {Prov}(y, x); \pi _{1}=\mathcal {S}(y, tk); b'\leftarrow \mathcal {A}(crs, \pi _b) \end{array} \right] -\frac{1}{2}\right| \le negl(\lambda ).$$

Strong True Simulation Extractability. There is an efficient algorithm Ext(\(y, \pi , ek\)) such that for all PPT algorithm \(\mathcal {A}\) in the following game, it holds that

$$\Pr \left[ \begin{array}{c} (y^*, x^*)\in \texttt {R}\vee (y^*, \pi ^*)\in Q \\ \vee ~ \textsf {Verf}(y^*, \pi ^*)=0 \end{array} : \begin{array}{l} (crs, tk, ek)\leftarrow \textsf {Gen}(1^{\kappa })\\ (y^*, \pi ^*)\leftarrow \mathcal {A}^{\mathcal {O}_{tk}(\cdot , \cdot )}(crs)\\ x^*\leftarrow \textsf {Ext}(y^*, \pi ^*, ek).\\ \end{array} \right] \ge 1-negl(\lambda ).$$

where Q denotes the set of all \((y, \pi )\) that \(\mathcal {A}\) obtained via the oracle \(\mathcal {O}_{tk}(\cdot , \cdot )\).

Specifically, if \(\mathcal {A}\) asks only for a single query to the simulation oracle, then \(\mathrm {\Pi }\) is called one-time strong true simulation extractable. From the above, we know that Ext succeeds to extract a valid witness for \(y^{*}\) with an overwhelming probability, if \(\mathcal {A}\) could output a fresh and valid pair \((y^{*}, \pi ^{*})\) at the end.

2.5 Public Key Encryption

A PKE is a tuple of polynomial time algorithms (Setup, KeyGen, Enc, Dec) with the following syntax: given a security parameter \(\kappa \), Setup(\(1^{\kappa }\)) generates the public parameters pp; given pp, KeyGen(pp) outputs a public and secret key pair \((pk, sk)\in \mathcal {PK}\times \mathcal {SK}\); given a public key pk and a message \(m\in \mathcal {M}\), Enc(pk, m) outputs a ciphertext \(c\in \mathcal {C}\); given a secret key sk and a ciphertext c, Dec(sk, c) returns a plaintext or \(\bot \) which indicates that the ciphertext is invalid.

The public parameters pp are system-wide and implicitly taken as part of the inputs of all algorithms. In an implementation, these parameters could be hardwired into the algorithm code and stored in a tamper-proof way. For the standard correctness, it is required that m = Dec(sk, Enc(pk, m)) for any message \(m\in \mathcal {M}\), \(pp\leftarrow \textsf {Setup}(1^{\kappa })\) and \((pk, sk)\leftarrow \textsf {KeyGen}(pp)\).

2.6 Security Definitions

In this part, we present two enhanced security notions against the leakage and tampering attacks, both of which are stronger than that in [38]. Similarly, the definitions are parameterized by a key-leakage bound \(\lambda \) (or a class \(\mathcal {F}\) of computationally uninvertible functions) and a class \(\mathcal {T}\) of restricted tampering functions.

First, we give the formal definition of CCA security against bounded-memory leakage and tampering attacks (i.e., \((\lambda , \mathcal {T})\)-sLTR-CCA Security), as follows.

Definition 5

(\((\lambda , \mathcal {T})\)-sLTR-CCA Security). Let PKE = (Setup, KeyGen, Enc, Dec) be a PKE scheme, it is \((\lambda , \mathcal {T})\)-strong leakage and tamper-resilient CCA (sLTR-CCA) secure if for any PPT adversary \(\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)\), its advantage

$$Adv_{\mathcal {A}, \textsf {PKE}, \mathcal {T}}^{\lambda \text {-}\mathrm {sLTR}\text {-}\mathrm {CCA}}(\kappa )=\left| \Pr [\mathbf {Expt}_{\mathcal {A}, \textsf {PKE}, \mathcal {T}}^{\lambda \text {-}\mathrm {sLTR}\text {-}\mathrm {CCA}}(\kappa )=1]-1/2\right| \le negl(\kappa ),$$

is negligible in \(\kappa \), where the experiment \(\mathbf {Expt}_{\mathcal {A}, \textsf {PKE}, \mathcal {T}}^{\lambda \text {-}\mathrm {sLTR}\text {-}\mathrm {CCA}}(\kappa )\) is defined as:

figure a

In the experiment, \(\mathcal {O}_{sk}^{\lambda }(\cdot )\) denotes a leakage oracle, by which \(\mathcal {A}\) is allowed to learn at most \(\lambda \)-bit secret information. Particularly, whenever receiving the i-th leakage query \(f_{i}(\cdot )\), the oracle returns \(f_{i}(sk)\) if \(\sum _{j=1}^{i}|f_{j}(sk)|\le \lambda \); otherwise, outputs \(\bot \). \(\mathcal {O}_{sk}^{\mathcal {T}}(\cdot , \cdot )\) denotes a tampering oracle, by which \(\mathcal {A}\) can observe the effect of decryption under a transformed key. Specifically, given a tampering query \((f_{t}(\cdot ), ct)\) s.t. \(f_{t}\in \mathcal {T}\), the oracle returns \(\textsf {Dec}(f_{t}(sk), ct)\). After seeing \(ct^*\), \(\mathcal {A}\) is disallowed to ask for any leakage query, but sill permitted to issue tampering queries only if \((f_t, ct)\ne (I, ct^*)\), where I denotes the identity function.

Notice that, this notion is parameterized by a leakage bound \(\lambda \) and a class \(\mathcal {T}\) of tampering functions, where each \(f_{t}\in \mathcal {T}\) has the form of \(f_{t}: \mathcal {SK}\rightarrow \mathcal {SK}\) and the leakage bound indicates that the whole lifetime of the system leaks at most \(\lambda \)-bit secret information. Specially, if \(\mathcal {T}=\{I\}\), \(\mathcal {O}_{sk}^{\mathcal {T}}(\cdot , \cdot )\) is the standard decryption oracle, and the above defines \(\lambda \)-leakage resilient CCA (LR-CCA) security. Moreover, when \(\mathcal {O}_{sk}^{\mathcal {T}}(\cdot , \cdot )\) is completely omitted from the experiment, it is exactly the definition of \(\lambda \)-LR-CPA security.

Remark 1

The sole limitation on tampering query is \((f_t, ct)\ne (I, ct^*)\), which means that \(\mathcal {A}\) is allowed to obtain the decryption of \(ct^*\) under the tampered secret key \(f_{t}(sk)\) only if \(f_t\ne I\). Clearly, this definition is much stronger than that in [38] where \((f_t, ct)\) is subject to \(ct\ne ct^*\). On the other hand, \((f_t, ct)\ne (I, ct^*)\) is the minimal restriction on tampering queries, since otherwise there is no PKE achieving the above security, thus our definition captures the essential constraint on tampering queries. Note that the challenger in above game needs to check if \(f_t = I\) when \(ct=ct^*\), so it is necessary for \(\mathcal {A}\) to give a clear description of \(f_t\), like in related-key attack security [5, 40] where the description of key-derivation function should be known by the challenger. Otherwise (e.g., \(f_t\) is obfuscated), it may be difficult to verify \(f_t\) belongs to the targeted function class and to simulate the tampering query.

Next, we introduce the definition of CCA security against auxiliary-input leakage and tampering attacks (i.e., \((\alpha , \mathcal {T})\)-sLTR-CCA Security). In contrast to bounded-memory leakage, auxiliary-input initialized by [14], may information-theoretically reveal the whole secret key, but still hard for any efficient algorithm to recover it. Hence, it captures a wider class of physical attacks and can be seen a generalization of bounded-memory leakage. Before presenting the formal security definition, we first recall the hardness of inverting a function family given in [38].

Definition 6

(Hard to Invert Function). A family of functions \(\mathcal {F}=\{f:\mathcal {PK}\times \mathcal {SK}\rightarrow \mathcal {SK}\}\) is said to be \(\alpha \)-hard to invert, denoted by \(\mathcal {F}(\alpha )\), if for any PPT algorithm \(\mathcal {A}\), \(\alpha =\alpha (k)\ge 2^{-k}\) and \(f\in \mathcal {F}\), the probability of \(\mathcal {A}\) inverting f is no more than \(\alpha \). That is,

$$Adv_{\mathcal {A}}^{f}(k)=\Pr [\mathcal {A}(1^{\kappa }, f(pk, sk))=sk: (pk, sk)\leftarrow \textsf {KeyGen}(1^{\kappa })]\le \alpha , $$

where k denotes the min-entropy of sk. If the probability \(Adv_{\mathcal {A}}^{f}(k)\le \alpha \) holds even for the adversary that also takes pk as input, the function family \(\mathcal {F}\) is called \(\alpha \)-strongly hard to invert.

Definition 7

(\((\alpha , \mathcal {T})\)-sLTR-CCA Security). Let PKE = (Setup, KeyGen, Enc, Dec) be a PKE scheme, it is said to be \((\alpha , \mathcal {T})\)-strong leakage and tamper-resilient CCA (sLTR-CCA) secure if for any PPT adversary \(\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)\) and \(\alpha \)-hard to invert function \(f\in \mathcal {F(\alpha )}\), its advantage

where the experiment is defined as:

figure b

The experiment above is almost the same as \(\mathbf{Expt}_{\mathcal {A}, \textsf {PKE}, \mathcal {T}}^{\lambda \text {-sLTR-CCA}}(\kappa )\), except that the leakage query \(f\in \mathcal {F}(\alpha )\) is now an \(\alpha \)-hard to invert function rather than a function with bounded output-length. Furthermore, the tampering oracle \(\mathcal {O}_{sk}^{\mathcal {T}}(\cdot , \cdot )\) in this experiment imposes a slightly stricter restriction on tampering queries \((f_{t}(\cdot ), ct)\). In fact, the adversary after seeing \(ct^*\) is only allowed to submit tampering queries s.t. \((f_{t}(sk), ct)\ne (sk, ct^*)\). Obviously, this limitation is not so reasonable as before since the adversary has no knowledge of sk, but it is still much weaker than [38] where \((f_{t}(\cdot ), ct)\) is required to satisfy \(ct\ne ct^*\). Therefore, this new definition is much stronger than the previous.

3 Construction of \((\lambda , \mathcal {T})\)-sLTR-CCA Secure PKE

In this section, we present a generic construction of \((\lambda , \mathcal {T})\)-sLTR-CCA secure PKE from a smooth HPS (with \(\mathcal {T}_{pm}\)-public-key malleability and public-key collision resistance) , where Param on input \(1^{\kappa }\) generates a parameterized instance \((\mathcal {G}, \mathcal {C}, \mathcal {V}, \mathcal {HK}, \mathcal {PK}, \mathcal {K}, \mathrm {\Lambda }, \mu )\). In addition, we need an average-case \((\log |\mathcal {K}|-\lambda , \varepsilon )\)-strong extractor \(\text {Ext}:\mathcal {K}\times \{0, 1\}^{\tau } \rightarrow \{0, 1\}^{\ell }\) and a tSE-NIZK proof system \(\mathrm {\Pi }=(\textsf {Gen}, \textsf {Prov}, \textsf {Verf})\) for the language

$$\texttt {L}=\{(\textit{pk}, c_{0}, c_{1}, s): \exists ~(m, w) ~s.t.~ \text {Ext}\big (\textsf {Pub}(\textit{pk}, c_{0}, w), s\big )\oplus m=c_{1} \wedge (c_0, w)\in \texttt {R}_{\mathcal {V}}\},$$

where \(\textit{pk}\in \mathcal {PK}\), \(m\in \{0, 1\}^{\ell }\), w is the witness of \(c_{0}\in \mathcal {V}\) (i.e., \((c_0, w)\) belongs to the relation \(\texttt {R}_{\mathcal {V}}\) defined by \(\mathcal {V}\)) and s is a random seed from \(\{0, 1\}^{\tau }\).

More concretely, our construction with message space \(\{0, 1\}^{\ell }\) consists of four efficient algorithms PKE = (Setup, KeyGen, Enc, Dec):

Setup(1\(^{\kappa }\)): given a security parameter \(\kappa \), the algorithm runs Param\((1^{\kappa })\) and \(\textsf {Gen}(1^{\kappa })\) to generate \(params=(\mathcal {G}, \mathcal {C}, \mathcal {V}, \mathcal {HK}, \mathcal {PK}, \mathcal {K}, \mathrm {\Lambda }, \mu )\) and the common reference string crs. It then outputs \(pp=(params, crs).\)

KeyGen(pp): given parameters pp, the algorithm samples a uniform secret hash key hk and outputs the public and secret key pair \((pk, sk)=(\mu (hk), hk).\)

Enc(pk, m): on input pk and a message \(m\in \{0, 1\}^{\ell }\), the algorithm samples \(c_{0}\in \mathcal {V}\) with witness w, chooses \(s\leftarrow \{0, 1\}^{\tau }\), and outputs the ciphertext \(ct=(c_{0},\) \(c_{1}, s, \pi )\), where \(c_{1}=\text {Ext}\big (\textsf {Pub}(pk, c_{0}, w), s\big )\oplus m, ~\pi =\textsf {Prov}\big ((pk, c_{0}, c_{1}, s);(m, w)\big ).\)

Dec(sk, ct): given secret key sk and a ciphertext \(ct=(c_{0}, c_{1}, s, \pi )\), the algorithm first checks if \(\textsf {Verf}\big ((\mu (sk), c_{0}, c_{1}, s), \pi \big ) =1\) (Note that pk here is computed from secret key sk, which is important for achieving the enchanced security). If not, returns \(\bot \). Otherwise, it recovers the message by computing \(m=\text {Ext}\big (\textsf {Priv}(sk, c_{0}), s\big )\oplus c_{1}.\)

We recall that the algorithm \(\textsf {Priv}(sk, c)\) computes the (public-key-malleable) projective hash function \(\mathrm {\Lambda }_{sk}(c)\) with secret hash key \(sk=hk\) for any \(c\in \mathcal {C}\) and \(\textsf {Pub}(pk, c_{0}, w)\) evaluates \(\mathrm {\Lambda }_{sk}(c_{0})\) with public key \(pk=\mu (sk)\) and the witness w of \(c_{0}\in \mathcal {V}\). Regarding the correctness, it follows easily from the fact that \(\textsf {Pub}(pk, c_0, w)=\mathrm {\Lambda }_{sk}(c_0)=\textsf {Priv}(sk, c_0)\) for any \(c_0\in \mathcal {V}\) with witness w as well as the completeness of the tSE-NIZK proof system \(\mathrm {\Pi }\).

Remark 2

We remark that the generic construction is similar to [38] from a high level, but the underlying HPS needs to be carefully refined for our purpose. More precisely, the main differences of this construction from [38] are reflected in the following aspects: (1) it is built upon a refined HPS with some extra properties, e.g., \(\mathcal {T}\)-public-key malleability and public-key collision resistance; (2) the consistency of ciphertext is verified with sk instead of pk, which is crucial for achieving our security; (3) its security analysis in the stronger model is much more complicated, although the framework seems similar. A high-level idea of the proof is shown below, whereas the details are given in the full version due to the limited pages.

Theorem 1

Assuming that PM-HPS is a \(\epsilon (\kappa )\)-smooth HPS with \(\mathcal {T}_{pm}\)-public-key malleability and public-key collision resistance, \(\text {Ext}\) is an average-case \((\log |\mathcal {K}|-\lambda , \varepsilon (\kappa ))\)-strong extractor and \(\mathrm {\Pi }\) is a tSE-NIZK proof system, then the proposed construction is \((\lambda , \mathcal {T})\)-\(\mathrm {sLTR}\)-\(\mathrm {CCA}\) secure for any \(\lambda \le \log |\mathcal {K}|-\ell -\omega (\log \kappa )\) and , where \(\ell \) is the length of encrypted message, \(\varepsilon (\kappa )\) and \(\epsilon (\kappa )\le (2^{\ell }-1)/|\mathcal {K}|\) are negligible in \(\kappa \), and . Particularly, for all parameter \(\kappa \) and PPT adversary \(\mathcal {A}\), it holds that

$$ \begin{array}{rcl} Adv_{\mathcal {A}, {\textsf {PKE}}, \mathcal {T}}^{\lambda \text {-sLTR-CCA}}(\kappa ) &{} \le &{} 2(Adv_{\textsf {PM-HPS}, \mathcal {B}}^{\mathrm {SMP}}({\kappa })+\epsilon (\kappa )+\varepsilon (\kappa ))+Adv_{\textsf {PM-HPS},\mathcal {B}'}^{\mathrm {PKC}}(\kappa ) \\ &{}&{} + ~ Q_t \cdot p(\kappa )\cdot 2^{\lambda }\cdot (1/|\mathcal {K}|+\epsilon )+negl(\kappa ). \end{array} $$

Proof

(Sketch). In an overview, the leakage oracle could be perfectly simulated since the simulator always possesses the secret key. Moreover, the \(\mathcal {T}\)-type tampering queries could be properly answered by exploiting the public-key malleability together with the tSE property of NIZK. Thus, once all the tampering queries are well processed, the leakage-resilience of the construction can be easily reduced to the underlying CPA secure PKE directly derived from HPS.

4 Construction of \((\alpha , \mathcal {T})\)-sLTR-CCA Secure PKE

In this part, we show that a slightly adapted version of the previous construction (in Sect. 3) can achieve \((\alpha , \mathcal {T})\)-\(\mathrm {sLTR}\)-\(\mathrm {CCA}\) security. In particular, the strong extractor Ext will never be used. For simplicity, we just present the different algorithms, exactly the encryption and decryption algorithms, in the following:

Enc(pk, m): on input pk and \(m\in \mathcal {M}\), it samples \(c_{0}\in \mathcal {V}\) with witness w, chooses a random seed s, and computes \(c_{1}=\textsf {Pub}(pk, c_{0}, w)\cdot m\) and \(\pi =\textsf {Prov}\big ((pk, c_{0}, c_{1});(m, w)\big )\). Finally, it outputs the ciphertext \(ct=(c_{0}, c_{1}, \pi )\).

Dec(sk, ct): on input sk and \(ct=(c_{0}, c_{1}, \pi )\), the algorithm first verifies whether \(\textsf {Verf}\big ((\mu (sk), c_{0}, c_{1}), \pi \big )=1.\) If not, returns \(\bot \). Otherwise, it recovers the message by computing \(m=c_{1}/\textsf {Priv}(sk, c_{0}).\)

The correctness holds as analyzed before. Like the previous scheme, there is also a similar underlying PKE w.r.t. this adapted version. Similar to the proof given in the previous section, the leakage-resilience property of this construction essentially inherits from the underlying \(\textsf {PKE}'\). Therefore, if \(\textsf {PKE}'\) is CPA-secure against auxiliary-input leakage, then the construction can be proven secure against both the auxiliary-input and tampering attacks with a similar proof idea. However, it cannot realize tamper-resilience w.r.t. the minimal restriction, i.e., \((f_t, ct)\ne (I, ct^*)\), the reason for which will be explained as below.

Theorem 2

Assuming that PM-HPS is a \(\epsilon (\kappa )\)-smooth HPS with \(\mathcal {T}_{pm}\)-public-key malleability and public-key collision resistance, and \(\mathrm {\Pi }\) is a tSE-NIZK proof system, if the underlying \(\textsf {PKE}'\) constructed only from PM-HPS is \(\alpha \)-\(\mathrm {LR}\)-\(\mathrm {CPA}\) secure, then the above construction is \((\alpha , \mathcal {T})\)-\(\mathrm {sLTR}\)-\(\mathrm {CCA}\) secure for \(\alpha \)-hard to invert functions and tampering functions \(\mathcal {T}=\mathcal {T}_{pm}\), where \(\epsilon (\kappa )\) is negligible in \(\kappa \). Particularly, for all parameter \(\kappa \) and PPT adversary \(\mathcal {A}\), it holds that

$$ \begin{array}{rcl} Adv_{\mathcal {A}, {\textsf {PKE}}, \mathcal {T}}^{\alpha \text {-sLTR-CCA}}(\kappa )\le & {} 2Adv_{\textsf {PKE}', \mathcal {A}}^{\alpha \text {-LR-CPA}}(\kappa )+Adv_{\textsf {PM-HPS},\mathcal {B}'}^{\mathrm {PKC}}(\kappa )+negl(\kappa ). \end{array} $$

The proof idea is similar to the previous scheme, except that (1) the leakage-resilience of this construction is reduced to a PKE scheme resilient to auxiliary-input and (2) we need not to process all queries (\(f_{t}, ct\)) s.t. \(ct=ct^*, f_{t}\ne I\) and \(f_{t}(sk)=sk\) since the definition of \((\alpha , \mathcal {T})\)-sLTR-CCA security requires that \((f_{t}(sk), ct)\ne (sk, ct^*)\) for each allowed tampering query \((f_t, ct)\). In fact, the main point of achieving tamper-resilience w.r.t. the restriction \((f_t, ct)\ne (I, ct^*)\) (rather than \((f_{t}(sk), ct)\ne (sk, ct^*)\)) is that \(f_{t}\ne I\) implies \(f_{t}(sk)\ne sk\) with an overwhelming probability. For the \((\lambda , \mathcal {T})\)-sLTR-CCA security, this is possible as sk may still have high min-entropy even conditioned on the \(\lambda \)-bit leakage. In the context of auxiliary input leakage, however, the leakage may reveal the whole entropy of sk, thus we cannot derive \(f_{t}(sk)\ne sk\) from \(f_{t}\ne I\). This is why we have to restrict \((f_{t}(sk), ct)\ne (sk, ct^*)\) for each tampering query \((f_t, ct)\) in the definition of \((\alpha , \mathcal {T})\)-sLTR-CCA security.

5 Instantiations

In this section, we present some instantiations based on the standard assumptions such as DDH and d-LIN assumption, which shows that the enhanced security notions can be achieved on basis of well-known hardness assumptions.

5.1 PM-HPS from DDH Assumption

The public-key-malleable HPS PM-HPS = (Param, Pub, Priv) based on the DDH assumption is described as below. In fact, it is the same as the HPS presented in [10, 38], then we further show it also satisfies the extended properties for our applications. First, we recall the description of PM-HPS as follows:

Param(\(1^{\kappa }\)): on input a security parameter \(\kappa \), it generates \((\mathbb {G}, g, p)\leftarrow \textsf {Group}(1^{\kappa })\), and then chooses \(g_{1}, g_{2}\leftarrow \mathbb {G}\) and outputs \(params=(\mathcal {G}, \mathcal {C}, \mathcal {V}, \mathcal {HK}, \mathcal {PK}, \mathcal {K}, \mathrm {\Lambda }, \mu )\):

  • \(\mathcal {G}=(\mathbb {G}, p, g_{1}, g_{2}), \mathcal {C}=\mathbb {G}\times \mathbb {G}, \mathcal {V}=\{(g_{1}^{w}, g_{2}^{w}): w\in \mathbb {Z}_{p}\}, \mathcal {HK}=\mathbb {Z}_{p}\times \mathbb {Z}_{p}, \mathcal {PK}=\mathbb {G}\), \(\mathcal {K}=\mathbb {G}\).

  • \(\textit{pk}=\mu (hk)=g_{1}^{x_{1}}g_{2}^{x_{2}}\), \(\mathrm {\Lambda }_{hk}(c)=c_{1}^{x_{1}}c_{2}^{x_{2}}\) for any \(hk=(x_{1}, x_{2})\in \mathcal {HK}\) and \(c=(c_{1}, c_{2})\in \mathcal {C}\).

Pub(\({\textit{pk}, c, w}\)): given public key \(\textit{pk}\) and ciphertext \(c=(c_{1}, c_{2})\in \mathcal {V}\) with witness \(w\in \mathbb {Z}_{p}\), the algorithm computes the hash value as \(\textit{pk}^{w}\).

Priv(hk, c): on input secret key \(hk=(x_{1}, x_{2})\in \mathcal {HK}\) and any ciphertext \(c=(c_{1}, c_{2})\in \mathcal {C}\), this algorithm computes the hash value on c as \(c_{1}^{x_{1}}c_{2}^{x_{2}}\).

The projectiveness and smoothness of this construction could be readily analyzed as in [10, 33]. In the following, we mainly show that it satisfies the properties of \(\mathcal {T}\)-public-key malleability and public-key collision resistance. Before going ahead, we first define the class \(\mathcal {T}\) of functions associated with the former property, which is exactly a family of restricted affine functions on \(\mathcal {HK}\) defined as \(\mathcal {T}_{raff }=\{f_{(a,\varvec{b})}(hk)=(ax_1+b_1, ax_2+b_2): a\in \mathbb {Z}_p, hk=(x_1,x_2), \varvec{b}=(b_1, b_2)\in \mathcal {HK}\}.\) Now we proceed to show the properties mentioned above:

\(\mathcal {T}_{\text {raff}}\)-public-key malleability: For all \(hk=(x_1, x_2)\in \mathcal {HK}\) and \(f_{(a, \varvec{b})}(\cdot )\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}=(b_1, b_2)\in \mathcal {HK}\), it is easy to observe that

$$\mu (f_{(a, \varvec{b})}(hk))=\mu (ax_1+b_1, ax_2+b_2)=g_{1}^{ax_{1}+b_1}g_{2}^{ax_{2}+b_2}=(g_{1}^{x_{1}}g_{2}^{x_{2}})^{a}\cdot g_1^{b_1}\cdot g_2^{b_2}.$$

Then for all \(\textit{pk}=\mu (hk)\in \mathcal {PK}\) and \(f_{(a, \varvec{b})}\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}=(b_1, b_2)\in \mathcal {HK}\), the \(\mathcal {T}_{raff }\)-public-key transformer \(\texttt {Trans}:\mathcal {T}_{raff }\times \mathcal {PK}\rightarrow \mathcal {PK}\) is defined as: \(\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))=\mu (hk)^a\cdot g_1^{b_1}\cdot g_2^{b_2}.\) Now due to \(\mu (hk)=g_{1}^{x_{1}}g_{2}^{x_{2}}\), we have that \(\mu (f_{(a, \varvec{b})}(hk))=\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))\).

Public-Key Collision Resistance: Under the discrete logarithm (DL) assumption, the PKC problem associated with the above PM-HPS is hard. Suppose for contradiction that there exists an adversary \(\mathcal {A}\) that can break the property of public-key collision resistance, i.e., finding \(hk=(x_1, x_2)\ne (x'_1, x'_2)=hk'\) s.t. \(\mu (hk)=\mu (hk')\), then we can construct an efficient algorithm \(\mathcal {B}\) that can solve the DL problem by invoking \(\mathcal {A}\).

Given a random DL instance \((\mathbb {G}, p, g, h)\), the algorithm \(\mathcal {B}\) aiming at computing \(\alpha =\log _{g}h\) sets \(g_1=g\) and \(g_2=h\), and then produces and returns the public parameters params to \(\mathcal {A}\). After that, if \(\mathcal {A}\) eventually outputs a collision \(hk=(x_1, x_2)\ne (x'_1, x'_2)=hk'\) of \(\mu \) s.t. \(\mu (hk)=\mu (hk')\), then we have \(g_{1}^{x_{1}+\alpha x_{2}}=g_{1}^{x'_{1}+\alpha x'_{2}}\) and can get from the equation that \(\alpha =\frac{x_1-x'_1}{x'_2-x_2}\). Hence, the PKC problem associated with PM-HPS is as hard as the DL problem.

As to the hardness of SMP problem, it is directly from the hardness of DDH problem, the detailed analysis of which can be found in [10, 33].

The preceding PM-HPS is constructed directly from the DDH problem. Next, we present its generalized version, as shown in [33, 38]. More concretely, the generalized construction is depicted as follows:

Param(\(1^{\kappa }\)): on input a security parameter \(\kappa \), the algorithm generates \((\mathbb {G}, g, p)\leftarrow \textsf {Group}(1^{\kappa })\), and then chooses \(\varvec{g}=(g_{1}, \cdots , g_{l})\in \mathbb {G}^{l}\) where \(l\ge 2\log p+\omega (\log \kappa )\), and sets \(params=(\mathcal {G}, \mathcal {C}, \mathcal {V}, \mathcal {HK}, \mathcal {PK}, \mathcal {K}, \mathrm {\Lambda }, \mu )\) as:

  • \(\mathcal {G}=(\mathbb {G}, p, \varvec{g}), \mathcal {C}=\mathbb {G}^{l}=\{(g_{1}^{r_{1}}, \cdots , g_{l}^{r_{l}}): r_{1}, \cdots , r_{l}\in \mathbb {Z}_{p}\}, \mathcal {V}=\{(g_{1}^{w}, \cdots , g_{l}^{w}): w\in \mathbb {Z}_{p}\}, \mathcal {HK}=\mathbb {Z}_{2}^{l}, \mathcal {PK}=\mathbb {G}\), \(\mathcal {K}=\mathbb {G}\).

  • \(\textit{pk}=\mu (hk)=\prod _{i=1}^{l}g_{i}^{x_{i}}\), \(\mathrm {\Lambda }_{hk}(c)=\prod _{i=1}^{l}c_{i}^{x_{i}}\) for any \(hk=(x_{1}, \cdots , x_{l})\in \mathcal {HK}\) and \(c=(c_{1}, \cdots , c_{l})\in \mathcal {C}\).

Pub(\({\textit{pk}, c, w}\)): given pubic key \(\textit{pk}\) and ciphertext \(c=(c_{1}, \cdots , c_{l})\in \mathcal {V}\) with witness \(w\in \mathbb {Z}_{p}\), the algorithm computes the hash value as \(\textit{pk}^{w}\).

Priv(hk, c): given \(hk=(x_{1}, \cdots , x_{l})\in \mathcal {HK}\) and \(c=(c_{1}, \cdots , c_{l})\in \mathcal {C}\), the algorithm evaluates the hash value on c as \(\prod _{i=1}^{l}c_{i}^{x_{i}}\).

The projectiveness and smoothness could be analyzed similarly to [38]. We notice that smoothness holds only if \(l\ge 2\log p+\omega (\log \kappa )\), due to the generalized leftover hash lemma. In the following, we mainly demonstrate that the construction satisfies both the \(\mathcal {T}\)-public-key malleability and public-key collision resistance property. With respect to the function class \(\mathcal {T}\) associated with the former property, it is formalized in a similar way as before. Specifically, it is defined as \(\mathcal {T}_{raff }=\{f_{(a,\varvec{b})}(hk)=(ax_1+b_1,\cdots , ax_l+b_l): a\in \mathbb {Z}_p, hk=(x_1,\cdots ,x_l), \varvec{b}=(b_1, \cdots , b_l)\in \mathcal {HK}\}.\) Now we continue to show the properties as desired:

\(\mathcal {T}_{\text {raff}}\)-Public-Key Malleability: For all \(hk=(x_1, \cdots , x_l)\in \mathcal {HK}\) and \(f_{(a, \varvec{b})}(\cdot )\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}=(b_1, \cdots , b_l)\in \mathcal {HK}\), it is easy to observe that

$$\mu (f_{(a, \varvec{b})}(hk))=\mu (ax_1+b_1,\cdots , ax_l+b_l)=\prod _{i=1}^{l}g_{i}^{ax_{i}+b_i}=(\prod _{i=1}^{l}g_{i}^{x_{i}})^{a}\cdot \prod _{i=1}^{l}g_i^{b_i}.$$

Then for all \(\textit{pk}=\mu (hk)\in \mathcal {PK}\) and \(f_{(a, \varvec{b})}\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}=(b_1, \cdots , b_l)\in \mathcal {HK}\), we define the \(\mathcal {T}_{raff }\)-public-key transformer \(\texttt {Trans}:\mathcal {T}_{raff }\times \mathcal {PK}\rightarrow \mathcal {PK}\) as: \(\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))=\mu (hk)^a\cdot \prod _{i=1}^{l}g_i^{b_i}.\) Following from \(\mu (hk)=\prod _{i=1}^{l}g_{i}^{x_{i}}\), we have \(\mu (f_{(a, \varvec{b})}(hk))=\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))\).

Public-Key Collision Resistance: Under the DL assumption, the PKC problem associated with the above PM-HPS is hard. Suppose that there exists an efficient adversary \(\mathcal {A}\) that can break the property of public-key collision resistance, i.e., finding \(hk=(x_1, \cdots , x_l)\ne (x'_1, \cdots , x'_l)=hk'\) s.t. \(\mu (hk)=\mu (hk')\), then we can design an efficient algorithm \(\mathcal {B}\) to solve the DL problem by invoking \(\mathcal {A}\).

Given a random DL instance \((\mathbb {G}, p, g, h)\), the algorithm \(\mathcal {B}\) aiming at computing \(\alpha =\log _{g}h\) randomly picks \(j\in [l], \beta _i \in \mathbb {Z}_p\) for all \(i\in [l]\setminus \{j\}\), and sets \(\varvec{g}=(g_{1}, \cdots , g_{l})\) as \(g_i=g^{\beta _i}\) for \(i\ne j\) and \(g_j=h\).

Then, it produces the public parameters params and sends them to the adversary \(\mathcal {A}\). After that, if \(\mathcal {A}\) eventually outputs a collision \(hk=(x_1, \cdots , x_l)\ne (x'_1, \cdots , x'_l)=hk'\) s.t. \(\mu (hk)=\mu (hk')\), then we have that \(\prod _{i=1}^{l}g_{i}^{x_{i}}=\prod _{i=1}^{l}g_{i}^{x'_{i}}\) which is equivalent to \(h^{x_j-x'_j}=\prod _{i\ne j}g^{\beta _i(x'_i-x_i)}\). Furthermore, we get that \(\alpha =\frac{\sum _{i\ne j}\beta _i(x'_i-x_i)}{x_j-x'_j}\) conditioned on \(x_j\ne x'_j\).

For analyzing \(\mathcal {B}\)’s success probability, we denote by \(\textsf {coll}\) the event that \(\mathcal {A}\) outputs \(hk\ne hk'\) but \(\mu (hk)=\mu (hk')\). Then the probability of \(\mathcal {B}\) solving the DL problem is \(\Pr [\mathcal {B}(\mathbb {G}, p, g, h)=\alpha ] \ge \Pr [\mathcal {B}(\mathbb {G}, p, g, h)=\alpha \wedge \textsf {coll} \wedge x_j\ne x'_j] \ge \frac{2}{l}Adv_{\textsf {PM-HPS},\mathcal {A}}^{\mathrm {PKC}}(\kappa ). \)

Hence, the PKC problem associated with PM-HPS is hard as long as the DL assumption holds. As to the hardness of SMP problem, it follows readily from the hardness of the (generalized) DDH problem [12].

5.2 PM-HPS from d-LIN Assumption

The public-key malleable HPS PM-HPS = (Param, Pub, Priv) based on d-LIN assumption is described below, which is in fact the same as the HPS in [38].

Param(\(1^{\kappa }\)): on input parameter \(\kappa \), it generates \((\mathbb {G}, g, p)\leftarrow \textsf {Group}(1^{\kappa })\), then randomly chooses \(\mathbf A \in \mathbb {Z}_{p}^{d\times (d+1)}\) and outputs \(params=(\mathcal {G}, \mathcal {C}, \mathcal {V},\) \( \mathcal {HK}, \mathcal {PK}, \mathcal {K}, \mathrm {\Lambda }, \mu )\):

  • \(\mathcal {G}=(\mathbb {G}, g, p, g^\mathbf{A }), \mathcal {C}=\{g^{\varvec{r}^{\top }}: \varvec{r}\in \mathbb {Z}_{p}^{d+1}\}, \mathcal {V}=\{g^{\varvec{w}^{\top }{} \mathbf A }: \varvec{w}\in \mathbb {Z}_{p}^{d}\}, \mathcal {HK}=\mathbb {Z}_{p}^{d+1}, \mathcal {PK}=\mathbb {G}^{d\times 1}\), \(\mathcal {K}=\mathbb {G}\).

  • \(\textit{pk}=\mu (hk)=g^\mathbf{A \varvec{x}}\), \(\mathrm {\Lambda }_{hk}(c)=g^{\varvec{r}^{\top }\varvec{x}}\) for \(hk=\varvec{x}\in \mathcal {HK}\) and \(c=g^{\varvec{r}^{\top }}\in \mathcal {C}\).

Pub(\({\textit{pk}, c, \varvec{w}}\)): given \(\textit{pk}=g^\mathbf{A \varvec{x}}\) and \(c=g^{\varvec{w}^{\top }{} \mathbf A }\in \mathcal {V}\) with witness \(\varvec{w}\in \mathbb {Z}_{p}^{d}\), the algorithm computes \(g^{\varvec{w}^{\top }{} \mathbf A \varvec{x}}\).

Priv(hk, c): given \(hk=\varvec{x}\in \mathcal {HK}\) and \(c=g^{\varvec{r}^{\top }}\in \mathcal {C}\), it computes \(g^{\varvec{r}^{\top }\varvec{x}}\).

The projectiveness and smoothness could be shown as in [38], and the hardness of SMP problem follows readily from that of \(\mathcal {L}_d\)-MDDH problem. What remains to do is to show this construction satisfies both the \(\mathcal {T}\)-public-key malleability and public-key collision resistance property as well. As to the function class \(\mathcal {T}\) associated with the malleability property, it is defined similarly as before. More precisely, \(\mathcal {T}_{raff }=\{f_{(a,\varvec{b})}(hk)=a\varvec{x}+\varvec{b}: a\in \mathbb {Z}_p, hk=\varvec{x}, \varvec{b}\in \mathcal {HK}\}.\) Now we continue to show the desired properties below:

\(\mathcal {T}_{{raff}}\)-Public-Key Malleability: For all \(hk=\varvec{x}\in \mathcal {HK}\) and \(f_{(a, \varvec{b})}\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}\in \mathcal {HK}\), it is easy to observe that

$$\mu (f_{(a, \varvec{b})}(hk))=\mu (a\varvec{x}+\varvec{b})=g^\mathbf{A (a\varvec{x}+\varvec{b})}=(g^\mathbf{A \varvec{x}})^{a}\cdot g^\mathbf{A \varvec{b}}.$$

Then for all \(\textit{pk}=\mu (hk)\in \mathcal {PK}\) and \(f_{(a, \varvec{b})}\in \mathcal {T}_{raff }\) with \(a\in \mathbb {Z}_p\) and \(\varvec{b}\in \mathcal {HK}\), we define the \(\mathcal {T}_{raff }\)-public-key transformer \(\texttt {Trans}:\mathcal {T}_{raff }\times \mathcal {PK}\rightarrow \mathcal {PK}\) as: \(\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))=\mu (hk)^a\cdot g^\mathbf{A \varvec{b}}.\) Following from that \(\mu (hk)=g^\mathbf{A \varvec{x}}\), we get \(\mu (f_{(a, \varvec{b})}(hk))=\texttt {Trans}(f_{(a, \varvec{b})}, \mu (hk))\).

Public-Key Collision Resistance: Under the \(\mathcal {L}_d\)-MDDH assumption, the PKC problem associated with the above construction is intractable. Suppose for contradiction that there exists a PPT adversary \(\mathcal {A}\) that can find two different secret key \(hk=(x_1, x_2)\ne (x'_1, x'_2)=hk'\) s.t. \(\mu (hk)=\mu (hk')\), then we can construct an efficient algorithm \(\mathcal {B}\) that can use \(\mathcal {A}\) to solve the \(\mathcal {L}_d\)-MDDH problem.

Given \((\mathbb {G}, p, g, g^\mathbf{A }, g^{\varvec{u}^{\top }})\), where \(\varvec{u}^{\top }=\varvec{w}^{\top }{} \mathbf A \) or \(\varvec{r}^{\top }\) with \(\varvec{w}\leftarrow \mathbb {Z}_p^d\) and \(\varvec{r}\leftarrow \mathbb {Z}_p^{d+1}\), the algorithm \(\mathcal {B}\) sets \(\mathcal {G}=(\mathbb {G}, p, g, g^\mathbf{A })\) and generates the public parameters params. After receiving params, \(\mathcal {A}\) outputs a pair of secret keys \((hk, hk')=(\varvec{x}, \varvec{x}')\). If they are distinct but satisfies \(\mu (hk)=\mu (hk')\), i.e., \(g^\mathbf{A \varvec{x}}=g^\mathbf{A \varvec{x}'}\), we get \(g^\mathbf{A (\varvec{x}-\varvec{x}')}=g^{\varvec{0}}\). Then \(\mathcal {B}\) sets \(\varvec{v}=\varvec{x}-\varvec{x}'\) and distinguishes \(\varvec{u}^{\top }=\varvec{w}^{\top }{} \mathbf A \) from \(\varvec{u}^{\top }=\varvec{r}^{\top }\) by checking if \(g^{\varvec{u}^{\top }\varvec{v}}=g^0\). Obviously, \(\mathcal {B}\) successfully solves the \(\mathcal {L}_d\)-MDDH problem as long as \(\mathcal {A}\) breaks the public-key collision resistance property.

At last, with respect to efficient constructions of tSE-NIZKs, they could be built in a generic and efficient way from any standard CCA-secure encryption scheme and NIZK argument system, just as shown and argued in [11, 13].

6 Comparison with Related Works

Next we give a brief comparison of our schemes with those works [11, 19, 38] that rely not on hardware assumptions. CCA security against both key-leakage and tampering attacks was initially studied by Damgård et al. [11], where they introduced the notion of BLT-CCA security. Their main idea is to reduce tampering to leakage. Although this enables to achieve tamper-resilience against arbitrary tampering attacks (or arbitrary key-relations), the total number of tampering attacks, due to the limited amount of key-leakage, must be strictly bounded and no post-tampering attempts are permitted (i.e., tampering attacks launched after observing challenge ciphertext). Moreover, this method leads to a significant reduction of the amount of leakage tolerated by the construction. In contrast, [38] revisited the problem from an alternative perspective and introduced the notion of LTR-CCA security, where the adversary is allowed to issue an arbitrary polynomial of tampering queries even after challenge phase. Furthermore, it can be realized in a more flexible way without any dependence between tampering and leakage. However, there is still a restriction on their security that the adversary is not allowed to issue any challenge-dependent (for short, C.-Dep.) tampering query. Instead, our enhanced security notion called sLTR-CCA security only stipulates that \((f_t, ct)\ne (I, ct^*)\), instead of \(ct\ne ct^*\).

As to efficiency, our constructions are similar to [11, 38], which are all built upon tSE-NIZK proof system, but they can achieve a better leakage-resilience than [11] and a higher security level than [38]. Recently, Faonio et al. [19] showed that the already existing scheme [34] can also achieve BLT security, and thus obtained the first direct, pairing free IND-CCA BLT secure PKE without relying on tSE-NIZK. However, we do not know how to realize sLTR-CCA security without using tSE-NIZK yet, and we leave it as an interesting future work. The results and comparison with related works is summarized in Table 1.

Table 1. Brief comparison with related works
Full size table

7 Conclusion

We introduced an enhanced security against both key-leakage and tampering attacks. Then, we show that our new security is achievable by presenting a generic construction on the basis of public-key-malleable HPSs. Our construction can tolerate a large amount of key-leakage and resist an arbitrary polynomial number of restricted tampering attempts. Moreover, we show that the construction with slight modifications can also achieve chosen-ciphertext security against both auxiliary-input leakage and tampering attacks. However, our instantiations based on DDH/DLIN assumption only achieve security against affine-tampering attacks, due to the restricted public-key malleability of the PM-HPS. We left open the constructions of PM-HPS with more general public-key malleability and sLTR-CCA secure PKE against more wider tampering function classes. In addition, designing CCA-secure PKE against both challenge-dependent leakage and tampering attacks is very meaningful, which is left as future work.