Functional Encryption with Secure Key Leasing

Our main contributions are introducing the notion of SKFE with secure key leasing and instantiating it with standard cryptographic assumptions. More specifically,

• •

  We define the syntax and security definitions for SKFE with secure key leasing.

• •

  We achieve a transformation from standard SKFE into SKFE with secure key leasing without using additional assumptions.

In SKFE with secure key leasing, a functional decryption key is a quantum state. More specifically, the key generation algorithm takes as input a master secret key, a function $f$, and an availability bound $n$ (in terms of the number of ciphertexts), and outputs a quantum decryption key $\mathpzc{fsk}$ tied to $f$. We can generate a certificate for deleting the decryption key $\mathpzc{fsk}$. If the user of this decryption key deletes $\mathpzc{fsk}$ within the declared availability bound $n$ and the generated certificate is valid, the user cannot compute $f(x)$ from a ciphertext of $x$ anymore. We provide a high-level overview of the security definition in Section 1.3.

We can obtain bounded collusion-resistant SKFE for $\mathsf{P}/\mathsf{poly}$ with secure key leasing from OWFs since we can instantiate bounded collusion-resistant SKFE for $\mathsf{P}/\mathsf{poly}$ with OWFs.²²2If we start with fully collusion-resistant SKFE, we can obtain fully collusion-resistant SKFE with secure key leasing. Note that all building blocks in this work are post-quantum secure since we use quantum computation and we omit “post-quantum”.

Our secure key leasing notion is similar to but different from secure software leasing [AL21] for FE because adversaries in secure software leasing (for FE) must run their pirate software by an honest evaluation algorithm (on a legitimate platform). This is a severe limitation. In our FE with secure key leasing setting, adversaries do not necessarily run their pirate software (for functional decryption) by an honest evaluation algorithm and can take arbitrary attack strategies.

We develop a transformation from standard SKFE into SKFE with secure key leasing by using quantum power. In particular, we use (reusable) secret-key encryption (SKE) with certified deletion [BI20, HMNY21], where we can securely delete ciphertexts, as a building block. We also develop a technique based on the security bound amplification for FE [AJL⁺19, JKMS20] to amplify the availability bound, that is, the number of encryption queries before $\mathsf{ct}^{\ast}$ is given. This technique deviates from known multi-party-computation-based techniques for achieving bounded many-ciphertext security for SKFE [GVW12, AV19].³³3These techniques [GVW12, AV19] work as transformations from single-key FE into bounded collusion-resistant FE. However, they also work as transformations from single-ciphertext SKFE into bounded many-ciphertext SKFE. See Section 1.4 for the detail. Many-ciphertext means that SKFE is secure even if adversaries can send unbounded polynomially many queries to an encryption oracle. The security bound amplification-based technique is of independent interest since the security bound amplification is not directly related to the amplification of the number of queries. These are the main technical contributions of this work. See Section 1.3 and main sections for more details.

The other contributions are copy-protected functional decryption keys. We introduce the notion of single-decryptor FE (SDFE), where each functional decryption key is copy-protected. This notion can be seen as a stronger cryptographic primitive than FE with secure key leasing, as we argued in Section 1.1.

• •

  We define the syntax and security definitions for SDFE.

• •

  We achieve collusion-resistant public key SDFE for $\mathsf{P}/\mathsf{poly}$ from sub-exponentially secure indistinguishability obfuscation (IO) and the sub-exponential hardness of the learning with errors problem (QLWE assumption).

First, we transform single-key PKFE for $\mathsf{P}/\mathsf{poly}$ into single-key SDFE for $\mathsf{P}/\mathsf{poly}$ by using SDE. Then, we transform single-key SDFE $\mathsf{P}/\mathsf{poly}$ into collusion-resistant SDFE for $\mathsf{P}/\mathsf{poly}$ by using an IO-based key bundling technique [KNT21, BNPW20]. We can instantiate SDE with IO and the QLWE assumption [CLLZ21, CV21] and single-key PKFE for $\mathsf{P}/\mathsf{poly}$ with PKE [SS10, GVW12].

