Rate-1 Key-Dependent Message Security via Reusable Homomorphic Extractor Against Correlated-Source Attacks

Abstract

In this work, we first present general methods to construct information rate-1 PKE that is $\mathsf {KDM}^{(n)}$-secure with respect to block-affine functions for any unbounded polynomial n. To achieve this, we propose a new notion of extractor that satisfies reusability, homomorphic, and security against correlated-source attacks, and show how to use this extractor to improve the information rate of the $\mathsf {KDM}$-secure PKE of Brakerski et al. (Eurocrypt 18). Then, we show how to amplify $\mathsf {KDM}$ security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting.

Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates $1-o(1)$ against a slightly smaller yet still general class – block leakage functions. We can instantiate the required building blocks from $\mathsf {LWE}$ or $\mathsf {DDH}$.

1 Introduction

The classic notion of semantic security by Goldwasser and Micali [18] guarantees security when the secret key is generated randomly and independently of the message being encrypted. This notion however, is not sufficient in various scenarios, e.g., [1, 10, 13, 24]. To tackle this issue, [8, 9] formally defined Key Dependent Message ($\mathsf {KDM}$) security, which requires $\mathsf {Enc}(\mathsf {pk}, \mathfrak {f}(\mathsf {sk}))$ to be indistinguishable from $\mathsf {Enc}(\mathsf {pk}, 0)$ for all $\mathfrak {f}$ in a certain class. The setting can be generalized to n-users, i.e., $\mathsf {KDM}^{(n)}$-security, where security holds even when the attacker obtains the encryption of $\mathfrak {f}(\mathsf {sk} _1,\dots , \mathsf {sk} _n)$ under some user’s (public) key. The community has established various theoretical feasibility results – we know how to construct $\mathsf {KDM}^{(n)}$-secure $\mathsf {PKE}$ for unbounded polynomial n from the $\mathsf {LWE}$ [5], $\mathsf {DDH}$ [9], or $\mathsf {LPN}$ [5, 16, 23] assumption, for bounded polynomial n from $\mathsf {QR}$/$\mathsf {DCR}$ assumption [10], and for $n=1$ from $\mathsf {CDH}$ [12].

On the other hand however, all the prior constructions have relatively small information rate¹ even for the class of linear functions, resulting in very large overhead in scenarios that require encrypting large data, e.g., storing large encrypted files in the cloud, or streaming encrypted high-resolution movies over the internet. To remove this limitation and enhance usability, it is necessary to determine whether a low information rate is inherent for KDM security.

As folklore, this issue (low information rate) can be solved easily for regular $\mathsf {PKE}$, as one can always achieve rate $1-o(1)$ by using the technique of hybrid encryption (the KEM-DEM paradigm). It is however, not clear whether $\mathsf {KDM}$ security can be preserved under a general hybrid encryption [22]. This direction has remained an important open problem (ref. [9, 10]). Therefore, we ask:

Main Question: Can we construct a $\mathsf {KDM}^{(n)}$-secure $\mathsf {PKE}$ with better information rate, e.g. $1-o(1)$, even for $n=1$ and linear functions?

1.1 Our Contributions

This work answers the main question and makes the following contributions:

Contribution 1. We show how to construct a $\mathsf {KDM}^{(1)}$-secure $\mathsf {PKE}$ with information rate $1-o(1)$ with respect to block-affine functions, a slightly more restricted class than that of bit-affine functions. To achieve this, we first propose a new primitive – reusable homomorphic extractor against correlated-source attacks, and instantiate it based on $\mathsf {DDH}$ or $\mathsf {LWE}$. Next, we show how to use this primitive to improve the approach of Batch Encryption ($\mathsf {BE}$) [12], which was used to derive $\mathsf {KDM}^{(1)}$-secure $\mathsf {PKE}$ (albeit low information rates.)

Particularly, we identify that $\mathsf {BE}$ implies a weak hash proof system ($\mathsf {wHPS}$) with important additional properties. Then we show that our new extractor can be integrated with such a $\mathsf {wHPS}$ to achieve $\mathsf {KDM}^{(1)}$-security with information rate $1-o(1)$. Our proof technique connects $\mathsf {wHPS}$ and the new reusable homomorphic extractor in a novel way, which deviates from the prior simulation approach [5, 7, 9,10,11,12]. The new extractor and proof technique can be of independent interest.

Contribution 2. We show how to upgrade the above approach to achieve $\mathsf {KDM}^{(n)}$-secure $\mathsf {PKE}$ for unbounded polynomial n. Particularly, we identify the technical barrier of the current $\mathsf {BE}$-based approach [12], which inherently can only achieve a bounded polynomial n. To tackle this, we construct an enhanced variant of the current $\mathsf {BE}$ by adding a new reusable property. By using this stronger $\mathsf {BE}$ as the underlying building block of $\mathsf {wHPS}$, the scheme in Contribution 1 can be proved $\mathsf {KDM}^{(n)}$-secure for any unbounded polynomial n. For instantiations, we construct the required extractor and $\mathsf {BE}$ from $\mathsf {DDH}$ or $\mathsf {LWE}$. Thus, either of these assumptions implies $\mathsf {KDM}^{(n)}$-secure $\mathsf {PKE}$ with the optimal information rate, i.e., $1-o(1)$.

Our design of $\mathsf {KDM}$-$\mathsf {PKE}$ is quite modular, which might open a path for further constructions from other assumptions, as long as we can construct the required building blocks.

Contribution 3. We generalize the above approach in two directions. First, we show that the class of block-affine function is still sufficient for $\mathsf {KDM}$ amplification to the class of general bounded-sized circuits via a variant of the technique in [4], even the class of block-affine functions is more restricted, i.e., it does not contain all projection functions, so that the generic $\mathsf {KDM}$ amplification of Applebaum [4] does not work. Thus, the affine function class is still sufficiently general, and can yield more efficient constructions.

Second, we construct $\mathsf {KDM}^{(n)}$-secure $\mathsf {IBE}$ for unbounded n with the $1-o(1)$ information rate. The corresponding $\mathsf {KDM}$ function class here is slightly smaller than the allowable $\mathsf {KDM}$ class for our $\mathsf {PKE}$. We discuss this allowable class next. Moreover, the required building blocks can be instantiated based on $\mathsf {DDH}$ in the bilinear group or $\mathsf {LWE}$.

In addition to $\mathsf {KDM}$ security, our $\mathsf {PKE}$ schemes (both $\mathsf {DDH}$ and $\mathsf {LWE}$-based) are leakage resilient. The leakage rate is optimal, i.e., $1-o(1)$, against block leakage, which is slightly smaller than the general leakage class². The $\mathsf {IBE}$ schemes are as well leakage resilient. For the same class of leakage functions, the $\mathsf {IBE}$ leakage rate can achieve $1-o(1)$ under $\mathsf {LWE}$ or $\mathsf {DDH}$ with respect to some bilinear maps.

1.2 Technical Overview

In this section, we present a technical overview of our contributions. We start with the construction of $\mathsf {KDM}^{(1)}$-secure $\mathsf {PKE}$ with information rate $1-o(1)$. To achieve this target, we first identify several new properties from (Identity-based) weak Hash Proof Systems ($\mathsf {wHPS}$) [2, 21], Batch Encryption ($\mathsf {BE}$) [12], and randomness extractors [3], and then describe our new idea to integrate these properties. Before describing our new insights, we first review the following two important tools – $\mathsf {wHPS}$ and $\mathsf {BE}$.

(Weak) Hash Proof System. A hash proof system can be described as a key encapsulation mechanism that consists of four algorithms $(\mathsf {Setup},$$\mathsf {Encap}, \mathsf {Encap}^{*},\mathsf {Decap})$: (1) $\mathsf {Setup}$ generates a key pair $(\mathsf {pk},\mathsf {sk})$, (2) $\mathsf {Encap}(\mathsf {pk})$ outputs a pair $(\mathsf {CT},\mathsf {k})$ where $\mathsf {k}$ is a key encapsulated in a “valid” ciphertext $\mathsf {CT}$, (3) $\mathsf {Encap}^{*}(\mathsf {pk})$ outputs an “invalid” ciphertext $\mathsf {CT} ^{*}$, and (4) $\mathsf {Decap}(\mathsf {sk},\mathsf {CT})$ outputs a key $\mathsf {k} '$. A (weak) hash proof system needs to satisfy the following three properties:

• Correctness. For a valid ciphertext $\mathsf {CT}$, the $\mathsf {Decap}$ algorithm always outputs the encapsulated key $\mathsf {k} ^\prime$ such that $\mathsf {k} '=\mathsf {k}$, where .

• Ciphertext Indistinguishability. Valid ciphertexts and invalid ciphertexts are computationally indistinguishable, even given the secret key $\mathsf {sk}$. This property is essential for achieving leakage resilience and $\mathsf {KDM}$ security.

• Universal. The $\mathsf {wHPS}$ is $(\ell ,w)$-universal if given the public key $\mathsf {pk}$ and an invalid ciphertext $\mathsf {CT} ^*$, the decapsulated key length is $\ell$ and the conditional min-entropy of the decapsulation of $\mathsf {CT} ^*$ is greater or equal to w, i.e., $H_\infty (\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^*) \ \big | \ \mathsf {pk},\mathsf {CT} ^* ) \ge w$. A $\mathsf {wHPS}$ only requires this property to hold for a random invalid ciphertext, i.e. , while a full-fledged $\mathsf {HPS}$ requires it to hold for any invalid ciphertext.

We note that $\mathsf {wHPS}$ has been used to achieve leakage resilience ($\mathsf {LR}$) in prior work [2, 25]. Homomorphic $\mathsf {wHPS}$ has been used to achieve $\mathsf {KDM}^{(1)}$-security [27]. It was not clear whether $\mathsf {wHPS}$ can be used to achieve $\mathsf {KDM}^{(1)}$-security with the optimal information rate.

Batch Encryption [12]. A Batch Encryption ($\mathsf {BE}$) consists of four algorithms: $(\mathsf {Setup}, \mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$. The secret key is a vector $\varvec{x}\in \mathbb {Z}_B^{n}$ for $B,n\in \mathbb {N}$. The $\mathsf {Setup}$ algorithm simply outputs a random common reference string $\mathsf {CRS}$, and $\mathsf {KeyGen} (\mathsf {CRS}, \varvec{x})$ is a projection function that outputs (a short) hash value h of $\varvec{x}$ and $\mathsf {CRS}$. The encryption algorithm takes an $n\times B$ matrix $\mathbf {M}$ and $(\mathsf {CRS}, h)$ as input, and outputs a ciphertext $\mathsf {CT} \leftarrow \mathsf {Enc}((\mathsf {CRS},h),\mathbf {M})$. The decryption algorithm taking as input a ciphertext $\mathsf {CT}$ and a secret key $\varvec{x}$, can only recover $M_{i, x_i}$, i.e., the $x_i$-th entry in the i-th row, for $1\le i\le n$, while the other entries remain hidden even given the secret key $\varvec{x}$. The work [12] showed that $\mathsf {BE}$ can be instantiated from $\mathsf {LWE}$, $\mathsf {CDH}$, and $\mathsf {LPN}$ with the succinctness property, i.e. the size of |h| depends only on the security parameter and can be set as o(n). Using a succinct $\mathsf {BE}$ as a central building block, the work [12] constructed a $\mathsf {PKE}$  that simultaneously achieves $\mathsf {KDM}^{(1)}$-security for affine functions and leakage resilience with the optimal leakage rate, i.e., $1-o(1)$.

Even though the above tools have been demonstrated powerful, there are two common limitations for the current techniques – (1) $\mathsf {KDM}$-security can be achieved only for bounded users, and (2) the information rate is quite low, e.g., $\frac{1}{O(\lambda )}$. Next, we present our new insights to break these technical barriers.

Our New Insights 

We start with a simple observation that $\mathsf {BE}$ can be used to construct $\mathsf {wHPS}$ with additional structures, which are critical in achieving $\mathsf {KDM}$-security. Then we introduce our new variant of random extractor, and sketch its instantiations from $\mathsf {DDH}$ and $\mathsf {LWE}$. With all these preparations, we show our new ideas to achieve $\mathsf {KDM}$ security.

${\mathbf {\mathsf{{wHPS}}}}$ from ${\mathbf {\mathsf{{BE}}}}$. We can construct a $\mathsf {wHPS}$ from $\mathsf {BE}$ in the following simple way. $\mathsf {wHPS}.\mathsf {sk}$ is a random $\varvec{x} \in \mathbb {Z}_B^n$, and $\mathsf {wHPS}.\mathsf {pk} = (\mathsf {CRS}, h)$ where $\mathsf {CRS},h$ are generated according to the underlying $\mathsf {BE}$. The valid encapsulation algorithm $\mathsf {wHPS}.\mathsf {Encap}$ just samples a random vector $\varvec{k} = (k_1,\dots , k_n)^\top \in \mathbb {Z}_B^n$ as the encapsulated key and generates the ciphertext by $\mathsf {BE}.\mathsf {Enc}(\mathbf {M})$, where the i-th row of $\mathbf {M}$ is set as $(k_i,k_i, \dots , k_i)$ for $i\in [n]$. On the other hand, the invalid encapsulation algorithm $\mathsf {wHPS}.\mathsf {Encap}^*$ generates an invalid ciphertext $\mathsf {CT} ^* \leftarrow \mathsf {BE}.\mathsf {Enc}(\mathbf {M})$ by first sampling a random vector $\varvec{k}' = (k_1',\dots ,k_n')^\top$ and then setting the i-th row of $\mathbf {M}$ as $(k_i'+ 0, k_i'+1, \dots , k_i' + B-1)$ for $i\in [n]$. Moreover, the decapsulation algorithm $\mathsf {wHPS}.\mathsf {Decap}$ simply outputs the decryption result of $\mathsf {BE}.\mathsf {Dec}(\varvec{x},\mathsf {CT})$.

It is not hard to show that this construction is an $(n\log B,n\log B- |h|)$-universal $\mathsf {wHPS}$, which can be used to achieve a $\mathsf {LR}$-$\mathsf {PKE}$ that tolerates $(n \log B- |h| - k)$-bit leakage by using a $(k,\varepsilon )$-extractor (ref. [2, 25]).³ Particularly, the corresponding leakage resilient public-key encryption scheme $\mathsf {PKE}_1$ can be constructed as follows: $\mathsf {PKE}_1.\mathsf {pk} = \mathsf {wHPS}.\mathsf {pk}$ and $\mathsf {PKE}_1.\mathsf {sk} = \mathsf {wHPS}.\mathsf {sk}$. To encrypt a message m, the encryption algorithm first generates $(\mathsf {CT}, \varvec{k}) \leftarrow \mathsf {wHPS}.\mathsf {Encap}$ and samples $\varvec{r}$ as the randomness of a strong randomness extractor $\mathsf {Ext} (\cdot , \cdot )$, and then outputs $(\mathsf {CT}, \varvec{r},\mathsf {Ext} (\varvec{r}, \varvec{k}) + m)$ as the ciphertext.

Generally, a plain extractor is not sufficient to derive $\mathsf {KDM}$ security for $\mathsf {PKE}_1$ in the above paradigm. Interestingly, this task is possible if we use our reusable homomorphic extractor against correlated-source attacks, and the $\mathsf {wHPS}$ has appropriate additional structures. Next, we describe the required extractor.

Our New Notion of Extractor and Constructions. We identify three properties of an extractor: (1) reusable, (2) homomorphic, and (3) secure against correlated-source attacks.