We first recall a standard SKFE scheme. It consists of four algorithms $(\mathsf{Setup},\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$. $\mathsf{Setup}$ is given a security parameter $1^{\lambda}$ and a collusion bound $1^{q}$ and generates a master secret key $\mathsf{msk}$. $\mathsf{Enc}$ is given $\mathsf{msk}$ and a plaintext $x$ and outputs a ciphertext $\mathsf{ct}$. $\mathsf{KG}$ is given $\mathsf{msk}$ and a function $f$ and outputs a decryption key $\mathsf{fsk}$ tied to $f$. $\mathsf{Dec}$ is given $\mathsf{fsk}$ and $\mathsf{ct}$ and outputs $f(x)$. Then, the indistinguishability-security of SKFE roughly states that any QPT adversary cannot distinguish encryptions of $x_{0}$ and $x_{1}$ under the existence of the encryption oracle and the key generation oracle. Here, the adversary can access the key generation oracle at most $q$ times and can query only a function $f$ such that $f(x_{0})=f(x_{1})$.

An SKFE scheme with secure key leasing (SKFE-SKL) is a tuple of six algorithms $(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\allowbreak\mathpzc{Cert},\mathsf{Vrfy})$, where the first four algorithms form a standard SKFE scheme except the following difference on $\mathpzc{KG}$. In addition to a function $f$, $\mathpzc{KG}$ is given an availability bound $1^{n}$ in terms of the number of ciphertexts. Also, given those inputs, $\mathpzc{KG}$ outputs a verification key $\mathsf{vk}$ together with a decryption key $\mathpzc{fsk}$ tied to $f$ encoded in a quantum state, as $(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$. By using $\mathpzc{Cert}$, we can generate a (classical) certificate that a quantum decryption key $\mathpzc{fsk}$ is deleted, as $\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})$. We check the validity of certificates by using $\mathsf{vk}$ and $\mathsf{Vrfy}$, as $\top/\bot\leftarrow\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$. In addition to the decryption correctness, an SKFE-SKL scheme is required to satisfy the verification correctness that states that a correctly generated certificate is accepted, that is, $\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$ for $(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$ and $\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})$.

The security notion of SKFE-SKL we call lessor security intuitively guarantees that if an adversary given $\mathpzc{fsk}$ deletes it and the generated certificate is accepted within the declared availability bound, the adversary cannot use $\mathpzc{fsk}$ any more. The following indistinguishability experiment formalizes this security notion. For simplicity, we focus on a selective setting where the challenge plaintext pair $(x_{0}^{*},x_{1}^{*})$ and the collusion bound $q$ are fixed outside of the security experiment in this overview.

1. 1.

   Throughout the experiment, $\mathpzc{A}$ can get access to the following oracles, where $L_{\mathtt{\mathpzc{KG}}}$ is a list that is initially empty.

   $O_{\mathtt{\mathsf{Enc}}}(x)$:

   This is the standard encryption oracle that returns $\mathsf{Enc}(\mathsf{msk},x)$ given $x$.

   $O_{\mathtt{\mathpzc{KG}}}(f,1^{n})$:

   This oracle takes as input a function $f$ and an availability bound $1^{n}$, generate $(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$, returns $\mathpzc{fsk}$ to $\mathpzc{A}$, and adds $(f,1^{n},\mathsf{vk},\bot)$ to $L_{\mathtt{\mathpzc{KG}}}$. Differently from the standard SKFE, $\mathpzc{A}$ can query a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$. $\mathpzc{A}$ can get access to the key generation oracle at most $q$ times.

   $O_{\mathtt{\mathsf{Vrfy}}}(f,\mathsf{cert})$:

   Also, $\mathpzc{A}$ can get access to the verification oracle. Intuitively, this oracle checks that $\mathpzc{A}$ deletes leased decryption keys correctly within the declared availability bounds. Given $(f,\mathsf{cert})$, it finds an entry $(f,1^{n},\mathsf{vk},M)$ from $L_{\mathtt{\mathpzc{KG}}}$. (If there is no such entry, it returns $\bot$.) If $\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$ and the number of queries to $O_{\mathtt{\mathsf{Enc}}}$ at this point is less than $n$, it returns $\top$ and updates the entry into $(f,1^{n},\mathsf{vk},\top)$. Otherwise, it returns $\bot$.

2. 2.

   When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if $\mathpzc{A}$ has correctly deleted all leased decryption keys for functions $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$. If so, the challenger gives the challenge ciphertext $\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x_{\mathsf{coin}}^{*})$ for random bit $\mathsf{coin}\leftarrow\{0,1\}$ to $\mathpzc{A}$, and otherwise the challenger output $0$. Hereafter, $\mathpzc{A}$ is not allowed to send a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$ to $O_{\mathtt{\mathpzc{KG}}}$.

3. 3.

   $\mathpzc{A}$ outputs a guess $\mathsf{coin}^{\prime}$ of $\mathsf{coin}$.

We say that the SKFE-SKL scheme is lessor secure if no QPT adversary can guess $\mathsf{coin}$ significantly better than random guessing. We see that if $\mathpzc{A}$ can use a decryption key after once $\mathpzc{A}$ deletes and the deletion certificate is accepted, $\mathpzc{A}$ can detect $\mathsf{coin}$ with high probability since $\mathpzc{A}$ can obtain a decryption key for $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$. Thus, this security notion captures the above intuition. We see that lessor security implies standard indistinguishability-security for SKFE.