Let $\mathsf {Ext} (\varvec{r}, \varvec{s})$ be an extractor, where $\varvec{s}$ is the source and $\varvec{r}$ is the seed. A reusable extractor requires that the same source $\varvec{s}$ can be repeatedly extracted by different seeds for any polynomially many times while maintaining pseudorandomness. That is, for any $m=\mathsf {poly}(\lambda )$ and source $\varvec{s}$ with sufficient entropy, we have $\left( \varvec{r}_1, \dots , \varvec{r}_m, \mathsf {Ext} (\varvec{r}_1, \varvec{s}),\dots , \mathsf {Ext} (\varvec{r}_m, \varvec{s}) \right) \approx \left( \varvec{r}_1, \dots , \varvec{r}_m, u_1,\dots , u_m \right)$, where each $u_i$ is uniformly random.⁴ Previously, the work [3, 14, 25] showed that under computational assumptions, e.g., $\mathsf {DDH}$ or $\mathsf {LWE}$, the reusability can be achieved.

The extractor $\mathsf {Ext} (\varvec{r}, \varvec{s})$ is (output) homomorphic with respect to a function $\mathfrak {h}$ if there exists a related function $\mathfrak {h}'$ such that $\mathsf {Ext} (\varvec{r}, \varvec{s}) + \mathfrak {h}(\varvec{s})=\mathsf {Ext} (\mathfrak {h}^\prime (\varvec{r}),\varvec{s})$. Similar to the work of [27], we will use this homomorphic property in a critical way to achieve $\mathsf {KDM}$ security.

We say the (reusable) extractor $\mathsf {Ext} (\varvec{r}, \varvec{s})$ is secure against correlated-source attacks if for functions (perhaps chosen adaptively by the attacker) in some class $\mathcal {F}$, such that for $m=\mathsf {poly}(\lambda )$ and $\mathfrak {g}_1,\dots , \mathfrak {g}_m \in \mathcal {F}$, the extractor remains pseudorandom as follows:⁵

$$\begin{aligned} \left( \varvec{r}_1, \dots , \varvec{r}_m, \mathsf {Ext} (\varvec{r}_1, \mathfrak {g}_1(\varvec{s})),\dots , \mathsf {Ext} (\varvec{r}_m, \mathfrak {g}_m(\varvec{s})) \right) \approx \left( \varvec{r}_1, \dots , \varvec{r}_m, u_1,\dots , u_m \right) . \end{aligned}$$

Our notion of correlated-source attacks is similar to that of a recent work by Goyal and Song [19], yet with the following major differences. First, the security requirements are different. The work [19] considers information-theoretic indistinguishability of one instance of extraction from the original source, even given multiple extractions from the modified source, i.e.,

$$\begin{aligned} \left( \varvec{r}, \mathsf {Ext} (\varvec{r}, \varvec{s}), \{\varvec{r}_i, \mathsf {Ext} (\varvec{r}_i, \mathfrak {g}_i(\varvec{s}))\}_{i \in m} \right) \approx \left( \varvec{r}, u, \{\varvec{r}_i, \mathsf {Ext} (\varvec{r}_i, \mathfrak {g}_i(\varvec{s}))\}_{i \in m} \right) . \end{aligned}$$

In contrast, our notion requires that all instances of $\mathsf {Ext} (\varvec{r}_i, \mathfrak {g}_i(\varvec{s}))$ remain pseudorandom, which is a stronger requirement (in this aspect).

Second, the ranges of feasible function classes are different. Specifically, our notion is too strong to achieve for the class of all functions. For example, if $\mathfrak {g}_i$ is a constant function, then $\mathsf {Ext} (\varvec{r}_i, \mathfrak {g}_i(\varvec{s}))$ becomes a fixed value given $\varvec{r}_i$, and thus cannot be pseudorandom. This indicates a necessary condition for feasibility that the function must be entropy preserving. However, the notion in [19] is possible to achieve even unconditionally for the class of all functions, as their challenge instance is extracted from an unmodified source.

Third, to achieve information-theoretic extraction for all arbitrary input correlated functions, the number m of extraction samples given extra in the distribution in [19] must be bounded inherently, and thus cannot be fully reusable.

Summing up the above analyses, we conclude that our security requirement is stronger, resulting in a relatively smaller feasible function class. Moreover, our notion requires reusability for an unbounded polynomial samples, and thus a computational assumption is necessary.

Next, we discuss how to construct such an extractor that simultaneously achieves all the three properties.

Construction Based on ${\mathbf {\mathsf{{DDH}}}}$. We start with a review of the existing $\mathsf {DDH}$-based reusable extractor. Let $\mathbb {G}$ be the $\mathsf {DDH}$ group of order q, $\varvec{r} \in \mathbb {G} ^n$ be seed, and $\varvec{s}\in \mathbb {Z}_q^n$ be source. The following function has been proved to be a reusable extractor in [3, 25]: $\mathsf {Ext} (\varvec{r},\varvec{s})= \prod _{i=1}^{n}r_{i}^{s_{i}}$. Moreover, we notice the following two properties about this extractor: (1) it is output homomorphic with respect to functions of the form $\mathfrak {h}_{\varvec{b}}(\varvec{s})=\prod _{i=1}^{n}b_{i}^{s_{i}}$, as $\mathsf {Ext} (\varvec{r},\varvec{s}) \cdot \mathfrak {h}_{\varvec{b}}(\varvec{s}) =\prod _{i=1}^{n} (r_i \cdot b_{i})^{s_{i}} = \mathsf {Ext} (\varvec{r} \circ \varvec{b} ,\varvec{s})$, where $\circ$ is the component-wise group multiplication; (2) the extractor remains pseudorandom against the correlated source attacks with respect to linear shift functions of the form $\mathfrak {g}_{\varvec{v}}(\varvec{s}) = \varvec{s} + \varvec{v}$. Due to the fact $\mathsf {Ext} (\varvec{r},\varvec{s} + \varvec{v})= \prod _{i=1}^{n}r_{i}^{s_{i} + v_{i} } = \mathsf {Ext} (\varvec{r},\varvec{s}) \cdot \mathsf {Ext} (\varvec{r}, \varvec{v})$, we can simulate $\mathsf {Ext} (\varvec{r},\mathfrak {g}_{\varvec{v}}(\varvec{s}))$ given $(\varvec{r},\mathsf {Ext} (\varvec{r},\varvec{s}))$ and $\mathfrak {g}_{\varvec{v}}$. Via this simple reduction, the security of the reusable extractor directly translates to the security against correlated-source attacks with respect to linear shifts.

At first, it seems that the existing construction already fulfills the three required properties. However, when considering the application to $\mathsf {KDM}$-secure $\mathsf {PKE}$, we notice an obstacle that this extractor is still not compatible with the above mentioned framework of the weak hash proof system based on batch encryption ($\mathsf {BE}$). Below, we sketch the major reason for this incompatibility, and discuss our solution in the following.

Particularly, the $\mathsf {BE}$-based system requires that each component of the secret vector comes from a polynomial-sized domain, i.e., $\varvec{s} \in S^n$ for $|S| = \mathsf {poly}(\lambda )$. However, the above construction has the domain $\mathbb {G} ^n$, which is clearly too large, as $\mathsf {DDH}$ assumption holds only when the order q is super-polynomial. To tackle this issue, one might set $S = \mathbb {Z}_p$ for some small p. However, for a subtle reason this approach faces an additional technical difficulty. More specifically, due to the $\mathsf {BE}$ feature, the linear shift should work in $\mathbb {Z}_p$, i.e., $\mathfrak {g}_{\varvec{v}}(\varvec{s}) = \varvec{s} + \varvec{v} \mod p$. However, this equation might not hold for the above mentioned reduction on correlated-source security, i.e., $\mathsf {Ext} (\varvec{r},(\varvec{s} + \varvec{v} \mod q)) = \mathsf {Ext} (\varvec{r},\varvec{s}) \cdot \mathsf {Ext} (\varvec{r}, \varvec{v}) \ne \mathsf {Ext} (\varvec{r},(\varvec{s} + \varvec{v} \mod p))$. Thus, it is unclear whether we can achieve correlated-source security against linear shifts (modulo p) by using the linearity of the extractor, which essentially works only in modulo q.

To solve this issue, we set $S = \mathbb {Z}_2$, and use another route of reduction that avoids using the above linearity equation. Particularly, we show a way to transform an instance of the form $(\varvec{r}, z= \mathsf {Ext} (\varvec{r}, \varvec{s}) )$ into $(\varvec{r}', \mathsf {Ext} (\varvec{r}', (\varvec{s} + \varvec{b} \mod 2)))$ given $\varvec{b}$, without using the linearity of the extractor. Furthermore, via a reduction from the reusability of the extractor, we can establish security against correlated-source attacks for linear shifts in modulo 2. This would suffice to achieve $\mathsf {KDM}$ security as we discuss later. More formally, the transformation works as follow:

• For $i\in [n]$, if $b_i =0$, set $r_i' = r_i$ and $z_i'=1$; otherwise for $b_i=1$, set $r_i' = r_i^{-1}$ and $z_i'=r_i^{-1}$.

• Output $(\varvec{r}', z \cdot \prod ^n_{i=1} z_i')$.

We note that if $b_i =0$, then the term $r_i^{s_i}$ would appear in z, or otherwise $r_i^{1- s_i}$. With a simple check, our transformation is consistent with this fact. It is not hard to formalize the security proof using this idea.

Construction Based on ${\mathbf {\mathsf{{LWE}}}}$. Next we look at the $\mathsf {LWE}$-based reusable extractor [3]. Let $q>p >1$ be parameters, S be some small set over $\mathbb {Z}_q$, $\varvec{r} \in \mathbb {Z}_q^n$ be seed, and $\varvec{s}\in S^n$ be source. The work [3, 6] showed that $\mathsf {Ext} (\varvec{r} , \varvec{s}) = \lceil \langle \varvec{r} , \varvec{s} \rangle \rfloor _p$ is a reusable extractor where $\lceil \cdot \rfloor$ is some rounding function, and the number of reusable samples can be any arbitrary polynomial if $q/p = \lambda ^{\omega (1)}$. For general settings of parameters however, this extractor might not be output homomorphic, as linearity might not hold for rounding of inner products. Nevertheless, we identify that if p|q, then the extractor is output homomorphic with respect to linear functions (i.e. $\mathfrak {h}_{\varvec{b}}(\varvec{s}) = \langle \varvec{b} , \varvec{s} \rangle \mod p$) by using the following equation:

$$\begin{aligned} \lceil \langle \varvec{r} , \varvec{s} \rangle \rfloor _p + \langle \varvec{b}, \varvec{s} \rangle = \lceil \langle \varvec{r} , \varvec{s} \rangle + (q/p) \langle \varvec{b}, \varvec{s} \rangle \rfloor _p = \lceil \langle \varvec{r} + (q/p) \varvec{b}, \varvec{s} \rangle \rfloor _p. \end{aligned}$$

Thus, we can set $\mathfrak {h}'_{\varvec{b}}(\varvec{r}) = \varvec{r} + (q/p) \varvec{b}$, achieving the desired property.

Next, we would like to show that the construction is secure against correlated-source attacks for linear shifts. Similar to the $\mathsf {DDH}$ construction, we need to tackle the issue that $\mathfrak {g}_{\varvec{b}} (\varvec{s})$ and $\mathsf {Ext} (\varvec{r}, \varvec{s})$ are working on different moduli. To solve this issue, we first apply the same idea by setting $S = \mathbb {Z}_2^n$, and then hopefully a similar reduction would work. However, this method does not work in a straight-forward way as rounding breaks linearity. Let us consider a simple case where $\varvec{b} = (1,0,0,\dots , 0)^T$, i.e., only $b_1 =1$ and others 0. Then the reduction would need to simulate $\lceil r_1 (1-s_1) + \sum _{i=2}^n r_i s_i \rfloor _p = \lceil -r_1' + r_1' s_1 + \sum _{i=2}^n r_i' s_i \rfloor _p$, where $r_1'=-r_1$ and $r_i' = r_i$ for $i= 2\sim n$. However, $\lceil -r_1' + r_1' s_1 + \sum _{i=2}^n r_i' s_i \rfloor _p \ne \lceil -r_1' \rfloor _p + \lceil r_1' s_1 + \sum _{i=2}^n r_i' s_i \rfloor _p$ in general, and thus the previous transformation would break down.

To solve this, we use the proof technique of [6], who first switches the rounded inner products into rounded $\mathsf {LWE}$ samples. Then we show that $\mathsf {LWE}$ is resilient to correlated-source attacks for linear shifts, translating to security of the whole construction. More specifically, we first switch $\lceil \langle \varvec{r} , \varvec{s} \rangle \rfloor _p$ to $\lceil \langle \varvec{r} , \varvec{s} \rangle + e \rfloor _p$. The switch incurs a negligible statistical distance if $q/p = \lambda ^{\omega (1)}$, which is required for the reusability for an arbitrary polynomial samples anyway (under current proof techniques). Then by using the above idea, we can easily show that samples of the form $\langle \varvec{r} , (\varvec{s} + \varvec{b} \mod 2) \rangle + e$ are computationally indistinguishable from random samples, and therefore so are their rounded versions. This describes the proof ideas.

${\mathbf {\mathsf{{KDM}}}}^\mathbf{(1)}$-${\mathbf {\mathsf{{PKE}}}}$ with $\mathbf{1}-\mathbf{o(1)}$ Rate via the Extractor

Achieving ${\mathbf {\mathsf{{KDM}}}}^\mathbf{(1)}$-Security. To illustrate our idea, we consider the case where $\mathsf {Ext}$ is homomorphic with respect to linear functions and secure against correlated-attacks with respect to linear shifts. Next, we identify three important additional structures of $\mathsf {wHPS}$ from the above construction:

• 1. The secret key of $\mathsf {wHPS}$ (and $\mathsf {PKE}_1$) is just a vector $\varvec{x} \in \mathbb {Z}_B^n$ as the $\mathsf {BE}$.

• 2. The decapsulation of an invalid ciphertext $\mathsf {CT} ^*$ has the following form: $\mathsf {Decap}(\varvec{x}, \mathsf {CT} ^*) = \varvec{x} + \varvec{k}'$, where $\varvec{k}'\in \mathbb {Z}_B^n$ is certain vector related to $\mathsf {CT} ^*$.

• 3. Given $\varvec{k}'$, the above $\mathsf {CT} ^*$ can be simulated faithfully.

Let $\mathfrak {h}$ be some linear functions, and let us take a look at the equation of upon a $\mathsf {KDM}$ query of an encryption of $\mathfrak {h}(\mathsf {sk})$.

Via a hybrid argument, we can switch all the adversary’s $\mathsf {KDM}$ queries to the form in the last equation. However, as $\mathsf {Ext} (\varvec{r}, \varvec{x} + \varvec{k}^\prime )-\mathfrak {h}(\varvec{k}^\prime )$ still depends on the secret key $\varvec{x}$, we cannot follow the prior proof technique in [5, 7, 9,10,11,12], which requires to simulate the $\mathsf {KDM}$ queries without using the secret key. To handle this, we observe that now the adversary’s view of his Q queries is of the form $\left\{ (\mathsf {CT} ^*_i, \mathfrak {h}_i^{\prime -1}(\varvec{r}_i), \mathsf {Ext} (\varvec{r}_i, \varvec{x} + \varvec{k}_i^\prime )-\mathfrak {h}(\varvec{k}_i^\prime )) \right\} _{i\in [Q]}$. We can then leverage the security of the extractor to switch these outputs of the extractor to uniformly random strings at one shot. Since $\mathsf {CT} _i^*$ can be generated given $\varvec{k}_i'$ (the third additional property of $\mathsf {wHPS}$), and $\mathsf {Ext}$ is secure against correlated-source attacks (even given $\varvec{k}'_i$’s), we can prove that $\{\mathsf {PKE}_1.\mathsf {Enc}(\mathfrak {h}_i(\mathsf {sk}))\}_{i\in [Q]}$ is indistinguishable from random via a simple reduction from the required extractor. We refer the details to Sect. 5.1.

Improving Information Rate. The information rate of the above scheme is $\frac{w}{|\mathsf {CT} | + |\varvec{r}| + w}$, where w denotes the length of the output of extractor. In our instantiations of the extractor, we have $|\mathsf {CT} | > |\varvec{k}| \lambda$ and $|\varvec{k}| \ge w$, and thus $|\mathsf {CT} |$ dominates the denominator, resulting in the ratio at most $O(1/\lambda )$. To improve the rate, we use the same $\mathsf {CT}$ (encapsulation) and repeatedly extract from the same source with different seeds when encrypting many different messages. That is, we consider the following scheme $\mathsf {PKE}_2$, where $\mathsf {PKE}_2.\mathsf {pk}$ and $\mathsf {PKE}_2.\mathsf {sk}$ are the same as the above $\mathsf {PKE}_1$. The encryption algorithm is modified as below:

$$\begin{aligned}&\mathsf {PKE}_2.\mathsf {Enc}((m_1,m_2,\dots , m_t))\\&\quad = \left( \mathsf {CT}, \varvec{r}_1, \mathsf {Ext} (\varvec{r}_1, \varvec{k}) + m_1, \varvec{r}_2, \mathsf {Ext} (\varvec{r}_2, \varvec{k}) + m_2, \dots , \varvec{r}_t, \mathsf {Ext} (\varvec{r}_t, \varvec{k}) + m_t\right) . \end{aligned}$$

By using the same proof idea of $\mathsf {PKE}_1$, we can show that suppose the reusable extractor is homomorphic with respect to linear functions and secure against correlated-source attacks, then the scheme $\mathsf {PKE}_2$ is $\mathsf {KDM}^{(1)}$-secure with respect to affine functions. In this case, the information rate would be $\frac{wt}{|\mathsf {CT} | + |\varvec{r}| t + wt}$, approaching $\frac{w}{|\varvec{r}| + w}$ for sufficiently large t.

However, in our both $\mathsf {LWE}$ and $\mathsf {DDH}$ instantiations, $w \ll |\varvec{r}|$, and thus the rate is still far from the optimal. To tackle this issue, we use a parallel repetition of the source, i.e., let $\varvec{k} = (\varvec{k}_1, \varvec{k}_2, \dots , \varvec{k}_d)$, and define

$$ \mathsf {Ext} _{||}(\varvec{r}, \varvec{k}) = \left( \mathsf {Ext} (\varvec{r}, \varvec{k}_1), \mathsf {Ext} (\varvec{r}, \varvec{k}_2),\dots , \mathsf {Ext} (\varvec{r}, \varvec{k}_d)\right) . $$

We can show that suppose $\varvec{k}$ forms a block source, then the output of $\mathsf {Ext} _{||}$ will be computationally indistinguishable from random. Moreover, $\mathsf {Ext} _{||}$ is as well homomorphic and secure against correlated-source attacks for appropriate classes. By using $\mathsf {Ext} _{||}$, we can still derive $\mathsf {KDM}^{(1)}$ security, for a slightly weaker class of block-affine functions. Now, the information rate would be $\frac{w d}{|\varvec{r}| + wd}$, approaching $1-o(1)$ by setting d such that $|\varvec{r}| = o(wd)$.

Achieving Arbitrary Polynomial ${\bar{{\varvec{n}}}}$

Next, we discuss how to upgrade the above framework to achieve $\mathsf {KDM}^{(\bar{n})}$-security for an unbounded polynomial $\bar{n}$. Before presenting our approach, we first abstract some important features from the above schemes $\mathsf {PKE}_1$ and $\mathsf {PKE}_2$ – (1) the schemes are based on $\mathsf {BE}$ as the most underlying tool, and (2) they have the following features: (a) the secret key is just a vector $\varvec{x}$, and (b) the public key has the form $(\mathsf {CRS}, \mathsf {H} (\mathsf {CRS}, \varvec{x}))$, where $\mathsf {H}$ denotes the projection function $\mathsf {KeyGen} (\cdot ,\cdot )$ of $\mathsf {BE}$ in [12]. We call this type of schemes as $\mathsf {BE}$-based public key encryption scheme.

Next we generalize the idea of [9], showing that if a $\mathsf {BE}$-based scheme satisfies certain key and ciphertext homomorphic properties, then one can prove $\mathsf {KDM}^{(\bar{n})}$-security from $\mathsf {KDM}^{(1)}$ by the following two steps: Let $\varPi$ be a $\mathsf {BE}$-based $\mathsf {PKE}$.

• 1. First we define an intermediate scheme $\varPi ^{\bar{n}}$ that runs $\bar{n}$ times the encryption algorithm of $\varPi$ to encrypt the same message, with $\bar{n}$ distinct public parameters but corresponding to the same secret key. Particularly, $\varPi ^{\bar{n}}.\mathsf {sk} = \varPi .\mathsf {sk} = \varvec{x}$, and $\varPi ^{\bar{n}}.\mathsf {pk} = (\varPi .\mathsf {pk} _1,\dots ,\varPi .\mathsf {pk} _{\bar{n}})$, where $\varPi .\mathsf {pk} _i = (\mathsf {CRS}_i, h_i = \mathsf {H} (\mathsf {CRS}_i, \varvec{x} ))$ for all $i \in [\bar{n}]$. The encryption algorithm works as follows:

  $$ \varPi ^{\bar{n}}.\mathsf {Enc}(m)= (\varPi .\mathsf {Enc}(\mathsf {pk} _1,m),\varPi .\mathsf {Enc}(\mathsf {pk} _2,m), \dots , \varPi .\mathsf {Enc}(\mathsf {pk} _{\bar{n}},m)). $$

• 2. Then we show, if $\varPi ^{\bar{n}}$ is $\mathsf {KDM}^{(1)}$-secure with respect to affine functions, then $\varPi$ is $\mathsf {KDM}^{ (\bar{n})}$-secure with respect to affine functions.

Thus, to show that $\mathsf {PKE}_2$ is $\mathsf {KDM}^{(\bar{n})}$ secure, it suffices to show that its intermediate scheme, i.e., $\mathsf {PKE}_2^{\bar{n}}$, is $\mathsf {KDM}^{(1)}$ secure.

However, the current instantiation of the underlying $\mathsf {BE}$ [12] can only derive $\mathsf {KDM}^{(1)}$ security of $\mathsf {PKE}_2^{\bar{n}}$ for a bounded polynomial $\bar{n}$. When $\bar{n}$ becomes too large, $\mathsf {PKE}_2^{\bar{n}}$ may completely loses security. As each $h_i = \mathsf {H} (\mathsf {CRS}_i, \varvec{x} )$ leaks some small information of the secret $\varvec{x}$, thus the secret might have no entropy given too many hashes in the $\mathsf {pk} _i$’s. Even worse, in the $\mathsf {LWE}$-based instantiation of [12], one can obtain $\varvec{x}$ given only n (the dimension of $\varvec{x}$) hashes of $h_i$’s by simply solving linear equations. This approach seems to hit an entropy barrier, inherently.

To tackle this challenge, we propose a new pseudorandom property of $\mathsf {BE}$ (and $\mathsf {BE}$-based $\mathsf {PKE}$) by adding reusability to the projection function $\mathsf {H}$. Particularly, the reusable property requires that the following two distributions are indistinguishable, even in conjunction with the reusable extractor against correlated-source attacks for any $\bar{n},m = \mathsf {poly}(\lambda )$:

$$\begin{aligned} \left( \left\{ \mathsf {CRS}_i, \mathsf {H} (\mathsf {CRS}_i,\varvec{x}) \right\} _{i\in [\bar{n}]}, \left\{ \varvec{r}_j, \mathsf {Ext} (\varvec{r}, \mathfrak {h}_j(\varvec{x})) \right\} _{j\in [m]}\right) \approx _c \left( \left\{ \mathsf {CRS}_i, u_i\right\} _{i\in [\bar{n}]}, \left\{ \varvec{r}_j, u_j'\right\} _{j\in [m]}\right) \end{aligned}$$

Conceptually, this would guarantee secrecy of $\varvec{x}$ even if the adversary can obtain many hashes on the same $\varvec{x}$ and samples from the reusable extractor (under correlated-source attacks).

As a result, by using a $\mathsf {BE}$ with this reusable property as the underlying building block of $\mathsf {wHPS}$, we are able to show that $\mathsf {PKE}^{\bar{n}}_2$ is $\mathsf {KDM}^{(1)}$-secure for any $\bar{n}=\mathsf {poly}(\lambda )$, implying that $\mathsf {PKE}_2$ is $\mathsf {KDM}^{(\bar{n})}$-secure for any $\bar{n}=\mathsf {poly}(\lambda )$.

New ${\mathbf {\mathsf{{BE}}}}$ Constructions. To instantiate the required $\mathsf {BE}$, we observe that the $\mathsf {CDH}$-based scheme in [12] as is, can achieve the reusability property if $\mathsf {DDH}$ is further assumed. However, the $\mathsf {LWE}$-based scheme becomes insecure if n hashes are given to the adversaries as we stated before, where n is the dimension of $\varvec{x}$. To solve this, we design a new projection function $\mathsf {H} '$ that makes a simple yet essential modification of the original $\mathsf {H}$ of [12]. Particularly, $\mathsf {H} '(\mathsf {CRS}, \varvec{x}) = \mathsf {H} (\mathsf {CRS},\varvec{x}) + \varvec{e}$, for some appropriate noise $\varvec{e}$. In this way, the distribution $(\mathsf {CRS}, \mathsf {H} '(\mathsf {CRS}, \varvec{x}))$ in this modified $\mathsf {BE}$ would be a sample of $\mathsf {LWE}$, which is pseudorandom even when polynomially many samples are given, and can be used in conjunction with the $\mathsf {LWE}$-based reusable extractor. This enables us to achieve $\mathsf {KDM}^{(\bar{n})}$-$\mathsf {PKE}$ for any unbounded polynomial $\bar{n}$ with optimal information rate with respect to affine functions.

Amplification. We first notice that the class of block-affine functions does not contain all projection functions, so the generic technique of Applebaum [4] does not apply to amplify the class. Nevertheless, we show that this class can still be used to encode the labels of Garbled Circuits (a common realization of randomized encoding), and thus we can amplify the class to be any bounded-sized boolean circuits.

As our scheme can encrypt messages of an indefinite length, we are able to further achieve $\mathsf {KDM}$ function class for $(\mathcal {F}_s || \mathcal {Q} ^{\tau })$, where $\mathcal {F}_s$ is the class of circuits up to sized s, $\mathcal {Q} ^{\tau }$ is the class of affine functions with $\tau$-element outputs, and $(\mathcal {F}_s || \mathcal {Q} ^{\tau })$ denotes the concatenation of two classes, i.e., every function $\mathfrak {f}$ in the class can be represented by $\mathfrak {f}= (\mathfrak {h}, \mathfrak {q})$ for some $\mathfrak {h}\in \mathcal {F}_s$ and $\mathfrak {q}\in \mathcal {Q} ^{\tau }$ such that $\mathfrak {f}(\mathsf {sk}) = (\mathfrak {h}(\mathsf {sk}) || \mathfrak {q}(\mathsf {sk}))$. For the parameter range $\tau \gg s$, our scheme achieves the optimal information rate, i.e., $1-o(1)$.

Upgrade to ${\mathbf {\mathsf{{KDM}}}}$-${\mathbf {\mathsf{{IBE}}}}$ 

The above framework can be further generalized to construct $\mathsf {IBE}$ with $\mathsf {KDM}$-security and leakage resilience. Particularly, we design a new compiler that uses an $\mathsf {IB}\text {-}\mathsf {wHPS}$ to amply the on-the-fly $\mathsf {KDM}$-security (a new notion) of $\mathsf {PKE}$ into $\mathsf {KDM}$-security of $\mathsf {IBE}$, and simultaneously the resulting $\mathsf {IBE}$ achieves leakage resilience. This improves the compiler of [23], which might not be leakage resilient.

Our compiler is straight-forward. Let $\varPi$ be a $\mathsf {BE}$-based $\mathsf {PKE}$ and $\mathsf {IB}\text {-}\mathsf {wHPS}$ be an identity-based $\mathsf {wHPS}$ that has additional structures: (1) the secret key has the structure $\mathsf {sk} _\mathsf {id} =( \varvec{x}, \mathsf {sk} _{\mathsf {id}, \varvec{x}})$, (2) $\mathsf {IB}\text {-}\mathsf {wHPS}.\mathsf {Decap}(\mathsf {sk} _\mathsf {id}, \mathsf {CT} ^*) = \varvec{x} + \varvec{k}$, and (3) given $\varvec{k}$, the above $\mathsf {CT} ^*$ can be simulated faithfully. (This is similar to the additional structures of our required $\mathsf {wHPS}$ above). Then we can design an $\mathsf {IBE}.\{\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ as follows. $\mathsf {IBE}.\{\mathsf {Setup},\mathsf {KeyGen} \}$ and $\mathsf {IBE}.\{\mathsf {mpk},\mathsf {msk},\mathsf {sk} _\mathsf {id} \}$ are the same as those of $\mathsf {IB}\text {-}\mathsf {wHPS}$. To encrypt a message m with an $\mathsf {id}$, $\mathsf {IBE}.\mathsf {Enc}$ first generates an encapsulation $(\mathsf {CT} _1,\varvec{k}) \leftarrow \mathsf {IB}\text {-}\mathsf {wHPS}.\mathsf {Encap}(\mathsf {mpk},\mathsf {id})$, then generates $\mathsf {pk} = (\mathsf {CRS}, \mathfrak {h}(\mathsf {CRS}, \varvec{k}))$ from the $\mathsf {BE}$, and then computes $\mathsf {CT} _2 \leftarrow \varPi .\mathsf {Enc}(\mathsf {pk}, m)$. The resulting ciphertext would be $(\mathsf {CT} _1, \mathsf {pk}, \mathsf {CT} _2)$.

Next we present a simple case that demonstrates the key idea of our $\mathsf {KDM}$-security proof. Consider the simple case of only one $\mathsf {KDM}$ query, i.e., an encryption for some message $\mathfrak {f}(\mathsf {sk} _\mathsf {id}) = \mathfrak {f}(\varvec{x}, \mathsf {sk} _{\mathsf {id}, \varvec{x}})$ (by Structure 2 of $\mathsf {IB}\text {-}\mathsf {wHPS}$) with respect to some $\mathsf {id}$. We can derive the following:

We observe that if $\mathfrak {f}( (\varvec{x}' - \varvec{k}'), \mathsf {sk} _{(\varvec{x}' - \varvec{k}')})$ can be expressed as $\mathfrak {g}(\varvec{x}')$ and the underlying $\varPi$ is $\mathsf {KDM}$-secure with respect to the function $\mathfrak {g}$, then the resulting $\mathsf {IBE}$ is $\mathsf {KDM}$-secure with respect to $\mathfrak {f}$. We further identify that the equation (*) holds even if the master secret key $\mathsf {msk}$ of $\mathsf {IB}\text {-}\mathsf {wHPS}$ is given. Thus, we can hardcode $\mathsf {msk}$ and $\varvec{k}'$ and randomness r into $\mathfrak {g}$ and set the function as follow: $\mathfrak {g}_{\mathsf {msk},\varvec{k}',r}(\varvec{x}')$ first computes $\mathsf {sk} _{\mathsf {id}, \varvec{x}' - \varvec{k}'} = \mathsf {IB}\text {-}\mathsf {wHPS}.\mathsf {KeyGen} (\mathsf {msk}, \mathsf {id}, \varvec{x}'-\varvec{k}' ;r)$ and then outputs $\mathfrak {f}( (\varvec{x}' - \varvec{k}'), \mathsf {sk} _{\mathsf {id},(\varvec{x}' - \varvec{k}')})$. We can instantiate $\varPi$ by using the above mentioned schemes $\mathsf {PKE}_1$ or $\mathsf {PKE}_2$ and the bootstrapping technique of Applebaum [4]. In this way, we can obtain a $\mathsf {KDM}$-secure $\mathsf {PKE}$ with respect to the class of bounded polynomial circuits, which includes the required $\mathfrak {g}$.

The above idea cannot be trivially extended to the general case where there are many $\mathsf {KDM}$ queries. A simple reason is that $\mathsf {pk}$ needs to be generated on-the-fly for each ciphertext. This does not match the traditional notion of $\mathsf {KDM}$-security for $\mathsf {PKE}$. To handle this technical issue, we propose a new notion called on-the-fly $\mathsf {KDM}$-security, where there is no $\mathsf {pk}$ upfront, and the adversary receives an on-the-fly $\mathsf {pk} = (\mathsf {CRS}, \mathsf {H} (\mathsf {CRS},\varvec{x}'))$ with respect to the same secret key $\varvec{x}'$ upon each $\mathsf {KDM}$ query. By using this on-the-fly $\mathsf {KDM}$-$\mathsf {PKE}$ with the $\mathsf {IB}\text {-}\mathsf {wHPS}$, we are able to achieve $\mathsf {KDM}$-$\mathsf {IBE}$. Moreover, we can prove that the above $\mathsf {PKE}_2$ satisfies the on-the-fly notion. We refer details to full version.

2 Preliminaries

We use several standard mathematical notations, whose detailed descriptions are deferred to the full version. In the full version we present the formal definitions of $\mathsf {KDM}$-security and leakage resilience. Below, we present the syntax of two important tools – batch encryption and weak hash proof systems. Due to space limit, we defer their detailed security properties to the full version.

Definition 2.1

(Batch Encryption in [12]). A batch encryption ($\mathsf {BE}$) scheme consists of the following four algorithms $\{\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$:

• $\mathsf {Setup}(1^{\lambda },1^n)$: The algorithm takes as input the security parameter $\lambda$ and key length n, and outputs a common reference string $\mathsf {CRS}$ which includes a parameter $B=B(\lambda ,n)$.

• $\mathsf {KeyGen}(\mathsf {CRS},\varvec{x})$: Given a common reference string $\mathsf {CRS}$ and the secret key $\varvec{x}\in \mathbb {Z}_B^n$ as input, the algorithm projects the secret key $\varvec{x}$ to a public key h.

• $\mathsf {Enc}(\mathsf {CRS},h,\mathbf {M})$: Given a common reference string $\mathsf {CRS}$, a public key h, and a message matrix $\mathbf {M}=(M_{i,j})_{i\in [n],j\in \mathbb {Z}_B}\in \mathbb {Z}_B^{n\times B}$ as input, the algorithm outputs a ciphertext $\mathsf {CT}$.

• $\mathsf {Dec}(\mathsf {CRS},\varvec{x},{\mathsf {CT}})$: Given a common reference string $\mathsf {CRS}$, a secret key $\varvec{x}$, and a ciphertext $\mathsf {CT}$ as input, the algorithm outputs a message vector $\varvec{m}^\prime =(M_{i,x_i})_{i\in [n]}$.

Remark 2.2

Let $\hat{\ell }$ denote the bit-length of the public key h. Then we notice that given the public key $\mathsf {pk}$, the conditional min-entropy of $\mathsf {sk}$ is $H_\infty (\mathsf {sk} |\mathsf {pk})=H_\infty (\varvec{x}|h)\ge n\log B-\hat{\ell }$.

Definition 2.3

(Weak Hash Proof System in [21]). A weak hash proof system ($\mathsf {wHPS}$) with the encapsulated-key-space $\mathcal {K}$ consists of four algorithms

$\mathsf {wHPS}$.{$\mathsf {Setup}$,$\mathsf {Encap}$,$\mathsf {Encap}$ $^*$,$\mathsf {Decap}$} as follows. (We will omit $\mathsf {wHPS}$ when the context is clear).

• Key generation. $\mathsf {Setup}$ $(1^{\lambda })$ takes a security parameter $\lambda$ as input, and generates a pair of public key and secret key $(\mathsf {pk},\mathsf {sk})$.

• Valid encapsulation. $\mathsf {Encap}$ $(\mathsf {pk})$ takes a public key $\mathsf {pk}$ as input, and outputs a valid ciphertext $\mathsf {CT}$ and its corresponding encapsulated key $\mathsf {k} \in \mathcal {K}$.

• Invalid encapsulation. $\mathsf {Encap}$ $^*$ $(\mathsf {pk})$ takes a public key $\mathsf {pk}$ as input, and outputs an invalid ciphertext $\mathsf {CT} ^*$.

• Decapsulation. $\mathsf {Decap}$ $(\mathsf {sk},\mathsf {CT})$ takes as input a secret key $\mathsf {sk}$ and ciphertext $\mathsf {CT}$, and deterministically outputs $\mathsf {k} \in \mathcal {K}$.

Additionally, we define the following function families that are useful for our results on $\mathsf {KDM}$ security.

Definition 2.4

(Linear, Affine and Shift Functions). Let $\mathcal {X},\mathcal {Y}$ be some additive groups. A function $\mathfrak {g}: \mathcal {X} \rightarrow \mathcal {Y}$ is linear if for every $x, x' \in \mathcal {X}$, we have $\mathfrak {g}(x + x') = \mathfrak {g}(x) + \mathfrak {g}(x')$; a function $\mathfrak {h}: \mathcal {X} \rightarrow \mathcal {Y}$ is affine if there exist a linear function $\mathfrak {g}: \mathcal {X} \rightarrow \mathcal {Y}$ and a constant $a\in \mathcal {Y}$ such that $\mathfrak {h}(x) = \mathfrak {g}(x) +a$ for every $x\in \mathcal {X}$. Moreover, a function $\mathfrak {s}:\mathcal {X} \rightarrow \mathcal {X}$ indexed by certain element $x\in \mathcal {X}$ is shift, if for every $x, x' \in \mathcal {X}$, we have $\mathfrak {s}_x(x') = x+x^\prime$.

Definition 2.5

Let $\mathcal {X},\mathcal {Y}$ be some additive groups. Given a class of linear functions $\mathcal {G} =\{\mathfrak {g}:\mathcal {X} \rightarrow \mathcal {Y} \}$, we define a related class of affine functions $\mathcal {G} ^t =\{\mathfrak {g}': \mathcal {X} \rightarrow \mathcal {Y} ^t\}$ where each $\mathfrak {g}'\in \mathcal {G} ^t$ can be indexed by a constant vector $\varvec{a} = (a_1,\dots , a_t)^\top \in \mathcal {Y} ^t$ and t functions in $\mathcal {G}$, i.e., $\mathfrak {g}_1, \mathfrak {g}_2, \dots , \mathfrak {g}_t \in \mathcal {G}$, such that for every $x\in \mathcal {X}$, $\mathfrak {g}'(x) = (\mathfrak {g}_1(x), \mathfrak {g}_2(x), \dots , \mathfrak {g}_t(x) )^\top + \varvec{a} = (\mathfrak {g}_1(x) + a_1, \mathfrak {g}_2(x) + a_2, \dots , \mathfrak {g}_t(x) + a_t )^\top$.

Besides, if the underlying linear functions $\mathfrak {g}\in \mathcal {G}$ is a block function, i.e., each output component of $\mathfrak {g}$ depends only on one block of its input, then the resulting functions $\mathfrak {g}'\in \mathcal {G} ^t$ are called block-affine function.

3 Randomness Extractor and Its Variants

In this section, we first define a new variant of (computational) randomness extractors, which serve as the most important tools of this paper. Then, we instantiate the required extractors based on $\mathsf {LWE}$ or $\mathsf {DDH}$, respectively.

3.1 Our New Variant of Randomness Extractors

We require an extractor that is (1) reusable, (2) secure against correlated-source attacks, and (3) homomorphic. We present their definitions below.

Definition 3.1

(Reusable Extractor in [3]). Let $\mathcal {X},\mathcal {S},\mathcal {Y}$ be efficient ensembles parameterized by the security parameter $\lambda$. An efficient function $\mathsf {Ext}:\mathcal {X} \times \mathcal {S}\rightarrow \mathcal {Y}$ is an (e, t)-reusable-extractor⁶, if for any correlated random variables $(s,\mathsf {aux})$ where s is over $\mathcal {S}$ and $H_{\infty }(s | \mathsf {aux})\ge e$, the following two distributions are computationally (statistically) indistinguishable:

$$(\mathsf {aux},r_1,\ldots ,r_t,\mathsf {Ext} (r_1,s),\ldots ,\mathsf {Ext} (r_t,s))\approx (\mathsf {aux},r_1,\ldots ,r_t,u_1,\ldots ,u_t),$$

where the strings , are sampled independently.

If $e> t \log |\mathcal {Y} | + O(\log (1/\varepsilon {}))$ for some $\varepsilon {}=\mathsf {negl} (\lambda )$, we can construct an (e, t)-reusable extractor information theoretically, e.g.,. Leftover hash lemma [15]. On the other hand for $e < t \log |\mathcal {Y} | + O(\log (1/\varepsilon {}))$, it is still possible to construct (e, t)-reusable extractor under appropriate computational assumptions, such as $\mathsf {DDH}$ or $\mathsf {LWE}$ [3, 25], for t being a bounded or even any arbitrary polynomial depending on the parameter settings.

Definition 3.2

(Reusable Extractor against Correlated-Source Attacks). Let $\mathsf {Ext}:\mathcal {X} \times \mathcal {S}\rightarrow \mathcal {Y}$ be some function, and $\mathcal {F}=\{\mathfrak {f}:\mathcal {S}\rightarrow \mathcal {Y} \}$ be some function class. We say $\mathsf {Ext}$ is an (e, t)-reusable extractor against correlated-source attacks with respect to $\mathcal {F}$, if for every random variables $s,\mathsf {aux}$ where s is over $\mathcal {S}$ and $\mathsf {H} _\infty (s|\mathsf {aux})\ge e$, the following oracles, $O_s(\cdot )$ and $U(\cdot )$, are computationally indistinguishable given up to t queries:

• $O_s(\cdot ):$ Take a function $\mathfrak {f}\in \mathcal {F}$ as input, sample a fresh random $r \leftarrow \mathcal {X}$, and return $(r, \mathsf {Ext} (r, \mathfrak {f}(s)))$ upon each query.

• $U(\cdot ):$ Take a function $\mathfrak {f}\in \mathcal {F}$ as input, return a uniform sample $(r,u) \leftarrow (\mathcal {X}, \mathcal {Y})$ upon each query.

Remark 3.3

The above Definition 3.2 can also be described in the indistinguishability form – for any correlated random variables $(s,\mathsf {aux})$ such that s is over $\mathcal {S}$ and $H_{\infty }(s|\mathsf {aux})\ge e$, the following two distributions are computationally (statistically) indistinguishable: $\left( \mathsf {aux},\left\{ r_{i}, \mathsf {Ext} (r_{i},\mathfrak {f}_i(s))\right\} _{i\in [t]}\right) \approx \left( \mathsf {aux},\left\{ r_{i}, u_{i}\right\} _{i\in [t]}\right) ,$ where the strings , are sampled independently, and $\{\mathfrak {f}_i\in \mathcal {F}\}_{i\in [t]}$ are chosen (adaptively) by any $\textsc {ppt}$ adversary $\mathcal {A}$.

Clearly, an (e, t)-reusable extractor is also one against correlated-source attacks with respect to the identity function.

Definition 3.4

(Homomorphic Extractor). Let $\mathcal {Y}$ be a group associated with operation ‘$\circ$’, $\mathsf {Ext}:\mathcal {X} \times \mathcal {S}\rightarrow \mathcal {Y}$ be an extractor following the syntax as in Definition 3.1, and $\mathcal {H} =\{\mathfrak {h}:\mathcal {S}\rightarrow \mathcal {Y} \}$ be some function class. We say that $\mathsf {Ext}$ is homomorphic with respect to $\mathcal {H}$, if for any function $\mathfrak {h}\in \mathcal {H}$, there exists an invertible function $\mathfrak {h}^\prime :\mathcal {X} \rightarrow \mathcal {X}$ (efficiently computable given $\mathfrak {h}$) such that for any $x\in \mathcal {X}$ and $s\in \mathcal {S}$, we have $\mathsf {Ext} (x,s)\circ \mathfrak {h}(s)=\mathsf {Ext} (\mathfrak {h}^\prime (x),s).$

3.2 Instantiations from $\mathsf {LWE}$ and $\mathsf {DDH}$

Definition 3.5

For integers n and $\delta$, we define the linear function class.

• $\mathcal {SF} _{\delta ,n}=\{\mathfrak {s}_{\varvec{a}}:\mathbb {Z}_\delta ^n \rightarrow \mathbb {Z}_\delta ^n\}$ where each function $\mathfrak {s}_{\varvec{a}}$ is indexed by a vector $\varvec{a}\in \mathbb {Z}_\delta ^n$ such that $\mathfrak {s}_{\varvec{a}} (\varvec{x}) = \varvec{x} + \varvec{a} ~\mathrm {mod} ~\delta$, for every $\varvec{x} \in \mathbb {Z}_\delta ^n$.

Construction 3.6

(${\mathbf {\mathsf{{LWE}}}}$-Based Extractor). Let $\mathcal {X} =\mathbb {Z}^{n}_{q}$, $\mathcal {S}=\mathbb {Z}_{2}^n$ and $\mathcal {Y} =\mathbb {Z}_p$, where p is a prime and p|q. We define $\mathsf {Ext}: \mathcal {X} \times \mathcal {S}\rightarrow \mathcal {Y}$ as:

$$\mathsf {Ext} (\varvec{a},\varvec{s})=\lfloor \langle \varvec{a},\varvec{s}\rangle ~\bmod ~q \rceil _{q,p},$$

where $\varvec{a}\in \mathcal {X}, \varvec{s}\in \mathcal {S}$ and $\lfloor \cdot \rceil _{q,p}$ is defined as the definition of $\mathsf {LWR}$ in [6]. The construction has ratio $\frac{|\mathcal {Y} |}{|\mathcal {X} |} = \frac{\log p}{n \log q}$.

Theorem 3.7

Let $\lambda$ be the security parameter, $q,p,d,\beta ,\sigma$ be parameters such that $q \ge p \beta \lambda ^{\omega (1)}$, $\beta = \sigma \lambda ^{\omega (1)}$, and p|q. Let $\chi$ be some $\sigma$-bounded distribution over $\mathbb {Z}^n_q$, $e\ge (d+\varOmega (\lambda ))\log q$. Assuming the hardness of $\mathsf {LWE}_{d,q,\chi }$, then $\mathsf {Ext}$ in Construction 3.6 is an $(e,\ell =\mathsf {poly}(\lambda ))$-reusable extractor against correlated-source attacks with respect to the function class $\mathcal {SF} _{2,n}$. Furthermore, this $\mathsf {Ext}$ is homomorphic with respect to the function class $\mathcal {G} _{p,n}=\{\mathfrak {g}_{\varvec{b}}:\mathbb {Z}_2^{n} \rightarrow \mathbb {Z}_p\}$, where each function $\mathfrak {g}_{\varvec{b}}$ is indexed by a vector $\varvec{b} \in \mathbb {Z}_q^n$ such that $\mathfrak {g}_{\varvec{b}}(\varvec{x})=\langle \varvec{b},\varvec{x}\rangle ~\mathrm {mod} ~p$, for every $\varvec{x} \in \mathbb {Z}_2^n$.

Due to space limit, we defer the detailed proof to the full version.

Construction 3.8

(${\mathbf {\mathsf{{DDH}}}}$-Based Extractor). Let $\mathbb {G}$ be a group of prime order q, $\mathcal {X} =\mathbb {G} ^{n}$, $\mathcal {S}=\mathbb {Z}_2^n$, and $\mathcal {Y} =\mathbb {G}$. We define $\mathsf {Ext}: \mathcal {X} \times \mathcal {S}\rightarrow \mathcal {Y}$ as:

$$\mathsf {Ext} (\varvec{a},\varvec{s})= \prod _{i=1}^{n}a_{i}^{s_{i}},$$

where $\varvec{a}\in \mathcal {X}$, $\varvec{s}\in \mathbb {Z}^{n}_{2}$. The construction has ratio $\frac{|\mathcal {Y} |}{|\mathcal {X} |} = \frac{1}{n}$.

Theorem 3.9

Let $\lambda$ be the security parameter, $\mathbb {G}$ be a group of prime order q. Assuming that $\mathsf {DDH}$ is hard with respect to the group $\mathbb {G}$ and $e\ge \log q+2\log (1/\varepsilon {})$ where $\varepsilon \in (0,1)$ is negligible, then $\mathsf {Ext}$ defined as Definition 3.8 is an $(e,t=\mathsf {poly}(\lambda ))$-reusable extractor against correlated-source attacks with respect to the function class $\mathcal {SF} _{2,n}$. Furthermore, $\mathsf {Ext}$ is homomorphic with respect to the function class $\mathcal {G} '_{q,n}$, where each $\mathfrak {g}\in \mathcal {G} '_{q,n}$ is indexed by certain vector $\varvec{b}\in \mathbb {G} ^n$, i.e., $\mathfrak {g}_{\varvec{b}}(\varvec{s})=\prod _{i=1}^{n}b_{i}^{s_{i}}$ for input $\varvec{s}\in \mathbb {Z}_2^{n}$.

Due to space limit, we defer the detailed proof to the full version.

4 $\mathsf {wHPS}$ and Its Instantiation from Batch Encryption

In this section, we first identify several new important structures of $\mathsf {wHPS}$, and then show an instantiation of the required $\mathsf {wHPS}$ from $\mathsf {BE}$.

4.1 Additional Structure of $\mathsf {wHPS}$

Definition 4.1

(${\mathbf {\mathsf{{wHPS}}}}$ with Additional Structures). We say that $\varPi$ is a $\mathsf {wHPS}$ with additional structures, if the following conditions hold:

• 1. $\varPi$ satisfies all conditions for a $\mathsf {wHPS}$ defined in Definition 2.3;

• 2. The secret key, $\mathsf {sk}$, of $\varPi$ can be written as $\mathsf {sk}:=(\varvec{a},\mathsf {sk} _{\varvec{a}})\in \mathbb {Z}_m^n\times \{0,1\}^{*}$, for certain positive integers $m,n\in \mathbb {Z}$. In particular, $\mathsf {sk} _{\varvec{a}}\in \{0,1\}^{*}$ can be viewed as an arbitrary bit string, but is related to the prefix vector $\varvec{a}\in \mathbb {Z}_m^n$.

• 3. The decapsulation of an invalid ciphertext, $\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^{*})$, can be written as $\mathfrak {s}_{\varvec{k}^\prime }(\varvec{a})=\varvec{a}+\varvec{k}^\prime \bmod m$, where the $\varvec{a}$ is the first part of the secrete key $\mathsf {sk}$, and $\varvec{k}^\prime \in \mathbb {Z}_m^n$ is the index vector related to the invalid ciphertext $\mathsf {CT} ^{*}$.

• 4. Given some $\varvec{k}^\prime \in \mathbb {Z}_m^n$, one can generate $\mathsf {CT} ^{*}$ such that $\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^{*}) = \mathfrak {s}_{\varvec{k}^\prime }(\varvec{a})$ and the distribution of $\mathsf {CT} ^*$ is identical to that of $\mathsf {Encap}^{*}(\mathsf {pk})$.

Remark 4.2

This additional structure can also be generalized to the notion of $\mathsf {IB}\text {-}\mathsf {wHPS}$ described in full version. In particular, for the case of $\mathsf {sk} _\mathsf {id}:=(\varvec{a},\mathsf {sk} _{\varvec{a},\mathsf {id}})$ in the $\mathsf {IB}\text {-}\mathsf {wHPS}$, $\mathsf {sk} _{\varvec{a},\mathsf {id}}$ is the output of an integrated algorithm $\mathsf {IB}\text {-}\mathsf {wHPS}.\mathsf {KeyGen} (\mathsf {msk},\mathsf {id},\varvec{a})$, where $\mathsf {msk}$ denotes the master secret key.

4.2 $\mathsf {wHPS}$ from $\mathsf {BE}$

Construction 4.3

(Construction of ${\mathbf {\mathsf{{wHPS}}}}$ from ${\mathbf {\mathsf{{BE}}}}$). Let $\varPi =$ $\varPi .\{\mathsf {Setup},$ $\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ be a batch encryption scheme with the message space $\mathbb {Z}_B^{n\times B}$, the secret-key space $\mathbb {Z}_B^n$ and the projected public key size $\hat{\ell }$. Then, we construct a weak hash proof system $\mathsf {HPS}$ scheme $\varPi _{\mathsf {wHPS}}=\varPi _{\mathsf {wHPS}}.\{\mathsf {Setup},\mathsf {Encap},\mathsf {Encap}^*,$ $\mathsf {Decap}\}$ with the same ciphertext space as $\varPi$ and the encapsulated key space $\mathcal {K}=\mathbb {Z}_B^n$ as follows:

• $\varPi _{\mathsf {wHPS}}.\mathsf {Setup}(1^\lambda )$: The algorithm runs for an integer $n\in \mathbb {N}$, and then runs $\varPi .\mathsf {KeyGen}(\mathsf {CRS},\varvec{x})$ to generate h for a randomly chosen vector $\varvec{x}\in \mathbb {Z}_B^n$ . Finally, the algorithm outputs $\mathsf {pk}:= (\mathsf {CRS},h)$ and $\mathsf {sk}:= \varvec{x}$.

• $\varPi _{\mathsf {wHPS}}.\mathsf {Encap}(\mathsf {pk})$: Given a public-key $\mathsf {pk}$ as input, the algorithm first chooses a random vector $\varvec{k}=(k_1,\ldots ,k_n)^{\top } \in \mathbb {Z}_B^n$, and set matrix $\mathbf {M}=(M_{i,j})_{i\in [n],j\in \mathbb {Z}_B}$ such that $M_{i,j}=k_i$ for every $i\in [n], j\in \mathbb {Z}_B$, i.e., all components in each row of $\mathbf {M}$ are the same. Then the algorithm runs , and outputs $\mathsf {CT}$ and $\varvec{k}$ as a valid ciphertext and its encapsulated key, respectively.

• $\varPi _{\mathsf {wHPS}}.\mathsf {Encap}^{*}(\mathsf {pk})$: Given a public-key $\mathsf {pk}$ as input, the algorithm chooses a random vector $\varvec{k}=(k_1,\ldots ,k_n)^\top \in \mathbb {Z}_B^n$, and set matrix $\mathbf {M}=(M_{i,j})_{i\in [n],j\in \mathbb {Z}_B}$ such that $M_{i,j}=k_i + j \mod B$ for every $i\in [n], j\in \mathbb {Z}_B$. (In this way, every element in a row is different from the others in the same row.) Then the algorithm runs , and outputs $\mathsf {CT} ^{*}$ as an invalid ciphertext.

• $\varPi _{\mathsf {wHPS}}.\mathsf {Decap}(\mathsf {sk},\mathsf {CT})$: Given a ciphertext $\mathsf {CT}$ and a secret key $\mathsf {sk}:=\varvec{x}$ as input, the algorithm runs $\varvec{m}^\prime =\varPi .\mathsf {Dec}(\mathsf {CRS},\varvec{x},\mathsf {CT})$, and outputs $\varvec{m}^\prime$ as the encapsulated key.

It is clear that this construction of $\mathsf {wHPS}$ satisfies the additional structures in Definition 4.1. Moreover, the secret key of $\mathsf {wHPS}$ does not have the second part $\mathsf {sk} _{\varvec{a}}$, which is one of our key points to prove the $\mathsf {KDM}$ security. Below we present the formal theorem and its proof.

Theorem 4.4

(${\mathbf {\mathsf{{wHPS}}}}$ from ${\mathbf {\mathsf{{BE}}}}$). Suppose $\varPi$ is a semantically secure batch encryption scheme with the message space $\mathbb {Z}_B^{n\times B}$, the secret-key space $\mathbb {Z}_B^n$ and the projected public key size $\hat{\ell }$. Then Construction 4.3 is an $(n\log B,w)$-universal weak hash proof system with the encapsulated key space $\mathcal {K}=\mathbb {Z}_B^n$ and $w=n\log B-\hat{\ell }$, and has the additional structure as Definition 4.1.

Proof

According to the definition of a $\mathsf {wHPS}$, we need to prove the following three properties: correctness, universality and ciphertext indistinguishability.

Correctness. Correctness of this $\mathsf {wHPS}$ follows directly from the correctness of the underlying $\mathsf {BE}$.

Universality and the Additional Structure as Definition 4.1. Given the public key $\mathsf {pk}$ and a random invalid ciphertext , we have

$$\varPi _{\mathsf {wHPS}}.\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^{*}) = \varPi _{\mathsf {wHPS}}.\mathsf {Decap}(\varvec{x},\mathsf {CT} ^{*}) = \varvec{x} + \varvec{k}^\prime ,$$

where $\varvec{k}^\prime$ is the vector used to generate the invalid ciphertext. Clearly, this function is an efficiently computable and invertible permutation, i.e., the decryption function can be written as the permutation $\mathfrak {s}_{\varvec{k}^\prime }(\varvec{x}) = \varvec{x} + \varvec{k}^\prime$.

As this is an injective function of $\varvec{x}$ (for any fixed $\varvec{k}^\prime$), the min-entropy of $\varvec{x}$ remains the same after applying this function, i.e., $H_\infty (\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^{*}) | (h, \mathsf {CT} ^*)) = H_\infty (\varvec{x} + \varvec{k}^\prime | (h, \mathsf {CT} ^*)) = H_\infty (\varvec{x} | (h, \mathsf {CT} ^*))$. Moreover, we note that given h, $\mathsf {CT} ^*$ is independent of $\varvec{x}$, so $H_\infty (\varvec{x}|(h,\mathsf {CT} ^{*})) = H_\infty (\varvec{x} | h)$. Therefore, we have

$$ H_\infty (\varvec{x} + \varvec{k} | (h ,\mathsf {CT} ^{*})) = H_\infty (\varvec{x}|(h,\mathsf {CT} ^{*})) = H_\infty (\varvec{x} | h)\ge H_\infty (\varvec{x})-|h|=n\log B-\hat{\ell }.$$

It is also clear from the argument that the scheme $\varPi _\mathsf {wHPS}$ satisfies the additional structure as Definition 4.1, i.e. the secret key $\mathsf {sk}$ has the structure $\varvec{x} \in \mathbb {Z}_B^n$, and $\varPi _{\mathsf {wHPS}}.\mathsf {Decap}(\mathsf {sk},\mathsf {CT} ^{*}) = \varvec{x} + \varvec{k}^\prime$, where $\varvec{k}^\prime$ is a vector related to the invalid ciphertext $\mathsf {CT} ^{*}$.

Ciphertext Indistinguishability. Directly from the security of $\mathsf {BE}$, we can prove that the ciphertexts output by $\varPi _{\mathsf {wHPS}}.\mathsf {Encap}(\mathsf {pk})$ and $\varPi _{\mathsf {wHPS}}.\mathsf {Encap}^{*}(\mathsf {pk})$ are computationally indistinguishable, even given the secret key $\varvec{x}$.    $\square$

5 Generic Construction $\mathsf {PKE}$ from $\mathsf {wHPS}$

In this section, we show that a weak hash proof system with the additional structure as Definition 4.1 can be used to obtain a public-key encryption scheme that is simultaneously leakage resilient and $\mathsf {KDM}$ secure.

Before presenting our generic construction, we introduce a useful definition of block source, and a parallel repetition description of randomness extractor.

Definition 5.1

(Block Source [26]). A random variable $S= (S_1,\dots , S_m)$ is a $(e_1,\dots , e_m)$ block source if for every $s_1,\dots ,s_{i-1}$, $S_i |_{S_1=s_1, S_2 = s_2, \dots , S_{i-1} = s_{i-1}}$ is a $e_i$-source. If $e_1=e_2=\dots = e_m =e$, then we call S an $m \times e$ block source.

Definition 5.2

(Parallel Repetition of Extractor). For any input $\varvec{s}=(s_1,\ldots ,s_m)\in \mathcal {S}^m$ and an underlying extractor $\mathsf {Ext}:\mathcal {R}\times \mathcal {S}\rightarrow \mathcal {Y}$, we use $\mathsf {Ext} _{||}(r,\varvec{s})=(r,\mathsf {Ext} (r,s_1),\ldots ,\mathsf {Ext} (r,s_m))$ to denote a parallel repetition of extractor.

Next, our generic construction of $\mathsf {PKE}$ can be derived from $\mathsf {wHPS}$ and $\mathsf {Ext}$ in the following way.

Construction 5.3

(${\mathbf {\mathsf{{PKE}}}}$ from ${\mathbf {\mathsf{{wHPS}}}}$ and ${\mathbf {\mathsf{{Ext}}}}$). Suppose that $\varPi _{\mathsf {wHPS}}=\varPi _{\mathsf {wHPS}}.\{\mathsf {Setup}, \mathsf {Encap}, \mathsf {Encap}^*,\mathsf {Decap}\}$ is a $\mathsf {wHPS}$ with the secret key space and the encapsulated key space being $\mathcal {S}= \mathcal {K}=\mathbb {Z}_B^n$ with $n=n^\prime \cdot m$, and $\mathsf {Ext}: \mathcal {R}\times \mathbb {Z}_B^{n^\prime } \rightarrow \mathcal {M}$ is an $(e, \mathsf {poly})$-reusable extractor. Then, for any polynomial integer t, we define a public-key encryption scheme $\varPi _{\mathsf {PKE}}=\varPi _{\mathsf {PKE}}.\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ with message space $\mathcal {M}^{t\times m}$ as follows:

• $\varPi _{\mathsf {PKE}}.\mathsf {KeyGen}(1^\lambda )$: The algorithm runs , and then outputs $\mathsf {pk}:= \mathsf {pk} ^{\varPi _{\mathsf {wHPS}}}$ and $\mathsf {sk}:= \mathsf {sk} ^{\varPi _{\mathsf {wHPS}}}$.

• $\varPi _{\mathsf {PKE}}.\mathsf {Enc}(\mathsf {pk},\varvec{\mu })$: Given a public-key $\mathsf {pk}$ and a message $\varvec{\mu }=(\varvec{\mu }_1,\ldots ,\varvec{\mu }_t)\in \mathcal {M}^{t\times m}$ as input with each $\varvec{\mu }_j\in \mathcal {M}^m$, the algorithm runs $\mathsf {wHPS}.\mathsf {Encap}$ to generate for $\varvec{k} \in \mathbb {Z}_B^n$. The algorithm interprets $\varvec{k}\in (\mathbb {Z}_B^{n^\prime })^m$, and then samples for $j\in [t]$. Furthermore, the algorithm computes and outputs $\mathsf {CT} =({\mathsf {CT}}_0,{\mathsf {CT}}_1,\ldots ,{\mathsf {CT}}_{t})$, where

  $$\mathsf {CT} _j=(\mathsf {CT} _j^{(1)},\mathsf {CT} _j^{(2)})=(r_j,\mathsf {Ext} _{||}(r_j,\varvec{k})+\varvec{\mu }_j), \text{ for } j \in [t].$$

• $\varPi _{\mathsf {PKE}}.\mathsf {Dec}(\mathsf {sk},\mathsf {CT})$: Given a ciphertext $\mathsf {CT} =({\mathsf {CT}}_0,{\mathsf {CT}}_1,\ldots ,{\mathsf {CT}}_{t})$ and a secret key $\mathsf {sk}$ as input, the algorithm first computes $\varvec{k}^\prime =\mathsf {wHPS}.\mathsf {Decap}(\mathsf {sk},\mathsf {CT} _0)$, and then outputs $\varvec{\mu }=(\varvec{\mu }_1^\prime ,\ldots ,\varvec{\mu }_{t}^\prime )$, where

  $$\varvec{\mu }_j^\prime =\mathsf {CT} _j^{(2)}-\mathsf {Ext} _{||}(\mathsf {CT} _j^{(1)},\varvec{k}^\prime ).$$

Our construction achieves $\mathsf {KDM}$ security and leakage-resilience simultaneously. We summarize the results in the following theorem.

Theorem 5.4

Assume that (1) $\varPi _{\mathsf {wHPS}}$ is a $(n\log B,w)$-universal $\mathsf {wHPS}$ with the secret key space and the encapsulated key space being $\mathcal {S}= \mathcal {K}= \mathbb {Z}_B^n$, $n = m n'$, $w= n\log B - \hat{\ell }$, where $\hat{\ell }$ denotes the bit length of $\mathsf {pk}$, and $n'\log B \ge \hat{\ell } + \lambda + e$, (2) $\varPi _\mathsf {wHPS}$ has the additional structures as Definition 4.1 and the secret key does not have the additional string $\mathsf {sk} _{\varvec{x}}$, (3) the extractor $\mathsf {Ext}: \mathcal {R}\times \mathbb {Z}_B^{n^\prime } \rightarrow \mathcal {M}$ is an $(e, \mathsf {poly})$-reusable extractor, which is also homomorphic with respect to the class of linear functions $\mathcal {G}:\{\mathfrak {g}: \mathbb {Z}_B^{n^\prime } \rightarrow \mathcal {M}\}$ and robust against correlated-source attacks with respect to the class of the shift functions $\mathcal {SF} _{B,n^\prime }:\{\mathfrak {s}: \mathbb {Z}_B^{n^\prime } \rightarrow \mathbb {Z}_B^{n^\prime }\}$. Then the above scheme $\varPi _{\mathsf {PKE}}$ is

• 1. leakage-resilient against block leakage⁷, with block leakage rate $(1-\frac{e+\hat{\ell } + \lambda }{n'\log B})$ per block.

• 2. $\mathsf {KDM}$ $^{(1)}$-secure with respect to the block-affine function class $\mathcal {G} ^t=\{\mathfrak {g}':\mathbb {Z}_B^n \rightarrow \mathcal {M}^{m\times t}\}$ as defined in Definition 2.5.

• 3. The information rate is $\frac{|\mathcal {M}|mt}{|\mathsf {CT} _0| + |\mathcal {R}| t + |\mathcal {M}|mt}$, where $|\cdot |$ denotes the bit description length of its elements. As a result, for large enough t and m, we obtain rate-1 $\mathsf {KDM}$-secure $\mathsf {PKE}$ scheme.

Remark 5.5

We note that any $\mathsf {wHPS}$ (without the additional structures) and reusable extractor (without the homomorphic and robust property) already suffice to prove leakage resilience, which detailed proof is deferred to full version due to space limit. The extra properties will be used for deriving $\mathsf {KDM}$ security, which will be formally presented in Sects. 5.1 and 6. In Sect. 3.2, we have presented homomorphic extractors from $\mathsf {DDH}$ and $\mathsf {LWE}$.

5.1 Proof of $\mathsf {KDM}$ $^{(1)}$-security

In this section, we present the proof of the second part of Theorem 5.4. Our proof takes the following high-level steps:

• We first define a modified encryption algorithm $\mathsf {Enc}'$, and then switch the responses of the $\mathsf {KDM}$ queries by using $\mathsf {Enc}'$ instead of the real $\mathsf {Enc}$. By a hybrid argument, we argue that the adversary cannot distinguish whether he is answered by $\mathsf {Enc}$ or $\mathsf {Enc}'$.

• We next modify the $\mathsf {KDM}$ responses by using $\mathsf {Enc}''$, which essentially generates random strings as the ciphertexts. We argue that this is indistinguishable from the above case by the security of the reusable extractor robust against correlated-source attacks with respect to the class of shift functions (ref. Definition 2.4);

• Finally, we show that even given multiple $\mathsf {KDM}$ encryption queries, $\mathsf {Enc}''$ is indistinguishable from $\mathsf {Enc}(0)$, implying $\mathsf {KDM}$-security.

Below, we first define the modified encryption algorithm $\mathsf {Enc}'$. On input a public-key $\mathsf {pk}$, a secret-key $\mathsf {sk}:= \varvec{x}\in \mathbb {Z}_B^{n}=(\mathbb {Z}_B^{n^\prime })^{m}$ and a function $\mathfrak {g}^{\prime }\in \mathcal {G} ^t$, where $\mathfrak {g}^{\prime }$ can be indexed by a vector $\varvec{a}=(\varvec{a}_1^\top ,\ldots ,\varvec{a}_t^\top )^\top \in \mathcal {M}^{m\times t}$ and t functions $\mathfrak {g}_1,\dots , \mathfrak {g}_t \in \mathcal {G}$ (ref. Definition 2.5), where for each $j\in [t]$, $\varvec{a}_j=(a_{j,1},\ldots ,a_{j,m})^\top \in \mathcal {M}^m$, $\mathfrak {g}_j=(\mathfrak {g}_{j,1},\ldots ,\mathfrak {g}_{j,m})$ with $\mathfrak {g}_{j,l}:\mathbb {Z}_B^{n^\prime }\rightarrow \mathcal {M}$ and $l\in [m]$, the algorithm does the following:

• 1. Generate an invalid ciphertext $\mathsf {CT} ^{*}_{0}$. By Property 4 in Definition 4.1, set $\varvec{x}' := \mathsf {Decap}(\mathsf {sk}, \mathsf {CT} ^{*}_{0})=\varvec{x}+\varvec{k}'$ for some $\varvec{k}'$.

• 2. Compute $t\cdot m$ invertible functions $\{\mathfrak {h}_{1,l}\}_{l\in [m]},\dots , \{\mathfrak {h}_{t,l}\}_{l\in [m]}$ such that $\mathsf {Ext} _{||}(r,\varvec{s}) + \mathfrak {g}_j(\varvec{s}) =(\mathsf {Ext} (r,\varvec{s}_1),\ldots ,\mathsf {Ext} (r,\varvec{s}_m))+(\mathfrak {g}_{j,1}(\varvec{s}_1),\ldots ,\mathfrak {g}_{j,m}(\varvec{s}_m))= (\mathsf {Ext} (\mathfrak {h}_{j,1}(r),\varvec{s}_1),\ldots ,\mathsf {Ext} (\mathfrak {h}_{j,m}(r),\varvec{s}_m))$ for any $j\in [t]$, by the property of homomorphic extractor (ref. Definition 3.4). Here, $\varvec{s}$ is a block source, i.e., $\varvec{s}=(\varvec{s}_1,\ldots ,\varvec{s}_m)$.

• 3. Then sample t random seeds $r_1,\dots , r_t \in \mathcal {R}$ for the extractor, and compute $z_j = \{\mathsf {Ext} (\mathfrak {h}_{j,l}(r_{j}), \varvec{x}^{\prime }_l)-\mathfrak {g}_{j,l}(\varvec{k}'_l)+a_{j,l}\}_{l\in [m]}$ for $j\in [t]$, where $\varvec{x}^{\prime }=(\varvec{x}^{\prime }_l)_{l\in [m]}$ and $\varvec{k}^{\prime }=(\varvec{k}^{\prime }_l)_{l\in [m]}$.

• 4. Output the ciphertext $\mathsf {CT} ^{\prime }$: $\big (\mathsf {CT} ^{*}_{0}, r_1,z_1,\dots ,r_t, z_t\big ).$

Then, we define the other modified encryption algorithm $\mathsf {Enc}''$:

• 1. Generate an invalid ciphertext $\mathsf {CT} ^{*}_{0}$.

• 2. Then for each $j\in [t]$, sample and ;

• 3. Output the ciphertext $\mathsf {CT} ^{\prime \prime }$: $\big (\mathsf {CT} ^{*}_{0}, r_1,z_1,\dots ,r_t, z_t\big ).$

Furthermore, we define a series of hybrids as follows:

• $\mathbf {Hybrid}~\mathsf {H} _{0}$: This hybrid is identical to the original $\mathsf {KDM}$ queries case, i.e. the responses of all the Q $\mathsf {KDM}$ queries are generated as the real encryptions of the $\mathfrak {g}^{\prime (i)}(\mathsf {sk})$ for $i\in [Q]$.

• $\mathbf {Hybrid}~\mathsf {H} _{0.i}$ for each $i \in [Q]$: Upon receiving the first i $\mathsf {KDM}$ queries, this hybrid uses $\mathsf {Enc}'$ to reply and then generates the remaining $\mathsf {KDM}$ responses according to the original encryption algorithm as $\mathsf {H} _0$.

• $\mathbf {Hybrid}~\mathsf {H} _{1}$: This hybrid replies all $\mathsf {KDM}$ queries with $\mathsf {Enc}''$.

• $\mathbf {Hybrid}~\mathsf {H} _{2}$: This hybrid replies all $\mathsf {KDM}$ queries with $\mathsf {Enc}(0)$.

Let events $\mathcal {E}_0$, $\mathcal {E}_1$, $\mathcal {E}_2$ denote that the $\mathsf {KDM}$ adversary $\mathcal {A}$ outputs 1 in $\mathsf {H} _0$, $\mathsf {H} _1$, and $\mathsf {H} _2$, respectively. Similarly, we define events $\mathcal {E}_{0.i}$. To show that $\mathsf {Pr}[\mathcal {E}_0] \approx \mathsf {Pr}[\mathcal {E}_2]$, we will take the following path:

$$\mathsf {Pr}[\mathcal {E}_0] \approx \mathsf {Pr}[\mathcal {E}_{0.1}]\approx \dots \approx \mathsf {Pr}[\mathcal {E}_{0.Q}] \approx \mathsf {Pr}[\mathcal {E}_1] \approx \mathsf {Pr}[\mathcal {E}_2].$$

We note that proving indistinguishability of $\mathsf {H} _1$ and $\mathsf {H} _2$ follows essentially the same idea from proving its semantic security. This can be captured in the proof of leakage resilience in the full version, so we just omit the proof to avoid repetition. For notational convenience, we define $\mathsf {H} _{0.0}:=\mathsf {H} _0$.

Finally, we use the following three lemmas to accomplish the above mentioned proof idea. Due to space limit, we defer the detailed proof to the full version.

Lemma 5.6

For $i\in [Q]$, $\big |\mathsf {Pr}[\mathcal {E}_{0.i-1}]-\mathsf {Pr}[\mathcal {E}_{0.i}]\big |\le \mathsf {negl} (\lambda )$, assuming the ciphertext indistinguishability of the underlying $\mathsf {wHPS}$.

Lemma 5.7

$\big |\mathsf {Pr}[\mathcal {E}_{0.Q}]-\mathsf {Pr}[\mathcal {E}_{1}]\big |\le \mathsf {negl} (\lambda )$, assuming that $(e,\mathsf {poly})$-reusable extractor is homomorphic with respect to the class of linear functions $\mathcal {G}:\{\mathfrak {g}: \mathbb {Z}_B^{n^\prime } \rightarrow \mathcal {M}\}$ and robust against correlated-source attacks with respect to the class of the shift functions $\mathcal {SF} _{B,n^\prime }:\{\mathfrak {s}: \mathbb {Z}_B^{n^\prime } \rightarrow \mathbb {Z}_B^{n^\prime }\}$.

Lemma 5.8

For $i\in [Q]$, $\big |\mathsf {Pr}[\mathcal {E}_{1}]-\mathsf {Pr}[\mathcal {E}_{2}]\big |\le \mathsf {negl} (\lambda )$, assuming the ciphertext indistinguishability of the underlying $\mathsf {wHPS}$.

Combining Lemma 5.6, 5.7 and 5.8, we can conclude that the advantage $\mathbf {Adv}_{\mathsf {PKE},\mathcal {A}}^{{\mathcal {F}\text {-}\mathsf{KDM}}}(\lambda )$ of $\mathcal {A}$ in the KDM security game satisfies that:

$$\mathbf {Adv}_{\mathsf {PKE},\mathcal {A}}^{{\mathcal {F}\text {-}\mathsf{KDM}}}(\lambda )\le (Q+2)\cdot \mathsf {negl} (\lambda )\le \mathsf {negl} (\lambda ). $$

This completes the proof that $\varPi _\mathsf {PKE}$ in Construction 5.3 is $\mathsf {KDM}^{(1)}$-secure with respect to $\mathcal {G} ^t$.

6 Achieving $\mathsf {KDM}$ $^{(\bar{n})}$-security from $\mathsf {KDM}$ $^{(1)}$-security

In this section, we show how to upgrade our Construction 5.3 to achieve $\mathsf {KDM}^{(\bar{n})}$-security for an unbounded polynomial $\bar{n}$. To achieve this, we first define a more general design paradigm called $\mathsf {BE}$ -based scheme, capturing several important features of Construction 5.3. Then we identify two homomorphic properties of $\mathsf {BE}$-based scheme, which only implies the $\mathsf {KDM}^{(\bar{n})}$-security for bounded polynomial $\bar{n}$. Finally, we define an additional pseudorandom property for $\mathsf {BE}$-based scheme, and prove $\mathsf {KDM}^{(\bar{n})}$-security for unbounded polynomial $\bar{n}$ with all these properties.

6.1 $\mathsf {BE}$-Based $\mathsf {PKE}$and Its Two Key-Homomorphic Properties

Definition 6.1

(${\mathbf {\mathsf{{BE}}}}$-based ${\mathbf {\mathsf{{PKE}}}}$). Let $\mathsf {BE}$ be a batch encryption as Definition 2.1. A $\mathsf {BE}$-based $\mathsf {PKE}$  $\varPi$ is a public-key encryption scheme with the following properties: (1) the secret key of $\varPi$ is a vector $\varvec{x} \in \mathbb {Z}_B^n$ for some $B,n\in \mathbb {Z}$, as in the scheme $\mathsf {BE}$, (2) the public key is $(\mathsf {CRS}, \mathsf {H} (\mathsf {CRS},\varvec{x}))$, where $\mathsf {CRS}$ is generated by $\mathsf {BE}.\mathsf {Setup}$, and $\mathsf {H} (\cdot , \cdot )= \mathsf {BE}.\mathsf {KeyGen} (\cdot , \cdot )$ is the projection function of $\mathsf {BE}$. In this way, $\mathsf {CRS}$ is independent of the secret key.

Clearly, Construction 5.3 is $\mathsf {BE}$-based $\mathsf {PKE}$. Next, we identify two crucial key-homomorphic properties on $\mathsf {BE}$-based $\mathsf {PKE}$ schemes, which can be used to achieve the $\mathsf {KDM}^{(\bar{n})}$-security.

Property 1: There is a deterministic algorithm $\mathcal {T} _1$ that takes as input a pair $(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}))$ and a vector $\varvec{k}\in \mathbb {Z}_B^n$, and outputs $(\mathsf {CRS}^\prime ,\mathsf {H} (\mathsf {CRS}^\prime ,\varvec{x}+\varvec{k}))$, i.e., $\mathcal {T} _1(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}),\varvec{k})=(\mathsf {CRS}^\prime ,\mathsf {H} (\mathsf {CRS}^\prime ,\varvec{x}+\varvec{k})).$

Moreover, for any vectors $\varvec{x},\varvec{k}\in \mathbb {Z}_B^n$ and , the following two distributions are identical (or statistically close):

$$\left( \mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}+\varvec{k}),\varvec{x},\varvec{k}\right) \equiv \left( \mathcal {T} _1(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}),\varvec{k}),\varvec{x},\varvec{k}\right) .$$

Property 2: There exists a deterministic algorithm $\mathcal {T} _2$ that takes a pair $(\mathsf {CT}, \varvec{k})$ as input and outputs a ciphertext $\mathsf {CT} '$, i.e., $\mathcal {T} _2(\mathsf {CT},\varvec{k})=\mathsf {CT} ^\prime$. Moreover, for any message $\mu \in \mathcal {M}$, vectors $\varvec{x}, \varvec{k}\in \mathbb {Z}_B^n$, and $\mathsf {CRS}$, the following distributions are identical (or statistically close):

$$\left( \mathsf {CT} _1,\mathcal {T} _1 (\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}), \varvec{k}),\varvec{x},\varvec{k}\right) \equiv \left( \mathcal {T} _2(\mathsf {CT},\varvec{k}), \mathcal {T} _1(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}), \varvec{k}), \varvec{x},\varvec{k}\right) ,$$