We basically work with the above indistinguishability based selective security for simplicity. In Appendix B, we also provide the definitions of adaptive security and simulation based security notions and general transformations to achieve those security notions from indistinguishability based selective security.

In SKFE-SKL, we can set the availability bound for each decryption key differently. We can also consider a weaker variant where we statically set the single availability bound applied to each decryption key at the setup algorithm. We call this variant SKFE with static bound secure key leasing (SKFE-sbSKL). In fact, by using a technique developed in the context of dynamic bounded collusion FE [AMVY21, GGLW21], we can generically transform SKFE-sbSKL into SKFE-SKL if the underlying SKFE-sbSKL satisfies some additional security property and efficiency requirement. For the overview of this transformation, see Section 3.2. Therefore, we below focus on how to achieve SKFE-sbSKL. For simplicity, we ignore those additional properties required for the transformation to SKFE-SKL.

We start with a simple construction of an SKFE-sbSKL scheme secure for the availability bound $0$ based on an SKE scheme with certified deletion [BI20, HMNY21]. The availability bound is $0$ means that it is secure if an adversary deletes decryption keys without seeing any ciphertext.

SKE with certified deletion consists of five algorithms $(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$. The first three algorithms form a standard SKE scheme except that $\mathpzc{Enc}$ output a verification key $\mathsf{vk}$ together with a ciphertext encoded in a quantum state $\mathpzc{ct}$. By using $\mathpzc{Del}$, we can generate a (classical) certificate that $\mathpzc{ct}$ is deleted. The certificate is verified using $\mathsf{vk}$ and $\mathsf{Vrfy}$. In addition to the decryption correctness, it satisfies the verification correctness that guarantees that a correctly generated certificate is accepted. The security notion roughly states that once an adversary deletes a ciphertext $\mathpzc{ct}$ and the generated certificate is accepted, the adversary cannot obtain any plaintext information encrypted inside $\mathpzc{ct}$, even if the adversary is given the secret key after the deletion.

We now construct an SKFE-sbSKL scheme $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ that is secure for the availability bound $0$, based on a standard SKFE scheme $\mathsf{SKFE}=(\mathsf{Setup},\mathsf{KG},\allowbreak\mathsf{Enc},\mathsf{Dec})$ and an SKE scheme with certified deletion $\mathsf{CDSKE}=(\mathsf{CD}.\mathsf{KG},\mathsf{CD}.\mathpzc{Enc},\allowbreak\mathsf{CD}.\mathpzc{Dec},\mathsf{CD}.\mathpzc{Del},\mathsf{CD}.\mathsf{Vrfy})$. In the setup of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$, we generate $\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})$ and $\mathsf{cd}.\mathsf{sk}\leftarrow\mathsf{CD}.\mathsf{KG}(1^{\lambda})$, and the master secret key of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ is set to $\mathsf{zmsk}=(\mathsf{msk},\mathsf{cd}.\mathsf{sk})$. To generate a decryption key for $f$, we generate a decryption key for $f$ by $\mathsf{SKFE}$ as $\mathsf{fsk}\leftarrow\mathsf{KG}(\mathsf{msk},f)$ and encrypt it by $\mathsf{CDSKE}$ as $(\mathsf{cd}.\mathpzc{ct},\mathsf{vk})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk},\mathsf{fsk})$. The resulting decryption key is $\mathpzc{zfsk}\coloneqq\mathsf{cd}.\mathpzc{ct}$ and the corresponding verification key is $\mathsf{vk}$. To encrypt a plaintext $x$, we just encrypt it by $\mathsf{SKFE}$ as $\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{msk},x)$ and append $\mathsf{cd}.\mathsf{sk}$ contained in $\mathsf{zmsk}$, as $\mathsf{zct}\coloneqq(\mathsf{ct},\mathsf{cd}.\mathsf{sk})$. To decrypt $\mathsf{zct}$ with $\mathpzc{zfsk}$, we first retrieve $\mathsf{fsk}$ from $\mathsf{cd}.\mathsf{ct}$ and $\mathsf{cd}.\mathsf{sk}$, and compute $f(x)\leftarrow\mathsf{Dec}(\mathsf{fsk},\mathsf{ct})$. The certificate generation and verification are simply defined as those of $\mathsf{CDSKE}$ since $\mathpzc{zfsk}$ is a ciphertext of $\mathsf{CDSKE}$.