where $\mathsf {CT} \leftarrow \varPi .\mathsf {Enc}(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}),\mu )$, and $\mathsf {CT} _1 \leftarrow \varPi .\mathsf {Enc}(\mathsf {CRS},\mathsf {H} (\mathsf {CRS},\varvec{x}+\varvec{k}),\mu )$.

Remark 6.2

These two properties can also be defined for $\mathsf {BE}$ schemes. Furthermore, if the underlying $\mathsf {BE}$ scheme has these two properties, Construction 5.3 would inherit these two properties, due to its designs of public key and ciphertext.

6.2 Intermediate Scheme $\varPi ^{\bar{n}}$

Following the above mentioned $\mathsf {BE}$-based $\mathsf {PKE}$ scheme $\varPi =\varPi .\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$, we define the following intermediate scheme $\varPi ^{\bar{n}}$.

Construction 6.3

(Intermediate ${\mathbf {\mathsf{{BE}}}}$-based ${\mathbf {\mathsf{{PKE}}}}$ ${\varvec{\varPi }}^{\bar{{\varvec{n}}}}$). Given a $\mathsf {BE}$-based $\mathsf {PKE}$ $\varPi =\varPi .\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ with the message space $\mathcal {M}$, we construct a new scheme $\varPi ^{\bar{n}}=\varPi ^{\bar{n}}.\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ with the same message space $\mathcal {M}$ as follows:

• $\varPi ^{\bar{n}}.\mathsf {KeyGen}(1^\lambda ,1^{\bar{n}})$: The algorithm does the following steps:

  • 1. Take the security parameter $\lambda$ and an integer $\bar{n}\in \mathbb {N}$ as input, run $\varPi .\mathsf {KeyGen}$ for $\bar{n}$ times to obtain for $1\le i\le \bar{n}$, where all these $\mathsf {CRS}_i$ contain the same size parameter $B\in \mathbb {Z}$.

  • 2. Choose a random vector to generates $h_i=\mathsf {H} (\mathsf {CRS}_i,\varvec{x})$ for $1\le i\le \bar{n}$;

  • 3. Output $\mathsf {pk}:=(\mathsf {pk} _i)_{1\le i\le \bar{n}}$ and $\mathsf {sk}:= \varvec{x}$, where $\mathsf {pk} _i=(\mathsf {CRS}_i,h_i)$.

• $\varPi ^{\bar{n}}.\mathsf {Enc}(\mathsf {pk},\mu )$: Given a public-key $\mathsf {pk}$ and a message $\mu \in \mathcal {M}$ as input, the algorithm runs $\varPi .\mathsf {Enc}$ for $\bar{n}$ times to generate for $1\le i\le \bar{n}$, and then outputs ${\mathsf {CT}}=({\mathsf {CT}}_1,\ldots ,{\mathsf {CT}}_{\bar{n}})$ as the ciphertext of $\mu \in \mathcal {M}$.

• $\varPi ^{\bar{n}}.\mathsf {Dec}(\mathsf {sk},{\mathsf {CT}})$: Given a ciphertext ${\mathsf {CT}}=({\mathsf {CT}}_1,\ldots ,{\mathsf {CT}}_{\bar{n}})$ and a secret key $\mathsf {sk}$ as input, the algorithm runs $\varPi .\mathsf {Dec}$ to generate $\mu ^\prime =\varPi .\mathsf {Dec}(\mathsf {sk},\mathsf {CT} _i)$ for some $i\in [\bar{n}]$, and then output $\mu ^\prime$ as a plaintext for $\mathsf {CT}$.

We note that the correctness of the scheme $\varPi ^{\bar{n}}$ follows clearly from that of $\varPi$. Next we present a $\mathsf {KDM}$-security reduction between $\varPi$ and $\varPi ^{\bar{n}}$.

Theorem 6.4

(${\mathbf {\mathsf{{KDM}}}}^{\mathbf{(}\bar{{\varvec{n}}}{} \mathbf{)}}$-security of ${\varvec{\varPi }}$). Suppose that (1) a $\mathsf {BE}$-based $\mathsf {PKE}$ scheme $\varPi$ satisfies Properties 1 and 2 in Sect. 6.1, and (2) the intermediate scheme $\varPi ^{\bar{n}}$ in Definition 6.3 is $\mathsf {KDM}^{(1)}$-security with respect to the class $\mathcal {G} =\{\mathfrak {g}:\mathcal {SK} \rightarrow \mathcal {M}\}$ of all affine (resp., block-affine) functions from $\mathcal {SK}$ to $\mathcal {M}$. Then $\varPi$ is $\mathsf {KDM}$ $^{(\bar{n})}$-secure with respect to the class $\mathcal {F}=\{\mathfrak {f}:\mathcal {SK} ^{\bar{n}}\rightarrow \mathcal {M}\}$ of all affine (resp., block-affine) functions from $\mathcal {SK} ^{\bar{n}}$ to $\mathcal {M}$.

Due to the limitation of space, the detailed proof is deferred to the full version.

Remark 6.5

Our construction can support more general relationship between $\mathcal {F}$ and $\mathcal {G}$. Particularly, the theorem also holds for the following relation. For every $\varvec{k}_1,\dots ,\varvec{k}_{\bar{n} }$ and $\mathfrak {h}\in \mathcal {F}$, we have $\mathfrak {g}_{\varvec{k}_1,\dots , \varvec{k}_{\bar{n}}} (\varvec{x}) := \mathfrak {h}(\varvec{x} + \varvec{k}_1, \dots , \varvec{x} + \varvec{k}_{\bar{n}}) \in \mathcal {G}$.

6.3 Proving $\mathsf {KDM}^{(1)}$-Security of $\varPi ^{\bar{n}}$

In this section, we first define the required new pseudorandom property, and then show how it derives $\mathsf {KDM}^{(1)}$-security of $\varPi _\mathsf {PKE}^{\bar{n}}$ for unbounded polynomial $\bar{n}$. In the next section, we show how to construct such an underlying $\mathsf {BE}$.

Definition 6.6

Let $\mathsf {Ext}: \mathcal {R}\times \mathbb {Z}_B^n \rightarrow \mathcal {M}$ be some (reusable) extractor. A $\mathsf {BE}$-based $\mathsf {PKE}$ satisfies an additional pseudorandom property if the following holds. For any polynomial $\bar{n} = \mathsf {poly}(\lambda )$, the following two distributions are computationally indistinguishable:

$$\begin{aligned}&\left( \left( \begin{array}{l} {\mathsf {CRS}_1}, \cdots , {\mathsf {CRS}_{\bar{n}}} \\ {~~h_1}, ~\cdots , {~~h_{\bar{n}}} \\ \end{array} \right) , \left\{ r_i, \mathsf {Ext} (r_i, \varvec{x} + \varvec{k}_i)\right\} _{i\in [t]}\right) \\ \approx _c&\left( \left( \begin{array}{l} {\mathsf {CRS}_1}, \cdots , {\mathsf {CRS}_{\bar{n}}} \\ {~~u_1}, ~\cdots , {~~u_{\bar{n}}} \\ \end{array} \right) , \left\{ r_i, u_i'\right\} _{i\in [t]}\right) \end{aligned}$$

where $\{\mathsf {CRS}_i\}_{i\in [\bar{n}]}$, $\{u_i\}_{i\in [\bar{n}]}$ and $\{u_i'\}_{i\in [\bar{t}]}$ are uniformly random, , and $h_i=\mathsf {H} (\mathsf {CRS}_i,\varvec{x})$ for all $i\in [\bar{n}]$.

Theorem 6.7

Let $\varPi _\mathsf {PKE}$ be the $\mathsf {BE}$-based scheme as Construction 5.3. Suppose the underlying $\mathsf {BE}$ satisfies the pseudorandom property as Definition 6.6. Then for any polynomial $\bar{n}$, the intermediate scheme $\varPi _{\mathsf {PKE}}^{\bar{n}}$ is $\mathsf {KDM}$ $^{(1)}$-secure with respect to all block-affine functions.

The proof of this theorem is similar to that of Theorem 5.4. Particularly, we would switch all the real $\mathsf {KDM}$ responses to $\mathsf {Enc}'$ as in the $\mathbf {Hybrid}~\mathsf {H} _{0,Q}$, and then use the reusable extractor (against shift functions) to further switch the responses to $\mathsf {Enc}''$ as in the $\mathbf {Hybrid}~\mathsf {H} _1$. The key observation is the following: $\mathsf {H} (\mathsf {CRS}, \varvec{x})$ does not leak $\varvec{x}$ in the computational sense and can be used in connection with the extractor. Thus, the same argument of Theorem 5.4 goes through in this case.

Due to the limitation of space, we defer the detailed proof and the constructions of the required $\mathsf {BE}$ to the full version.

Summing up Theorems 6.4, 6.7 and the instantiations of the required $\mathsf {BE}$ in full version, we conclude that for any polynomial $\bar{n}$, Construction 5.3 is $\mathsf {KDM}^{(\bar{n})}$-secure with respect to block-affine functions.

7 Putting Things Together

By instantiating Construction 5.3 with (1) the specific reusable extractor from $\mathsf {LWE}$ in Construction 3.6 and (2) the $\mathsf {LWE}$-based $\mathsf {BE}$ in full version. we are able to achieve the following corollary via Theorems 6.4, 6.7.

Corollary 7.1

Assuming that $\mathsf {LWE}$ is hard, there exists a rate-1 (both information and leakage rates) $\mathsf {PKE}$ that is leakage resilient against block leakage and $\mathsf {KDM}^{(\bar{n})}$-secure w.r.t. block-affine functions for any unbounded polynomial $\bar{n}$.

Similarly, by instantiating Construction 5.3 with (1) the specific reusable extractor from $\mathsf {DDH}$ in Construction 3.8 and (2) the $\mathsf {DDH}$-based $\mathsf {BE}$ in full version, we are able to achieve the following corollary via Theorems 6.4, 6.7:

Corollary 7.2

Assuming that $\mathsf {DDH}$ is hard, there exists a rate-1 (both information and leakage rates) $\mathsf {PKE}$ that is leakage resilient against block leakage and $\mathsf {KDM}^{(\bar{n})}$-secure w.r.t. block-affine functions for any unbounded polynomial $\bar{n}$.

We notice that the overall construction of the $\mathsf {DDH}$-based scheme resembles a modification of the scheme of [9]. We do not present this variant. Instead, we take a more modular approach by identifying a framework that suffices for $\mathsf {KDM}$ security and can be instantiated from various assumptions.

Remark 7.3

The class of block affine functions is more restricted than the regular (bit) affine class. In particular, each output component of a block affine function can depend only on one block of the input, whereas the output of a bit affine function can depend on every bit of the input. Nevertheless, this restricted class already suffices for $\mathsf {KDM}$ amplification to any bounded-size functions, and moreover allows constructions with better information rate. We discuss how to amplify the function class in the following section.

8 Extensions

In this section, we further extend our above results in Sect. 7 in two directions: the first one is to enlarge the class of $\mathsf {KDM}$ functions via Garbled Circuits; the second one is to generalize our results to the setting of $\mathsf {IBE}$.

8.1 Garbled Circuits

In this section, we recall the key ingredient for the $\mathsf {KDM}$ amplification of Applebaum [4]: Garbled Circuits.

Definition 8.1

(Garbled Circuits [12]). A garbling scheme consists of three algorithms $(\mathsf {Garble},\mathsf {Eval},\mathsf {Sim})$ as follows:

• $\mathsf {Garble}(1^\lambda ,1^n,1^m,C)$ is a $\textsc {ppt}$ algorithm that first takes as input $\lambda$, a circuit $C:\{0,1\}^n\rightarrow \{0,1\}^m$ together with its input length n and output length m, and then outputs a garbled circuit $\widehat{C}$ along with labels $\{\mathsf {lab}_{i,b}\}_{i\in [n],b\in \{0,1\}}$, where each label $\mathsf {lab}_{i,b}\in \{0,1\}^\lambda$.

• $\mathsf {Eval} (1^\lambda ,\widehat{C},\widehat{L})$ is a deterministic algorithm that first takes as input a garbled circuit $\widehat{C}$ along with a set of n labels $\widehat{L}=\{\mathsf {lab}_{i}\}_{i\in [n]}$, and then outputs a string $y\in \{0,1\}^m$.

• $\mathsf {Sim}(1^\lambda ,1^{|C|},1^n,y)$ is a $\textsc {ppt}$ algorithm that first takes as input $\lambda$ and a bit description length of circuit C, an input length n and a string $y\in \{0,1\}^m$, then outputs a simulated garbled circuit $\widetilde{C}$ and labels $\widetilde{L}=\{\widetilde{\mathsf {lab}}_i\}_{i\in [n]}$.

Moreover, the garbling scheme needs to satisfy the following two properties.

• 1. Correctness. For any circuit $C:\{0,1\}^n\rightarrow \{0,1\}^m$, any input $x=(x_i)_{i\in [n]}\in \{0,1\}^n$, and any $(\widehat{C},\{\mathsf {lab}_{i,b}\})\leftarrow \mathsf {Garble}(C)$, it holds $\mathsf {Eval} (\widehat{C},\widehat{L})=C(x)$ where $\widehat{L}=\{\mathsf {lab}_{i,x_i}\}_{i\in n}$.

• 2. Simulation Security. For any circuit $C:\{0,1\}^n\rightarrow \{0,1\}^m$, any input $x=(x_i)_{i\in [n]}\in \{0,1\}^n$, the following two distributions are computational indistinguishability:

  $$\begin{aligned}&\{(\widehat{C},\widehat{L}):(\widehat{C},\{\mathsf {lab}_{i,b}\})\leftarrow \mathsf {Garble}(C),\widehat{L}=\{\mathsf {lab}_{i,x_i}\}_{i\in n}\} \\ \approx&\{(\widetilde{C},\widetilde{L}):(\widetilde{C},\widetilde{L})\leftarrow \mathsf {Sim}(1^\lambda ,1^{|C|},1^n,C(x))\}. \end{aligned}$$

8.2 Bootstrapping to Larger Classes of KDM Functions

We first present a bootstrapped variant of Construction 5.3 by using the technique of garbled circuits.⁸ Then, we analyze the $\mathsf {KDM}$-security and information rate of this improved scheme.

Construction 8.2

(Amplification of Our ${\mathbf {\mathsf{{KDM}}}}$ Security). Let $\varPi =\varPi .\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ be the $\mathsf {PKE}$ of Construction 5.3 instantiated with parameter $B=2$ such that its secret key size $|\mathsf {sk} |=n=n^\prime \cdot m$. And let $\mathsf {GC}=\mathsf {GC}.(\mathsf {Garble},\mathsf {Eval},\mathsf {Sim})$ be a garbled scheme, whose label size $|\mathsf {lab}_{i,j}|$ is equivalent to the bit length of element in $\mathcal {M}$. Then, we construct a new scheme $\widehat{\varPi }=\widehat{\varPi }.\{\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec}\}$ with the message space $\widehat{\mathcal {M}}=\mathcal {M}^{(t-n^\prime +1)\times m}$ as follows:

• $\widehat{\varPi }.\mathsf {KeyGen}(1^\lambda )$: The algorithm gets $(\mathsf {pk},\mathsf {sk})$ just as $\varPi .\mathsf {KeyGen}(1^\lambda )$.

• $\widehat{\varPi }.\mathsf {Enc}(\mathsf {pk},\mu )$: Given a public-key $\mathsf {pk}$ and a message $\mu =\{\mu _{i,j}\}_{i\in [t-n^\prime +1],j\in [m]}\in \!\!\!\mathcal {M}^{(t-n^\prime +1)\times m}$ as input, the algorithm first invokes $(\widetilde{C},\widetilde{L})\leftarrow \mathsf {GC}.\mathsf {Sim}(\mu _{1,1},\ldots ,\mu _{1,m})$ with $\widetilde{L}=\{\mathsf {lab}_{i,j}\}_{i\in [n^\prime ],j\in [m]}$, and then runs $\varPi .\mathsf {Enc}$ to output the ciphertext

  $$\begin{aligned} \mathsf {CT}:=&\Big (\widetilde{C},\varPi .\mathsf {Enc}(\mathsf {pk},\widetilde{L},\{\mu _{i,j}\}_{i\in [2,t-n^\prime +1],j\in [1,m]})\Big )\\ =&\Big (\widetilde{C},\mathsf {CT} _{0}, r_{1},\{\mathsf {Ext} (r_{1}, \varvec{k}_{1})+\mathsf {lab}_{1,1},\ldots ,\mathsf {Ext} (r_{1}, \varvec{k}_{m})+\mathsf {lab}_{1,m}\},\\&\ \ \ \ \ \ \dots ,r_{n^\prime },\{\mathsf {Ext} (r_{n^\prime }, \varvec{k}_{1})+\mathsf {lab}_{n^\prime ,1},\ldots ,\mathsf {Ext} (r_{n^\prime }, \varvec{k}_{m})+\mathsf {lab}_{n^\prime ,m}\},\\&\ \ \ \ \ \ \ \ \ \ \ \,r_{n^\prime +1},\{\mathsf {Ext} (r_{n^\prime +1}, \varvec{k}_{1})+\mu _{2,1},\ldots ,\mathsf {Ext} (r_{n^\prime +1}, \varvec{k}_{m})+\mu _{2,m}\},\\&\ \ \ \ \ \ \dots ,r_{t},\{\mathsf {Ext} (r_{t}, \varvec{k}_{1})+\mu _{(t-n^\prime +1),1},\ldots ,\mathsf {Ext} (r_{t}, \varvec{k}_{m})+\mu _{(t-n^\prime +1),m}\}\Big ). \end{aligned}$$

  Here, we use $\{\mathsf {lab}_{i,j}\}_{i\in [n^\prime ]}$ to denote the garbled results of the j-th block of $\mathsf {sk}$ for any $j\in [m]$.

• $\widehat{\varPi }.\mathsf {Dec}(\mathsf {sk},{\mathsf {CT}})$: Given a ciphertext ${\mathsf {CT}}$ and a secret key $\mathsf {sk}$ as input, the algorithm first runs $\varPi .\mathsf {Dec}$ to recover all $\{\mathsf {lab}_{i,j}\}_{i\in [n^\prime ],j\in [m]}$ and $\{\mu _{i,j}^\prime \}_{i\in [2,t-n^\prime +1],j\in [m]}$, and then runs $\mathsf {GC}.\mathsf {Dec}(\widetilde{C},\{\mathsf {lab}_{i,j}\})$ to get $\{\mu _{1,j}^\prime \}_{j\in [m]}$. Finally, the algorithm outputs

  $$\mu ^\prime =\{\mu ^\prime _{i,j}\}_{i\in [t-n^\prime +1],j\in [m]}\in \mathcal {M}^{(t-n^\prime +1)\times m}.$$

Remark 8.3

For simplicity of presentation, we have implicitly assumed that $|\mathsf {lab}_{i,j}|=|\mathcal {M}|$. For the more general case such that $|\mathsf {lab}_{i,j}|>|\mathcal {M}|$, we can easily handle through using many more elements in $\mathcal {M}$ to cover each $\mathsf {lab}_{i,j}$.

It is not hard to verify that the correctness of $\widehat{\varPi }$ follows from that of the underlying scheme $\varPi$ and garble scheme $\mathsf {GC}$. Below, we first argue the $\mathsf {KDM}$-security of the scheme $\widehat{\varPi }$, and then analyze its information rate.

Before presenting the formal theorem about the $\mathsf {KDM}$ security of $\widehat{\varPi }$, we define a particular $\mathsf {KDM}$ function class $\hat{\mathcal {F}}=(\mathcal {F}_{s} || \mathcal {Q} ^{\tau })$ as follows.

Definition 8.4

Let $\mathcal {F}_s$ be the class of functions of the secret key $\mathsf {sk}:=\varvec{x}\in \mathbb {Z}_B^{n}$, where the circuit size of each function in $\mathcal {F}_{s}$ is up to s. Let $\mathcal {Q} ^{\tau }$ denote the block-affine function class $\{\mathfrak {g}':\mathbb {Z}_B^n \rightarrow \mathcal {M}^{\tau \times m}\}$, which is defined similarly as in Definition 2.5. Moreover, $(\mathcal {F}_{s} || \mathcal {Q} ^{\tau })$ denotes the concatenation of two classes, i.e., every function $\mathfrak {f}$ in the class can be represented by $\mathfrak {f}= (\mathfrak {h}, \mathfrak {q})$ for some $\mathfrak {h}\in \mathcal {F}_s$ and $\mathfrak {q}\in \mathcal {Q} ^{\tau }$ such that $\mathfrak {f}(\mathsf {sk}) = (\mathfrak {h}(\mathsf {sk}) || \mathfrak {q}(\mathsf {sk}))$.

Theorem 8.5

For the parameter setting in Construction 8.2, if $\varPi$ is $\mathsf {KDM}^{(1)}$-secure with respect to $\mathcal {G} ^t=\{\mathfrak {g}':\mathbb {Z}_B^n \rightarrow \mathcal {M}^{t\times m}\}$ as defined in Definition 2.5, and $\mathsf {GC}$ is a secure garbling scheme, then $\widehat{\varPi }$ is $\mathsf {KDM}^{(1)}$-secure with respect to $\widehat{\mathcal {F}}=(\mathcal {F}_{s} || \mathcal {Q} ^{\tau })$ as defined in Definition 8.4.

Proof (Sketch)

As pointed out by [4], we just need to focus on $\mathsf {KDM}$ reduction from $\mathcal {F}_s$ to the corresponding part of block-affine function class $\mathcal {G} ^t$, denoted by $\mathcal {G} ^{n^\prime }$, i.e., $\mathcal {F}_s\le _{\mathsf {KDM}}\mathcal {G} ^{n^\prime }$. Particularly, it suffices to show that block-affine functions in $\mathcal {G} ^{n^\prime }$ can encode any bounded size circuits of $\varvec{x}\in \mathbb {Z}_2^n$, according to Applebaum’s concepts on the $\mathsf {KDM}$ reduction in [4].

More specifically, suppose that $\mathcal {A}$ is the adversary against the $\mathsf {KDM}$-security of $\widehat{\varPi }$ with respect to $\mathfrak {h}\in \mathcal {F}_s$, and $\mathcal {C}$ is the challenger for the $\mathsf {KDM}$-security of $\varPi$ with respect to $\mathcal {G} ^{n^\prime }$. Then, through using $\mathcal {A}$ as a building block, we can establish a reduction algorithm $\mathcal {B}$ to break the $\mathsf {KDM}$-security of $\varPi$ with the same advantage as that of $\mathcal {A}$.

In particular, after receiving a function $\mathfrak {h}(\cdot ) \in \mathcal {F}_s$ of $\mathsf {sk}$ from $\mathcal {A}$, $\mathcal {B}$ conducts the followings

• 1. Choose 2n labels $\{\mathsf {lab}_{i,j,0},\mathsf {lab}_{i,j,1}\}_{i\in [n^\prime ],j\in [m]}$, with $|\mathsf {sk} |=n=n^\prime \cdot m$.

• 2. For each $j\in [m]$,

  • Set a matrix $\mathbf {A}^{(j)}=(\varvec{a}_1^{(j)},\ldots ,\varvec{a}_{n^\prime }^{(j)})$ of dimension $(n^\prime \times n^\prime )$, where for $l\in [n^\prime ]$, the l-th component of $\varvec{a}_l^{(j)}$ is $(\mathsf {lab}_{l,j,1}-\mathsf {lab}_{l,j,0})$ and all others are 0.

  • Set a vector $\varvec{b}^{(j)}=(\mathsf {lab}_{1,j,0},\ldots ,\mathsf {lab}_{n^\prime ,j,0})^\top$ of $n^\prime$ dimension.

  • Take $(\mathbf {A}^{(j)})^\top$ and $\varvec{b}^{(j)}$ as the index of the j-th block-affine function $\mathfrak {g}_j(\mathsf {sk} _j) =(\mathbf {A}^{(j)})^\top \cdot \mathsf {sk} _j+\varvec{b}^{(j)}$, where $\mathsf {sk} _j\in \{0,1\}^{n^\prime }$ is the j-th block of $\mathsf {sk}$.

• 3. Send the indexes of all m block-affine functions to $\mathcal {C}$ to conduct $\mathsf {KDM}$ query.

• 4. Receive the $\mathsf {KDM}$ ciphertexts $\{\mathsf {ct} _{i,j}\}_{i\in [n^\prime ],j\in [m]}$ from $\mathcal {C}$.

• 5. Run the algorithm $\mathsf {GC}.\mathsf {Garble}$ to obtain the garbled circuit $\widehat{C}$ with respect to the $\mathsf {KDM}$ query function $\mathfrak {h}(\cdot )$ from $\mathcal {A}$.

• 6. Send $\mathsf {CT}:=(\widehat{C},\{\mathsf {ct} _{i,j}\}_{i\in [n^\prime ],j\in [m]})$ to $\mathcal {A}$.

• 7. Finally, $\mathcal {B}$ outputs whatever $\mathcal {A}$ outputs.

It is not hard to verify that $\mathsf {ct} _{i,j}$ will be a encryption of $\mathsf {lab}_{i,j,b}$ for $b:=\mathsf {sk} _{i,j}$. Thus, the above reduction process is clearly set up. Finally, this theorem holds.

   $\square$

Remark 8.6

Although Theorem 8.5 just focuses on the case of $\mathsf {KDM}^{(1)}$, the above construction and analysis can be easily (though somewhat tedious) extended to $\mathsf {KDM}^{(\bar{n})}$ for any polynomially unbounded $\bar{n}$.

Finally, we focus on the information rate of the above construction. We remark that for this amplified $\mathsf {KDM}$ function class $\hat{\mathcal {F}}=(\mathcal {F}_{s} || \mathcal {Q} ^{\tau })$, the parameters t, s and $\tau$ should satisfy: $\tau < t$ and s is the size of circuits amplified from block-affine function with outputs $(t-{\tau })$ vectors over $\mathcal {M}^m$.

By setting $\tau \gg s$, our scheme achieves the optimal information rate, i.e., $1-o(1)$. This is because although the additional garble circuit in the ciphertext and the encryption of labels will increase the ciphertext length to certain bounded size, we can use large enough $\tau \gg s$ such that the last $\tau$ part of ciphertext dominates the whole information rate.

8.3 Upgrade to KDM-Secure and Leakage Resilient $\mathsf {IBE}$

In this section, we present our general compiler to construct an $\mathsf {IBE}$ that is both $\mathsf {KDM}$-secure and leakage resilient. The compiler uses as key ingredients an $\mathsf {IB}\text {-}\mathsf {wHPS}$ (described in full version) with additional structure (ref. Remark 4.2) and an on-the-fly $\mathsf {KDM}$-secure $\mathsf {PKE}$ (described in full version). Conceptually, this general $\mathsf {IBE}$ scheme can be view as the hybrid encryption of the $\mathsf {IB}\text {-}\mathsf {wHPS}$ and $\mathsf {PKE}$: to encrypt a message m, the $\mathsf {IBE}$ encryption algorithm first generates (1) a pair of encapsulated key and ciphertext $(\mathsf {CT}, \varvec{k})$ according to the $\mathsf {IB}\text {-}\mathsf {wHPS}$, and then generates (2) a pair of session public-key and ciphertext according to the $\mathsf {PKE}$, i.e., $\mathsf {pk} = (\mathsf {CRS}, \mathsf {H} (\mathsf {CRS}, \varvec{k}) )$ and $\mathsf {Enc}(\mathsf {pk}, m)$, respectively, under the same encapsulated key $\varvec{k}$. By connecting the two security properties in a novel way, we are able to derive the desired $\mathsf {IBE}$.

Construction 8.7

(${\mathbf {\mathsf{{KDM}}}}$-secure ${\mathbf {\mathsf{{IBE}}}}$). Let be an $\mathsf {IB}\text {-}\mathsf {wHPS}$ with the encapsulated key space $\mathcal {K}$ and the identity space $\mathcal {ID}$. Let be a $\mathsf {BE}$-based $\mathsf {PKE}$. Then, we construct an $\mathsf {IBE}$ scheme for message space $\mathcal {M}$ as follows.

• : The algorithm runs , and then outputs and .

• : Given a master secret-key $\mathsf {msk}$ and an identity $\mathsf {id} \in \mathcal {ID}$ as input, the algorithm runs $\mathsf {IB}\text {-}\mathsf {wHPS}$.$\mathsf {KeyGen}$ to generate and output .

• : Given a master public-key , an identity and a message as input, the algorithm does the following steps:

  • 1. Generates ;

  • 2. Chooses an on-the-fly common reference string $\mathsf {CRS}$ for ;

  • 3. Computes where ;

  • 4. Outputs as the ciphertext of m under the identity $\mathsf {id}$.

• : Given a ciphertext and a secret key as input, the algorithm does the following steps:

  • 1. Run to generate ;

  • 2. Output .

We sketch that the above construction can be proven to be a rate-1 (both information and leakage rates) $\mathsf {IBE}$ that is leakage resilient against block leakage and $\mathsf {KDM}^{(\bar{n})}$-secure w.r.t. a restricted block-function class for any polynomial unbounded $\bar{n}$. Due to space limit, the corresponding formal theorem statement and its detailed proof are deferred to the full version.