The security of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ is easily analyzed. Let $(x_{0}^{*},x_{1}^{*})$ be the challenge plaintext pair. When an adversary $\mathpzc{A}$ queries $f$ to $O_{\mathtt{\mathpzc{KG}}}$, $\mathpzc{A}$ is given $\mathpzc{zfsk}\coloneqq\mathsf{cd}.\mathpzc{ct}$, where $\mathsf{fsk}\leftarrow\mathsf{KG}(\mathsf{msk},f)$ and $(\mathsf{cd}.\mathpzc{ct},\mathsf{vk})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk},\mathsf{fsk})$. If $f(x_{0}^{*})\neq f(x_{1}^{*})$, $\mathpzc{A}$ is required to delete $\mathpzc{zfsk}$ without seeing any ciphertext. This means that $\mathpzc{A}$ cannot obtain $\mathsf{cd}.\mathsf{sk}$ before $\mathpzc{zfsk}$ is deleted. Then, from the security of $\mathsf{CDSKE}$, $\mathpzc{A}$ cannot obtain any information of $\mathsf{fsk}$. This implies that $\mathpzc{A}$ can obtain a decryption key of $\mathsf{SKFE}$ only for a function $f$ such that $f(x_{0}^{*})=f(x_{1}^{*})$, and thus the lessor security of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ follows form the security of $\mathsf{SKFE}$.

We now explain how to amplify the availability bound from $0$ to any polynomial $n$. One possible solution is to rely on the techniques for bounded collusion FE [GVW12, AV19]. Although the bounded collusion techniques can be used to amplify “$1$-bounded security” to “poly-bounded security”, it is not clear how to use it starting from “$0$-bounded security”. For more detailed discussion on this point, see Remark 3.7. Therefore, we use a different technique from the existing bounded collusion FE. At a high level, we reduce the task of amplifying the availability bound to the task of amplifying the security bound, which has been studied in the context of standard FE [AJL⁺19, JKMS20].

We observe that we can obtain an SKFE-sbSKL scheme with availability bound $n$ for any $n$ that is secure with only inverse polynomial probability by just using many instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ in parallel. Concretely, suppose we use $N=\alpha n$ instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ to achieve a scheme with availability bound $n$, where $\alpha\in\mathbb{N}$. To generate a decryption key for $f$, we generate $(\mathpzc{zfsk}_{j},\mathsf{vk}_{j})\leftarrow\mathpzc{zKG}(\mathsf{zmsk}_{j},f)$ for every $j\in[N]$, and set the resulting decryption key as $(\mathpzc{zfsk}_{j})_{j\in[N]}$ and the corresponding verification key as $(\mathsf{vk}_{j})_{j\in[N]}$. To encrypt $x$, we randomly choose $j\leftarrow[N]$, generate $\mathsf{zct}_{j}\leftarrow\mathsf{zEnc}(\mathsf{zmsk}_{j},x)$, and set the resulting ciphertext as $(j,\mathsf{zct}_{j})$. To decrypt this ciphertext with $(\mathpzc{zfsk}_{j})_{j\in[N]}$, we just compute $f(x)\leftarrow\mathpzc{zDec}(\mathpzc{zfsk}_{j},\mathsf{zct}_{j})$. The certification generation and verification are done by performing them under all $N$ instances. The security of this construction is analyzed as follows. The probability that the $j^{*}$ chosen when generating the challenge ciphertext collides with some of $n$ indices $j_{1},\cdots,j_{n}$ used by the first $n$ calls of the encryption oracle, is at most $n/N=1/\alpha$. If such a collision does not happen, we can use the security of $j^{*}$-th instance of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ to prove the security of this construction. Therefore, this construction is secure with probability roughly $1-1/\alpha$ (denoted by $1/\alpha$-secure scheme).

Thus, all we have to do is to convert an SKFE-sbSKL scheme with inverse polynomial security into one with negligible security. As stated above, such security amplification has been studied for standard FE. In this work, we adopt the amplification technique using homomorphic secret sharing (HSS) [AJL⁺19, JKMS20].

In this overview, we describe our construction using HSS that requires the LWE assumption with super-polynomial modulus to give a high-level intuition. However, our actual construction uses a primitive called set homomorphic secret sharing (SetHSS) [JKMS20], which is a weak form of HSS and can be based on OWFs. ⁴⁴4The definition of HSS provided below is not standard. We modify the definition to be close to SetHSS. Note that HSS defined below can be constructed from multi-key fully homomorphic encryption with simulatable partial decryption property [MW16]. See Section 5 for our construction based on OWFs.

An HSS scheme consists of three algorithms $(\mathsf{InpEncode},\allowbreak\mathsf{FuncEncode},\allowbreak\mathsf{Decode})$. $\mathsf{InpEncode}$ is given a security parameter $1^{\lambda}$, a number $1^{m}$, and an input $x$, and outputs $m$ input shares $(s_{i})_{i\in[m]}$. $\mathsf{FuncEncode}$ is given a security parameter $1^{\lambda}$, a number $1^{m}$, and a function $f$, and outputs $m$ function shares $(f_{i})_{i\in[m]}$. $\mathsf{Decode}$ takes a set of evaluations of function shares on their respective input shares $(f_{i}(s_{i}))_{i\in[m]}$, and outputs a value $f(x)$. Then, the security property of an HSS scheme roughly guarantees that for any $(i^{*},x_{0}^{*},x_{1}^{*})$, given a set of input shares $(s_{i})_{i\in[m]\setminus\{i^{*}\}}$ for some $i^{*}$, an adversary cannot detect from which of the challenge inputs they are generated, under the existence of function encode oracle that is given $f$ such that $f(x_{0}^{*})=f(x_{1}^{*})$ and returns $(f_{i}(s_{i}))_{i\in[m]}$.

We describe SKFE-sbSKL scheme $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ with the availability bound $n\geq 1$ of our choice using a HSS scheme $\mathsf{HSS}=(\mathsf{InpEncode},\allowbreak\mathsf{FuncEncode},\mathsf{Decode})$. In the setup of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first set up $1/2$-secure SKFE-sbSKL scheme $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ with the availability bound $n$. This is done by parallelizing $2n$ instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ as explained before. We generate $m$ master secret keys $\mathsf{msk}_{1},\cdots,\mathsf{msk}_{m}$ of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$. Then, to generate a decryption key for $f$ by $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first generate $(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(1^{\lambda},1^{m},f)$, and generate a decryption key $\mathpzc{fsk}_{i}$ tied to $f_{i}$ under $\mathsf{msk}_{i}$ for each $i\in[m]$. To encrypt $x$ by $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first generate $(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(1^{\lambda},1^{m},x)$ and generate a ciphertext $\mathsf{ct}_{i}$ of $s_{i}$ under $\mathsf{msk}_{i}$ for each $i\in[m]$. The certification generation and verification are done by performing those of $\mathsf{SKFE\textrm{-}SKL}^{\prime}$ for all of the $m$ instances. When decrypting the ciphertext $(\mathsf{ct}_{i})_{i\in[m]}$ by $(\mathpzc{fsk}_{i})_{i\in[m]}$, we can obtain $f_{i}(s_{i})$ by decrypting $\mathsf{ct}_{i}$ with $\mathpzc{fsk}_{i}$ for every $i\in[m]$. By combining $(f_{i}(s_{i}))_{i\in[m]}$ using $\mathsf{Decode}$, we can obtain $f(x)$.

The lessor security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ can be proved as follows. Each of $m$ instances of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ is secure independently with probability $1/2$. Thus, there is at least one secure instance without probability $1/2^{m}$, which is negligible by setting $m=\omega(\log\lambda)$. Suppose $i^{*}$-th instance is a secure instance. Let $(x_{0}^{*},x_{1}^{*})$ be the challenge plaintext pair, and let $(s^{*}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(1^{\lambda},1^{m},x^{*}_{\mathsf{coin}})$ for $\mathsf{coin}\leftarrow\{0,1\}$. In the security experiment, from the security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ under $\mathsf{msk}_{i^{*}}$, an adversary cannot obtain the information of $s_{i^{*}}$ except for its evaluation on function shares for a function $f$ queried to $O_{\mathtt{\mathpzc{KG}}}$ that satisfies that $f(x_{0}^{*})=f(x_{1}^{*})$. Especially, from the security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ under $\mathsf{msk}_{i^{*}}$, the adversary cannot obtain an evaluation of $s_{i^{*}}$ on function shares for a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$, though $\mathpzc{A}$ can query such a function to $O_{\mathtt{\mathpzc{KG}}}$. Then, we see that the lessor security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ can be reduced to the security of $\mathsf{HSS}$. ⁵⁵5Actual construction and security proof needs to use a technique called the trojan method [ABSV15]. We ignore the issue here for simplicity.

In the actual construction, we use SetHSS instead of HSS, as stated before. Also, in the main body, we abstract the parallelized $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ as index-based SKFE-sbSKL. This makes the security proof of our construction using SetHSS simple. Moreover, in the actual construction of an index-based SKFE-sbSKL, we bundle the parallelized instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ using a PRF. This modification is necessary to achieve the efficiency required for the above transformation into SKFE-SKL.

Goyal et al. [CGO21] use a similar technique using HSS in a different setting (private simultaneous message protocols). However, their technique relies on the LWE assumption unlike ours.

In this work, we also define the notion of single decryptor PKFE, which is PKFE whose functional decryption key is copy-protected. The definition is a natural extension of SDE (PKE with copy-protected decryption keys). An adversary $\mathpzc{A}$ tries to copy a target functional decryption key $\mathpzc{sk}_{f^{\ast}}$. More specifically, $\mathpzc{A}$ is given $\mathpzc{sk}_{f^{\ast}}$ and outputs two possibly entangled quantum distinguishers $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$ and two plaintexts $(x_{0},x_{1})$ such that $f^{\ast}(x_{0})\neq f^{\ast}(x_{1})$. If $\mathpzc{D}_{1}$ or $\mathpzc{D}_{2}$ cannot distinguish a given ciphertext is encryption of $x_{0}$ or $x_{1}$, $\mathpzc{sk}_{f^{\ast}}$ is copy-protected.⁶⁶6In the security definition of SDE, quantum decryptors try to recover the entire plaintext [CLLZ21]. We extend the definition because quantum decryptors are not sufficient for using SDFE as a building block. See Section 7 for detail. If both $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$ have $\mathpzc{sk}_{f^{\ast}}$, they can trivially distinguish the challenge ciphertext. Thus, the definition guarantees copy-protection security. We provide a collusion-resistant single-decryptor PKFE scheme, where adversaries obtain polynomially many functional decryption keys, based on IO.

We first show that a single-key single-decryptor PKFE can be constructed from a single-key standard PKFE scheme and SDE scheme. The construction is simple nested encryption. Namely, when encrypting a plaintext $x$, we first encrypt it by the standard PKFE scheme and then encrypt the ciphertext by the SDE scheme. The secret key of the SDE scheme is included in the functional decryption key of the resulting single-decryptor PKFE scheme. Although a PKFE functional decryption key can be copied, the SDE decryption key cannot be copied and adversaries cannot break the security of PKFE. This is because we need to run the SDE decryption algorithm before we run the PKFE decryption algorithm.

The security notion for SDE by Coladangelo et al. [CLLZ21] is not sufficient for our purpose since SDE plaintexts are ciphertexts of the standard PKFE in the construction. We need to extend the security notion for SDE to prove the security of this construction because we need to handle randomized messages (the PKFE encryption is a randomized algorithm). Roughly speaking, this new security notion guarantees that the security of SDE holds for plaintexts of the form $g(x;r)$, where $g$ and $x$ respectively are a function and an input chosen by an adversary and $r$ is a random coin chosen by the experiment. We can observe that the SDE scheme proposed by Coladangelo et al. [CLLZ21] based on IO satisfies this security notion. Then, by setting $g$ as the encryption circuit of the standard PKFE, the security of the single-key single-decryptor PKFE scheme above can be immediately reduced to the security of the SDE scheme. We also extend adversarial quantum decryptors, which try to output an entire plaintext, to adversarial quantum distinguishers, which try to guess a $1$-bit coin used to generate a ciphertext. We need this extension to use SDE as a building block. It is easy to observe the SDE scheme by Coladangelo et al. [CLLZ21] is secure even against quantum distinguishers.

Once we obtain a single-key single-decryptor PKFE scheme, we can transform it into a collusion-resistant single-decryptor PKFE scheme by again using IO. This transformation is based on one from a single-key standard PKFE scheme into a collusion-resistant standard PKFE scheme [BNPW20, KNT21]. The idea is as follows. We need to generate a fresh instance of the single-key scheme above for each random tag and bundle (unbounded) polynomially many instances to achieve collusion-resistance. We use IO to bundle multiple instances of single-key SDFE. More specifically, a public key is an obfuscated circuit of the following setup circuit. The setup circuit takes a public tag $\tau$ as input, generates a key pair $(\mathsf{pk}_{\tau},\mathsf{msk}_{\tau})$ of the single-key SDFE scheme using PRF value $\mathsf{F}_{\mathsf{K}}(\tau)$ as randomness, and outputs only $\mathsf{pk}_{\tau}$. The master secret key is the PRF key $\mathsf{K}$. We can generate a functional decryption key for $f$ by choosing a random tag $\tau$ and generating a functional decryption key $\mathpzc{sk}_{f,\tau}$ under $\mathsf{msk}_{\tau}$. A functional decryption key of our collusion-resistant scheme consists of $(\tau,\mathpzc{sk}_{f,\tau})$. A ciphertext is an obfuscated circuit of the following encryption circuit, where a plaintext $x$ is hardwired. The encryption circuit takes a public tag $\tau$, generates $\mathsf{pk}_{\tau}$ by using the public key explained above, and outputs a ciphertext of $x$ under $\mathsf{pk}_{\tau}$. Due to this mechanism, only one functional decryption key $\mathpzc{sk}_{f,\tau}$ under $\mathsf{msk}_{\tau}$ is issued for each $\tau$, but we can generate polynomially many functional decryption keys by using many tags. If we use a different tag $\tau^{\prime}$, an independent key pair $(\mathsf{pk}_{\tau^{\prime}},\mathsf{msk}_{\tau^{\prime}})$ is generated and it is useless for another instance under $(\mathsf{pk}_{\tau},\mathsf{msk}_{\tau})$. The IO security guarantees that the information about $\mathsf{K}$ (and $\mathsf{msk}_{\tau}$) is hidden.⁷⁷7We use puncturable PRFs and the puncturing technique here as the standard technique for cryptographic primitives based on IO [SW21]. Thus, we can reduce the collusion-resistance to the single-key security of the underlying single-decryptor PKFE. Note that we need to consider super-polynomially many hybrid games to complete the proof since the tag space size must be super-polynomial to treat unbounded polynomially many tags. This is the reason why we need the sub-exponential security for building blocks.

Ananth and La Place [AL21] achieve secure software leasing for $\mathsf{subEVS}$ from the QLWE assumption and IO. Kitagawa, Nishimaki, and Yamakawa [KNY21] achieve secure software leasing for PRFs and $\mathsf{subEVS}$ only from the QLWE (that is, without IO). Broadbent, Jeffery, Lord, Podder, and Sundaram [BJL⁺21] achieve secure software leasing for $\mathsf{subEVS}$ without assumptions. Coladangelo, Majenz, and Poremba [CMP20] also achieve secure software leasing for $\mathsf{subEVS}$ in the quantum random oracle (QROM) model (without assumptions).

In secure software leasing, we force adversaries to run pirate software by an honest evaluation algorithm denoted by $\mathpzc{Run}$ [AL21]. An honest evaluation algorithm verifies the format of software when software is executed, and adversaries cannot adopt arbitrary strategies for creating pirate software. Aaronson, Liu, Liu, Zhandry, and Zhang [ALL⁺21] introduce copy-detection, which is essentially the same notion as secure software leasing. Although a check algorithm verifies returned software, there is no honest evaluation algorithm, and adversaries can adopt arbitrary strategies in the copy-detection setting. Aaronson et al. [ALL⁺21] achieve copy-detection for PRFs, PKE, and signatures from IO and standard cryptographic assumptions. Those cryptographic functionalities are much weaker than FE. Moreover, we need IO to achieve security against adversaries that adopt any strategy to execute pirate software. Secure software leasing by Coladangelo et al. [CMP20] is also secure against such arbitrary adversaries, but their construction relies on QROM, and its functionality is severely limited.

Broadbent and Islam [BI20] present the notion of quantum encryption with certified deletion. They achieve one-time SKE with certified deletion without assumptions. Hiroka, Morimae, Nishimaki, and Yamakawa [HMNY21] extend the notion to reusable SKE, PKE, and ABE with certified deletion, and instantiate them with standard SKE, PKE, and IO and OWFs, respectively. Our FE with secure key leasing can also be seen as certified deletion for functional decryption keys.

Aaronson [Aar09] achieves copy-protection for arbitrary unlearnable Boolean functions relative to a quantum oracle, and presents two heuristic copy-protection schemes for point functions. Aaronson et al. [ALL⁺21] achieve quantum copy-protection for all unlearnable functions by using classical oracles. Georgiou and Zhandry [GZ20] present the notion of SDE and instantiate it with one-shot signatures [AGKZ20] and extractable witness encryption (WE) [GKP⁺13]. They also introduce the notion of broadcast encryption with unclonable decryption and splittable ABE, which can be seen as copy-protected variants of broadcast encryption and ABE, respectively. They instantiate splittable ABE with the same tools as those for SDE. They instantiate broadcast encryption with unclonable decryption with tokenized signatures [BS17], extractable WE, and collision-resistant hash functions. Coladangelo et al. [CLLZ21] achieve quantum copy-protection for PRFs and SDE from IO and OWFs, the QLWE assumption, and the strong monogamy-of-entanglement conjecture. Later, Culf and Vidick prove that the strong monogamy-of-entanglement conjecture is true without any assumption [CV21]. Those cryptographic functionalities are weaker than FE, as in the case of secure software leasing. Most of those works rely on magical oracles or knowledge-type assumptions such as the existence of extractable WE, which is implausible [GGHW17]. Only the constructions by Coladangelo et al. [CLLZ21, CV21] do not rely on such strong tools. However, note that there is no provably secure post-quantum IO from well-founded assumptions so far.⁸⁸8There are some candidates [BGMZ18, CHVW19, AP20, DQV⁺21]. The known IO constructions from well-founded assumptions [JLS21, JLS22] are vulnerable against quantum adversaries.

Ben-David and Sattath [BS17] present the notion of tokenized signatures, where we can generate a delegated signing token from a signing key. A signing token enables a user to sign one and only one message. They instantiate it with virtual black-box obfuscation [BGI⁺12]. Amos, Georgiou, Kiayias, and Zhandry present the notion of one-shot signatures, where adversaries cannot generate two valid signatures for different two messages even under an adversarially generated verification key. They instantiate it with classical oracles, which can be seen as an idealized virtual black-box obfuscation. Those are copy-protected variants of signatures. Relationships between (copy-protected) FE and them are not known so far.

FE has been extensively studied since Boneh, Sahai, and Waters [BSW11] formally defined its notion. Although there are many works on FE, we focus on FE for $\mathsf{P}/\mathsf{poly}$ that are closely related to our work in this paper.

Sahai and Seyalioglu [SS10] present the first (selectively secure) single-key PKFE for $\mathsf{P}/\mathsf{poly}$ from PKE. Gorbunov, Vaikuntanathan, and Wee [GVW12] present transformations from (adaptively secure) single-key PKFE for $\mathsf{NC}^{1}$ into (adaptively secure) bounded collusion-resistant PKFE for $\mathsf{P}/\mathsf{poly}$ by using pseudorandom generators (PRGs) in $\mathsf{NC}^{1}$. The transformation also converts single-key and many-ciphertext SKFE for $\mathsf{NC}^{1}$ into bounded collusion-resistant and many-ciphertext SKFE for $\mathsf{P}/\mathsf{poly}$. They also show that we can achieve adaptively secure single-key PKFE (resp. SKFE) for $\mathsf{NC}^{1}$ from PKE (resp. OWFs). Ananth, Brakerski, Segev, and Vaikuntanathan [ABSV15] observe that we can invert the roles of the functions and plaintexts in SKFE by using the function-privacy of SKFE [BS18], and obtain collusion-resistant and bounded many-ciphertext SKFE for $\mathsf{P}/\mathsf{poly}$ from OWFs by using the transformations. Later, Ananth and Vaikuntanathan [AV19] improve the assumptions (remove PRGs in $\mathsf{NC}^{1}$) for the transformation and achieve the optimal ciphertext size (in the asymptotic sense). These transformations [GVW12, AV19] run $N$ independent copies of a single-key FE scheme and encrypt the views of some $N$-party multi-party computation (MPC) protocol. Agrawal and Rosen [AR17] construct bounded collusion-resistant PKFE for $\mathsf{NC}^{1}$ by using FE for inner-product [ABDP15, ALS16] and the homomorphic property of some encryption scheme [BV11].⁹⁹9We can upgrade FE for $\mathsf{NC}^{1}$ to FE for $\mathsf{P}/\mathsf{poly}$ by using randomized encoding [ABSV15]. Their construction supports arithmetic circuits. Agrawal, Maitra, Vempati, and Yamada [AMVY21] and Garg, Goyal, Lu, and Waters [GGLW21] concurrently and independently present the notion of dynamic bounded collusion-resistant FE and how to achieve it from identity-based encryption (IBE). In the dynamic bounded collusion setting, the setup algorithm of FE does not depend on the number of key queries, and only the encryption algorithm of FE depends on it.

Security amplification is transforming an $\epsilon$-secure cryptographic scheme into a $\nu$-secure one, where $\epsilon\in(0,1)$ is a constant and $\nu$ is a negligible function. Ananth, Jain, Lin, Matt, and Sahai [AJL⁺19] propose security amplification techniques for standard FE. Their techniques are based on multi-key homomorphic encryption, which can be instantiated with the LWE assumption. Jain, Korb, Manohar, and Sahai [JKMS20] also propose how to amplify the security of standard FE by using SetHSS, which can be instantiated with OWFs.

IO for $\mathsf{P}/\mathsf{poly}$ is necessary and sufficient for collusion-resistant FE (for $\mathsf{NC}^{1}$) up to sub-exponential security loss [GGH⁺16, BV18, AJ15, AJS15, KNT22]. Jain, Lin, and Sahai [JLS21, JLS22] achieve the first IO (and collusion-resistant FE for $\mathsf{P}/\mathsf{poly}$) from well-founded assumptions. However, they are not post-quantum secure since the constructions heavily rely on cryptographic bilinear maps.

Revocation mechanisms have been extensively studied, especially in the context of broadcast encryption [NP01, NNL01].¹⁰¹⁰10We omit references since there are too many previous works on broadcast encryption and trace-and-revoke systems. Nishimaki et al. [NWZ16] introduce revocable FE to achieve a trace-and-revoke system with flexible identities. They achieve the first revocable FE by using IO and OWFs. We need to manage a revocation list and update ciphertexts to revoke a user.